一種基于MDL的日志序列模式挖掘算法

杜詩晴，王 鵬，汪 衛(wèi)

（1.復(fù)旦大學(xué)軟件學(xué)院，上海 201203；2.復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 201203）

0 概述

日志數(shù)據(jù)記錄了互聯(lián)網(wǎng)系統(tǒng)運(yùn)行時的狀態(tài)以及任務(wù)的開始與結(jié)束等重要事件，其易于獲取且含有豐富的信息，已經(jīng)成為系統(tǒng)運(yùn)維領(lǐng)域的重要數(shù)據(jù)源。系統(tǒng)運(yùn)行產(chǎn)生的日志數(shù)據(jù)可被視作時序事件序列，利用序列模式挖掘技術(shù)可從時序事件序列中發(fā)現(xiàn)有意義的序列模式。挖掘得到的模式結(jié)果能夠有效幫助工程師理解系統(tǒng)行為，還可進(jìn)一步用于異常檢測、故障診斷與原因分析等任務(wù)。

序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域中的重要研究課題之一，由AGRAWAL和SRIKANT［1］于1995年提出。傳統(tǒng)的序列模式挖掘算法致力于發(fā)現(xiàn)序列中頻繁出現(xiàn)的序列模式，但是該類算法生成的模式結(jié)果集數(shù)目眾多且信息冗余，不利于人工查看分析，因此從序列中挖掘出高質(zhì)量低冗余的序列模式具有實(shí)際意義。為了減少模式結(jié)果的數(shù)目并降低模式結(jié)果冗余度，常用的方法是篩選出原始結(jié)果集中的部分模式作為最終結(jié)果返回，使得最終結(jié)果中的模式在充分代表原序列中典型行為模式的同時有效降低結(jié)果集數(shù)目。文本壓縮中廣泛使用的最小描述長度（Minimum Description Length，MDL）準(zhǔn)則［2］是一種有效的篩選準(zhǔn)則，該準(zhǔn)則使得模式結(jié)果集中的復(fù)雜度和其代表序列的能力之間達(dá)到良好平衡。

目前，文獻(xiàn)［3-5］將MDL準(zhǔn)則應(yīng)用于序列模式挖掘，該類算法的基本思路是通過設(shè)計(jì)編碼方案，采用一組模式集合作為字典對原始序列進(jìn)行編碼。由于編碼后所需的描述長度更少，因此該過程可視作對原始序列信息的壓縮。通過尋找具有最佳壓縮能力的集合作為結(jié)果返回，即可得到信息緊湊的模式結(jié)果。利用MDL準(zhǔn)則篩選出的模式集合能夠最大程度地壓縮原始序列中的信息，因此該集合可以有效代表整個序列。然而，目前尚未有研究充分考慮時序序列中存在的時間規(guī)律性。日志數(shù)據(jù)記錄的是系統(tǒng)運(yùn)行過程中重復(fù)產(chǎn)生的行為，系統(tǒng)日志中事件與事件之間通常存在顯著的時間規(guī)律性。相對于普通的序列模式而言，對相鄰事件之間的時間關(guān)系進(jìn)行總結(jié)的模式能夠有效指示系統(tǒng)的運(yùn)行狀態(tài)，這說明發(fā)現(xiàn)具有時間規(guī)律的模式具有一定的實(shí)際意義和應(yīng)用價值。

本文提出一種從時序日志序列中挖掘序列模式（Discovering sequential patterns from Temporal log Sequences，DTS）的算法，通過挖掘序列中能充分代表事件關(guān)系和時序關(guān)系的模式，有效增強(qiáng)模式結(jié)果集的表達(dá)能力?；贛DL準(zhǔn)則設(shè)計(jì)一種編碼方案，該方案以序列模式結(jié)果為字典集，在信息無損的前提下對原始時序序列進(jìn)行編碼，并通過計(jì)算編碼前后的描述長度來衡量不同序列模式的有效性，從而發(fā)現(xiàn)高質(zhì)量的序列模式結(jié)果集。

1 相關(guān)工作

