基于差分壓縮的大規模日志壓縮系統

唐球1,2,3，姜磊1,2，戴瓊1,2

(1. 信息內容安全技術國家工程實驗室, 北京100093; 2. 中國科學院 信息工程研究所, 北京 100093; 3. 中國科學院大學，北京 100049)

1 引言

隨著計算機技術與網絡應用的快速發展，企業或機構內部部署了多套網絡設備與信息系統。這些設備或系統不間斷地將各自的運行狀態記錄為日志數據，如Web服務日志、防火墻日志、入侵檢測系統日志等。日志數據是服務改進、系統審計、安全分析、數據挖掘等應用的重要數據源[1～4]，因此需要長期存儲信息系統的日志數據。隨著大數據、移動互聯網時代的到來，信息系統變得日益復雜，面向互聯網提供服務的信息系統訪問量急劇增長，隨之而來的系統日志數據也呈現出爆炸式增長。尤其對于一些核心系統模塊，需要記錄其所發生的一切操作并將其傳輸回數據中心進行存儲與分析，海量的日志數據對于日志系統的設計是一個巨大的挑戰。因此，有效的壓縮、傳輸并存儲大規模日志數據是現代信息系統的迫切需求。

在數據規模較小且可定期刪除歷史日志數據的情況下，可以使用傳統的壓縮工具定期進行日志數據的壓縮存儲，如Linux日志管理工具logrotate，它使用gzip定期對日志數據進行壓縮與輪詢存儲。但是，使用傳統的通用壓縮算法降低日志數據存儲空間存在效率低的問題。一方面，傳統壓縮算法的通用性導致了其壓縮率低，因為通用的壓縮算法沒有充分利用日志數據的自身特性；另一方面，通用壓縮算法計算量大，難以線速處理大規模的日志數據。近年來，針對大規模日志數據的壓縮存儲，國內外開展了大量相關工作。文獻[5]利用Web日志數據在結構與內容方面均存在大量相似性的特性，提出了一種日志數據變換機制，將當前日志中與前一條日志相同的數據塊轉換為相同數據塊的長度值；不相同的數據塊則保留；然后對變換后的日志數據再使用通用的壓縮算法做進一步的壓縮；該方法的不足是對于不同類型的日志數據塊采用同樣的壓縮算法。文獻[6～8]先后嘗試字段合并、不同字段差異化壓縮策略等技術對Apache的Web日志進行差分壓縮，與本文提出的方法的思想有一定的相似之處，但是該文獻中的方法缺少可配置的靈活性，而且是專門針對于Apache的Web日志，缺少對更廣泛類型日志數據的通用性設計。Kimmo等提出了基于日志數據中的頻繁重復數據模式塊消冗的防火墻日志壓縮算法[9]。文獻[10]通過分析DNS日志數據的特性，針對 DNS日志數據所涉及的時間、IP地址、域名和類型4類數據分別進行不同的壓縮方法。文獻[11]提出了基于通用壓縮算法壓縮日志數據的預處理算法，通過預處理算法中的分區函數將日志數據劃分至多個同質日志桶（homogeneous buckets），然后對不同的同質日志桶內的日志數據使用傳統的壓縮算法bzip2或gzip進行壓縮。由于同質日志桶內容日志結構高度相似，因此比直接使用bzip2或gzip壓縮壓縮更高。文獻[12]使用硬件FPGA實現 LZ4算法對外匯交易系統中的事務日志進行壓縮，在保證LZ4的壓縮率的情況下，獲得了專用硬件帶來的壓縮速度優勢。已有日志壓縮工作降低了日志存儲空間，但是存在以下幾點不足：1）通用性較差，依賴于具體的某一類日志；2）不具可擴展性，不支持壓縮策略的可配置；3）粗粒度壓縮策略，針對不同數據類型采用相同的壓縮策略；4）不支持流式差分，難以滿足在線實時日志壓縮需求。

本文針對以上不足，提出了一種支持大規模日志數據的流式差分壓縮架構。該架構首先充分利用日志數據的先驗知識，將一類日志數據中固定不變的數據塊提取為模板，日志壓縮時，刪除模板中定義的數據塊，只存儲一個模板指針。在解壓時，根據模板內容即可復原日志數據；然后，針對日志數據中不同類型的數據塊定制其差分壓縮策略。本文提出大規模日志壓縮系統不依賴于特定的日志類型，對于不同類型的日志數據可以配置不同的細粒度差分壓縮策略，該系統采用流式的差分壓縮架構，從而使本文提出的日志壓縮系統具有明顯的壓縮率與壓縮速度優勢。

