Case study — Redis HLL & Kafka offset

TL;DR: Redis nhúng HyperLogLog trực tiếp vào data store — PFADD key element cập nhật sketch 12 KB, PFCOUNT key trả về distinct count xấp xỉ với sai số 0.81%, và PFMERGE gộp nhiều HLL trong O(1). Kafka giải quyết bài toán khác nhưng liên quan: lưu toàn bộ stream như một append-only log phân vùng, mỗi message có offset bất biến. Consumer không xóa message — họ commit offset để ghi nhớ mình đã đọc tới đâu. Hai hệ thống triển khai hai triết lý của module: Redis dùng approximation để tiết kiệm bộ nhớ, Kafka dùng sequential log để tối đa throughput.

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

Một trang thương mại điện tử muốn biết số user khác nhau đã xem trang sản phẩm X trong 24 giờ qua. Với 500 triệu lượt xem, nếu mỗi user ID 8 byte, đếm chính xác bằng hash set cần 500 triệu × 8 = 4 GB RAM — chỉ cho một trang sản phẩm, với hàng triệu trang sản phẩm là không thể.

Redis giải quyết bằng HyperLogLog: mỗi key HLL chiếm tối đa 12 KB bất kể số phần tử distinct, sai số xác suất là 0.81% (nhỏ hơn cả sai số sampling trong phần lớn analytics pipeline).

2. Cấu trúc dense/sparse representation

Redis HLL dùng 16,384 register (2¹⁴ = 16384), mỗi register 6 bit → tổng 16384 × 6 / 8 = 12,288 byte ≈ 12 KB. Mỗi register lưu maximum leading-zero count của tất cả phần tử hash vào register đó.

Quá trình PFADD key x:

function pfadd(key, x):
    h <- murmurhash64(x)         -- 64-bit hash, uniform distribution
    -- 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 & ((1 << 50) - 1)
    leadingZeros <- countLeadingZeros(remaining) + 1  -- +1 vì đếm từ 1
    -- cập nhật register nếu tìm được số lớn hơn
    if leadingZeros > register[registerIdx]:
        register[registerIdx] <- leadingZeros
// Time: O(1)  Space: O(1) — register đã cố định 12 KB

Tại sao leading-zero lại ước lượng được distinct count? Nếu hash là uniform random 50-bit, xác suất để leading-zero count = k là 1/2^k. Nếu maximum leading-zero trong một register là M, ta ước lượng số phần tử hashed vào register đó khoảng 2^M. Với 16,384 register, tổng distinct count xấp xỉ alpha × 16384² × harmonic_mean(2^M[i]) — harmonic mean giảm ảnh hưởng của outlier (một register có M rất lớn không làm hỏng toàn bộ ước lượng).

Sparse vs dense representation: Redis không ngay lập tức dùng 12 KB khi mới tạo HLL key. Khi số register được set còn ít (dưới 1% tổng 16384 = khoảng 164 register), Redis dùng sparse encoding — chỉ lưu các register khác 0 dưới dạng run-length encoding. Key chuyển sang dense encoding (12 KB cố định) khi sparse không còn tiết kiệm hơn. Điều này quan trọng với hệ thống có hàng triệu HLL key cho hàng triệu trang sản phẩm — phần lớn key ban đầu chỉ tốn vài chục byte.

graph LR
    NEW["Key mới tạo\nsparse encoding\n(vài chục byte)"] -- "thêm phần tử\ncho đến ~164 register" --> SPARSE["Sparse\nrun-length encoding\n(nhỏ hơn 12 KB)"]
    SPARSE -- "dense hơn hiệu quả" --> DENSE["Dense encoding\n12,288 byte cố định\n(12 KB)"]
    DENSE -- "PFADD thêm phần tử\nbất kỳ" --> DENSE

3. PFMERGE — gộp nhiều HLL trong O(m)

PFMERGE dest src1 src2 ... gộp nhiều HLL key thành một key mới. Cơ chế: với mỗi register i, dest[i] = max(src1[i], src2[i], ...). Max là đúng vì mỗi register lưu maximum leading-zero count — max của max vẫn là max.

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
// Space: O(1) — ghi vào dest đã có sẵn

