Case study — Redis HLL & Kafka offset

TL;DR: Bài này xem hai công cụ thực tế giải bài toán streaming bằng cách nào. Redis HyperLogLog cho phép đếm số phần tử khác nhau (unique visitor, distinct user ID…) trên dữ liệu khổng lồ, chỉ tốn 12 KB bộ nhớ, sai số chưa tới 1%. Kafka giải bài toán khác: làm sao để nhiều ứng dụng cùng đọc một luồng sự kiện, mỗi ứng dụng ở tốc độ riêng, mà không ứng dụng nào làm phiền ứng dụng kia — bằng cách lưu mỗi sự kiện như một bản ghi có địa chỉ cố định (gọi là offset), không xoá sau khi đọc. Hai hệ thống thể hiện hai triết lý: Redis dùng xấp xỉ để tiết kiệm bộ nhớ, Kafka dùng ghi tuần tự để tối đa tốc độ.

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 — không phải bao nhiêu lượt xem, mà bao nhiêu người khác nhau. Số liệu này (gọi kỹ thuật là cardinality — tức là số phần tử khác nhau trong một tập) rất thường gặp trong analytics, nhưng tốn kém để tính chính xác khi dữ liệu lớn.

Ví dụ cụ thể: một trang thương mại điện tử có 500 triệu lượt xem một ngày. Nếu lưu từng user ID đã thấy vào một hash set để đếm chính xác, cần 500 triệu × 8 byte = 4 GB RAM — chỉ cho một trang sản phẩm. Với hàng triệu trang, không thể.