2 日志數據分析

日志數據格式可以是系統設計者自定義，或使用被廣泛使用的 syslog日志格式[13]，后者由RFC3164規范定義。它規定一條日志消息由“優先級”、“頭部”與“消息體”3部分構成，其中優先級是一個數字，它代表了生成日志的程序模塊（facility）與嚴重性（severity）；頭部包含時間與主機名；消息體是具體的日志內容。由于syslog日志規范只是一個建議，規范寬泛，其消息體包含了大量的日志屬性，但這些內容的組織格式并沒有確定的定義，由系統設計者自行定義。所以，很多日志系統是將其作為一種支持的格式，更多的是對它進行擴展。如防火墻安全領域更多的是使用 NetIQ公司提出的WELF日志格式。從真實的應用系統中采集了21 GB的真實日志數據，這個數據集由真實系統中的防火墻（天融信、思科）日志、交換機（華為）日志，入侵檢測系統（IDS）日志、VPN日志與病毒檢測系統日志構成。通過對該數據集分析，發現目前的日志系統存在以下3個顯著特征。

1) 日志格式規整相似。目前成熟產品的日志數據格式類似于syslog RFC3164規范的格式，或者更加規范的日志格式，如WELF。前者如思科防火墻的日志格式（如表 1所示）；后者的一條日志消息通常是由多個“<字段名，字段值>”的鍵值對構成，不同日志系統僅在鍵值連接符與鍵值對之間的分割符上有細微的差別，如表1中的最后3條日志數據，天融信的防火墻日志的鍵值對分隔符為空格，鍵值連接符為等號，而綠盟的IDS日志的分隔符為分號，鍵值連接符為分號。

2) 日志數據存在冗余結構模式。從表 1中可知，同一類日志數據無論以哪種格式表示，在消息結構上都存在大量的相同模式，如思科防火墻的106017類型日志（表1中的第1、第2行）均含有“ASA*Deny IP due to Land Attack from*to*”的模式；天融信防火墻的訪問控制日志（表1的第3、第4行）均含有 “id=*time=*fw=*pri=*…”模式。其中模式中的星號表示可變內容，非星號字符為恒定不變內容（即冗余的結構模式）。

3) 日志數據中的屬性值類型是固定且具有很強的時間局部性相似性。即對于同一類日志數據，即使在數據組織格式上有差異，但所承載的核心信息是相同的。如不同供應商的防火墻設備生成的訪問控制日志數據均包含某一次穿越防火墻連接的五元組、時間、MAC地址、生成日志的設備名、防火墻策略 ID號等信息；在一個具體的日志系統中這些屬性值的類型是確定的，且在短時間內，這些屬性值是局部相似的，如時間屬性值只是秒數的差異、少數IP地址在五元組中頻繁重復出現等。

表1 常見網絡設備日志數據實例（隱私信息已做替換）

3 日志數據差分壓縮

3.1 基于模板的日志去重

基于第2節關于21 GB日志數據的分析結論，本節提出一種基于模板的日志消冗機制，消除日志數據中存在的冗余結構模式，形式化定義如下。

定義1（字段，field）。字段是由字段名（fld）與字段值（val）構成的鍵值對（fldλval），其中“λ”為字段名與字段值之間的連接符。一個字段表示一個具體的日志屬性，如表 1中的天融信防火墻訪問控制日志中的源IP地址字段為“src= x.x.x.x”，其中 src為字段名（源 IP），“x.x.x.x”為字段值（IP地址），字段名與字段值連接符為等號。

定義2（日志消息,log_msg）。一條日志消息表示一個事件，它是由有限個字段構成，字段之間有先后順序、由字段分隔符（θ）相連接；即log_msg=field1θfield2θ…fieldN，其中，fieldi=fldiλvali。

定義 3（日志，log）。日志是由多條日志消息構成的集合，log={log_msgi | i∈1,2,3,…,M; log_msgi=field1iθfield2iθ …fieldNi;fieldji=fldjiλvalji,j∈1,2,…,N}。

由前一節的分析可知，已有的日志格式與本文形式化定義的日志格式很相似，因此只需對待壓縮的日志數據進行簡單預處理，將日志數據轉換為規整的日志格式(log)。日志數據所有的字符都是可打印字符，不含控制類字符，因此可以選擇控制類字符作為λ與θ。對于同一類日志數據，可以通過正則表達式匹配加文本處理腳本完成日志預處理。

