COUNT DISTINCT на мільярдах подій: як Uber вирішив проблему OOM і чому це змінює підхід до аналітики великих даних

Коротко: COUNT DISTINCT на великих даних справді може стати джерелом OOM і дуже дорогих агрегацій. Але кейс Uber у 2026 році цікавий саме тим, що компанія не перейшла на HyperLogLog для критичних метрик: їй був потрібен точний результат. Uber побудував chunked aggregation buffer на основі Roaring64Bitmap і обійшов JVM-ліміт приблизно 2 ГБ для одного масиву/серіалізованого aggregation state. HyperLogLog залишається важливою альтернативою там, де статистична похибка прийнятна.

Вступ

Підрахунок унікальних значень — одна з найпоширеніших операцій в аналітиці. DAU, MAU, унікальні сесії, активні водії або користувачі за період — усе це сценарії для COUNT(DISTINCT). На невеликих таблицях така агрегація зазвичай не створює проблем. На мільярдах ідентифікаторів її реалізація вже стає архітектурним питанням.

У липні 2026 року Uber описав саме такий кейс. Для частини mission-critical non-rollup метрик — зокрема monthly active users, quarterly retention і cross-window engagement — компанії потрібен точний підрахунок. На квартальному вікні це означало одночасну роботу приблизно з 3,6 млрд UUID-ідентифікаторів. Approximate counting через HyperLogLog Uber розглядав, але відкинув для цих метрик через неприйнятну похибку.

У цій статті розберемо, чому exact COUNT DISTINCT стає складним на великих даних, де HyperLogLog справді доречний, що конкретно зробив Uber для точного підрахунку без OOM і як обирати між exact та approximate підходами.

Чому звичайний COUNT(DISTINCT) ламається на великих даних?

Що насправді відбувається всередині движка при COUNT(DISTINCT)

Уявіть великий distributed pipeline, який рахує унікальних користувачів за квартал. Проблема тут не просто в кількості рядків: критичною є кардинальність — скільки різних ідентифікаторів треба одночасно звести в один точний агрегат.

Точний COUNT(DISTINCT) не обов’язково реалізується одним hash set у RAM. Движок може використовувати hash aggregation, сортування, spill на диск, compressed bitmaps і partial aggregation. Але exact-підхід усе одно повинен зберегти достатньо інформації, щоб не втратити ідентичність елементів до фінального merge. На дуже високій кардинальності aggregation state, shuffle і серіалізація можуть стати вузьким місцем.

Саме це сталося в Uber. Перехід на Roaring64Bitmap дозволив хешувати UUID у 64-бітні значення без глобального словника, але Hive/Spark UDAF мав повертати aggregation state як один Java byte[]. Через JVM-обмеження близько 2 ГБ монолітний bitmap досягав межі приблизно на 179 млн унікальних ідентифікаторів — значно нижче за квартальні 3,6 млрд.

OOM у distributed aggregation: коли проблема не вирішується додаванням RAM

Distributed engines можуть паралельно рахувати partial aggregates, але в певний момент ці стани потрібно об’єднати. Якщо фінальний або проміжний state має бути матеріалізований як один великий об’єкт, структурний ліміт формату чи runtime може зламати job незалежно від загальної RAM кластера. У випадку Uber проблема була детермінованою: збільшення heap не прибирало 2-гігабайтний JVM-бар’єр для одного масиву.

Оптимізація SQL-запитів — лише частина ширшого арсеналу. Техніки на кшталт CTE, window functions або акуратнішого SQL допомагають із читабельністю й іноді з планом виконання, але не усувають фундаментальну проблему high-cardinality exact aggregation state.

Є два різні шляхи: погодитися на approximate cardinality estimation або змінити структуру exact aggregation так, щоб вона масштабувалась. Uber обрав другий.

Як працює HyperLogLog: альтернативний шлях для approximate COUNT DISTINCT

Що таке sketch-алгоритми і навіщо вони аналітику

Sketch-алгоритми — це компактні структури даних, які зберігають статистичний опис потоку замість усіх елементів. Вони дають оцінку з відомими статистичними властивостями, але не гарантують точного результату для кожного конкретного набору даних.

HyperLogLog — один із найвідоміших sketch-алгоритмів для оцінки кардинальності. Його пам’ять визначається параметрами precision і конкретною реалізацією, а не кількістю оброблених рядків. Тому зі зростанням набору даних sketch не росте лінійно разом із числом унікальних значень.

