Cấu trúc dữ liệu và Giải thuật Bài 82: Count-Min Sketch - Đếm tần suất phần tử (Frequency) trên luồng dữ liệu khổng lồ.

Ở các bài trước, chúng ta đã giải quyết bài toán "Tồn tại hay không?" (Bloom Filter) và "Có bao nhiêu phần tử độc lập?" (HyperLogLog). Trong hệ thống Big Data, còn một câu hỏi sinh tử thứ ba: "Phần tử này xuất hiện bao nhiêu lần?"

Giả sử tại Hasaki, hệ thống cần theo dõi Top 100 sản phẩm được xem nhiều nhất trong một đợt Flash Sale, hoặc hệ thống tường lửa (WAF) cần đếm số lượng request từ từng địa chỉ IP để chặn đứng các cuộc tấn công DDoS (Heavy Hitters).

• Nếu dùng Hash Map map[string]int để đếm, với 1 tỷ IP hoặc thao tác, hệ thống sẽ bị tràn RAM ngay lập tức.

• HyperLogLog không giúp được vì nó chỉ đếm tổng số phần tử độc lập, chứ không đếm tần suất của từng cá thể.

Để giải quyết bài toán đếm tần suất trong không gian RAM cực kỳ giới hạn (ví dụ: chỉ 2MB), năm 2003, Cormode và Muthukrishnan đã phát minh ra Count-Min Sketch (CMS). Đây là một cấu trúc dữ liệu xác suất kết hợp sức mạnh của Bloom Filter và nguyên lý "lấy giá trị nhỏ nhất" để khử nhiễu.

1. Cơ chế Hoạt động: Ma trận Đếm (2D Array)

Thay vì dùng một mảng bit 1 chiều như Bloom Filter, Count-Min Sketch sử dụng một Ma trận 2 chiều (2D Array) gồm $D$ hàng và $W$ cột, trong đó mỗi ô lưu trữ một số nguyên (Counter). Đi kèm với nó là $D$ hàm băm độc lập (mỗi hàng sử dụng một hàm băm riêng).

A. Thao tác Thêm (Add):

Khi một sự kiện xảy ra (ví dụ: User A xem một sản phẩm):

1. Hệ thống đưa "User A" qua $D$ hàm băm để nhận về $D$ giá trị (từ $0$ đến $W-1$).

2. Mỗi giá trị này tương ứng với một cột trên một hàng cụ thể.

3. Hệ thống cộng thêm 1 vào các ô tọa độ đó.

B. Thao tác Đếm/Truy vấn (Estimate):

Khi muốn biết "User A" đã xem bao nhiêu lần:

1. Hệ thống lại băm "User A" qua $D$ hàm băm để tìm ra $D$ tọa độ ô nhớ tương ứng.

2. Do hiện tượng đụng độ (Collision) của hàm băm, các ô này chắc chắn đã bị cộng dồn bởi các Users khác. Nghĩa là giá trị tại các ô này luôn luôn lớn hơn hoặc bằng số lần xem thực sự của User A (Overestimation).

3. Bí quyết của Count-Min Sketch nằm ở chữ "Min": Thuật toán quét qua $D$ ô đó và trả về giá trị nhỏ nhất (Minimum). Bằng cách lấy giá trị nhỏ nhất, nó đã loại bỏ được lượng nhiễu lớn nhất sinh ra do đụng độ từ các phần tử khác.

3. Triển khai Count-Min Sketch bằng Golang

Đoạn code sau cài đặt CMS với cơ chế giả lập nhiều hàm băm thông qua thuật toán FNV-1a và trộn seed (giống cách làm ở Bloom Filter).

Go

package main

import (
	"fmt"
	"hash/fnv"
	"math"
)

// Cấu trúc Count-Min Sketch
type CountMinSketch struct {
	width  uint32     // Số cột (W) - Ảnh hưởng đến sai số (epsilon)
	depth  uint32     // Số hàng (D) - Ảnh hưởng đến xác suất độ tin cậy (delta)
	matrix [][]uint32 // Ma trận 2D lưu các Counter
}

// Khởi tạo CMS với số hàng (depth) và số cột (width)
func NewCountMinSketch(width, depth uint32) *CountMinSketch {
	matrix := make([][]uint32, depth)
	for i := uint32(0); i < depth; i++ {
		matrix[i] = make([]uint32, width)
	}
	return &CountMinSketch{
		width:  width,
		depth:  depth,
		matrix: matrix,
	}
}

// Hàm băm phụ trợ: Sinh ra 'depth' giá trị hash độc lập
func (cms *CountMinSketch) getHashes(key string) []uint32 {
	hashes := make([]uint32, cms.depth)
	for i := uint32(0); i < cms.depth; i++ {
		h := fnv.New32a()
		// Sử dụng index i làm seed để tạo ra các hàm băm khác nhau
		h.Write([]byte(fmt.Sprintf("%s-%d", key, i)))
		hashes[i] = h.Sum32() % cms.width
	}
	return hashes
}

