Scaling Exact COUNT(DISTINCT) for High-Cardinality Non-Rollup Metrics in Distributed Data Pipelines

Summary

Uber needed exact COUNT(DISTINCT) for high-cardinality non-rollup metrics such as monthly active users and quarterly retention, where daily or monthly counts cannot be combined and quarterly processing involved 3.6 billion UUID-valued identifiers. RoaringBitmap was exact but failed when a merged bitmap exceeded the JVM’s roughly 2 GB array limit, while HyperLogLog’s 1–5% error was unacceptable for financial reporting. The implemented chunked aggregation buffer hashes each UUID with xxHash64, routes it by the top 16 bits into one of 65,536 Roaring64Bitmap chunks, serializes chunks independently, and returns the final cardinality as an 8-byte long. Across 75 metric families, the deployment reduced two-year backfill time by 65% on average, improved daily runtime by 23%, and recorded no post-deployment OutOfMemoryError failures while retaining exact distinct counts.

Takeaways

1. 1

   Non-rollup metrics cannot be calculated correctly by combining daily or monthly distinct counts because entities may appear repeatedly across those periods.

2. 2

   Using 16 hash bits creates 65,536 chunks; at 3.6 billion quarterly identifiers, the source reports an average of about 55,000 values per chunk and an effectively zero probability of reaching the 179 million-value OOM threshold.

3. 3

   The deployment covered 75 metric families and reported a 65% average reduction in two-year backfill time, a 23% daily runtime improvement, and zero post-deployment OutOfMemoryError failures.