◆袁沐春 郭育辰

（中國人民公安大學(xué) 北京 102600）

數(shù)據(jù)包位圖索引壓縮算法研究

◆袁沐春 郭育辰

（中國人民公安大學(xué) 北京 102600）

為解決從存儲(chǔ)海量數(shù)據(jù)包的數(shù)據(jù)庫中快速找到少量的被需要的數(shù)據(jù)包的時(shí)間效率問題，本文引入位圖索引數(shù)據(jù)庫，并對(duì)三種常見的位圖索引壓縮算法做簡要分析。

數(shù)據(jù)包；位圖索引；數(shù)據(jù)庫；算法

0 引言

傳統(tǒng)的關(guān)系型數(shù)據(jù)庫是面向更改的，存儲(chǔ)在數(shù)據(jù)庫中的數(shù)據(jù)需要經(jīng)常改動(dòng)。而位圖索引數(shù)據(jù)庫專門為科學(xué)數(shù)據(jù)設(shè)計(jì)，這些數(shù)據(jù)通常是由科學(xué)儀器或是科學(xué)仿真產(chǎn)生的，特點(diǎn)是數(shù)據(jù)量極其大，而且不再更改。位圖索引數(shù)據(jù)庫解決了如何在存儲(chǔ)海量數(shù)據(jù)包的數(shù)據(jù)庫中快速地找出那些少量被需要的數(shù)據(jù)包的問題，而傳統(tǒng)的關(guān)系型數(shù)據(jù)庫并不適合這項(xiàng)任務(wù)。

位圖索引數(shù)據(jù)庫中用到的技術(shù)主要是位圖索引、位圖壓縮和歸類。在位圖索引數(shù)據(jù)庫中，數(shù)據(jù)是按列存儲(chǔ)的，一個(gè)列的數(shù)據(jù)存儲(chǔ)在一起，并做位圖索引。一個(gè)簡單的位圖索引的例子如表1所示。其中RowID表示對(duì)應(yīng)值在表中第幾行，生成的索引是一個(gè)矩陣，矩陣中每一行只有一個(gè)1，其余都是0，標(biāo)1的位置對(duì)應(yīng)于該行數(shù)據(jù)在這一列上的取值。這樣生成的位圖索引有一個(gè)比較大的缺點(diǎn)，索引的列數(shù)隨著取值的多樣性而線性增長。為了控制索引的大小和查詢時(shí)間，需要對(duì)索引壓縮和歸類。壓縮是減小索引中大量0帶來的空間消耗，歸類是對(duì)位圖索引的一些列的合并。比如值1.01和1.02可以歸類成1。通過歸類可以減少位圖索引的列數(shù)，增加查詢和存儲(chǔ)的效率。

表1 位圖索引示例

下面主要研究三種位圖索引壓縮算法WAH[1]、PLWAH[2]、COMPAX[3]。

1 WAH索引壓縮算法

WAH索引壓縮算法示例如表2所示。

表2 WAH索引壓縮算法示例

WAH算法是FastBit索引數(shù)據(jù)庫的默認(rèn)算法，將位序列分成以31b（對(duì)于WAH64就是63b）為單位的group。這樣，group有兩種類型。

（1）Literal，即這31b中有0有1。

（2）Fill，即這31b全為0或者全為1。

在WAH算法中，最終形成的word是32b，其中最高位為類型的標(biāo)志位。Literal類型的Group：類型標(biāo)志位為0，余下的31b即為原來的literal group；Fill類型的Group：分為1-Fill和0-Fill。此時(shí)32b中類型標(biāo)志位為1，第二位作為Fill類型的標(biāo)志（0-Fill即為0，1-Fill即為1），余下的30b作為counter，表示連續(xù)出現(xiàn)多少個(gè)0-Fill（或者1-Fill）的 group。

2 PLWAH算法及改進(jìn)

PLWAH算法和WAH算法類似，同樣是將原始碼流分成以31b為單位的group。Group也和WAH算法中提到的相同，一樣分成Literal和Fill兩種類型，但是壓縮方式有變化，具體如下所示。

第一步：依照WAH算法對(duì)于Fill-Group和Literal-Group添加標(biāo)志位與編碼，形成一組以32b為單位的編碼（標(biāo)志位為0稱為literal-word，標(biāo)志位為1稱為fill-word，下同）。此處的區(qū)別是對(duì)于fill-word只有低25b作為counter（WAH算法是低30b都是counter，PLWAH要留出中間的5b作為position list）。

第二步：檢查每個(gè)fill-word后的word。如果下一個(gè)word是literal-word且是nearly identical（表現(xiàn)為literal-word和上一個(gè)fill-word的差異小于等于s位，s此處暫且為1），則在fill-word的position list上填入下一個(gè)word（此時(shí)為literal-word）的差異位位置（此處是31b，因此差一位標(biāo)號(hào)是1～3，留出5b目的在此），同時(shí)刪去下一個(gè)word（因?yàn)樾畔⒁呀?jīng)保存在此fill-word中，沒有必要繼續(xù)留著），若fill-word后的word是如下三種情況：

（1）異類型的fill-word。

（2）非nearly identical的literal-word。

（3）同類型的fill-word（這種情況產(chǎn)生的原因是連續(xù)的fill-group超出了1個(gè)fill-word的counter計(jì)數(shù)范圍），則position list不變。

進(jìn)行擴(kuò)展討論：