同一設備或系統的日志存在冗余的結構模式：日志消息的字段組成結構是固定的，且各個字段名是相同的，即log_msg1與log_msg2都包含相同的內容 ：fld1λ,θfld2λ … θfldN； 不 同 的 部 分 是 ：val1,val2,…,valN。基于此特征，本文提出的日志壓縮系統將日志中冗余的結構模式以字段為單位提取為模板，然后將模板定義的冗余模式從日志消息中刪除，并在日志消息中存儲模板指針。具體的模板形式化描述如下。

定義 4（模板，template）。一個模板由字段名與字段值連接符、字段分割符、各個字段名以及該模板的 ID 號（tid）構成，即template={tid,λ,θ,fld1,fld2,…,fldN}。

因此，基于模板的日志去重機制主要步驟如下。

Step1日志預處理。

Step2對每一條日志消息log_msgi進行如下操作。

1) 模板庫中查找與log_msgi相匹配的模板（templatek）；

2) 將templatek定義的字段名從log_msgi中刪除，并將templatek的模板ID寫入日志消息中，最后得到基于模板變換后log_msgi為“tidkθval1iθval2iθ…θvalN i”。

對于壓縮后的日志數據，根據模板指針，通過執行基于模板的逆去重操作即可恢復原始的日志數據。

3.2 日志數據細粒度差分壓縮

基于模板的日志數據重后降低了日志的存儲空間，但仍存在大量的信息冗余，尤其是短時間內的同類日志消息字段之間存在局部相似性。為了進一步壓縮日志數據空間，本文設計的日志差分架構對基于模板去重后的日志數據做進一步的細粒度的差分壓縮。首先定義幾類通用的差分壓縮策略（diff_strgy）；然后，根據不同的字段值特性，選擇各個字段值最適合的差分策略對基于模板去重后的日志數據進行字段級別的差分壓縮。為了支持日志消息的線速壓縮，日志差分壓縮只選擇與前一條同類型的歷史日志消息進行差分計算；由于日志消息具有時間域的局部相似性，所以該差分壓縮策略保證了日志壓縮的時間與空間效率。

3.2.1 字段細粒度差分壓縮

每個字段的細粒度差分壓縮（FFDE, finegrained field differential encoding）可以描述為一個五元組：ffde=(fld,fld_type,diff_strgy,initVal,size)，五元組中各個屬性的定義如下。

fld：字段名。

fld_type：字段值類型，分為字符串、整數2大類，其中整數分為8位，16位，32位，64位的有符號與無符號整數；浮點數轉化為指數與尾數的 2個整數表示。

diff_strgy：字段值差分策略，本日志壓縮系統定義了4類差分策略，具體定義見表2，對于不同特性的字段采用不同差分策略，也可擴展新差分策略以支持新類型字段。

表2 字段差分策略定義

initVal：字段的初始值。當第一條消息差分壓縮時，將initVal作為歷史值（val'）與當前字段值做差分運算。當字段差分策略為“定值”時，則initVal屬性值定義為該字段的定值。

size：標識使用差分策略得到的字段差值使用定長編碼（編碼為size個字節）還是變長編碼（size=0）。定長編碼即保持原始值；變長編碼采用被廣泛使用的 LEB128[14]變長編碼技術，即一個字節的7 bit表示實際數據，最高比特位標識當前字節是否為變長數據的最后一個字節（如0表示結束）。對于差分壓縮后的字段值的取值范圍固定（如 IP地址的一個段的值范圍為0～255），且等于1字節或大于4個字節的定長值采用定長編碼，反之采用變長編碼。這樣可以使存儲空間達到最優。如一個無符號的 32為整數值采用變長編碼時，當其值的區間為[0, 127]內的任意一個值時，只需要一個字節存儲表示，而不是4個字節。

3.2.2 字段差分存在位圖

差分策略導致字段的值具有3種“值存在”狀態：存在、不存在、條件存在。“存在”表示字段差分之后總是有值，如“差值”字段差分策略；“不存在”表示字段差分后總是沒有值，如“定值”差分策略；“條件存在”表示字段差分后依據條件可能有值也可能無值。如字段差分策略為“復制”，當與前一條日志消息的值相同時，當前日志直接刪除該值，差分后的字段無值；反之則保留該值，差分后的字段有值。因此一條差分后的日志消息所包含的字段值數目不固定。為了正確解碼日志消息，一條差分壓縮的日志消息需要存儲一個字段值存在位圖向量（FVPB, field value presence bitmap），FVPB中的每一個比特對應日志中的一個具有“條件存在”狀態的字段，置位表示字段值存在；復位表示字段值不存在。對于“存在”與“不存在”的字段值則不需要FVPB標示。