國內(nèi)外有許多關(guān)于日志分析領(lǐng)域的研究工作，如文獻(xiàn)［6］提出DeepLog算法，該算法將原始日志文本轉(zhuǎn)換為事件序列，并利用日志序列對系統(tǒng)進(jìn)行異常檢測和原因分析。文獻(xiàn)［7］提出CloudSeer算法，以日志序列為輸入數(shù)據(jù)，并對系統(tǒng)運(yùn)行時的工作流進(jìn)行建模。文獻(xiàn)［8］提出一種基于歸一化特征判別的日志模板挖掘算法，將原始日志文本解析成不同的事件類型。文獻(xiàn)［9］利用層次聚類算法挖掘頻繁日志事件序列，并以此為基礎(chǔ)對不同類型的故障進(jìn)行預(yù)測?，F(xiàn)有工作主要集中在通過日志分析進(jìn)行自動化系統(tǒng)維護(hù)和故障分析［10］。本文旨在從原始日志序列中發(fā)現(xiàn)有意義的序列模式，且發(fā)現(xiàn)的模式可以用作在線監(jiān)控和異常檢測等任務(wù)。

序列模式挖掘問題作為數(shù)據(jù)挖掘領(lǐng)域廣泛研究的重要課題之一，其具有很高的研究熱度。傳統(tǒng)的序列模式挖掘算法例如PrefixSpan算法［11］的生成模式結(jié)果集數(shù)目眾多且信息冗余。為解決該問題，用于衡量模式結(jié)果質(zhì)量的不同模式語義被提出，例如閉頻繁模式集［12］、最大頻繁模式集［13］、高效用模式集［14］以及top-k模式集［15］等。然而，上述算法挖掘得到的模式結(jié)果集依舊存在高度冗余。

為進(jìn)一步降低結(jié)果集冗余度，Krimp算法［16］將MDL準(zhǔn)則應(yīng)用于模式挖掘，并以此為評價標(biāo)準(zhǔn)篩選出最能代表原始數(shù)據(jù)的模式結(jié)果集合。GoKrimp算法［4］進(jìn)一步將MDL準(zhǔn)則應(yīng)用拓展到序列模式挖掘領(lǐng)域，后續(xù)的SQS算法［3］和CSC算法［5］均沿用了該思路?，F(xiàn)有基于MDL準(zhǔn)則的序列模式挖掘算法可以分為兩類。GoKrimp算法［4］和SQS算法［3］僅考慮了事件與事件之間的關(guān)系，通過對長時間間隔懲罰的方式，選擇事件間隔盡可能小的模式，得到的模式依舊存在一定的冗余且不能正確反映序列信息。CSC算法［5］將一條序列模式中相鄰事件之間的事件間隔限制為固定長度，并且不允許同一條模式中出現(xiàn)兩個同一類型的事件，極大地限制了模式的表達(dá)能力，且對于同一條序列需要更多的序列模式來表示。上述算法均未充分考慮處理時序序列中存在的時間規(guī)律性，相比之下，DTS利用模式中的事件關(guān)系以及相鄰事件之間的時間規(guī)律性來獲得更好的模式，并且能夠發(fā)現(xiàn)冗余度較低的模式集合。

2 問題描述

2.1 相關(guān)定義

定義1（時序日志序列）一條時序日志序列是由n條具有時間戳的日志構(gòu)成的有序序列Slog={(log1，t1)，(log2，t2)，…，(logn，tn)}，其中ti≤ti+1(1≤i≤n)。序列的時間跨度為Δ(S)=tn-t1。時間戳的粒度可以按需設(shè)置為不同級別。

由于原始日志信息的形式為無結(jié)構(gòu)文本，日志分析工作的一個常用預(yù)處理步驟是將無結(jié)構(gòu)的日志文本解析為結(jié)構(gòu)化的表示形式［17］。由同一條日志輸出語句生成的日志信息具有高度相似的結(jié)構(gòu)，反之亦然。基于此觀察，一條原始日志文本可以被解析為事件類型和參數(shù)兩個部分信息。其中，事件類型對應(yīng)日志輸出語句的文本常量部分，參數(shù)對應(yīng)日志輸出語句中變量部分的取值。由于Drain算法［18］與現(xiàn)有同類算法相比具有優(yōu)異的性能，因此本文使用該算法解析原始日志序列。一條日志信息logi可以被解析為[ei，para1，para2，…，parap]的結(jié)構(gòu)化形式，其中，ei表示事件類型，paraj表示logi中的第j個參數(shù)值。由于本文的后續(xù)工作不涉及參數(shù)部分的信息，后續(xù)中僅用相應(yīng)的事件類型ei表示一條日志。

