HyperLogLog — đếm distinct xấp xỉ

TL;DR: Bài toán: đếm số phần tử khác nhau trong một luồng khổng lồ — ví dụ hôm nay có bao nhiêu người khác nhau ghé web, khi có 2 tỷ lượt và một người vào nhiều lần. Cách thẳng tay là ghi nhớ từng người đã thấy, nhưng thế thì tốn nhiều GB bộ nhớ. HyperLogLog đếm gần đúng (lệch chỉ vài phần trăm) mà chỉ tốn vài KB, nhờ một mẹo: biến mỗi phần tử thành một dãy bit trông như ngẫu nhiên, rồi chỉ ghi nhớ một con số về dãy "may mắn nhất" từng gặp — càng nhiều phần tử khác nhau, con số đó càng lớn, từ đó suy ngược ra số lượng. Redis dùng đúng cách này (lệnh PFADD/PFCOUNT, 12 KB). (Tên kỹ thuật của "số phần tử khác nhau" là cardinality — sẽ gặp lại từ này nhiều.)

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 phải quét toàn bộ bảng (thời gian tỉ lệ thuận với số dòng), tốn vài 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 — trò chơi tung đồng xu

Trước khi đụng công thức, hãy chơi một trò. Bạn tung đồng xu liên tục; mỗi lượt là tung cho tới khi ra ngửa lần đầu, và đếm số sấp liên tiếp trước đó. "Ngửa" ngay = 0 sấp; "sấp, ngửa" = 1 sấp; "sấp, sấp, sấp, ngửa" = 3 sấp.

Giờ bạn chỉ nhớ một con số duy nhất: chuỗi sấp dài nhất từng thấy. Nếu con số đó là 10, bạn đã chơi khoảng bao nhiêu lượt? Để xuất hiện 10 sấp liên tiếp cần xác suất 1/2^10 ≈ 1/1000, nên bạn hẳn đã chơi khoảng 1000 lượt (2^10). Chỉ từ một con số, bạn ước lượng được tổng số lượt — không cần nhớ từng lượt.

HyperLogLog làm đúng trò này trên dữ liệu:

Điểm mấu chốt: phép hash chỉ là một cách biến mỗi phần tử thành một dãy bit trông như ngẫu nhiên — và cùng một phần tử thì luôn cho cùng một dãy. Vì vậy hai phần tử giống nhau cho dãy giống hệt, không tạo "lượt chơi mới"; ta đang đếm đúng số phần tử khác nhau. Và như trò chơi, ta chỉ giữ một con số R_max, không lưu phần tử nào — đó là lý do HyperLogLog tốn vài KB thay vì vài GB.

Vì sao mẹo này đúng (phần công thức)

Giờ mới tới công thức, để thấy trực giác trên là có cơ sở. Vì dãy bit trông như ngẫu nhiên, xác suất một dãy mở đầu bằng ít nhất r số 0 là 1/2^r (đúng bằng xác suất tung được r lần sấp liên tiếp). Với n phần tử khác nhau, số 0-ở-đầu nhiều nhất quan sát được R_max thoả:

E[R_max] ≈ log2(n)      →      n ≈ 2^R_max

Lý do gọn: xác suất KHÔNG phần tử nào đạt r leading zero là (1 - 1/2^r)^n — giá trị này chuyển nhanh từ ~1 sang ~0 quanh n ≈ 2^r. Vậy R_max chính là thước đo tự nhiên của log2(n).

Ví dụ: n = 1.000.000 → kỳ vọng thấy ~20 leading zero (vì 2^20 ≈ 1M). Nếu R_max = 20 → n ≈ 2^20 = 1.048.576.

Vấn đề còn lại: một con số thì quá nhiễu — một phần tử "ăn may" 40 leading zero làm ước lượng sai gấp triệu lần. Chính nhu cầu giảm nhiễu này dẫn tới ý tưởng tiếp theo.

2. Đo nhiều lần rồi gộp (stochastic averaging) — chia thùng

Trực giác giảm nhiễu: hỏi một người chiều cao trung bình cả lớp thì sai số lớn; hỏi nhiều người rồi gộp lại thì ổn định hơn nhiều. HyperLogLog cũng vậy — thay vì một thước đo duy nhất, ta đo nhiều lần song song rồi gộp (tên kỹ thuật là stochastic averaging).

