重慶大學(xué)微電子與通信工程學(xué)院 張家銘

本文提出了一種擴(kuò)展PIE算法，使用新型的數(shù)據(jù)結(jié)構(gòu)Dynamic Cuckoo Filter替代PIE算法中的空時(shí)布隆過(guò)濾器，用Raptor碼編碼對(duì)象的ID信息，大幅降低對(duì)象存儲(chǔ)所需的空間，并在后續(xù)過(guò)程解碼識(shí)別持續(xù)熱點(diǎn)的原始ID。識(shí)別階段，擴(kuò)展PIE算法利用一個(gè)Cuckoo Filter加速熱點(diǎn)查詢過(guò)程，將PIE算法識(shí)別階段的平方時(shí)間復(fù)雜度降低為線性復(fù)雜度。實(shí)驗(yàn)結(jié)果證明，擴(kuò)展PIE算法的查詢時(shí)間復(fù)雜度和空間效率均優(yōu)于PIE算法。

1 研究背景

作為流處理挖掘技術(shù)一個(gè)重要問(wèn)題，高頻熱點(diǎn)挖掘技術(shù)獲得了許多研究人員的關(guān)注，取得了眾多的研究成果。

作為高頻熱點(diǎn)問(wèn)題的廣義擴(kuò)展，持續(xù)熱點(diǎn)識(shí)別是流處理挖掘的一個(gè)新問(wèn)題。在一個(gè)短周期內(nèi)，不同于高頻熱點(diǎn)，持續(xù)熱點(diǎn)并不比其他對(duì)象有更大的出現(xiàn)頻率，卻會(huì)在長(zhǎng)周期內(nèi)連續(xù)出現(xiàn)。持續(xù)熱點(diǎn)挖掘技術(shù)可以應(yīng)用在一系列的應(yīng)用上，如網(wǎng)絡(luò)安全中，持續(xù)熱點(diǎn)挖掘技術(shù)可以檢測(cè)穩(wěn)定的DDoS攻擊，即攻擊者并不在短時(shí)間內(nèi)采用大流量攻擊，而是在很長(zhǎng)的時(shí)間內(nèi)用數(shù)量較少的機(jī)器保持穩(wěn)定的攻擊。

2 PIE算法

2.1 記錄階段

在記錄階段，PIE在給定的觀察周期，記錄下所在觀察節(jié)點(diǎn)的所觀察到的ID信息。在每個(gè)觀察周期的開(kāi)始階段，PIE在SRAM中初始化一個(gè)STBF，并在該周期記錄完畢后將STBF存入固定存儲(chǔ)器中。STBF初始化過(guò)程中，每個(gè)元胞對(duì)應(yīng)的三個(gè)域(標(biāo)志位域，Raptor碼域，信息指紋域)都清零。在觀察周期i觀察到對(duì)象e，PIE有三個(gè)處理步驟：

一、計(jì)算出對(duì)應(yīng)的ID的r位Raptor碼和p位信息指紋。

二、計(jì)算出k個(gè)散列函數(shù)值hy(e)，得到k個(gè)元胞地址。

三、對(duì)于每個(gè)元胞，PIE檢查該元胞是否為空，若為空，則將該元胞的標(biāo)志位置1，存入Raptor碼和信息指紋。若不為空，PIE檢查該元胞中存儲(chǔ)的Raptor碼和信息指紋是否和當(dāng)然對(duì)象e的Raptor碼和信息指紋匹配。若匹配，有極高的概率當(dāng)前對(duì)象在這個(gè)觀察周期內(nèi)已經(jīng)被觀察到，那么當(dāng)前對(duì)象e的信息不予處理。若不匹配，則屬于散列碰撞。PIE將該元胞的標(biāo)志位清零，Raptor碼域和信息指紋域置1。即當(dāng)出現(xiàn)碰撞的情況，PIE不處理該元胞。

2.2 識(shí)別階段

在識(shí)別階段，我們的目標(biāo)是恢復(fù)在T個(gè)觀察周期中出現(xiàn)次數(shù)超過(guò)閾值的對(duì)象ID。為了恢復(fù)ID，PIE將T個(gè)STBF相同地址的元胞作為一個(gè)處理單元，稱為元胞列(cell line)。假設(shè)一個(gè)STBF有m個(gè)元胞，處理過(guò)程中我們就有m個(gè)元胞列。每個(gè)元胞列的處理過(guò)程分為三步，首先，我們排除空的元胞和因?yàn)榕鲎矡o(wú)效的元胞；然后，每個(gè)元胞列中，基于這樣一種認(rèn)識(shí)：信息指紋相同的ID大概率相同，PIE將屬于相同信息指紋的元胞聚為一組。而根據(jù)聚為一類的元胞，利用Raptor碼恢復(fù)ID信息。

