Bài 26: HyperLogLog — Đếm Unique Xấp Xỉ

• Giải thích được HyperLogLog là gì, trade-off giữa memory cố định và error ~0.81%.
• Dùng được PFADD, PFCOUNT, PFMERGE đúng cách.
• Thiết kế DAU, WAU, MAU bằng HLL với pattern key hợp lý.
• Biết PFADD return value có ý nghĩa gì và khi nào cần đọc giá trị đó.
• Phân biệt sparse encoding và dense encoding của HLL.
• Quyết định được khi nào dùng HLL, khi nào dùng Set hoặc Bitmap thay thế.
• Nhận diện các anti-pattern phổ biến khi dùng HLL trong production.

Bài toán cơ bản: đếm có bao nhiêu user khác nhau truy cập hệ thống trong một ngày (Daily Active Users — DAU). Đơn giản khi tập nhỏ, nhưng phức tạp ở scale lớn.

Với Set, bạn lưu từng user_id vào một key. Đây là cách chính xác nhất, nhưng memory tăng tuyến tính theo số user:

• 1 triệu user unique × ~16 bytes mỗi ID = ~16MB per ngày.
• 10 triệu user × ~16 bytes = ~160MB per ngày.
• 30 ngày × 10 triệu user = ~4.8GB chỉ cho DAU Set.
• Nhân thêm số dimension (endpoint, country, device) thì memory nhân theo.

Bitmap (bài 25) giải được bài toán này với integer ID dense: 10 triệu user chỉ ~1.25MB. Nhưng Bitmap đòi user_id là integer nhỏ gọn, không xử lý được UUID hay string ID.

HyperLogLog giải quyết bài toán theo hướng khác: chấp nhận một sai số nhỏ để đổi lấy memory cố định không phụ thuộc cardinality.

Cardinality	Set memory	HLL memory
1 nghìn	~16KB	~12KB (sparse, ít hơn)
1 triệu	~16MB	~12KB
10 triệu	~160MB	~12KB
1 tỷ	~16GB	~12KB

Trade-off: HLL chỉ trả về ước lượng cardinality (standard error 0.81%), và không cho biết member cụ thể nào đã được thêm — chỉ có con số đếm.

HyperLogLog là một probabilistic data structure để ước lượng cardinality của tập hợp. Được giới thiệu bởi Flajolet et al. trong paper "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" (2007).

Intuition cơ bản (không đi sâu vào toán): khi bạn hash một phần tử ngẫu nhiên, pattern các bit đầu của hash value mang thông tin thống kê về số phần tử trong tập. Cụ thể, nếu bạn quan sát được một chuỗi k bit 0 ở đầu hash, xác suất xảy ra điều đó là 2^−(k+1) — nghĩa là bạn đã xử lý khoảng 2^k+1 phần tử. Bằng cách theo dõi run leading zeros dài nhất qua nhiều sub-register, thuật toán ước lượng được tổng cardinality.

Cài đặt trong Redis:

• 16384 register (2¹⁴), mỗi register 6 bit.
• Tổng memory: 16384 × 6 bit = 12KB (dense encoding).
• Standard error: 1.04 / √16384 ≈ 0.81%.
• Prefix PF trong tên lệnh là tribute cho Philippe Flajolet, tác giả paper gốc.

Về mặt người dùng, HLL trong Redis hoạt động giống Set về interface (add, count, merge) nhưng không lưu member thực tế — chỉ cập nhật nội bộ 16384 register.

PFADD — thêm element

PFADD visitors:2026-05-28 "user:1" "user:2" "user:3"
# (integer) 1  — cardinality estimate đã thay đổi

PFADD visitors:2026-05-28 "user:1"
# (integer) 0  — estimate không đổi (user:1 đã được thêm trước)

PFADD nhận một hoặc nhiều element trong cùng lệnh. Return 1 nếu cardinality estimate thay đổi, 0 nếu không (chi tiết ở mục 8).

PFCOUNT — lấy ước lượng unique

PFCOUNT visitors:2026-05-28
# (integer) 3

# PFCOUNT có thể nhận nhiều key — tương đương merge tạm thời rồi đếm
PFCOUNT visitors:2026-05-27 visitors:2026-05-28
# trả về unique của union hai ngày

Khi PFCOUNT nhận nhiều key, Redis merge các HLL đó tạm thời để tính union cardinality. Merge này không ghi lại, không tạo key mới.

