实时数据捕获的百分位数

Question

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

例如，考虑服务器应用程序的开发。

服务器的响应时间可能如下：17 MS 33 MS 52 MS 60 MS 55毫秒等。

报告第 90 个百分位数响应时间、第 80 个百分位数响应时间等非常有用。

朴素的算法是将每个响应时间插入到一个列表中。当需要统计数据时，对列表进行排序并在适当的位置获取值。

内存使用量与请求数量成线性比例。

是否有一种算法可以在有限的内存使用情况下生成“近似”百分位统计数据？例如，假设我想以处理数百万个请求的方式解决这个问题，但只想使用 1 KB 内存进行百分位数跟踪（放弃对旧请求的跟踪不是一个选项，因为百分位数应该适用于所有请求）。

还要求没有分布的先验知识。例如，我不想提前指定任何存储桶范围。

Answer 1

我相信有这个问题很多很好的近似算法。一个良好的第一切割方法是简单地用一个固定大小的数组（比方说1K价值的数据）。修正了一些概率p。对于每个请求，以概率p，写入其响应时间到阵列（替换最早的时间在那里）。由于阵列是直播流的二次抽样和二次抽样以来保持了分配，这样做阵列上的统计数据会给你全面，实时流的统计数据的近似。

此方法有几个优点：它不要求的先验信息，并且很容易代码。您可以快速构建并实验确定，为您的特定服务器，在什么时候生长缓冲只会对答案的影响可以忽略。这就是近似是足够精确的点。

如果您发现您需要太多的内存给你足够精确的统计数据，那么你就必须进一步深入研究。好的关键字是：“流计算”，“流统计”，当然还有“百分”。您也可以尝试“愤怒和诅咒”的做法。

Answer 2

如果您想在获得越来越多的数据时保持内存使用量恒定，那么您将不得不 重新采样 该数据以某种方式。这意味着您必须应用某种 重新装箱 方案。您可以等到获得一定数量的原始输入后再开始重新分类，但您无法完全避免它。

所以你的问题实际上是在问“动态分箱数据的最佳方法是什么”？有很多方法，但如果您想最小化对可能收到的值的范围或分布的假设，那么一种简单的方法是对固定大小的桶进行平均 k, ，具有对数分布的宽度。例如，假设您想在内存中随时保存 1000 个值。选择尺寸 k, ，说 100。选择最小分辨率，例如 1 毫秒。然后

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

这类 对数标度 方法类似于中使用的分块系统 哈希表算法, ，由某些文件系统和内存分配算法使用。当您的数据具有较大的动态范围时，它效果很好。

当新值出现时，您可以根据您的要求选择重新采样的方式。例如，您可以跟踪 移动平均线, ， 用一个 先进先出, ，或其他一些更复杂的方法。请参阅 卡德姆利亚 一种方法的算法（由 比特流).

最终，重新分类肯定会丢失一些信息。您对分级的选择将决定丢失哪些信息的具体情况。另一种说法是，恒定大小的内存存储意味着在两者之间进行权衡 动态范围 和 采样保真度;如何进行权衡取决于您，但就像任何抽样问题一样，这个基本事实是无法回避的。

如果您真的对利弊感兴趣，那么这个论坛上的任何答案都不可能是足够的。你应该调查一下 抽样理论. 。关于这个主题有大量的研究。

就其价值而言，我怀疑您的服务器时间将具有相对较小的动态范围，因此更宽松的缩放以允许对常见值进行更高的采样可能会提供更准确的结果。

编辑: ：为了回答您的评论，这里有一个简单的分箱算法的示例。

• 您可以在 10 个容器中存储 1000 个值。因此，每个 bin 包含 100 个值。假设每个 bin 都实现为动态数组（Perl 或 Python 术语中的“列表”）。

• 当新值进来时：

  • 根据您选择的垃圾箱限制确定应将其存储在哪个垃圾箱中。
  • 如果 bin 未满，则将该值追加到 bin 列表中。
  • 如果 bin 已满，则删除 bin 列表顶部的值，并将新值附加到 bin 列表的底部。这意味着旧的价值观会随着时间的推移而被抛弃。