圖1 空時(shí)布隆濾波器和元胞列

如 圖1，假設(shè)k=3，即使用三個(gè)散列函數(shù)，每個(gè)對(duì)象映射到三個(gè)元胞。為了簡(jiǎn)化問(wèn)題，每個(gè)STBF僅僅插入一個(gè)元素。圖中相同灰度陰影的元胞代表相同的信息指紋(但不一定是相同的元素)。在本例中，x=7的元胞列中，按照陰影灰度可以分為三組。然而STBF2和STBF1、STBF6的插入元素不同，因?yàn)槿齻€(gè)散列值不完全相同。第三步，對(duì)于接下來(lái)的元胞列繼續(xù)相同的操作直到最后一個(gè)元胞列。

恢復(fù)出的ID信息不一定是正確的持續(xù)熱點(diǎn)，所以PIE提出兩步驗(yàn)證策略。第一步是驗(yàn)證信息指紋。將恢復(fù)出的ID經(jīng)過(guò)散列映射成信息指紋，對(duì)比存在STBF中的信息指紋，如果不同無(wú)法通過(guò)檢測(cè)；如果相同進(jìn)行第二步檢測(cè)，用k個(gè)散列函數(shù)將恢復(fù)出的ID映射到k個(gè)位置，對(duì)比存在STBF中的k個(gè)位置，如果相同即判斷恢復(fù)出的ID是持續(xù)熱點(diǎn)。

3 擴(kuò)展PIE算法

擴(kuò)展PIE算法分為兩個(gè)階段：記錄階段和識(shí)別階段。記錄階段，不同于PIE在每個(gè)記錄周期初始化一個(gè)STBF，因?yàn)镈CF的動(dòng)態(tài)增長(zhǎng)特性，我們只需要在每一個(gè)處理周期開(kāi)始初始化一個(gè)DCF，在識(shí)別階段處理這個(gè)DCF即可。在識(shí)別階段，初始化一個(gè)Cuckoo Filter作為查詢階段的從初始地址開(kāi)始按地址相同的桶處理，我們稱之為桶列。

記錄階段，一開(kāi)始初始化一個(gè)DCF在SRAM中，每個(gè)Cuckoo Filter由m個(gè)桶組成，每個(gè)桶包含n個(gè)入口(n一般是4的倍數(shù)，如4或8)。每個(gè)入口由兩個(gè)域組成，一個(gè)Raptor碼域，另一個(gè)是信息指紋域。Raptor碼域存儲(chǔ)原始ID信息經(jīng)過(guò)編碼得到的r位，一般來(lái)說(shuō)r遠(yuǎn)小于原始ID信息的位數(shù)存儲(chǔ)需求。信息指紋域是原始ID信息經(jīng)過(guò)一次散列映射得到的p位固定長(zhǎng)度數(shù)。因?yàn)椴煌^察周期相同ID的raptor碼不同，所以我們需要有統(tǒng)一的信息指紋信息來(lái)標(biāo)識(shí)，相同的ID得到的信息指紋一定相同，所以處理過(guò)程中我們查詢到相同的信息指紋，那么有極大的概率是相同的ID經(jīng)過(guò)散列映射得到的。當(dāng)然，因?yàn)樯⒘信鲎驳脑?，不同的ID信息也有一定的概率映射為相同的信息指紋，故而我們會(huì)引入兩步驗(yàn)證確保信息指紋來(lái)自于相同的ID。

對(duì)于元素e，首先第一步是數(shù)據(jù)準(zhǔn)備過(guò)程。計(jì)算出其插入DCF的地址i1=hash1(e)，然后我們計(jì)算出其信息指紋f =hash2(e)，根據(jù)地址和信息指紋我們得到該元素的備選地址。經(jīng)過(guò)Raptor編碼得到rap = Raptor code(e)。第二步是插入Cuckoo Filter。首先查詢i1是否有空的入口，若有入口，將Raptor碼和信息指紋存入該入口，即Raptor碼存入Raptor域，信息指紋存入信息指紋域。若無(wú)空間，查詢備選地址i2是否有空的入口，有即插入，若還是沒(méi)有，隨機(jī)選取一個(gè)入口，將存入其中的信息(Raptor碼和信息指紋)踢出，然后插入該入口。被踢出的元素查詢自身的備選地址，有空間即插入，沒(méi)有空間即重復(fù)這個(gè)踢出過(guò)程，知道所有的元素都成功插入或者達(dá)到最大踢出次數(shù)而失敗。在插入失敗后，我們申請(qǐng)一個(gè)新的Cuckoo Filter，將插入失敗的元素插入新的表中。

