Scaling Exact COUNT(DISTINCT) for High-Cardinality Non-Rollup Metrics

Uber · 2026 · 3. Quy mô lớn · Độ khó: Khó — bài gốc

Bối cảnh

• Một lớp metric (user hoạt động theo tháng, giữ chân theo quý) phải tính chính xác và là non-rollup: không ghép được từ số theo ngày (một user hoạt động thứ Hai và thứ Tư chỉ tính một lần trong tuần). Theo quý, phải giữ cùng lúc hơn 3,6 tỉ UUID. HyperLogLog sai 1–5%, không chấp nhận được với metric dùng cho báo cáo tài chính.
• Hai cách cũ đều hỏng một cách tất định:
  • Bitmap-32 (RoaringBitmap trên số 32-bit) cần từ điển toàn cục ánh xạ UUID → số thứ tự: một điểm hỏng chung (hỏng hay trễ nhân bản là sai mọi job đang chạy), và các job song song sinh số trùng nhau nên backfill phải chạy tuần tự; backfill hai năm mất hơn 20 ngày.
  • Bitmap-64 (Roaring64Bitmap, hash UUID thẳng ra 64-bit, không cần từ điển) nhưng hợp đồng UDAF của Hive/Spark bắt trạng thái gộp trả về là một byte[], bị JVM chặn ở khoảng 2 GB (Integer.MAX_VALUE). Mốc đó vỡ ở khoảng 179 triệu ID; với 3,6 tỉ, job OutOfMemoryError ở mọi lần chạy, không cấu hình nào cứu được.

Thay đổi chính

• Bộ đệm gộp chia khúc: thay một bitmap lớn bằng Map<Integer, Roaring64Bitmap>; hash UUID bằng xxHash64 (hàm có sẵn của Hive, phân phối đều), 16 bit đầu chọn khúc (chunkId = hash >>> 48), 65.536 khúc rời nhau nên tổng chính xác là tổng số phần tử từng khúc. Với 3,6 tỉ ID, trung bình khoảng 55.000 mỗi khúc; theo cận Chernoff, xác suất một khúc chạm 179 triệu gần như bằng 0. 8 bit (256 khúc, khoảng 14 triệu mỗi khúc) không đủ khoảng đệm khi lệch; 24 bit (16 triệu khúc) tốn chi phí map và GC.
• Serialize theo luồng: mỗi khúc serialize vào buffer riêng rồi ghi tuần tự; khi đọc, mỗi lần một khúc, cấp byte[] đúng cỡ, gộp, giải phóng; bộ nhớ đỉnh bằng khúc lớn nhất chứ không bằng tổng. Bước cuối terminate() không serialize bitmap mà chỉ trả một số 8 byte. Ngưỡng an toàn từ khoảng 179 triệu lên khoảng 11,7 nghìn tỉ.
• Bỏ trạng thái chung giữa các job: không còn từ điển nên backfill chạy song song mặc định.
• Migration không gián đoạn: mỗi kết quả trung gian dạng khúc có tiền tố 4 byte 0xDEADBEEF (không thể trùng header của Roaring64Bitmap); bộ gộp đọc 4 byte đầu để chọn đường mới hay đường cũ, nên kết quả Bitmap-64 cũ đã lưu trên HDFS vẫn gộp được, không pipeline nào phải tính lại lịch sử. Kiểm đúng: so với COUNT(DISTINCT) thô trên 10 họ metric, theo ngày, tháng, quý, 30 lần chạy khớp tuyệt đối; thử định tuyến với kết quả trung gian trộn hai loại trong một job.
• Kết quả, theo Uber: 75 họ metric (Mobility, Delivery, Platform), không còn OOM; backfill hai năm trung bình 8,58 → 2,96 ngày (−65%, tới −94% ở pipeline cardinality cao nhất; một metric grocery 19,1 → 1,1 ngày; trung bình nhanh 3,8 lần với 3 cửa sổ song song); pipeline ngày nhanh hơn 23% (shuffle một số 8 byte thay vì bitmap nhiều KB); chuẩn bị dữ liệu hàng tháng 20 → khoảng 10 ngày.

Vì sao

• Giới hạn 2 GB là cấu trúc của JVM và của hợp đồng UDAF, không phải tham số; chỉ có lời giải cấu trúc: không bao giờ dựng một đối tượng vượt giới hạn đó.

Bài học cho SWE

• Giới hạn cứng của nền tảng (kích thước mảng, kiểu trả về) cần được biết trước khi chọn cách biểu diễn trạng thái.
• Chia không gian giá trị thành các khúc rời nhau: tổng chính xác vẫn giữ, bộ nhớ đỉnh bị chặn bởi khúc lớn nhất.
• Từ điển toàn cục cấp số thứ tự là trạng thái chung buộc chạy tuần tự; hash thẳng bỏ được nó.
• Định dạng mới tự mô tả (magic number) cho phép đọc lẫn dữ liệu cũ, tránh phải tính lại lịch sử.

Liên quan

• Pipeline dữ liệu và analytics · Sinh ID phân tán
• Cùng công ty: Uber 2026 · Uber 2026