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

Question

我正在一个包含超过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 ...]，但是我找不到一种汇总它们的方法。由于不同的前端实例可能处理不同类型的请求，并且请求到前端实例的分布是未知的，因此仅计算ALL 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％，但可以获得高精度的结果。您如何看待这种方式？

Answer 1

系统设计:

如果通话费用昂贵，那么也许您可以流式传输数据？在您的描述中，我看不到这种中间层的真正好处-为什么前端->中间层的通话费用比前端->后端低？

如果您担心丢失数据，则有两种选择:

将事件发送到多个节点。但是您将需要在处理它们时以某种方式避免重复。

将所有内容写入持久日志(Kafka可以在此处完成工作)

这完全取决于事件的数量(1/min/前端或10k/s/前端)以及前端与后端之间的距离(相同的数据中心或移动设备->数据中心？)。

如果是同一数据中心，则可以通过持久日志与后端进行通信-这解决了数据丢失问题。
如果有很多事件，您可以将其汇总到前端并向下游推送汇总

汇总:

有多种算法，例如q-消化，t-消化。参见 Quantiles over Data Streams: An Experimental Study

还值得注意的是HdrHistograms can be combined