HyperLogLog зсередини: хешування, відра і магія leading zeros

Ідея алгоритму без зайвої математики:

1. Кожне вхідне значення хешується у бінарний рядок.
2. Хеші розподіляються по “відрах” (buckets) на основі перших бітів.
3. У кожному відрі відстежується максимальна кількість ведучих нулів (leading zeros) у хеші.
4. Статистично: чим більше унікальних елементів, тим довші послідовності ведучих нулів зустрічаються.
5. На основі цієї статистики по всіх відрах алгоритм оцінює загальну кількість унікальних значень.

Ключова властивість HLL: sketches можна об’єднувати. Наприклад, денні sketches можна змержити для отримання оцінки унікальних користувачів за тиждень або місяць — без повторного читання сирих ідентифікаторів. Саме ця mergeability робить sketches зручними для pre-aggregation.

Яка точність реальна: cardinality estimation на практиці

Похибка HHL залежить від реалізації та precision. Наприклад, Trino для approx_distinct() документує standard error 2,3% за замовчуванням і дозволяє задати цільовий standard error параметром e; це статистична характеристика, а не жорстка гарантія максимальної похибки для кожного набору даних. Spark SQL використовує HyperLogLog++ і параметр relativeSD.

Ось спрощене порівняння підходів:

Приклад синтаксису для розуміння механіки в Trino:

-- Точний підрахунок
SELECT COUNT(DISTINCT user_id) FROM events;

-- Наближений підрахунок через HyperLogLog
SELECT approx_distinct(user_id) FROM events;

-- Матеріалізація HLL sketch для подальшого merge
SELECT cast(approx_set(user_id) AS varbinary) AS hll_sketch
FROM events
GROUP BY event_date;

-- Merge збережених sketches
SELECT cardinality(merge(cast(hll_sketch AS HyperLogLog)))
FROM precomputed_sketches
WHERE event_date BETWEEN date '2026-01-01' AND date '2026-01-07';

-- Точний підрахунок
SELECT COUNT(DISTINCT user_id) FROM events;

-- Наближений підрахунок через HyperLogLog
SELECT approx_distinct(user_id) FROM events;

-- Матеріалізація HLL sketch для подальшого merge
SELECT cast(approx_set(user_id) AS varbinary) AS hll_sketch
FROM events
GROUP BY event_date;

-- Merge збережених sketches
SELECT cardinality(merge(cast(hll_sketch AS HyperLogLog)))
FROM precomputed_sketches
WHERE event_date BETWEEN date '2026-01-01' AND date '2026-01-07';

Як Uber реалізував точний підрахунок унікальних значень на мільярдах подій: архітектурне рішення

Проблема Uber: exact non-rollup metrics на мільярдах UUID

За наведеними Uber production-цифрами, distinct cardinality становила приблизно 40 млн на денному вікні, 1,2 млрд на місячному, 3,6 млрд на квартальному і 28,8 млрд на дворічному. Для таких non-rollup метрик не можна просто скласти денні counts: користувач, активний у кількох днях, має залишитися одним унікальним користувачем на довшому вікні.

Для частини цих показників Uber вимагав exact result. HyperLogLog міг би прибрати memory bottleneck, але вносив би приблизно 1–5% статистичної похибки, що команда визнала неприйнятним для MAU та інших метрик, пов’язаних із фінансовою звітністю.

Chunked Roaring64Bitmap: розділити aggregation state замість переходу на approximation

Ключове рішення Uber — не зберігати один монолітний Roaring64Bitmap. Кожен UUID хешується через xxHash64, а верхні 16 бітів хешу визначають один із 65 536 chunk IDs. Для кожного chunk зберігається окремий Roaring64Bitmap у Map<Integer, Roaring64Bitmap>.

Патерн виглядає так:

• UUID перетворюється на 64-бітний hash.
• Верхні 16 бітів визначають chunkId; решта значення потрапляє у відповідний Roaring64Bitmap.
• Кожен chunk серіалізується незалежно, тому peak memory прив’язаний до найбільшого chunk, а не до всього union.
• На фінальній стадії система не серіалізує весь bitmap: вона підсумовує cardinality неперетинних chunk-ів і повертає 8-байтний long.

