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.
Engineering 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.