OpenAI vừa nộp hồ sơ IPO bí mật lên SEC với định giá 852 tỷ USD, tiết lộ rằng ChatGPT phục vụ 900 triệu người dùng mỗi tuần. Nhưng làm thế nào để đếm chính xác 900 triệu người dùng duy nhất mà không lưu trữ danh sách hàng trăm triệu ID? Câu trả lời nằm ở HyperLogLog, một thuật toán xác suất tinh tế đến bất ngờ: nó có thể ước lượng số phần tử duy nhất trong tập dữ liệu hàng tỷ bản ghi chỉ với 12 kilobyte bộ nhớ, sai số dưới 1%.

Bài toán đếm phần tử duy nhất

Giả sử bạn vận hành một dịch vụ web và muốn biết có bao nhiêu người dùng riêng biệt truy cập mỗi ngày. Cách đơn giản nhất là dùng một tập hợp (Set) để lưu mọi ID, mỗi lần có truy cập mới thì thêm vào. Với 900 triệu ID, mỗi ID chiếm khoảng 16 byte, bạn cần khoảng 14 GB RAM chỉ để đếm. Nhân lên cho hàng nghìn chỉ số khác nhau (theo quốc gia, theo tính năng, theo phiên bản), chi phí bộ nhớ trở nên không thể chấp nhận được.

Trò chơi tung đồng xu

HyperLogLog dựa trên một quan sát thống kê đơn giản: nếu bạn tung đồng xu liên tục, trung bình phải tung 2 lần mới gặp mặt sấp đầu tiên, 4 lần mới gặp chuỗi hai mặt ngửa liên tiếp, 8 lần cho ba mặt ngửa liên tiếp. Nói cách khác, nếu chuỗi mặt ngửa liên tiếp dài nhất mà bạn quan sát được là k, thì số lần tung ước lượng khoảng 2^k.

Thuật toán áp dụng nguyên lý này bằng cách băm (hash) mỗi phần tử thành một chuỗi bit ngẫu nhiên đều, sau đó đếm số bit 0 liên tiếp ở đầu chuỗi (leading zeros). Nếu bit 0 dài nhất bạn từng thấy là 25, thuật toán ước lượng có khoảng 2^25 ≈ 33,5 triệu phần tử duy nhất. Bản thân phần tử gốc không cần lưu lại, chỉ cần ghi nhớ con số leading zeros lớn nhất.

Chia nhỏ để chính xác hơn

Một bộ đếm duy nhất cho kết quả rất thiếu chính xác vì chỉ cần một phần tử có nhiều leading zeros cũng đủ làm lệch toàn bộ ước lượng. HyperLogLog giải quyết vấn đề này bằng cách chia không gian hash thành nhiều bucket (thường là 2^14 = 16.384 bucket). Mỗi bucket theo dõi riêng giá trị leading zeros lớn nhất của các phần tử rơi vào nó. Kết quả cuối cùng được tính bằng trung bình điều hòa (harmonic mean) của tất cả các bucket, kèm hệ số hiệu chỉnh để giảm sai lệch hệ thống.

Với 16.384 bucket, mỗi bucket chỉ cần 6 bit (đủ lưu giá trị leading zeros tối đa 63), tổng bộ nhớ chỉ khoảng 12 KB. Sai số tiêu chuẩn vào khoảng 0,81%, nghĩa là với 900 triệu người dùng, kết quả sẽ dao động trong khoảng ±7,3 triệu, hoàn toàn chấp nhận được cho mục đích phân tích.

Ứng dụng thực tế

Redis tích hợp HyperLogLog qua lệnh PFADD/PFCOUNT (PF viết tắt của Philippe Flajolet, nhà toán học Pháp đồng tác giả thuật toán năm 2007). Google BigQuery dùng hàm APPROX_COUNT_DISTINCT(), bên trong cũng là HyperLogLog++, phiên bản cải tiến với độ chính xác cao hơn ở tập dữ liệu nhỏ. CloudFlare đếm hàng nghìn tỷ truy cập duy nhất mỗi ngày bằng cùng cấu trúc này. Khi các công ty AI như OpenAI hay Anthropic chuẩn bị lên sàn chứng khoán, những con số hàng trăm triệu người dùng mà họ báo cáo cho SEC rất có thể được đếm bằng chính HyperLogLog hoặc các biến thể của nó.