Case study — Redis HLL & Kafka offset

TL;DR: Bài này xem hai công cụ production giải bài toán streaming. Redis HyperLogLog đếm số phần tử khác nhau trên dữ liệu khổng lồ với tối đa 12 KB và sai số chuẩn 0,81%. Kafka cho nhiều ứng dụng cùng đọc một luồng sự kiện, mỗi ứng dụng ở tốc độ riêng, vì sự kiện được lưu thành bản ghi có địa chỉ cố định (offset) và không bị xoá sau khi đọc. Redis đổi độ chính xác lấy bộ nhớ; Kafka đổi dung lượng đĩa lấy khả năng đọc lại, và chỉ đảm bảo thứ tự trong từng partition.

12 KB đếm hàng tỷ phần tử distinct — PFADD / PFCOUNT / PFMERGE

Partition = append-only log. Consumer commit offset để track vị trí đọc

Phần A: Redis HyperLogLog internals

1. Vấn đề: đếm unique visitor ở quy mô tỷ request

Bạn cần biết hôm nay có bao nhiêu người khác nhau xem trang sản phẩm X. Số này gọi là cardinality (số phần tử khác nhau trong một tập). Một trang có 500 triệu lượt xem mỗi ngày, lưu từng user ID vào hash set thì cần 500 triệu × 8 byte = 4 GB RAM, chỉ cho một trang. Với hàng triệu trang thì không thể. Redis HyperLogLog chiếm tối đa 12 KB mỗi key bất kể số phần tử, sai số chuẩn 0,81% theo tài liệu Redis.

2. Bên trong: register, dense và sparse

Trước khi xem lệnh Redis, cần hiểu một khái niệm nội tại: register. Trong HyperLogLog, register là một ô nhớ nhỏ (6 bit) lưu một con số thống kê về những phần tử đã hash vào ô đó. Redis dùng 16.384 register (tức 2¹⁴), mỗi register 6 bit → tổng 16384 × 6 / 8 = 12.288 byte ≈ 12 KB (cộng header ngắn).

Quá trình PFADD key x:

function pfadd(key, x):
    h <- murmurhash2_64(x)       -- Redis dùng MurmurHash2 64-bit, phân phối đều
    -- 14 bit đầu xác định register index (0..16383)
    registerIdx <- h >> 50        -- lấy 14 bit cao nhất
    -- 50 bit còn lại dùng để đếm leading zero
    remaining <- h << 14          -- bỏ 14 bit chỉ số, 50 bit còn lại dồn lên đầu word
    rank <- min(countLeadingZeros(remaining), 50) + 1  -- +1 vì đếm từ 1; chặn khi toàn 0
    -- cập nhật register nếu tìm được số lớn hơn
    if rank > register[registerIdx]:
        register[registerIdx] <- rank
// Time: O(1)  Space: O(1) — register đã cố định 12 KB

Đoạn trên là bản đơn giản hoá cho dễ đọc. Mã C của Redis lấy 14 bit thấp của hash làm chỉ số register và đếm số 0 liên tiếp tính từ bit thấp trong phần còn lại; ý tưởng giống hệt, chỉ khác phía bit mà nó đọc.

Vì sao số 0 đứng đầu ước lượng được số phần tử khác nhau? Với hash đều, xác suất có đúng k số 0 đứng đầu là 1/2^k, nên register có số 0 nhiều nhất là M thì khoảng 2^M phần tử đã rơi vào đó. Công thức ghép 16.384 register bằng trung bình điều hoà đã giải ở bài HyperLogLog; ở đây chỉ cần nhớ nó là lý do một register may mắn không làm hỏng cả ước lượng.

Sparse vs dense — tại sao Redis không tốn ngay 12 KB?

Khi mới tạo một HLL key, hầu hết 16.384 register đều bằng 0 — không cần lưu. Redis dùng hai chế độ (theo hyperloglog.c và redis.conf):

• Sparse encoding (mã hoá thưa): chỉ lưu các register khác 0 dưới dạng danh sách nén (run-length encoding). Khi key mới tạo và còn ít phần tử, key chỉ tốn vài chục byte.
• Dense encoding (mã hoá đặc): mảng 12 KB cố định. Redis chuyển sang dense khi dạng thưa vượt ngưỡng hll-sparse-max-bytes (mặc định 3000 byte, đã tính cả header 16 byte) hoặc khi có register mang giá trị lớn hơn 32, vì dạng thưa không biểu diễn nổi giá trị đó.

Redis tự chuyển sang dense khi cần.

12 KB là trần, không phải giá khởi điểm. Hệ có hàng triệu key mà phần lớn chỉ vài chục phần tử thì tổng RAM thực tế nhỏ hơn "số key × 12 KB" rất nhiều lần.

Thử ngẫmRAM Redis tăng đột ngột sau một chiến dịch marketing viral. Nếu hàng loạt HLL key cùng lúc vượt ngưỡng chuyển từ sparse sang dense, biểu đồ RAM theo thời gian sẽ trông thế nào?

3. PFMERGE: gộp mà không đếm trùng

PFMERGE dest src1 src2 ... lấy max từng register của các nguồn. Lấy max là đúng vì mỗi register lưu số 0 đứng đầu nhiều nhất, và max của hai giá trị lớn nhất chính là giá trị lớn nhất của phép hợp hai tập. Nhờ vậy PFMERGE uv:total uv:page1 uv:page2 đếm người xem nhiều trang đúng một lần, còn cộng PFCOUNT từng key thì đếm họ nhiều lần.

function pfmerge(dest, sources[]):
    for i from 0 to 16383:
        dest.register[i] <- max(src.register[i] for src in sources)
// Time: O(m × 16384) với m = số source key

4. API Redis và khi nào không dùng HLL

PFADD page:product123:uv "user-id-abc"     -- trả 1 nếu có register bị đổi
PFCOUNT page:product123:uv                 -- (integer) 42831
PFMERGE page:all:uv page:product123:uv page:product456:uv
PFCOUNT page:product123:uv page:product456:uv   -- gộp tạm rồi đếm

Không dùng HLL khi cần tần suất từng phần tử (dùng CMS hoặc hash map), khi cần liệt kê phần tử (HLL không lưu phần tử, dùng Set), hoặc khi sai số 0,81% không chấp nhận được như billing (dùng exact counter).

Thử ngẫmmarketing hỏi có bao nhiêu người xem trang A hoặc trang B hôm nay. Bạn dùng lệnh Redis nào để trả lời, và con số đó là đếm chính xác hay xấp xỉ?