HyperLogLog — đếm distinct xấp xỉ

3:58HyperLogLog: đếm 2 tỷ lượt truy cập bằng đúng 12 KB — cơ chế đầy đủ4 phút nắm ý chính · bài viết dưới đây là bản đầy đủ ~14 phút

TL;DR: Bài toán: đếm số phần tử khác nhau trong một luồng khổng lồ, ví dụ hôm nay có bao nhiêu người khác nhau ghé web, khi có 2 tỷ lượt và một người vào nhiều lần. Ghi nhớ từng người thì tốn nhiều GB. HyperLogLog đếm gần đúng (lệch chỉ vài phần trăm) mà chỉ tốn vài KB. Mẹo là biến mỗi phần tử thành một dãy bit trông như ngẫu nhiên, rồi chỉ ghi nhớ một con số về dãy "may mắn nhất" từng gặp. Càng nhiều phần tử khác nhau thì con số đó càng lớn, từ đó suy ngược ra số lượng. Redis dùng đúng cách này (PFADD/PFCOUNT, 12 KB). Số phần tử khác nhau gọi là cardinality.

Analytics pipeline của bạn cần trả lời: "Hôm nay có bao nhiêu unique user truy cập?" Dữ liệu: 2 tỷ event, mỗi event có user_id. COUNT(DISTINCT user_id) phải quét toàn bộ bảng, tốn vài phút; hash set mọi user_id tốn 2 tỷ × 8 byte = 16 GB RAM. Bạn chỉ cần con số "khoảng bao nhiêu" (sai 1-2% được), trả lời trong vài millisecond với vài KB.

1. Trực giác: trò chơi tung đồng xu

Bạn tung đồng xu liên tục; mỗi lượt là tung cho tới khi ra ngửa lần đầu, và đếm số sấp liên tiếp trước đó. "Ngửa" ngay = 0 sấp; "sấp, ngửa" = 1 sấp; "sấp, sấp, sấp, ngửa" = 3 sấp.

Giờ bạn chỉ nhớ một con số duy nhất: chuỗi sấp dài nhất từng thấy. Nếu con số đó là 10, bạn đã chơi khoảng bao nhiêu lượt? Để xuất hiện 10 sấp liên tiếp cần xác suất 1/2^10 ≈ 1/1000, nên bạn hẳn đã chơi khoảng 1000 lượt (2^10). Chỉ từ một con số, bạn ước lượng được tổng số lượt.

Ghép hai bên lại thì ra HyperLogLog:

Hash biến mỗi phần tử thành dãy bit trông ngẫu nhiên, và cùng phần tử luôn cho cùng dãy, nên phần tử giống nhau không tạo "lượt chơi mới": ta đếm số phần tử khác nhau. Chỉ giữ R_max, không lưu phần tử nào, nên tốn vài KB thay vì vài GB.

Vì sao mẹo này đúng (phần công thức)

Vì dãy bit trông như ngẫu nhiên, xác suất một dãy mở đầu bằng ít nhất r số 0 là 1/2^r (đúng bằng xác suất tung được r lần sấp liên tiếp). Với n phần tử khác nhau, số leading zero nhiều nhất quan sát được, R_max, thoả:

E[R_max] ≈ log2(n)      →      n ≈ 2^R_max

Xác suất KHÔNG phần tử nào đạt r leading zero là (1 - 1/2^r)^n, chuyển nhanh từ ~1 sang ~0 quanh n ≈ 2^r. Ví dụ n = 1.000.000 → kỳ vọng ~20 leading zero.

Vấn đề còn lại: một con số quá nhiễu — một phần tử "ăn may" 40 leading zero làm ước lượng sai gấp triệu lần.