Для квартальних 3,6 млрд ідентифікаторів це дає в середньому близько 55 тис. значень на chunk. За оцінкою Uber, безпечний поріг зріс приблизно зі 179 млн до 11,7 трлн distinct values — приблизно в 65 000 разів. Після розгортання рішення на 75 metric families компанія повідомила про нуль OOM-збоїв; середня тривалість дворічного backfill зменшилася на 65%, а daily pipeline runtime — приблизно на 23%.

approx_distinct у Trino, Spark, BigQuery і ClickHouse: коли approximation усе ж доречна

Кейс Uber не робить HyperLogLog «неправильним». Він показує, що approximate і exact counting вирішують різні задачі. Якщо статистична похибка прийнятна, HLL/HLL++ може суттєво зменшити aggregation state. Синтаксис і гарантії відрізняються між движками:

-- Trino
SELECT approx_distinct(user_id) FROM events;
SELECT approx_distinct(user_id, 0.01) FROM events; -- цільовий standard error 1%

-- ClickHouse
SELECT uniqHLL12(user_id) FROM events;

-- BigQuery: approximate count із системною точністю
SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;

-- Spark SQL (HyperLogLog++)
SELECT approx_count_distinct(user_id) FROM events;
SELECT approx_count_distinct(user_id, 0.01) FROM events; -- relativeSD

-- Trino
SELECT approx_distinct(user_id) FROM events;
SELECT approx_distinct(user_id, 0.01) FROM events; -- цільовий standard error 1%

-- ClickHouse
SELECT uniqHLL12(user_id) FROM events;

-- BigQuery: approximate count із системною точністю
SELECT APPROX_COUNT_DISTINCT(user_id) FROM events;

-- Spark SQL (HyperLogLog++)
SELECT approx_count_distinct(user_id) FROM events;
SELECT approx_count_distinct(user_id, 0.01) FROM events; -- relativeSD

Важливо не переносити параметри точності між платформами механічно. У Trino другий аргумент — цільовий standard error; у Spark — relativeSD. BigQuery APPROX_COUNT_DISTINCT не дозволяє задавати precision, а для матеріалізованих HLL++ sketches і контрольованого precision має окремі HLL_COUNT.* функції.

Де approximate distinct рятує, а де точний COUNT(DISTINCT) все ще потрібен?

Коли statistical error прийнятний, а коли потрібна exactness

Approximate counting підходить:

• оперативні та exploratory dashboards, де важливий порядок величини або тренд;
• великі telemetry/event streams із дуже високою кардинальністю;
• швидкі ad hoc оцінки перед важчими exact-розрахунками;
• pre-aggregated HLL/HLL++ metrics, якщо бізнес явно приймає статистичну похибку.
  Водночас DAU/MAU не можна автоматично записувати в «approximate» категорію: в Uber частина таких метрик вимагала точного результату через їхню роль у фінансовій звітності.

Точний COUNT(DISTINCT) потрібен:

• фінансові, регуляторні та юридично значущі показники, якщо допускається лише exact result;
• reconciliation і контрольні звірки;
• deduplication, де помилка змінює сам набір записів;
• метрики, визначення яких прямо вимагає точного підрахунку ідентичностей через весь aggregation window.

Типові помилки при виборі exact та approximate distinct counting

Помилка 1: не комунікувати наближеність стейкхолдерам.
Якщо dashboard показує «унікальні користувачі» через approximate function, а бізнес сприймає число як exact, виникає проблема довіри до даних. Approximate metrics потрібно явно документувати разом із очікуваною статистичною похибкою.

Помилка 2: припускати, що всі HLL sketches взаємозамінні.
Формат, precision і правила merge залежать від реалізації. Не варто мержити sketches з різних engines, версій або параметрів без перевірки сумісності. У межах однієї платформи використовуйте її офіційний sketch type і merge-функції.

Помилка 3: очікувати, що approx_distinct автоматично вирішить усі проблеми продуктивності.
Движок усе одно повинен прочитати релевантні дані. Partition pruning, clustering/sorting, file statistics, pushdown і правильний data layout залишаються важливими навіть для approximate aggregation.

Погляд практика: що кейс Uber змінює в підході до approximate та exact аналітики

