实时数据捕获的百分位数

Question

我正在寻找一种算法来确定实时数据捕获的百分位数.

例如,考虑开发服务器应用程序.

服务器的响应时间可能如下:17 ms 33 ms 52 ms 60 ms 55 ms等.

报告第90百分位响应时间,第80百分位响应时间等是有用的.

朴素算法是将每个响应时间插入列表中.请求统计信息时,对列表进行排序并将值放在适当的位置.

内存使用量与请求数量呈线性关系.

是否有一种算法可以在内存使用量有限的情况下产生"近似"百分位数统计量？例如,假设我想以一种处理数百万个请求的方式来解决这个问题,但只想使用一千字节的内存进行百分位跟踪(丢弃旧请求的跟踪不是一个选项,因为百分位数应该是满足所有要求).

还要求不存在分布的先验知识.例如,我不希望提前指定任何范围的存储桶.

Answer 1

如果您希望在获得越来越多的数据时保持内存使用量不变,那么您将不得不以某种方式重新采样该数据.这意味着你必须应用某种重组计划.你可以等到你在开始重组之前获得一定数量的原始输入,但你无法完全避免它.

所以你的问题实际上是在问"动态分类数据的最佳方法是什么"？有很多方法,但是如果你想最小化你可能得到的值的范围或分布的假设,那么一个简单的方法是平均固定大小为k的桶,具有对数分布的宽度.例如,假设您希望一次在内存中保存1000个值.选择k的大小,比如100.选择最小分辨率,比如说1ms.然后

• 第一个桶处理0-1ms(宽度= 1ms)之间的值
• 第二桶:1-3ms(w = 2ms)
• 第三桶:3-7ms(w = 4ms)
• 第四桶:7-15ms(w = 8ms)
• ...
• 第十桶:511-1023ms(w = 512ms)

这种类型的对数缩放方法类似于散列表算法中使用的分块系统,由一些文件系统和内存分配算法使用.当您的数据具有较大的动态范围时,它可以正常工作.

随着新值的出现,您可以根据需要选择重新取样的方式.例如,您可以跟踪移动平均线,使用先进先出或其他更复杂的方法.有关一种方法(由Bittorrent使用),请参阅Kademlia算法.

最终,重组必须失去一些信息.您对分箱的选择将决定丢失哪些信息的具体细节.另一种说法是,恒定大小的存储器存储意味着在动态范围和采样保真度之间进行权衡; 你如何做出这种权衡取决于你,但就像任何抽样问题一样,没有解决这个基本事实.

如果你真的对利弊感兴趣,那么在这个论坛上没有答案就足够了.你应该研究一下抽样理论.有关该主题的大量研究可用.

对于它的价值,我怀疑您的服务器时间将具有相对较小的动态范围,因此更宽松的缩放以允许更高的公共值采样可以提供更准确的结果.

编辑:要回答您的评论,这是一个简单的分箱算法的例子.

• 您可以在10个箱中存储1000个值.因此每个箱保持100个值.假设每个bin都实现为动态数组('list',Perl或Python术语).

• 当有新值出现时:

  • 根据您选择的bin限制,确定应该存储哪个bin.
  • 如果bin未满,请将值附加到bin列表.
  • 如果bin已满,请删除bin列表顶部的值,并将新值附加到bin列表的底部.这意味着旧的价值观随着时间的推移而被抛弃.

• 要找到第90个百分位数,请对bin 10进行排序.第90个百分位数是排序列表中的第一个值(元素900/1000).

如果您不喜欢丢弃旧值,那么您可以实现一些替代方案来代替使用.例如,当bin变满(在我的示例中达到100个值)时,您可以取最旧的50个元素(即列表中的前50个)的平均值,丢弃这些元素,然后将新的平均元素追加到垃圾箱,留下51个元素的箱子,现在有空间容纳49个新值.这是重组的一个简单例子.

重组的另一个例子是下采样 ; 例如,丢弃排序列表中的每第5个值.

我希望这个具体的例子有所帮助 要点的重点是有很多方法可以实现恒定的内存老化算法; 只有你能根据自己的要求决定什么是令人满意的.

Answer 2

我刚刚发表了关于这个主题的博客文章.基本思路是减少对精确计算的要求,支持"95%的响应需要500ms-600ms或更短"(对于所有精确百分位数为500ms-600ms)

您可以使用任意数量的任意大小的桶(例如0ms-50ms,50ms-100ms,......只适合您的用例).通常情况下,对于最后一个桶中超过特定​​响应时间(例如,Web应用程序为5秒)的所有请求(即> 5000ms)应该不是问题.

对于每个新捕获的响应时间,您只需为其所属的桶增加一个计数器.为了估计第n个百分位数,所需要的只是总计计数器,直到总和超过总数的百分之n.

这种方法每桶仅需要8个字节,允许跟踪具有1K内存的128个桶.绰绰有余地使用50ms的粒度分析Web应用程序的响应时间.

例如,这是我从1小时捕获数据创建的Google Chart(使用60个计数器,每桶200ms):

响应时间http://j.mp/3bTf36

不错,不是吗？:) 在我的博客上阅读更多内容.

Answer 3

我相信这个问题有很多好的近似算法.一个好的第一步方法是简单地使用固定大小的数组(比如说1K的数据).修正一些概率p.对于每个请求,以概率p,将其响应时间写入数组(替换其中的最旧时间).由于数组是实时流的子采样,并且由于子采样保留了分布,因此对该数组进行统计将为您提供完整实时流的统计数据的近似值.