PFMERGE — merge nhiều HLL thành một

# Merge 7 ngày thành HLL tuần
PFMERGE visitors:week:2026-W22 \
  visitors:2026-05-26 \
  visitors:2026-05-27 \
  visitors:2026-05-28 \
  visitors:2026-05-29 \
  visitors:2026-05-30 \
  visitors:2026-05-31 \
  visitors:2026-06-01

PFCOUNT visitors:week:2026-W22
# unique visitors cả tuần, không double-count

PFMERGE destination source [source ...] ghi kết quả vào destination. Nếu destination đã tồn tại, các source được merge vào nó. Cardinality của destination sẽ ≥ cardinality lớn nhất trong các source (đặc tính union).

Complexity

• PFADD: O(1).
• PFCOUNT với 1 key: O(1) nếu cached; O(N) lần đầu hoặc khi HLL dirty.
• PFCOUNT với N key: O(N).
• PFMERGE với N source: O(N).

Đây là use case phổ biến nhất của HLL. Mỗi khi user có action (login, page view, API call), ghi vào HLL của ngày hôm đó:

# Mỗi khi user_id có action trong ngày
PFADD dau:2026-05-28 user_id

# Cuối ngày hoặc bất kỳ lúc nào cần số liệu
PFCOUNT dau:2026-05-28

Memory luôn cố định ~12KB per ngày, bất kể 1 nghìn hay 10 triệu user. Lưu 365 ngày × 12KB = 4.4MB, so với Set có thể lên hàng chục GB.

PFADD idempotent theo nghĩa thống kê: add cùng một user nhiều lần không làm tăng cardinality estimate. HLL không lưu member, nhưng nội bộ xử lý đủ để duplicate không làm lệch kết quả đếm.

Phân tách theo dimension: nếu cần DAU per platform:

PFADD dau:2026-05-28:ios user_id
PFADD dau:2026-05-28:android user_id
PFADD dau:2026-05-28:web user_id

PFCOUNT dau:2026-05-28:ios
PFCOUNT dau:2026-05-28:android
# Union tất cả platform (không double-count user dùng nhiều platform)
PFCOUNT dau:2026-05-28:ios dau:2026-05-28:android dau:2026-05-28:web

Để có Weekly Active Users (WAU) hoặc Monthly Active Users (MAU) mà không double-count user xuất hiện nhiều ngày:

# Merge 7 ngày thành WAU
PFMERGE wau:2026-W22 \
  dau:2026-05-26 dau:2026-05-27 dau:2026-05-28 \
  dau:2026-05-29 dau:2026-05-30 dau:2026-05-31 dau:2026-06-01

PFCOUNT wau:2026-W22
# => unique user cả tuần (không cộng trùng)

# Tương tự cho MAU — merge 30 ngày
PFMERGE mau:2026-05 \
  dau:2026-05-01 dau:2026-05-02 ... dau:2026-05-31

PFCOUNT mau:2026-05

Điểm quan trọng: PFMERGE tính union. User active 5 ngày trong tuần chỉ được đếm 1 lần trong WAU. Đây là điều mà việc cộng đơn giản DAU1 + DAU2 + ... + DAU7 không làm được.

Nếu muốn biết số user active ít nhất N ngày (retention), HLL không làm được — đó là bài toán của Bitmap với BITOP AND (đã cover ở bài 25). HLL chỉ cho union cardinality.

HLL đặc biệt phù hợp khi bạn cần đếm unique theo nhiều dimension — vì mỗi dimension chỉ tốn 12KB thay vì Set có thể vài chục MB.

Unique IP per endpoint

# Mỗi request đến /api/products
PFADD ips:endpoint:/api/products "192.168.1.1"
PFADD ips:endpoint:/api/products "10.0.0.5"

PFCOUNT ips:endpoint:/api/products
# unique IP gọi endpoint này

Unique search term

PFADD unique-searches:2026-05-28 "redis hyperloglog"
PFADD unique-searches:2026-05-28 "cách dùng pfadd"

PFCOUNT unique-searches:2026-05-28

Unique product viewed per category

PFADD viewed-products:category:electronics product_id
PFCOUNT viewed-products:category:electronics

