HyperLogLog — đếm distinct xấp xỉ

TL;DR: Đếm số phần tử khác nhau (cardinality) trên stream 1 tỷ phần tử đòi O(n) RAM nếu dùng hash set — vài GB. HyperLogLog (Flajolet et al. 2007) làm điều đó với vài kilobyte, sai số chuẩn ~1.04/sqrt(m) (~2% với m=2048 bucket). Ý tưởng: nếu hash đều, số leading zero tối đa quan sát được tương quan với log2 cardinality. Cải tiến: chia m bucket (stochastic averaging), dùng harmonic mean để triệt tiêu outlier. Redis PFADD/PFCOUNT dùng đúng thuật toán này với 12 KB, sai số 0.81%. Ứng dụng: đếm unique visitor, distinct query trong analytics, cardinality estimation cho query planner.

Analytics pipeline của bạn cần trả lời: "Hôm nay có bao nhiêu unique user truy cập?" Dữ liệu: 2 tỷ event, mỗi event có user_id. Dùng SELECT COUNT(DISTINCT user_id) — Postgres scan toàn bảng, sort hoặc hash O(n), tốn phút. Lưu hash set tất cả user_id đã thấy? 2 tỷ × 8 byte = 16 GB RAM chỉ cho bộ đếm. Bạn chỉ cần con số "khoảng bao nhiêu", sai số 1-2% chấp nhận được — nhưng phải trả lời trong vài millisecond với vài KB bộ nhớ.

HyperLogLog là câu trả lời. Đây không phải "trick" — nó có nền toán học chặt chẽ từ lý thuyết xác suất và combinatorics.

1. Trực giác — leading zero và cardinality

Quan sát cốt lõi: nếu hash function trải đều output trên [0, 2^32), và ta quan sát n giá trị hash riêng biệt, thì số leading zero tối đa quan sát được R_max thoả mãn:

E[R_max] ≈ log2(n)

Lý do: xác suất một hash có ít nhất r leading zero = 1/2^r. Trong n phần tử distinct, xác suất có ít nhất một cái đạt r leading zero ≈ 1 - (1 - 1/2^r)^n. Con số này chuyển từ ~0 sang ~1 khi n vượt 2^r. Vậy R_max quan sát được là ước lượng tự nhiên của log2(n), và 2^R_max ≈ n.

Ví dụ cụ thể: với n = 1.000.000 distinct phần tử, ta kỳ vọng thấy ít nhất một hash có 20 leading zero (vì 2^20 ≈ 1M). Nếu R_max = 20 → ước lượng n ≈ 2^20 = 1.048.576.

Vấn đề: variance rất lớn. Một phần tử duy nhất có thể tình cờ có 40 leading zero → ước lượng sai lệch gấp triệu lần. Cần kỹ thuật giảm variance.

2. Stochastic averaging — chia bucket

Thay vì dùng 1 ước lượng, chia thành m bucket bằng cách dùng b = log2(m) bit đầu của hash làm bucket index. Các bit còn lại dùng để đếm leading zero.

function HyperLogLog_add(x, M[0..m-1]):
    h <- hash(x)                        -- hash 64-bit, phân phối đều
    b <- log2(m)                        -- số bit dùng cho bucket index
    idx <- h >> (64 - b)                -- b bit đầu = bucket index
    w <- h << b                         -- bỏ b bit bucket, đẩy (64-b) bit còn lại lên đầu word
    leading <- countLeadingZeros(w) + 1 -- rank: vị trí bit 1 đầu tiên trong phần còn lại
    M[idx] <- max(M[idx], leading)      -- giữ giá trị tối đa

// Time: O(1)  Space: O(m) registers, mỗi register 5-6 bit

Mỗi bucket M[idx] giữ giá trị R_max của riêng phần tử hash vào bucket đó. Sau khi xử lý toàn stream, ta có m ước lượng độc lập.

3. Harmonic mean và hiệu chỉnh

Trung bình cộng của 2^M[i] rất nhạy với outlier (1 bucket có R_max lớn tình cờ làm tăng vọt kết quả). Harmonic mean (trung bình điều hoà) ít nhạy với outlier hơn:

function HyperLogLog_estimate(M[0..m-1]):
    Z <- 0
    for i từ 0 đến m-1:
        Z <- Z + 2^(-M[i])              -- nghịch đảo của ước lượng từng bucket

    alpha_m <- hằng số hiệu chỉnh(m)   -- xấp xỉ 0.7213 / (1 + 1.079/m)
    E <- alpha_m × m^2 / Z             -- ước lượng cardinality

    -- Hiệu chỉnh biên (small/large range correction):
    if E <= 5m/2:                       -- vùng nhỏ: có thể nhiều bucket rỗng
        V <- số bucket M[i] = 0
        if V > 0:
            E <- m × ln(m / V)          -- linear counting (chính xác hơn khi n nhỏ)
    if E > (1/30) × 2^32:              -- vùng lớn (chỉ cần với hash 32-bit)
        E <- -2^32 × ln(1 - E/2^32)

    return E
// Time: O(m)  Space: O(1) ngoài array M

