Uber: Scaling Exact COUNT(DISTINCT) for High-Cardinality Metrics
Problem + constraints
Uber's internal metrics platform, uMetric, needed to support exact COUNT(DISTINCT) — not approximate — for high-cardinality, non-rollup metrics like monthly active users (MAU) computed over distributed data pipelines (Hive/Spark-style JVM engines). At quarterly-scale cardinality, the naive approach hit a wall that no tuning could fix: the Hive/Spark UDAF contract requires aggregation state to be serialized into a single Java byte[], and the JVM caps array size at roughly 2 GB. That's a structural, not a configuration, limit — no amount of memory tuning, framework upgrades, or partition rebalancing gets around it. The obvious workaround, HyperLogLog-style probabilistic counting, was off the table: it introduces a 1-5% error rate, which is unacceptable for metrics that feed financial and business reporting where "approximately right" isn't good enough.
Solution
Uber built a chunked aggregation buffer strategy: instead of one monolithic aggregation buffer serialized as a single byte[], the buffer is partitioned across disjoint value-space segments (e.g., hash-range shards of the distinct-value domain), each chunk is serialized independently, and the final cardinality is returned as a compact 8-byte long rather than the full buffer. This sidesteps the JVM array-size ceiling entirely — no single chunk ever needs to approach 2 GB — while still computing an exact, not estimated, distinct count. The partitioning scheme generalizes to any 64-bit hashed identity domain (device IDs, session tokens, geohash-encoded locations), not just user IDs.
Rather than leaving this as a one-off UDAF that individual teams reimplement, Uber exposed chunked exact COUNT(DISTINCT) as a first-class metric type inside the uMetric platform. Any team can now define a high-cardinality non-rollup metric declaratively, without hand-writing custom UDAF code and without risking an out-of-memory failure in production. Since rollout across 75 metric families spanning Uber's Mobility, Delivery, and Platform verticals, the platform has recorded zero OOM failures on this metric class.
What to steal
- A hard platform ceiling (JVM array size, a protocol's max message size, a database's row-size limit) is not always a memory-tuning problem — sometimes it requires restructuring the computation itself (partition, chunk, and reduce) rather than fighting the constraint head-on.
- Exact vs. approximate is a real tradeoff, not just an engineering preference: HyperLogLog-class algorithms are the right default for dashboards and exploratory analytics, but any metric feeding financial reporting or contractual SLAs needs the exact answer, even at higher engineering cost.
- Turning a hard-won fix into a first-class platform primitive (a declarative metric type, not a bespoke UDAF) is what makes the fix actually scale across an org — otherwise every team rediscovers and reimplements the same workaround.
Principal Engineer Lens
This is a good example of a constraint that looks like a tuning problem at first glance but is actually structural — and recognizing that distinction early saves weeks of futile parameter sweeps. The reusable judgment call is knowing when "add more memory" or "increase the timeout" stops being a valid lever and a redesign of the data structure is the only path forward. It's also a clean illustration of defending an accuracy/cost tradeoff in an architecture review: probabilistic counting is cheaper and simpler, but the burden of proof shifts to justifying why approximate is good enough for a given metric's consumers — financial reporting metrics generally fail that bar, dashboards generally pass it.
Reel Script
Setup: Uber needed an exact (not approximate) distinct-count for high-cardinality metrics like monthly active users, computed at massive scale inside Hive/Spark pipelines — and hit a wall no config change could fix.
Concept walkthrough: Walk through the JVM's 2 GB byte[] limit on UDAF aggregation state, why HyperLogLog's 1-5% error rate was unacceptable for financially-relevant metrics, and how the chunked aggregation buffer strategy partitions the aggregation state across disjoint value-space segments so no single chunk approaches the size ceiling — while still returning an exact count.
Real example tie-in: Trace how this became a platform primitive: instead of a one-off fix, Uber exposed chunked exact COUNT(DISTINCT) as a declarative metric type in uMetric, rolled out across 75 metric families across Mobility, Delivery, and Platform, with zero OOM failures since.
Tradeoffs & alternatives: Compare against HyperLogLog and other approximate sketches — far cheaper in memory and compute, and the right default for exploratory dashboards, but wrong for anything feeding financial or contractual reporting. Also compare against simply scaling up cluster memory — which doesn't work here because the limit is a JVM array-size ceiling, not available RAM.
Principal Engineer takeaway: Before reaching for more memory or a longer timeout, check whether the wall you've hit is structural (a hard platform limit) rather than a tuning problem — and when accuracy genuinely matters to the consumer of a metric, be ready to defend paying the engineering cost for exact over approximate.
Related
Sources: