Bloom filter là cấu trúc xác suất trả lời phần tử có thể có trong tập hay chắc chắn không — chỉ bằng một mảng bit và k hàm băm, không lưu phần tử. Đo thật khi tự cài trong Go: 1 triệu phần tử, 0 âm tính giả, dương tính giả đúng 1% như thiết kế, và bộ nhớ 1.20 MB so với 56.1 MB của set thường.
Cần kiểm tra một phần tử có trong tập triệu phần tử không, mà không muốn tốn hàng chục MB? Bloom filter làm được bằng một mảng bit và vài hàm băm. Bài này tự cài Bloom và đo thật: thay 57MB set bằng 1.25MB (nhỏ hơn 46 lần), tỉ lệ báo nhầm thực tế 0.83% khớp gần như hoàn hảo công thức lý thuyết 0.82%, và không bao giờ báo sót. Cơ chế, công thức, và khi nào dùng.
Bloom filter chỉ tốt khi bạn cấp đúng số bit và đúng số hàm băm. Bài này đo thật: quét k từ 1 tới 15 cho thấy có một k tối ưu (7) cho tỉ lệ báo nhầm thấp nhất, nhiều hơn lại tệ hơn; công thức m = -n·ln(p)/(ln2)² cho đúng số bit để đạt 1%, 0.1%, 0.01%; và cái bẫy chết người — nhồi gấp đôi số phần tử dự kiến làm báo nhầm nhảy từ 0.8% lên 13.8%.
Bloom filter thường không xóa được — tắt bit sẽ phá phần tử khác. Counting Bloom thay mỗi bit bằng một bộ đếm nhỏ để hỗ trợ xóa. Bài này tự cài và đo thật: xóa 'bob' làm nó biến mất mà 'alice' vẫn còn nguyên; nhưng cái giá là tốn 4 lần bộ nhớ, có rủi ro tràn bộ đếm, và xóa phần tử chưa từng thêm có thể sinh báo sót. Cơ chế và khi nào đáng dùng.
Đếm 'bao nhiêu user duy nhất' hay 'bao nhiêu IP khác nhau' bằng set thì tốn RAM tỉ lệ số phần tử. HyperLogLog đếm số phần tử phân biệt bằng bộ nhớ CỐ ĐỊNH — bất kể 10 nghìn hay 1 triệu, vẫn 16KB. Bài này tự cài HLL và đo thật: đếm 1 triệu phần tử sai chỉ 1.06%, nhỏ hơn set 3479 lần. Trực giác về số 0 dẫn đầu, cơ chế register, và vì sao Redis dùng nó.
Ý tưởng HyperLogLog đẹp, nhưng công thức thô không chạy được. Bài này đo thật ba hiệu chỉnh biến nó thành thuật toán thật: trung bình điều hòa thay trung bình thường (sai số 1% thay vì 150% vì giảm ảnh hưởng ngoại lai), hằng số alpha bù thiên lệch, và linear counting cho cardinality nhỏ (thiếu nó sai tới 2900% ở tập nhỏ). Đây chính là những gì HyperLogLog++ của Google hoàn thiện.