一種提升細粒度日志解析準確度的方法

葛志輝，邱 晨，李陶深，葉 進

(廣西大學 計算機與電子信息學院，南寧 530004)

1 引 言

在當今不斷變化的數字世界中，幾乎所有的計算系統都被設計成將其運行狀態、環境變化、配置修改和錯誤等信息記錄到某種事件日志中(例如系統日志或應用程序日志).日志被開發人員和操作人員廣泛用于確保系統可靠性，因為它們通常是在生產環境中記錄詳細的系統運行時信息的唯一可用數據，每一個字段包括事件的發生時間、級別和任務執行的狀態等運行時的信息.原始日志消息通常是非結構化的，要實現日志分析，第一步也是最重要的一步是日志解析[1]，這是一個將自由文本原始日志消息解析為結構化事件和事件分類的過程.隨著現代系統的規模和復雜性的不斷增加，日志的數量也在快速增長，每小時以GB級別的速度增長[2].目前許多最近的研究以及工業解決方案，已經發展到提供強大的文本搜索和基于機器學習的分析功能，具有較高的解析準確度.然而，對于大多數系統日志存在不同比例的細粒度日志，現有的日志解析器無法正確解析這些日志，導致整體解析準確度不高的問題.例如：分布式系統日志HDFS的事件等長率占比為93%，以此對應的可變長度日志占比為7%，因為這些解析器選取日志長度作為粗分類的特征，導致不同長度但具有相同事件的日志相互分離，造成額外的事件分類；此外，在計算日志相似度時也容易忽略日志的狀態變量帶來的影響，該系統日志有19%的錯誤合并事件，造成必要事件的減少.因此，如何正確分類細粒度日志以提升自動化日志解析的整體準確度成為一個備受關注的重要研究問題.我們提出一個結合常量令牌長度特征的決策樹解析模型，在完成日志分類的基礎上提升細粒度日志解析的有效性，從而提高解析器整體的準確度，這有利于后續使用相關機器學習算法進行日志分析.

2 相關研究

為了實現日志自動化解析，提升日志解析準確度，學術界和工業界提出了許多數據驅動方法，能夠從日志數據中學習模式并自動生成公共事件模板[3].主要分為聚類和迭代分區方法.Cheng等人[4]結合Canopy聚類和K-means聚類算法用于提升錯誤日志的分類方法，Zhong和Guo[5]改進logSig聚類算法以提升解析準確度.然而聚類算法需要計算每個日志文本之間的距離，時間開銷巨大，而迭代分區技術在運行時間上更為高效.迭代分區技術將所有日志消息聚集到粗分區中，然后迭代地劃分粗分區，以創建所有日志消息都對應于單個模板的集群.LKE算法[6]使用層次聚類技術，通過計算每對日志消息的編輯距離來創建初始集群，這使得這個過程在內存和計算利用率方面都非常昂貴，并且無法在有限的時間內處理數據量較大的任務；IPLoM算法[7]根據行中的令牌數量創建初始集群，它們進一步識別在給定位置出現最頻繁的令牌，并在這些令牌位置上分割集群，此方法在運行效率上具有優勢，但是整體解析準確度偏低；Spell算法[8]使用前綴樹劃分日志集群，在計算文本相似度和事件生成時使用最長公共子序列算法(LCS)，但沒有限制前綴樹的深度，LCS容易導致過度分區，在事件較多的日志集中也存在準確度不高的情況；Drain算法[9]使用結合日志長度的固定深度樹來表示日志消息，并有效地提取通用模板，然而沒有考慮細粒度日志的存在，在事件等長占比率低、事件數較多的日志集中存在解析準確度不高的情況.在日志解析中，細粒度日志分類是解析器的一大難點，目前考慮細粒度日志劃分的日志解析研究相對較少.對于提升整體解析準確度而言，研究細粒度日志劃分有著重要意義.

