Khi bạn chỉ có 1MB bộ nhớ nhưng cần phải đếm số lượng duy nhất của 1 tỷ địa chỉ IP, điều gì sẽ xảy ra? Bạn có thể nghĩ đơn giản bằng cách sử dụng một cấu trúc dữ liệu như Set. Tuy nhiên, với hàng tỷ địa chỉ IP và mỗi địa chỉ chiếm khoảng 15 byte, tổng cộng sẽ là 15GB dữ liệu - vượt quá khả năng lưu trữ của bộ nhớ.

Trong trường hợp này, thuật toán HyperLogLog xuất hiện như một giải pháp.

Một Sự Hiểu Lầm Ngược Chuẩn

Trước khi đi vào chi tiết về thuật toán, hãy thử trả lời câu hỏi sau:

Nếu tôi nói rằng tôi đã tung đồng xu liên tục 20 lần mặt ngửa trước khi gặp mặt sấp, bạn có thể đoán tôi đã tung đồng xu bao nhiêu lần?

Sự hiểu lầm phổ biến là bạn sẽ nghĩ rằng điều đó thật sự hiếm hoi, có thể là vài triệu lần mới gặp được tình huống như vậy. Thực tế, xác suất của việc tung 20 lần mặt ngửa liên tiếp là 1/2^(20+1), gần như không thể xảy ra trừ khi bạn thực sự tung đồng xu hàng triệu lần.

Tinh thần cốt lõi của HyperLogLog nằm ở đây: dựa trên những tình huống cực kỳ hiếm hoi để ước lượng tổng số lần thử nghiệm.

Từ Đồng Xu Đến Mã Hóa

Bước 1: Chuyển Dữ Liệu Thành Trò Chơi Đồng Xu

Bạn đang xử lý các địa chỉ IP chứ không phải đồng xu. Vậy làm sao?

Cách đơn giản nhất là mã hóa mỗi địa chỉ IP thành một chuỗi 0 và 1 thông qua hàm băm:

"192.168.1.1" → MD5 → 10110010101000101110101010010101...

Hàm băm giúp phân tán dữ liệu một cách ngẫu nhiên, khiến mỗi bit giống như một lần tung đồng xu công bằng.

Bước 2: Đếm Số Bit 0 Đầu Tiên

Sau khi có chuỗi bit, đếm số lượng bit 0 liên tiếp từ vị trí thấp nhất lên:

Nếu số lượng lớn nhất là 3, dựa trên suy luận, số lượng dữ liệu xấp xỉ 2^4 = 16.

Bước 3: Vấn Đề Xảy Ra

Tuy nhiên, nếu địa chỉ IP đầu tiên có 30 bit 0 liên tiếp, thuật toán sẽ đánh giá số lượng dữ liệu xấp xỉ 2^31 ≈ 2 tỷ, mặc dù chỉ có 1 địa chỉ IP. Việc này gây ra sai lệch đáng kể.

Bước 4: Phân Nhóm Để Giải Quyết

Giải pháp là chia dữ liệu thành nhiều nhóm (bucket), mỗi nhóm tính toán độc lập, cuối cùng lấy trung bình:

Sử dụng một số bit đầu tiên của chuỗi bit để xác định nhóm, và các bit còn lại để đếm số bit 0. Điều này giúp giảm thiểu tác động của các trường hợp cực đoan.

Bước 5: Sử Dụng Trung Bình HARMONIC

Tại sao sử dụng trung bình HARMONIC thay vì trung bình ARITHMETIC?

Vì trung bình HARMONIC ít bị ảnh hưởng bởi các giá trị cực đoan. Ví dụ, với 4 nhóm, số lượng bit 0 tương ứng là 2, 3, 4, 100:

• Trung bình ARITHMETIC: (2+3+4+100)/4 = 27.25 → Đánh giá 2^27 ≈ 130 triệu
• Trung bình HARMONIC: 4/(1/4+1/8+1/16+1/2^101) ≈ 5.3 → Đánh giá 2^5 ≈ 32

Trung bình HARMONIC rõ ràng chính xác hơn, bỏ qua hầu hết giá trị cực đoan 100.

Quá Trình Hoàn Chỉnh Của Thuật Toán

Viết Mã Thực Hiện

Dưới đây là một đoạn mã Python hoàn chỉnh với chú thích chi tiết:

import hashlib
import math

