近似聚合

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

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

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

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

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

我们需要选择其中两项：

精确 + 实时:: 数据可以存入单台机器的内存之中，我们可以随心所欲，使用任何想用的算法。结果会 100% 精确，响应会相对快速。

大数据 + 精确:: 传统的 Hadoop。可以处理 PB 级的数据并且为我们提供精确的答案，但它可能需要几周的时间才能为我们提供这个答案。

大数据 + 实时:: 近似算法为我们提供准确但不精确的结果。

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

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

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

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