Khi có 1000 endpoint × 30 ngày, dùng Set sẽ ngốn nhiều GB; dùng HLL chỉ tốn 1000 × 30 × 12KB = 360MB tệ nhất — thực tế còn ít hơn vì sparse encoding khi cardinality nhỏ.

PFADD trả về integer:

• 1: cardinality estimate đã thay đổi sau khi thêm element. Tức là có ít nhất một element mới về mặt thống kê.
• 0: cardinality estimate không đổi. Element đã có (hoặc hash pattern không làm thay đổi bất kỳ register nào).

PFADD session-events:session:abc "page_view"
# (integer) 1 — first event of this session

PFADD session-events:session:abc "page_view"
# (integer) 0 — duplicate, estimate không đổi

Cảnh báo về "first seen": return 1 không chắc chắn là element thực sự mới với HLL. Do probabilistic nature, một element cũ đôi khi không làm thay đổi register và PFADD trả 0 ngay lần đầu (hiếm nhưng có thể). Ngược lại, return 1 có thể xảy ra khi estimate tăng do tích lũy nhiều element hash vào cùng bucket. Nếu cần xác định chính xác "đây có phải lần đầu user này xuất hiện không", dùng Set với SISMEMBER + SADD.

Dùng thực tế: return value của PFADD ít được dùng trong production DAU/WAU. Nó hữu ích hơn trong các use case muốn giảm số lệnh pipeline — chỉ gọi PFCOUNT khi PFADD vừa trả 1 (có thay đổi).

Redis HLL có standard error 0.81%. Đây là sai số lý thuyết trên phân phối thống kê — trên thực tế phần lớn lần đo sẽ nằm trong khoảng đó, nhưng có thể lệch hơn trong những trường hợp xui:

Cardinality thực	Khoảng ước lượng (±0.81%)
10,000	9,919 – 10,081
100,000	99,190 – 100,810
1,000,000	991,900 – 1,008,100
10,000,000	9,919,000 – 10,081,000

Với DAU analytics, sai số ±8,100 trên 1 triệu user (±0.81%) là hoàn toàn chấp nhận được. Nhưng trong các ngữ cảnh cần exact count — ví dụ tính số API call của một customer để lập hóa đơn, hoặc kiểm tra quota — sai số đó có thể gây ra vấn đề pháp lý hay tài chính.

Error không phụ thuộc cardinality: sai số 0.81% áp dụng cho cả 1 nghìn lẫn 1 tỷ phần tử. Đây là ưu điểm so với naive sampling.

Redis không lập tức cấp phát đủ 12KB cho mọi HLL. Bên trong có hai chế độ encoding:

Sparse encoding

Khi HLL mới tạo hoặc còn ít element, Redis dùng sparse representation — chỉ lưu các register khác 0 theo định dạng nén. Memory thực tế nhỏ hơn 12KB đáng kể ở giai đoạn đầu.

• Tiết kiệm memory khi dimension nhiều nhưng traffic mỗi dimension thấp.
• Redis tự quyết định khi nào chuyển: mặc định khi sparse representation vượt quá hll-sparse-max-bytes (default 3000 bytes trong Redis config).

Dense encoding

Khi HLL có đủ nhiều element, Redis chuyển sang dense representation: full 16384 register × 6 bit = 12KB. Chuyển đổi xảy ra tự động, không cần can thiệp.

• Một khi chuyển sang dense, không quay lại sparse — kể cả khi bạn DEL và tạo lại từ ít element.
• 12KB là ceiling không đổi cho mọi HLL ở dense mode.

Kiểm tra encoding của một HLL:

OBJECT ENCODING dau:2026-05-28
# "raw" — bất kể sparse hay dense, Redis báo "raw" vì HLL là String dưới dạng raw bytes
# Để biết sparse hay dense, dùng DEBUG OBJECT hoặc kiểm tra memory usage

MEMORY USAGE dau:2026-05-28
# Nếu nhỏ (< 3000): sparse
# Nếu ~12KB: dense

Tiêu chí	Set	Bitmap	HyperLogLog
Memory (10M unique)	~160MB	~1.25MB (dense int ID)	~12KB
Độ chính xác	Exact	Exact	~0.81% error
Biết member cụ thể	Có (SMEMBERS)	Có (offset)	Không
Kiểu ID	Bất kỳ (string, UUID)	Dense integer (0 đến N)	Bất kỳ (hash nội bộ)
Kiểm tra membership	SISMEMBER	GETBIT	Không
Retention (AND)	SINTERSTORE	BITOP AND	Không
Union count	SUNION	BITOP OR + BITCOUNT	PFMERGE + PFCOUNT
Scale cardinality lớn	Tốn memory	Tốt (integer ID)	Tốt nhất