这种方法有几个优点:它不需要先验信息,并且易于编码.您可以快速构建它,并通过实验确定,对于您的特定服务器,增长缓冲区对答案的影响可以忽略不计.这是近似足够精确的点.

如果您发现需要太多内存来为您提供足够精确的统计信息,那么您将需要进一步挖掘.好的关键词是:"流计算","流统计",当然还有"百分位数".你也可以尝试"愤怒和诅咒"的方法.

Answer 4

(问这个问题已经有一段时间了,但我想指出一些相关的研究论文)

在过去几年中,对数据流的近似百分位数进行了大量研究.一些有趣的论文,包含完整的算法定义:

• 一种快速算法用于高速数据流中的近似分位数

• 用于数据流上偏置分位数的空间和时间有效的确定性算法

• 有效计算数据流上的偏差分位数

所有这些论文都提出了具有亚线性空间复杂度的算法,用于计算数据流上的近似百分位数.

Answer 5

尝试使用论文“Sequential Procedure for Simultaneous Estimation of Multiple Percentiles” (Raatikainen) 中定义的简单算法。它很快，需要 2*m+3 个标记（对于 m 个百分位数）并且趋于快速准确近似。

Answer 6

@thkala 首先引用了一些文献。让我扩展一下。

实施

• 2019 年 Dunning 论文中的T-digest提供了 Java 的参考实现，并在该页面上将其移植到 Python、Go、Javascript、C++、Scala、C、Clojure、C#、Kotlin 和facebook 的 C++ 移植，以及进一步的Rust 移植那个 C++ 端口
• Spark实现了 2001 年 Greenwald/Khanna 论文中的“GK01”以获得近似分位数
• Beam：org.apache.beam.sdk.transforms.ApproximateQuantiles有近似分位数
• Java：Guava：com.google.common.math.Quantiles实现精确的分位数，因此占用更多内存
• Rust：分位数箱具有 2001 GK 算法“GK01”和 2005 CKMS 算法的实现。（注意：我发现 CKMS 实施缓慢 -问题）
• C++: boost quantiles有一些代码，但我不明白。
• 我对 Rust [链接] 中最多 100M 项的选项进行了一些分析，发现 GK01 最好，T-digest 第二，“在优先级队列中保留 1% 的最高值”第三。

文学

• 2001 年：节省空间的在线分位数摘要计算（作者：Greenwald、Khanna）。在 Rust 中实现：quantiles::greenwald_khanna。

• 2004 年：中位数及其他：传感器网络的新聚合技术（作者：Shrivastava、Buragohain、Agrawal、Suri）。引入“q-digests”，用于固定宇宙数据。

• 2005 年：有效计算数据流上的偏差分位数（由 Cormode、Korn、Muthukrishnan、Srivastava 编写）...用 Rust 实现：quantiles::ckms，其中指出 IEEE 的演示文稿是正确的，但自行发布的演示文稿存在缺陷。通过精心设计的数据，空间可以随着输入大小线性增长。“有偏差”意味着它关注 P90/P95/P99 而不是所有百分位数）。

• 2006 年：针对数据流上的偏置分位数的空间和时间高效的确定性算法（作者：Cormode、Korn、Muthukrishnan、Srivastava）...改进了 2005 年论文的空间限制

• 2007 年：高速数据流中近似分位数的快速算法（作者：Zhang、Wang）。声称比 GK 加速 60-300 倍。下面的 2020 年文献综述表明，这具有最先进的空间上限。

• 2019使用 t-digests 计算极其准确的分位数（作者：Dunning、Ertl）。引入 t-digests、O(log n) 空间、O(1) 更新、O(1) 最终计算。它的一个巧妙的功能是您可以构建部分摘要（例如每天一个）并将它们合并为几个月，然后将几个月合并为几年。这就是大型查询引擎所使用的。

• 2020年大规模数据近似分位数计算综述（技术报告）（陈、张）。

• 2021 The t-digest：有效的分布估计- 一篇关于 t-digest 的平易近人的总结论文。

对 <10M 值的 P99 进行廉价破解：只需将前 1% 存储在优先级队列中！

这听起来很愚蠢，但如果我想计算 10M float64 的 P99，我只需创建一个具有 100k float32 的优先级队列（需要 400kB）。这仅占用“GK01”的 4 倍空间，并且速度更快。对于 5M 或更少的物品，它比 GK01 占用的空间更少！

struct TopValues {
    values: std::collections::BinaryHeap<std::cmp::Reverse<ordered_float::NotNan<f32>>>,
}

impl TopValues {
fn new(count: usize) -> Self {
    let capacity = std::cmp::max(count / 100, 1);
    let values = std::collections::BinaryHeap::with_capacity(capacity);
    TopValues { values }
}

fn render(&mut self) -> String {
    let p99 = self.values.peek().unwrap().0;
    let max = self.values.drain().min().unwrap().0;
    format!("TopValues, p99={:.4}, max={:.4}", p99, max)
}
fn insert(&mut self, value: f64) {
    let value = value as f32;
    let value = std::cmp::Reverse(unsafe { ordered_float::NotNan::new_unchecked(value) });

    if self.values.len() < self.values.capacity() {
        self.values.push(value);
    } else if self.values.peek().unwrap().0 < value.0 {
        self.values.pop();
        self.values.push(value);
    } else {
    }
}
}