Базы данных
System Design: геолокационный сервис (Uber)
Когда пассажир открывает Uber в Нью-Йорке в час пик, система должна найти ближайшего свободного водителя среди 50,000 активных в городе - за 500 миллисекунд. Обычный SQL запрос по координатам занял бы секунды. Uber решил задачу через H3 гексагональную сетку + Redis - 1 миллисекунда.
- **Uber**: H3 опубликован как open source в 2018, используется для matching, surge pricing и analytics
- **Lyft**: аналогичная архитектура с Redis GEO commands и GEORADIUS для поиска водителей
- **DoorDash**: H3 для зонирования доставки - определение зоны по координатам ресторана за O(1)
Требования и масштаб
Uber обрабатывает 28 миллионов поездок в день в 70+ странах. Ключевая задача - matching: найти ближайшего свободного водителя для пассажира за < 500ms. Система получает обновления GPS от 5 миллионов активных водителей каждые 4 секунды - это 1.25 миллиона событий в секунду только на location updates.
Uber разделил сервисы по доменам: Dispatch (matching), Supply (водители), Demand (пассажиры), Maps (маршруты). Каждый домен имеет свою БД - это позволяет масштабировать независимо. Dispatch использует in-memory geospatial store, не PostgreSQL.
Uber получает GPS от 5M водителей каждые 4 сек. Сколько location updates/sec поступает в систему?
Геопространственные индексы
Наивный подход - хранить lat/lng и делать запросы вида WHERE lat BETWEEN x1 AND x2 AND lng BETWEEN y1 AND y2. Это не масштабируется: 2D range queries не покрываются обычными B-Tree индексами эффективно. Решение - пространственные индексы: R-Tree (PostGIS), квадродеревья (QuadTree), S2 geometry (Google), H3 (Uber).
R-Tree хранит минимальные ограничивающие прямоугольники (MBR) для групп объектов. ST_DWithin использует R-Tree: сначала фильтрует по MBR (быстро), затем точная проверка по расстоянию. Это позволяет обрабатывать geo-запросы к 10M+ точкам за миллисекунды.
Почему обычный B-Tree индекс по (lat, lng) неэффективен для поиска ближайших точек?
H3: гексагональная сетка Uber
Uber разработал H3 - систему разбиения Земли на иерархические шестиугольники. Шестиугольники лучше квадратов: все 6 соседей равноудалены от центра, нет угловых эффектов. H3 имеет 16 уровней разрешения: resolution 9 (~174 м диаметр), resolution 12 (~1.5 м). Каждая ячейка кодируется 64-bit integer - можно хранить как обычный числовой индекс.
Uber использует H3 в production с 2018 года и опубликовал как open source. Помимо matching, H3 используется для ценообразования (surge pricing по ячейкам), аналитики (агрегация поездок по зонам), machine learning features для предсказания спроса.
Почему H3 использует шестиугольники, а не квадраты?
Real-time трекинг местоположения
Архитектура location tracking в Uber: мобильное приложение водителя шлёт GPS каждые 4 сек через WebSocket. Supply Service пишет в Kafka topic (partitioned by city), Dispatch Service читает и обновляет Redis. Redis хранит текущее положение водителей - O(1) чтение, sub-millisecond latency. Cassandra хранит исторический GPS trail.
Cassandra для GPS history: partition key = (driver_id, date), clustering key = timestamp. Это позволяет эффективно читать маршрут водителя за день. Write-heavy workload Cassandra обрабатывает лучше PostgreSQL благодаря LSM-Tree архитектуре. Uber хранит GPS данные 30 дней для расследования инцидентов.
PostgreSQL с PostGIS достаточно для хранения real-time location 5M водителей
PostgreSQL используется для постоянного хранения и сложных geo-запросов, но real-time matching требует in-memory store (Redis) с sub-millisecond latency
PostGIS ST_DWithin на 5M строк даже с индексом займёт 10-100ms - слишком медленно для matching SLA 500ms. Redis SUNION по H3 ячейкам возвращает ближайших водителей за <1ms. Uber использует оба: Redis для matching, Cassandra для истории и аналитики.
Зачем устанавливать TTL на Redis ключи driver:location в 30 секунд?
Итоги
- **1.25M updates/sec** - масштаб Uber требует in-memory геопространственного хранилища, не PostgreSQL
- **H3 шестиугольники** - равноудалённые соседи, иерархические уровни, 64-bit integer ключ для Redis Set
- **Redis + Cassandra** - Redis для real-time matching с TTL 30 сек, Cassandra для GPS history
Связанные темы
Геолокационный сервис сочетает несколько технологий из других уроков:
- Redis структуры данных — Set и Hash - основа хранения driver location и cell membership в H3 ячейках
- Cassandra data modeling — GPS history хранится в Cassandra с partition key (driver_id, date) для efficient reads
- Шардинг — Kafka topic для location updates партиционируется по city - аналог шардинга по географии
Вопросы для размышления
- Uber хранит GPS trail в Cassandra с partition key (driver_id, date). Что произойдёт если один водитель очень активен - будет ли проблема с hot partition?
- H3 resolution 9 даёт ячейки ~174м. Какой resolution и k-ring radius выбрать для airport pickup (большой радиус) vs центр города (высокая плотность)?
- Как система должна обрабатывать ситуацию когда водитель теряет GPS сигнал в тоннеле на 2 минуты во время поездки?