Ứng dụng thực tế: PFMERGE uv:total uv:page1 uv:page2 uv:page3 tính tổng unique visitor trên tất cả trang mà không double-count user đã thăm nhiều trang.

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

-- Thêm phần tử vào HLL (trả về 1 nếu cardinality thay đổi, 0 nếu không)
PFADD page:product123:uv "user-id-abc"

-- Lấy ước lượng distinct count
PFCOUNT page:product123:uv
-- Trả về: (integer) 42831

-- Gộp nhiều HLL
PFMERGE page:all:uv page:product123:uv page:product456:uv

-- PFCOUNT nhiều key cùng lúc (tương đương PFMERGE tạm thời rồi count)
PFCOUNT page:product123:uv page:product456:uv

Khi nào KHÔNG dùng Redis HLL:

• Cần tần suất của từng phần tử (HLL chỉ cho distinct count, không biết ai xuất hiện bao nhiêu lần) — dùng CMS hoặc hash map.
• Cần enumerate các phần tử distinct (HLL không lưu phần tử, chỉ lưu sketch) — dùng Set hoặc Bloom filter.
• Sai số 0.81% không chấp nhận được (ví dụ billing, legal counting) — dùng exact counter.

Phần B — Kafka offset & append-only log

5. Vấn đề: stream processing ở quy mô hàng triệu message/giây

Apache Kafka là distributed event streaming platform được dùng để xử lý stream dữ liệu real-time. Các hệ thống như LinkedIn (nơi Kafka ra đời), Uber, Netflix dùng Kafka để truyền hàng triệu sự kiện mỗi giây giữa các service.

Bài toán cốt lõi Kafka giải quyết: làm thế nào để nhiều consumer đọc cùng một stream, mỗi consumer ở tốc độ riêng, mà không consumer nào ảnh hưởng đến consumer khác?

6. Partition = append-only log

Mỗi topic trong Kafka được chia thành nhiều partition. Mỗi partition là một append-only log — danh sách message chỉ thêm vào cuối, không bao giờ sửa hay xóa (trong retention window):

graph LR
    P["Partition 0\n(append-only log)"]
    subgraph P["Partition 0"]
        M0["offset 0\nmsg A"] --> M1["offset 1\nmsg B"] --> M2["offset 2\nmsg C"] --> M3["offset 3\nmsg D"] --> M4["offset 4\nmsg E"]
    end
    C1["Consumer Group 1\ncommitted offset: 3"] -.->|"đọc tiếp từ 3"| M3
    C2["Consumer Group 2\ncommitted offset: 1"] -.->|"đọc tiếp từ 1"| M1

Offset là số nguyên không âm tăng dần, đóng vai trò địa chỉ bất biến của mỗi message trong partition. Một khi message được ghi với offset 42, nó luôn ở offset 42 cho đến khi bị xóa do retention. Consumer không xóa message sau khi đọc — họ chỉ commit offset để ghi nhớ mình đã đọc tới đâu.

7. Vì sao append-only log hiệu quả hơn queue truyền thống?

Queue truyền thống (RabbitMQ, ActiveMQ) xóa message sau khi consumer ACK:

graph LR
    PROD["Producer"] --> Q["Queue\n(xóa sau ACK)"]
    Q --> C1["Consumer 1"]
    Q --> C2["Consumer 2"]

Kafka log giữ message trong retention window:

graph LR
    PROD2["Producer"] --> LOG["Append-only log\n(giữ trong retention)"]
    LOG --> CG1["Consumer Group 1\n(analytics pipeline)"]
    LOG --> CG2["Consumer Group 2\n(real-time dashboard)"]
    LOG --> CG3["Consumer Group 3\n(backup to S3)"]

Với append-only log:

