杜詩晴，王 鵬，汪 衛(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)行時(shí)的狀態(tài)以及任務(wù)的開始與結(jié)束等重要事件，其易于獲取且含有豐富的信息，已經(jīng)成為系統(tǒng)運(yùn)維領(lǐng)域的重要數(shù)據(jù)源。系統(tǒng)運(yùn)行產(chǎn)生的日志數(shù)據(jù)可被視作時(shí)序事件序列，利用序列模式挖掘技術(shù)可從時(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é)果中的模式在充分代表原序列中典型行為模式的同時(shí)有效降低結(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ì)編碼方案，采用一組模式集合作為字典對(duì)原始序列進(jìn)行編碼。由于編碼后所需的描述長度更少，因此該過程可視作對(duì)原始序列信息的壓縮。通過尋找具有最佳壓縮能力的集合作為結(jié)果返回，即可得到信息緊湊的模式結(jié)果。利用MDL準(zhǔn)則篩選出的模式集合能夠最大程度地壓縮原始序列中的信息，因此該集合可以有效代表整個(gè)序列。然而，目前尚未有研究充分考慮時(shí)序序列中存在的時(shí)間規(guī)律性。日志數(shù)據(jù)記錄的是系統(tǒng)運(yùn)行過程中重復(fù)產(chǎn)生的行為，系統(tǒng)日志中事件與事件之間通常存在顯著的時(shí)間規(guī)律性。相對(duì)于普通的序列模式而言，對(duì)相鄰事件之間的時(shí)間關(guān)系進(jìn)行總結(jié)的模式能夠有效指示系統(tǒng)的運(yùn)行狀態(tài)，這說明發(fā)現(xiàn)具有時(shí)間規(guī)律的模式具有一定的實(shí)際意義和應(yīng)用價(jià)值。

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

1 相關(guān)工作

國內(nèi)外有許多關(guān)于日志分析領(lǐng)域的研究工作，如文獻(xiàn)［6］提出DeepLog算法，該算法將原始日志文本轉(zhuǎn)換為事件序列，并利用日志序列對(duì)系統(tǒng)進(jìn)行異常檢測和原因分析。文獻(xiàn)［7］提出CloudSeer算法，以日志序列為輸入數(shù)據(jù)，并對(duì)系統(tǒng)運(yùn)行時(shí)的工作流進(jìn)行建模。文獻(xiàn)［8］提出一種基于歸一化特征判別的日志模板挖掘算法，將原始日志文本解析成不同的事件類型。文獻(xiàn)［9］利用層次聚類算法挖掘頻繁日志事件序列，并以此為基礎(chǔ)對(duì)不同類型的故障進(jìn)行預(yù)測?，F(xiàn)有工作主要集中在通過日志分析進(jìn)行自動(dòng)化系統(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)用于模式挖掘，并以此為評(píng)價(jià)標(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)系，通過對(duì)長時(shí)間間隔懲罰的方式，選擇事件間隔盡可能小的模式，得到的模式依舊存在一定的冗余且不能正確反映序列信息。CSC算法［5］將一條序列模式中相鄰事件之間的事件間隔限制為固定長度，并且不允許同一條模式中出現(xiàn)兩個(gè)同一類型的事件，極大地限制了模式的表達(dá)能力，且對(duì)于同一條序列需要更多的序列模式來表示。上述算法均未充分考慮處理時(shí)序序列中存在的時(shí)間規(guī)律性，相比之下，DTS利用模式中的事件關(guān)系以及相鄰事件之間的時(shí)間規(guī)律性來獲得更好的模式，并且能夠發(fā)現(xiàn)冗余度較低的模式集合。

2 問題描述

2.1 相關(guān)定義

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

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

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

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