定義2（事件類型集合）事件類型集合Σ={E1，E2，…，El}為日志序列Slog中出現(xiàn)的所有事件類型的集合。

定義3（解析后時序日志序列）通過對原始時序日志序列中的日志文本進(jìn)行解析，得到解析后的時序日志序列S={(e1，t1)，(e2，t2)，…，(en，tn)}。

本文后續(xù)的模式挖掘工作以解析后的時序日志序列為輸入數(shù)據(jù)。序列模式的相關(guān)定義如下：

定義4（序列模式）一條序列模式Pi是由事件類型構(gòu)成的偏序序列＜E1，E2，…，Em＞，Ej∈Σ(1≤j≤m)。其中，Ei出現(xiàn)在Ej之前(1≤i＜j≤m)，模式長度為m。

定義6（支持度）模式Pi的支持度suppi為所有非重疊的實(shí)例數(shù)目。如果2個實(shí)例之間不共享同一事件實(shí)例，則它們被認(rèn)為是非重疊的。本文要求不同模式的實(shí)例之間也是非重疊的。

定義8（單事件序列模式）單事件序列模式Pi為只包含一個事件類型的特殊序列模式，Pi=＜Ei＞，且長度為1。單事件序列模式不包含直方圖信息。

2.2 問題定義

給定一條解析后時序日志序列S，本文目標(biāo)是發(fā)現(xiàn)一組序列模式，這些模式能以最佳的形式無損壓縮原序列中的事件關(guān)系以及時間規(guī)律性。本文使用MDL準(zhǔn)則作為衡量數(shù)據(jù)壓縮質(zhì)量和結(jié)果復(fù)雜性之間平衡的指標(biāo)。

MDL準(zhǔn)則的基本思想為：給定模型集合M，對于序列S而言，模型M∈M能使描述長度L(S，M)=L(M)+L(S|M)最小，其中L(M)為M所需的描述長度，L(S|M)為編碼后的S所需的描述長度，描述長度按位級別計(jì)算。

對于本文的目標(biāo)問題而言，模型M為序列模式Pi構(gòu)成的集合P。確定好如何利用P中的模式對序列S進(jìn)行編碼的方案后，可以通過計(jì)算編碼前后描述長度的變化來衡量模式質(zhì)量。本文的問題可以形式化定義為：給定時序日志序列S，尋找模式集合P，使得描述長度L(S，P)=L(P)+L(S|P)最小。

3 編碼方案

本節(jié)給出具體的編碼方案和描述長度的計(jì)算方法。由于對序列編碼是本文評價模式質(zhì)量的手段而非目標(biāo)，因此DTS更關(guān)注于編碼后的描述長度而非具體的編碼結(jié)果。

3.1 模式集合編碼

根據(jù)MDL準(zhǔn)則，需要計(jì)算模型編碼后的描述長度L(P)，計(jì)算方法如下所示：

下文介紹單條模式的描述長度L（P）i的計(jì)算過程。如表1所示，模式集合P中存儲了用于編碼的序列模式的內(nèi)容，包括模式、支持度、模式編碼、描述相鄰事件之間時間間隔分布的直方圖和對應(yīng)的編碼。

表1 模式集合的描述Table 1 Description of the set of patterns

以表1中的模式P1=＜ABC＞為例，該模式的支持度為20，模式編碼為C(P1)。P1使用了兩個直方圖分布描述事件A和事件B以及事件B和事件C之間的時間間隔分布。其中，事件A和事件B的時間間隔有兩種取值，分別為2和5，兩個非空桶的編碼分別為

