37-论文阅读笔记：Diamond Sketch Accurate Per-flow Measurement for Big Streaming Data

论文阅读笔记：Diamond Sketch: Accurate Per-flow Measurement for Big Streaming Data

这篇文章是杨仝老师发表在TPDS2019(IEEE Transaction on Parallel and Distributed Systems)(并行与分布式计算领域CCF A类期刊)的文章，面向单流测量(per-flow measurement)提出一种新的sketch架构，称作Diamond sketch，由三部分组成：Increment part(增加部分)、carry part(进位部分)和deletion part(删除部分)，通过将多个原子sketch进行组合，对单流大小估计准确性大大提高。

Abstract

单流测量定义：单流测量(per-flow measurement)是计算机网络中的一个关键问题，其关键任务之一是计算每个流中的数据包数量(对于大流数据)。sketch重要性：sketch是计算任务中最节省内存(most memory-efficient)的数据结构，在分布式系统中得到了广泛的应用。现存sketch缺陷：第一，现有的sketch通常使用许多相同大小的计数器来记录流中的数据包数量，因此计数器被迫足够大以适应最大流的大小。不幸的是，由于大多数流都很小(例如，老鼠流)，只有极少数流很大(例如，大象流)，因此许多计数器表示非常小的值，这是对内存的浪费。第二，sketch通常存储在快速但昂贵的内存中(例如，SRAM)，因此实现高内存效率(high memory efficiency)至关重要。提出方案：为了解决这个问题，我们提出了一个新的sketch，即金刚石sketch(diamond sketch)。diamond sketch由原子sketch(atom sketches)组成，每个原子sketch使用小计数器。Diamond的关键思想是根据需要动态地为每个流分配适当数量的原子sketch，从而优化内存效率(optimizing memory efficiency)。实验结果表明，在保持相当速度的情况下，Diamond sketch的相对误差优于5种典型sketch的508.3倍。我们在GitHub上提供了所有六个sketch的源代码：https://github.com/data-kth/Diamond-Sketch.git

Introduction

1.1 背景和动机

单流测量(per-flow measurement) 是计算机网络中的一个关键问题，它为异常检测(anomaly detection)、容量规划(capacity planning)、会计(accounting)和计费(billing)以及服务提供(service provising)提供信息。定义：在单流测量(per-flow measurement)中，一个基本问题是为大的流数据估计每个流中的数据包数量(流大小)。流标识：一条流通常由数据包头中的五元组字段的特定组合来标识:源IP地址、目的IP地址、源端口号、目的端口号和协议类型。一秒钟的网络数据包含数以亿计的流。真实网络流具有高速(high-speed)和不均匀分布(non-uniform distribution) 两个特点。一方面，网络流量的速度非常快，很难精确记录流量的大小。另一方面，网络流的大小通常是非均匀分布的，这意味着一小部分流的大小非常大(大象流)，而大多数流的大小很小(老鼠流)。这类网络流量的两个典型分布是齐夫分布Zipfian和幂律分布Powerlaw，其大小符合Zipfian分布的流量称为偏斜网络流量(skewed network traffic)。

由于网络流量的第一个特点——高速(high speed)，用sketch对数据进行近似记录和估计(approximately recording and estimating)得到了流行。sketch特性：sketch是一种概率数据结构，可以实现小内存占用(small memory footprints)、高精度(high accuracy)和快速的插入和查询(fast speed of insertions and queries)。sketch在分布式系统测量中扮演重要角色，因为他能够对整个系统进行全网测量。分布式sketch节点进行网络测量流程：在经典场景中，数据中心有许多监视节点，每个节点运行一个sketch来监视网络流。收集者将从这些sketch中收集所有数据并产生有用的信息。缺陷：现有的sketch在均匀流量(uniform traffic)上工作得很好。不幸的是，由于网络流量的第二个特征——非均匀分布(non-uniform distribution)，它们在实践中不能很好地工作。具体来说，传统的sketch(如CM， CU， Count， CSM sketch)使用相同大小的计数器来存储数据包的数量。一方面，大象流通常被认为比老鼠流更重要，因此计数器需要足够大以表示大象流的最大大小。另一方面，大量的鼠标流意味着大多数计数器将只表示一个小值，并且这些计数器中较高的位都是0，导致内存浪费。此外，sketch的内存使用是有限的，因为为了赶上高速的网络流量，sketch应该存储在快速内存fast memory(如SRAM, Static RAM)中。与DRAM(动态RAM)相比，SRAM的速度要快几十倍，但价格要贵得多，而且大小有限。因此，有限的内存大小和较大的计数器导致计数器数量有限，这进一步导致了sketch的高碰撞率，最终大大降低了sketch的准确性。本文的目标是设计一种新颖的sketch，可以实现比现有技术更高的精度，特别是在使用很小的内存占用处理非均匀分布的网络流量时(processing non-uniformly distributed network traffic using just a small memory footprint)。

