介绍大数据 OLAP 中的近似聚合算法，包括 HyperLogLog、Count-Min Sketch 和 T-Digest。通过牺牲少量精度换取性能提升，适用于海量数据的去重计数、频率估算和分位数计算。文章涵盖算法原理、Java 实现细节、在 Druid 和 Spark 中的应用，以及参数调优指南，帮助开发者在准确性和效率间取得平衡。
随着数据量的爆炸式增长，传统精确计算方式面临着严峻挑战。一个简单的 COUNT(DISTINCT) 查询在 PB 级数据上可能需要小时级甚至天级的时间完成，消耗大量计算资源和存储空间。在许多实际应用场景中，用户往往不需要 100% 精确的结果，而是可以接受有一定误差的高效近似值。
近似聚合算法的核心价值在于：用可控制的精度损失，换取数量级的性能提升。就像在日常生活中，我们不需要知道一杯水中确切的水分子数量，只需要知道大概的毫升数就能满足大多数使用场景。
本文适合以下读者：
想象一下，你要估算一个大型商场一天的客流量。精确计算需要每个入口安装高精度计数器并实时同步数据，而近似估算可以通过统计几个主要入口的人流并乘以一个系数来实现。后者虽然不够精确，但成本低、速度快，足以满足大多数决策需求。
在近似算法中，我们常用以下指标衡量算法效果：
| 类型 | 算法 |
|---|---|
| 基数估算 | HyperLogLog, Linear Counting |
| 频率估算 | Count-Min Sketch, Count-Sketch |
| 分位数计算 | GK 算法, T-Digest |
| 数据采样 | 随机采样，分层采样 |
HyperLogLog(HLL) 是基数估算中最著名的算法之一，用于估算大规模数据集中不重复元素的个数。它的核心思想是：通过观测数据哈希值的分布模式来推断基数。
让我们通过一个有趣的比喻来理解 HLL：假设你在一片森林中想要估算鸟类的种类数量，而不是一只只数。你可以记录下每只鸟的叫声模式，通过分析叫声的多样性来估计种类数量。叫声就相当于哈希值，多样性模式就反映了基数值。
HLL 基于以下概率论观察：对于均匀分布的随机变量，连续出现 k 次正面的概率与样本大小存在数学关系。
设我们有一个哈希函数 h 将元素映射到 [0,1) 区间，则： P(max(h(x1), h(x2), ..., h(xn)) ≤ t) = t^n
对于随机哈希值，观察前导零的个数ρ（第一个 1 出现的位置），则： E[2^-ρ] ≈ 1/n
HLL 的标准实现步骤如下：
public class HyperLogLog {
private final int[] registers;
private final int registerCount;
private final int log2RegisterCount;
public HyperLogLog(int precision) {
this.log2RegisterCount = precision;
this.registerCount = 1 << precision;
this.registers = new int[registerCount];
}
public void add(Object element) {
long hash = MurmurHash.hash64(element);
int index = (int) (hash & (registerCount - 1));
int value = Long.numberOfLeadingZeros(hash >>> log2RegisterCount) + 1;
if (value > registers[index]) {
registers[index] = value;
}
}
public long count() {
double sum = 0.0;
for (int value : registers) {
sum += 1.0 / (1 << value);
}
double estimate = ALPHA * registerCount * registerCount / sum;
// 小范围修正
if (estimate <= 2.5 * registerCount) {
int zeroCount = 0;
for (int value : registers) {
if (value == 0) zeroCount++;
}
if (zeroCount > 0) {
estimate = registerCount * Math.log(registerCount / (double) zeroCount);
}
}
return (long) estimate;
}
// 合并多个 HLL 实例
public void merge(HyperLogLog other) {
for (int i = 0; i < registerCount; i++) {
if (other.registers[i] > this.registers[i]) {
this.registers[i] = other.registers[i];
}
}
}
}
HLL 的标准误差为： σ = 1.04 / √m
这意味着：
Count-Min Sketch(CM Sketch) 用于估算数据流中元素的频率。想象你在一个人流密集的广场，想要估算不同年龄段人群的数量。你可以安排多个观察员，每人使用不同的分类标准进行统计，最后取各个年龄段的最小估算值作为最终结果。
CM Sketch 使用 d 个哈希函数和 w 个计数器阵列。对于每个元素，使用每个哈希函数计算位置并增加相应计数。查询时取所有哈希位置的最小值作为频率估算。
误差边界为： f^(x) - εN ≤ f(x) ≤ f^(x) 其中ε = e/w，置信度 1-δ，δ = e^-d
public class CountMinSketch {
private final long[][] table;
private final int depth;
private final int width;
private final long[] hashA;
private long count;
public CountMinSketch(int depth, int width) {
this.depth = depth;
this.width = width;
this.table = new long[depth][width];
this.hashA = new long[depth];
this.count = 0;
Random random = new Random();
for (int i = 0; i < depth; i++) {
hashA[i] = random.nextLong();
}
}
private int[] getIndices(Object element) {
int[] indices = new int[depth];
long hash = MurmurHash.hash64(element);
for (int i = 0; i < depth; i++) {
long mixed = hash ^ hashA[i];
indices[i] = (int) (Math.abs(mixed) % width);
}
return indices;
}
public void add(Object element, long increment) {
int[] indices = getIndices(element);
for (int i = 0; i < depth; i++) {
table[i][indices[i]] += increment;
}
count += increment;
}
public long estimateFrequency(Object element) {
int[] indices = getIndices(element);
long min = Long.MAX_VALUE;
for (int i = 0; i < depth; i++) {
min = Math.min(min, table[i][indices[i]]);
}
return min;
}
// 计算点积，用于内积估算
public long dotProduct(CountMinSketch other) {
// 简化实现，实际需要更复杂的合并逻辑
long result = 0;
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
result += this.table[i][j] * other.table[i][j];
}
}
return result;
}
}
T-Digest 用于估算数据流的分位数（如中位数、95 百分位数等）。它将数据压缩为一系列中心点，每个中心点代表一个数据区间，并记录该区间的数据量和均值。
T-Digest 使用缩放函数控制聚类大小： k(q) = δ / (2π) * sin^-1(2q - 1) 其中 q 是分位数，δ是压缩参数。
public class TDigest {
private final List<Centroid> centroids;
private final double compression;
private long count;
private static class Centroid {
double mean;
long count;
Centroid(double mean, long count) {
this.mean = mean;
this.count = count;
}
}
public TDigest(double compression) {
this.compression = compression;
this.centroids = new ArrayList<>();
this.count = 0;
}
public void add(double value) {
add(value, 1);
}
public void add(double value, long weight) {
// 寻找插入位置
int index = findInsertionIndex(value);
if (index < centroids.size() && canMerge(index, value, weight)) {
// 合并到现有中心点
mergeCentroid(index, value, weight);
} else {
// 创建新中心点
centroids.add(index, new Centroid(value, weight));
}
count += weight;
// 定期压缩
if (count % 1000 == 0) {
compress();
}
}
private boolean canMerge(int index, double value, long weight) {
// 根据缩放函数判断是否可以合并
Centroid centroid = centroids.get(index);
double newMean = (centroid.mean * centroid.count + value * weight) / (centroid.count + weight);
double q1 = (double) getCumulativeCount(index) / count;
double q2 = (double) (getCumulativeCount(index) + centroid.count + weight) / count;
return (scaleFunction(q2) - scaleFunction(q1)) * count <= compression;
}
private double scaleFunction(double q) {
return (compression / (2 * Math.PI)) * Math.asin(2 * q - 1);
}
public double quantile(double q) {
// 计算分位数
long target = (long) (q * count);
long cumulative = 0;
for (int i = 0; i < centroids.size(); i++) {
Centroid c = centroids.get(i);
long nextCumulative = cumulative + c.count;
if (nextCumulative >= target) {
// 线性插值
if (i == 0 || i == centroids.size() - 1) {
return c.mean;
}
double left = centroids.get(i - 1).mean;
double right = centroids.get(i + 1).mean;
double t = (double) (target - cumulative) / c.count;
return left + (right - left) * t;
}
cumulative = nextCumulative;
}
return centroids.get(centroids.size() - 1).mean;
}
}
Apache Druid 是一个高性能的实时 OLAP 数据库，广泛使用近似算法：
-- 精确计数
SELECT COUNT(DISTINCT user_id) FROM user_events
-- 近似计数（使用 HLL）
SELECT APPROX_COUNT_DISTINCT(user_id) FROM user_events
-- 分位数计算
SELECT APPROX_QUANTILE(response_time, 0.99) FROM metrics
Spark 提供了多种近似聚合函数：
import org.apache.spark.sql.functions._
import org.apache.spark.sql.expressions._
// 精确去重计数
df.agg(countDistinct("user_id"))
// 近似去重计数（默认 5% 误差）
df.agg(approx_count_distinct("user_id"))
// 可控制误差的近似计数
df.agg(approx_count_distinct("user_id", 0.01))
// 分位数计算
df.stat.approxQuantile("response_time", Array(0.5, 0.95), 0.01)
需求：实时统计每日独立访客(UV)、最热门页面、响应时间百分位数
解决方案：
// 使用 HLL 统计 UV
HyperLogLog dailyUV = new HyperLogLog(14); // 0.8% 误差
// 使用 CM Sketch 统计页面热度
CountMinSketch pagePopularity = new CountMinSketch(5, 8192);
// 使用 T-Digest 统计响应时间
TDigest responseTimeDigest = new TDigest(100);
// 实时处理每条访问记录
public void processVisit(Visit visit) {
dailyUV.add(visit.userId);
pagePopularity.add(visit.pageUrl, 1);
responseTimeDigest.add(visit.responseTime);
}
需求：实时监控商品销量排名、用户购买行为分析、交易金额分布
解决方案架构：
| 需求 | 推荐算法 | 误差特征 | 内存占用 | 适用场景 |
|---|---|---|---|---|
| 去重计数 | HyperLogLog | 1-5% | 极低 | UV 统计、distinct 计算 |
| 频率统计 | Count-Min Sketch | 可控 | 低 | 热门排行、频率分析 |
| 分位数计算 | T-Digest | 高精度 | 中 | 性能监控、指标分布 |
| Join 大小估算 | FM Sketch | 中等 | 低 | 查询优化 |
HyperLogLog 参数选择：
Count-Min Sketch 参数配置：
// 期望误差 1%，置信度 99%
int width = (int) Math.ceil(2 / 0.01); // ε=0.01 → w=200
int depth = (int) Math.ceil(Math.log(1 / 0.01)); // δ=0.01 → d=5
未来的近似算法将更加智能化，能够根据数据特征自动选择最优算法和参数。例如，对于高度偏斜的数据分布，系统可以自动识别并采用更适合的加权采样策略。
随着专用 AI 芯片和 FPGA 的普及，近似算法将越来越多地利用硬件加速。例如，哈希计算和位操作可以在硬件层面极大优化，进一步提升处理速度。
未来的系统将能够根据业务需求动态调整精度要求。在业务高峰期间自动降低精度保证性能，在闲时提高精度提供更准确的结果。
近似算法使得实时大数据分析成为可能，支持企业做出更快速的业务决策。例如，实时个性化推荐、动态定价、欺诈检测等场景。
在 IoT 和边缘计算场景中，资源受限的设备可以利用近似算法在本地进行数据分析，只将汇总结果传输到云端，大幅减少带宽需求。
近似算法将与机器学习更深度结合，用于训练数据采样、模型压缩、分布式训练等场景，提高 AI 系统的效率和可扩展性。
近似聚合算法是大数据时代的必然选择，它巧妙地在精度和效率之间找到了平衡点。通过本文的介绍，我们看到了：
这些算法不仅在理论上有优美的数学基础，在实际工程中也经过了大规模验证，成为现代大数据平台不可或缺的组成部分。
近似聚合算法正如它的哲学：完美是优秀的敌人。在大数据的世界里，有时候'足够好'比'完美'更有价值。掌握这些算法，让你在数据的海洋中游刃有余，以最小的代价获取最大的洞察力。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online