流数据持续热点实时识别

重庆大学微电子与通信工程学院 张家铭

本文提出了一种扩展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。