实时数据捕获的百分比
我正在寻找一种algorithm来确定实时数据捕获的百分比。
例如，考虑服务器应用程序的开发。
服务器的响应时间如下所示：17 ms 33 ms 52 ms 60 ms 55 ms等
报告第90百分位响应时间，第80百分位响应时间等是有用的。
天真的algorithm是将每个响应时间插入一个列表。 当请求统计信息时，对列表进行sorting，并将值在适当的位置。
内存使用量与请求数成线性关系。
是否有一个algorithm，给出有限的内存使用“近似”百分数统计？ 例如，假设我想以一种处理数百万个请求的方式来解决这个问题，但是只想使用一千字节的内存来进行百分比跟踪（丢弃对旧请求的跟踪不是一种select，因为百分点应该是适用于所有请求）。
还要求没有关于分配的先验知识。 例如，我不想提前指定任何桶的范围。
我相信这个问题有很多很好的近似algorithm。 一个好的方法就是简单地使用一个固定大小的数组（比如说1K的数据）。 修正一些概率p。 对于每个请求，以概率p，将它的响应时间写入数组（replace那里最老的时间）。 由于数组是对实时stream的二次采样，并且由于二次采样保留了分布，所以对该数组进行统计将给出完整的实时stream的统计量的近似值。
这种方法有几个优点：它不需要先验信息，而且很容易编码。 您可以快速构build它，并通过实验确定，对于您的特定服务器，在什么时候增长缓冲区对答案只有微不足道的影响。 这是近似值足够精确的地方。
如果你发现你需要太多的内存来给你足够精确的统计数据，那么你将不得不进一步挖掘。 好的关键词是：“stream计算”，“stream统计”，当然还有“百分位”。 你也可以尝试“ire and curses”的方法。
如果你想保持内存使用不变，因为你获得越来越多的数据，那么你将不得不以某种方式重新采样数据。 这意味着你必须采用某种重组scheme。 你可以等到你获得一定数量的原始投入，然后再开始重组，但是你无法完全避免。
所以你的问题是真的问“什么是dynamic装箱我的数据的最佳方式”？ 有很多方法，但是如果你想最大限度地减less你对可能接收的值的范围或分布的假设，那么一个简单的方法是平均大小为k的固定大小的桶，并以对数分布的宽度。 例如，假设你想在任何时候在内存中保存1000个值。 为kselect一个大小，比如100.select你的最小分辨率，比如1ms。 然后
- 第一个桶处理0-1ms（宽度= 1ms）
- 第二桶：1-3ms（w = 2ms）
- 第三桶：3-7ms（w = 4ms）
- 第四桶：7-15ms（w = 8ms）
- …
- 第十桶：511-1023ms（w = 512ms）
这种types的日志缩放方法类似于散列表algorithm中使用的分块系统，由一些文件系统和内存分配algorithm使用。 当您的数据具有较大的dynamic范围时，效果很好。
随着新的价值观的到来，您可以根据自己的要求select要重新采样的方式。 例如，您可以跟踪移动平均线 ，使用先进先出或其他更复杂的方法。 一种方法见Kademliaalgorithm（由Bittorrent使用 ）。
最终，重组必须让你失去一些信息。 您关于分箱的select将决定哪些信息丢失的具体情况。 另一种说法是，恒定大小的存储器意味着dynamic范围和采样保真度之间的折衷; 你如何做出这种交换取决于你，但是就像任何抽样问题一样，没有办法解决这个基本事实。
如果你真的对利弊感兴趣，那么在这个论坛上没有任何答案是可以的。 你应该看看抽样理论 。 关于这个话题有大量的研究。
对于什么是值得的，我怀疑你的服务器时间将有一个相对较小的dynamic范围，所以更宽松的缩放以允许更高的通用值采样可以提供更准确的结果。
编辑 ：要回答您的评论，这里是一个简单的分箱algorithm的例子。
- 您存储1000个值，分10个分箱。 因此每个垃圾箱都有100个值。 假设每个bin都被实现为一个dynamic数组（一个“列表”，以Perl或Python术语来说）。
-
当有新的价值时：
- 根据您select的垃圾箱限制，确定应该将垃圾箱存储在哪个垃圾箱中。
- 如果垃圾箱未满，请将该值附加到垃圾箱列表中。
- 如果垃圾箱已满，请移除垃圾箱列表顶部的值，然后将新值附加到垃圾箱列表的底部。 这意味着旧的价值随着时间的推移而被抛弃。
-
为了find第90个百分位，分类箱10.第90个百分位是sorting列表（元素900/1000）中的第一个值。
如果你不喜欢扔旧的价值，那么你可以实现一些替代scheme来使用。 例如，当一个bin变满（在我的例子中达到100个值），可以取最老的50个元素的平均值（即列表中的前50个），丢弃这些元素，然后将新的平均元素附加到仓，留给你一个有51个元素的箱子，现在有空间来存放49个新值。 这是重新绑定的一个简单例子。
重组的另一个例子是下采样 ; 例如，在sorting列表中丢弃每个第五个值。
我希望这个具体的例子有帮助。 要拿走的关键是有很多方法来实现一个恒定的内存老化algorithm; 只有你可以根据你的要求来决定什么是满意的。
我刚刚发表了关于这个主题的博客文章 。 基本思想是减less精确计算的要求，以“95％的答案需要500毫秒-600毫秒或更less”（对于500毫秒-600毫秒的所有确切百分比）
您可以使用任意数量的任意大小的桶（例如0ms-50ms，50ms-100ms，…只是适合您的用例的任何东西）。 通常情况下，对于最后一个桶（即> 5000ms）中超过一定响应时间（例如，Web应用程序需要5秒）的所有请求，这都不成问题。
对于每个新捕获的响应时间，只需增加一个计数器即可。 为了估计第n个百分点，所需要的就是总计柜台，直到总数超过总数的百分之十。
这种方法只需要每个桶8个字节，允许跟踪1K内存的128个桶。 绰绰有余的分析使用粒度为50毫秒的Web应用程序的响应时间）。
作为一个例子，下面是我从一个小时的捕获数据创build的Google Chart （使用60个每桶200毫秒的计数器）：
很好，不是吗？ 🙂 阅读更多在我的博客 。
（问这个问题已经有一段时间了，但是我想指出一些相关的研究论文）
近几年来，对数据stream的近似百分比进行了大量的研究。 一些有趣的论文全面的algorithm定义：
-
高速数据stream近似分位数的快速algorithm
-
空间和时间有效的确定性algorithm，用于数据stream上偏置的分位数
-
有效计算数据stream上的偏置分位数
所有这些论文都提出了具有亚线性空间复杂度的algorithm来计算数据stream上的近似百分数。
尝试在“几个百分点的同时估计的顺序过程”（Raatikainen）论文中定义的简单algorithm。 速度很快，需要2 * m + 3个标记（对于百分位数），并且趋向于快速精确地近似。
使用大整数的dynamic数组T []或者其中T [n]计数响应时间为n毫秒的次数。 如果你真的在服务器应用程序上做统计，那么可能250毫秒的响应时间是你绝对的限制。 因此，您的1 KB在0到250之间的每个ms中保存一个32位整数，并且您有一定空间可用于溢出存储区。 如果你想要更多箱子的东西，用8位数字代替1000个箱子，当计数器溢出的时候（即响应时间的第256个请求），你把所有箱子中的位减1。所有箱）。 这意味着你无视所有能够捕捉到访问量最大的垃圾箱延迟时间的1/127的垃圾箱。
如果你真的需要一套特定的箱子，我build议使用请求的第一天来拿出一个合理的固定的一组箱子。 任何dynamic的东西都会对现场敏感的应用程序非常危险。 如果你select这个path，你最好知道自己在做什么，或者有一天你会从床上打电话来解释为什么你的统计跟踪器突然在生产服务器上吃掉了90％的CPU和75％的内存。
至于额外的统计：对于均值和方差有一些很好的recursionalgorithm ，占用很less的内存。 这两个统计量对于大量的分布是足够的，因为中心极限定理表明，由足够多的自variables引起的分布接近于正态分布（可以用均值和方差完全定义）对最后一个N（其中N足够大但受到你的记忆要求的限制）的正态性检验之一来监测正态性的假设仍然成立。
