Cấu trúc dữ liệu và Giải thuật Bài 81: HyperLogLog - Cấu trúc dữ liệu xác suất đếm số lượng phần tử độc lập (Cardinality) trên luồng dữ liệu khổng lồ.

Ở Bài 80, Bloom Filter đã giúp chúng ta giải quyết câu hỏi "Có hay Không?" (Membership) với bộ nhớ cực nhỏ. Nhưng khi vận hành các hệ thống Big Data tại Hasaki, bạn sẽ thường xuyên đối mặt với một câu hỏi hóc búa khác: "Có bao nhiêu phần tử ĐỘC LẬP (Unique / Distinct) trong luồng dữ liệu này?"

Ví dụ: Bạn cần đếm chính xác số lượng địa chỉ IP truy cập (Unique Visitors) vào website trong ngày hôm nay.

Nếu dùng một bảng băm (Hash Set) để lưu trữ tất cả các IP đã ghé thăm:

1 tỷ địa chỉ IP (IPv4) sẽ ngốn khoảng ~4GB RAM.
Nếu bạn cần theo dõi chỉ số này cho 10,000 danh mục sản phẩm khác nhau, máy chủ sẽ bốc cháy vì cần tới 40TB RAM.

Để giải quyết bài toán đếm (Cardinality) mà không làm sập RAM, năm 2007, Philippe Flajolet và các cộng sự đã công bố một thuật toán vĩ đại: HyperLogLog (HLL). Cấu trúc xác suất này có khả năng đếm lên tới hàng tỷ phần tử độc lập mà chỉ tiêu tốn đúng ~12KB RAM, với sai số cực nhỏ chỉ khoảng 0.81%.

1. Bí mật Toán học: Tung đồng xu và Đếm số lượng số 0 (Leading Zeros)

Hãy tưởng tượng bạn chơi trò tung đồng xu (Sấp/Ngửa).

Xác suất để tung được 1 mặt Ngửa là $1/2$ .
Xác suất để tung được 2 mặt Ngửa liên tiếp là $1/4$ .
Xác suất để tung được $K$ mặt Ngửa liên tiếp là $1/2^K$ .

Nếu một người bạn nói: "Tôi vừa tung được 5 mặt Ngửa liên tiếp", bạn có thể đoán ngay rằng anh ta phải tung đồng xu khoảng $2^5 = 32$ lần thì mới may mắn trúng được chuỗi đó.

HyperLogLog áp dụng nguyên lý này vào luồng dữ liệu (Stream) thông qua các Hàm băm (Hash Functions):

Băm mỗi IP (hoặc User ID) vào một chuỗi nhị phân 64-bit phân phối hoàn toàn ngẫu nhiên. (Ví dụ: 0100101...).
Thuật toán đếm số lượng bit 0 liên tiếp tính từ phải sang trái (Leading Zeros hoặc Trailing Zeros, tùy cấu hình). Gọi con số này là $R$ .
Nếu trong toàn bộ luồng dữ liệu, chuỗi có nhiều số 0 liên tiếp nhất mà bạn quan sát được là $R_{max} = 10$ , thuật toán sẽ ước lượng rằng đã có khoảng $2^{10} = 1,024$ phần tử độc lập đi qua hệ thống.

2. Giải quyết Sai số bằng Phân mảnh (Stochastic Averaging)

Vấn đề của thuật toán tung đồng xu bên trên là phương sai (Variance) quá lớn. Lỡ như ngay ở phần tử thứ 3, bạn gặp may mắn "trúng quả" một chuỗi hash có tận 20 số 0? Hệ thống sẽ báo cáo có 1 triệu visitor dù thực tế mới có 3 người!

Để làm mịn kết quả, HyperLogLog sử dụng kỹ thuật Phân mảnh không gian (Bucketing / Registers):

Nó không dùng một biến duy nhất để lưu $R_{max}$ . Thay vào đó, nó tạo ra một mảng gồm $m$ thanh ghi (Registers), thường $m = 16,384$ (hay $2^{14}$ ).
Khi có một chuỗi hash 64-bit đi vào, nó lấy 14 bit đầu tiên làm "địa chỉ" để chọn ra 1 trong 16,384 thanh ghi đó.
50 bit còn lại được dùng để đếm số lượng số 0 liên tiếp, và lưu vào thanh ghi tương ứng (chỉ cập nhật nếu số 0 hiện tại lớn hơn số đang lưu trong thanh ghi).

Cuối cùng, thuật toán tính Trung bình điều hòa (Harmonic Mean) của tất cả $m$ thanh ghi. Harmonic Mean có đặc tính tự động "kéo chìm" các giá trị ngoại lai (outliers) quá cao, mang lại kết quả cực kỳ ổn định.

$E = \alpha_m \cdot m^2 \cdot \left( \sum_{j=1}^{m} 2^{-R_j} \right)^{-1}$

(Trong đó $\alpha_m$ là hằng số hiệu chỉnh bias).

4. Triển khai HyperLogLog cơ bản bằng Golang

Đoạn code dưới đây cài đặt một phiên bản HyperLogLog thu gọn, sử dụng mảng byte để làm thanh ghi. Với $m = 16,384$ , toàn bộ cấu trúc chỉ tốn đúng 16 KB RAM.

package main

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

const (
	P          = 14             // Số bit dùng làm Index thanh ghi (14 bit)
	M          = 1 << P         // Số lượng thanh ghi (2^14 = 16384)
	AlphaM     = 0.7213 / (1 + 1.079/float64(M)) // Hằng số hiệu chỉnh
)