3.3 基于模板的日志數據細粒度差分壓縮

結合3.2節與3.3節，本節給出基于模板的日志數據細粒度差分壓縮總體架構。日志先通過模板去重，然后再對日志字段值進行細粒度的差分壓縮。這兩者均定義在日志差分壓縮模板中，定義如下。

定義5（細粒度差分模板，template′）。一個細粒度差分模板由字段值存在位圖向量、各個字段的細粒度差分五元組、模板 ID號、字段名與字段值連接符與字段分割符構成，即template'={ffdetid,λ,θ,ffde1,ffed2,…,ffedN}。其中模板ID號也作為日志消息添加的一個普通字段（ffdetid），使用“復制”差分策略（可減少連續同類型日志消除中模板 ID的存儲）。基于細粒度差分模板的日志差分壓縮算法描述為算法1。

字段差分壓縮是當前值（val）與同類型的前一條日志數據的對應字段值(val')執行差分壓縮，因此整個日志的差分壓縮過程需要維護一個差分字典，用于記錄前一條同類型日志數據的字段值。算法 1第 1行為每個模板定義一個差分字典（dict[k][0…N]），其初始值為對應模板的字段初始值（initVal）；每執行完一條日志消息的差分運算，用當前日志的字段值更新該差分字典（算法1第6行）。對于每一條日志消息，首先需要確定適合其的模板，然后根據模板對該日志消息進行細粒度差分壓縮（算法1中的第3～7行）。

算法1基于細粒度差分模板的日志壓縮算法

輸入：日志log={log_msgi |i=1,2,…,M}; 差分壓縮模板集合temp_set={template'k|k=1,2,…,K};其中template'k={ffdetidk,λ,θ,ffde1k,…,ffedNk},ffedjk=(fldjk,fld_typejk,diff_strgyjk,initValjk,sizejk),j=1,2,…,N};

輸出：差分壓縮的日志數據;

1) 初始化模板字段差分字典dict[k][0…N]={k,initVal1k,…,initValN k};

2) 對于每個日志消息log_msgi，執行如下操作；

3) 根據日志消息的結構查找與其相對應的模板template'k；

4) 對模板ID號（k）與log_msgi的每個字段值valji執行如下操作；

5) 依據diff_strgyjk的對valji與dict[k][j]進行差分運算；如果當字段差分編碼狀態為“條件存在”且差分后有值，則FVPB[j']=1;否則FVPB[j']=0；/*j'為當前字段在字段值存儲位圖中的比特位*/；

6) 更新字段前值字典dict[k][j]=valj;

7) 輸出FVPB與各個字段差分后的值。

4 實驗結果與分析

本節通過測試真實的網絡系統日志數據，分析本文提出的支持大規模日志壓縮系統的效率。主要考察其壓縮率與壓縮速度。

實驗環境：處理器為Intel Core I3-3240，內存2 GB，Fedora-14的操作系統。

由于提出的差分架構是流式工作方式，即只與前一條日志消息做差分計算，因此壓縮總時延與日志的規模成正比關系，小規模數據集測試即可說明該架構的壓縮速度。為了快速得到測試數據集的壓縮率與壓縮速度，本節從真實的天融信防火墻訪問控制日志數據集中提出部分字段，組成4個數據集，數據集的特性描述如表3所示。

表3 數據集特性

對這4個數據集分別使用本文提出的基于模板的細粒度差分壓縮架構與通用的壓縮工具gzip進行壓縮測試，選擇gzip進行參照是因為廣泛使用的開源日志管理工具logrotate使用的就是gzip作為其日志壓縮算法；而且類似的日志壓縮文獻[6～9]的實驗對比也是與gzip相比較。2個壓縮工具對于各個數據集的壓縮時間與壓縮率分別如圖1和圖2所示，由于gzip可以設置其壓縮參數典型的可以設置為快速壓縮模式（速度快、低壓縮率）、高壓縮率模式（速度慢、高壓縮率）與普通壓縮壓縮模式（壓縮速度與壓縮率介于前2種模式之間），所以在實際測試中對于同一數據集，分別使用3種不同的gzip模式進行壓縮測試。從圖 1可知，本文提出的基于模板差分的日志壓縮系統在壓縮速度上比普通或快速模式的gzip快2～5倍，比高壓縮率模式的gzip快一個數量級（圖1中的時間縱軸為對數刻度）。

