performance - 如何在不存储大量数据的情况下生成性能指标？（分位数流）

Question

这是一个常见的问题，但很难找到答案。我想测量 [ web server 95th percentile response time | 的性能 API 调用 | 算法性能 | 磁盘 I/O | 任何 ]。但是，你知道，这是很多数据，我不想存储它，因为这是在生产中使用的。此外，我不想花费大量 CPU 时间来计算我的软件有多慢。

如果您搜索答案，您会看到许多对古老算法的引用，这些算法将大量数据存储在 bin 中或保留大量随机样本数据。常见的结果包括 P-square 和 binmedian ，请注意很难找到任何体面的实现，因为尽管通常认为它们也是垃圾，但没有人使用它们。

您还会发现无法实现的听起来很聪明的答案，因为缺少一半的解释。如果你是统计学专业的，也许你会明白这一点。

那么我可以使用什么来获得廉价的性能统计信息呢？求算法和源代码。

标签： performancequantile

Answer 1

寻找算法意味着进入学术界，所以知道问题的正确名称是有帮助的。我们正在寻找一种流式算法，可能是分位数流式，尽管您可能还需要其他统计数据。搜索该短语，您将获得更明智的答案。

一个简单的答案是这篇论文，这是亚马逊和学术界之间的合作，描述了截至 2007 年的最新技术。它提供了 Greenwald-Khanna (GK) 和 Q-Digest 算法的高级视图。您实际上可以在库中找到这些算法。这个库有一个易于使用的 C++ 和 JS 实现。英特尔数学核心函数库实现了 Zhang 2007。

虽然 sengelha 库看起来易于使用且足以满足大多数需求，但自 2007 年以来世界一直在发展。今年的一篇论文（亚马逊、雅虎和学术界）描述了在数据草图中实现的“惰性 kll”算法库（C++、Java、Python）在这里。

这些信息应该足以让您从您的软件甚至分布式软件生成分位数数据，我希望其他人发布更好的答案。