HyperLogLog — сильний інструмент, коли approximation є частиною контракту метрики. Але кейс Uber добре показує іншу сторону: на великих даних «приблизно» не завжди є єдиним способом масштабуватися. Якщо exactness має бізнес-цінність, інженерна задача полягає в пошуку структури даних і execution model, які зберігають точність без монолітного memory bottleneck.

Головна навичка — починати не з вибору функції, а з вимог метрики. Чи може вона мати статистичну похибку? Чи є вона non-rollup? Яке aggregation window? Яка кардинальність? Чи потрібно повторно об’єднувати partial results? Відповіді на ці питання визначають, чи вам потрібен HLL, exact bitmap, sort-based distinct або інший підхід.

Практична порада: позначайте approximate metrics у data contracts і dashboards, а для exact high-cardinality jobs вимірюйте не лише heap, а й розмір serialized aggregation state, shuffle, GC та межі конкретного runtime. У випадку Uber саме структурний JVM-ліміт, а не просто «замало RAM», був коренем проблеми.

Для експерименту порівняйте COUNT(DISTINCT) і approximate distinct на великій таблиці, але не робіть висновок лише за швидкістю. Порівняйте також похибку, memory footprint, shuffle і те, чи відповідає результат бізнес-вимогам.

FAQ: питання про COUNT DISTINCT на великих даних, Uber і HyperLogLog

Питання: Що саме зробив Uber, щоб exact COUNT(DISTINCT) не падав з OOM?

Відповідь: Uber розбив один великий Roaring64Bitmap на 65 536 незалежних chunk-ів. UUID хешується через xxHash64, верхні 16 бітів визначають chunk, а кожен chunk серіалізується окремо. Це прибирає необхідність матеріалізувати весь aggregation state в одному Java byte[] і обходить приблизно 2-гігабайтний JVM-ліміт. На фінальній стадії повертається лише 8-байтний exact cardinality result.

Питання: Що таке HyperLogLog і коли його використовувати для COUNT(DISTINCT)?

Відповідь: HyperLogLog — probabilistic cardinality estimator. Він зберігає компактний sketch замість усіх distinct identifiers, тому пам’ять залежить переважно від precision, а не від cardinality input. Його варто використовувати там, де бізнес приймає статистичну похибку. У Trino approx_distinct() базується на HyperLogLog; Spark SQL approx_count_distinct() використовує HyperLogLog++.

Питання: HyperLogLog vs точний COUNT(DISTINCT) — що обрати для аналітики?

Відповідь: Якщо метрика допускає статистичну похибку і пріоритетом є компактний state та швидка агрегація, HLL/HLL++ часто є хорошим вибором. Якщо результат є фінансово, регуляторно або продуктово критичним і має бути exact, потрібен точний алгоритм. Кейс Uber показує, що на мільярдах UUID exact counting теж можна масштабувати, якщо правильно спроєктувати aggregation state.

Питання: Які помилки роблять при COUNT(DISTINCT) на великих даних?

Відповідь: Типові помилки — не оцінити distinct cardinality та aggregation window; вважати будь-який OOM просто наслідком недостатньої RAM; використовувати approximate result там, де потрібна exactness; не документувати статистичну похибку; і переносити HLL sketches між engines або precision-параметрами без перевірки сумісності.

Висновок

COUNT DISTINCT на великих даних — це не просто SQL-функція, а вибір representation та execution model. Approximate algorithms на кшталт HyperLogLog дозволяють отримати компактний і mergeable cardinality sketch, якщо статистична похибка прийнятна. Але вони не є універсальною відповіддю на OOM.

Кейс Uber показує протилежний сценарій: для критичних non-rollup метрик компанія зберегла exact semantics і перепроєктувала Roaring64Bitmap aggregation state. 16-бітне chunking, незалежна streaming serialization і cardinality-only final output прибрали 2-гігабайтний JVM bottleneck; після rollout на 75 metric families Uber повідомив про нуль OOM failures.

Практичний наступний крок: перед вибором COUNT(DISTINCT), HLL або bitmap оцініть кардинальність, aggregation window, вимогу до exactness і межі execution engine. Тоді оптимізація буде архітектурним рішенням, а не випадковою заміною однієї SQL-функції іншою.

А якщо хочете навчитися будувати scalable data-платформи з Spark, dbt та сучасними warehouse-рішеннями — зверніть увагу на спеціалізацію Analytics & Data Engineer від Data Lab.