type HyperLogLog struct {
	registers []uint8 // Mỗi thanh ghi chỉ cần 1 byte (vì số lượng số 0 tối đa là 64-14=50)
}

func NewHyperLogLog() *HyperLogLog {
	return &HyperLogLog{
		registers: make([]uint8, M),
	}
}

// Băm phần tử thành số nguyên 64-bit
func getHash(data string) uint64 {
	h := fnv.New64a()
	h.Write([]byte(data))
	return h.Sum64()
}

// Thêm phần tử vào HyperLogLog
func (hll *HyperLogLog) Add(data string) {
	hash := getHash(data)

	// Lấy P bit đầu tiên làm chỉ mục thanh ghi (Bucket Index)
	idx := hash >> (64 - P)
	
	// Xóa P bit đầu đi để lấy phần còn lại đếm số 0
	w := hash << P

	// Tính số lượng số 0 liên tiếp tính từ bit cao nhất (Leading Zeros)
	// Bắt buộc cộng 1 vì xác suất cơ sở của chuỗi đếm
	zeros := uint8(bits.LeadingZeros64(w)) + 1

	// Cập nhật thanh ghi: Chỉ lưu giá trị lớn nhất
	if zeros > hll.registers[idx] {
		hll.registers[idx] = zeros
	}
}

// Ước lượng số lượng phần tử độc lập (Cardinality)
func (hll *HyperLogLog) Count() int64 {
	sum := 0.0
	zeroRegisters := 0

	// Tính tổng nghịch đảo theo công thức Harmonic Mean
	for _, val := range hll.registers {
		sum += 1.0 / math.Pow(2.0, float64(val))
		if val == 0 {
			zeroRegisters++
		}
	}

	estimate := AlphaM * float64(M) * float64(M) / sum

	// Hiệu chỉnh đếm tuyến tính (Linear Counting) cho các tập hợp nhỏ
	if estimate <= 2.5*float64(M) && zeroRegisters > 0 {
		estimate = float64(M) * math.Log(float64(M)/float64(zeroRegisters))
	}

	return int64(estimate)
}

func main() {
	hll := NewHyperLogLog()

	// Giả lập luồng 1 triệu lượt truy cập, nhưng chỉ có 500,000 user độc lập
	fmt.Println("Đang bơm dữ liệu vào HyperLogLog...")
	uniqueCount := 500000
	
	for i := 0; i < uniqueCount; i++ {
		user := fmt.Sprintf("user_%d", i)
		hll.Add(user) // Lượt truy cập đầu tiên
		hll.Add(user) // Lượt truy cập lặp lại (không làm tăng count)
	}

	estimated := hll.Count()
	fmt.Printf("Số lượng Unique User thực tế: %d\n", uniqueCount)
	fmt.Printf("HyperLogLog ước lượng:     %d\n", estimated)
	
	errorRate := math.Abs(float64(estimated-int64(uniqueCount))) / float64(uniqueCount) * 100
	fmt.Printf("Sai số: %.2f%%\n", errorRate)
}

5. Phân tích Hiệu năng và Ứng dụng Thực tế

Bộ nhớ siêu việt (Space): Một tập hợp HLL chuẩn sử dụng $M = 16,384$ thanh ghi 8-bit. Tổng dung lượng chiếm đúng 16,384 Bytes $\approx$ 16 KB. Với 16KB, nó có thể đếm một cách tin cậy lên tới $10^9$ (1 tỷ) phần tử.
Thời gian (Time): $O(1)$ cho mỗi lần gọi hàm Add(). Các phép toán bitwise (shift, đếm leading zeros) chạy trực tiếp trên CPU Register với tốc độ tính bằng nano-giây.

Ứng dụng trong Hạ tầng Backend:

Redis (PFADD, PFCOUNT): Các lệnh tiền tố PF trong Redis chính là viết tắt của Philippe Flajolet (cha đẻ thuật toán). Redis tích hợp sẵn HLL để đếm Unique Views cho các bài viết, livestream, hoặc sản phẩm một cách cực rẻ.
Database Query Optimizer (MySQL, PostgreSQL): Khi thực hiện lệnh JOIN giữa các bảng, hệ quản trị cơ sở dữ liệu cần biết xấp xỉ có bao nhiêu giá trị độc lập trong cột để lên kế hoạch thực thi (Execution Plan) tốt nhất. Việc quét toàn bảng để đếm là quá đắt, thay vào đó chúng duy trì các cấu trúc HLL ngầm.
Hệ thống Phân tích Big Data (Google BigQuery, Datadog): Đếm số lượng thiết bị độc lập (Unique Devices) phát sinh lỗi (Errors) trong một phút đối với các luồng dữ liệu cỡ hàng Terabytes.

Cùng với Bloom Filter, HyperLogLog là đại diện xuất sắc nhất của Thuật toán Xác suất (Probabilistic Algorithms). Khi vượt qua rào cản về tính "chính xác tuyệt đối 100%", chúng ta mở ra cánh cửa thiết kế các hệ thống vĩ mô vượt qua giới hạn của RAM và phần cứng.

cấu trúc dữ liệu

1. Bí mật Toán học: Tung đồng xu và Đếm số lượng số 0 (Leading Zeros)

2. Giải quyết Sai số bằng Phân mảnh (Stochastic Averaging)

4. Triển khai HyperLogLog cơ bản bằng Golang

5. Phân tích Hiệu năng và Ứng dụng Thực tế

Mục lục