// Add: Tăng tần suất của phần tử lên 1
func (cms *CountMinSketch) Add(key string) {
	hashes := cms.getHashes(key)
	for i := uint32(0); i < cms.depth; i++ {
		// Tọa độ: Hàng i, Cột hash[i]
		col := hashes[i]
		cms.matrix[i][col]++
	}
}

// Estimate: Truy vấn ước lượng số lần xuất hiện
func (cms *CountMinSketch) Estimate(key string) uint32 {
	hashes := cms.getHashes(key)
	var minCount uint32 = math.MaxUint32

	for i := uint32(0); i < cms.depth; i++ {
		col := hashes[i]
		count := cms.matrix[i][col]
		// Thuật toán: Lấy giá trị nhỏ nhất (Min) giữa các ô bị băm
		if count < minCount {
			minCount = count
		}
	}
	return minCount
}

func main() {
	// Khởi tạo CMS với 5 hàng (hash functions) và 10,000 cột
	cms := NewCountMinSketch(10000, 5)

	// Giả lập luồng dữ liệu
	cms.Add("IP_192.168.1.1")
	cms.Add("IP_192.168.1.1")
	cms.Add("IP_192.168.1.1")

	cms.Add("IP_10.0.0.5")
	cms.Add("IP_10.0.0.5")
	
	// Thêm hàng ngàn IP khác để tạo đụng độ... (Bỏ qua trong ví dụ này)

	fmt.Printf("Tần suất ước lượng của IP_192.168.1.1: %d\n", cms.Estimate("IP_192.168.1.1"))
	fmt.Printf("Tần suất ước lượng của IP_10.0.0.5: %d\n", cms.Estimate("IP_10.0.0.5"))
	fmt.Printf("Tần suất ước lượng của IP_Chưa_Từng_Vào: %d\n", cms.Estimate("IP_Unknown"))
}

4. Phân tích Toán học và Hiệu năng (Big-O)

• Thời gian Truy vấn / Thêm (Time): $O(D)$ (với $D$ là số hàm băm/số hàng). Do $D$ thường rất nhỏ (từ 5 đến 10), thuật toán chạy với tốc độ xấp xỉ $O(1)$, đáp ứng được lưu lượng mạng Gigabit/s.

• Không gian RAM (Space): $O(W \times D)$. Để đếm tần suất của một mạng botnet tấn công có thể lên tới chục triệu IP, bạn chỉ cần khoảng $D = 5$ và $W = 50,000$. Tổng bộ nhớ cần thiết: $5 \times 50,000 \times 4 \text{ bytes (uint32)} \approx \mathbf{1 \text{ MB RAM}}$.

Kiểm soát sai số:

• Sai số luôn dương: CMS không bao giờ trả về số lượng nhỏ hơn thực tế (Không có False Negative). Nó chỉ có xu hướng báo cáo nhiều hơn thực tế do đụng độ.

• Để giảm sai số (tăng độ chính xác), hãy tăng chiều rộng $W$ (Số cột).

• Để tăng độ tin cậy của kết quả (giảm xác suất bị lệch nghiêm trọng), hãy tăng độ sâu $D$ (Số hàng).

5. Ứng dụng Thực tế trong Hệ thống Enterprise

Cùng với Bloom Filter và HyperLogLog, Count-Min Sketch là mảnh ghép thứ 3 hoàn thiện "Tam giác ma thuật" của các hệ thống Stream Processing hiện đại:

• Bộ đệm chống DDoS lớp 7 (Layer 7 WAF Mitigation): Khi có dấu hiệu bị DDoS HTTP, Nginx hoặc Envoy Load Balancer duy trì một cấu trúc CMS nhỏ trên RAM. Mỗi Request đi vào sẽ đẩy qua CMS. Nếu hàm Estimate(IP) vượt quá ngưỡng (ví dụ 1000 requests/s), hệ thống tự động gán cờ block IP đó (Rate Limiting khẩn cấp) mà không cần lưu trữ danh sách hàng triệu IP thật.

• Tìm kiếm Phần tử Nặng ký (Heavy Hitters / Top K): Sử dụng CMS kết hợp với một Min-Heap để duy trì bảng xếp hạng "Top 10 Hashtag thịnh hành nhất (Trending)" hoặc "Top 100 bài hát được nghe nhiều nhất" trên luồng dữ liệu liên tục của Twitter hoặc Spotify mà không cần đếm toàn bộ cơ sở dữ liệu.

• Tối ưu hóa Truy vấn Cơ sở Dữ liệu (Query Optimizer): RDBMS dùng CMS ngầm để ước lượng nhanh xem một từ khóa (Condition) có mang lại nhiều dòng kết quả hay không, từ đó quyết định xem nên dùng Index Search hay Full Table Scan để tối ưu thời gian.

Chúng ta đã khai thác triệt để các cấu trúc trên ổ đĩa và cấu trúc xác suất. Ở bài học tiếp theo, chúng ta sẽ quay trở lại với RAM và Cây, khám phá một biến thể của Linked List sử dụng xác suất để đạt được sức mạnh tìm kiếm ngang ngửa Cây nhị phân, nhưng lại dễ lập trình hơn cực kỳ nhiều.