對于每個模式Pi，需要對其內(nèi)容序列和描述相鄰事件之間時間間隔分布的直方圖分別編碼。使用編碼（Code）替換模式在序列S中的實(shí)例，即可得到編碼后的序列。盡管S中的大部分事件會被一條模式所覆蓋，最終編碼后的序列中可能依舊保留一些孤立事件，這些事件不屬于任何模式的實(shí)例。本文用長度為1的單事件序列模式＜Ei＞對這些孤立事件進(jìn)行編碼，Ei為孤立事件的事件類型。

對單條模式Pi而言，描述長度L(Pi)的計(jì)算如下：描述一個事件類型需要lb|Σ|位比特，因此長度為m的模式需要m×lb|Σ|位比特描述序列內(nèi)容。本文使用全局唯一碼來描述每個模式?？紤]到出現(xiàn)更頻繁的模式應(yīng)當(dāng)消耗更短的描述長度，因此二進(jìn)制形式的模式編碼的長度由模式頻率fi決定，其中，F(xiàn)為所有模式支持度之和本文使用最佳前綴碼，因此編碼長度|C(Pi)|=-lbfi。

對一條序列進(jìn)行編碼所需描述長度L(Pi)計(jì)算方法如下：

假設(shè)表1中模式集合描述的序列包含事件類型數(shù)目為|Σ|=100的序列，則表1中模式P1=＜ABC＞的描述長度如下所示：

3.2 序列編碼

圖1 時序事件序列編碼結(jié)果Fig.1 Encoding result of a temporal event sequence

使用模式集合P對序列S編碼所需的描述長度L(S|P)計(jì)算方法如下：

4 序列模式挖掘算法

文獻(xiàn)［4］證明了基于MDL準(zhǔn)則從序列S中挖掘最優(yōu)模式集合P為NP問題。因此，本文設(shè)計(jì)一種啟發(fā)式算法DTS迭代地從序列中發(fā)現(xiàn)模式。

假定序列S最初僅用單事件模式編碼，模式集合P初始狀態(tài)下為空，DTS迭代地更新P。本文涉及到的更新操作有兩種：添加操作和改進(jìn)操作，且分別定義如下：

定義9（添加操作）將從序列中新發(fā)現(xiàn)的候選模式P添加到集合P中，更新后的模式集合為P ∪P。

定義10（改進(jìn)操作）給定集合P中的某條序列模式P=＜E1，E2，…，Em＞，通過在位置j添加事件類型為E′的事件實(shí)例，對集合OP中部分實(shí)例改進(jìn)，生成長度為m+1的新模式Pr，事件E′稱為改進(jìn)事件。新模式Pr=P⊕E′有如下3種情況：

1）j=0，Pr=＜E′，E1，E2，…，Em＞。

2）j∈[1，2，…，m-1]，Pr=＜E1，E2，…，Ei，E′，Ei+1，Ei+2，…，Em＞。

3）j=m，Pr=＜E1，E2，…，Em，E′＞。

若OP中所有實(shí)例均被改進(jìn)，稱作完全改進(jìn)，更新后的集合為{P ?P}∪{Pr}，否則，稱作部分改進(jìn)，Pm為原模式，更新后的模式集合為{P ?P}∪{Pm，Pr}。

一種常見的情況是候選模式P覆蓋的某些事件，亦是集合P中某條模式P′的改進(jìn)事件，即出現(xiàn)了事件沖突。每輪迭代中決策更新操作時，若不存在事件沖突，可以直接采用添加操作將當(dāng)前最佳候選模式更新到集合P中。在出現(xiàn)事件沖突的情況下，考慮到本文定義的編碼方案要求不同模式之間是非重疊的，即同一條事件實(shí)例不能被多個模式所覆蓋，DTS需要選擇更優(yōu)的更新操作，即能夠使得描述長度L(P)+L(S|P)減少更多的更新操作。每次對集合P更新后，DTS對S中為新模式所覆蓋的事件實(shí)例進(jìn)行編碼。DTS對集合P迭代更新，直到?jīng)]有更新操作能夠使得描述長度進(jìn)一步減少為止。DTS維護(hù)了兩個數(shù)據(jù)結(jié)構(gòu)來分別支持添加和改進(jìn)這兩個更新操作，即候選模式集和候選改進(jìn)表。下面詳細(xì)介紹這兩個數(shù)據(jù)結(jié)構(gòu)和算法流程。

