HyperLogLog (Ước lượng lực lượng tập hợp)
1. Tổng quan
A. Định nghĩa
HyperLogLog (HLL) là một cấu trúc dữ liệu và thuật toán xác suất (probabilistic) ước lượng xấp xỉ số lượng phần tử khác nhau — tức lực lượng tập hợp (cardinality, số phần tử duy nhất) — trong một luồng dữ liệu quy mô lớn mà không lưu toàn bộ phần tử, bằng bộ nhớ gần như hằng số (vài KB), suy ngược ra kích thước tập hợp từ một đại lượng thống kê: số lượng tối đa các bit 0 dẫn đầu (leading zeros) quan sát được trong giá trị băm của mỗi phần tử.
HyperLogLog trả lời câu hỏi "có bao nhiêu giá trị khác nhau trong tập hợp này (COUNT DISTINCT)?". Để đếm chính xác thì phải giữ mọi phần tử duy nhất đã thấy trong một tập hợp (HashSet), nên bộ nhớ tăng tỷ lệ với số phần tử n (O(n)) và bùng nổ. Thay vào đó HLL không lưu phần tử nào và chỉ để lại dấu vết — "một mẫu băm hiếm đến mức nào đã xuất hiện" — trong một mảng thanh ghi có kích thước cố định. Kết quả là dù có 1 phần tử hay một tỷ phần tử, bộ nhớ vẫn không đổi (ví dụ khoảng 12KB), đổi lại chấp nhận sai số tương đối ở mức vài %. Khác với [[bloom-filter]] đã bàn ở trước vốn xấp xỉ "sự thuộc về", HLL xấp xỉ "số lượng", khiến chúng là các cấu trúc dữ liệu xác suất bổ trợ cho nhau.
Tính chất của HLL có thể tóm lại thành ba điểm. Thứ nhất, bộ nhớ cố định bất kể quy mô đầu vào (không gian hằng số). Thứ hai, xử lý mỗi phần tử chỉ gồm một lần băm và một lần cập nhật thanh ghi, nên thao tác chèn là O(1) và rất nhanh. Thứ ba, hai hoặc nhiều sketch có thể hợp nhất không mất mát, phù hợp tự nhiên với tổng hợp phân tán. Đổi lại, kết quả là xấp xỉ, và nó không phù hợp để xóa một phần tử cụ thể hay tính giao chính xác. Chính bó đánh đổi này quyết định phạm vi áp dụng của HLL.
B. Bối cảnh ra đời và sự cần thiết
Khi môi trường web, di động và IoT lớn lên, các phép tổng hợp đếm duy nhất như "số khách truy cập duy nhất (Unique Visitor)", "số từ khóa tìm kiếm duy nhất", "số IP khác nhau đã kết nối", "số sự kiện sau khử trùng lặp" đã trở thành chỉ số then chốt. Nhưng phép toán này vốn dĩ đắt đỏ. COUNT DISTINCT chính xác phải loại trùng nên phải ghi nhớ mọi giá trị đã thấy, và để đếm người dùng duy nhất từ hàng tỷ bản ghi nhật ký mỗi ngày cần vài GB đến vài chục GB bộ nhớ. Ở các dashboard và hệ thống quảng cáo phải tổng hợp hàng nghìn chỉ số đồng thời và theo thời gian thực, chi phí này chuyển trực tiếp thành chi phí hạ tầng và độ trễ.
HyperLogLog khai thác về mặt kỹ thuật thực tế kinh doanh rằng "không cần con số chính xác; mức ±2% là đủ." Việc khách truy cập duy nhất là 1.000.230 hay 1.000.235 người không ảnh hưởng đến quyết định, nên đánh đổi sai số nhỏ để tiết kiệm hàng nghìn đến hàng triệu lần bộ nhớ là hợp lý. Đặc biệt HLL có lợi thế quyết định là hợp nhất (merge) dễ dàng: các kết quả tổng hợp riêng theo khu vực, thời gian, máy chủ có thể gộp không mất mát để có "tổng số duy nhất toàn cục". Nhờ tính cộng tính (additivity) này, nó đã trở thành 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ề bản chất là đắt đỏ sẽ làm rõ giá trị của HLL. COUNT DISTINCT phải xác định "đã thấy giá trị này chưa?" mỗi lần, nên để chính xác thì phải hoặc giữ toàn bộ giá trị duy nhất trong bộ nhớ (HashSet) hoặc sắp xếp/xáo trộn toàn bộ tập (tổng hợp phân tán). Trong môi trường mở rộng theo chiều ngang, trạng thái toàn phần này đụng cùng lúc hai bức tường: giới hạn bộ nhớ mỗi nút và chi phí xáo trộn mạng. HLL né hai bức tường này bằng nhận thức rằng nếu tất cả những gì cần chỉ là đại lượng thống kê duy nhất "số đếm duy nhất" thì không có lý do gì phải nhớ từng phần tử. Điều này giống như lồng vào cấu trúc dữ liệu ý tưởng thống kê về ước lượng tổng thể từ mẫu thay vì tổng điều tra.
2. Nguyên lý hoạt động và trực giác
Trực giác cốt lõi của HyperLogLog được ví như tung đồng xu. Một chuỗi bit đã đi qua hàm băm công bằng trông như một dãy ngẫu nhiên mà mỗi vị trí là 0/1 đồng nhất, độc lập. Xác suất một chuỗi bit bắt đầu bằng k số 0 liên tiếp từ đầu là (1/2)^k. Do đó, nếu bạn "đã thấy ít nhất một lần một mẫu có k số 0 dẫn đầu liên tiếp", bạn có thể ước lượng mình đã quan sát khoảng 2^k giá trị khác nhau — mẫu càng hiếm càng là bằng chứng rằng đã rút nhiều.
Diễn đạt trực giác này theo đời thường thì giống như đoán rằng hẳn đã tung đồng xu khá nhiều lần nếu chứng kiến "mười mặt ngửa liên tiếp". Điều quan trọng là ước lượng này không bị ảnh hưởng bởi trùng lặp. Dù cùng một phần tử đến 100 lần, giá trị băm của nó như nhau nên số số 0 dẫn đầu không đổi; vì vậy HLL nắm bắt không phải "đã đến bao nhiêu lần (tần suất)" mà chỉ "các mẫu xuất hiện đa dạng đến mức nào (tính duy nhất)". Chính tính chất này là nguyên lý gốc cho phép nó lọc trùng lặp và chỉ đếm phần tử duy nhất mà không lưu phần tử. Tuy nhiên chỉ một quan sát đơn lẻ có phương sai quá lớn (vì chỉ ước lượng được theo lũy thừa của 2) để dùng ngay, và việc lấy trung bình theo bucket dưới đây là thiết yếu.
flowchart LR
X["phần tử đầu vào x"] --> HASH["hàm băm h(x) → 64 bit"]
HASH --> SPLIT["b bit cao: chỉ số thanh ghi j"]
HASH --> REST["bit còn lại: số 0 dẫn đầu +1 = ρ"]
SPLIT --> REG["thanh ghi M[j]"]
REST --> UPD["M[j] ← max(M[j], ρ)"]
UPD --> REG
Thuật toán thực tế dùng lấy trung bình ngẫu nhiên (stochastic averaging) để giảm phương sai ước lượng. Nó chọn một trong 2^b = m bucket (thanh ghi) bằng b bit cao của giá trị băm, tính ρ từ các bit còn lại là số số 0 dẫn đầu cộng một, và chỉ lưu giá trị lớn nhất tích lũy vào thanh ghi đó. Nghĩa là mỗi thanh ghi nhớ "cường độ của mẫu hiếm nhất trong số các giá trị rơi vào bucket này". Dù một phần tử đến nhiều lần, giá trị lớn nhất của ρ không đổi nên trùng lặp tự động bị bỏ qua — đó là lý do chỉ số đếm duy nhất được đếm.
Lực lượng cuối cùng được ước lượng bằng trung bình điều hòa (harmonic mean) của m giá trị thanh ghi. Việc dùng trung bình điều hòa thay cho trung bình cộng là cải tiến cốt lõi đã nâng LogLog lên HyperLogLog, vì trung bình điều hòa kìm hãm ảnh hưởng của các giá trị thanh ghi lớn bất thường (giá trị ngoại lai) và giảm mạnh phương sai ước lượng.
flowchart TB
A["m thanh ghi M[0..m-1]"] --> B["Z = (Σ 2^(-M[j]))^(-1) : hạng trung bình điều hòa"]
B --> C["raw E = alpha_m · m^2 · Z"]
C --> D{"hiệu chỉnh ước lượng"}
D -->|"khi E nhỏ (E ≤ 2.5m)"| E1["ước lượng lại bằng LinearCounting"]
D -->|"khoảng giữa"| E2["dùng raw E"]
D -->|"rất lớn (gần giới hạn 32 bit)"| E3["hiệu chỉnh cận trên"]
E1 --> OUT["ước lượng lực lượng cuối cùng"]
E2 --> OUT
E3 --> OUT
Công thức ước lượng có dạng E = α_m · m² · (Σ_{j} 2^(−M[j]))^(−1), trong đó α_m là hằng số hiệu chỉnh độ lệch (bias) của ước lượng (với m lớn, α_m ≈ 0.7213/(1+1.079/m)). Tuy nhiên khi số phần tử quá nhỏ so với số thanh ghi m (nhiều thanh ghi vẫn trống ở 0), công thức này cho sai số lớn, nên ở khoảng lực lượng nhỏ này nó chuyển sang Linear Counting vốn dùng "tỷ lệ thanh ghi bằng 0" để hiệu chỉnh ước lượng.
A. Ví dụ chèn theo từng bước
Cụ thể hóa hoạt động bằng một ví dụ nhỏ sẽ làm sắc nét trực giác. Giả sử ta chỉ đặt m = 4 thanh ghi (đánh chỉ số bằng 2 bit cao). Mọi thanh ghi khởi tạo bằng 0. Nếu băm phần tử x cho 2 bit cao 10 (= bucket 2) và các bit còn lại 0010…, thì có 2 số 0 dẫn đầu ở phần còn lại nên ρ = 2+1 = 3 và M[2] ← max(0, 3) = 3. Nếu phần tử tiếp theo y có 2 bit cao 00 (bucket 0) và phần còn lại 1…, thì có 0 số 0 dẫn đầu nên ρ = 1 và M[0] ← 1. Dù cùng x đến lần nữa, M[2] vẫn là max(3,3) = 3, nên trùng lặp được hấp thụ một cách tự nhiên. Theo cách này mỗi bucket chỉ nhớ tích lũy "cường độ của mẫu hiếm nhất" trong số các giá trị nó nhận.
Điểm then chốt là giá trị của một bucket tỷ lệ với logarit số phần tử của bucket đó. Đó là lý do tên cấu trúc dữ liệu chứa "Log", và vì một thanh ghi chỉ chứa số số 0 dẫn đầu (= một giá trị log), một thanh ghi chỉ cần 5–6 bit. Gộp các giá trị log của m bucket qua trung bình điều hòa sẽ ra logarit của lực lượng toàn cục, rồi nhân với hằng số hiệu chỉnh để khôi phục giá trị ước lượng thực. Tóm lại, triết lý thiết kế của HLL là giảm phương sai lớn của một quan sát đơn lẻ xuống mức 1/√m bằng cách thu thập phân tán bằng chứng thống kê "đã thấy một mẫu hiếm = đã rút nhiều" trên m bucket rồi lấy trung bình.
3. Thiết kế độ chính xác/bộ nhớ và trường hợp Redis
Sai số chuẩn tương đối (standard error) của HLL được cho là khoảng 1.04/√m theo số thanh ghi m. Nghĩa là để tăng gấp đôi độ chính xác (giảm sai số đi một nửa) phải tăng thanh ghi lên bốn lần, nên bộ nhớ và độ chính xác tạo thành một đánh đổi quan hệ bình phương. Không ngoa khi nói quan hệ này là toàn bộ thiết kế HLL.
Các con số cụ thể làm rõ cảm nhận thiết kế. Giả sử băm 64 bit, số số 0 dẫn đầu lưu trong mỗi thanh ghi tối đa khoảng hơn 50, nên 6 bit là đủ. Với m = 2^14 = 16.384 thanh ghi, bộ nhớ là 16.384 × 6 bit ≈ khoảng 12KB, và sai số chuẩn là 1.04/√16384 = 1.04/128 ≈ khoảng 0,81%. Đây chính là cấu hình HyperLogLog của Redis — nó đếm các giá trị duy nhất ở quy mô hàng tỷ với sai số dư 1% chỉ bằng 12KB. Làm cùng công việc bằng tập chính xác sẽ tốn vài chục byte mỗi phần tử và cần vài GB, nên đây là tiết kiệm bộ nhớ hàng trăm nghìn lần trở lên.
Điều quan trọng là hiểu chính xác "sai số chuẩn 0,81%" nghĩa là gì. Đây là sai số kỳ vọng một sigma (1σ), không phải cận trên được bảo đảm. Nghĩa là khi giá trị thực là 10 triệu, ước lượng rơi vào khoảng ±khoảng 80.000 (0,81%) trung bình, nhưng hiếm khi có thể lệch tới 2–3 lần mức đó. Trong thực tế, hãy diễn giải thận trọng là "khoảng ±1%", và nếu một chỉ số rất nhạy thì an toàn hơn là tăng m để có dự phòng. Ngoài ra, một điểm thiết kế then chốt là tăng số bit mỗi thanh ghi hầu như không ảnh hưởng độ chính xác và chỉ số thanh ghi m chi phối độ chính xác — số bit chỉ đặt số số 0 dẫn đầu tối đa (= quy mô tối đa) có thể chứa.
Tham số thực tế thường chọn số thanh ghi log b (= log₂m) từ 4 đến 16. Nếu b nhỏ (ví dụ b=10, m=1024), bộ nhớ giảm xuống vài trăm byte nhưng sai số tăng tới khoảng 3%; nếu b lớn (ví dụ b=16, m=65536), bộ nhớ tăng lên 48KB nhưng sai số co lại còn 0,4%. Vận hành mỗi chỉ số ở độ chính xác nào được quyết bởi lựa chọn b này, và trong hệ thống duy trì hàng nghìn chỉ số cùng lúc, việc phân bổ b có phân biệt chi phối ngân sách bộ nhớ toàn cục.
| Hạng mục | Tập chính xác (HashSet) | HyperLogLog | Góc nhìn so sánh |
|---|---|---|---|
| Bộ nhớ | O(n), tỷ lệ với số phần tử | O(1), cố định (ví dụ 12KB) | HLL dùng 12KB cho cả một tỷ |
| Kết quả | Chính xác | Xấp xỉ (sai số chuẩn ~0,81%) | Chấp nhận sai số nhỏ |
| Hợp nhất | Tính lại sau khi hợp | Hợp nhất tức thì bằng max theo thanh ghi | HLL lợi cho phân tán |
| Xóa | Có thể | Không thể (chỉ thêm/hợp nhất) | HLL chỉ dùng để tổng hợp |
| Giao | Chính xác | Xấp xỉ bằng bao hàm-loại trừ (sai số lớn) | Điểm yếu của HLL |
Như bảng cho thấy, lợi thế thực tế lớn nhất của HLL là sự đơn giản của hợp nhất. Để gộp hai HLL chỉ cần lấy giá trị lớn hơn (max) giữa các thanh ghi cùng chỉ số, điều này thỏa luật giao hoán và kết hợp và khớp hoàn hảo vào giai đoạn reduce của tổng hợp MapReduce/luồng. Ví dụ, nếu 100 máy chủ web mỗi máy dựng một HLL cho lưu lượng của mình rồi trung tâm gộp 100 cái bằng max, tổng khách truy cập duy nhất hiện ra, và quá trình này không cần gom nhật ký gốc về một nơi, giảm mạnh chi phí mạng và lưu trữ. Ngược lại, giao (số người dùng chung) không thể có được trực tiếp chỉ từ HLL và phải xấp xỉ bằng nguyên lý bao hàm-loại trừ, nơi sai số tích lũy, nên nếu giao là then chốt thì phải kết hợp với kỹ thuật khác như MinHash.
4. So sánh với các kỹ thuật tương tự và sự phát triển: HyperLogLog++
HyperLogLog bắt đầu từ thuật toán Flajolet–Martin năm 1984, phát triển thành LogLog năm 2003 và thành HyperLogLog do Flajolet và cộng sự đề xuất năm 2007, rồi đạt đỉnh ở HyperLogLog++ (HLL++), được Google cải tiến năm 2013 cho ứng dụng thực tế quy mô lớn. Mỗi giai đoạn là một lịch sử cải tiến kỹ thuật hướng tới "làm sao giảm sai số thêm nữa với cùng bộ nhớ".
Các cải tiến then chốt của HLL++ gồm ba điểm. Thứ nhất, mở rộng băm từ 32 bit lên 64 bit đã loại bỏ trên thực tế vấn đề đụng độ băm (bão hòa cận trên) từng phát sinh ở các lực lượng rất lớn vượt hàng tỷ. Thứ hai, nó nâng độ chính xác bằng cách hiệu chỉnh — bằng một bảng hiệu chỉnh độ lệch theo kinh nghiệm (empirical bias correction) đo trước — độ lệch lớn mà HLL gốc thể hiện ở khoảng lực lượng nhỏ. Thứ ba, vì khi số phần tử nhỏ thì phần lớn trong 16.384 thanh ghi trống và bộ nhớ bị lãng phí, nó ban đầu chỉ lưu các quan sát ở biểu diễn thưa (sparse representation) và chuyển sang thanh ghi dày khi lớn lên, qua đó tiết kiệm bộ nhớ nhiều hơn ở lực lượng nhỏ. HLL++ này đã trở thành nền tảng của các engine phân tích thương mại ngày nay như APPROX_COUNT_DISTINCT của Google BigQuery, approx_distinct của Presto/Trino, Apache Druid, và phép tổng hợp cardinality của Elasticsearch.
| Thuật toán | Xuất hiện | Phương thức lấy trung bình | Sai số tương đối | Đặc điểm |
|---|---|---|---|---|
| Flajolet–Martin | 1984 | Bitmap đơn | Lớn | Đếm xác suất đầu tiên |
| LogLog | 2003 | Trung bình cộng | 1.30/√m | Vài bit mỗi thanh ghi |
| HyperLogLog | 2007 | Trung bình điều hòa | 1.04/√m | Giảm mạnh phương sai |
| HyperLogLog++ | 2013 | Trung bình điều hòa + hiệu chỉnh | 1.04/√m (cải thiện khoảng thấp) | 64 bit, hiệu chỉnh độ lệch, biểu diễn thưa |
A. Phân biệt vai trò với các cấu trúc dữ liệu xác suất lân cận
HLL chỉ là một trục của họ "sketch xác suất", và lựa chọn khác đi khi câu hỏi khác đi. Để tránh nhầm lẫn, phải phân biệt theo tiêu chí "cái gì đang được xấp xỉ." Bloom filter xấp xỉ sự thuộc về (membership) ("giá trị này có trong tập không?"), HyperLogLog xấp xỉ lực lượng ("có bao nhiêu phần tử duy nhất?"), Count–Min Sketch xấp xỉ tần suất ("giá trị này xuất hiện bao nhiêu lần?"), còn MinHash/Theta Sketch xấp xỉ độ tương tự/giao ("hai tập chồng lấp bao nhiêu?"). Nếu ánh xạ câu hỏi sai thì dù tinh chỉnh bao nhiêu cũng không ra câu trả lời mong muốn.
| Sketch | Đối tượng xấp xỉ | Truy vấn điển hình | Quan hệ với HLL |
|---|---|---|---|
| Bloom filter | Sự thuộc về | "đã thấy chưa?" | Bổ trợ (sự tồn tại) |
| HyperLogLog | Số đếm duy nhất | "bao nhiêu loại?" | Chủ đề này |
| Count–Min Sketch | Tần suất | "bao nhiêu lần?" | Bổ trợ (tần suất) |
| MinHash/Theta | Giao/độ tương tự | "chồng lấp bao nhiêu?" | Bổ khuyết điểm yếu của HLL |
Trong thực tế chúng được dùng kết hợp. Ví dụ, trong giám sát lưu lượng ta lọc IP mới bằng Bloom filter, đếm số IP duy nhất bằng HLL, và theo dõi các IP lưu lượng cao nhất (heavy hitter) bằng Count–Min Sketch. Vì mỗi sketch chia sẻ triết lý thiết kế chung là chỉ xấp xỉ một đại lượng thống kê cụ thể bằng bộ nhớ cố định, chúng được bó lại cùng nhau như bộ công cụ tiêu chuẩn cho phân tích luồng quy mô lớn.
5. Chuyên sâu: Áp dụng thực tế và xu hướng sử dụng mới nhất
HyperLogLog đã trở thành tính năng cơ bản của các nền tảng dữ liệu nhờ nhu cầu rộng về "đếm duy nhất nơi xấp xỉ là chấp nhận được". Là trường hợp tiêu biểu, Redis cung cấp HLL qua ba lệnh — PFADD (thêm phần tử), PFCOUNT (truy vấn ước lượng), PFMERGE (hợp nhất) — và tiền tố PF tôn vinh Philippe Flajolet, người phát minh HyperLogLog. Nó được dùng rộng rãi cho dashboard khách truy cập duy nhất theo thời gian thực, số client duy nhất của lời gọi API, tổng hợp độ phủ (reach) duy nhất của lần hiển thị quảng cáo, v.v.
Để cho một cảm nhận cụ thể về quy mô, giả sử một dịch vụ nhận 100 triệu yêu cầu mỗi ngày tổng hợp số người dùng duy nhất theo từng phút. Tổng hợp chính xác phải giữ hàng trăm nghìn ID duy nhất trong bộ nhớ mỗi phút và gộp cả ngày vào lúc nửa đêm, nhưng HLL chỉ cần một sketch 12KB mỗi phút, và dù gom cả một ngày (1.440 cái) cũng chỉ khoảng 17MB, với số duy nhất cho bất kỳ khoảng nào có được tức thì chỉ bằng hợp nhất. Ba chi phí — lưu trữ, tính toán, truy vấn — đều giảm hàng trăm lần trở lên cùng lúc.
Trong lĩnh vực kho dữ liệu, các hàm xấp xỉ dựa trên HLL giải quyết vấn đề COUNT(DISTINCT) chính xác chậm đi trên các bảng lớn do chi phí xáo trộn/sắp xếp. Ví dụ, khi xu hướng người dùng duy nhất theo ngày phải được làm mới mỗi giờ trên một nhật ký hàng chục tỷ hàng, tổng hợp chính xác có thể mất vài phút đến vài chục phút mỗi truy vấn, trong khi APPROX_COUNT_DISTINCT trả lời trong vài giây đến vài chục giây với sai số quanh 1%. Trong môi trường phân tích đám mây tính phí, giảm khối lượng quét và tính toán nghĩa là giảm hóa đơn trực tiếp, nên hiệu quả kinh tế là tức thì.
Ngoài ra, mẫu hình lưu sketch HLL như sản phẩm trung gian được dùng rộng rãi. Thay vì quét bảng nguồn mỗi lần, nếu dựng sẵn các sketch HLL theo giờ và nạp vào một bảng riêng (hay các khóa Redis), thì số duy nhất ngày/tuần/tháng được tính gần như tức thì bằng cách hợp nhất (PFMERGE/HLL_UNION) các sketch cho khoảng đó. Đây là chiến lược bất khả thi với tổng hợp chính xác, khai thác việc HLL "bảo tồn kết quả tổng hợp ở dạng có thể tái sử dụng, tái kết hợp". Kết quả là có thể hạ đồng thời cả chi phí tính lại theo lô và độ trễ truy vấn thời gian thực.
Các xu hướng mới nhất gồm ① nhúng HLL vào một cơ sở dữ liệu chuỗi thời gian để tổng hợp trước số duy nhất ở giai đoạn roll-up, ② xử lý tổng hợp duy nhất đa chiều — các truy vấn kết hợp các trục khác nhau (khu vực × thiết bị × chiến dịch) — bằng cách dựng sẵn các sketch HLL và xử lý qua hợp nhất, và ③ nghiên cứu kết hợp HLL với Quyền riêng tư vi sai (Differential Privacy) bằng cách thêm nhiễu vào sketch HLL để tăng cường quyền riêng tư. Tuy nhiên, dù bản thân sketch HLL không chứa thông tin định danh cá nhân, vẫn có thảo luận về khả năng suy ngược, trong một số điều kiện nhất định, sự thuộc về của một tập nhỏ, nên cần thiết kế thận trọng cho dữ liệu nhạy cảm.
Tổng hợp duy nhất đa chiều là mẫu hình tiêu biểu nơi tính hợp nhất của HLL tỏa sáng. Ví dụ, nếu một nền tảng quảng cáo quét lại nguồn mỗi lần cho một truy vấn kết hợp các trục, như "độ phủ duy nhất trong số người dùng Android ở khu vực Seoul của chiến dịch A", thì chi phí bùng nổ. Thay vào đó, nếu một sketch HLL được dựng và lưu sẵn cho mỗi tổ hợp chi tiết của (khu vực, thiết bị, chiến dịch), thì các truy vấn cấp cao hơn có thể trả lời tức thì bằng cách hợp nhất max các sub-sketch liên quan. Vì một COUNT DISTINCT chính xác sẽ phải khử trùng lặp lại cho mỗi tổ hợp, khiến việc tổng hợp trước và roll-up này bất khả thi, HLL về mặt cấu trúc có lợi cho phân tích kiểu khối OLAP (OLAP cube).
Ngoài ra, trong các khung xử lý luồng (Apache Flink / Spark Structured Streaming), số duy nhất theo mỗi cửa sổ được duy trì dưới dạng một sketch HLL và chỉ ước lượng được phát ra khi cửa sổ đóng lại, ràng buộc kích thước trạng thái (state) thành một hằng số. Trong một luồng đến vô hạn, tổng hợp chính xác làm trạng thái lớn lên không giới hạn, nhưng HLL có kích thước cố định mỗi cửa sổ, nên bộ nhớ không bùng nổ dù vận hành dài hạn. Tính chất "tóm tắt một luồng vô hạn bằng trạng thái hữu hạn" này là một lý do khác khiến HLL trở thành sketch tiêu chuẩn cho phân tích thời gian thực.
6. Cân nhắc và hàm ý
Dưới góc nhìn kỹ sư chuyên nghiệp, việc áp dụng HyperLogLog cần cân nhắc tổng thể những điều sau.
Trước hết hãy đánh giá mức dung sai và bản chất của chỉ số. HLL phù hợp cho các chỉ số xu hướng/quy mô (khách truy cập duy nhất, độ phủ) nơi sai số ±1–2% là chấp nhận được. Nó không phù hợp cho các tổng hợp mà độ chính xác được yêu cầu về pháp lý hoặc tài chính, như tính phí, quyết toán, báo cáo tuân thủ, và luôn phải đi kèm tổng hợp chính xác hoặc một lộ trình kiểm chứng tính nhất quán hậu kiểm.
Ước lượng trước số thanh ghi m theo mục tiêu độ chính xác. Vì sai số là 1.04/√m và bộ nhớ tỷ lệ với m, giảm một nửa sai số mục tiêu tốn 4 lần bộ nhớ. Thay vì áp độ chính xác cao cho mọi chỉ số, một thiết kế phân biệt độ chính xác (bộ nhớ) theo mức quan trọng của từng chỉ số sẽ hiệu quả về chi phí.
Phản ánh thế mạnh của tính hợp nhất vào kiến trúc. Phép hợp nhất max của HLL thỏa luật giao hoán và kết hợp, khiến nó lý tưởng cho thu thập phân tán và tổng hợp luồng. Dựng sketch theo mỗi biên/máy chủ rồi hợp nhất tập trung tránh việc di chuyển nhật ký gốc, nên nó kết hợp tốt với [[edge-computing]] và các chiến lược tính cục bộ dữ liệu (data locality). Tuy nhiên, các sketch dựng với m hoặc hàm băm khác nhau không thể hợp nhất, nên chuẩn hóa tham số phải đi trước.
Xác nhận sớm các yêu cầu về giao/hiệu. HLL mạnh ở hợp (hợp nhất) nhưng phải xấp xỉ giao bằng bao hàm-loại trừ, nơi sai số tích lũy. Nếu "số người dùng chung của hai phân khúc" là một chỉ số then chốt thì riêng HLL không phù hợp, và phải cân nhắc kết hợp MinHash, Theta Sketch và tương tự.
Cân nhắc đặc tính không xóa được và quyền riêng tư. HLL là một cấu trúc chỉ thêm/hợp nhất mà trong đó không thể xóa phần tử, nên nếu cần loại một người dùng cụ thể khỏi tổng hợp (xử lý quyền rút lui, v.v.) thì cần tính lại hoặc một thiết kế riêng. Ngoài ra, dù một sketch không chứa trực tiếp thông tin định danh, ở các miền nhạy cảm hãy đánh giá rủi ro suy ngược và đi kèm nhiễu cùng kiểm soát truy cập khi cần.
Chuẩn hóa chất lượng hàm băm và tính tương thích tham số. Sai số lý thuyết của HLL đứng vững trên giả định rằng hàm băm đủ đồng nhất và độc lập, nên một hàm băm thiên lệch hay ngắn làm sai số thực tế tệ hơn giá trị lý thuyết. Hãy dùng một hàm băm phi mật mã nhanh, chất lượng cao như MurmurHash hay xxHash, nhưng để hợp nhất các sketch do các hệ thống khác nhau tạo ra, hàm băm, số thanh ghi và quy ước mã hóa phải hoàn toàn giống nhau. Nếu quy ước này không được chuẩn hóa toàn tổ chức, chi phí tái tạo sketch về sau sẽ phát sinh.
Tóm lại, HyperLogLog là một trường hợp tiêu biểu của xấp xỉ kỹ thuật "nhượng một phần độ chính xác để đổi lấy lợi ích thực chất về bộ nhớ và tính hợp nhất", và nó là một công cụ cốt lõi mà trong môi trường AI/dữ liệu lớn với quy mô dữ liệu bùng nổ mở rộng tuyến tính việc đếm duy nhất bằng bộ nhớ cố định. Khi áp dụng, việc thiết kế phạm vi áp dụng dựa trên mức dung sai, định cỡ bộ nhớ theo độ chính xác mục tiêu, các yêu cầu hợp nhất/giao, và các ràng buộc xóa/quyền riêng tư là cái quyết định thành bại.
Tài liệu tham khảo
- Salvatore Sanfilippo (antirez), "Redis new data structure: the HyperLogLog", https://antirez.com/news/75
- Flajolet, Fusy, Gandouet, Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" (2007), http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- Heule, Nunkesser, Hall, "HyperLogLog in Practice" (Google, EDBT 2013), https://research.google/pubs/pub40671/
Tóm tắt một câu: HyperLogLog ghi giá trị lớn nhất của số 0 dẫn đầu trong giá trị băm vào một mảng thanh ghi và ước lượng ngược bằng trung bình điều hòa, đếm số phần tử duy nhất ở quy mô hàng tỷ với sai số khoảng 1% chỉ bằng vài KB bộ nhớ cố định — một kỹ thuật ước lượng lực lượng tập hợp xác suất.