另一類工作為提升細粒度日志分類的研究.POP算法[10]的結構與Drain類似，它還使用層次聚類進一步將相似的事件合并，雖然獲得了目前解析器最高的整體水平，仍沒有解決狀態變量導致的細粒度日志錯誤合并.Guo[11]采用離線層次化解析來實現不同粒度下的日志解析，以及改進的基本簽名生成算法來確保狀態變量保持低熵，剝離需要考慮狀態變量的日志，但是額外的模型勢必造成額外的時間開銷，不能確保在一個模型中解決多個粒度日志的問題.因此，提出一種用于日志解析的結合常量令牌長度特征的決策樹方法，用于解決長度可變的或含有狀態變量的細粒度日志劃分問題.

3 CLDT日志解析模型

本文設計一個結合常量令牌長度特征的樹狀結構(CLDT，decision tree with constant lenth)來幫助日志組的搜索.模型主要包括數據預處理、決策樹搜索、相似度計算與事件生成、更新決策樹.其中，常量令牌指的是日志文本中的不變部分，而狀態變量屬于不含參數的可變部分.

3.1 按照常量令牌長度搜索

大部分解析方法基于這樣的假設：具有相同日志事件的日志消息可能具有相同的日志消息長度.然而，即便具有不等長度的日志消息也可能屬于同一事件.這使得具有可變長度的同一類型日志相互分離.在此步驟中，決策樹選擇常量令牌長度(conLen，Constant token length)作為日志消息的特征，使用conLen可以有效合并具有可變長度的日志類型，因為它們日志長度不同，但conLen卻是相同的.對于包含n個令牌T的日志序列seq={T1，T2，T3，…，Tn}，conLen表示為式(1)：

(1)

其中，c表示常量令牌，ρ表示變量令牌.

3.2 按照常量令牌搜索

狀態變量在系統日志中尤為重要，具有不同狀態變量的日志往往不屬于同一類型.傳統的解析方法將狀態變量歸為含參變量來處理，這會導致具有不同狀態的日志歸為同一類.通常狀態變量的形式與常量令牌相同，借助常量令牌的搜索可以有效地保留狀態變量.具體地說，決策樹制定參數特征，通過日志消息開始位置的標記選擇下一個搜索節點，當遇到匹配參數特征的令牌時會略過此令牌的搜索，只對常量令牌以及常量形式的狀態變量進行搜索.這一步有效地保留了狀態變量，以防錯誤的事件合并.如圖1所示：‘PacketResponder 1 for block <*> terminating’和‘PacketResponder 0 for block <*> Interrupted’，這兩類日志很容易合并，它們都有4個常量令牌，如果樹的深度為6層(包括根節點和葉節點2層)，決策樹根據常量令牌‘PacketResponder’、‘fo’、‘block’及對應的狀態變量來指導搜索過程，‘terminating’和‘Interrupted’因此得到保留.

圖1 一棵深度為6的決策樹

3.3 改進的相似度計算

其他解析方法通常考慮完整的日志消息與事件模板的相似度，然而相似度會受到參數變量的影響，通常不會對日志分類有太大的幫助.在此步驟中，決策樹考慮常量令牌并計算日志消息與事件模板的相似度logSim，確定日志的最終歸類.logSim的定義如式(2)所示：

(2)

其中event和log分別表示日志事件和日志消息；event(i)表示事件模板的第i個常量令牌；log(i)表示日志消息的第i個常量令牌；n表示常量令牌比較的次數；函數comToken定義如式(3)所示：

(3)

其中tc1和tc2分別表示event和log的常量令牌.如圖2所示，在找到logSim最大的日志組之后，將其與預定義的相似閾值st進行比較.如果logSim≥st，決策樹將這一日志消息添加到該日志組.否則，決策樹將新建一個日志組.

圖2 事件生成

3.4 更新決策樹

如圖3所示，每當決策樹學習新的日志，決策樹從根節點遍歷到應該包含新日志組的葉子節點，并相應地沿著路徑添加缺少的conLen節點、常量令牌節點和葉子節點.

