近似聚合编辑

如果所有的数据都在一台机器上,那么生活会容易许多。 CS201 课上教的经典算法就足够应付这些问题。如果所有的数据都在一台机器上,那么也就不需要像 Elasticsearch 这样的分布式软件了。不过一旦我们开始分布式存储数据,就需要小心地选择算法。

有些算法可以分布执行,到目前为止讨论过的所有聚合都是单次请求获得精确结果的。这些类型的算法通常被认为是 高度并行的 ,因为它们无须任何额外代价,就能在多台机器上并行执行。比如当计算 max 度量时,以下的算法就非常简单:

  1. 把请求广播到所有分片。
  2. 查看每个文档的 price 字段。如果 price > current_max ,将 current_max 替换成 price
  3. 返回所有分片的最大 price 并传给协调节点。
  4. 找到从所有分片返回的最大 price 。这是最终的最大值。

这个算法可以随着机器数的线性增长而横向扩展,无须任何协调操作(机器之间不需要讨论中间结果),而且内存消耗很小(一个整型就能代表最大值)。

不幸的是,不是所有的算法都像获取最大值这样简单。更加复杂的操作则需要在算法的性能和内存使用上做出权衡。对于这个问题,我们有个三角因子模型:大数据、精确性和实时性。

我们需要选择其中两项:

精确 + 实时
数据可以存入单台机器的内存之中,我们可以随心所欲,使用任何想用的算法。结果会 100% 精确,响应会相对快速。
大数据 + 精确
传统的 Hadoop。可以处理 PB 级的数据并且为我们提供精确的答案,但它可能需要几周的时间才能为我们提供这个答案。
大数据 + 实时
近似算法为我们提供准确但不精确的结果。

Elasticsearch 目前支持两种近似算法( cardinalitypercentiles )。 它们会提供准确但不是 100% 精确的结果。 以牺牲一点小小的估算错误为代价,这些算法可以为我们换来高速的执行效率和极小的内存消耗。

对于 大多数 应用领域,能够 实时 返回高度准确的结果要比 100% 精确结果重要得多。乍一看这可能是天方夜谭。有人会叫 “我们需要精确的答案!” 。但仔细考虑 0.5% 误差所带来的影响:

  • 99% 的网站延时都在 132ms 以下。
  • 0.5% 的误差对以上延时的影响在正负 0.66ms 。
  • 近似计算的结果会在毫秒内返回,而“完全正确”的结果就可能需要几秒,甚至无法返回。

只要简单的查看网站的延时情况,难道我们会在意近似结果是 132.66ms 而不是 132ms 吗?当然,不是所有的领域都能容忍这种近似结果,但对于绝大多数来说是没有问题的。接受近似结果更多的是一种 文化观念上 的壁垒而不是商业或技术上的需要。