Liu*_*nao 6 algorithm distribution histogram aggregation codahale-metrics
我正在包含超过100,000个前端实例的实例组中构建度量报告系统.对于任何请求,每个实例都有一个响应时间.我需要的是在整个车队中分配各种请求的响应时间.例如[requestType1,requestType2 ... requestType1000]的[Percentile 50,Percentile 90,Percentile 99,Percentile99.9 ...].
每个实例都会收集内部发生的响应时间.所以一分钟之内,一个实例在内存中收集的是各种requestTypes的响应时间列表.例如requestType1 - [1,2,3,4,1,2],requestType2 - [2,2,3,2,1] ......所以我需要做的是处理这些数据并生成最后的结果.
我尝试了很多设计,我的主要痛点是我收集的每个requestType的数据点大小,以及实例之间的通信费用. 我将在下面解释我目前的设计,但我也想知道是否有更好的设计或某些花哨的算法可以聚合直方图？
目前最有希望的是:每个前端实例都会将其数据发送到中间层实例组的随机实例.在这个中间层车队中,每个实例都会聚合它在短时间内获得的所有数据点,例如5秒.(它没有足够的内存来保持更长的时间).然后,中间层实例将通过requestTypes的哈希值将聚合数据分发到后端实例.这意味着所有中间层实例都会将相同requestTypes的数据点发送到同一个后端实例.然后在后端实例中我可以使用第三方的直方图容器(CodaHale的直方图或HdrHistogram)来计算传入数据点的P50,P90,P99 ......我需要中间层实例队列的原因是从前面发送数据 - 最终实例是昂贵的,所以我希望它的所有数据一次发送,但不要100次调用发送到100个不同的后端实例.
我可能会想到这个设计的主要问题是相对较高的复杂性,如果一个后台实例关闭,我可能会丢失某些requestTypes的所有数据.那么对于系统设计部分,任何人都有一些更好的想法？
我想的另一种方法是找到一种奇特的算法来聚合现有的直方图.上面的设计,我得到的数据将是100%准确.但实际上我可以容忍一些错误.例如在CodaHale的直方图和HdrHistogram中,我确信它们实际上并没有保存所有数据点,而是应用了一些高级数学算法以非常低的成本获得相对高精度的结果.我可以在前端或中间层实例中使用直方图库.但问题是虽然我能以低成本获得每个前端实例或中间层实例的[P50,P90,P99 ......],但我找不到聚合它们的方法.因为不同的前端实例可能会处理不同类型的请求,并且对前端实例的请求分配是未知的,所以简单地计算所有P50,P90,P99的平均值会产生很多不准确.那么有没有人有想法,我怎样才能将多个CodaHale的直方图或HdrHistogram聚合在一起？或者是否有任何算法可以帮助将直方图聚合成一个？
================================================== ======================
昨晚我有了一些新想法.由于P50和P90正在测量所有数据的"平均值",我认为在每个中间层实例中计算的所有P50和P90的简单应用加权平均值应该足够好.但是P99,P99.9和P99.99正在测量那些外围数据,因此子集的P99的平均值可能不准确.
但是如果假设中间层实例中的数据是相对随机分布的,那么我可以在每个中间层实例中获得前5%的数据点,并将它们发送到后端.每个中间层数据点的5%合计为总数据点的5%.而且我更有信心,这5%数据的P80接近整体数据P99,这5%数据的P98接近整体数据的P99.9,而5%数据的P99.8接近P99 .99总体数据.
我希望通过这种方式,我只能传输5%的总体数据,但能获得高精度的结果.你觉得这样怎么样？
系统设计：
如果通话费用昂贵，那么您可以传输数据吗？我在您的描述中没有看到这个中间层的真正好处 - 为什么前端->中间层调用成本低于前端->后端？
如果您担心丢失数据，您有两种选择：
这完全取决于事件量（1/分钟/前端或 10k/s/前端）以及前端和后端之间的距离（相同数据中心或移动设备 -> 数据中心？）。
如果是同一个数据中心，您可以通过持久日志与后端通信 - 这解决了数据丢失问题。如果有很多事件，您可以在前端聚合它们并将聚合推送到下游
聚合：
有多种算法，例如q-digest、t-digest。查看数据流上的分位数：实验研究
还值得注意的是，HdrHistograms可以组合