圖3 更新決策樹

本文提出一種面向細粒度日志的CLDT解析模型.操作步驟如下：Begin

Step 1.設置全局變量、樹的深度和相似度閾值；

Step 2.日志切割、使用正則表達式將日志消息進行預處理；

Step 3.計算日志消息的常量令牌長度，若決策樹存在該長度節點，執行Step 3.1，否則執行Step 3.2；

Step 3.1選擇對應的第一層長度節點；

Step 3.2創建對應的長度節點；

Step 4.常量令牌與節點匹配搜索，若存在節點，則執行Step 4.1，否則執行Step 4.2；

Step 4.1匹配完畢后選擇到下一層節點，重復執行Step 4；

Step 4.2創建對應的搜索節點；

Step 5.日志消息抵達葉節點，計算日志與列表中每個日志組事件模板的相似度，若最大相似度大于閾值，執行Step 5.1，否則執行Step 5.2；

Step 5.1日志消息與最大相似度的日志組以頻繁項生成事件模板；

Step 5.2在此列表中生成新的日志組，事件模板就是此日志消息.

End

4 實驗結果

4.1 評價指標

4.1.1 F-measure

使用F-measure這一典型的算法評價指標來評價日志解析方法.F-measure的定義如下：

(4)

其中精度(Precision)和召回率(Recall)定義如下：

(5)

其中，真陽性(TP，True Positive)表示將兩個具有相同事件的日志消息分配給相同的日志組；假陽性(FP，False Positive)表示將兩個具有不同事件的日志消息分配給同一個日志組；假陰性(FN，False Negative)表示將兩個具有相同事件的日志消息分配給不同的日志組.

4.1.2 Accuracy

準確度(Accuracy)指標定義為正確解析的日志消息與日志消息總數的比值[3].當且僅當日志消息的事件模板與真實數據(ground truth)對應的同一組日志消息相同時，日志消息才被認為是正確解析的.Accuracy的定義如下：

(6)

其中，假陰性(TN，True Negative)表示將兩個具有不相同事件的日志消息分配給不同的日志組.

4.2 實驗設置

采用HPC、Zookeeper、HDFS數據集[3](如表1所示)進行實驗，首先通過小樣本數據來綜合評價解析器的Precision、Recall、F-measure、Accuracy；然后在不同規模的數據集中(如表2所示)比較CLDT、Drain、Spell、IPLoM的準確度和運行效率來評估解析器的性能.參數涉及樹的深度(depth)和相似度閾值(st)，經過大量測試，對于不同日志集，決策樹參數設置如表3所示.

表1 日志集描述

表2 數據集的大小劃分(單位：條)

表3 CLDT解析方法的參數設置

4.3 模型評價

我們的評估中從每個數據集隨機抽取2k日志消息.在很多情況下，現有日志解析器的準確度都大于0.8.此外，HDFS數據集的整體準確率高于HPC.我們發現，這主要是因為HPC日志涉及的事件類型要多得多，并且與HDFS、Zookeeper相比，它們具有更多不同的日志長度范圍.

實驗結果如圖4所示，觀察到CLDT為所有這些數據集提供了最佳的解析準確度.對于日志事件相對較少的數據集HDFS，其解析精度為1.00，這意味著所有日志都可以被正確解析.對于具有相對較多日志事件的數據集，CL-DT仍然提供非常高的解析精度，HPC為0.9775.CLDT具有最佳的解析準確度，原因有兩點：首先，可以根據領域知識手動提取日志中某些特有屬性，減少解析過程的噪音；其次，CLDT根據常量令牌長度特征將日志劃分到合適的組，解決了不同長度的日志消息可能屬于同一事件導致無法正確分類的問題，并且借助常量令牌搜索來劃分狀態變量，以防具有不同狀態變量的日志錯誤合并.與其他具有相似結構的決策樹解析器相比，CLDT提供了更細粒度的劃分.

圖4 解析方法在3種數據集的測試評價

4.4 日志解析方法的準確度

