PR-Sketch 阅读笔记

流数据它是一组顺序、大量、快速、连续的数据序列。一般来说，流量数据可以被视为随着时间的推移而无限增长的动态数据集。

本文实现在有限每键信息的资源使用高覆盖率，如果结果覆盖率高，管理员可以专注于处理误报或未检测事件的有限报告。高覆盖率还可以推断每个键聚合的准确分布。它有利于基于分布的任务，如 DDoS 测试，每个任务都集中在单个项目的键上。

准确的每键信息在异常检测、攻击预防和在线诊断中发挥着重要作用

两阶段架构通常用于流处理：

1. 更新阶段（维护轻量级数据结构，以有限的内存和计算资源实时处理项目，并将数据结构发送到带宽使用有限的恢复阶段）[关键点：如何在有限的资源中以更高的处理精度处理实时数据流]
2. 恢复阶段(从资源充足的数据结构中检索统计信息)

在有限的资源下，现有的方法无法实现高覆盖率

图2的目标是实现95%的覆盖率，每种方法的最低内存至少为46%MB，甚至达到100MB

图3采用复杂的键跟踪机制，需要超过50%的内存或超过40%的处理时间

在基于草图的技术路线中，现有的方法对大多数键都有很高的错误率，根本原因是：

• 在更新阶段，通过复杂的机制跟踪键(一方面导致内存和计算资源不足；另一方面，更新阶段有限的内存只能存储有限数量的键)
• 在恢复阶段，通过计算器简单地计算每键聚合(哈希冲突不能容忍，导致严重的相对误差)

本文提出了一种新的草图设计PR-Sketch，主要优化了两个阶段的过程：

• 在更新阶段建立计数器和每个键之间的线性方程，以提高准确性
• 在恢复阶段记录键，以减少更新阶段资源的使用

具体来说，PR-Sketch 线性方程系统建立在计数器值和每键聚合之间，并找到最佳解决方案。它容忍哈希冲突，从而提高了覆盖率。此外PR-Sketch 将键记录部分从更新阶段转移到恢复阶段。特别是在更新阶段，通过轻量级数据结构识别新键。然后，它以很少的带宽成本将密钥发送到恢复阶段并记录下来进一步分析。在更新阶段，为了节省内存，减少哈希冲突，可以在恢复阶段记录任何丰富的资源键，避免关键信息丢失。

（ a 1 , a 2 , a 3 , . . . , a S ） （a_1, a_2, a_3, ..., a_S） （a1,a2,a3,...,aspan class="pstrut" style="height: 2.7em;">S​）是每个epoch时间内固定输入的一系列项目，每个项目$$a_i$$定为一个键值元组$$（x,u_x）$$，目标就是为了计算流上的每键聚合：即统计同属于一个键名x的所有值$$u_x$$的和

在这里每键聚合的一些信息用法：在给定用户提供的阈值情况下，将聚合大于阈值的热键称为heavy hitters（频繁项）；连续两个epoch中聚合变化大于阈值的称为heavy changers（重变化者）

• 在更新阶段，维护一些数据结构来记录每个 epoch 中的每个键的聚合。由于底层实体通常具有有限的资源，因此数据结构必须是轻量级的。在 epoch 结束时，将数据结构从更新阶段发送到恢复阶段。

• 恢复阶段在逻辑上是集中的，它分析接收到的数据结构以检索最终结果。

• 更新阶段
  • 键识别（维护了一个数据结构识别键并将其转移到恢复阶段）
  • 聚合记录（记录聚合）
• 恢复阶段
  • 键记录（存储被传输过来的键，这里减少了更新阶段键跟踪机制的资源使用）
  • 基于等式的恢复（根据键记录和聚合记录发送过来的草图数据恢复每键聚合）

2. 更新阶段算法

   如何在更新阶段更新 PR-Sketch

• 过滤器部分（用于键识别）
  • 一个一维数组$$A_f$$，每个位置用一个比特（0或1）来表示x是否为一个新键
  • 与一个独立的哈希函数$$k_f$$相关联，用$$h_{fi}$$表示
  • 对传输过来的项来说，每次要检查通过$$k_f$$映射后的$$A_f$$中的位状态，识别出x是新键就将其发送到恢复阶段
• 记数部分（聚合记录）
  • 一个一维数组$$A_c$$，每个位置用一个32位大小的计数器记录聚合
  • 与一个独立的哈希函数$$k_c$$相关联，用$$h_{ci}$$表示
  • 对传输过来的项来说，对通过$$k_c$$映射的位置加$$v_x$$，每个epoch后将$$A_c$$发送到恢复阶段
• 转发器（连接过滤器部分和记数部分）

过滤器部分确保最多为每个键的第一个项发送一次，节省开销，但是记数部分依旧会加$$v_x$$

3. 恢复阶段算法

   如何通过基于方程的恢复来恢复每个键的聚合

给定健集合$$\chi$$和记数部分的数组$$A_c$$，利用哈希函数构建系数矩阵$$M$$，图中在$$M$$的第一列，只有$$h_{c1}(x)和h_{c2}(x)$$有哈希值，所以值为1。最后调用过程 LeastSqareEqationSolver 来恢复每个键的聚合$$V$$

LeastSqareEqationSolver是通过迭代方法解决最小二乘问题的共轭梯度求解器

4. Fast PR-Sketch

这是在PR-Sketch的基础上不影响覆盖比例的情况下减少了哈希运算的改进算法，通过减少不必要的哈希操作来提高处理速度

与PR-Sketch的区别在于多增加了一个pruner，在更新记数部分之前，转发器查询$$A_c$$中映射位置的最小计数器值并将其转发给剪枝器，如果最小计数器值不大于预定义的阈值，则修剪器利用确定性策略将项目标记为 𝑥 的第一个。

在相同的内存条件下，PR-Sketch在准确率、召回率、F1分数、覆盖率上都接近100%