Cụ thể: chia thành m "thùng" (bucket — mỗi thùng là một bộ đếm riêng). Mỗi dãy bit của một phần tử bắt đầu bằng vài bit; ta lấy vài bit đầu tiên của dãy đó để quyết định phần tử rơi vào thùng nào, phần bit còn lại mới dùng để đếm số 0 ở đầu. Cần b bit để đánh số m thùng, với b và m liên hệ qua:

m = 2^b      (b bit đánh số được 2^b thùng)

Mỗi thùng giống một lượt chơi tung xu độc lập.

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 thùng M[idx] chỉ giữ một con số: chuỗi 0-ở-đầu dài nhất từng thấy trong các phần tử rơi vào thùng đó. Sau khi xử lý hết luồng, ta có m ước lượng độc lập để gộp lại.

3. Chạy thử thuật toán add một lần

Hãy theo dõi từng bước khi đưa một phần tử qua thuật toán, với b = 14 (tức m = 16384 thùng, đúng cấu hình Redis).

Trước hết, một câu cho người chưa quen làm việc trực tiếp với bit. Giá trị hash là một dãy 64 con số 0/1. Ta sẽ làm hai thao tác đơn giản trên dãy đó: (1) cắt 14 con số đầu làm số hiệu thùng; (2) trong phần còn lại, đếm xem có bao nhiêu số 0 đứng liền nhau ở đầu trước khi gặp số 1 đầu tiên. Hai thao tác này tương ứng với các lệnh dịch bit (>>, <<) và hàm đếm số 0 ở đầu (countLeadingZeros) trong đoạn dưới — đừng lo nếu chưa quen ký hiệu, cứ đọc theo nghĩa "cắt" và "đếm".

Ví dụ dưới dùng một hash viết ở hệ 16 (0xA3C0..., cách viết gọn của dãy bit) để minh hoạ.

Input: h = 0xA3C0100000000000  (64-bit)
       b = 14   -> m = 16384,  phần còn lại w rộng 64 - 14 = 50 bit

Bước 1 — viết h dạng nhị phân (64 bit):
  1010001111 0000 | 00000100000000000000000000000000000000000000000000
  \________ 14 bit đầu ________/   \____________ 50 bit w ____________/

Bước 2 — idx = h >> (64 - 14) = h >> 50
  idx = 10100011110000 (nhị phân) = 10480 (thập phân)

Bước 3 — w = 50 bit còn lại (sau khi bỏ 14 bit bucket)
  w = 00000 1 0000...0   -> có 5 leading zero rồi tới bit 1 đầu tiên

Bước 4 — rank = countLeadingZeros(w) + 1 = 5 + 1 = 6

Bước 5 — cập nhật register:
  M[10480] <- max(M[10480], 6)
  // nếu M[10480] đang là 4 -> thành 6;  nếu đang là 8 -> giữ 8 (max)

Một phần tử có rank = 6 đóng góp ước lượng cục bộ 2^6 = 64 cho bucket 10480 — nhưng chỉ là một trong 16384 bucket; con số cuối cùng đến từ harmonic mean qua toàn bộ register (mục dưới).

Vẽ ra thì quan hệ giữa hai nửa thành hình học: 14 bit đầu không tham gia đếm số 0, và 50 bit sau không tham gia chọn thùng. Đó cũng là một đánh đổi mà bảng sai số không nói ra — tăng số thùng để chính xác hơn thì phần dùng để đếm ngắn đi.

4. Vì sao HyperLogLog dùng harmonic mean thay vì trung bình cộng?

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ả.

5. Độ chính xác — sai số và bộ nhớ

Kết quả là ước lượng nên luôn lệch một chút so với con số thật. Mức lệch điển hình (gọi là sai số chuẩn — trung bình kết quả lệch bao nhiêu phần trăm) phụ thuộc vào số thùng m: càng nhiều thùng càng chính xác. Quan hệ đó là:

sai số chuẩn ≈ 1.04 / sqrt(m)

(sqrt(m) là căn bậc hai của m.)

Redis chọn m = 16384 thùng (cần 14 bit để đánh số) và mỗi bộ đếm rộng 6 bit, tổng 12 KB, sai số chuẩn khoảng 0,81%. Cấu trúc này đếm tốt tới khoảng 2^32 phần tử khác nhau (vài trăm triệu tới vài tỷ). Vượt ngưỡng đó, hai phần tử khác nhau bắt đầu dễ tình cờ cho cùng một dãy hash (hiện tượng trùng ngẫu nhiên này gọi là birthday paradox, xuất hiện quanh mốc 2^32) — khiến kết quả lệch ngày một nhiều theo một hướng cố định (sai lệch hệ thống, tiếng Anh là bias).