4.1 候選模式集

對于添加操作，被添加到P中的模式應(yīng)當(dāng)能夠最大限度地優(yōu)化描述長度。一個直觀的思路是通過窮舉當(dāng)前序列中所有模式來選擇最佳的候選模式，然而在指數(shù)級空間中搜索的復(fù)雜度很高。因此，在算法迭代過程中，候選模式集CP中僅存儲當(dāng)前有潛力被添加到集合P的候選模式。候選模式P對描述長度優(yōu)化能力的評價函數(shù)如式（6）所示，且gain(P)值越大，模式P的優(yōu)化能力越強(qiáng)。

候選模式集CP的初始化計(jì)算如算法1所示，初始狀態(tài)下CP為不包含任何模式的空集。對于序列S中的每個事件類型E∈Σ，創(chuàng)建一個以E開頭的模式P，對該序列模式以深度優(yōu)先的方式調(diào)用程序BestGrowth，計(jì)算以當(dāng)前事件類型為開頭能生成的最佳序列模式。若最佳序列模式能進(jìn)一步優(yōu)化描述長度，將該模式加入候選模式集，即候選模式集CP貪心地存儲了以每種事件類型為開頭，并將能生成具有最佳優(yōu)化能力的模式作為候選模式。

算法1候選模式集初始化Initialize CP

子程序BestGrowth嘗試將模式P擴(kuò)展到長度為|P|+1且具有更好優(yōu)化能力的新模式中，具體過程為：嘗試使用每個事件類型對當(dāng)前模式擴(kuò)展，得到新模式P′←P?E′。依次計(jì)算序列S中P′的最左實(shí)例并存入直到S中不存在P′的最左實(shí)例為止。其中，最左實(shí)例為序列中最早出現(xiàn)的實(shí)例，例如圖1中(a，0)(b，2)(c，5)即為模式＜ABC＞的一個最左實(shí)例。根據(jù)編碼方案計(jì)算gain(P′)，選取其中描述長度降低最多的模式作為最佳擴(kuò)展結(jié)果返回。若本次調(diào)用BestGrowth沒有找到新擴(kuò)展模式，程序返回null。

4.2 候選改進(jìn)表

對于改進(jìn)操作，DTS維護(hù)了一個候選改進(jìn)表CR并用于存儲模式集合P中所有模式P所有位置上的最佳改進(jìn)。一個模式P在位置j處的改進(jìn)可以格式化地存儲為結(jié)構(gòu)［改進(jìn)位置j，改進(jìn)事件E′，原模式Pm，改進(jìn)模式Pr］。例如[1，F(xiàn)，DD，DFD]存儲的是模式DD在位置1處部分改進(jìn)得到的模式DFD，原模式DD依舊保留部分實(shí)例。若DD被完全改進(jìn)，結(jié)果為[1，F(xiàn)，null，DFD]。候選改進(jìn)表中的改進(jìn)結(jié)構(gòu)以改進(jìn)事件類型為索引，即同一改進(jìn)事件類型關(guān)聯(lián)的改進(jìn)結(jié)構(gòu)聚集為一組。

每次由添加操作或改進(jìn)操作新生成的模式P存入模式集合P后，需要對P計(jì)算其每個位置上可能的改進(jìn)。對模式P計(jì)算改進(jìn)操作的流程如算法2所示，對模式P的每個位置j調(diào)用程序Refine計(jì)算該位置上能生成的最佳改進(jìn)，即最能減少編碼后描述長度的改進(jìn)。若位置j上存在最佳改進(jìn)，將最佳改進(jìn)存入候選改進(jìn)表，改進(jìn)操作對描述長度優(yōu)化能力的評價函數(shù)如式（7）所示，且值越大，則改進(jìn)的優(yōu)化能力越強(qiáng)。

算法2對模式P計(jì)算改進(jìn)ComputeRefining

