大规模实时分位数计算——Quantile Sketches 简史

概念及入门

前言

在数据领域，有几类经典的查询场景：

想要统计某段时间内访问某网站的 UV 数，或是统计某段时间内既访问了页面 A 又访问了页面 B 的 UV 数，亦或是统计某段时间内访问了页面 A 但未访问页面 B 的 UV 数，通常我们对这种查询叫做基数统计。想要观察某些指标的数据分布，例如统计某段时间范围内访问页面 A 与页面 B 各自的浏览时长 95 分位数、50 分位数，则需要用到分位数统计。想要统计某段时间内播放量最多或者点击率最高的 10 个视频或者文章（热榜列表），则需要用到 TopN 统计。

这几类问题在数据量不大的情况下都是非常容易处理的。我们可以通过遍历 排序轻易而准确的解决这种问题。但一旦数据到达 Billion 量级，常规算法可能要花费数小时甚至数天的时间，并且即使提供充足的计算资源也于事无补，因为这几类问题都难以并行化处理。

DataSketches[1] 就是为了解决大数据和实时场景下的这几类典型问题而诞生的一组算法，最初由雅虎开源。这些算法以牺牲查询结果的精确性为代价，可以在极小的空间内并行、快速地解决上述几类问题。

Sketch 结构的核心思想

Sketch 结构即「数据草图」结构，主要是为了计算海量的流式数据的概率指标而设计的一种数据结构。一般占用固定大小的内存，不随着数据量的增加而增大。这种结构通过巧妙地保存或丢弃一些数据的策略，将数据流的信息抽象存储起来，汇总成 Sketch 结构，最终能根据 Sketch 结构还原始数据的分布，实现基数统计、分位数计算等操作。

Sketch、Summary 都可以理解为数据草图，不同论文中使用的称呼不太一致，但是符号一般都是大写的 S。

Sketch 一般具有以下几个特征：

1. 单次遍历

可以把 Sketch 理解为一个状态存储器，它时刻承载着数据流迄今为止的所有历史信息，因此 Sketch 通常是 single-pass 的，只需要遍历一遍数据即可取得所需的统计信息。

2. 占用空间小

传统的统计方式需要维护一个巨大的数据列表，且随着数据的输入越来越大。Sketch 可以在很小的常量空间内摄入海量的数据，通常在 KB 量级。这使得 Sketch 在海量数据的统计中非常有优势。

对于一个包含上亿条数据、包含多个维度组合的数据集，可以在每个维度组合上转化生成一个 KB 大小的 Sketch 结构，从而加快查询。

3. 可合并性

可合并性使得 Sketch 可以自由地分布式并行处理大量数据，因此具有快速、高效的优势。以基数统计 (Distinct Value, DV)为例，要解决的问题是从具有重复元素的数据流中查找不同元素的数量，Sketch 可以轻易地将局部统计结果合并为全局统计结果，而直接计数则做不到这一点，即：

DV(uid | city=北京 or 上海)