Quan hệ đáng nhớ: muốn giảm sai số một nửa thì phải tăng bộ nhớ gấp 4 (vì sai số phụ thuộc vào căn bậc hai của số thùng). Đây là sự đánh đổi cơ bản của mọi cấu trúc dữ liệu ước lượng kiểu này.

6. Mở rộng: HyperLogLog++ và khả năng gộp

Bản chạy thật trong sản phẩm thường dùng HyperLogLog++ (Heule và cộng sự, 2013, Google) với hai cải tiến:

• Lưu dạng thưa (sparse representation): khi số phần tử còn ít, hầu hết thùng đang rỗng nên thay vì giữ đủ mảng m thùng, ta chỉ ghi vài cặp "số hiệu thùng → giá trị" đang khác rỗng để đỡ tốn bộ nhớ; khi dữ liệu nhiều lên thì tự chuyển về lưu đủ mảng (dense).
• Hiệu chỉnh sai lệch bằng số đo thực tế (empirical bias correction): với vùng ít phần tử, thay công thức đơn giản bằng một bảng tra dựng từ đo đạc thật để bù phần lệch.

Chi tiết kỹ thuật đi sâu ở case study Redis & Kafka.

Tính chất quan trọng nhất cho hệ chạy trên nhiều máy là khả năng gộp (mergeability) — ghép nhiều bộ đếm rời thành một:

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

Khả năng gộp cực kỳ quan trọng: chia luồng cho nhiều máy, mỗi máy xử lý một phần, rồi gộp kết quả bằng cách lấy số lớn hơn ở từng thùng — cho ra đúng kết quả như khi một máy chạy toàn bộ luồng. Nhờ vậy cả cụm máy đếm được số phần tử khác nhau mà không cần gửi dữ liệu gốc qua lại.

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

• Hash function: HyperLogLog phụ thuộc hoàn toàn vào việc hash trải đều các phần tử. Hash kém (hay cho trùng ở những bit đầu) làm sai số vượt mức lý thuyết. Các hàm hash nhanh, không dùng cho mật mã như MurmurHash2, MurmurHash3 hay xxHash đều hợp vì chúng trải đều tốt — Redis dùng một biến thể 64-bit của MurmurHash2 (MurmurHash64A), không phải MurmurHash3.
• Bloom filter: cùng họ cấu trúc dữ liệu trả lời gần đúng dựa trên hash — Bloom filter trả lời "phần tử này đã có chưa", còn HyperLogLog trả lời "có bao nhiêu phần tử khác nhau". Cả hai chấp nhận trả lời gần đúng để đổi lấy việc tốn rất ít bộ nhớ.
• Count-Min Sketch: thêm một thành viên cùng họ — đếm tần suất xấp xỉ (mỗi phần tử xuất hiện bao nhiêu lần) thay vì số phần tử khác nhau. Ba cấu trúc (Bloom, HyperLogLog, Count-Min) giải ba bài toán khác nhau theo cùng một cách làm: hash + giữ ít trạng thái + chấp nhận sai số có giới hạn.
• Reservoir sampling: cùng bài toán xử lý luồng nhưng hướng khác — reservoir giữ một mẫu chính xác các phần tử, còn HyperLogLog chỉ giữ con số nén lại. Khi cần "lấy mẫu để phân tích" thì dùng reservoir; khi chỉ cần biết có bao nhiêu phần tử khác nhau thì 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

• Leading-zero tối đa ≈ log2(cardinality); chia m bucket bằng b bit đầu hash, mỗi bucket giữ leading-zero max riêng → m ước lượng độc lập.
• Harmonic mean triệt tiêu outlier; sai số chuẩn 1.04/sqrt(m) — muốn sai số 2× nhỏ hơn cần 4× bộ nhớ.
• Redis: m=16384, 6 bit/register, 12 KB, sai số 0,81%; trần thực tế ~2^32 distinct — quanh birthday-bound 64-bit hash bắt đầu trùng, sai số tăng dần.
• Mergeability: max từng register → union đúng toán học; đếm distinct trên cluster mà không 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ỉ