Tại sao harmonic mean? Với các số 2^M[i] — một bucket tình cờ có M[i] = 40 cho 2^40 ≈ 1T. Harmonic mean dùng 2^(-M[i]) — outlier 40 đóng góp 2^(-40) ≈ 0 thay vì 10^12, không làm lệch kết quả.

flowchart LR
    ITEM(["Phần tử x"])
    HASH["hash(x)\n→ 64-bit"]
    SPLIT["Tách:\nb bit đầu → bucket idx\n64-b bit còn lại → w"]
    COUNT["leading_zeros(w) + 1\n= r"]
    UPDATE["M[idx] <- max(M[idx], r)"]
    EST["Harmonic mean\nqua m bucket\n→ ước lượng n"]

    ITEM --> HASH --> SPLIT --> COUNT --> UPDATE
    UPDATE -.->|"sau toàn stream"| EST

4. Độ chính xác — sai số chuẩn và bộ nhớ

Sai số chuẩn (standard error) của HyperLogLog:

σ = 1.04 / sqrt(m)

Redis chọn m=16384 (14 bit bucket) và 6-bit register → 12 KB tổng, sai số chuẩn 0.81%. Đếm được đến 2^64 phần tử distinct với sai số này.

Quan hệ thú vị: sai số tỉ lệ nghịch với sqrt(m) — muốn giảm sai số 2 lần phải tăng bộ nhớ 4 lần. Đây là trade-off cơ bản của mọi sketch algorithm.

5. HyperLogLog++ và sparse representation

Google đề xuất HyperLogLog++ (Heule et al. 2013) với hai cải tiến chính:

Sparse representation: khi cardinality nhỏ (ít phần tử), phần lớn bucket rỗng. Lưu sparse dictionary {bucket_idx: register_value} thay vì dense array → tiết kiệm memory khi n nhỏ; tự động chuyển sang dense khi fill ratio vượt ngưỡng.

Bias correction: với cardinality nhỏ, bias của estimator lớn hơn lý thuyết. HyperLogLog++ dùng empirical bias correction table thay vì công thức đơn giản.

-- Merge 2 HyperLogLog (ứng dụng distributed counting):
function merge(M_A[0..m-1], M_B[0..m-1]):
    M_merged <- []
    for i từ 0 đến m-1:
        M_merged[i] <- max(M_A[i], M_B[i])  -- union: max từng register
    return M_merged
// Time: O(m)  Space: O(m)
-- Merge đúng vì max leading zero = union của 2 tập distinct elements

Mergeability là tính chất cực kỳ quan trọng: mỗi shard xử lý 1/k stream, merge kết quả bằng max từng register — đúng như chạy trên toàn stream. Cho phép đếm distinct trên cluster mà không gửi dữ liệu thô.

6. Liên hệ các bài khác

• Hash function: HyperLogLog hoàn toàn phụ thuộc vào hash function phân phối đều. Hash xấu (collision nhiều ở leading bit) làm sai số vượt lý thuyết. MurmurHash3 hoặc xxHash64 thường được chọn vì uniformity tốt.
• Bloom filter: cùng họ probabilistic data structure dùng hash — Bloom filter trả lời "có tồn tại không" (membership), HyperLogLog trả lời "có bao nhiêu distinct" (cardinality). Cả hai trade exact answer lấy memory efficiency.
• Count-Min Sketch: thêm một thành viên trong họ sketch — đếm tần suất xấp xỉ (frequency) thay vì cardinality. Ba cấu trúc (Bloom, HyperLogLog, Count-Min) giải ba bài toán khác nhau cùng paradigm: hash + compact state + probabilistic bound.
• Reservoir sampling: cùng bài toán streaming, cách tiếp cận khác — reservoir lưu mẫu exact, HyperLogLog lưu sketch compressed. Khi cần "mẫu để analyse", dùng reservoir; khi chỉ cần cardinality, dùng HyperLogLog.
• Case study Redis & Kafka: Redis PFADD/PFCOUNT/PFMERGE là triển khai HyperLogLog production — case study đi sâu vào config thực tế và khi nào nên dùng.

📚 Deep Dive

Tóm tắt

• Ý tưởng cốt lõi: số leading zero tối đa của hash ≈ log2(cardinality) — không cần lưu phần tử, chỉ cần 1 số đếm.
• Stochastic averaging: chia m bucket bằng b bit đầu hash, mỗi bucket giữ leading-zero tối đa riêng → m ước lượng độc lập.
• Harmonic mean qua m bucket triệt tiêu outlier; nhân hằng số hiệu chỉnh alpha_m.
• Sai số chuẩn 1.04/sqrt(m) — muốn sai số 2x nhỏ hơn cần 4x bộ nhớ.
• Redis: m=16384, 6-bit register, 12 KB total, sai số 0.81% cho đến 2^64 distinct (trần lý thuyết của không gian hash 64-bit; va chạm hash đáng kể quanh ~2^32 birthday-bound nên sai số thực tế tăng dần khi cardinality tiếp cận 2^32).
• Mergeability: max từng register — đếm distinct trên cluster bằng cách merge sketch, không cần gửi dữ liệu thô.

Tự kiểm tra

Bài tiếp theo: Count-Min Sketch — đếm tần suất xấp xỉ