【论文阅读】-- Omnisketch：高效的多维任意谓词高速流分析

---

摘要

不同学科的一个关键需求是对快节奏的数据流执行分析，其性质类似于关系数据库中的传统 OLAP 分析，即使用过滤器和聚合。然而，由于存储要求高，以及存储海量数据时引入的延迟，存储无界流不是一种现实或理想的方法。因此，已经提出了许多概要/草图，它们可以在小内存（通常足够小以存储在RAM中）中总结流，这样就可以有效地近似聚合查询，而无需存储整个流。然而，过去的概要主要关注对单一属性流的总结，无法有效地处理对多个属性的任意子集进行过滤和约束。在这项工作中，我们提出了OmniSketch，这是第一个能够适应快节奏和复杂数据流（具有许多属性）的草图，并支持在查询时动态选择多个属性的过滤器的计数聚合。该草图提供概率保证、有利的空间精度权衡以及更新和查询执行的最坏情况下的对数复杂度。我们通过对真实和合成数据的实验证明，该草图优于最先进的技术，并且可以在配置好的精度保证下，以较小的内存需求近似复杂的临时查询。

PVLDB 参考格式：Wieger R. Punter, Odysseas Papapetrou, and Minos Garofalakis. OmniSketch: Efficient Multi-Dimensional High-Velocity Stream Analytics with Arbitrary Predicates. PVLDB, 17(3): 319 - 331, 2023. doi:10.14778/3632093.3632098

PVLDB 工件可用性：源代码、数据和/或其他工件已在 https://github.com/wiegerpunter/omnisketch 上提供。

1 引言

筛选器和聚合器构成了数据分析的主力，并在所有数据库中实现。因此，已经实施了索引和存储技术，以有效地回答此类查询，即使在大数据上也是如此。当涉及到无法完整存储或实时查询的流数据时，首选技术基于草图 [5]：小内存数据结构，用于汇总流，随后可用于执行聚合查询。文献中的示例草图支持计数、范数和连接聚合的估计 [2， 6， 23]）、集合大小的估计 [9] 以及频繁项目和重击者的识别 [4]。

尽管被大量使用，但迄今为止，大多数草图都侧重于根据单个属性或预先选择的属性组合来总结频率分布。例如，考虑网络监控领域，其中 Count-min 草图经常用于统计维护 [6]。标准 IPv4 数据包报头定义至少 13 个字段/属性，包括版本、报头长度、总长度、DSCP 代码点、源地址和目标地址、协议，以及 30 个附加选项中的一个或多个。为了能够估计满足属性值组合（在查询时定义）的数据包数，我们需要构造一个草图，该草图使用这些属性的组合值（例如，它们的串联）作为键。作为运行示例，考虑图 1 中简化的 IPv4 标头流，它包含 13 个属性中的 4 个。为了总结每个 IP 地址发送的数据包数的分布，我们需要一个使用 ipSrc 作为密钥构建的草图。需要在 ipDest 上再绘制一个草图，以汇总每个 IP 地址接收的数据包数。如果我们还想汇总任意两个 IP 地址之间交换的数据包数，我们需要维护一个草图，该草图使用源-目标 IP 地址的串联作为键。为支持任意谓词（在此示例中，标题中包含的 13 个字段的任意子组合）而需要维护的草图数总计为 O （213） – 幂组的大小。将其推广到任意用例，估计 p 谓词的所有子组合的频率分布需要维护 2p − 1 草图。这显然是不可行的，因为空间要求和数据流上下文中出现的严格的效率限制。1

我们的贡献。在这项工作中，我们提出、分析和评估了一种名为 OmniSketch 的新型草图工具，它通过将草图与采样相结合，有效地解决了空间和时间效率问题。OmniSketch 结合了草图的紧凑性（这是减少内存约束所必需的）和采样的通用性（这是支持常规查询的关键），适用于在查询时动态决定的谓词。简而言之，用于汇总 p 属性数据流的 OmniSketch 由 p 个单独的小内存子草图组成，每个子草图都类似于 Count-Min 草图。但是，与 Count-Min 草图不同的是，OmniSketch 子草图中的单元格包含哈希到其中的所有记录的固定大小的摘要。在查询时，将定位并查询与查询相关的子草图以及每个子草图中的相关单元格，以估计答案。与以前的工作不同，OmniSketch 提供了计算复杂性（用于更新和查询），该复杂性随属性数量线性扩展（而不是指数级），使其成为迄今为止唯一可行的通用解决方案，用于在狭小空间内汇总具有许多属性的快节奏流。我们的草图以提供形式错误保证的理论分析为后盾，以及基于理论分析的自动初始化算法，以充分利用可用的草图存储器。

我们在真实和合成生成的流上对 OmniSketch 进行了实验性评估，并将其与最先进的竞争对手 Hydra 进行了比较。我们的实验证实，OmniSketch 是汇总复杂流的唯一可行选择，并且具有有利的复杂性和准确性权衡。相比之下，Hydra 在汇总具有五个或更多属性的流时变得非常慢，因此无法有效地汇总快节奏的流。

路线图。本文的其余部分结构如下。在第 2 节中，我们介绍了初步情况并讨论了相关工作。在第 3 节中，我们介绍了 OmniSketch 并分析了其理论特性，而第 4 节总结了我们的实验结果。我们总结了这项工作，并在第 5 节中总结了未来的计划。

2 预备知识及相关工作