對(duì)于32位PLWAH，由于nearly identical的定義中的s不為1，則在第一步時(shí)需要留出5*s位nearly identical，余下的32-2-5*s位為counter。在第二步時(shí)，向fill-word中的position list添加差異位時(shí)需按序添加差異位位置（5b標(biāo)識(shí)一個(gè)差異位，5*s位標(biāo)識(shí)至多s個(gè)差異位），當(dāng)s=0時(shí)，PLWAH退化為WAH。

對(duì)于64位PLWAH，position list以6為單位，即留出6*s位作為position list，余下的64-2-6*s位為counter。

以PLWAH32，s=1為例，對(duì)PLWAH進(jìn)行了小幅改進(jìn)，即考慮連續(xù)出現(xiàn)極多的0或者1以至于1個(gè)word的counter無法完全容納。此處選用的方法為使用兩個(gè)連續(xù)的同類型fill-word，把兩個(gè)counter部分視為一個(gè)大的counter，第一個(gè)fill-word記錄LSB25位，第二個(gè)fill-word記錄MSB25位（相當(dāng)于50b的大counter），同時(shí)第一個(gè)fill-word的position list為空，第二個(gè)fill-word的position list照常計(jì)算，如表3所示。這樣的好處是無需擴(kuò)展word位數(shù)即可完成對(duì)更多連續(xù)碼流的編碼任務(wù)，節(jié)約index空間。

表3 PLWAH改進(jìn)舉例

25 MSB of counter

3 COMPAX算法

COMPAX壓縮算法示例如圖1所示。

COMPAX算法也是WAH的改進(jìn)，這里以32b為例，但COMPAX的標(biāo)志位相對(duì)較多。這里L(fēng)iteral和Fill的定義同WAH和PLWAH。同樣是每31b分成一個(gè)group，并且將這些group按照以下特征分組。

（1）Literal-Fill-Literal（LFL），即一個(gè)literal group +N個(gè)Fill group+1個(gè)literal group，且這兩個(gè)literal group 的非0位（或者非1位）在同一個(gè)byte上（一個(gè)group在前面補(bǔ)一位0即構(gòu)成4個(gè)完整的byte，要求非0位在同一個(gè)完整的byte上）。

（2）Fill-Literal-Fill（FLF），即N個(gè)Fill-group+1個(gè)literal group+N個(gè)fill-group（對(duì)literal group要求同上）。

（3）Fill（F），分為0-Fill和1-Fill，無法按照（1）和（2）進(jìn)行分組的fill-group即歸入此類型。

（4）Literal（L），無法按照（1）和（2）進(jìn)行分組的literal group 即歸入此類型。

圖1 COMPAX壓縮算法示例

對(duì)于這4種類型，就有4種不同的word。

（1）L-word第一位為標(biāo)志位1，余下31b即為原來的literal group。

（2）F-word第一位為標(biāo)志位0，對(duì)于0-Fill第二、三位為00，對(duì)于1-Fill第二、三位為11。余下29b位counter，即記錄有多少個(gè)連續(xù)這樣的group。

（3）LFL-word第一位為標(biāo)志位0，第二、三位為01，第四、五位標(biāo)識(shí)第一個(gè)literal group的非零字節(jié)位置（共4b，標(biāo)號(hào)為0～3），第六、七位標(biāo)識(shí)第二個(gè)literal group的非零字節(jié)位置（共4b，標(biāo)號(hào)為0～3），第八位標(biāo)識(shí)F類型，0為0-Fill，1為1-Fill；第九到十六位為第一個(gè)literal group中非零字節(jié)，第十七到二十四位為Fill的counter，標(biāo)示有多少個(gè)連續(xù)的fill group，第二十五到三十二位為第二個(gè)literal group中的非零字節(jié)。

（4）FLF-word第一位為標(biāo)志位0，第二、三位為10，第四、五位為第一個(gè)fill的類型（0-Fill為00，1-Fill為11），第六、七位為第二個(gè)fill的類型，第八位空閑。第九到十六位為第一個(gè)fill的counter，第十七到二十四位為literal group的非零字節(jié)，第二十五到三十二位為第二個(gè)fill的counter。

在已知COMPAX的情況下，具體讀碼方式如下：

（1）如果第一位為1，為L-word。

（2）如果第一位為0；

1第二、三位為00：0-fill-word。

2第二、三位為11：1-fill-word。

3第二、三位為01：LFL。

4第二、三位為10：FLF。

4 結(jié)語

隨著互聯(lián)網(wǎng)的普及滲透，網(wǎng)絡(luò)日常運(yùn)營中生成積累的用戶行為數(shù)據(jù)往往達(dá)到TB級(jí)甚至PB級(jí)。本文對(duì)數(shù)據(jù)包查詢優(yōu)化過程中的三種位圖索引壓縮算法進(jìn)行研究改進(jìn)，以期為龐大的數(shù)據(jù)流量管理與網(wǎng)絡(luò)流量檔案化提供更多的技術(shù)手段。

[1]Wu K,Otoo E J,Shoshani A.Optimizing bitmap indices with efficient compression[J].Acm Transactions on Database Systems,2006.

[2]Deli&#,ge,Fran&#,Pedersen T B.Position list word aligned hybrid:optimizing space and performance for compressed bitmaps[C]//EDBT 2010,13thInternational Conference on Extending Database Technology，Lausanne,Switzerland,March 22-26,2010.

[3]Fusco F,Stoecklin M P,Vlachos M.Net-Fli:On –thefly Compression,Archiving and Indexing of Streaming Network Traffic.[J].Proceedings of the Vld Endowment，2010.