給定待改進(jìn)模式P，改進(jìn)位置j，改進(jìn)事件E，子程序Refine計(jì)算是否能使用事件E在位置j處對模式P改進(jìn)，具體過程為：首先根據(jù)改進(jìn)操作的定義創(chuàng)建新模式Pr，對實(shí)例集合OP中的每個實(shí)例，計(jì)算該實(shí)例能否被事件E的實(shí)例按照定義進(jìn)行改進(jìn)，此處依舊遵循最左原則。若存在改進(jìn)，將改進(jìn)后的實(shí)例結(jié)果存入模式Pr的實(shí)例集合。若不為空，說明存在有效改進(jìn)，OP中未被改進(jìn)的實(shí)例OP?Oused對應(yīng)原模式剩余的實(shí)例，用Pm表示原模式，返回改進(jìn)結(jié)果為[j，E，Pm，Pr]。圖2展示了調(diào)用程序Refine(P，S，2，E)對模式計(jì)算改進(jìn)的過程，使用事件對P的前兩個實(shí)例在位置2處改進(jìn)得到模式Pr的實(shí)例集合，而第三個實(shí)例找不到滿足時序關(guān)系的改進(jìn)事件實(shí)例e，因此保留為原模式Pm的實(shí)例。

圖2 Refine程序計(jì)算示例Fig.2 Example of the computation of Refine program

4.3 序列模式挖掘

DTS基于啟發(fā)式的思路迭代地從序列中挖掘模式，算法描述如算法3所示。首先對算法涉及的數(shù)據(jù)結(jié)構(gòu)初始化（第1行～第2行），模式集合P初始狀態(tài)下為空，S僅用單事件序列模式編碼。調(diào)用程序InitializeCP初始化候選模式集CP，由于集合P中尚未存入新模式，則候選改進(jìn)表CR初始狀態(tài)下為空。

算法3序列模式挖掘算法DTS

如前文所述，DTS對P的迭代更新是由候選模式主導(dǎo)的。在出現(xiàn)事件沖突的情況下，DTS選擇能夠使得描述長度減少更多的操作，比較模式P和改進(jìn)對描述長度優(yōu)化能力的函數(shù)為：

由于長模式或支持度較高的模式往往對描述長度有更多的優(yōu)化，而改進(jìn)操作的優(yōu)化僅由單個事件貢獻(xiàn)，為了保證比較的公平性，此處比較的是單個事件的優(yōu)化能力。函數(shù)返回值為正則表明模式P有更好的優(yōu)化能力。

在開始迭代過程之前，從候選模式集CP中獲取當(dāng)前最佳候選模式P，由于候選改進(jìn)表CR為空，不存在事件沖突，直接將P存入集合P。由于加入了新模式，調(diào)用程序ComputeRefining計(jì)算其相應(yīng)的改進(jìn)并存入CR。在接下來的算法迭代過程中（第6行～15行），DTS首先從CP中獲取最佳候選模式P*，若沒有新的候選模式，迭代流程終止（第8行）。檢測CR中是否存在與P*事件沖突的改進(jìn)，即模式P*中的事件是其他模式的改進(jìn)事件，并獲取優(yōu)化能力最佳的改進(jìn)對集合P的更新采用添加操作還是改進(jìn)操作取決于cmp函數(shù)的比較結(jié)果。

以圖3為例說明算法核心思想，圖3（a）所示為當(dāng)前待更新的模式集合P以及當(dāng)前迭代輪次的候選模式集CP和候選改進(jìn)表CR。若當(dāng)前CP中的最佳候選模式P*為P1=＜EF＞，相應(yīng)的CR中兩個改進(jìn)對P1存在事件沖突，其中=[1，F(xiàn)，DD，DFD]具有最佳的優(yōu)化能力。調(diào)用函數(shù)cmp對二者的優(yōu)化能力進(jìn)行比較，若優(yōu)化能力更強(qiáng)，模式集合P被改進(jìn)操作更新為P′，更新后的模式集合如圖3（b）所示。否則，將P1存入P，模式集合P被添加操作更新為P″，更新后的模式集合如圖3（c）所示。每輪更新P后，需要及時對數(shù)據(jù)結(jié)構(gòu)候選模式集CP以及候選改進(jìn)表CR中的內(nèi)容更新，刪除已經(jīng)失效的模式和改進(jìn)結(jié)構(gòu)，并重新計(jì)算新的候選模式和改進(jìn)結(jié)構(gòu)。DTS對模式集合P的迭代更新在無法產(chǎn)生新候選模式后終止，隨后僅用改進(jìn)操作更新P直到CR=?。