1.2 提出的方法

我们提出了一个新的sketch，即钻石草图(diamond sketch) ，因为它采用了钻石形状(diamond shape)。一个Diamond sketch由许多小的sketches组成，他们的计数器有非常小数量的比特(即4比特)。每一个小的sketch叫做碳原子sketch(carbon atom sketch)或者一个原子sketch(atom sketch)。因为一个Diamond sketch是由许多碳原子sketch组成的，类似于一个金刚石(diamond)有许多碳原子组成。

Diamond的关键思想是按需将原子sketch分配给流。Diamond由增量部分(Incremnet part)、进位部分(carry part)和删除部分(deletion part) 组成。增量部分和进位部分用于插入和查询，删除部分用于删除。这三个部分都由原子sketch组成:增量部分包含几个原子sketches，进位部分和删除部分都只包含一个原子sketch。

我们推荐使用CU sketch作为原子草图(atom sketch)，因为它易于实现(easy implementation)，效率高(high efficiency)，精度高(high accuracy)。这里我们简要地展示CU sketch是如何工作的。具体来说，CU sketch是一个包含w个计数器和k个独立哈希函数$h_i(.)(1\le i\le k,1\le h_i(.)\le w)$ 的数组A。给定一个传入数据包，它首先从数据包的报头中获取流ID，计算k个哈希函数并定位k个映射计数器。然后，它只将最小的计数器加1。可以有多个最小的计数器，我们需要将所有最小的计数器增加1。查询流ID时，计算k个哈希函数，并返回k个映射计数器的最小值。

事实上，原子sketch可以是本文所提到的任何一种普通sketch。例如，如果我们使用CM草图作为我们的原子sketch，由于CM sketch和CU sketch之间的相似性，插入和查询的算法保持不变。至于删除部分，我们甚至不需要它，因为CM sketch本身支持删除，因此可以进一步减少内存使用。然而，由于在网络测量中删除操作的频率远低于插入操作，并且使用CU sketch作为原子 sketch可以获得更高的精度，因此我们将主要讨论使用CU sketch作为原子sketch的数据结构。

Diamond sketch由三部分组成:增量部分(Increment part)、进位部分(carry part)和删除部分(deletion part)。每个部分由一个或几个原子sketches组成。

Increment part: 如图一所示，Diamond sketch的increment part是由d个原子sketch组成：$I_1,I_2,\cdots ,I_d$ ，其中$I_j$ 有$L_j$ 个计数器，$j$ 被叫做sketch $I_j$ 的深度(depth)，$d$ 被叫做Diamond sketch的深度(depth)。所有这些原子sketch的每个计数器有$w_1$ 个比特，$w_1$ 通常是非常小的(即$w_1$ =4)，因此溢出可能会频繁发生。为了记录一个即将到来的数据包，我们首先把它插入到第一个原子sketch$I_1$ 中，如果$I_1$ 中相应的计数器溢出，我们将其插入到$I_2$ 中，以此类推，直到这里没有溢出，或者最低层$I_d$ 的计数器溢出。

Carry part: 为了记录每个流的溢出状态，我们也需要一个进位部分(carry part)(一个原子sketch C，如图所示)去告诉最深层sketch一个流已经被插入了。假设某流在插入原子sketch $I_1$ 和$I_2$ 时引起溢出，并成功插入到$I_3$ 中，则3称为该流的溢出深度(overflow depth of the flow)。我们在原子sketch C中查询这个流，如果查询结果是2，这意味着这个流是第一次插入到$I_3$ 中，我们需要通过将这个流插入到C中来更新进位部分。否则，我们不更新carry part，carry part在查询操作也会被需要。