圖1 壓縮時間對比

從圖2可知，本文提出的基于模板的日志差分壓縮架構的壓縮率均低于 3種模式下 gzip 的壓縮率，且壓縮到達為10.5%。

圖 3描述了本文所提方法與 gzip對于fw_log(150w)數據集在壓縮速度與壓縮率2方面的整體對比。其中柱狀圖表示壓縮率，黑色三角形圖塊表示壓縮時間。圖3表明本文提出的日志差分壓縮架構與gzip相比，具有明顯的速度優勢（快2～10倍），同時壓縮率也優于 gzip。這是合理的，因為基于模板的差分壓縮充分利用了日志數據自身的特性，在壓縮前就獲得了日志數據的先驗知識（模板），而通用的gzip工具沒有這些先驗知識。

圖3 基于模板的差分壓縮與gzip在壓縮率（柱狀圖）與壓縮速度（三角形）上的對比

5 結束語

基于模板流式差分的日志壓縮系統首先消除日志數據中冗余的結構模式。其次，利用日志數據在時間域上的局部相似性，通過配置適用于日志內容屬性（字段）的差分策略執行差分壓縮，進一步降低了日志數據的存儲空間。由于采用流式差分壓縮，使本文所提的日志壓縮架構具有顯著的壓縮速度優勢。差分策略的可配置性使該架構具有通用性與可擴展性，該方法可以應用于一般的日志壓縮。

[1] YEN T F,et al. Beehive: large-scale log analysis for detecting suspicious activity in enterprise networks[A]. Proceedings of the 29th Annual Computer Security Applications Conference[C].2013.199-208.

[2] BREIER J, BRANI?OVá J. Anomaly detection from log files using data mining techniques[A]. Information Science and Applications[C].2015.449-457.

[3] DUMAIS S,et al. Understanding user behavior through log data and analysis[A]. Ways of Knowing in HCI[C]. 2014. 349-372.

[4] SRIVASTAVA M, GARG , MISHRA P K. Analysis of data extraction and data cleaning in Web usage mining[A]. Proceedings of the 2015 International Conference on Advanced Research in Computer Science Engineering Technology (ICARCSET 2015)[C]. 2015. 1-6.

[5] SKIBI?SKI P, SWACHA J. Fast and efficient log file compression[A].Proceedings of CEUR Workshop of 11th East-European Conference on Advances in Databases and Information Systems(ADBIS 2007)[C]. 2007.

[6] GRABOWSKI S, DEOROWICZ S. Web log compression[J]. Automatyka/Akademia Górniczo-Hutniczaim Stanis?awa Staszicaw Krakowie, 2007, (11): 417-424.

[7] DEOROWICZ S, GRABOWSKI S. Efficient preprocessing for Web log compression[J]. International Journal of Computing, 2008, 7(1): 35-42.

[8] DEOROWICZ S, GRABOWSKI S. Sub-atomic field processing for improved Web log compression[A]. Proceedings of IEEE International Conference on Modern Problems of Radio Engineering, Telecommunications and Computer Science[C]. 2008.551-556.

[9] H?T?NEN K.et al. Comprehensive log compression with frequent patterns[A]. Data Warehousing and Knowledge Discovery[C]. 2003.360-370.

[10] 王艷峰, 王正,閻保平. 一種高效的 DNS 日志壓縮算法[J]. 計算機工程, 2010, 36(15): 32-35.WANG Y F, WANG Z, YAN B P. High efficient DNS log compression algorithm[J]. Copular Engineering, 2010, 36(15): 32-35.

[11] CHRISTENSEN R. Improving compression of massive log data[EB/OL].http://www.erg.utal.edu, 2013.

[12] JANG J H,et al. Accelerating forex trading system through transaction log compression[A]. SoC Design Conference (ISOCC), 2014 International[C]. IEEE, 2014. 24-75.

[13] LONVICK C. RFC 3164: The BSD Syslog Protocol[S]. Network Working Group.

[14] LEB128 [EB/OL]. http://en.wikipedia.org/wiki/LEB128, 2015.