Tóm gọn quy tắc chọn:

• Set: cần biết member nào, cần intersection/difference, cardinality không quá lớn, ID bất kỳ.
• Bitmap: ID là integer dense, cần exact count, cần retention (AND), memory quan trọng.
• HLL: chỉ cần count, cardinality lớn, memory critical, ID bất kỳ, chấp nhận ~1% error.

Dùng HLL khi

• Cần đếm unique count và cardinality dự kiến lớn (> 100k thường là ngưỡng có lợi).
• Có nhiều dimension: nhiều endpoint, nhiều ngày, nhiều country — memory nhân với số key.
• ID không phải integer dense (UUID, email, composite key).
• Chấp nhận sai số ~1% — dashboard analytics, reporting, monitoring.
• Cần union cardinality qua nhiều tập (PFMERGE) mà không double-count.

Không dùng HLL khi

• Cần exact count: billing theo API call, quota enforcement, compliance reporting — error 0.81% gây sai số tài chính.
• Cardinality nhỏ (< 1000): Set vừa chính xác vừa đủ rẻ (~16KB), không cần probabilistic.
• Cần biết member cụ thể: "user nào đã xem sản phẩm này?" — HLL không lưu member, phải dùng Set.
• Cần kiểm tra membership: "user này đã active hôm nay chưa?" — HLL không có lệnh tương đương SISMEMBER hay GETBIT.
• Cần retention analytics: "bao nhiêu user active cả thứ 2 lẫn thứ 3?" — cần intersection, HLL chỉ có union.

Dùng HLL cho billing / exact count

Hệ thống tính tiền theo số API call của customer dùng HLL để đếm. Với 1 triệu call, sai số ±8100 call — có thể tính thiếu hoặc thừa. Dùng counter chính xác (INCR, database, stream) cho billing.

PFCOUNT realtime per request trên nhiều key

Mỗi HTTP request gọi PFCOUNT trên 30 key (30 ngày WAU). PFCOUNT với nhiều key là O(N), và kết quả chỉ thay đổi khi có PFADD mới. Giải pháp: cache kết quả PFCOUNT vào key riêng với TTL ngắn (30–60 giây), chỉ tính lại định kỳ.

# Thay vì mỗi request đều gọi
PFCOUNT dau:d1 dau:d2 ... dau:d30

# Cache kết quả
PFMERGE wau:cached dau:d1 dau:d2 ... dau:d30
SET wau:cached:count (PFCOUNT wau:cached) EX 60

Dùng HLL cho cardinality nhỏ

HLL nhỏ hơn 12KB nhờ sparse encoding, nhưng Set với 500 member cũng chỉ ~8–10KB — và cho biết chính xác ai trong đó. Nếu cardinality nhỏ và cần exact, Set rõ ràng hơn.

Kỳ vọng xóa được member cụ thể

HLL không có lệnh xóa một element. Một khi thêm vào, không thể undo. Nếu cần rollback (ví dụ bị phát hiện bot traffic), cần rebuild HLL từ nguồn clean. Thiết kế data pipeline có lưu raw event để có thể rebuild khi cần.

Không đặt TTL cho HLL daily

Key dau:2026-05-28 không cần giữ mãi. Sau khi đã merge vào WAU/MAU, set TTL để tự cleanup:

EXPIRE dau:2026-05-28 2592000  # 30 ngày

import redis
from datetime import date, timedelta

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

# --- DAU: thêm user active ---
today = date.today().isoformat()  # "2026-05-28"
dau_key = f"dau:{today}"

user_ids = ["user:1001", "user:1002", "user:1003", "user:1001"]  # user:1001 trùng
r.pfadd(dau_key, *user_ids)

dau_count = r.pfcount(dau_key)
print(f"DAU {today}: {dau_count}")  # 3 (không phải 4)

r.expire(dau_key, 30 * 24 * 3600)  # TTL 30 ngày

# --- PFADD return value ---
# Thêm user mới
changed = r.pfadd(dau_key, "user:9999")
print(f"Changed: {changed}")  # 1

