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 算法相当标准,在实现中使用三种变体:
- Twitter 的Algebird库,用 Scala 实现。Algebird 有很好的使用文档,但是稀疏和密集 HLL 表示的实现细节并不容易理解。
- HyperLogLog++ 的实现位于stream-lib中,用Java 实现。Stream-lib 中的代码有很好的文档记录,但理解如何正确使用该库并根据需要调整它有点困难。
- Redis 的 HLL 实现(推荐选择的)。 HLL 的 Redis 实现文档齐全且易于配置,并且提供的与 HLL 相关的 API 易于集成。使用 Redis 的另一个好处是,通过将计数应用程序(HLL 计算)的 CPU 和内存密集型部分移出并将其移至专用服务器上,缓解了许多性能问题。
Reddit使用Redis的HLL文章