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;
}