Count-Min Sketch: Ước lượng tần suất với bộ nhớ nhỏ

Nếu một luồng có hàng tỷ sự kiện và hàng triệu key, lưu bộ đếm chính xác cho mọi key có thể vượt quá ngân sách RAM. Count-Min Sketch (CMS) nén bài toán thành một ma trận counter có kích thước cố định. Mỗi lần key xuất hiện, nhiều hàm hash chọn một ô ở mỗi hàng; khi truy vấn, giá trị nhỏ nhất trong các ô đó trở thành ước lượng.

Đổi lại cho bộ nhớ nhỏ và cập nhật nhanh, CMS chấp nhận va chạm hash và sai số có kiểm soát. Đây là cấu trúc phù hợp để ước lượng tần suất request, event, query hoặc item trên stream—không phải bảng đếm chính xác, không tự liệt kê heavy hitter và không thay thế cơ chế lưu dữ liệu gốc.

1. Bài toán frequency estimation

Cho stream gồm các cập nhật (key, weight). Với mô hình insert-only, weight không âm và tần suất thật của key x là tổng weight của mọi cập nhật dành cho x. Một hash map chính xác cần số entry tăng theo số key phân biệt. CMS giữ kích thước độc lập với số key, do đó hữu ích khi cardinality rất lớn hoặc chưa biết trước.

2. Cấu trúc ma trận width × depth

CMS có d hàng và w cột. Mỗi hàng dùng một hàm hash độc lập hᵢ ánh xạ key vào một cột. Mọi counter ban đầu bằng 0.

update(x, amount):
  for row in 0 .. d-1:
    column = hash[row](x) mod w
    counter[row][column] += amount

estimate(x):
  answer = infinity
  for row in 0 .. d-1:
    column = hash[row](x) mod w
    answer = min(answer, counter[row][column])
  return answer

Mỗi update và query cần d phép hash/counter. Bộ nhớ là w × d counter, không phụ thuộc trực tiếp vào kích thước universe.

3. Vì sao lấy giá trị nhỏ nhất?

Counter của x có thể nhận thêm đóng góp từ key khác cùng hash vào một ô. Trong stream chỉ có update không âm, va chạm chỉ làm counter tăng, không làm nó thấp hơn tần suất thật. Mỗi hàng tạo một mức nhiễu khác nhau; lấy giá trị nhỏ nhất chọn hàng ít nhiễu nhất trong số đã quan sát.

Với counter không overflow và implementation đúng:

• Ước lượng không thấp hơn tần suất thật trong mô hình insert-only.
• Va chạm có thể làm ước lượng cao hơn.
• Tăng width giảm lượng va chạm trong mỗi hàng.
• Tăng depth giảm xác suất mọi hàng cùng bị nhiễu lớn.

Tên “Count-Min” đến từ việc giữ nhiều count rồi lấy minimum; “minimum” không có nghĩa kết quả là lower bound.

4. Cam kết sai số chuẩn

Với lựa chọn thường gặp w = ceil(e/ε) và d = ceil(ln(1/δ)), ước lượng của một key trong mô hình cập nhật không âm thỏa:

true_frequency(x) ≤ estimate(x) ≤ true_frequency(x) + εN

với xác suất ít nhất 1 - δ, trong đó N là tổng weight của stream. Các giả định về họ hash và mô hình update phải khớp với chứng minh của implementation.

Đây là sai số cộng theo tổng stream, không phải “sai số ε phần trăm của từng key”. Nếu N = 1.000.000 và ε = 0,001, biên cộng là 1.000. Với key thật có count 200.000, biên đó có thể hữu ích; với key thật count 2, nó quá rộng.

5. Ví dụ sizing

Giả sử cần ε = 0,001 và δ = 10⁻⁶:

• w = ceil(e / 0,001) = 2.719.
• d = ceil(ln(1.000.000)) = 14.
• Số counter: 2.719 × 14 = 38.066.
• Counter 32-bit cần khoảng 152.264 byte, xấp xỉ 149 KiB, chưa tính metadata.

Không chọn 32-bit chỉ vì nó nhỏ. Với tốc độ cao hoặc weight lớn, counter có thể overflow. Hãy tính giá trị tối đa trong vòng đời sketch, dùng counter 64-bit hoặc saturation policy phù hợp và tạo cảnh báo trước ngưỡng.

6. Một ví dụ va chạm nhỏ

Giả sử key A xuất hiện 10 lần. Ở ba hàng, counter tương ứng lần lượt là 14, 10 và 17 vì A va chạm với key khác ở hàng 1 và 3. Query trả min(14,10,17)=10. Nếu A va chạm ở cả ba hàng, ước lượng sẽ cao hơn 10; depth làm trường hợp nhiễu đồng thời này ít có khả năng hơn.

CMS không lưu danh sách key trong ô. Từ ma trận, không thể đảo ngược để biết những key nào đóng góp vào một counter.

7. CMS không tự tìm heavy hitter

API cốt lõi trả lời “ước lượng của key X là bao nhiêu?”. Nó không thể duyệt mọi key nếu không lưu chúng. Muốn tìm top-k/heavy hitter, hệ thống cần thêm candidate set, heap hoặc thuật toán chuyên dụng như Misra–Gries/Space-Saving/Frequent Items Sketch.

Một pattern là đưa key vào candidate set khi ước lượng vượt threshold rồi xác minh hoặc xếp hạng các candidate. Nhưng threshold, eviction và bộ nhớ candidate phải được thiết kế; không nên gọi ma trận CMS là một top-k index hoàn chỉnh.

8. So sánh với các sketch dễ nhầm