圖3 模式集合的更新示例Fig.3 Update example of pattern collection

5 實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)環(huán)境

本文所有實(shí)驗(yàn)在單機(jī)環(huán)境下運(yùn)行，處理器為Intel?CoreTMi7-3770 CPU@ 3.40 GHz，內(nèi)存為24 GB，操作系統(tǒng)為64位Windows 10。

5.2 實(shí)驗(yàn)數(shù)據(jù)

本文采用真實(shí)Hadoop分布式文件系統(tǒng)（Hadoop Distributed File System，HDFS）環(huán)境運(yùn)行生成的日志序列作為輸入數(shù)據(jù)，共生成8條不同長度的日志序列，其中4條日志序列是HDFS系統(tǒng)的NameNode生成的，包含200種事件類型，4條日志序列是HDFS系統(tǒng)的DataNode生成的，包含106種事件類型。這兩種日志數(shù)據(jù)有不同的特點(diǎn)，其中NameNode日志包含更豐富的事件類型和更復(fù)雜的系統(tǒng)行為，因此模式更為復(fù)雜，而DataNode日志包含相對更少的事件類型，其中的模式也相對更為簡單規(guī)律。

5.3 算法對比分析

實(shí)驗(yàn)對DTS與SQS［3］、GoKrimp［4］、CSC［5］、ISM［19］算法進(jìn)行對比分析。其中，文獻(xiàn)［3-5］都是基于MDL準(zhǔn)則挖掘模式，ISM算法是一個基于概率的機(jī)器學(xué)習(xí)方法。對于CSC和DTS，輸入數(shù)據(jù)即為整條序列，對于其他3種算法，將序列切分為長度為10的子序列作為輸入數(shù)據(jù)。DTS由Java實(shí)現(xiàn)，其余算法的源代碼由作者提供。

5.3.1 運(yùn)行效率的評估

本節(jié)使用不同長度的日志數(shù)據(jù)對算法的效率和可擴(kuò)展性進(jìn)行評估，5種算法所需運(yùn)行時間如圖4所示。值得指出的是，盡管5種算法的結(jié)果呈現(xiàn)在一張圖內(nèi)，CSC、GoKrimp和DTS算法的時間單位為秒，SQS和ISM的時間單位為分鐘，為了節(jié)省空間，本文將不同數(shù)量級的運(yùn)行時間展示在同一張圖片內(nèi)。從圖4可以看出，DTS略慢于CSC和GoKrimp，這是因?yàn)镃SC和GoKrimp在計(jì)算過程中通過設(shè)定間隔閾值的方式減枝，極大地減少了搜索空間，但后續(xù)實(shí)驗(yàn)證明這也限制了模式的表達(dá)能力。盡管DTS相對來說耗時較長，但也只需400 s即可處理長度為600 000的復(fù)雜日志序列，這是一個可以接受的耗時時間，說明DTS可以高效發(fā)現(xiàn)模式且有很好的可擴(kuò)展性。相比之下，SQS和ISM算法效率不高，處理日志所需耗時從幾十分鐘到幾小時不等，難以滿足日常應(yīng)用需求。

圖4 不同數(shù)據(jù)集下的運(yùn)行時間對比Fig.4 Comparison of processing time under different datasets

5.3.2 模式表達(dá)能力的評估

本節(jié)使用不同長度的日志序列對模式結(jié)果的表達(dá)能力進(jìn)行評估，使用到的評估指標(biāo)為壓縮率（Compression Ratio，CR）?；贛DL準(zhǔn)則篩選模式挖掘出的模式結(jié)果可以用于對序列編碼，與原序列所需描述長度相比，編碼后的序列長度大幅減少。根據(jù)MDL準(zhǔn)則描述長度越小，用于編碼的模式集合表達(dá)能力越強(qiáng)。壓縮率的計(jì)算為只使用單事件序列模式對序列編碼所需描述長度和使用模式集合對序列編碼所需描述長度的比值。

