Java中如何实现Sketch算法HyperLogLog？

Reddit论坛希望显示其庞大数量帖子的浏览计数问题。

2017 年，天真地将一组唯一 ID 存储为 long（每个 8 字节），但马上迅速增加内存和磁盘的使用量，在该实现中，一个 1000 万浏览量的帖子就有 80MB内存消耗。

如果需要

  • - 读取
  • - 修改
  • - 持久化

每次用户首次查看帖子时都需要读取-修改-持久化，每个都需要计数器，你可以想象有多消耗内存。
现在......将其应用到成千上万的此类帖子（旧帖子等）中： 1,000 个帖子，1,000 万次浏览，等于 800GB。

由于所有帖子的浏览量来来去去，系统需要并发访问的容量几乎达到 1 TB。

这突然变成了一个很难解决的问题。 值得庆幸的是，Reddit 意识到他们可以使用一套非常特殊的算法，这套算法非常适合此类大数据问题：

Sketch算法
是一套以准确性换取不成比例的巨大效率提升的算法。
优点是

  • - 小而一致的大小
  • - 亚线性空间增长
  • - 输入数据线性增长，而空间需求不线性增长。
  • - 经过数学验证的误差边界

Reddit 使用的Sketch算法名为 HyperLogLog。

HyperLogLog 是一种概率算法，用于近似计算多集的基数（不同元素的计数）。它常用于大数据场景，在这种场景中，由于内存限制，存储所有不同元素是不可行的。下面是一个使用 com.google.common.hash 库在 Java 中实现 HyperLogLog 的简单示例。

首先，您需要在项目中包含 Guava 库。如果使用 Maven，请添加以下依赖项：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.1-jre</version> <!-- or the latest version -->
</dependency>

代码：

import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;

import java.util.Arrays;

public class HyperLogLog {

    private final int log2m;
    private final int m;
    private final double alphaMM;
    private final long[] registers;

    public HyperLogLog(int log2m) {
        this.log2m = log2m;
        this.m = 1 << log2m;
        this.alphaMM = getAlphaMM(m);
        this.registers = new long[m];
    }

    public void add(Object value) {
        HashFunction hashFunction = Hashing.murmur3_128();
        long hash = hashFunction.hashObject(value, HyperLogLogFunnel.INSTANCE).asLong();
        int index = (int) (hash >>> (64 - log2m));
        int rho = Long.numberOfLeadingZeros((hash << log2m) | (1L << (log2m - 1)) + 1) + 1;
        registers[index] = Math.max(registers[index], rho);
    }

    public long cardinality() {
        double estimate = calculateEstimate();
        // Apply small range correction
        if (estimate <= 2.5 * m) {
            int zeroRegisters = (int) Arrays.stream(registers).filter(value -> value == 0).count();
            if (zeroRegisters != 0) {
                estimate = m * Math.log((double) m / zeroRegisters);
            }
        }
        return Math.round(estimate);
    }

    private double calculateEstimate() {
        double harmonicMean = Arrays.stream(registers).mapToDouble(value -> 1.0 / (1L << value)).sum();
        return alphaMM / harmonicMean;
    }

    private static double getAlphaMM(int m) {
        if (m == 16) return 0.673;
        if (m == 32) return 0.697;
        if (m == 64) return 0.709;
        return 0.7213 / (1 + 1.079 / m);
    }

    public static void main(String[] args) {
        HyperLogLog hyperLogLog = new HyperLogLog(12);

        // Add elements to the HyperLogLog
        hyperLogLog.add("Element1");
        hyperLogLog.add("Element2");
        hyperLogLog.add("Element3");

        // Estimate cardinality
        long cardinality = hyperLogLog.cardinality();
        System.out.println("Estimated Cardinality: " + cardinality);
    }
}

本示例包含一个用于序列化的简单 HyperLogLogFunnel。算法的精度由参数 log2m 控制。log2m 值越高，精度越高，但需要的内存也越多。请根据自己的需求尝试使用不同的值。

虽然 HLL 算法相当标准，在实现中使用三种变体：

  1. Twitter 的Algebird库，用 Scala 实现。Algebird 有很好的使用文档，但是稀疏和密集 HLL 表示的实现细节并不容易理解。
  2. HyperLogLog++ 的实现位于stream-lib中，用Java 实现。Stream-lib 中的代码有很好的文档记录，但理解如何正确使用该库并根据需要调整它有点困难。
  3. Redis 的 HLL 实现（推荐选择的）。 HLL 的 Redis 实现文档齐全且易于配置，并且提供的与 HLL 相关的 API 易于集成。使用 Redis 的另一个好处是，通过将计数应用程序（HLL 计算）的 CPU 和内存密集型部分移出并将其移至专用服务器上，缓解了许多性能问题。

Reddit使用Redis的HLL文章