Allen_Jeo

Allen_Jeo

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

image

HyperLogLog 算法简介#

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

1. 什么是 HyperLogLog?#

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

2. HyperLogLog 原理#

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

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

image

举个例子:如果我们连续不断地抛硬币,连续 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. 合并计数器值#

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

image

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;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。