algorithm - 实时数据捕获的百分比

Question

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

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

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

报告 90% 响应时间、80% 响应时间等很有用。

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

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

鉴于内存使用量有限，是否有一种算法可以产生“近似”的百分位数统计数据？例如，假设我想以处理数百万个请求的方式解决这个问题，但只想使用一千字节的内存进行百分位数跟踪(丢弃旧请求的跟踪不是一种选择，因为百分位数应该适用于所有请求)。

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

Answer 1

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

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

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