Redis giải quyết bằng HyperLogLog: mỗi bộ đếm HLL chiếm tối đa 12 KB bất kể có bao nhiêu phần tử khác nhau, sai số xác suất là 0,81% — nhỏ hơn cả sai số của hầu hết pipeline analytics.

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. Bài HyperLogLog giải thích tại sao con số register này cho sai số 0,81%.

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 & ((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² / (tổng các 2^(−M[i])) (đúng công thức ở bài HyperLogLog). Mẫu số tổng 2^(−M[i]) chính là phép trung bình điều hoà (harmonic mean) — nó làm giảm ảnh hưởng của một register may mắn có M quá lớn, không làm hỏng toàn bộ ướ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ế độ:

• 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, dùng khi có đủ register khác 0 (khoảng trên 164 register) đến mức mã hoá thưa không còn tiết kiệm hơn.

Redis tự động chuyển từ sparse sang dense khi cần — bạn không cần làm gì.

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.

3. PFMERGE — gộp nhiều bộ đếm mà không đếm trùng

PFMERGE dest src1 src2 ... gộp nhiều HLL key thành một key mới. Câu hỏi tự nhiên: tại sao gộp được mà không đếm trùng người dùng đã thăm nhiều trang?

Cơ chế: với mỗi register thứ i, giá trị kết quả là max(src1[i], src2[i], ...). Max là đúng vì mỗi register lưu maximum leading-zero count — max của hai maximum vẫn là maximum, đúng với nghĩa tập hợp hợp (union).

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 đếm trùng người đã thăm nhiều trang.

4. API Redis và khi nào nên — không nên — 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 liệt kê 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 đề: nhiều ứng dụng cùng đọc một luồng sự kiện

Hãy tưởng tượng một hệ thống e-commerce gửi ra sự kiện "đơn hàng vừa được đặt" mỗi khi có đơn mới. Ba ứng dụng cần đọc luồng sự kiện này:

• Pipeline analytics tổng hợp doanh thu theo giờ
• Dashboard real-time hiển thị đơn mới
• Job backup ghi sang S3

Nếu dùng queue truyền thống (RabbitMQ, SQS), mỗi sự kiện bị xoá sau khi một consumer ACK — ứng dụng thứ hai và thứ ba không đọc được. Phải tạo ba queue riêng, sao chép sự kiện sang cả ba — không scalable.

Apache Kafka giải bài này bằng cách lưu sự kiện như một cuốn sổ nhật ký chỉ ghi thêm: không xoá sau khi đọc, mỗi dòng có số trang cố định, ai muốn đọc trang nào cũng được.

6. Partition = append-only log — danh sách chỉ ghi thêm

Mỗi topic (chủ đề) trong Kafka được chia thành nhiều partition (phân vùng). Một partition là một append-only log — danh sách sự kiện chỉ được thêm vào cuối, không bao giờ sửa hay xoá trong thời gian lưu trữ (retention window).

Mỗi sự kiện trong partition có một offset — số nguyên tăng dần bắt đầu từ 0, đóng vai trò địa chỉ bất biến: một khi sự kiện ghi vào offset 42, nó luôn ở offset 42 cho đến khi hết retention. Consumer không xoá sự kiện sau khi đọc — họ chỉ commit offset để ghi nhớ "tôi đã đọc tới offset này".

Hai con số offset nằm ở phía consumer — nét đứt là vì thế. Log không biết và không đổi gì khi chúng đổi; muốn xử lý lại từ đầu thì chỉ cần đặt con số về 0.

Consumer Group 1 (analytics) đang ở offset 3, Consumer Group 2 (dashboard) đang ở offset 1 — cả hai đọc từ cùng partition nhưng hoàn toàn độc lập.

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

Queue truyền thống xoá sự kiện sau khi consumer ACK — muốn ba ứng dụng đọc phải tạo ba queue riêng và sao chép dữ liệu:

Toàn bộ khác biệt quy về một dòng: queue xoá sau ACK, log thì không. Mọi thứ người ta khen Kafka — nhiều consumer group độc lập, đọc lại được, thêm consumer mới sau vẫn có dữ liệu cũ — đều là hệ quả của đúng dòng đó.

Kafka log giữ sự kiện trong retention window — ba ứng dụng đọc cùng một partition, mỗi ứng dụng có offset riêng:

Ba lợi ích cụ thể:

• Nhiều consumer group đọc độc lập — Consumer Group 1 (analytics) xử lý chậ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 xử lý lại dữ liệu có thể đặt offset về 0 và đọc lại toàn bộ log từ đầu.
• Sequential I/O — ghi luôn vào cuối file, đọc theo offset liên tiếp → I/O tuần tự, throughput hàng triệu sự kiện/giây trên ổ cứng 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 là một nhóm ứng dụng cùng đọc một topic. Kafka lưu bảng offset riêng cho mỗi group trong internal topic __consumer_offsets. Consumer commit offset sau khi xử lý xong để ghi nhận "tôi đã xử lý tới đây":

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

Ba mức đảm bảo khi consumer bị crash — câu hỏi cốt lõi: nếu ứng dụng chết giữa chừng, mỗi sự kiện được xử lý bao nhiêu lần?

• At-least-once (ít nhất một lần, mặc định): ghi nhớ vị trí đọc sau khi xử lý xong. Nếu consumer chết giữa chừng, lúc khởi động lại nó đọc lại từ vị trí đã ghi nhớ — nên một sự kiện có thể bị xử lý hai lần (trùng). Đây là mặc định vì đơn giản và thường đủ khi việc xử lý là idempotent (chạy nhiều lần cho cùng một kết quả).
• At-most-once (nhiều nhất một lần): ghi nhớ vị trí trước khi xử lý. Nếu chết giữa chừng, sự kiện đó mất luôn, không được xử lý lại. Phù hợp với log hoặc số liệu đo lường không cần chính xác tuyệt đối.
• Exactly-once (đúng một lần): nhờ cơ chế giao dịch của Kafka (Kafka Transactions) — gói việc xử lý và việc ghi nhớ vị trí vào một giao dịch chung với Kafka, để cả hai cùng thành công hoặc cùng huỷ. Chi phí cao hơn nhưng đảm bảo mỗi sự kiện được xử lý đúng một lần: không trùng, không mất.

9. Retention và log compaction

Kafka không lưu sự kiện mãi mãi. Hai chính sách kiểm soát vòng đời sự kiện:

• Giữ theo thời gian — tham số retention.ms (số mili-giây giữ một sự kiện): xoá các phần log cũ hơn ngưỡng đó. Ví dụ đặt retention.ms bằng 7 ngày — phù hợp với luồng sự kiện ngắn hạn như click, lượt xem.
• Dọn theo key (log compaction) — bật bằng cleanup.policy=compact. "Log compaction" nghĩa là dọn bớt bản ghi cũ, chỉ giữ giá trị mới nhất cho mỗi key: với cùng một key, các sự kiện cũ bị xoá, chỉ còn lại bản ghi gần nhất. Phù hợp với luồng cập-nhật-trạng-thái (changelog stream) — nơi mỗi key chỉ cần biết giá trị cuối cùng, ví dụ trạng thái hiện tại của một đơn hàng.

Khi nào chọn HLL, khi nào chọn log append-only?

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 log và external sort cùng khai thác một nguyên lý — đọc/ghi tuần tự (đọc liên tiếp từ đầu tới cuối file) nhanh hơn đọc/ghi ngẫu nhiên (nhảy lung tung) hàng chục lần. File partition của Kafka là một log tuần tự vì cùng lý do external sort chọn trộn các file tuần tự thay vì đọc ngẫu nhiên. Khác biệt nằm ở số lần quét dữ liệu: external sort phải quét nhiều lượt (chia khối rồi trộn nhiều vòng) nên khối lượng I/O tăng theo số vòng trộn, còn Kafka chỉ ghi một lần và đọc một lần nên khối lượng I/O tỉ lệ thẳng với số sự kiện.
• 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óm tắt

• Redis HLL: 12 KB cố định; PFMERGE lấy max từng register → union đúng toán học, không đếm trùng.
• Sparse encoding tiết kiệm bộ nhớ khi key còn mới (ít register khác 0); tự chuyển sang dense 12 KB khi cần.
• Kafka partition = append-only log với offset bất biến; consumer chỉ commit offset, không xoá — nhiều consumer group đọc cùng partition hoàn toàn độc lập.
• Hai chính sách vòng đời: retention.ms (xoá theo thời gian) và log compaction (giữ giá trị mới nhất mỗi key, cleanup.policy=compact) — dùng cho changelog stream trạng thái.

Tự kiểm tra

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