葛志輝，邱 晨，李陶深，葉 進(jìn)

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004)

1 引 言

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

2 相關(guān)研究

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

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

3 CLDT日志解析模型

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

3.1 按照常量令牌長(zhǎng)度搜索

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

(1)

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

3.2 按照常量令牌搜索

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

圖1 一棵深度為6的決策樹(shù)

3.3 改進(jìn)的相似度計(jì)算

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

(2)

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

(3)

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

圖2 事件生成

3.4 更新決策樹(shù)

如圖3所示，每當(dāng)決策樹(shù)學(xué)習(xí)新的日志，決策樹(shù)從根節(jié)點(diǎn)遍歷到應(yīng)該包含新日志組的葉子節(jié)點(diǎn)，并相應(yīng)地沿著路徑添加缺少的conLen節(jié)點(diǎn)、常量令牌節(jié)點(diǎn)和葉子節(jié)點(diǎn).

圖3 更新決策樹(shù)

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

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

Step 2.日志切割、使用正則表達(dá)式將日志消息進(jìn)行預(yù)處理；

Step 3.計(jì)算日志消息的常量令牌長(zhǎng)度，若決策樹(shù)存在該長(zhǎng)度節(jié)點(diǎn)，執(zhí)行Step 3.1，否則執(zhí)行Step 3.2；

Step 3.1選擇對(duì)應(yīng)的第一層長(zhǎng)度節(jié)點(diǎn)；

Step 3.2創(chuàng)建對(duì)應(yīng)的長(zhǎng)度節(jié)點(diǎn)；

Step 4.常量令牌與節(jié)點(diǎn)匹配搜索，若存在節(jié)點(diǎn)，則執(zhí)行Step 4.1，否則執(zhí)行Step 4.2；

Step 4.1匹配完畢后選擇到下一層節(jié)點(diǎn)，重復(fù)執(zhí)行Step 4；

Step 4.2創(chuàng)建對(duì)應(yīng)的搜索節(jié)點(diǎn)；

Step 5.日志消息抵達(dá)葉節(jié)點(diǎn)，計(jì)算日志與列表中每個(gè)日志組事件模板的相似度，若最大相似度大于閾值，執(zhí)行Step 5.1，否則執(zhí)行Step 5.2；

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

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

End

4 實(shí)驗(yàn)結(jié)果

4.1 評(píng)價(jià)指標(biāo)

4.1.1 F-measure

使用F-measure這一典型的算法評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)日志解析方法.F-measure的定義如下：

(4)

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

(5)

其中，真陽(yáng)性(TP，True Positive)表示將兩個(gè)具有相同事件的日志消息分配給相同的日志組；假陽(yáng)性(FP，F(xiàn)alse Positive)表示將兩個(gè)具有不同事件的日志消息分配給同一個(gè)日志組；假陰性(FN，F(xiàn)alse Negative)表示將兩個(gè)具有相同事件的日志消息分配給不同的日志組.

4.1.2 Accuracy

準(zhǔn)確度(Accuracy)指標(biāo)定義為正確解析的日志消息與日志消息總數(shù)的比值[3].當(dāng)且僅當(dāng)日志消息的事件模板與真實(shí)數(shù)據(jù)(ground truth)對(duì)應(yīng)的同一組日志消息相同時(shí)，日志消息才被認(rèn)為是正確解析的.Accuracy的定義如下：

(6)

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

4.2 實(shí)驗(yàn)設(shè)置

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

表1 日志集描述

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

表3 CLDT解析方法的參數(shù)設(shè)置

4.3 模型評(píng)價(jià)

我們的評(píng)估中從每個(gè)數(shù)據(jù)集隨機(jī)抽取2k日志消息.在很多情況下，現(xiàn)有日志解析器的準(zhǔn)確度都大于0.8.此外，HDFS數(shù)據(jù)集的整體準(zhǔn)確率高于HPC.我們發(fā)現(xiàn)，這主要是因?yàn)镠PC日志涉及的事件類型要多得多，并且與HDFS、Zookeeper相比，它們具有更多不同的日志長(zhǎng)度范圍.

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

圖4 解析方法在3種數(shù)據(jù)集的測(cè)試評(píng)價(jià)

4.4 日志解析方法的準(zhǔn)確度

先在小樣本數(shù)據(jù)集上進(jìn)行參數(shù)調(diào)優(yōu)，并直接將它們應(yīng)用于大型數(shù)據(jù).將完整的原始數(shù)據(jù)集劃分為15個(gè)不同規(guī)模的數(shù)據(jù)集.

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

圖5 解析方法在3種數(shù)據(jù)集的準(zhǔn)確度

在15個(gè)采樣數(shù)據(jù)集上測(cè)量這些日志解析器的效率.本文中的效率是指用于運(yùn)行日志解析器的時(shí)間.日志大小對(duì)本文解析方法運(yùn)行時(shí)間的影響結(jié)果如圖6所示.日志解析運(yùn)行時(shí)間隨著日志大小的增加而增加，并且增長(zhǎng)幅度逐漸增加，因?yàn)樗鼈兊倪\(yùn)行時(shí)間主要依賴于日志事件的數(shù)量和日志長(zhǎng)度等因素，解析過(guò)程中的正則表達(dá)式匹配、日志劃分匹配、相似度計(jì)算和模板生成等每個(gè)階段的效率也各不相同.

圖6 解析方法在3種數(shù)據(jù)集的運(yùn)行效率

4.5 日志解析方法的效率

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

5 結(jié) 語(yǔ)

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