之前没听过也没相识过 HyperLogLog，通过翻译这篇文章正好简朴进修下。接待指正错误~

我们想要更好的向用户展示 Reddit 的局限。为了这一点，投票和评论数是一个帖子最重要的指标。然而，在 Reddit 上有相当多的用户只欣赏内容，既不投票也不评论。所以我们想要成立一个可以或许计较一个帖子欣赏数的系统。这一数字会被展示给帖子的创作者和版主，以便他们更好的相识某个帖子的活泼水平。

在这篇博客中，我们将接头我们是如何实现超大数据量的计数。

计数机制

对付计数系统我们主要有四种需求:

要全部满意以上四个需求的坚苦远远比听上去大的多。为了及时精准计数，图纸加密，我们需要知道某个用户是否曾经会见过这篇帖子。想要知道这个信息，我们就要为每篇帖子维护一个会见用户的荟萃，然后在每次计较欣赏量时查抄荟萃。一个 naive 的实现方法就是将会见用户的荟萃存储在内存的 hashMap 中，以帖子 Id 为 key。

这种实现方法对付会见量低的帖子是可行的，但一旦一个帖子变得风行，会见量剧增时就很难节制了。甚至有的帖子有高出 100 万的独立访客！ 对付这样的帖子，存储独立访客的 ID 而且频繁查询某个用户是否之前曾会见过会给内存和 CPU 造成很大的承担。

因为我们不能提供精确的计数，我们查察了几种差异的基数预计较法。有两个切合我们需求的选择：

下面看下 HLL 会节减几多内存。假如我们需要存储 100 万个独立访客的 ID, 每个用户 ID 8 字节长，那么为了存储一篇帖子的独立访客我们就需要 8 M的内存。反之，假如回收 HLL 会显著淘汰内存占用。差异的 HLL 实现方法耗损的内存差异。假如回收这篇文章的实现要领，那么存储 100 万个 ID 仅需 12 KB，是本来的 0.15%！！

Big Data Counting: How to count a billion distinct objects using only 1.5KB of Memory – High Scalability -这篇文章很好的总结了上面的算法。

很多 HLL 的实现都是团结了上面两种算法。在荟萃小的时候回收线性计数，当荟萃巨细达到必然的阈值后切换到 HLL。前者凡是被成为 ”稀疏“(sparse) HLL，后者被称为”浓密“(dense) HLL。这种团结了两种算法的实现有很大的长处，因为它对付小荟萃和大荟萃都可以或许担保准确度，同时担保了适度的内存增长。可以在 google 的这篇论文中相识这种实现的具体内容。

此刻我们已经确定要回收 HLL 算法了，不外在选择详细的实现时，我们思量了以下三种差异的实现。因为我们的数据工程团队利用 Java 和 Scala，所以我们只思量 Java 和 Scala 的实现。

Reddit 的数据管道依赖于 Kafka。当一个用户会见了一篇博客，会触发一个事件，事件会被发送到事件收集处事器，并被耐久化在 Kafka 中。

之后，计数系统会依次顺序运行两个组件。在我们的计数系统架构中，第一部门是一个 Kafka 的消费者，我们称之为 Nazar。Nazar 会从 Kafka 中读取每个事件，并将它通过一系列设置的法则来判定该事件是否需要被计数。我们取这个名字仅仅是因为 Nazar 是一个眼睛形状的护身符，而 ”Nazar“ 系统就像眼睛一样使我们的计数系统远离不怀盛情者的粉碎。个中一个我们不将一个事件计较在内的原因就是同一个用户在很短时间内反复会见。Nazar 会修改事件，加上个标明是否应该被计数的布尔标识，并将事件从头放入 Kafka。