識(shí)別過(guò)程，經(jīng)過(guò)T個(gè)觀察周期后，我們此時(shí)有s張Cuckoo Filter組成的DCF。我們將s張表中相同地址的桶組成一列處理，稱之為桶列。每個(gè)桶有n個(gè)入口，故我們有每一個(gè)桶列最多有s×n個(gè)對(duì)象。我們初始化一個(gè)Cuckoo Filter，稱為Query Filter(QF)。來(lái)存儲(chǔ)桶列查詢信息。具體做法如下：對(duì)于每個(gè)桶列，從第一張開(kāi)始處理，按順序取信息指紋，對(duì)其做散列映射，映射到QF中。QF的每個(gè)入口由三部分組成，信息指紋域，計(jì)數(shù)域和Raptor碼域。信息指紋域用來(lái)存儲(chǔ)每個(gè)桶列的信息指紋，計(jì)數(shù)域就是一個(gè)計(jì)數(shù)器，插入一個(gè)信息指紋置1，倘若發(fā)現(xiàn)待插入的信息指紋已經(jīng)存在，計(jì)數(shù)值加一。當(dāng)計(jì)數(shù)值達(dá)到閾值時(shí)，作為觸發(fā)條件啟動(dòng)解碼，恢復(fù)檢測(cè)到的持續(xù)熱點(diǎn)ID信息。若計(jì)數(shù)值為1時(shí)，表明沒(méi)有重復(fù)的信息指紋，Raptor域存儲(chǔ)Raptor碼。若計(jì)數(shù)值大于1，Raptor域存儲(chǔ)指針，指向存儲(chǔ)不同Raptor碼的數(shù)據(jù)段。

圖2 不同大小數(shù)據(jù)集下空間大小變化曲線

圖3 不同大小數(shù)據(jù)集下假陰性率變化曲線

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

我們以PIE算法為基準(zhǔn)，對(duì)比兩種算法的性能，輸入的數(shù)據(jù)集對(duì)比空間效率和假陰性率。

由圖2可見(jiàn)，在我們的測(cè)試集上，PIE算法的空間效率比PIE算法要高出47%，因?yàn)镻IE算法需要映射到k個(gè)元胞中以應(yīng)對(duì)散列碰撞問(wèn)題，而擴(kuò)展PIE算法只需要存儲(chǔ)到一個(gè)入口中即可，具有更高的空間效率。

由圖3可見(jiàn)，PIE算法的假陰性率略高于擴(kuò)展PIE算法，這個(gè)性能提升來(lái)自于處理散列碰撞階段處理策略，因?yàn)閿U(kuò)展PIE算法保留了所有的信息，所以獲得了更好的假陰性率。

擴(kuò)展PIE算法主要考慮實(shí)時(shí)應(yīng)用場(chǎng)景，對(duì)于時(shí)間復(fù)雜度和空間效率的需求更重要，所以犧牲了一定的識(shí)別率，大幅度提高時(shí)空效率。

參考：H Dai, M Shahzad, AX Liu, Y Zhong. Finding persistent items in data streams[J]. Proceedings of the Vldb Endowment.2016；G. S.Manku, R. Motwani. Approximate frequency counts over data streams[C].In Proc. VLDB. Hong Kong, China, 2002；A. Metwally, D. Agrawal,and A. El Abbadi. Efficient computation of frequent and top-k elements in datamstreams[C]. In Proc. ICDT, Vienna, Austria, 2005；M.Charikar,K.Chen,and M.Farach-Colton. Finding frequent items in data streams[C]. In Automata, Languages and Programming.Malaga,Spain,2002；G.Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and itsapplications[J]. Journal of Algorithms,2005；B.H.Bloom.Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970；Byers J W, Luby M, Mitzenmacher M,et al. A digital fountain approach toreliable distribution of bulk data [J].ProcAcm Sigcomm98 Vancouver Canada Sept, 1998；A.Shokrollahi.Raptor codes[J].IEEE Transactions on Information Theory,2006；R. Pagh and F. Rodler. Cuckoo hashing[J]. Journal of Algorithms. 2004；B. Fan,D.G.Andersen, M. Kaminsky, and M.Mitzenmacher.Cuckoo filter:Practically better than bloom[C].inCoNEXT. Sydney, Australia,2014。