Count-Min Sketch (Bản tóm lược ước lượng tần suất)
1. Tổng quan
A. Định nghĩa
Count-Min Sketch (CMS) là một cấu trúc dữ liệu xác suất (probabilistic) ước lượng xấp xỉ mỗi phần tử đã xuất hiện bao nhiêu lần (tần suất, frequency) trong một luồng dữ liệu lớn mà không lưu một bộ đếm riêng cho từng phần tử, chỉ dùng một mảng bộ đếm hai chiều kích thước cố định và một vài hàm băm; khi truy vấn, nó lấy giá trị nhỏ nhất (min) trong các bộ đếm của nhiều hàng để triệt tiêu sự ước lượng vượt quá do đụng độ băm gây ra.
Count-Min Sketch trả lời câu hỏi "phần tử này cho đến nay đã xuất hiện bao nhiêu lần." Để đếm chính xác thì phải đặt một bộ đếm cho mỗi khóa duy nhất xuất hiện, nên nếu có hàng trăm triệu khóa khác nhau thì bộ nhớ cũng lớn tương ứng (O(số khóa duy nhất)). CMS không lưu khóa, mà ghi chồng tần suất của nhiều khóa lên một mảng số nguyên nhỏ duy nhất có chiều rộng w · chiều sâu d. Kết quả là dù có mười nghìn hay một tỷ khóa duy nhất thì bộ nhớ không đổi, đổi lại chịu một sai số nhỏ là ước lượng vượt quá (overestimation) do đụng độ. Khác với [[bloom-filter]] đã nêu trước (xấp xỉ "sự thuộc về") và [[hyperloglog]] (xấp xỉ "số lượng duy nhất"), CMS xấp xỉ "tần suất (số lần)," nên ba cấu trúc tạo thành một họ bản tóm lược xác suất (sketch) bổ trợ lẫn nhau.
CMS có bốn tính chất. Thứ nhất, bộ nhớ cố định bất kể quy mô đầu vào hay số khóa duy nhất (không gian hằng số). Thứ hai, chèn và tra cứu mỗi thao tác chỉ chạm d hàm băm và d bộ đếm, nên rất nhanh ở mức O(d), trong đó d thường là hằng số nhỏ từ vài đến khoảng mười. Thứ ba, hai sketch dùng cùng chiều rộng, chiều sâu và hàm băm có thể hợp nhất không mất mát bằng phép cộng theo từng phần tử, phù hợp tự nhiên với tổng hợp phân tán. Thứ tư, khi không có cập nhật âm (chỉ tăng đếm), giá trị ước lượng luôn lớn hơn hoặc bằng giá trị thật và không bao giờ ước lượng thấp. Bó bốn tính chất này quyết định phạm vi áp dụng của CMS.
B. Bối cảnh ra đời và sự cần thiết
Khi nhật ký web, quảng cáo, viễn thông và tài chính đổ về với hàng trăm nghìn sự kiện mỗi giây, các truy vấn tần suất và phát hiện phần tử xuất hiện nhiều nhất (heavy hitter) như "URL nào được gọi nhiều nhất," "IP nguồn nào gửi số gói tin bất thường lớn," "từ khóa tìm kiếm nào đang tăng vọt" đã trở thành chỉ số vận hành cốt lõi. Tuy nhiên tổng hợp tần suất chính xác vốn dĩ tốn kém. Vì phải duy trì một bộ đếm cho mỗi khóa, với hàng trăm triệu khóa duy nhất trong hàng tỷ mục nhật ký mỗi ngày thì cần một hash map vài GB đến vài chục GB, và cập nhật, truy vấn nó theo thời gian thực biến áp lực bộ nhớ và độ trễ GC thành chi phí dịch vụ trực tiếp.
Count-Min Sketch khai thác về mặt kỹ thuật thực tế vận hành rằng "một sai số tương đối trong vài phần trăm, chứ không phải tần suất chính xác, là đủ tốt." Việc một IP kết nối chính xác 1.000.230 hay 1.000.245 lần không ảnh hưởng đến quyết định "IP này có phải heavy hitter vượt ngưỡng không," nên dung thứ một ước lượng vượt quá nhỏ để đổi lấy việc tiết kiệm bộ nhớ hàng chục đến hàng nghìn lần là hợp lý. Đặc biệt, nhờ ưu thế quyết định là CMS dễ hợp nhất, các sketch được tổng hợp riêng theo máy chủ, khung thời gian hay shard có thể gộp lại không mất mát để khôi phục tần suất toàn cục, khiến nó trở thành cấu trúc tóm lược tiêu chuẩn trên thực tế trong môi trường phân tán và luồng.
Hiểu vì sao tổng hợp chính xác về cơ bản tốn kém sẽ làm rõ giá trị của CMS. Một bảng tần suất chính xác phải ghi nhớ "mọi khóa đã thấy cho đến nay," nên nếu không gian khóa mở (ví dụ: chuỗi, IP, URL tùy ý) và phân phối đuôi dài thì số bộ đếm bùng nổ. Trong môi trường mở rộng theo chiều ngang, toàn bộ trạng thái này đụng hai bức tường cùng lúc: giới hạn bộ nhớ nút và chi phí xáo trộn (shuffle) mạng. CMS né tránh các bức tường này bằng nhận thức rằng "nếu chỉ cần một thống kê duy nhất là tần suất thì không có lý do gì phải ghi nhớ từng khóa một," chồng nhiều khóa lên cùng bộ đếm trong khi triệt tiêu về mặt thống kê ảnh hưởng của đụng độ.
C. Đặc điểm
CMS có cấu trúc sai số một chiều trong đó không bao giờ ước lượng thấp. Điều này đặc biệt có lợi cho việc phát hiện không được phép bỏ sót (false negative), như "phát cảnh báo khi vượt ngưỡng." Mặt khác, ngay cả một khóa hiếm khi xuất hiện cũng có thể trông bị thổi phồng nếu đụng độ với một khóa thường xuyên khác, nên có giới hạn là ước lượng cho các khóa thưa tương đối không chính xác. Ngoài ra, dạng cơ bản chỉ hỗ trợ chèn và tra cứu; cho phép xóa (cập nhật âm) phá vỡ bảo đảm một chiều của min, nên cần một biến thể riêng.
Về mặt cấu trúc, CMS có quan hệ thân thuộc sâu sắc với [[bloom-filter]]. Ở nơi bộ lọc Bloom dựng một bit, CMS đặt một bộ đếm số nguyên, khái quát hóa "có được dựng không" thành "đã tích bao nhiêu." Thật vậy, thu bộ đếm xuống một bit thì hội tụ về bộ lọc Bloom, và đổi tra cứu từ min sang OR thì hội tụ về truy vấn thuộc về. Góc nhìn này minh họa nguyên lý thiết kế rằng "đếm cái gì và tổng hợp ra sao trên cùng một cấu trúc chồng băm quyết định công dụng của cấu trúc dữ liệu," và gắn ba bản tóm lược xác suất (Bloom, HLL, CMS) vào một khung tư duy duy nhất.
2. Cấu trúc và nguyên lý hoạt động
Cốt lõi của Count-Min Sketch là "ghi một khóa phân tán trên d bộ đếm bằng d hàm băm khác nhau, và khi truy vấn thì tin vào giá trị nhỏ nhất trong d giá trị đó." Dù một bộ đếm cụ thể bị thổi phồng bởi đụng độ, xác suất cả d cùng đụng độ nặng một lúc rất thấp, nên giá trị nhỏ nhất gần với giá trị thật. Đây là cùng ý tưởng với việc đo nhiều lần và tin vào kết quả nhỏ nhất; nhờ tính một chiều rằng "đụng độ chỉ làm tăng giá trị," giá trị nhỏ nhất trở thành ước lượng ít bị nhiễm nhất.
flowchart TB
X["đầu vào (khóa x, lượng tăng c)"] --> H1["băm h1(x) → cột j1"]
X --> H2["băm h2(x) → cột j2"]
X --> HD["băm hd(x) → cột jd"]
H1 --> R1["hàng1: C[1][j1] += c"]
H2 --> R2["hàng2: C[2][j2] += c"]
HD --> RD["hàngd: C[d][jd] += c"]
subgraph TABLE["mảng bộ đếm d hàng x w cột"]
R1
R2
RD
end
Cấu trúc dữ liệu gồm một mảng bộ đếm số nguyên hai chiều C gồm d hàng (chiều sâu, depth) x w cột (chiều rộng, width) và d hàm băm độc lập lẫn nhau h₁…h_d. Mỗi hàm băm ánh xạ một khóa sang chỉ số cột trong khoảng [0, w). Mỗi hàng là một "bảng tần suất xấp xỉ" độc lập, và vì các hàng dùng hàm băm khác nhau nên dù hai khóa đụng độ ở hàng 1, chúng thường không đụng độ ở hàng 2 và 3. Chính tính độc lập giữa các hàng này biện minh cho việc tin vào giá trị nhỏ nhất của d ước lượng.
Thao tác Cập nhật (Update) Update(x, c) tính chỉ số cột hᵢ(x) cho mỗi hàng i (=1…d) và cộng c vào C[i][hᵢ(x)]. Thông thường c=1 mỗi khi một phần tử đến trong luồng, nhưng với nhật ký có trọng số có thể cộng một c dương tùy ý. Vì một khóa chỉ chạm đúng một ô ở mỗi hàng, chi phí cập nhật là hằng số ở mức O(d) bất kể quy mô đầu vào. Ví dụ với d=4, mỗi sự kiện chỉ cần 4 lần băm và 4 phép cộng, nên một luồng hàng triệu mỗi giây có thể xử lý trên một nút duy nhất.
Thao tác Truy vấn (Query) Query(x) đọc C[i][hᵢ(x)] ở mỗi hàng và trả về giá trị nhỏ nhất trong d giá trị đó làm tần suất ước lượng f̂(x). Nếu tần suất thật của một khóa x là f(x), thì mọi bộ đếm nơi x được ghi chứa ít nhất f(x) cộng với đóng góp của các khóa khác, nên C[i][hᵢ(x)] ≥ f(x) đúng ở mọi hàng. Do đó giá trị nhỏ nhất cũng ít nhất bằng f(x), và đây là bảo đảm cốt lõi của CMS rằng ước lượng vượt quá là có thể nhưng ước lượng thấp là không thể.
Hãy củng cố trực giác bằng một ví dụ nhỏ. Giả sử một sketch với d=2, w=4 nhận khóa A 5 lần, B 3 lần và C 2 lần. Nếu hàm băm h₁ ở hàng 1 đưa A và C về cùng một cột, cột đó tích 5+2=7, nên truy vấn A chỉ từ hàng 1 sẽ ước lượng vượt quá 2 ở mức 7. Nhưng nếu hàm băm h₂ ở hàng 2 đưa A về một cột khác với B và C, cột đó đúng bằng 5, và truy vấn khôi phục giá trị thật với min(7, 5)=5. Như vậy công dụng của phép min là một đụng độ ở một hàng được hiệu chỉnh bởi một bộ đếm "sạch" ở hàng khác, và khi số hàng d tăng thì xác suất mọi hàng bị nhiễm cùng lúc giảm theo cấp số mũ, làm ước lượng ổn định.
3. Luồng xử lý truy vấn và phát hiện heavy hitter
Chỉ riêng CMS chỉ có thể trả lời "tần suất của một khóa cụ thể" và không thể trực tiếp trả lời "top-K phần tử thường gặp là gì." Vì yêu cầu phổ biến nhất trong thực tế chính là phát hiện heavy hitter, CMS thường được dùng kết hợp với một min-heap nhỏ hoặc cấu trúc Top-K. Luồng dưới đây là một pipeline điển hình nhận một phần tử luồng, cập nhật sketch, và thăng một phần tử lên ứng viên nếu tần suất ước lượng của nó vượt cận dưới của heap.
flowchart LR
S["phần tử luồng x"] --> U["CMS.Update(x, 1)"]
U --> Q["est = CMS.Query(x)"]
Q --> D{"est > giá trị nhỏ nhất của heap?"}
D -- "có" --> P["phản ánh x, est vào heap Top-K"]
D -- "không" --> N["bỏ qua"]
P --> O["định kỳ xuất top-K phần tử thường gặp"]
N --> O
Trong cấu trúc này, CMS đảm nhận vai trò "duy trì tần suất xấp xỉ của mọi khóa trong bộ nhớ hằng số," còn heap đảm nhận vai trò "chọn và giữ đã sắp xếp chỉ top K." Vì kích thước heap cố định ở K nên tổng bộ nhớ vẫn là hằng số. Ví dụ, nếu một nhà mạng viễn thông trích top 100 IP đích mỗi cửa sổ một phút ([[stream-processing-windowing]]), thì vài MB CMS và một heap 100 ô là đủ thay vì một bảng chính xác của toàn bộ hàng triệu IP duy nhất. Tuy nhiên do ước lượng vượt quá, một khóa thưa thỉnh thoảng có thể lọt sai vào heap, nên người ta dùng các thiết kế thêm biên (margin) vào ngưỡng hoặc gắn kiểm chứng chính xác khi kết thúc cửa sổ.
Điểm phải lưu ý trong phát hiện heavy hitter là tính bất đối xứng rằng CMS bắt mọi "ứng viên có tần suất ước lượng bằng hoặc trên ngưỡng" (không bỏ sót), nhưng một số ứng viên có thể là giả, bị thổi phồng bởi đụng độ. Do đó các pipeline thực tế thường áp dụng cấu trúc hai giai đoạn "lọc rẻ các ứng viên lượt đầu bằng CMS (độ nhớ lại 100%), rồi kiểm chứng bằng bộ đếm chính xác hoặc lấy mẫu (hiệu chỉnh độ chính xác)." Điều này áp tổng hợp chính xác đắt đỏ chỉ lên vài ứng viên thay vì toàn bộ, một mẫu hình kết hợp xấp xỉ-chính xác điển hình nắm được cả chi phí và độ chính xác.
Tính hợp nhất được (mergeability) cũng là một trục quan trọng của luồng truy vấn. Nếu shard A và shard B mỗi cái duy trì CMS_A và CMS_B, thì CMS_A+B, tức cộng hai mảng theo từng tọa độ, là tương đương về mặt toán học với "xử lý toàn bộ luồng bằng một sketch duy nhất." Nhờ đó, trong tổng hợp phân tán kiểu MapReduce hay Spark, mỗi phân vùng có thể xây một sketch cục bộ và giai đoạn reduce chỉ cần cộng chúng lại, loại bỏ chi phí xáo trộn dữ liệu thô. Tính cộng được này, cùng với [[hyperloglog]], là tính chất quyết định khiến CMS trở thành một bản tóm lược tiêu chuẩn trong môi trường phân tán.
4. Giới hạn sai số và thiết kế tham số
Sai số của CMS được kiểm soát không phải bằng may rủi mà bằng một cận trên xác suất chặt chẽ. Gọi tổng tần suất của toàn bộ luồng (chuẩn L1) là N = Σf(x), và đặt chiều rộng là w, chiều sâu là d; khi đó điều sau đúng. Đóng góp kỳ vọng của các khóa khác lẫn vào bộ đếm của khóa x ở một hàng xấp xỉ N/w (trực giác rằng tổng khối lượng N trải đều trên w cột). Áp dụng bất đẳng thức Markov, xác suất ước lượng vượt quá ở một hàng vượt εN là (N/w)/(εN) = 1/(εw). Đặt chiều rộng thành w = ⌈e/ε⌉ làm xác suất này bằng 1/e, và vì d hàng độc lập, xác suất mọi hàng đồng thời vượt εN là (1/e)^d = e^(−d). Để điều này nhiều nhất bằng xác suất thất bại δ, một chiều sâu d = ⌈ln(1/δ)⌉ là đủ.
Tóm lại, khi w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉, ước lượng bảo đảm f(x) ≤ f̂(x) ≤ f(x) + εN với xác suất ít nhất 1−δ, và không gian cố định ở O((1/ε)·ln(1/δ)) bộ đếm. Ví dụ, nếu bạn muốn ε=0.001 (0,1% tổng khối lượng) và δ=0.001 (độ tin cậy 99,9%), thì w ≈ ⌈e/0.001⌉ = 2.719 và d = ⌈ln(1000)⌉ = 7, nên với khoảng 2.719×7 ≈ 19.033 bộ đếm (khoảng 76KB cho số nguyên 4 byte) bạn có thể xấp xỉ tần suất của hàng trăm triệu khóa. Việc bộ nhớ cố định ở mức này bất kể số khóa duy nhất là sức hấp dẫn thực tiễn của CMS.
| Tham số | Ý nghĩa | Công thức | Nếu lớn hơn/nhỏ hơn |
|---|---|---|---|
| ε (epsilon) | tỷ lệ sai số cho phép (εN) | yêu cầu đầu vào | nhỏ hơn thì chính xác hơn, w tăng |
| δ (delta) | xác suất thất bại bảo đảm | yêu cầu đầu vào | nhỏ hơn thì nâng độ tin cậy, d tăng |
| w (chiều rộng) | số cột | ⌈e/ε⌉ | lớn hơn thì giảm đụng độ, tăng bộ nhớ |
| d (chiều sâu) | số hàng/hàm băm | ⌈ln(1/δ)⌉ | lớn hơn thì nâng độ tin cậy, tăng chi phí truy vấn |
Điểm phải lưu ý ở đây là cận sai số tỷ lệ với lượng tuyệt đối εN. Luồng tần suất cao N càng lớn thì εN càng lớn, nên các khóa thường xuyên (heavy hitter) có sai số tương đối nhỏ còn các khóa thưa bị vùi dưới εN và có sai số tương đối lớn. Điều này giải thích về mặt toán học đặc tính rằng CMS theo thiết kế mạnh ở phát hiện heavy hitter và yếu ở ước lượng chính xác phân phối đuôi (tail). Để bảo đảm này giữ được, các hàm băm phải có tính chất ít nhất là độc lập từng cặp (pairwise independence), và trong thực tế d hàm băm được xây bằng cách cho các hạt giống (seed) khác nhau vào các hàm băm phi mật mã như MurmurHash hay xxHash.
5. Các biến thể và mở rộng chính
Nhiều biến thể đã được đề xuất để giảm ước lượng vượt quá của CMS cơ bản hoặc mở rộng chức năng của nó, và mỗi cái khác nhau ở "từ bỏ cái gì và được cái gì." Thay vì chỉ liệt kê các biến thể, hiểu vì sao mỗi biến thể là cần thiết mới là cốt lõi của phán đoán thiết kế.
Cập nhật bảo thủ (Conservative Update, CU) là kỹ thuật giảm ước lượng vượt quá nhiều nhất trong thực tế. Thay vì nâng cả d bộ đếm khi cập nhật, nó trước hết tìm giá trị nhỏ nhất m trong d giá trị hiện tại và chỉ nâng các bộ đếm có giá trị bằng m lên c. Vì truy vấn dù sao cũng nhìn giá trị nhỏ nhất, việc không nâng "các bộ đếm vốn đã đủ lớn" không làm hại ước lượng, và bằng cách triệt tiêu các lần tăng không cần thiết, sai số trung bình giảm nhiều. Cái giá là việc xóa trở nên bất khả (bảo đảm sụp đổ dưới cập nhật âm) và phép tính giá trị nhỏ nhất thêm vào làm cập nhật chậm hơn chút ít. Tính đến năm 2024, các phân tích chính xác về sai số trường hợp xấu nhất và trung bình của cập nhật bảo thủ vẫn đang được công bố, nên nó vẫn là một biến thể được nghiên cứu tích cực ngay cả về mặt lý thuyết.
Count Sketch là một cấu trúc họ hàng được đề xuất trước CMS; nó bổ sung gán cho mỗi khóa một hàm băm dấu ±1 bên cạnh chỉ số cột, cộng ±c vào bộ đếm khi cập nhật, và lấy trung vị (median) của d ước lượng khi truy vấn. Vì các dấu triệt tiêu lẫn nhau, ảnh hưởng của đụng độ hội tụ về 0 trung bình, cho một ước lượng không chệch (unbiased), và sai số tỷ lệ với chuẩn L2 thay vì L1 (N), điều này có thể thuận lợi hơn cho các luồng lệch. Nó cũng hỗ trợ cập nhật âm (xóa). Đổi lại, hàm băm dấu và phép tính trung vị làm việc triển khai phức tạp hơn, và bảo đảm một chiều của CMS rằng "nó không bao giờ ước lượng thấp" biến mất. Bảng dưới đây tóm tắt sự khác biệt vai trò của ba bản tóm lược xác suất.
| Cấu trúc | Câu hỏi được trả lời | Hướng sai số | Xóa | Chỉ số tiêu biểu |
|---|---|---|---|---|
| [[bloom-filter]] | sự thuộc về (có không?) | chỉ dương tính giả | bất khả (cơ bản) | FPP |
| [[hyperloglog]] | số lượng duy nhất (bao nhiêu loại?) | cả hai hướng | bất khả | sai số tương đối ~2% |
| Count-Min Sketch | tần suất (bao nhiêu lần?) | chỉ ước lượng vượt quá | bất khả (cơ bản) | εN, δ |
| Count Sketch | tần suất (bao nhiêu lần?) | cả hai hướng (không chệch) | khả thi | dựa trên L2 |
Ngoài những cái này, các biến thể nén lượng tăng biến thiên theo thang logarit để tiết kiệm bộ nhớ hơn nữa, một CMS suy giảm (decay) làm suy giảm các tần suất cũ theo thời gian, và một CMS cửa sổ trượt giữ một CMS cho mỗi cửa sổ và chỉ tổng hợp khoảng gần đây được dùng rộng rãi trong phân tích luồng. Dù chọn biến thể nào, cốt lõi là nó là một câu trả lời khác nhau cho câu hỏi chung "xử lý đụng độ ra sao."
Lựa chọn biến thể rốt cuộc là một sự đánh đổi tam giác giữa sai số, chức năng và chi phí. Khi độ chính xác quan trọng nhất và không có xóa, cập nhật bảo thủ là mặc định; khi cần xóa hoặc ước lượng không chệch thì là Count Sketch; cho xu hướng thời gian thực thì suy giảm hoặc cửa sổ trượt được xếp chồng lên—lắp ráp cấu trúc ngược từ yêu cầu. Một nguyên lý thiết kế quan trọng là thay đổi chiều rộng, chiều sâu, hàm băm hay sơ đồ dấu đã cố định một lần sẽ phá vỡ tính tương thích hợp nhất với các sketch hiện có, nên biến thể và tham số phải được cố định cẩn thận với con mắt hướng về vòng đời dịch vụ.
6. Các trường hợp áp dụng
Giám sát mạng và phát hiện DDoS là một công dụng kinh điển của CMS. Bộ định tuyến và tường lửa phải tìm "các nguồn gửi lưu lượng lớn bất thường" giữa hàng triệu gói tin mỗi giây, nhưng không đủ bộ nhớ để giữ một bộ đếm cho mỗi IP. Bằng cách xấp xỉ số gói tin của các IP nguồn với CMS và chỉ thăng các heavy hitter trên ngưỡng lên làm đối tượng ACL và [[rate-limiting]], phát hiện ở tốc độ đường truyền (line-rate) là khả thi với vài MB bộ nhớ. Vì không có ước lượng thấp, điểm không có nguy cơ bỏ sót lưu lượng tấn công phù hợp đặc biệt tốt với phát hiện bảo mật.
Tối ưu hóa truy vấn cơ sở dữ liệu cũng là một trường hợp quan trọng. Để ước lượng độ chọn lọc (selectivity) của join và filter, bộ tối ưu hóa cần phân phối tần suất của các giá trị cột. Duy trì một biểu đồ tần suất chính xác của mọi giá trị là tốn kém, nên CMS được dùng để xấp xỉ tần suất xuất hiện của các giá trị cụ thể nhằm ước lượng "điều kiện này cho ra khoảng bao nhiêu hàng kết quả" và chọn một kế hoạch thực thi. Dù là xấp xỉ, nó đủ cho so sánh tương đối, và việc ngân sách bộ nhớ cố định giữ chi phí thu thập thống kê trong tầm kiểm soát.
Chính sách loại bỏ bộ nhớ đệm có W-TinyLFU của Caffeine làm đại diện. Như đã thấy trong [[caching-strategy]], để bảo vệ "các mục thường được dùng," LFU phải biết tần suất truy cập của mỗi mục, nhưng một bảng tần suất chính xác của hàng triệu khóa có thể lớn hơn chính bộ nhớ đệm. W-TinyLFU xấp xỉ tần suất truy cập bằng CMS và thêm suy giảm theo thời gian, kết hợp tính mới của LRU và tần suất của LFU để đạt tỷ lệ trúng cao với ít bộ nhớ. Thực tế, Caffeine cho thấy lợi thế so với Guava về tỷ lệ trúng và thông lượng, và nền tảng của nó là ước lượng tần suất dựa trên CMS.
Gian lận tài chính và hệ thống gợi ý cũng dựa vào xấp xỉ tần suất. Các công ty thẻ phải theo dõi theo thời gian thực xem "liệu một số lượng bất thường lớn các lần thử phê duyệt có tập trung tại cùng một đơn vị chấp nhận hay thiết bị đầu cuối trong thời gian ngắn không," nhưng cập nhật và truy vấn các bộ đếm chính xác cho hàng chục triệu đơn vị chấp nhận ở độ hạt mili giây là khó. Bằng cách xấp xỉ tần suất thử theo đơn vị chấp nhận, thiết bị đầu cuối và BIN thẻ với CMS và định tuyến những cái trên ngưỡng sang xác thực bổ sung hay tạm giữ, việc xử lý được thực hiện trong bộ nhớ hằng số mà không bỏ sót các giao dịch đáng ngờ, vì không có ước lượng thấp. Các hệ thống gợi ý cũng xấp xỉ tần suất phổ biến của các mục và từ khóa tìm kiếm với CMS để hiệu chỉnh độ phổ biến và khử trùng lặp, và vì xếp hạng tương đối quan trọng hơn con số chính xác nên sai số xấp xỉ không phải là vấn đề thực tiễn.
Về mặt nền tảng phân tích luồng và sản phẩm hóa, Redis là đại diện. Mô-đun cấu trúc dữ liệu xác suất của Redis cung cấp Count-Min Sketch như một kiểu hạng nhất, tạo một sketch bằng CMS.INITBYDIM (chỉ định chiều rộng và chiều sâu trực tiếp) hoặc CMS.INITBYPROB (chỉ định ε và δ mục tiêu), cập nhật nhiều mục cùng lúc với CMS.INCRBY, trả về tần suất ước lượng với CMS.QUERY, và hỗ trợ hợp nhất nhiều sketch với CMS.MERGE. Như vậy các khối lượng công việc như "từ khóa tìm kiếm tăng vọt thời gian thực," "số lượt xem xấp xỉ theo sản phẩm," và "khối lượng gọi ước lượng theo khóa API" được xử lý trong bộ nhớ hằng số mà không thay đổi mã ứng dụng. Các thư viện phân tích quy mô lớn (ví dụ: các thư viện sketch trong hệ sinh thái Spark) cũng dùng họ CMS và Count Sketch làm công cụ cơ bản để ước lượng phần tử thường gặp.
7. Chuyên sâu — Điểm thiết kế và xu hướng mới nhất khi áp dụng thực tế
Khi đưa CMS vào một hệ thống thực, nó không kết thúc với các công thức lý thuyết mà đòi hỏi điều chỉnh khớp với bối cảnh vận hành. Thứ nhất, thói quen tính ngược ε và δ từ "sai số tuyệt đối mong muốn" là quan trọng. Vì cận sai số là εN, với một dịch vụ nơi tổng luồng N tăng lên hàng tỷ mỗi ngày, ε phải được đặt đủ nhỏ để cho ra các ước lượng dùng được ngay cả với các khóa thưa. Ngược lại, nếu "chỉ cần biết một vài heavy hitter hàng đầu là đủ," đặt ε lỏng để tiết kiệm bộ nhớ là hợp lý. Tức là, sự đánh đổi giữa độ chính xác yêu cầu và ngân sách bộ nhớ phải được thiết kế rõ ràng theo đúng câu hỏi nghiệp vụ.
Thứ hai, suy giảm và phân cửa sổ gần như luôn cần thiết. CMS thuần chỉ đếm tần suất tích lũy, nên "độ phổ biến từ lâu" còn lại mãi mãi. Để thấy các đợt tăng vọt và xu hướng thời gian thực, bạn phải đặt lại sketch định kỳ, áp dụng suy giảm theo cấp số mũ, hoặc chỉ tổng hợp khoảng gần đây bằng một cửa sổ trượt. Đây là điểm nó kết hợp với ngữ nghĩa thời gian của [[stream-processing-windowing]], một quyết định thiết kế định nghĩa "tần suất trong khoảng thời gian nào bạn nhìn vào."
Thứ ba, lựa chọn kỹ thuật giảm thiểu ước lượng vượt quá. Khi độ chính xác quan trọng, hãy áp dụng cập nhật bảo thủ (CU) làm mặc định để hạ sai số trung bình, nhưng với các khối lượng công việc cần xóa (ví dụ: trừ dần khi kết thúc phiên), dùng một cấu trúc hỗ trợ cập nhật âm như Count Sketch thay vì CU. Tính đến năm 2024, với các phân tích mới về đặc tính sai số của cập nhật bảo thủ đang được công bố, họ CMS tiếp tục tiến theo hướng "thuần hóa đụng độ và sai số tốt hơn." Ngoài ra, gần đây một thiết kế lai đang được nghiên cứu trong đó CMS kết hợp ước lượng tần suất với một mô hình học được (learned sketch), kéo các khóa thường xuyên vào các bộ đếm chính xác riêng và chỉ giao các khóa thưa cho sketch để hạ sai số tổng thể.
Thứ tư, góc nhìn bảo mật và quyền riêng tư cũng đang nổi lên. Khi CMS tổng hợp tần suất hành vi người dùng, tính chất không lưu các mục riêng lẻ là thân thiện với quyền riêng tư, nhưng vì thông tin nhạy cảm có thể bị suy ra ngược chỉ từ ước lượng do đụng độ, nghiên cứu về kết hợp nhiễu quyền riêng tư vi phân (DP) vào sketch đang được tiến hành. Điều này kết nối với xu hướng gần đây cố gắng xử lý "tính hữu dụng của tổng hợp và quyền riêng tư" đồng thời.
Thứ năm, tính quan sát được (observability) và kiểm chứng phải được đưa vào thiết kế. Một cấu trúc xấp xỉ khó tin cậy trừ khi "ước lượng hiện tại có thể sai bao nhiêu" là nhìn thấy được. Do đó, trong vận hành, nên liên tục tính cận sai số hiện tại εN từ tổng N và chiều rộng w rồi phơi bày trên một bảng điều khiển, và giám sát phạm vi ước lượng vượt quá thực tế bằng cách định kỳ so sánh một vài khóa với các bộ đếm chính xác. Quy giản "chất lượng của xấp xỉ về một chỉ số đo lường được" theo cách này cho phép tinh chỉnh lại các tham số sớm khi đặc tính lưu lượng thay đổi và sai số tăng.
8. Cân nhắc và hàm ý
Thứ nhất, phán đoán tính phù hợp áp dụng (chiến lược áp dụng). CMS tối ưu khi bạn muốn biết "tần suất/heavy hitter trong bộ nhớ hằng số, không ước lượng thấp." Ngược lại, khi bạn cần một bảng tần suất chính xác (quyết toán, tính phí), muốn một số lượng duy nhất ([[hyperloglog]]), hoặc chỉ cần sự thuộc về ([[bloom-filter]]), một công cụ khác phù hợp. Từ góc nhìn Kỹ sư chuyên nghiệp, cốt lõi là năng lực thiết kế trước hết phân rã "yêu cầu là độ chính xác hay dung thứ xấp xỉ, câu hỏi là tần suất hay lực lượng" rồi ánh xạ cấu trúc dữ liệu.
Thứ hai, tính định hướng sai số và thiết kế an toàn (đánh đổi). Ước lượng vượt quá một chiều của CMS cho sự an toàn khi thất bại (fail-safe) là "không bỏ sót trong phát hiện," nhưng đồng thời gây ra dương tính giả (false positive). Trong các lĩnh vực mà chi phí báo động giả cao, như chặn DDoS và phát hiện gian lận, dương tính giả phải được kiểm soát bằng cách kết hợp biên ngưỡng, kiểm chứng chính xác lượt hai, và cập nhật bảo thủ. Nhìn hướng của sai số cùng với cấu trúc chi phí là chìa khóa của sự ổn định vận hành.
Thứ ba, sự khớp với kiến trúc phân tán/luồng (công nghệ liên quan). Tính hợp nhất cộng được của CMS ăn khớp tự nhiên với xử lý phân tán như MapReduce, Spark và Kafka Streams. Mẫu hình mỗi phân vùng xây một sketch cục bộ và cộng ở reduce loại bỏ chi phí xáo trộn và, kết hợp với [[stream-processing-windowing]] và suy giảm, cấu thành một pipeline xu hướng thời gian thực. Việc lựa chọn cấu trúc dữ liệu dẫn trực tiếp đến cấu trúc chi phí kiến trúc phải được phản ánh sớm trong thiết kế.
Thứ tư, quản trị tham số và tính tái lập (vận hành/triển vọng). Các tham số như w, d, hạt giống băm và chu kỳ suy giảm khó thay đổi một khi đã đặt, vì tính tương thích hợp nhất. Vì các sketch với thiết lập khác nhau không thể gộp lại, ở cấp tổ chức, thiết lập sketch phải được chuẩn hóa và quản lý phiên bản, với một chiến lược di trú sẵn sàng cho các thay đổi. Về triển vọng, với sketch học được, kết hợp quyền riêng tư vi phân, và tăng tốc phần cứng (xử lý tốc độ đường truyền) mở rộng phạm vi của CMS, giá trị của nó như một cấu trúc tóm lược tiêu chuẩn cho phân tích thời gian thực quy mô lớn sẽ còn mãi.
Tài liệu tham khảo
- Cormode, Muthukrishnan, "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" (2005): http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
- Redis — Tài liệu chính thức Count-Min Sketch: https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/
- Ben Mazziane, Marfoq, "Count-Min Sketch with Conservative Updates: Worst-Case Analysis" (2024): https://arxiv.org/abs/2405.12034
Tóm tắt một câu: Count-Min Sketch chồng các tần suất lên một mảng bộ đếm 2 chiều bằng d hàm băm và lấy giá trị nhỏ nhất khi truy vấn, xấp xỉ tần suất và heavy hitter mà không ước lượng thấp trong bộ nhớ hằng số độc lập với số khóa duy nhất.