流數據持續熱點實時識別

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

本文提出了一種擴展PIE算法，使用新型的數據結構Dynamic Cuckoo Filter替代PIE算法中的空時布隆過濾器，用Raptor碼編碼對象的ID信息，大幅降低對象存儲所需的空間，并在后續過程解碼識別持續熱點的原始ID。識別階段，擴展PIE算法利用一個Cuckoo Filter加速熱點查詢過程，將PIE算法識別階段的平方時間復雜度降低為線性復雜度。實驗結果證明，擴展PIE算法的查詢時間復雜度和空間效率均優于PIE算法。

1 研究背景

作為流處理挖掘技術一個重要問題，高頻熱點挖掘技術獲得了許多研究人員的關注，取得了眾多的研究成果。

作為高頻熱點問題的廣義擴展，持續熱點識別是流處理挖掘的一個新問題。在一個短周期內，不同于高頻熱點，持續熱點并不比其他對象有更大的出現頻率，卻會在長周期內連續出現。持續熱點挖掘技術可以應用在一系列的應用上，如網絡安全中，持續熱點挖掘技術可以檢測穩定的DDoS攻擊，即攻擊者并不在短時間內采用大流量攻擊，而是在很長的時間內用數量較少的機器保持穩定的攻擊。

2 PIE算法

2.1 記錄階段

在記錄階段，PIE在給定的觀察周期，記錄下所在觀察節點的所觀察到的ID信息。在每個觀察周期的開始階段，PIE在SRAM中初始化一個STBF，并在該周期記錄完畢后將STBF存入固定存儲器中。STBF初始化過程中，每個元胞對應的三個域(標志位域，Raptor碼域，信息指紋域)都清零。在觀察周期i觀察到對象e，PIE有三個處理步驟：

一、計算出對應的ID的r位Raptor碼和p位信息指紋。

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

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

2.2 識別階段

在識別階段，我們的目標是恢復在T個觀察周期中出現次數超過閾值的對象ID。為了恢復ID，PIE將T個STBF相同地址的元胞作為一個處理單元，稱為元胞列(cell line)。假設一個STBF有m個元胞，處理過程中我們就有m個元胞列。每個元胞列的處理過程分為三步，首先，我們排除空的元胞和因為碰撞無效的元胞；然后，每個元胞列中，基于這樣一種認識：信息指紋相同的ID大概率相同，PIE將屬于相同信息指紋的元胞聚為一組。而根據聚為一類的元胞，利用Raptor碼恢復ID信息。

圖1 空時布隆濾波器和元胞列

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

恢復出的ID信息不一定是正確的持續熱點，所以PIE提出兩步驗證策略。第一步是驗證信息指紋。將恢復出的ID經過散列映射成信息指紋，對比存在STBF中的信息指紋，如果不同無法通過檢測；如果相同進行第二步檢測，用k個散列函數將恢復出的ID映射到k個位置，對比存在STBF中的k個位置，如果相同即判斷恢復出的ID是持續熱點。

3 擴展PIE算法

擴展PIE算法分為兩個階段：記錄階段和識別階段。記錄階段，不同于PIE在每個記錄周期初始化一個STBF，因為DCF的動態增長特性，我們只需要在每一個處理周期開始初始化一個DCF，在識別階段處理這個DCF即可。在識別階段，初始化一個Cuckoo Filter作為查詢階段的從初始地址開始按地址相同的桶處理，我們稱之為桶列。

記錄階段，一開始初始化一個DCF在SRAM中，每個Cuckoo Filter由m個桶組成，每個桶包含n個入口(n一般是4的倍數，如4或8)。每個入口由兩個域組成，一個Raptor碼域，另一個是信息指紋域。Raptor碼域存儲原始ID信息經過編碼得到的r位，一般來說r遠小于原始ID信息的位數存儲需求。信息指紋域是原始ID信息經過一次散列映射得到的p位固定長度數。因為不同觀察周期相同ID的raptor碼不同，所以我們需要有統一的信息指紋信息來標識，相同的ID得到的信息指紋一定相同，所以處理過程中我們查詢到相同的信息指紋，那么有極大的概率是相同的ID經過散列映射得到的。當然，因為散列碰撞的原因，不同的ID信息也有一定的概率映射為相同的信息指紋，故而我們會引入兩步驗證確保信息指紋來自于相同的ID。

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

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

圖2 不同大小數據集下空間大小變化曲線

圖3 不同大小數據集下假陰性率變化曲線

4 實驗結果分析

我們以PIE算法為基準，對比兩種算法的性能，輸入的數據集對比空間效率和假陰性率。

由圖2可見，在我們的測試集上，PIE算法的空間效率比PIE算法要高出47%，因為PIE算法需要映射到k個元胞中以應對散列碰撞問題，而擴展PIE算法只需要存儲到一個入口中即可，具有更高的空間效率。

由圖3可見，PIE算法的假陰性率略高于擴展PIE算法，這個性能提升來自于處理散列碰撞階段處理策略，因為擴展PIE算法保留了所有的信息，所以獲得了更好的假陰性率。

擴展PIE算法主要考慮實時應用場景，對于時間復雜度和空間效率的需求更重要，所以犧牲了一定的識別率，大幅度提高時空效率。

參考：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。