流数据持续热点实时识别
发布时间：
ELECTRONICS WORLD・技术交流流数据持续热点实时识别本文提出了一种扩展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 空时布隆滤波器和元胞列• 166 •重庆大学微电子与通信工程学院 张家铭如图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经过散列映射得到的。当然，因为散列碰撞的原因，不 