当查询流时，我们首先在原子sketch C中查询它。假设结果是a，这意味着我们需要在$I_1,I_2,\cdots I_a$ 中查询这个流，计算查询结果。

Deletion part: 单流测量通常不需要删除，因为每个流的大小不会随着网络流量的增加而减少。尽管删除并不总是必需的，但在某些需要删除的场景中(例如，当流结束时，一些应用程序需要从sketch中删除其信息)，Diamond可以通过添加删除部分(deletion part)来支持此操作，这也是一个原子草图(atom sketch)。

除了单流测量(per-flow measurement)之外，Diamond还可以应用于计算机网络中的其他重要问题，如top-k问题和多集成员查询问题(multiple-set membership query problems) 。

1.3 关键贡献

• 我们提出了一种新颖的sketch，即Diamond sketch，用于准确快速地记录和查询实际网络流量中的流量大小。
• 我们使用Diamond sketch来解决另外两个重要的网络问题:top-k和多集成员查询(multiple-set membership query problems)
• 我们进行了大量的实验，结果表明，我们的Diamond sketch在流量大小估计的相对误差方面优于现有技术中的最佳方案两个数量级，并且在处理top-k和多集成员查询问题时也显著优于目前的解决方案。

2. 相关工作

为了解决单流测量(per-flow measurement)问题，提出了三种数据结构:草图(sketch)、布隆过滤器(bloom filter)和计数器(counters) 。更多细节可以参考这篇综述：G. Cormode, “Sketch techniques for approximate query processing,” Synposes for Approximate Query Processing: Samples, Histograms, Wavelets and Sketches, Foundations and Trends in Databases. NOW publishers, 2011.

Sketches: 我们选择了本文中最流行的五种草图sketch，分别是CU sketch、Count sketch、CSM sketch、Count-min sketch和Augmented sketch，并与Diamond sketch进行比较。

Count-min (CM) sketch 几乎与CU sketch 相同，除了在插入期间，它向所有k个映射计数器添加1，而不是其中最小的一个(s)。这样，CM sketch就可以支持删除。

对于像CU sketch这样的传统方法，小尺寸的计数器会意外溢出，这可能导致准确性的损失，特别是对于大流量。然而，在大多数情况下，对大流量的测量是最关键的部分，例如finding heavy hitters、finding heavy changes、finding SuperSpreaders、finding network anomaly。减少CU sketch的计数器的大小将限制其使用。

相比之下，由于我们的数据结构更合理地为大流和小流分配计数器，因此可以在不同的场景下实现较高的准确性，同时消耗较少的内存使用。