本文后續(xù)的模式挖掘工作以解析后的時(shí)序日志序列為輸入數(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個(gè)實(shí)例之間不共享同一事件實(shí)例，則它們被認(rèn)為是非重疊的。本文要求不同模式的實(shí)例之間也是非重疊的。

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

2.2 問題定義

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

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

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

3 編碼方案

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

3.1 模式集合編碼

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

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

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

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

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

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

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

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

3.2 序列編碼

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

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

4.1 候選模式集

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

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

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

子程序BestGrowth嘗試將模式P擴(kuò)展到長度為|P|+1且具有更好優(yōu)化能力的新模式中，具體過程為：嘗試使用每個(gè)事件類型對(duì)當(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＞的一個(gè)最左實(shí)例。根據(jù)編碼方案計(jì)算gain(P′)，選取其中描述長度降低最多的模式作為最佳擴(kuò)展結(jié)果返回。若本次調(diào)用BestGrowth沒有找到新擴(kuò)展模式，程序返回null。

4.2 候選改進(jìn)表

對(duì)于改進(jìn)操作，DTS維護(hù)了一個(gè)候選改進(jìn)表CR并用于存儲(chǔ)模式集合P中所有模式P所有位置上的最佳改進(jìn)。一個(gè)模式P在位置j處的改進(jìn)可以格式化地存儲(chǔ)為結(jié)構(gòu)［改進(jìn)位置j，改進(jìn)事件E′，原模式Pm，改進(jìn)模式Pr］。例如[1，F(xiàn)，DD，DFD]存儲(chǔ)的是模式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后，需要對(duì)P計(jì)算其每個(gè)位置上可能的改進(jìn)。對(duì)模式P計(jì)算改進(jìn)操作的流程如算法2所示，對(duì)模式P的每個(gè)位置j調(diào)用程序Refine計(jì)算該位置上能生成的最佳改進(jìn)，即最能減少編碼后描述長度的改進(jìn)。若位置j上存在最佳改進(jìn)，將最佳改進(jìn)存入候選改進(jìn)表，改進(jìn)操作對(duì)描述長度優(yōu)化能力的評(píng)價(jià)函數(shù)如式（7）所示，且值越大，則改進(jìn)的優(yōu)化能力越強(qiáng)。

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

給定待改進(jìn)模式P，改進(jìn)位置j，改進(jìn)事件E，子程序Refine計(jì)算是否能使用事件E在位置j處對(duì)模式P改進(jìn)，具體過程為：首先根據(jù)改進(jìn)操作的定義創(chuàng)建新模式Pr，對(duì)實(shí)例集合OP中的每個(gè)實(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對(duì)應(yīng)原模式剩余的實(shí)例，用Pm表示原模式，返回改進(jìn)結(jié)果為[j，E，Pm，Pr]。圖2展示了調(diào)用程序Refine(P，S，2，E)對(duì)模式計(jì)算改進(jìn)的過程，使用事件對(duì)P的前兩個(gè)實(shí)例在位置2處改進(jìn)得到模式Pr的實(shí)例集合，而第三個(gè)實(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所示。首先對(duì)算法涉及的數(shù)據(jù)結(jié)構(gòu)初始化（第1行～第2行），模式集合P初始狀態(tài)下為空，S僅用單事件序列模式編碼。調(diào)用程序InitializeCP初始化候選模式集CP，由于集合P中尚未存入新模式，則候選改進(jìn)表CR初始狀態(tài)下為空。

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

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

由于長模式或支持度較高的模式往往對(duì)描述長度有更多的優(yōu)化，而改進(jìn)操作的優(yōu)化僅由單個(gè)事件貢獻(xiàn)，為了保證比較的公平性，此處比較的是單個(gè)事件的優(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)對(duì)集合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中兩個(gè)改進(jìn)對(duì)P1存在事件沖突，其中=[1，F(xiàn)，DD，DFD]具有最佳的優(yōu)化能力。調(diào)用函數(shù)cmp對(duì)二者的優(yōu)化能力進(jìn)行比較，若優(yōu)化能力更強(qiáng)，模式集合P被改進(jìn)操作更新為P′，更新后的模式集合如圖3（b）所示。否則，將P1存入P，模式集合P被添加操作更新為P″，更新后的模式集合如圖3（c）所示。每輪更新P后，需要及時(shí)對(duì)數(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對(duì)模式集合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日志包含相對(duì)更少的事件類型，其中的模式也相對(duì)更為簡單規(guī)律。

5.3 算法對(duì)比分析

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

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

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

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

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

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

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

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

5.3.3 模式冗余度的評(píng)估

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

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

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

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

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

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

6 結(jié)束語

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