• Nhiều consumer group đọc độc lập — Consumer Group 1 (analytics) có thể đọc chậm mà không ảnh hưởng Consumer Group 2 (dashboard real-time). Không có "queue drain" hay back-pressure lan sang consumer khác.
• Replay — Consumer mới (hoặc consumer cần reprocess) có thể đặt offset về 0 và đọc lại toàn bộ log từ đầu.
• Sequential I/O — write luôn vào cuối file, read theo offset liên tiếp → sequential I/O, throughput hàng triệu message/giây trên disk thông thường (liên hệ external sort — cùng nguyên lý I/O tuần tự nhanh hơn random I/O).

8. Consumer group và offset commit

Mỗi consumer group có một bảng offset riêng trong Kafka (lưu ở internal topic __consumer_offsets). Consumer commit offset để ghi nhận "tôi đã xử lý xong message tới offset N":

-- Consumer loop cơ bản
function consumeLoop(consumer, topic, partition):
    consumer.subscribe(topic)
    while đang chạy:
        records <- consumer.poll(timeout=100ms)
        for each record in records:
            process(record)
        -- commit sau khi process xong (at-least-once)
        consumer.commitSync()

At-least-once vs exactly-once:

• At-least-once (mặc định): commit AFTER processing. Nếu consumer crash giữa chừng, khi restart sẽ đọc lại từ offset đã commit → có thể process duplicate. Đây là mặc định vì đơn giản hơn và idempotent processing thường đủ.
• At-most-once: commit BEFORE processing. Nếu crash, message bị mất. Phù hợp với log/metrics không quan trọng.
• Exactly-once: Kafka Transactions (Kafka 0.11+) — producer và consumer commit trong cùng transaction với Kafka broker. Chi phí cao hơn nhưng đảm bảo không duplicate, không mất message.

9. Retention và log compaction

Kafka không lưu message mãi mãi. Hai chính sách:

• Time-based retention (retention.ms): xóa segment cũ hơn N ngày. Ví dụ retention.ms=604800000 (7 ngày) — phù hợp với event stream ngắn hạn.
• Log compaction (cleanup.policy=compact): giữ message mới nhất cho mỗi key, xóa message cũ có cùng key. Phù hợp với changelog stream (state update) — mỗi key chỉ cần giá trị cuối cùng.

Vì sao chọn cấu trúc nào

graph TD
    Q0["Bài toán streaming"] --> Q1{"Cần biết gì?"}
    Q1 -- "Số phần tử distinct\n(unique visitors)" --> HLL2["HyperLogLog\nRedis PFADD/PFCOUNT\n12 KB, sai số 0.81%"]
    Q1 -- "Tần suất phần tử\n(top-K views)" --> CMS2["Count-Min Sketch\n+ min-heap\nModule 3 bài 6"]
    Q1 -- "Truyền event\ngiữa service" --> Q2{"Nhiều consumer\nhay một?"}
    Q2 -- "Một consumer" --> MQ["Queue truyền thống\n(RabbitMQ, SQS)"]
    Q2 -- "Nhiều consumer\nđộc lập" --> KFK["Kafka append-only log\noffset bất biến, replay"]
    Q1 -- "Sắp xếp\ndữ liệu lớn" --> ES2["External merge sort\nbài 01 module này"]

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

• HyperLogLog: bài concept giải thích cơ chế leading-zero, register, harmonic mean. Case study này là ứng dụng Redis cụ thể — đọc bài 03 trước để hiểu tại sao 16,384 register cho sai số 0.81%.
• Count-Min Sketch: Redis không có CMS built-in nhưng RedisBloom module (Redis Stack) cung cấp CMS.INCRBY và CMS.QUERY. Mini-challenge bài 06 dùng CMS để giải bài toán top-K mà Kafka thường generate.
• External sort: Kafka sequential log và external sort cùng khai thác một nguyên lý — sequential I/O nhanh hơn random I/O hàng chục lần. Kafka partition file là sequential log vì cùng lý do external sort chọn merge sequential file thay vì random read.
• Sliding window: Kafka Streams và Flink cung cấp window operator để tính thống kê trên sliding window trên stream Kafka — window size và grace period là tham số thiết kế liên quan trực tiếp đến bài 05.

Tự kiểm tra

Bài tiếp theo: Module 3 — Tổng kết & cheat sheet