Count © sketch 的结构与CM sketch完全相同，除了k个哈希函数( $h_i(.)(1\le i\le k)$ )之外，Count sketch也联系另外k个哈希函数$g_j(.)(1\le j\le k)$ ，每一个哈希函数等概率地哈希一个流ID到{-1,1}。为了记录一个包以及它的流ID e，Count sketch首先计算$h_i(e)$ 和$g_i(e)(1\le i\le k)$ ，然后添加$g_i(e)$ 到计数器$A[h_i(e)]$ 。当查询一个流ID为e的流时，它会报告 { A i [ h i ( e ) ⋅ g i ( e ) , ( 1 ≤ i ≤ k ) } \{A_i[h_i(e) \cdot g_i(e),(1 \leq i \leq k)\} {Ai​[hi​(e)⋅gi​(e),(1≤i≤k)} 的中位数作为查询结果。

CSM sketch 在插入流ID为e的数据包时计算k个哈希函数，但CSM sketch并没有增加所有k个映射计数器，而是随机增加其中一个。在查询过程中，CSM sketch将k个映射计数器中的值相加，并返回减去噪声值的结果。

Augmented sketch 是建立在其他sketch(如CM sketch或CU sketch)之上的sketch框架。它为现有sketch添加了一个额外的过滤器。要记录流ID为e的数据包，如果e已经在过滤器中，则sketch只需更新其在过滤器中的大小;否则，它将使用该sketch的标准插入操作将其插入到sketch中，并在sketch中查询e。如果e的查询结果大于过滤器中最小的$e^{\prime }$ 的大小，则用e代替$e^{\prime }$ ，并将$e^{\prime }$ 驱逐到sketch中。这种技术将使驻留在过滤器中的流(通常是象流)的查询结果更加准确，但代价是查询和插入速度的降低。

Bloom filter 变种：原始的Bloom过滤器可以判断一条流是否已经出现。后来，Bloom过滤器的几个变体在原始过滤器的基础上进行了增强，使其能够存储流的大小，而不仅仅是确定其是否出现在集合中。这些变体包括计数布隆滤波器Counting bloom filters(CBF)、光谱布隆滤波器spectral bloom filters(SBF)和动态计数布隆滤波器Dynamic Count Bloom filters(DCF)。

有几种用于频率估计的布隆滤波器变体 ，如SBF和DCF，它们使用复杂的技术和许多指针来提高精度，代价是更新缓慢。更糟糕的是，它们无法在硬件中实现。我们的目标是在软件和硬件上实现更高的精度，相当的速度和易于实现。因此，我们没有进行实验来比较Diamond与这些变体的性能

计数器变体:Counter Braids算法在计数时执行压缩compression，并且几乎可以毫无错误地恢复压缩结果。但是，作者承认，它必须事先知道所有流的id，并且不支持瞬时点查询。此外，根据文献，CSM sketch在准确性方面优于Counter Braids。因此，我们的实验中没有使用Counter Braids算法。

本文利用的关键思想似乎与参考文献[26]相似(将计数器分为两组)，但实际上它们非常不同。我们的论文主要关注于减少数据结构的内存使用，以适应小而昂贵的SRAM。存储不存在二分法，而是不同层的sketches，其大小逐渐减小。分配更多计数器给大流通过自然溢出(natural overflows)完成。相反，参考文献[26]侧重于平衡DRAM和SRAM之间的计数器数量和更新速度。最近的更新由SRAM计数器保存，并定期转移到对应的DRAM。[26]中的算法是一种粗略排序算法(rough sorting algorithm)，根据形式化分析得出的阈值将计数器组织到高阶和低阶箱(high and low-order bins)中。

参考文献[26]： S. Ramabhadran and G. Varghese, “Efficient implementation of a statistics counter architecture,” SIGMETRICS Perform. Eval. Rev., vol. 31, no. 1, pp. 261–271, Jun. 2003. [Online]. Available: http://doi.acm.org/10.1145/885651.781060

当我们只使用CU sketch时，为了避免对于通常非常重要的大流的计数器溢出，每个计数器都应该足够大。通过这种方式，对于由小流映射的计数器，它们的较高位将全部为0并被浪费。为了尽量减少这样的内存浪费，Diamond利用自然溢出(natural overflows)并减小增量部分的更深层的大小(reduces size of deeper layers of the increment part)，以便为大流自动分配更多的原子sketch，为小流自动分配更少的原子sketch。

3. The Diamond Sketch

3.1 基本原理

存在问题：真实的数据集通常是不均匀(non-uniform)的或倾斜的(skewed)。对于这样的数据集，现有的sketch将达到较低的精度。为了解决这个问题，我们提出了碳原子sketch (carbon atom sketch)(简称原子草图atom sketch)的概念，这是一个由小计数器(如4位)组成的sketch。插入过程：我们将从一个原子sketch $I_1$ 开始记录项目。由于它的计数器很小，溢出可能经常发生。当发生溢出时，我们使用第二个原子sketch $I_2$ 来帮助记录单个小计数器无法表示的值。$I_2$ 也可能溢出，我们随后可以找到另一个$I_3$ ，以此类推。这样，一个大值的项目将由几个原子sketch中的几个小计数器记录下来。显然，插入到$I_{i+1}$ 中的项数要小于插入到$I_i$ 中的项数。因此，为了实现内存效率，$I_{i+1}$ 的大小应该小于$I_i$ 。此外，那些位于增量部分(increment part)的更深层的计数器将只有在插入期间通过溢出过程的大流才能访问。相比之下，小流大多停留在增量部分的表面(the surface of the increment part)，例如第一层。

效果：换句话说，我们在插入过程中自然地完成了根据每个流的大小分配适当数量的原子sketch的任务。而且，当分布不均匀时，流量大小分布越偏斜，其“尾部”(tail)越长越小，且尾部(小流量)越有可能存储在第一层，而大流量则跨多层存储。这样，无论大流量还是小流量，我们都可以达到很高的精度。

为了在查询项目时计算期望的值，我们还需要记录插入期间每个项目的溢出深度(overflow depth) 。具体来说，当插入项目e时，如果它被插入到$I_1,I_2,\cdots ,I_i$ ，我们需要记录它的溢出深度 i 。有很多方法可以做到这一点，比如在每个计数器上添加一个额外的位来指示它是否溢出，或者对每个原子sketch使用Bloom过滤器来记录遭受溢出的项目。我们最终选择使用另一个原子sketch C来记录每个项目的溢出深度，原因有以下两点。第一，当使用相同大小内存时，sketch比布隆过滤器更加准确。第二，我们使用另一个原子sketch来记录溢出深度，而不是引入异构数据结构，以保持我们的Diamond的同质性(homogeneity)。

我们的sketch可以扩展，以支持在某些应用场景中需要的删除。如前所述，我们建议使用CU sketch作为原子sketch，但是CU sketch不支持删除。为了解决这个问题，我们建议使用另一个原子sketch D 来记录每个项目被删除的频率。当查询项目e时，我们将删除部分(deletion part)报告的值与增量进位部分(increment part and carry part)报告的值相减，作为项目e的估计频率。

总之，我们的sketch由三部分组成:增量部分(increment part)，进位部分(carry part)和删除部分(deletion part) 。增量部分由多个原子草图(atom sketch)组成，进位部分和删除部分均由一个原子草图组成。我们把我们的草图sketch命名为钻石草图(Diamond sketch)，因为我们的整个sketch是由原子sketch组成的，就像钻石是由碳原子组成的一样。

通过将增量部分的原子sketch分层，深层中的大多数计数器将主要用于存储大流量，而小流量将主要记录在浅层中。这相当于在插入不同大小的流时动态分配原子sketch。Diamond sketch的这一关键特性使内存得到了有效的利用，并进一步保证了后续实验的高准确性。此外，在增量部分(increment part)逐渐减小层大小的设计避免了深层内存(memory in the deep layers)的潜在浪费。最后，进位部分的错误率几乎可以忽略不计，因为它存储的值确实很小(不超过增量部分的深度)，这进一步保证了Diamond sketch的整体精度。

3.2 数据结构

Increment part 和carry part 一起记录已经插入的每条流的大小。它由d个原子sketch组成，我们表示第$i^{th}$ 个原子sketch用$I_i$ 表示。每个原子sketch$I_i$ 由$L_i$ 个计数器组成，每个计数器包含$w_1$ 个比特。我们表示第$i^{th}$ 原子sketch的第$j^{th}$ 个计数器用 I i [ j ] . { L 1 , L 2 , ⋯ , L d } I_i[j].\{L_1,L_2,\cdots,L_d\} Ii​[j].{L1​,L2​,⋯,Ld​} 表示，是一个递减数列。carry part记录每个流的溢出深度(overflow depth)，它是一个由$L_C$ 个计数器组成的原子sketch，每个计数器包含$w_2$ 个比特($2^{w_2}\ge d是必备条件$) 。我们用$C$ 表示这个原子sketch，用$C[j]$ 表示第$j^{th}$ 个计数器。deletion part 用来支持删除。它是一个原子sketch，由$L_D$ 个计数器组成，每个计数器包含$w_3$ 个比特。我们用$D$ 表示这个原子sketch，用$D[j]$ 表示第$j^{th}$ 个计数器。

每个原子sketch $I_i,C,D$ 分别联系$k_1,k_2,k_3$ 个哈希函数 ，哈希函数的输出结果均匀分布在$[1,L_i],[1,L_C],[1,L_D]$ 的范围内。我们分别用$h_j^i(.),h_j^C(.),h_j^D(.)$ 表示第$j^{th}$ 个哈希函数。

Diamond sketch的初始化 是简单设置所有计数器$I_i[j],C[l],D[m]$ 为0，其中$1\le i\le d,1\le j\le L_i,1\le l\le L_C,1\le m\le L_D$ 。下面讨论插入、查询和删除操作。

3.3 插入

如算法1所示，给定流ID为e的传入数据包(简称数据包e)，为了增加流量大小，我们首先更新增量部分(increment part)，然后更新进位部分(carry part)。我们计算了第一个原子sketch$I_1$ 的$k_1$ 个哈希函数:$h_1^1(e),h_2^1(e),\cdots ,h_{k_1}^1(e)$ ，并增加$k_1$ 个计数器$I_1[h_1^1(e)],I_1[h_2^1(e)],\cdots ,I_1[h_{k_1}^1(e)]$ (简称为$k_1$ 个映射计数器) 中最小的一个加一。如果有多个计数器具有最小值，则将它们全部加1。如果所有$k_1$ 个计数器的值都是$2^{w_1}-1$ ，这是$w_1$ 位所能表示的最大数字，那么将它们增加1将导致溢出(overflow)。

发生溢出后进行的4个步骤：当$I_i$ 中的$k_1$ 个映射计数器溢出，进行以下4步： 1）设置所有$k_1$ 个映射计数器$I_i[h_1^i(e)],I_i[h_2^i(e),\cdots ,I_i[h_{k_1}^i(e)]$ 的值是0。 2）计算$I_{i+1}$ 的$k_1$ 个哈希函数:$h_1^{i+1},h_2^{i+1},\cdots ,h_{k_1}^{i+1}(e)$ ，增加$k_1$ 个计数器中的最小值$I_{i+1}[h_1^{i+1}(e)],I_{i+1}[h_2^{i+1}(e)],\cdots ,I_{i+1}[h_{k_1}^{i+1}(e)]$ 。 3）如果$I_{i+1}$ 的所有$k_1$ 个计数器溢出，那么重复步骤一和二直到终止条件满足，并且我们记录溢出深度$dep$ 。这里有两个终止条件:在$I_i（1\le i\le d)$ 没有溢出(我们设置$dep$ 为$i$ )，或者最后一个原子sketch $I_d$ 溢出(我们设置$dep$ 为$d$ )。 4）计算Carry part中原子sketch C的$k_2$ 个哈希函数，得到$k_2$ 个计数器$C[h_1^C(e)],C[h_2^C(e)],\cdots ,C[h_{k_2}^C(e)]$中的最小值。如果最小值比$dep-1$ 更小，我们需要更新carry part以保证最小值等于$dep-1$ 。为了实现这样，对于$C[h_1^C(e)],C[h_2^C(e)],\cdots ,C[h_{k_2}^C(e)]$ 中每个计数器，如果它的值比$dep-1$ 更小，我们设置它的值是$dep-1$ 。否则，我们不进行操作。

为了将流大小增加x (x大于1)，我们首先将x添加到第一层具有最小值p的映射计数器中。然后我们再次检查所有映射计数器，对于每个值小于p+x的计数器，我们将其值设置为p+x。

3.4 删除

删除操作在单流测量中不是必需的，但在其他场景中可以根据需要添加。要删除一个包e, Diamond sketch只更新它的删除部分(deletion part)。我们计算D的$k_3$ 个哈希函数$h_1^D(e),h_2^D(e),\cdots ,h_{k_3}^D(e)$ ，并且检查相应的$k_3$ 个计数器$D[h_1^D(e)],D[h_2^D(e)],\cdots ,D[h_{k_3}^D(e)]$ 。如果所有的$k_3$ 个映射的计数器都是$2^{w_3}-1$ ，这是$w_3$ 位所能表示的最大数，我们不进行操作；否则，我们增加$k_3$ 个映射计数器中的最小值加一。

3.5 查询

原理：先检查carry part，得到溢出深度，再检查increment part，利用公式计算查询结果，最后再减去删除部分即可。

当查询流ID为e的流大小时，我们需要检查所有三个部分的状态。第一 ，我们检查carry part部分。具体来说，Diamond sketch计算原子sketch C 的$k_2$ 个哈希函数，返回计数器$C[h_1^C(e)],C[h_2^C(e)],\cdots ,C[h_{k_2}^C(e)]$ 中的最小值。第二 ，我们检查increment part 部分。具体来说，我们对carry part 部分返回的最小值加一，假设这个结果是深度$dep$ ，因此我们需要检查深度原子sketch(dep atom sketches)$I_1,I_2,\cdots ,I_{dep}$ 。对于在这些原子sketch层(dep atom sketches)的每个原子sketch$I_i$ ，我们计算$k_1$ 个哈希函数，并且得到$k_1$ 个映射计数器$I_i[h_1^i(e)],I_i[h_2^i(e)],\cdots ,I_i[h_{k_1}^i(e)]$ 的最小值。一旦所有$dep$ 最小值被计算，由increment part和carry part确定的查询结果可以通过下面公式计算：$V_{insert}={\sum }_{i=1}^{dep}{V}_i\cdot (2^{w_1}{)}^{i-1}$ 。第三，我们需要检查deletion part。具体来说，我们计算原子sketch D的$k_3$ 个哈希函数，在$D[h_1^D(e)],D[h_2^D(e)],\cdots ,D[h_{k_3}^D(e)]$ 中返回最小值$V_{delete}$ 。最终我们计算$V_{insert}-V_{delete}$ 作为查询结果。

3.6 举例

在例子中我们假设：$d=4$ (即increment part 有4层或者说有4个原子sketch)；$(w_1,w_2,w_3)=(4,2,7)$ (即increment part每个计数器$w_1$ 个比特，carry part每个计数器$w_2$ 个比特，deletion part每个计数器$w_3$ 个比特)；$(k_1,k_2,k_3)=(3,3,3)$ (即3个部分分别联系的哈希函数的数量)。

3步走插入过程：为了记录一个数据包e，第一，我们将其插入至increment part部分的原子sketch $I_1$ ，我们计算3个哈希函数，定位3个计数器$I_1[h_1^1(e)],I_1[h_2^1(e)],I_1[h_3^1(e)]$ ，发现所有3个计数器的值都是15，因此增加最小计数器将导致溢出。我们设置所有3个计数器为0，并且将e插入至$I_2$ 。第二， 我们计算3个哈希函数定位3个相应的计数器$I_2[h_1^2(e)],I_2[h_2^2(e)],I_2[h_3^2(e)]$ ,它们分别对应的值是4，8，10，最小值是存储在$I_2[h_1^2(e)]$ 的4。我们增加1，$I_2[h_1^2(e)]$ 变成5。因为$I_2$ 没有溢出，我们记录$dep=2$ ，在下一步更新carry part。第三，我们定位carry part的3个计数器$C[h_1^C(e)],C[h_2^C(e)],C[h_{k_3}^C(e)]$ ,然后$C[h_1^C(e)],C[h_2^C(e)]$ 的值是0，比1更小(通过dep-1=1)，因此我们需要设置$C[h_1^C(e)],C[h_2^C(e)]$ 是1，$C[h_{k_3}^C(e)]$ 有值是3，比1大，因此我们不进行处理。

查询过程：同样，要查询一个数据包$e^{\prime }$ ，我们首先检查进位部分carry part(通过计算三个哈希函数，找到三个计数器$C[h_1^C(e^{\prime })],C[h_2^C(e^{\prime })],C[h_{k_3}^C(e^{\prime })]$，找到最小的值是1，所以我们需要检查原子sketch$I_1$ 和$I_2$ 来确定$e^{\prime }$ 的值。第二步，检查$I_1$ 得到最小值2，检查$I_2$ 得到最小值2。由自增部分(increment part)和进位部分(carry part)决定的查询结果计算如下:2 + 2·16 = 34。第三，我们检查删除部分。删除部分$e^{\prime }$ 的最小值为24，因此最终查询结果为34−24 = 10。

删除：为了删除一个包$e^{\ast }$ ，我们通过将最小的计数器$D[h_2^D(e^{\ast })]$ 从52增加到53来更新删除部分。

3.7 Diamond sketch的其他用途

Top-k: top-k问题是从网络流量中找出k个最大的大象流。一个经典的方法是使用CM sketch和最小堆来解决这个问题。在本文中，我们建议使用Diamond sketch来代替CM sketch。

Multiple-set Membership Query: 给定集合$S_1,S_2,\cdots ,S_n$ ，多集成员查询问题是确定项目e属于哪个集合。

3.8 限制

由于sketch算法家族主要针对可用内存有限的情况，因此我们不会解决维护流标识符(maintaining flow identifiers)的问题，这将消耗大量内存。此外，我们所有的实验都是使用CM、CU、CSM、C和assketch等sketch进行的，这些sketch也不保留流标识符。

4. 性能评价

4.1 评价指标

在固定内存大小的情况下，sketch的性能通常通过准确性(accuracy)和速度(speed)来评估。精度通常用AAE和ARE来衡量，速度通常用吞吐量(Throughput)来衡量。所以衡量指标有：Average Absolute Error(AAE)、Average Relative Error(ARE)、Throughput(单位是Mops，即每秒百万次操作)。

4.2 实验建立

数据集：Real IP trace streams、Real-life transactional dataset、Synthetic datasets。对比实验：5类经典sketch:CM Sketch、CU Sketch、Count sketch、CSM Sketch、Augmented sketch。

5. 结论

单流测量(per-flow measurement)是计算机网络中一个重要议题，sketch是一种流行的数据结构用于解决这类问题。现存sketch缺陷：现有的sketch存储效率较差，而且不够准确，特别是对于非均匀数据集。提出方案：本文提出了包含增量部分(increment part)、进位部分(carry part)和删除部分(deletion part)的钻石草图(diamond sketch)。diamond sketch特性：我们的Diamond sketch可以动态分配适当数量的原子sketch，以按需方式记录每个流的大小，从而可以优化内存效率。对比实验：我们将Diamond sketch与五种典型sketch: CM、CU、Count、Augmented和CSM sketch进行了比较，大量的实验结果表明，Diamond sketch在相对误差方面优于五种典型sketch中的最佳草图，最高可达两个数量级。github代码：https://github.com/data-kth/Diamond-Sketch.git

6.可继续学习的参考文献

[1] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen, “Sketch-based change detection: methods, evaluation, and applications,” in Proc. ACM IMC, pp. 234–247.

[2] X. Li, F. Bian, and et al., “Detection and identification of network anomalies using sketch subspaces,” in Proc. ACM SIGCOMM, 2006, pp. 147–152.

[3] G. Cormode, “Sketch techniques for approximate query processing,” Synposes for Approximate Query Processing: Samples, Histograms, Wavelets and Sketches, Foundations and Trends in Databases. NOW publishers, 2011.

[4] T. Buddhika, M. Malensek, S. L. Pallickara, and S. Pallickara, “Synopsis: A distributed sketch over voluminous spatiotemporal observational streams,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 11, pp. 2552–2566, 2017.

[5] L. Fan, P. Cao, J. Almeida, and A. Z. Broder, “Summary cache: a scalable wide-area web cache sharing protocol,” IEEE/ACM TON, vol. 8, no. 3, pp. 281–293, 2000. (CBF)

[6] S. Cohen and Y. Matias, “Spectral bloom filters,” in Proc. ACM SIGMOD, 2003, pp. 241–252.(SBF)

[7] J. Aguilar-Saborit, P. Trancoso, V. Muntes-Mulero, and J.-L. Larriba-Pey, “Dynamic count filters,” ACM SIGMOD Record, vol. 35, no. 1, pp. 26–32, 2006. (DCF)

[8] S. Ramabhadran and G. Varghese, “Efficient implementation of a statistics counter architecture,” SIGMETRICS Perform. Eval. Rev., vol. 31, no. 1, pp. 261–271, Jun. 2003. [Online]. Available: http://doi.acm.org/10.1145/885651.781060

[9] M. Yu, A. Fabrikant, and J. Rexford, “Buffalo: Bloom filter forwarding architecture for large organizations,” in Proc. ACM Conex, 2009, pp. 313–324

g/10.1145/885651.781060

[9] M. Yu, A. Fabrikant, and J. Rexford, “Buffalo: Bloom filter forwarding architecture for large organizations,” in Proc. ACM Conex, 2009, pp. 313–324

[10] G. Cormode and S. Muthukrishnan, “Summarizing and mining skewed data streams,” in Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 2005, pp. 44–55.