预备知识。OmniSketch 继承了 CountMin 草图 [6] 的基本结构，并建立在 k-minwise 哈希理论 [22] 的基础上。现在，我们将简要介绍这两部作品，以深入理解我们的工作。

计数-最小素描（Count-Min Sketch）。由Cormode和Muthukrishnan于2005年提出[6]，计数-最小素描已成为数据流分布汇总的事实标准方法。一个计数-最小素描CM是一个二维数组，宽度为w，深度为d，并伴随有d个两两独立的哈希函数，将输入映射到范围 { 1 , . . . , w } \{1, ..., w\} {1,...,w}内。设$CM[j,h_j(\cdot )]$表示二维数组中第j行，第$h_j(\cdot )$列的计数器。一条记录r（例如，一个IP地址）通过增加$CM[j,h_j(r)]$处的计数被添加到素描中一次，其中j属于 { 1 , . . . , d } \{1, ..., d\} {1,...,d}。流中任何查询q的到达次数估计是通过查找每行j对应的单元格$CM[j,h_j(q)]$，并返回最小计数值，即 f ^ ( q ) = m i n j ∈ { 1 , . . . , d } ( C M [ j , h j ( q ) ] ) \hat{f}(q) = min_{j\in\{1,...,d\}}(CM[j,h_j(q)]) f^​(q)=minj∈{1,...,d}​(CM[j,hj​(q)])。由于哈希冲突（除了q之外落在相同计数器上的其他项）f̂(q)可能是真实频率f(q)的过高估计。通过设置w = ⌈e/ε⌉和d = ⌈ln(1/δ)⌉，我们有f̂(q) - f(q) ≤ εN的概率≥1-δ，其中N是流的长度。

计数-最小草图（Count-Min sketches）也支持范围查询，通过将范围分解为规范覆盖（canonical covers）[6]来实现。为属性 $a$ 添加范围查询的支持会使得空间和时间复杂度大约增加一个$O(\log (|D(a)|))$的因子，其中(D(a))表示该属性的域。

由于计数-最小草图（Count-Min sketches）具有吸引人的成本-精度权衡，因此在快速数据流上维护多个草图也是可能的，每个草图总结一个属性。例如，我们的运行示例（图1）的数据流可以被4个单独的计数-最小草图所概括，这使得能够对以下四种过滤条件中的任何一种进行频率估计：WHERE ipSrc=?, WHERE ipDest=?, WHERE totalLen=?, WHERE dscp=?（其中？表示谓词值）。然而，计数-最小草图不支持在同一查询中使用多个谓词，例如，WHERE ipSrc=? AND ipDest=?。如果这些谓词组合在观察数据流之前已知，那么可以为每种组合构建一个单一的草图，索引属性的串联。例如，为了支持查询WHERE ipSrc=? AND ipDest=?, 我们可以为每条记录构造一个复合键<ipSrc,ipDest>，并将其汇总到一个草图中。然后，具有两个属性作为谓词集的查询可以通过以类似方式构建查询的复合键，并对其进行查询来回答。但是，如果这些谓词组合不是事先知道的，或者如果我们想让用户能够使用任意的属性组合进行查询，那么总结具有n个属性的流需要构建$2^n-1$个草图，以覆盖所有可能的谓词组合。因此，从时间和空间复杂度的角度来看，这种做法不是一个可行的解决方案。

K-minwise 哈希。在这项工作中，我们依靠最小散列来估计多个集合的交集的基数。所有最小哈希方案背后的关键思想是使用一个或多个哈希函数对每个集合中的所有项目进行哈希处理，并且仅保留每个哈希函数具有最小哈希值的 B 项作为每个集合的样本。然后，可以缩放不同集合的这些样本的交集大小，以估计集合交集的基数。

我们在这项工作中将要使用的K-minwise哈希算法估计集合交集的基数如下[22]：设$R_1,R_2,\dots ,R_p$表示我们想要估计其交集基数的 $p$ 个集合。首先，我们通过使用全局哈希函数 g ( ⋅ ) → { 0 , 1 } b g(\cdot) \rightarrow \{0, 1\}^b g(⋅)→{0,1}b对每个集合$R_i$中的每一项进行哈希，并保留 $B$ 个最小的哈希值来构造每个集合的摘要 $S_i$，其中 $b$ 至少设置为$\lceil \log (4B^{2.5}/\delta )\rceil$。然后，我们可以从这些摘要中估计 $p$ 个集合的交集的基数 $|R_{\cap }|=|R_1\cap ...\cap R_p|$ 为${\hat{R}}_{\cap }=|{\bigcap }_{i=1}^p{S}_i|\ast n_{max}/B$，其中 $n_{max}={\max }_{1\le i\le p}|R_i|$ 。当 ${\hat{R}}_{\cap }\ge 3n_{max}\log (2p/\delta )/(B{ϵ}^2)$时，此估计具有((\epsilon, \delta))保证。当上述条件不满足时，可以证明一个较弱的界：以概率 $1-\delta /\sqrt{B}$，有 $0\le |R_{\cap }|\le 4n_{max}\log (2p/\delta )/(B{ϵ}^2)$ 。

我们选择了 K-minwise 哈希而不是其他采样方法，因为该算法已被证明性能同样好或优于其他采样方法（包括 [3， 16， 18]），并且空间复杂度几乎与问题的理论下限相匹配 [22]。此外，所选算法也适用于流数据，因为样本可以增量维护。

数据流模型和支持的查询。输入数据是一个记录流，例如，类似于图1中我们持续示例的记录。设A = {