• 要查找第 90 个百分位数，请对 bin 10 进行排序。第 90 个百分位是排序列表中的第一个值（元素 900/1000）。

如果您不喜欢丢弃旧值，那么您可以实现一些替代方案来代替。例如，当一个 bin 变满时（在我的示例中达到 100 个值），您可以取最旧的 50 个元素的平均值（即列表中的前 50 个），丢弃这些元素，然后将新的平均元素附加到容器中，留下一个包含 51 个元素的容器，现在有空间容纳 49 个新值。这是重新装箱的一个简单示例。

重新装箱的另一个例子是 下采样;例如，丢弃排序列表中的每第 5 个值。

我希望这个具体的例子能有所帮助。需要注意的关键点是，有很多方法可以实现恒定的内存老化算法；只有您才能根据您的要求决定什么是令人满意的。

Answer 3

我刚刚出版了一本博客帖子上这个话题。的基本思想是，以减少赞成“的应答95％百分比取为500ms-600毫秒或更小”（宽度为500ms-600毫秒的所有精确百分）

的精确计算的要求

您可以使用任意数量的任意大小的桶（例如0毫秒，50毫秒，50毫秒，100毫秒，...只是任何适合您的用例）。通常情况下，它不应该是一个问题，但超过在最后一个桶（即> 5000毫秒）一个一定的响应时间（例如5秒的网络应用程序）的所有请求。

对于每个新捕获的响应时间，只需增加它落入水桶的计数器。为了估计第n个百分位，所有的需要，直到总和超过总的n个百分比总结计数器。

这个方法只需要每铲斗8字节，从而允许跟踪128个水桶的存储器1K。绰绰有余使用了50ms的粒度）分析的网络应用程序的响应时间。

作为一个例子，在这里是一个谷歌我是从1小时创建图表捕获的数据（使用60个计数器，具有200ms的每一个桶）：

尼斯，是吗？ :) 了解更多关于我的博客。

Answer 4

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

在过去的几年里，人们对数据流的近似百分位进行了大量的研究。一些带有完整算法定义的有趣论文：

• 高速数据流中近似分位数的快速算法

• 针对数据流上的偏置分位数的空间和时间高效的确定性算法

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

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

Answer 5

尝试在纸“顺序程序的几个百分的同时估计”（Raatikainen）中定义的简单算法。它快速，需要2 * M + 3个标记（对于m百分），并迅速趋向于一个准确的近似。

Answer 6

使用大整数的动态数组 T[] 或 T[n] 计算响应时间为 n 毫秒的次数的数组。如果您确实正在对服务器应用程序进行统计，那么 250 毫秒的响应时间可能是您的绝对限制。因此，您的 1 KB 在 0 到 250 之间每毫秒保存一个 32 位整数，并且您有一些空间用于溢出箱。如果您想要具有更多 bin 的东西，请为 1000 个 bin 使用 8 位数字，并且在计数器溢出时（即计数器溢出）。在该响应时间的第 256 个请求）您将所有 bin 中的位向下移动 1。（有效地将所有箱中的值减半）。这意味着您会忽略所有捕获少于最常访问的 bin 捕获的延迟 1/127 的 bin。

如果您真的非常需要一组特定的垃圾箱，我建议您使用第一天的请求来提出一组合理的固定垃圾箱。在实时、性能敏感的应用程序中，任何动态都会非常危险。如果您选择这条路，您最好知道自己在做什么，否则有一天您会被叫下床，解释为什么您的统计跟踪器突然消耗了生产服务器上 90% 的 CPU 和 75% 的内存。

至于额外的统计数据：对于均值和方差，有一些 不错的递归算法 占用很少的内存。这两个统计数据本身对于许多分布来说就足够有用了，因为 中心极限定理 指出由足够多的自变量产生的分布接近正态分布（完全由均值和方差定义），您可以使用以下之一 正态性检验 在最后一个 N（其中 N 足够大但受内存要求限制）上以监视正态性假设是否仍然成立。