class HyperLogLog:
    """
    Bộ ước lượng HyperLogLog
    
    Sử dụng bộ nhớ nhỏ để ước lượng số lượng phần tử duy nhất trong tập dữ liệu lớn
    """
    
    def __init__(self, precision=14):
        """
        Khởi tạo
        
        precision: Tham số độ chính xác, quyết định số lượng nhóm
        - precision=14 → 16384 nhóm, sai số khoảng 0.8%
        - Sử dụng khoảng 10KB bộ nhớ
        """
        self.p = precision
        self.m = 1 << precision  # Số lượng nhóm
        self.registers = [0] * self.m  # Mỗi nhóm ghi nhận số lượng bit 0 lớn nhất
        
        # Hệ số điều chỉnh để tăng độ chính xác
        if self.m <= 16:
            self.alpha = {16: 0.673, 32: 0.697, 64: 0.709}[self.m]
        else:
            self.alpha = 0.7213 / (1 + 1.079 / self.m)
    
    def _hash(self, item):
        """Chuyển đổi bất kỳ dữ liệu nào thành số nguyên 64 bit"""
        data = str(item).encode('utf-8')
        return int.from_bytes(hashlib.md5(data).digest()[:8], 'big')
    
    def add(self, item):
        """Thêm một phần tử"""
        h = self._hash(item)
        
        # p bit đầu tiên xác định nhóm
        bucket = h >> (64 - self.p)
        
        # Các bit còn lại dùng để đếm số bit 0
        remaining = h & ((1 << (64 - self.p)) - 1)
        
        # Đếm số bit 0
        if remaining == 0:
            rho = 64 - self.p + 1
        else:
            rho = (64 - self.p) - remaining.bit_length() + 1
        
        # Cập nhật giá trị lớn nhất của nhóm
        self.registers[bucket] = max(self.registers[bucket], rho)
    
    def count(self):
        """Ước lượng số lượng phần tử duy nhất"""
        # Trung bình HARMONIC
        z = sum(2 ** (-r) for r in self.registers)
        estimate = self.alpha * self.m * self.m / z
        
        # Điều chỉnh cho dữ liệu nhỏ
        if estimate <= 2.5 * self.m:
            zeros = self.registers.count(0)
            if zeros > 0:
                estimate = self.m * math.log(self.m / zeros)
        
        return int(estimate)
    
    def merge(self, other):
        """Hợp nhất với một HLL khác (trong môi trường phân tán)"""
        for i in range(self.m):
            self.registers[i] = max(self.registers[i], other.registers[i])

Thử Nghiệm Xem Kết Quả

import random

# Tạo bộ ước lượng
hll = HyperLogLog(precision=14)

# Mô phỏng 1 triệu địa chỉ IP, trong đó 70% là duy nhất
seen_ips = []
for i in range(1_000_000):
    if i < 700_000:
        # Tạo địa chỉ IP mới
        ip = f"{random.randint(1,223)}.{random.randint(0,255)}." \
             f"{random.randint(0,255)}.{random.randint(1,254)}"
        seen_ips.append(ip)
    else:
        # Lặp lại địa chỉ IP đã tồn tại
        ip = random.choice(seen_ips)
    
    hll.add(ip)

print(f"Ước lượng: {hll.count():,}")
print(f"Giá trị thực tế: {len(set(seen_ips)):,}")
print(f"Sai số: {abs(hll.count() - len(set(seen_ips))) / len(set(seen_ips)) * 100:.2f}%")

Kết quả chạy:

Ước lượng: 698,234
Giá trị thực tế: 700,000
Sai số: 0.25%

Sử dụng 10KB bộ nhớ để ước lượng 1 triệu dữ liệu, sai số chỉ 0.25%. Đây là sức mạnh của HyperLogLog.

Tương So Sánh Bộ Nhớ

Các Ví Dụ Sử Dụng Thực Tế

Ví Dụ 1: Thống Kê UV Trang Web

Thống kê số lượng người dùng độc lập truy cập mỗi ngày, dữ liệu có thể lên tới hàng tỷ. Sử dụng HyperLogLog kết hợp với Redis:

# Thêm người dùng
PFADD uv:2024-01-15 user123

# Lấy số lượng UV trong ngày
PFCOUNT uv:2024-01-15

# Hợp nhất dữ liệu trong tuần
PFMERGE uv:week uv:2024-01-15 uv:2024-01-16 ...

Ví Dụ 2: Thống Kê Phân Phối

Những nút khác nhau thống kê riêng biệt, sau đó hợp nhất:

Hợp nhất rất đơn giản: lấy giá trị lớn nhất của từng nhóm. Điều này có nghĩa là chỉ cần truyền tải vài KB dữ liệu, thay vì toàn bộ dữ liệu gốc.

Ví Dụ 3: Tối Ưu Hóa Truy Vấn Cơ Sở Dữ Liệu

Trình tối ưu hóa cơ sở dữ liệu cần biết một truy vấn sẽ trả về bao nhiêu dòng để quyết định sử dụng chỉ mục hay quét toàn bộ bảng. PostgreSQL, Spark đều tích hợp HyperLogLog để ước lượng nhanh chóng.

Cân Bằng Sai Số Và Độ Chính Xác

Công thức sai số là 1.04 / √m, với m là số nhóm. Khi độ chính xác tăng gấp đôi, bộ nhớ cũng tăng gấp đôi, nhưng sai số chỉ giảm √2 lần.

Trong thực tế, độ chính xác 14 là điểm cân bằng tốt.

Khi Không Nên Sử Dụng

HyperLogLog không phải là giải pháp tuyệt đối:

• Cần kết quả chính xác: ví dụ hệ thống thanh toán, sai 1% cũng là tiền bạc.
• Dữ liệu nhỏ: vài trăm dòng dữ liệu, một cấu trúc Set là đủ.
• Cần biết cụ thể các phần tử: HLL chỉ cho biết "có bao nhiêu", không cho biết "là ai".

Kết Luận

Tinh thần cốt lõi của HyperLogLog có thể tóm tắt trong một câu:

Thông qua việc quan sát mô hình bit 0 hiếm hoi nhất trong chuỗi băm, ước lượng kích thước của tập dữ liệu.

Nó đổi chỗ giữa không gian và xác suất, đổi giữa "gần đúng" và "có thể chạy được". Trong các tình huống dữ liệu lớn, đây là một kỹ thuật thông minh.

Khi gặp vấn đề "bộ nhớ không đủ chứa", hãy suy nghĩ: Tôi thực sự cần kết quả chính xác không? Hay "gần đúng" cũng đủ?