先在小樣本數據集上進行參數調優，并直接將它們應用于大型數據.將完整的原始數據集劃分為15個不同規模的數據集.

實驗結果如圖5所示，從實驗中觀察到CLDT對于所有數據集的準確性是非常一致的，即便在小樣本數據上調優參數也能在所有數據集上一致獲得高準確度.對于HDFS、Zookeeper，5個規模的數據集上的準確度都達到了0.99.對于HPC，CLDT最小準確度達到了0.9197.觀察到CLDT在這類日志數據集上準確度表現出一定的波動.在75k數據量上，細粒度日志占比約0.53，CLDT和Drain能夠保證較好的準確度.Spell基于LCS匹配日志與模板，LCS算法容易出現過度區分長度不同的日志與模板，僅能夠正確解析部分含參數變量的日志；IPLoM根據日志長度、令牌位置和映射關系將消息劃分為多個組，Drain結合日志長度和有限令牌將消息劃分為多個組，然而日志長度特征對于可變長度和含狀態變量的日志都不能保證良好的解析準確度；由于CLDT限制了決策樹的深度，在限定層內可以很好的區分狀態變量，常量令牌數量一旦超過樹的深度時，CLDT不能區分后續的狀態變量.但隨著數據量增大(375k的HPC細粒度日志僅為0.14)，各解析算法的準確度逐漸提升.現有的解析算法即便在小規模數據集中具有較高的解析準確度，但是在不同規模數據下仍存在缺陷.與最先進的解析算法Drain相比，CLDT在不同規模的數據集中具有良好的穩定性和較高的準確度.

圖5 解析方法在3種數據集的準確度

在15個采樣數據集上測量這些日志解析器的效率.本文中的效率是指用于運行日志解析器的時間.日志大小對本文解析方法運行時間的影響結果如圖6所示.日志解析運行時間隨著日志大小的增加而增加，并且增長幅度逐漸增加，因為它們的運行時間主要依賴于日志事件的數量和日志長度等因素，解析過程中的正則表達式匹配、日志劃分匹配、相似度計算和模板生成等每個階段的效率也各不相同.

圖6 解析方法在3種數據集的運行效率

4.5 日志解析方法的效率

這些解析方法在日志劃分匹配過程中均采用決策樹結構.Drain的時間復雜度為O((d+cL)n)，其中d為解析樹的深度，c為葉節點中候選日志組的數量，L為日志的令牌數，n為日志消息的數量，d、L、c都可看做常數.而CLDT在搜索時需要判斷令牌類別，與Drain的時間復雜度類似，為O((d+c·conLen)n+conLen)；IPLoM的結構同樣類似，但是需要將所有日志消息加載到計算機內存中，在處理大規模的日志數據時效果欠佳.因此，上述3個解析算法的時間復雜度均為O(n).對于Spell，采用LCS算法并依賴于比較日志的每個令牌，時間復雜度為O(L1·L2)，其中L1和L2分別為日志的令牌數.通過計算日志消息和日志候選事件之間的令牌相似性，相比于LCS可以大幅度降低運行時間，時間復雜度為O(L1+L2)，由于CLDT更具細粒度的劃分，每個日志組的事件數和令牌比較次數更少，因而此階段的運行效率更高.對于不同的日志解析器，每個階段的運行時間各具優勢和不足，但總體而言，它們均采用決策樹結構來劃分日志，所以效率是相似的.

5 結 語

本文提出了結合常量令牌長度特征的決策樹的日志解析模型，在保證一定的執行效率下，解決細粒度日志影響整體解析準確度的問題，進一步提升日志解析的準確度.實驗結果表明，該模型在HDFS、HPC、Zookeeper這3類日志集中獲得準確度提升，與同類解析器相比，具有較高的準確度，運行時間相當.然而，本文提出的模型未考慮參數字段的語義，識別參數語義能夠幫助用戶理解日志.未來的研究可以結合自然語言處理技術來識別參數語義.