Source: Uber Engineering Blog — 2026-07-30
Summary
Uber built an exact, non-approximate distinct-count aggregator for use inside Hive/Spark UDAFs, for metrics like MAU-style numbers that feed financial reporting, where approximation error is unacceptable. The trigger was a hard ceiling: the JVM's 2GB byte[] cap on serialized aggregation state meant their previous approach maxed out around 179 million unique IDs. Their fix hashes UUIDs directly to 64-bit integers and sets bits in a Roaring64Bitmap, dropping the dictionary-encoding step earlier approaches relied on, and now handles billions of unique identifiers — on the order of 3.6 billion at a quarterly scale in Uber's own data.
Key Takeaways
- The old approach hit a hard wall at roughly 179 million unique IDs because the JVM caps a serialized byte array at 2GB, and their aggregation state grew with a dictionary-encoding step.
- HyperLogLog, the standard approximate distinct-count algorithm, was ruled out entirely for these metrics because its typical 1-5% error rate is unacceptable for numbers that feed financial reporting.
- The fix hashes UUIDs directly into 64-bit integers and sets bits in a Roaring64Bitmap, skipping the dictionary-encoding step that caused the previous approach to balloon in memory.
- The new aggregator, built as a Hive/Spark UDAF, now handles billions of unique identifiers — on the order of 3.6 billion at Uber's quarterly scale — without hitting the old ceiling.
Reel Script
Hook (~15-20s, 35-45 words) Most companies count unique users with an algorithm that's allowed to be wrong by up to 5 percent. Uber couldn't accept that for numbers that feed financial reporting, so they rebuilt exact counting to handle billions of IDs without breaking.
Core Concept (~45-90s, 105-200 words) Counting distinct things at huge scale is normally done approximately, with something like HyperLogLog — it uses tiny, fixed memory no matter how many items you're counting, but you pay for that with a 1 to 5 percent error rate. For most dashboards that's a fine trade. But for metrics like monthly active users that roll up into financial reporting, being off by even a percent or two isn't acceptable — that number needs to be exact. So Uber needed a way to count distinct values exactly, at massive scale, inside their Hive and Spark pipelines. Their earlier exact-counting approach worked by dictionary-encoding every ID it saw, which meant its in-memory state grew and grew. And it ran straight into a very unglamorous limit: the JVM caps any single serialized byte array at 2 gigabytes. Once their aggregation state for a job crossed that line, it just couldn't hold more IDs.
Hands-On (~45-150s, 105-350 words) That 2GB byte array cap translated into a real number: their old approach maxed out at around 179 million unique IDs. Past that, it broke. Here's how they fixed it. Instead of dictionary-encoding every UUID — building up a growing lookup table mapping each ID to some internal representation — they hash each UUID directly down to a 64-bit integer. No dictionary, no growing lookup table. That 64-bit integer becomes a single bit position they flip on inside a Roaring64Bitmap, which is a compressed bitmap structure built specifically to store large sets of integers efficiently — it groups values into chunks and only spends real memory on the chunks that actually have data in them, instead of allocating for the full range. So counting a distinct ID becomes: hash it, find its bit, set it. No dictionary to maintain, no linear growth in the way that hit the 2GB wall. The result: what used to cap out around 179 million unique IDs now handles billions — Uber cites numbers on the order of 3.6 billion at a quarterly scale — while staying exact the entire time.
Takeaway (~20-30s, 45-70 words) This is a good reminder that "just use HyperLogLog" isn't universal advice — when the number has to be exact, you need a structure built for that, and Roaring64Bitmap plus direct hashing is a clean way to get there. If you're hitting memory ceilings on exact aggregations, look at whether you're paying for a dictionary-encoding step you don't actually need.