# Thêm lại user đã có
changed = r.pfadd(dau_key, "user:9999")
print(f"Changed: {changed}")  # 0 (thường là 0, không đảm bảo 100%)

# --- WAU: merge 7 ngày ---
week_key = "wau:2026-W22"
daily_keys = []
start = date(2026, 5, 26)
for i in range(7):
    day = start + timedelta(days=i)
    key = f"dau:{day.isoformat()}"
    daily_keys.append(key)

r.pfmerge(week_key, *daily_keys)
wau_count = r.pfcount(week_key)
print(f"WAU 2026-W22: {wau_count}")

r.expire(week_key, 90 * 24 * 3600)  # TTL 90 ngày

# --- Unique per dimension ---
r.pfadd("ips:endpoint:/api/v1/products", "192.168.1.1", "10.0.0.5", "192.168.1.1")
unique_ips = r.pfcount("ips:endpoint:/api/v1/products")
print(f"Unique IPs: {unique_ips}")  # 2

# --- Pipeline để tăng throughput ---
pipe = r.pipeline()
for uid in range(10_000):
    pipe.pfadd(f"dau:{today}", f"user:{uid}")
pipe.execute()
print(f"DAU sau 10k users: {r.pfcount(dau_key)}")

Dùng pipeline (r.pipeline()) khi cần thêm nhiều element cùng lúc để giảm round-trip latency. Mỗi PFADD trong pipeline là độc lập — không cần transaction.

HyperLogLog là data structure phù hợp cho bài toán đếm unique cardinality lớn với memory cố định. Ba điểm cốt lõi:

• Memory ~12KB bất kể cardinality — không phụ thuộc số phần tử.
• Standard error 0.81% — phù hợp analytics, không phù hợp exact/billing.
• Không lưu member — chỉ có count, không có membership check hay intersection.

Module 8 sẽ đi sâu hơn vào HLL cùng với Count-Min Sketch, Top-K và so sánh trade-off giữa các probabilistic structure cho analytics workload. Bài này dừng ở mức data structure và use case.

Quiz

1. Tại sao PFCOUNT key1 key2 key3 không double-count user xuất hiện trong nhiều key?
2. Bạn cần biết user nào đã xem sản phẩm A. HLL có dùng được không? Nếu không, dùng gì?
3. Cardinality thực là 500,000. Với standard error 0.81%, khoảng ước lượng là bao nhiêu?
4. Khi nào HLL dùng sparse encoding thay vì dense? Điều đó ảnh hưởng gì đến memory?
5. Tại sao không dùng HLL để tính quota API của customer và charge tiền?

Đáp án gợi ý

1. PFCOUNT với nhiều key thực hiện merge tạm thời (tương đương PFMERGE in-memory không ghi) rồi tính cardinality của union. Union của các tập đã tự xử lý trùng lặp — phần tử xuất hiện trong nhiều key chỉ được đếm một lần trong union.
2. Không. HLL không lưu member, không có lệnh tương đương SMEMBERS hay SISMEMBER. Dùng Set: SADD product:A:viewers user_id rồi SMEMBERS hoặc SISMEMBER.
3. ±0.81% của 500,000 = ±4,050. Khoảng ước lượng: 495,950 – 504,050.
4. Khi HLL mới tạo và ít element, Redis dùng sparse encoding (chỉ lưu register khác 0 dạng nén). Memory nhỏ hơn 12KB. Khi số byte sparse vượt hll-sparse-max-bytes (default 3000 bytes), Redis tự chuyển sang dense encoding (full 12KB). Với nhiều key HLL nhỏ (traffic thấp per dimension), sparse tiết kiệm đáng kể tổng memory.
5. Sai số 0.81% trên 1 triệu call = ±8,100 call. Nếu mỗi call tính tiền $0.001, sai số là ±$8.1 per million — không chấp nhận được về pháp lý và tài chính. Dùng exact counter (INCR trong Redis, hoặc counter trong database) cho billing.

Bài tiếp theo

Bài 27 giới thiệu GEO commands — lưu tọa độ địa lý và tìm kiếm "nearby" (tìm địa điểm trong bán kính).

Tham khảo

• Redis Docs — HyperLogLog
• Redis Docs — PFADD
• Redis Docs — PFCOUNT
• Redis Docs — PFMERGE
• redis-py — Redis client cho Python
• Flajolet et al. 2007 — HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm