Count-Min Sketch — đếm tần suất xấp xỉ

TL;DR: Bài toán: trên một luồng hàng triệu sự kiện, đếm xem mỗi phần tử xuất hiện bao nhiêu lần — ví dụ sản phẩm nào đang được thêm vào giỏ nhiều nhất. Đếm chính xác phải nhớ từng key, key nhiều thì tốn hàng GB. Count-Min Sketch đếm gần đúng mà chỉ tốn vài chục KB cố định, nhờ một mẹo: thay vì cho mỗi phần tử một ô đếm riêng, ta ép nhiều phần tử dùng chung một số ít ô (đụng nhau) nên số đếm hơi dư; rồi dùng nhiều bộ ô, mỗi bộ trộn các phần tử theo một cách khác, và khi cần biết số đếm của một phần tử thì lấy con số nhỏ nhất trong các bộ — vì đụng độ chỉ làm dư, số nhỏ nhất luôn gần con số thật nhất. Kết quả vì thế không bao giờ thấp hơn thật, chỉ có thể cao hơn một chút. Redis dùng đúng cách này (lệnh CMS.INCRBY/CMS.QUERY).

Ngày 11/11 năm ngoái, Shopee xử lý hơn 87 triệu đơn hàng trong 24 giờ — tương đương ~1.000 đơn/giây. Với mỗi sự kiện add-to-cart, service cần biết sản phẩm nào đang hot để đẩy lên "trending". Nếu dùng một từ điển đếm productId → số lần, từ điển sẽ phình ra hàng triệu key; riêng phần bộ nhớ đã vài GB. Khi dữ liệu không vừa RAM, đẩy hết xuống DB lại tạo nghẽn cổ chai.

Count-Min Sketch giải quyết bài này: ước lượng tần suất với bộ nhớ vài chục KB cố định, chấp nhận đếm dư một chút (over-count) kiểm soát được, và không bao giờ đếm thiếu (under-count).

1. Trực giác — trò bỏ phiếu vào ít hộp

Trước khi đụng công thức, hãy hình dung một trò. Bạn tổ chức bỏ phiếu cho rất nhiều ứng viên (hàng triệu), nhưng chỉ có vài cái hộp (ít hơn ứng viên rất nhiều). Quy tắc: mỗi ứng viên được gán cố định vào một hộp; ai bỏ phiếu cho ứng viên đó thì thả phiếu vào đúng cái hộp ấy. Vì hộp ít mà ứng viên nhiều, nhiều ứng viên buộc phải dùng chung một hộp. Khi muốn biết một ứng viên được bao nhiêu phiếu, bạn đọc số phiếu trong hộp của ứng viên đó — nhưng con số này hơi dư, vì trong hộp còn lẫn phiếu của những ứng viên khác cùng hộp.

Hai phần tử đụng nhau (chung một hộp) chỉ làm số đếm dư lên, không bao giờ làm thiếu — đây là chìa khoá. Để con số bớt dư, ta dùng một mẹo: thay vì một bộ hộp, dùng nhiều bộ hộp, mỗi bộ xếp ứng viên vào hộp theo một cách khác nhau. Hai ứng viên đụng nhau ở bộ này thì thường không đụng nhau ở bộ kia. Khi cần số phiếu của một ứng viên, ta đọc số của ứng viên đó ở mọi bộ rồi lấy con số nhỏ nhất — vì đụng độ chỉ làm dư, bộ nào dư ít nhất sẽ cho con số nhỏ nhất và gần thật nhất.

Count-Min Sketch làm đúng trò này trên dữ liệu:

Điểm mấu chốt: dùng chung hộp chỉ cộng thêm, chẳng bao giờ trừ bớt — nên mọi bộ đều cho con số không nhỏ hơn số thật. Lấy con số nhỏ nhất là cách chọn ước lượng sát nhất mà vẫn không bao giờ thấp hơn thật. Vì thế tên gọi là Count-Min (đếm rồi lấy nhỏ nhất).

2. Cấu trúc và tham số

2.1 Bài toán và cấu trúc

Cho một luồng (stream) các phần tử x_1, x_2, ..., x_t chảy qua. Ta cần trả lời frequency(x) = số lần x đã xuất hiện cho tới hiện tại. Đếm chính xác phải giữ một từ điển key → số lần; với log truy cập của một sàn thương mại điện tử, số key khác nhau có thể tới hàng chục triệu — từ điển chiếm hàng GB.

Count-Min Sketch (CMS) hiện thực hoá trò bỏ phiếu ở trên bằng một bảng số nguyên kích thước d hàng × w cột (khởi tạo toàn 0). Mỗi hàng là một "bộ hộp" và đi kèm một hàm băm riêng h_1, h_2, ..., h_d; mỗi hàm băm một phần tử về một cột trong khoảng [0, w-1] (một cái "hộp"). Tổng cộng có d hàm băm độc lập.

function CMS_init(d, w):
    -- Tạo bảng d hàng × w cột, khởi tạo 0
    for i <- 0 to d-1:
        for j <- 0 to w-1:
            table[i][j] <- 0
    return table
// Space: O(d * w)

Hai tham số ta tự chọn:

• w (số cột mỗi hàng) — càng nhiều cột thì mỗi hộp gánh ít ứng viên hơn, số đếm dư ít hơn.
• d (số hàng) — càng nhiều bộ hộp thì xác suất bị dư nhiều ở cả mọi bộ càng nhỏ (vì ta lấy con nhỏ nhất).

Phần đặt số cụ thể cho w và d theo mức sai số mong muốn để ở mục công thức (§4) — ở đây chỉ cần nhớ: thêm cột để bớt dư, thêm hàng để bớt rủi ro.

2.2 Một lần cập nhật minh hoạ

Lấy min không phải để "cho chắc" — nó là cách chọn hàng ít ô nhiễm nhất. Không hàng nào đếm thiếu được, vì chẳng có thao tác nào lấy phiếu ra khỏi hộp; nên con nhỏ nhất luôn là con gần sự thật nhất, và thêm hàng chính là giảm rủi ro cả ba cùng bẩn.

3. Thao tác update và query

3.1 Update — tăng đếm

function CMS_update(x):
    -- Tăng ô tương ứng trên mỗi hàng
    for i <- 0 to d-1:
        j <- h_i(x) mod w
        table[i][j] <- table[i][j] + 1
// Time: O(d)  Space: O(1) thêm

3.2 Query — ước lượng tần suất

function CMS_query(x):
    -- Lấy min qua tất cả hàng
    result <- +∞
    for i <- 0 to d-1:
        j <- h_i(x) mod w
        result <- min(result, table[i][j])
    return result
// Time: O(d)  Space: O(1)

Vì sao lấy số nhỏ nhất (Min)? Mỗi ô table[i][j] là một cái hộp dùng chung — nó cộng dồn cả số lần của những phần tử khác cùng băm về đó (đụng độ). Vì dùng chung hộp chỉ cộng thêm chứ không trừ bớt, mọi ô liên quan tới x đều có giá trị không nhỏ hơn số lần thật của x. Lấy con nhỏ nhất qua các hàng tức là chọn cái hộp "sạch" nhất (ít lẫn phiếu người khác nhất) — đó là ước lượng sát nhất mà vẫn không bao giờ thấp hơn thật. Với d hàm băm khác nhau, khả năng một phần tử xui xẻo bị đụng nặng ở cả d hàng là rất nhỏ, nên con nhỏ nhất thường rất sát.

3.3 Trace ví dụ nhỏ — d=2, w=4

Stream: phone, laptop, phone, tablet, phone

Giả sử: h_1(phone)=0, h_1(laptop)=2, h_1(tablet)=0; h_2(phone)=1, h_2(laptop)=3, h_2(tablet)=3.

query(phone): min(table[0][0], table[1][1]) = min(4, 3) = 3. Thật là 3. ✓

query(tablet): min(table[0][0], table[1][3]) = min(4, 2) = 2. Thật là 1. Sai số +1 do collision tablet và phone cùng bucket 0 trên hàng 0.

Đây đúng là tính chất sai số một chiều: kết quả ≥ giá trị thật, không bao giờ dưới.

4. Phân tích sai số (phần công thức)

Giờ mới tới công thức, để biết đặt w và d bao nhiêu cho mức dư mong muốn. Hai ký hiệu cần làm quen: ε (epsilon) là mức dư tương đối ta chấp nhận (ví dụ dư không quá 0,1% tổng lượt), và δ (delta) là xác suất hiếm hoi mà kết quả vẫn dư quá mức đó. Đặt thêm N = tổng số phần tử đã chảy qua stream.

Định lý: Với CMS kích thước d × w, query(x) trả về f̂(x) thoả:

f̂(x) ≥ f(x) luôn luôn (không bao giờ under-count).

P[f̂(x) > f(x) + ε·N] ≤ δ, với ε = e/w và δ = e^(-d) (e ≈ 2,718, là hằng số e tự nhiên — đừng nhầm với ε epsilon ở trên).

N là tổng số phần tử trên stream. Khi chọn w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉, ta đảm bảo sai số tương đối ≤ ε với xác suất ≥ 1 - δ.

Ví dụ thực tế: muốn sai số ≤ 0.1% tổng lượt (ε=0.001) với xác suất ≥ 99% (δ=0.01):

• w = ⌈e/0.001⌉ = ⌈2718.28⌉ = 2719
• d = ⌈ln(100)⌉ = ⌈4.6⌉ = 5
• Bộ nhớ: 5 × 2719 × 8 = 108,760 byte ≈ 106 KB

So với HashMap lưu 10 triệu key (mỗi entry ~50 byte) = ~500 MB — CMS tiết kiệm hơn 4.500 lần.

5. Count-Min Sketch khác Bloom Filter thế nào?

Cả hai đều là cấu trúc xác suất dùng multiple hash functions + bit/ô đếm. Điểm khác biệt then chốt:

Cả hai đều KHÔNG bao giờ false negative: Bloom Filter không nói "không có" khi thật ra có; CMS không nói "ít hơn" khi thật ra nhiều hơn — đây là tính chất bảo toàn quan trọng cho ứng dụng thực tế.

Xem thêm về Bloom Filter tại bài 09 module tìm kiếm nhanh.

6. Ứng dụng thực tế

Tìm phần tử nóng (heavy hitters — những phần tử xuất hiện nhiều nhất, ví dụ top-K sản phẩm bán chạy): chạy CMS song song với một min-heap giữ K phần tử nhiều nhất (heap "min-size-K" — cấu trúc luôn bỏ ra phần tử nhỏ nhất khi đầy, nên giữ lại đúng K phần tử lớn nhất). Mỗi lần cập nhật một phần tử, nếu số đếm ước lượng của nó vượt ngưỡng thì đẩy vào heap. Đây là ý tưởng cơ sở cho mini-challenge bài 06.

Giới hạn tốc độ truy cập (rate limiting — chặn bớt khi một nguồn gửi quá nhiều yêu cầu): thay vì lưu một bộ đếm riêng cho mỗi địa chỉ IP trong Redis, dùng CMS để ước lượng số yêu cầu từ một IP trong cửa sổ thời gian. Vì CMS chỉ đếm dư, sai số chỉ làm việc chặn gắt hơn mức cần: hệ thống có thể chặn nhầm một IP bình thường (false throttle — chặn oan) nhưng không bao giờ thả lọt một IP đáng chặn (false pass — thả oan). Hướng sai lệch này an toàn hơn cho bảo mật.

Giám sát lưu lượng mạng: một router cần biết luồng dữ liệu nào chiếm băng thông lớn nhất. Với hàng triệu luồng mỗi giây, chỉ CMS mới đủ nhanh và đủ nhỏ để chạy trên một con chip chuyên dụng gắn trong router (ASIC — chip thiết kế riêng cho một việc, không phải CPU đa dụng).

7. Pitfall

Pitfall 1 — Nhầm CMS trả về giá trị chính xác

-- SAI: tin query() trả về đúng → dùng để billing
if CMS_query(userId) > 1000:
    charge(userId)     -- Lỗi: over-count có thể charge oan

-- DUNG: dùng CMS chỉ để lọc ứng viên, verify bằng nguồn chính xác
candidates <- items where CMS_query(x) > threshold
for x in candidates:
    exact_count <- DB.count(x)  -- verify chính xác trước khi hành động
    if exact_count > 1000: charge(x)

CMS phù hợp để sàng lọc và theo dõi, không phải để tính tiền hay kiểm toán — những việc cần con số chính xác tuyệt đối.

Pitfall 2 — Chọn d và w không dựa trên ràng buộc bài toán

-- SAI: đoán mò d=3, w=100 mà không kiểm tra ε và δ
-- ε = e/100 ≈ 2.7% — quá lớn nếu N = 10 triệu, sai số tuyệt đối ~270.000!

-- DUNG: tính ngược từ ràng buộc
epsilon <- 0.001   -- chấp nhận sai số 0.1% * N
delta   <- 0.01    -- xác suất vượt sai số ≤ 1%
w <- ceil(e / epsilon)        -- = 2719
d <- ceil(ln(1 / delta))      -- = 5

Luôn xuất phát từ ε và δ chấp nhận được, sau đó tính w và d. Ngược lại sẽ cho kết quả sai quá ngưỡng cho phép.

Pitfall 3 — Dùng hàm băm không độc lập hoặc dùng chung seed

-- SAI: dùng cùng 1 hàm băm với d offset khác nhau
h_i(x) = hash(x) + i   -- Không độc lập: cùng collision pattern!

-- DUNG: d hàm băm thực sự độc lập (khác seed hoặc thuật toán khác nhau)
h_i(x) = murmur3(x, seed=i)  -- seed độc lập → độc lập thống kê

Các hàm băm phải độc lập từng cặp (pairwise independent — nghĩa là hai hàm băm thực sự khác nhau: biết kết quả của hàm này không giúp đoán được kết quả của hàm kia) thì bảo đảm sai số lý thuyết mới đúng. Dùng phép cộng offset đơn giản không đủ độc lập: các hàm vẫn đụng độ theo cùng một kiểu, nên sai số thực tế tệ hơn mức lý thuyết hứa hẹn.

8. Liên hệ các bài khác

• Hash function — nền tảng băm: hàm băm độc lập là viên gạch nền của CMS. Bài đó giải thích thế nào là độc lập từng cặp và hiệu ứng tuyết lở (avalanche — đổi một chút đầu vào thì kết quả băm đổi hẳn) — hai tính chất ảnh hưởng trực tiếp tới chất lượng CMS.
• Bloom Filter: anh em họ của CMS — cùng dùng nhiều hàm băm trên một mảng, nhưng trả lời câu hỏi "phần tử có trong tập chưa" thay vì "xuất hiện bao nhiêu lần". Đọc bài đó để thấy rõ điểm giống và khác về cách dựng.
• HyperLogLog: cùng họ xác suất — HyperLogLog ước lượng số phần tử khác nhau, còn CMS ước lượng số lần xuất hiện của từng phần tử. Hai bài bổ trợ cho nhau khi xử lý luồng dữ liệu.
• Mini-challenge top-K: áp dụng CMS kết hợp min-heap để tìm các phần tử nóng — bài thực hành trực tiếp của bài này.
• Amortized analysis: phân tích khấu hao giải thích vì sao mỗi thao tác chỉ chạm d ô (số hàng), gộp lại trên toàn bộ luồng vẫn cho tốc độ xử lý cao trong thực tế.

📚 Deep Dive

Tóm tắt

• Đụng độ → chỉ đếm dư, không thiếu; lấy min qua d hàng → ước lượng sát nhất mà vẫn ≥ thật.
• Chọn w = ⌈e/ε⌉ để sai số ≤ ε×N; d = ⌈ln(1/δ)⌉ để xác suất vượt ngưỡng ≤ δ — bộ nhớ cố định d×w ô.
• Bloom Filter hỏi "có trong tập chưa?" (bit, false positive); CMS hỏi "xuất hiện bao nhiêu lần?" (số nguyên, over-count) — cả hai không bao giờ false negative.
• Dùng để sàng lọc và theo dõi (heavy hitters, rate limiting); cần số chính xác tuyệt đối thì verify bằng nguồn đếm thật.

Tự kiểm tra

Bài tiếp theo: Sliding window — thống kê trên cửa sổ trượt