實(shí)驗(yàn)所涉及的基于MDL準(zhǔn)則算法的壓縮率如圖5所示。從圖5可以看出：對于NameNode日志，DTS在所有長度的日志序列上均取得了最高的壓縮率。在對比算法中，SQS的壓縮率最好，CSC和GoKrimp相對更差，如前所述，這兩種算法的減枝和貪心策略使得它們不能很好地處理復(fù)雜的日志序列；對于DataNode日志，所有算法的壓縮率都較低，這是因?yàn)樵撊罩局械哪Ｊ礁鼮楹喍?。DTS在部分序列上仍然擁有最高的壓縮率，僅在兩條序列上略遜于CSC，這與前文的分析一致，CSC更適合處理模式相對簡短的序列數(shù)據(jù)，但是后續(xù)實(shí)驗(yàn)分析可以看出CSC結(jié)果的冗余度很高。DTS在大部分?jǐn)?shù)據(jù)上取得了最好的壓縮率，這表明DTS挖掘出的模式能更好地代表原序列。

圖5 不同數(shù)據(jù)集下的壓縮率對比Fig.5 Comparison of compression ratio under different datasets

5.3.3 模式冗余度的評估

DTS挖掘出的模式集合能更好地對序列進(jìn)行壓縮，這并不意味著DTS的模式集合有很高的冗余度，本節(jié)對該結(jié)論加以實(shí)驗(yàn)驗(yàn)證。本文采用的評估指標(biāo)如下：

1）平均序列間編輯距離（Average inter-sequence Edit Distance，AED）［19］：用于評估模式與模式之間的文本相似度，計(jì)算方式為對模式集合CP中所有模式P與CP中其他模式P′之間編輯距離的最小值求平均值，且AED越高，模式集合冗余度越低。

2）平均序列間杰卡德距離（Average intersequence Jaccard Distance，AJD）：用于評估模式與模式之間的杰卡德相似度，計(jì)算方式與AED類似。

3）事件覆蓋率（Event Coverge，EC）［20］：用于評估模式集合對事件類型的覆蓋率，且EC越高，說明模式集合涵蓋的事件類型越豐富。

表2展示了5種算法在不同數(shù)據(jù)集下的3種評估指標(biāo)結(jié)果。其中，最優(yōu)結(jié)果加粗表示。由于空間限制，此處僅列出兩個最長序列的結(jié)果。從表2可以看出：DTS具有最大的AED和AJD；與其他算法相比，DTS發(fā)現(xiàn)的模式具有最低冗余度；此外，DTS在事件覆蓋率方面也優(yōu)于其他算法，這表明DTS挖掘出的模式結(jié)果在高質(zhì)量的同時且低冗余，這對于人工分析和處理是非常便利的。

表2 5種算法在不同數(shù)據(jù)集下的模式冗余度對比Table 2 Comparison of pattern redundancy of five algorithms under different datasets

6 結(jié)束語

為從時序日志序列中發(fā)現(xiàn)高質(zhì)量的序列模式，本文提出一種基于MDL的序列模式挖掘算法DTS。DTS能夠以黑盒的方式處理日志數(shù)據(jù)，在不需要任何先驗(yàn)系統(tǒng)知識的情況下，從日志序列中發(fā)現(xiàn)有意義的行為序列用于日志分析。該算法結(jié)合系統(tǒng)行為在執(zhí)行時間上存在一定規(guī)律性的特點(diǎn)，設(shè)計(jì)一種考慮事件關(guān)系以及時間規(guī)律性的編碼方案，以編碼前后描述長度的變化為衡量標(biāo)準(zhǔn)來評估序列模式質(zhì)量，并從數(shù)據(jù)中迭代挖掘出可有效代表序列的模式。實(shí)驗(yàn)結(jié)果表明，DTS可以有效發(fā)現(xiàn)高質(zhì)量且低冗余的模式結(jié)果集。下一步將對算法搜索策略進(jìn)行改進(jìn)，以有效減少計(jì)算開銷，提高算法效率。