问如何计算分布式系统中大量数据的分布(直方图)？

EN

我正在构建一个包含100,000多个前端实例的实例群上的度量报告系统。对于任何请求，每个实例都有一个响应时间。我需要的是所有请求的响应时间在整个舰队中的分布。例如百分位数50，百分位数90，百分位数99，Percentile99.9……requestType1，requestType2...requestType1000.

每个实例都会收集内部的响应时间。因此，在一分钟内，一个实例在内存中收集的是各种requestTypes的响应时间列表。例如requestType1 - 1，2，3，4，1，2，2，requestType2 - 2，2，3，2，1…所以我需要做的是处理这些数据并产生最终结果。

我尝试了很多设计，我的主要痛处是我收集到的每一个requestType的数据点的巨大大小，以及实例间通信的开销。我将在下面解释我目前的设计，但我也想知道是否有更好的设计或一些奇特的算法可以聚合直方图？。

目前最有希望的是:每个前端实例都会将它们的数据发送到中间层实例的随机实例中。在这个中间层舰队中，每一个实例都会在短时间内聚集所有的数据点，例如5秒。(它没有足够的记忆来保存更长的时间)。然后，中间层实例将通过requestTypes的哈希值将聚合的数据分发到后端实例。这意味着所有中间层实例都会将相同requestTypes的数据点发送到同一个后端实例。然后，在后端实例中，我可以使用第三方的直方图容器(CodaHale的直方图或HdrHistogram)来计算P50、P90、P99的传入datapoints...The原因--中间层实例舰队从前端实例发送数据是昂贵的，所以我希望将所有数据立即发送出去，而不是打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%的整体数据，但得到了一个高精度的结果。你觉得这条路怎么样？