HyperLogLog —— 利用统计和概率原理估算数据规模

HyperLogLog 算法简介#

在大数据处理中，经常遇到需要统计独立元素数量的问题。例如，我们想知道一个大型网站每天有多少独立用户访问。简单的方法是使用哈希表来跟踪每个用户。但对于巨大的用户量，这种方法需要大量的内存。你需要为每一个用户在表上预留一个位置，因此在大数据的场景下并不适用。加之，我们大多数情况下，只需要了解用户的大致规模，所以 HyperLogLog 作为一种精确度较高，内存使用极低的算法，适合这种情况。

1. 什么是 HyperLogLog？#

HyperLogLog (HLL) 是由 Philippe Flajolet 和其他人在 2007 年提出的一个算法，用于估算大型数据集中的独立元素数量。与直接计数相比，HLL 的美妙之处在于它只需要很小的固定大小的内存（通常为几 KB）。

2. HyperLogLog 原理#

HLL 的基础是观察随机数据的哈希值的特点。当我们哈希一个元素，一个均匀的哈希函数应该会给我们一个均匀分布的结果，其结果可以看作是随机的。

HLL 的核心思想是：统计二进制哈希值最前面的连续 0 的数量。例如，哈希值 "001010..." 的前导 0 数量为 2。因为哈希值是随机的，所以前导 0 的平均数量可以作为估计基数的一个指标。简单理解，就是统计前导 0 个数，如果这个值越大，概率上来说，我们需要 **“见到”** 的不同用户越多。

举个例子：如果我们连续不断地抛硬币，连续 5 次正面和连续 10 次正面相比，一定是 10 次正面概率上更加小，一般来讲，得到连续 10 次正面需要抛的硬币次数更多。

由于 HLL 是基于概率的统计方法，有以下几点决定了估算精度：

1. 哈希函数的均匀分布#

当使用均匀分布的哈希函数对数据进行哈希时，生成的二进制哈希值可以被视为随机数。哈希值的某一位为 0 或 1 的概率均为 50%。

2. 哈希函数的性能#

HLL 的性能在很大程度上依赖于哈希函数的性能。哈希函数需要将输入数据均匀分布到其输出空间，确保每个桶都获得近似相等数量的数据。而且需要确保其速度。

3. 前导零 (Leading Zeros)#

考虑一个随机的二进制数字，最高位为 0 的概率是 50%，连续两个最高位为 0 的概率是 25%，以此类推。因此，哈希值前有连续 k 个零的事件是非常稀少的，可以用来表示大量独特元素的存在。

4. 桶或计数器 (Buckets)#

为了解决单一数据的随机性导致的估计不稳定问题，HLL 使用了多个桶。哈希值的前几位决定了元素应该进入哪个桶，而其余部分用于计算前导零。

例如，如果使用 2^4 = 16 个桶，那么哈希值的前 4 位将决定桶的编号（0-15）。每个桶维护该桶内哈希值的前导零的最大数量。

5. 合并计数器值#

为了得到整体的基数估计，我们不能简单地将所有桶的数值相加。我们应该使用使用调和平均数： $\frac{m}{\sum_{j=1}^{m} 2^{-M[j]}}$ ，这里 m 是桶的数量，M [j] 是第 j 个桶记录的前导零的数量。
因为桶之间并不是相互独立的。一个桶可能观察到 5 个前导零，而另一个桶可能观察到 3 个前导零。简单地将这些数值相加（例如 $2^5 + 2^3$ ）会导致重复计数，因为这些桶可能观察到了部分相同的元素。重要的是，我们是在估算整体的基数，而不是累加每个桶的独立估计。

6. 修正小计数和大计数偏差#

尽管上述方法对于中等大小的基数工作得很好，但对于非常小或非常大的基数，它可能会出现偏差。为了修正这些偏差，HLL 提供了以下修正：

小数修正: 当估计值小于 5/2m 时，考虑到可能有很多空桶，可以通过线性计数的方式来修正估计值。
大数修正: 当估计值接近 2^32 (对于 32 位哈希) 时，算法会考虑溢出，并对估计值进行修正。

3. 数据结构#

HyperLogLog 使用一个桶数组来存储信息。每个桶记录了对应哈希值前导 0 的最大数量。算法的输出是基于所有桶的值的一个函数。

4. 精确度和内存#

HLL 的精确度与其桶的数量有关。更多的桶意味着更高的精确度，但同时也意味着更多的内存使用。幸运的是，即使是几 KB 的内存，HLL 也能提供非常合理的估计。

5. 合并#

HLL 的一个强大特点是它支持合并操作。如果你有两个独立的 HLL 数据结构，并且它们跟踪的是两个不同的数据集，那么你可以将它们合并成一个，这个新的 HLL 会像你在一个大数据集上跟踪一样。

这意味着 HLL 可以在多台机器进行分布式处理，符合大数据的处理场景。对于多台机器处理数据，我们可以通过一个简单的 “求并集” 的操作，获得样本总体统计结果。

总结#

HyperLogLog 是一种高效的算法，适用于在有限的内存下估算大数据集的基数。尽管它只提供了一个近似值，但在许多实际应用中，这种近似是足够的，并且内存节省的好处使其成为一个宝贵的工具。

下面给出算法简单的 C 语言实现，这个代码旨在提供一个简洁、直观的示例，但可能不是生产就绪的。它省略了很多细节，例如优化和边界情况的处理。此外，该哈希函数也是简化的，并不适合实际生产环境

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define BUCKET_COUNT 1024  // 2^10 buckets

typedef struct {
    unsigned char buckets[BUCKET_COUNT];
} HyperLogLog;

// 哈希函数简化示例。在实际应用中，你会希望使用更高质量的哈希函数，如MurmurHash、CityHash等。
unsigned int hash_function(const char* data) {
    unsigned int hash = 0;
    while (*data) {
        hash = (hash * 31) + *data++;  // 使用简单的乘法哈希
    }
    return hash;
}

int leading_zeros(unsigned int value) {
    if (value == 0) return 32;
    int count = 0;
    while ((value & 0x80000000) == 0) {
        count++;
        value <<= 1;
    }
    return count;
}

void hll_add(HyperLogLog *hll, const char* data) {
    unsigned int hash = hash_function(data);
    int bucket_idx = hash & (BUCKET_COUNT - 1);
    int zero_count = leading_zeros(hash >> 10);  // 使用除了bucket_idx外的其余部分
    if (zero_count > hll->buckets[bucket_idx]) {
        hll->buckets[bucket_idx] = zero_count;
    }
}

double hll_count(const HyperLogLog *hll) {
    double sum = 0.0;
    for (int i = 0; i < BUCKET_COUNT; i++) {
        sum += pow(2.0, -hll->buckets[i]);
    }
    return BUCKET_COUNT * BUCKET_COUNT / sum;
}

int main() {
    HyperLogLog hll;
    memset(&hll, 0, sizeof(hll));

    const char* samples[] = {
        "user1", "user2", "user3", "user1", "user2", "user4"
    };
    int sample_count = sizeof(samples) / sizeof(samples[0]);
    for (int i = 0; i < sample_count; i++) {
        hll_add(&hll, samples[i]);
    }
    printf("Estimated unique count: %f\n", hll_count(&hll));
    return 0;
}