HyperLogLog và Bitmaps: Đếm unique không tốn bộ nhớ

Bạn có biết?

Đếm số user hoạt động hôm nay (DAU) cho 10 triệu user — nếu lưu cả 10 triệu ID vào Set, bạn tốn hàng trăm MB RAM. Nhưng với HyperLogLog, cùng con số đó chỉ tốn 12KB — gấp 10.000 lần tiết kiệm hơn. Còn Bitmaps thì theo dõi trạng thái 10 triệu user chỉ với ~1.2MB. Đây là hai "vũ khí bí mật" của Redis cho bài toán đếm và theo dõi ở quy mô lớn.

HyperLogLog: đếm unique với sai số chấp nhận được

HyperLogLog (HLL) là thuật toán xác suất ước lượng số phần tử duy nhất trong một tập dữ liệu khổng lồ, với:

• Bộ nhớ cố định ~12KB — không đổi dù đếm 1 nghìn hay 1 tỷ phần tử
• Sai số ~0.81% — đủ chính xác cho hầu hết bài toán analytics
• O(1) mỗi thao tác — PFADD và PFCOUNT cực nhanh

# Ghi nhận user truy cập (trùng lặp không sao — HLL tự loại)
PFADD stats:2026-08-01:visitors user_1001 user_1002 user_1001 user_1003

# Đếm số user duy nhất hôm nay
PFCOUNT stats:2026-08-01:visitors
# (integer) 3

# Gộp nhiều ngày để tính tuần / tháng
PFMERGE stats:week-32:visitors stats:2026-08-01:visitors stats:2026-08-02:visitors
PFCOUNT stats:week-32:visitors

Quy ước đặt tên stats:<kỳ>:<metric> giúp bạn tổng hợp DAU → WAU → MAU chỉ bằng PFMERGE — không cần quét lại dữ liệu thô.

Bitmaps: theo dõi trạng thái từng user

Bitmap là một string, nhưng mỗi bit (0/1) đại diện một trạng thái. Với 10 triệu user, bạn chỉ cần 10 triệu bit ≈ 1.25MB — và có thể đánh dấu "user X online/offline", "user X đã dùng tính năng Y" chỉ bằng một lệnh.

Cấu trúc	10 triệu user	Ưu điểm	Nhược điểm
Set	~300-500MB	Lấy được danh sách thật	Tốn bộ nhớ
HyperLogLog	12KB	Cực rẻ, PFMERGE gộp kỳ	Chỉ ước lượng, không lấy được danh sách
Bitmap	~1.25MB	Rẻ, BITOP phân tích điều kiện	User id phải là số nhỏ (offset)

# User_id = offset của bit. Đánh dấu user 1001 đã online hôm nay
SETBIT online:2026-08-01 1001 1
SETBIT online:2026-08-01 1002 1

# User 1001 có online không?
GETBIT online:2026-08-01 1001
# (integer) 1

# Tổng số user online hôm nay
BITCOUNT online:2026-08-01
# (integer) 2

# User online CẢ hai ngày (AND) / ít nhất một ngày (OR)
BITOP AND online:both online:2026-08-01 online:2026-08-02
BITOP OR  online:any  online:2026-08-01 online:2026-08-02
BITCOUNT online:any

Với BITOP, bạn tính được cả lớp bài toán "user thỏa mãn nhiều điều kiện" — dùng tính năng A và B, online cả tuần — bằng phép toán bit, nhanh hơn hàng triệu lần so với query database.

• Cần con số chính xác tuyệt đối → Set (hoặc database)
• Cần danh sách user thật (vd "100 user mới nhất") → Set
• Chỉ cần con số ước lượng, quy mô lớn (DAU/MAU, unique visitors) → HyperLogLog
• User id là số, cần track trạng thái + phép giao/hợp → Bitmap

Mẹo kết hợp: dùng HyperLogLog cho số liệu thô và Bitmap cho phân tích điều kiện; Set chỉ cho các tập nhỏ cần liệt kê.

import Redis from "ioredis";
const redis = new Redis();

// Middleware: ghi nhận user truy cập (HLL) + online (bitmap)
async function trackVisit(userId, date = "2026-08-01") {
  await redis.pfadd(`stats:${date}:visitors`, String(userId));
  await redis.setbit(`online:${date}`, userId, 1);
}

// Báo cáo DAU
const dau = await redis.pfcount("stats:2026-08-01:visitors");

// User dùng cả tính năng A và B hôm nay (bitmap)
await redis.bitop("AND", "feature:ab", "feature:a:0801", "feature:b:0801");
const bothCount = await redis.bitcount("feature:ab");

// WAU: gộp 7 ngày
const weekKeys = ["stats:2026-07-26:visitors", "stats:2026-07-27:visitors", "stats:2026-07-28:visitors", "stats:2026-07-29:visitors", "stats:2026-07-30:visitors", "stats:2026-07-31:visitors", "stats:2026-08-01:visitors"];
await redis.(, ...weekKeys);
 wau =  redis.();

• HLL sai số ~0.81% — với 10 triệu user, kết quả có thể lệch ±80.000. Chấp nhận được cho analytics, không chấp nhận cho thanh toán
• Bitmap yêu cầu user id số nhỏ — offset tối đa 2^32; id dạng UUID không dùng được, phải map sang index
• PFADD thêm trùng không sao — HLL tự dedup, cứ gọi thoải mái
• BITCOUNT trên bitmap lớn — O(N) theo kích thước; với 10 triệu user vẫn chỉ vài ms
• Đặt TTL cho key theo kỳ — stats cũ nên tự xóa sau 30-90 ngày để tiết kiệm bộ nhớ

HyperLogLog và Bitmap là hai công cụ không thể thiếu cho hệ thống analytics quy mô lớn: HLL đếm unique với 12KB bất chấp số lượng, Bitmap track trạng thái hàng triệu user với phép toán bit siêu tốc. Biết chọn đúng cấu trúc, bạn tiết kiệm được hàng trăm MB RAM và hàng triệu query mỗi ngày.

Bước tiếp theo: kết hợp với Sets để hiểu khi nào cần danh sách thật, hoặc xem Redis Monitoring để theo dõi bộ nhớ và hiệu năng.