System Design
Case Study: Uber
В 2014 году в Сан-Франциско Uber на Halloween на час отключил surge pricing. Время ожидания подскочило с 5 до 30 минут, completion rate упал на 70%, и компания через час вернула surge. Цена - это не жадность, это control loop.
- Uber: 25M поездок в день, 5M активных водителей, latency на матчинг < 2 секунд во всех 70+ странах.
- H3 (Uber-разработанная hex-grid): покрытие земли с разрешением 1 кв.м, всё в Apache Foundation, используется в Foursquare, DoorDash, Airbnb.
- Apache Pinot (Uber-разработка): real-time analytics на trip events с p99 < 200 ms на петабайтах данных.
- DISCO (Dispatch Optimization): глобальная задача матчинга решается на 10K H3-ячейках independently, координация только на границах.
Требования и масштаб
Цели урока
- Определить функциональные и нефункциональные требования
- Провести back-of-envelope estimation
- Понять уникальные challenges ride-sharing platform
Функциональные требования
Uber - это real-time платформа, соединяющая водителей и пассажиров. Ключевые функции:
Масштаб Uber (реальные цифры)
Back-of-Envelope Estimation
Ключевые технические challenges
High-Level Architecture
Ключевые идеи
- Uber - это real-time location-centric система
- Главные challenges: 1M+ location updates/sec, matching за <15 сек, accurate ETA, dynamic pricing
- Ключевые компоненты: Location Service (Redis Geo), Matching Service, Trip Service, Pricing Service
Что является главной нагрузкой в системе типа Uber?
Geospatial Indexing
Цели урока
- Понять различные подходы к geospatial indexing
- Изучить Geohash, S2, и H3 системы
- Освоить Redis Geospatial для location queries
Проблема: spatial proximity queries
Главный запрос в Uber: "найди всех водителей в радиусе 3 км от точки (lat, lng)". Как сделать это быстро при миллионах водителей?
Geohash
Geohash кодирует координаты в строку. Близкие точки имеют общий prefix. Это позволяет использовать prefix search.
H3 (Uber's Solution)
H3 - это hexagonal hierarchical spatial index, разработанный Uber. Hexagons решают проблему edge effects и обеспечивают uniform distance.
Redis Geospatial Implementation
H3 + Redis для высокой нагрузки
Сравнение подходов
Ключевые идеи
- Geospatial indexing превращает O(N) proximity search в O(1) cell lookup
- Geohash - простой и встроен в Redis
- H3 - hexagonal grid с uniform distance, разработанный Uber специально для ride-sharing
- Выбор зависит от требований: простота (Geohash) vs оптимальность (H3)
Почему Uber использует hexagonal cells (H3) вместо rectangular (Geohash)?
Matching Algorithm
Цели урока
- Понять проблему driver-rider matching
- Изучить scoring и ranking drivers
- Освоить batch matching для оптимизации
Проблема: оптимальное matching
Наивный подход "ближайший водитель" работает плохо при высокой нагрузке. Почему?
Batch Matching Approach
Driver Scoring
Не только расстояние влияет на выбор водителя. Uber использует multi-factor scoring:
Matching Service Implementation
Race Conditions и Locking
Ключевые идеи
- Matching в Uber - это не просто 'ближайший водитель'
- Batch matching каждые 2-3 секунды позволяет оптимизировать global assignment
- Scoring учитывает ETA, heading, rating, acceptance rate
- Optimistic locking предотвращает race conditions при concurrent matching
Почему batch matching лучше последовательного matching?
Dynamic Pricing (Surge)
Цели урока
- Понять экономику supply-demand в ride-sharing
- Изучить алгоритм surge pricing
- Освоить zone-based pricing calculation
Зачем нужен surge pricing
Surge pricing (динамическое ценообразование) - это механизм балансировки спроса и предложения в real-time. Без него система не работает при пиках спроса.
Zone-Based Surge Calculation
Surge Calculation Algorithm
Fare Calculation
Anti-Gaming Measures
Ключевые идеи
- Surge pricing балансирует supply и demand в real-time
- Город разбит на зоны (H3 cells), для каждой зоны считается demand/supply ratio и surge multiplier
- Smoothing предотвращает резкие скачки
- Anti-gaming measures защищают от манипуляций со стороны водителей и пассажиров
Почему применяется smoothing к surge multiplier?
Real-Time Architecture
Цели урока
- Спроектировать trip state machine
- Понять real-time communication patterns
- Изучить fault tolerance для critical operations
Trip State Machine
Каждая поездка проходит через определённые состояния. State machine обеспечивает consistency и правильную обработку edge cases.
Real-Time Communication
Trip Service Implementation
Fault Tolerance
Ключевые идеи
- Real-time architecture Uber включает: Trip State Machine с валидацией transitions, dual-channel communication (HTTP/2 для updates, WebSocket для push), optimistic locking для consistency
- Fault tolerance обеспечивается через authorization holds, multi-layer fallbacks, и geographic partitioning
Surge pricing - это просто механизм увеличения прибыли Uber: больше спроса = выше цена = больше денег платформе.
Surge - это control loop, который привлекает водителей в region с высоким спросом. Без surge драйверы остаются дома, и waiting time выходит за SLA. Цена закрывает gap supply/demand быстрее, чем расписание.
Uber paper (Diamond & Hall 2015) показал: при отмене surge в Halloween 2014 в Сан-Франциско wait time подскочил с 5 до 30+ минут, completion rate упал на 70%. Surge - не extraction, а распределённый сигнал, балансирующий рынок в реальном времени.
Почему Uber использует authorization hold вместо прямого charge после поездки?
Связь с предыдущим
YouTube решал задачу распределения статичного контента: видео загружается раз, читается миллиарды раз. Uber решает противоположную задачу - real-time matching стохастической supply (водители) со стохастическим demand (пассажиры) в течение секунд. Те же CDN-паттерны заменяются на geospatial sharding, ABR-стратегии - на surge control loop.
- Case Study: YouTube — От read-heavy static content к real-time matching
- Consistent Hashing — Геошардинг через H3 hex-grid - consistent hashing на сферу
- Redis — Driver location с TTL 5s - hot path Uber matching
Итоги
- Geospatial indexing через H3 hex-grid: вся планета покрыта иерархией шестиугольников, каждый ride/driver мапится в ячейку за O(1).
- Driver location storage: Redis с TTL 5 сек, ключ = driver_id, hot data только. Postgres хранит trip-state, не геолокацию.
- Matching algorithm: DISCO смотрит drivers в радиусе 5 km, считает ETA через batched routing, оптимизирует waiting time globally в окне 5 сек.
- Dynamic pricing - control loop: surge multiplier = f(supply, demand, history); пересчитывается каждые 60 сек на H3 cell.
- Trip state machine: 8 состояний, transitions валидируются central service. Optimistic locking защищает от race conditions при concurrent updates.
- Real-time architecture: HTTP/2 server push для driver app, WebSocket для rider app, Apache Kafka для event stream, Pinot для analytics.
Вопросы для размышления
- Surge pricing работает как control loop. Что произойдёт, если added latency между измерением spike и применением цены вырастет с 60 сек до 5 минут? Какой механизм компенсирует delay?
- Геошардинг через H3 работает на земной поверхности. Как изменится архитектура для service на воде (морская перевозка) или в воздухе (drone delivery)?
- Optimistic locking на trip state выбран вместо pessimistic. Какой паттерн ошибок появляется при росте concurrent updates 1000x, и какая защита (CRDT? consensus?) применима в качестве escape hatch?
Связанные уроки
- sd-15-youtube — YouTube scale паттерны: геораспределённые данные
- sd-18-consistent-hashing — Consistent hashing для шардирования геоданных
- net-15-tcp-basics — WebSocket/long polling для real-time обновления позиции
- db-19-redis — Redis хранит текущие позиции водителей (TTL = 5 сек)
- alg-14-dijkstra