Bitmap và HyperLogLog

Hai kiểu dữ liệu ít dùng nhất của Redis, và cũng là hai kiểu tiết kiệm nhất. Bài này đo cả bộ nhớ lẫn sai số của chúng.

Đếm một triệu phần tử khác nhau: ba cách

HyperLogLog nhỏ hơn Set 3.364 lần.

Bitmap nhỏ hơn Set 35,4 lần — đo trên 951.659 id nằm trong khoảng 0 đến 10 triệu.

Ba con số này giải thích vì sao hai kiểu này tồn tại: chúng trả lời một câu hỏi hẹp hơn, và trả lời rẻ hơn nhiều bậc.

HyperLogLog: bộ nhớ đứng yên

Từ khoảng 10.000 phần tử trở đi, bộ nhớ không tăng nữa. Đếm một triệu hay một tỷ đều 14.384 byte.

Sai số cũng không xấu đi theo số lượng — nó dao động quanh 0,1–0,5% ở mọi mức. Đó là bảo đảm của thuật toán, không phải may mắn.

Dưới 3.000 byte, Redis dùng biểu diễn thưa: 100 phần tử chỉ tốn 432 byte. Vượt hll-sparse-max-bytes (mặc định 3.000) thì nó chuyển sang biểu diễn dày với kích thước cố định.

Và nó nhanh hơn Set khi ghi

PFADD    0,502 µs        SADD    0,812 µs
PFCOUNT  0,172 µs        SCARD   0,144 µs

PFADD nhanh hơn SADD 1,6 lần. Tôi trông đợi ngược lại — băm rồi cập nhật thanh ghi nghe phức tạp hơn là thêm vào bảng băm.

Lý do: PFADD không lưu phần tử. Nó băm giá trị, lấy vài bit đầu chọn thanh ghi, đếm số bit 0 liên tiếp, và chỉ ghi nếu số đó lớn hơn giá trị đang có. Không cấp phát, không mở rộng bảng, không sao chép chuỗi.

SADD phải cấp phát chỗ cho chuỗi, chèn vào bảng băm, và thỉnh thoảng phải mở rộng lại cả bảng.

PFCOUNT cũng gần nhanh bằng SCARD dù nó phải tính từ 16.384 thanh ghi — vì Redis lưu kết quả đã tính và chỉ tính lại khi có thay đổi.

Nghĩa là với bài toán đếm số khác nhau, HyperLogLog thắng cả về bộ nhớ lẫn tốc độ. Cái duy nhất nó không cho là danh sách phần tử và con số chính xác.

Bitmap: cấp phát theo bit cao nhất

bit cao nhất        1.000  ->       208 byte
bit cao nhất    1.000.000  ->   131.120 byte
bit cao nhất   10.000.000  -> 1.310.768 byte

Bộ nhớ phụ thuộc hoàn toàn vào chỉ số bit lớn nhất, không phụ thuộc số bit đã đặt.

SETBIT key 10000000 1 cấp phát ngay 1,3 MB dù bạn chỉ đặt đúng một bit. Đây là cái bẫy chính của bitmap: dùng id người dùng thật làm chỉ số, mà id là số tự tăng đã lên tới 500 triệu, thì một bitmap tốn 62 MB cho dù bạn chỉ theo dõi mười người.

Cách dùng đúng là ánh xạ id thật sang chỉ số liên tục bắt đầu từ 0. Bảng ánh xạ đó cũng tốn bộ nhớ, nên phép tính chỉ có lợi khi tập id dày.

Khi nào dùng cái nào

Bitmap hợp với câu hỏi "người dùng X có làm việc Y hôm nay không":

SETBIT hoat-dong:2026-09-01 12345 1
BITCOUNT hoat-dong:2026-09-01                    # bao nhiêu người
BITOP AND ca-hai hoat-dong:2026-09-01 hoat-dong:2026-08-31

BITOP là chỗ bitmap không thể thay thế: giao, hợp, hiệu giữa các ngày bằng phép toán bit trên hàng megabyte, rất nhanh. Tính "người dùng quay lại trong 7 ngày" là bảy BITOP thay vì bảy phép giao tập hợp.

HyperLogLog hợp với "có bao nhiêu thứ khác nhau" khi bạn không cần biết chúng là gì:

PFADD khach:2026-09-01 user123 user456
PFCOUNT khach:2026-09-01
PFMERGE khach:thang-9 khach:2026-09-01 khach:2026-09-02   # gộp được

PFMERGE là tính chất quan trọng nhất: gộp hai HyperLogLog cho ra ước lượng đúng của hợp hai tập, không phải tổng hai số. Nghĩa là đếm theo ngày rồi gộp thành tháng, không cần lưu gì thêm.

Set khi bạn cần con số chính xác, cần liệt kê, hoặc cần kiểm tra một phần tử cụ thể có trong tập không. HyperLogLog không trả lời được câu hỏi cuối.

Sai số 0,5% có chấp nhận được không

Câu hỏi này phụ thuộc vào việc con số dùng để làm gì.

Với "hôm nay có bao nhiêu khách" hiển thị trên bảng điều khiển, 0,5% là vô hình — không ai phân biệt được 1.001.188 với 1.000.000.

Với hoá đơn tính theo số khách, 0,5% là tiền thật và đi cả hai hướng — đo được cả +0,50% lẫn −0,23%. Trường hợp đó cần Set.

Ranh giới thực dụng: HyperLogLog cho số liệu vận hành, Set cho số liệu ai đó sẽ tranh cãi.

Thử ba mươi giây

So ba cách trên chính dữ liệu của bạn:

# lay 100.000 gia tri that tu mot Set dang co
redis-cli --scan --pattern 'khoa-mau:*' | head -1 | while read k; do
  redis-cli smembers "$k" | head -100000 > /tmp/mau.txt
done

# nap vao HyperLogLog roi so
awk '{print "PFADD thu-hll " $0}' /tmp/mau.txt | redis-cli > /dev/null
echo "chinh xac: $(wc -l < /tmp/mau.txt)"
echo "PFCOUNT  : $(redis-cli pfcount thu-hll)"
echo "bo nho Set: $(redis-cli memory usage <ten-set-cua-ban>)"
echo "bo nho HLL: $(redis-cli memory usage thu-hll)"
redis-cli del thu-hll

Tỷ lệ bộ nhớ thường lớn hơn người ta đoán, và sai số thường nhỏ hơn. Nếu bạn đang lưu Set chỉ để gọi SCARD, đây là chỗ tiết kiệm rẻ nhất trong toàn bộ Redis.

Phần sau: TTL và chính sách đuổi khoá — đo Redis xoá khoá hết hạn lúc nào, và chuyện gì xảy ra khi đầy bộ nhớ.