Đếm một triệu phần tử khác nhau bằng 14.384 byte với sai số 0,12% — và HyperLogLog còn ghi nhanh hơn Set 1,6 lần vì nó không lưu phần tử nào

Muốn biết có bao nhiêu người khác nhau đã bước qua một hội trường suốt cả ngày, cách hiển nhiên là ghi tên từng người vào sổ rồi đếm — chính xác, nhưng cuốn sổ phình to theo từng khách. Có một mẹo lạ: thay vì giữ danh sách, bạn chỉ ghi lại "dấu vết hiếm nhất" từng thấy — kiểu như chuỗi số 0 dài nhất ở đầu một mã băm ngẫu nhiên — và từ độ hiếm đó ước lượng ngược ra quy mô đám đông, vì càng đông người thì càng dễ gặp một trường hợp cực hiếm. Bạn không biết họ là ai, không đếm chính xác, nhưng đổi lại chỉ tốn một mẩu giấy cố định dù đám đông là nghìn hay tỷ. HyperLogLog của Redis đúng là cái mẹo ấy, và bài này đo hai kiểu dữ liệu ít dùng nhưng tiết kiệm nhất của Redis.

Đế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ó — đúng cái "chỉ giữ dấu vết hiếm nhất". 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.

Mẫu số chung: cấu trúc chuyên biệt trả lời một câu hỏi hẹp rẻ hơn nhiều bậc

Cái làm HyperLogLog thắng cả bộ nhớ lẫn tốc độ là một quy luật chung: một cấu trúc dữ liệu xác suất trả lời đúng một câu hỏi hẹp ("có bao nhiêu thứ khác nhau", "phần tử này có thể đã thấy chưa") với bộ nhớ cố định và sai số bị chặn, rẻ hơn nhiều bậc so với một cấu trúc tổng quát giữ đủ mọi phần tử để trả lời được mọi câu hỏi. Đổi lại, nó vứt bỏ khả năng liệt kê và con số chính xác — và ở quy mô lớn, đó gần như luôn là đánh đổi đúng cho số liệu vận hành.

Trong thế giới Java, đây đúng là HyperLogLog và BloomFilter của Guava: Bloom filter trả lời "chắc chắn không / có thể có" bằng vài bit mỗi phần tử thay vì giữ cả HashSet, và roaring bitmap nén tập số nguyên thưa — cùng tinh thần "chọn cấu trúc theo đúng câu hỏi bạn hỏi". Còn ở cơ sở dữ liệu, đây là approx_count_distinct / HLL của PostgreSQL, BigQuery, ClickHouse: đếm số khác nhau trên hàng tỷ dòng bằng vài KB thay vì một phép COUNT(DISTINCT) quét và giữ toàn bộ.

Mẫu số chung: một cấu trúc chuyên biệt trả lời một câu hỏi hẹp với bộ nhớ cố định và sai số bị chặn thắng một cấu trúc tổng quát nhiều bậc — miễn là bạn thật sự chỉ cần câu hỏi hẹp đó. Câu hỏi đúng không phải "cấu trúc nào lưu dữ liệu này" mà là "tôi thật sự cần trả lời câu hỏi gì — đếm, kiểm tra thành viên, hay liệt kê — và nếu chỉ cần một trong số đó thì có cấu trúc nào bỏ hết phần còn lại để đổi lấy chi phí nhỏ hơn không". Nếu bạn đang giữ một Set chỉ để gọi SCARD, bạn đang trả cho một khả năng mình không dùng.

Muốn tự 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ớ.