Không chọn sketch chỉ vì cùng “xấp xỉ”. Hãy bắt đầu từ query cần trả lời và loại error mà nghiệp vụ chấp nhận.

9. Weighted update và update âm

CMS hỗ trợ weight nguyên không âm một cách tự nhiên: cộng cùng weight vào một ô ở mỗi hàng. Ví dụ có thể ước lượng số byte theo endpoint thay vì số request.

Update âm phức tạp hơn. Khi counter giảm, tính chất “không bao giờ underestimate” không còn tự động giữ nguyên. Mô hình turnstile, strict-turnstile và các biến thể CMS có giả định khác nhau. Không bật delete bằng cách truyền số âm vào implementation insert-only mà vẫn quảng bá guarantee cũ.

10. Conservative update

Conservative update là heuristic phổ biến: thay vì tăng mọi counter của key, chỉ tăng các counter đang ở mức minimum cần thiết. Nó thường giảm overestimate trên dữ liệu thực tế, nhưng thay đổi update semantics và có thể ảnh hưởng khả năng merge/guarantee của thư viện.

Nếu cần conservative update, dùng implementation có tài liệu rõ và kiểm thử merge, weighted update cùng error bound. Không tự pha trộn sketch chuẩn và sketch conservative trong cùng pipeline.

11. Merge trong hệ phân tán

CMS tuyến tính cơ bản có thể merge bằng cách cộng từng counter tương ứng, rất tiện cho shard hoặc time bucket. Chỉ merge khi các sketch tương thích hoàn toàn:

• Cùng width, depth và kiểu counter.
• Cùng thuật toán hash, seed cho từng hàng và serialization key.
• Cùng update model và interpretation của weight.
• Cùng version format và overflow policy.

Sau merge, tổng stream weight N tăng nên biên lỗi tuyệt đối εN cũng tăng. Metadata phải mang configuration fingerprint; từ chối merge khi không khớp thay vì tạo kết quả trông hợp lệ nhưng vô nghĩa.

12. Cửa sổ thời gian và decay

Một CMS tích lũy mãi sẽ trả tần suất toàn lịch sử. Nếu cần “15 phút gần nhất”, cách thực dụng là giữ vòng các sketch theo bucket thời gian rồi cộng các bucket còn hiệu lực. Boundary bucket tạo sai số thời gian cần được mô tả.

Không thể xóa một event hết hạn khỏi CMS insert-only nếu không biết đúng key/weight và chưa thiết kế turnstile. Exponential decay cũng thay đổi semantics; cần scale counter, tuổi dữ liệu và quy tắc merge nhất quán.

13. Hash, dữ liệu đối kháng và bảo mật

Guarantee xác suất giả định hash phân phối phù hợp. Nếu input có thể bị kẻ tấn công chọn để tạo collision, hash yếu hoặc seed công khai có thể biến sai số ngẫu nhiên thành tấn công có chủ đích. Cân nhắc keyed hash/seed bí mật, rotation có version và giới hạn rate theo threat model.

CMS không ẩn dữ liệu theo nghĩa riêng tư. Một bên có quyền query hoặc biết cấu hình có thể suy luận thông tin về tần suất. Nếu yêu cầu differential privacy, cần cơ chế noise và phân tích privacy budget riêng.

14. Vận hành và quan sát

• Ghi width, depth, seed/version, counter type và total weight cùng artifact.
• Đo tỷ lệ ô bằng 0, phân phối counter, saturation và update rate.
• Duy trì exact sample hoặc shadow map nhỏ để ước lượng error thực tế.
• Không dùng estimate làm quyết định tiền bạc/quyền truy cập mà không có guardrail.
• Version serialization và kiểm tra checksum trước khi restore.
• Khi đổi tham số, chạy song song sketch cũ/mới qua đủ một window.

15. Kiểm thử implementation

1. So sánh với hash map exact trên stream nhỏ, ngẫu nhiên.
2. Assert estimate không thấp hơn true count trong insert-only.
3. Đo error trên phân phối đều, Zipf và burst.
4. Tạo key collision có chủ đích để kiểm tra hash/seed.
5. Kiểm tra merge bằng cách chia stream rồi so với sketch chạy toàn stream.
6. Test serialization round-trip và từ chối cấu hình không tương thích.
7. Test counter gần overflow và saturation policy.
8. Benchmark update/query throughput cùng memory thực tế.

Khi nào nên dùng?

• Dùng CMS khi cardinality lớn, RAM cố định, update nhanh và overestimate có thể chấp nhận.
• Dùng exact map khi số key vừa phải hoặc quyết định đòi count chính xác.
• Dùng heavy-hitter sketch khi cần tự liệt kê top key.
• Dùng HyperLogLog khi câu hỏi là số lượng distinct.
• Thiết kế time bucket nếu query có cửa sổ.
• Không dùng CMS như cơ chế authorization, billing chính xác hoặc bằng chứng audit.

Tài liệu tham khảo

• Cormode & Muthukrishnan: The Count-Min Sketch and Its Applications
• Approximating Data with the Count-Min Data Structure
• Apache DataSketches: CountMin Sketch

Kết luận

Count-Min Sketch đổi độ chính xác tuyệt đối lấy bộ nhớ cố định, update nhanh và khả năng merge. Trong mô hình insert-only, min của nhiều hàng tạo ước lượng không thấp hơn count thật và có biên cộng xác suất theo tổng stream. Muốn dùng đúng, cần hiểu error một phía, sizing theo ε/δ, giới hạn của key hiếm, tính tương thích khi merge, overflow và threat model của hash. Khi query và sai số phù hợp, một ma trận chỉ vài trăm KiB có thể tóm tắt luồng dữ liệu khổng lồ.