Системный дизайн сервиса такси: геолокация водителей, геоиндексы и матчинг

Как спроектировать сервис такси вроде Uber или Яндекс Go на system design интервью: поток GPS-точек, geohash, quadtree и H3, поиск ближайших водителей, матчинг и состояние поездки.

11 мин чтениясистемный дизайн · геоданные · python

Коротко

ВопросРешение в этом разборе
Главная нагрузкане заказы, а GPS-точки: 1 млн водителей × точка раз в 4 с = 250 тыс. записей в с
Где хранить позициив памяти, шардированно по географии; в базу пишется только история треков
Геоиндексgeohash или H3: ячейка как ключ, поиск по своей ячейке и соседям
Поиск водителейкандидаты по ячейкам → фильтр по статусу → сортировка по ETA, а не по прямой
Матчингпредложение одному водителю за раз, с блокировкой и таймаутом
Состояние поездкиконечный автомат в надёжной базе, переходы через проверку версии
Связь с клиентамиWebSocket или долгоживущее соединение для водителя, push как запасной канал

Сервис такси — любимая задача на секции системного дизайна, потому что в ней две очень разные системы под одной крышей. Первая — горячий поток координат: сотни тысяч мелких записей в секунду, каждая живёт несколько секунд и почти никому не нужна потом. Вторая — поездки и деньги: записей мало, но каждая должна быть консистентной, и двойное назначение водителя или потерянная оплата недопустимы.

Сильный кандидат разделяет эти два мира в первые десять минут. Слабый пытается положить координаты в ту же PostgreSQL, где лежат поездки, и делает WHERE lat BETWEEN ... AND lon BETWEEN ....

Общий порядок секции описан в статье про подходы к проектированию систем. Идём по нему: требования, оценка, API, архитектура и дальше вглубь.

Шаг 1. Требования

ВопросОтвет интервьюераЧто это меняет
Что делает пассажир?видит машины рядом, заказывает, следитпоиск рядом и подписка на позицию водителя
Что делает водитель?выходит на линию, принимает заказыпоток координат и канал для предложений
Как выбирается водитель?система предлагает, водитель принимаетматчинг с таймаутами и повторами
Совместные поездки, тарифы, доставка?вне рамокодин тип поездки, одна машина на заказ
Динамическое ценообразование?кратко, если останется времянужна статистика спроса и предложения по ячейкам
Оплата?есть, но платёжный сервис внешнийпоездка отдаёт итог, списание асинхронное
География?много городов в разных странахшардирование по региону естественно

Нефункциональные требования проговорите сами:

  • Позиция водителя на карте пассажира отстаёт не больше чем на несколько секунд. Потерять одну точку не страшно, следующая придёт через 4 секунды.
  • Один водитель никогда не получает две поездки одновременно, а одна поездка — двух водителей.
  • Назначение водителя занимает секунды, а не минуты. Пассажир, который ждёт минуту без ответа, уходит к конкуренту.
  • Поездка, которая уже началась, не теряется при падении любого сервиса: от неё зависят деньги.

Отсюда главная мысль разбора: для координат выбираем доступность и скорость, для поездок — консистентность. Если хочется обосновать это формально, пригодится CAP-теорема.

Шаг 2. Оценка нагрузки

Допущения для крупного сервиса:

  • 1 млн водителей на линии в пиковый час по всем городам.
  • Каждый присылает точку раз в 4 секунды. Точка — около 100 байт: id, координаты, скорость, курс, время, статус.
  • 20 млн поездок в сутки, пик втрое выше среднего.
  • Пассажиры открывают приложение и смотрят машины рядом в разы чаще, чем заказывают.
drivers_online = 1_000_000 # водителей на линии в пик update_every_s = 4 # GPS-точка раз в 4 секунды point_bytes = 100 # id, lat, lon, скорость, курс, время, статус writes_per_s = drivers_online / update_every_s print(f"обновлений в секунду: {writes_per_s:,.0f}") print(f"входящий поток: {writes_per_s * point_bytes / 1e6:.0f} МБ/с") # Сколько нужно держать в памяти, если храним только последнюю точку print(f"текущие позиции: {drivers_online * point_bytes / 1e6:.0f} МБ") # История треков за сутки (водитель в среднем 8 часов на линии) points_per_day = drivers_online * 8 * 3600 / update_every_s print(f"точек в сутки: {points_per_day / 1e9:.1f} млрд, " f"{points_per_day * point_bytes / 1e12:.2f} ТБ") trips_per_day = 20_000_000 print(f"поездок в секунду: {trips_per_day / 86_400:.0f} в среднем, " f"{trips_per_day / 86_400 * 3:.0f} в пик")
обновлений в секунду: 250,000 входящий поток: 25 МБ/с текущие позиции: 100 МБ точек в сутки: 7.2 млрд, 0.72 ТБ поездок в секунду: 231 в среднем, 694 в пик

Выводы, которые стоит произнести вслух:

  1. Текущие позиции всех водителей мира помещаются в 100 МБ. Это задача не про объём, а про частоту записей. Держим в памяти.
  2. 250 тыс. обновлений в секунду — много для одной реляционной базы с индексами, но нормально для шардированного in-memory хранилища или очереди.
  3. Поездок меньше тысячи в секунду. Для транзакционной базы это скромно, её можно сделать надёжной и консистентной без героизма.
  4. История треков — около терабайта в сутки. Пишем её асинхронно в дешёвое хранилище: она нужна для расчёта стоимости по фактическому маршруту, разбора споров и аналитики, а не для поиска.

Подробнее про такие прикидки — в статье об оценке нагрузки на салфетке.

Шаг 3. API

Водитель и пассажир держат с сервером долгоживущее соединение: водителю нужно мгновенно получить предложение заказа, пассажиру — видеть, как едет машина. Выбор между WebSocket, long polling и SSE разобран в отдельной статье; здесь берём WebSocket с push-уведомлением как запасным каналом, когда приложение в фоне.

# Водитель WS driver.location {lat, lon, speed, heading, ts} каждые 4 с WS driver.status {status: online | offline} WS <- offer {offer_id, trip_id, pickup, eta_s, expires_at} POST /offers/{offer_id}/accept | /decline POST /trips/{trip_id}/arrived | /start | /complete # Пассажир GET /drivers/nearby?lat=&lon= машинки на карте POST /trips {pickup, dropoff, tariff} Idempotency-Key: <uuid> POST /trips/{trip_id}/cancel WS <- trip.update {status, driver, driver_location, eta_s}

Создание поездки идёт с ключом идемпотентности: на плохой мобильной сети клиент повторит запрос, и без ключа пассажир получит две машины. Как это устроено, рассказано в статье про идемпотентность.

Шаг 4. Архитектура верхнего уровня

Водитель ──WS──► Gateway ──► Location Service ──► Geo Index (in-memory, шарды по регионам) │ │ │ └──► Kafka: locations ──► трек-хранилище, аналитика, surge │ Пассажир ──WS──► Gateway ──► Trip Service ──► Trip DB (PostgreSQL, шарды по городу) ▲ │ │ └──► Matching Service ──► Geo Index (поиск кандидатов) │ │ └──── Push/Connection ◄──┘ ETA Service (граф дорог, пробки)
  • Gateway держит WebSocket-соединения. Это отдельный слой, потому что миллион открытых соединений — отдельная инженерная задача. Он знает, на каком узле висит какой водитель, и умеет доставить ему сообщение.
  • Location Service принимает точки, валидирует (точка из будущего, скачок на 50 км за 4 секунды), обновляет геоиндекс и публикует событие в очередь для всех, кому нужна история. Про очереди — в статье о брокерах сообщений.
  • Geo Index отвечает на один вопрос: кто из свободных водителей рядом с точкой.
  • Trip Service — владелец поездки и её состояния.
  • Matching Service выбирает водителя и проводит его через цикл предложений.
  • ETA Service считает время в пути по графу дорог с учётом пробок. Сам по себе это отдельная большая система; на интервью достаточно сказать, что она есть, и что внутри неё работает что-то из семейства Дейкстры и A* с предподсчётом.

Шаг 5. Геоиндекс: как найти водителей рядом

Наивный вариант — таблица drivers(lat, lon) и запрос по прямоугольнику. Обычный B-tree индекс работает по одной колонке: найдёт всех водителей в полосе широт по всему миру, а потом отфильтрует долготу. При 250 тыс. обновлений в секунду ещё и индекс перестраивается непрерывно. Почему так, подробно в статье про индексы в базах данных.

Все практичные решения делают одно и то же: превращают двумерную точку в ключ ячейки. Дальше «рядом» означает «в той же ячейке или в соседних», а ячейка — обычный ключ в хеш-таблице.

Geohash

Мир делится пополам по долготе, потом по широте, потом снова по долготе и так далее. Каждое деление — один бит, каждые 5 бит — символ base32. Длинная строка — маленькая ячейка, и у точек в одной ячейке общий префикс.

BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz" def geohash(lat: float, lon: float, precision: int = 7) -> str: lat_range, lon_range = [-90.0, 90.0], [-180.0, 180.0] bits, bit_count, even, result = 0, 0, True, [] while len(result) < precision: rng, value = (lon_range, lon) if even else (lat_range, lat) mid = (rng[0] + rng[1]) / 2 if value >= mid: bits = (bits << 1) | 1 rng[0] = mid else: bits <<= 1 rng[1] = mid even = not even bit_count += 1 if bit_count == 5: # 5 бит -> один символ base32 result.append(BASE32[bits]) bits, bit_count = 0, 0 return "".join(result) print(geohash(55.7539, 37.6208)) # Красная площадь print(geohash(55.7520, 37.6175)) # Кремль, ~300 м print(geohash(55.7558, 37.6176, precision=5)) print(geohash(57.64911, 10.40744, 11)) # классический пример из Википедии
ucfv0jd ucfv0j2 ucfv0 u4pruydqqvj

Две точки в 300 метрах друг от друга совпали в шести символах из семи. Длина общего префикса — грубая мера близости, ровно как в задаче про наибольший общий префикс.

Размеры ячеек на экваторе: 5 символов — примерно 4,9 × 4,9 км, 6 символов — 1,2 × 0,6 км, 7 символов — около 150 × 150 м. Ближе к полюсам ячейки сужаются по долготе.

Подводных камней два, и про оба стоит сказать до того, как спросит интервьюер:

  • Граница ячейки. Пассажир стоит у края, водитель в 20 метрах, но в соседней ячейке с совсем другим префиксом. Поэтому ищут всегда в своей ячейке и восьми соседних, а не по префиксу.
  • Неравномерная плотность. В центре Москвы в ячейке 1,2 км сотни водителей, на окраине — ноль. Фиксированный размер ячейки плох или для центра, или для пригорода.

Geohash удобен тем, что его поддерживают готовые инструменты. Например, Redis GEO хранит точки в sorted set с 52-битным geohash в качестве score и умеет искать по радиусу командой GEOSEARCH.

Quadtree

Квадродерево решает проблему плотности: ячейка делится на четыре только тогда, когда в ней слишком много точек. В центре города дерево глубокое и листья маленькие, за городом — один большой лист.

import random CAPACITY = 4 # в проде сотни точек на лист class QuadTree: def __init__(self, lat0, lon0, lat1, lon1, depth=0): self.box = (lat0, lon0, lat1, lon1) self.depth = depth self.points = [] self.children = None def insert(self, lat, lon, item): if self.children: return self._child_for(lat, lon).insert(lat, lon, item) self.points.append((lat, lon, item)) if len(self.points) > CAPACITY and self.depth < 20: self._split() def _split(self): lat0, lon0, lat1, lon1 = self.box mlat, mlon = (lat0 + lat1) / 2, (lon0 + lon1) / 2 d = self.depth + 1 self.children = [ QuadTree(lat0, lon0, mlat, mlon, d), QuadTree(lat0, mlon, mlat, lon1, d), QuadTree(mlat, lon0, lat1, mlon, d), QuadTree(mlat, mlon, lat1, lon1, d), ] for p in self.points: self._child_for(p[0], p[1]).insert(*p) self.points = [] def _child_for(self, lat, lon): lat0, lon0, lat1, lon1 = self.box i = (lat >= (lat0 + lat1) / 2) * 2 + (lon >= (lon0 + lon1) / 2) return self.children[i] def leaves(self): if not self.children: yield self else: for c in self.children: yield from c.leaves() random.seed(1) tree = QuadTree(55.5, 37.3, 56.0, 37.9) for i in range(40): # плотный центр tree.insert(55.75 + random.uniform(-0.01, 0.01), 37.62 + random.uniform(-0.01, 0.01), i) for i in range(40, 48): # редкие окраины tree.insert(random.uniform(55.5, 56.0), random.uniform(37.3, 37.9), i) depths = sorted({leaf.depth for leaf in tree.leaves() if leaf.points}) print("глубины непустых листьев:", depths)
глубины непустых листьев: [1, 2, 3, 6, 7]

Плотный центр ушёл на глубину 6–7, окраины остались на 1–3. Минус для такси: квадродерево хорошо для статичных данных вроде ресторанов в Yelp-подобной задаче, а водители двигаются. Каждое обновление может перенести точку в другой лист, листья приходится делить и сливать, и всё это под 250 тыс. записей в секунду и с конкурентным доступом. На практике дерево перестраивают периодически, а между перестройками живут с устаревшей разбивкой.

H3 и S2

Uber открыл свою библиотеку H3 в 2018 году: Земля покрыта шестиугольниками на 16 уровнях детализации (от 0 до 15). На уровне 0 — 122 базовые ячейки, каждый следующий уровень примерно в 7 раз мельче. Для города обычно берут уровни 7–9: средняя площадь ячейки около 5 км², 0,7 км² и 0,1 км² соответственно.

Почему шестиугольники, а не квадраты:

  • У шестиугольника все шесть соседей на одинаковом расстоянии от центра. У квадрата четыре соседа по сторонам и четыре по углам, и «кольцо вокруг» получается неравномерным.
  • Поиск по кольцам (grid_disk в H3) даёт приблизительный круг, а не квадрат.
  • Агрегаты по ячейкам — спрос, предложение, коэффициент surge — выглядят и считаются ровнее.

Google S2 проецирует сферу на грани куба и нумерует ячейки кривой Гильберта: близкие точки получают близкие 64-битные id, и диапазон id — это область на карте. S2 хорош для покрытия произвольного полигона набором ячеек, например зоны аэропорта.

Что сказать на интервью: «Возьму geohash или H3 с фиксированным уровнем, ячейка — ключ шарда и ключ в хеш-таблице. Плотность решу выбором уровня по городу и поиском по расширяющимся кольцам, а не динамическим деревом». Это честный и рабочий ответ.

ИндексФорма ячейкиСильные стороныСлабые стороны
Geohashпрямоугольникстрока, префиксы, есть в Redis и базахискажения у полюсов, неровные соседи
Quadtreeквадрат, адаптивныйподстраивается под плотностьсложно обновлять движущиеся точки
H3шестиугольникравные соседи, удобные кольца и агрегатыячейки не вкладываются друг в друга точно
S2четырёхугольник на сфереточное покрытие полигонов, иерархиясложнее объяснить за 5 минут

Индекс на практике

Сам индекс — это две хеш-таблицы: «ячейка → множество водителей» и «водитель → последняя позиция и ячейка». Обновление — O(1): убрать из старой ячейки, положить в новую. Поиск — обойти кольца ячеек вокруг пассажира, собрать кандидатов и выбрать k ближайших кучей. Ниже упрощённая версия на квадратной сетке:

import heapq import math from collections import defaultdict CELL_DEG = 0.01 # ~1.1 км по широте; в Москве ~0.6 км по долготе def haversine_m(lat1, lon1, lat2, lon2): r = 6_371_000 p1, p2 = math.radians(lat1), math.radians(lat2) dp, dl = p2 - p1, math.radians(lon2 - lon1) a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2 return 2 * r * math.asin(math.sqrt(a)) def cell_of(lat, lon): return (math.floor(lat / CELL_DEG), math.floor(lon / CELL_DEG)) class DriverIndex: def __init__(self): self.cells = defaultdict(set) # ячейка -> id водителей self.where = {} # id -> (lat, lon, ячейка) def update(self, driver_id, lat, lon): new_cell = cell_of(lat, lon) old = self.where.get(driver_id) if old and old[2] != new_cell: self.cells[old[2]].discard(driver_id) self.cells[new_cell].add(driver_id) self.where[driver_id] = (lat, lon, new_cell) def remove(self, driver_id): old = self.where.pop(driver_id, None) if old: self.cells[old[2]].discard(driver_id) def nearest(self, lat, lon, k=3, max_rings=5): ci, cj = cell_of(lat, lon) found = [] for ring in range(max_rings + 1): for di in range(-ring, ring + 1): for dj in range(-ring, ring + 1): if max(abs(di), abs(dj)) != ring: continue # только новый «квадратный круг» found.extend(self.cells.get((ci + di, cj + dj), ())) # остановиться можно, когда кандидатов с запасом if len(found) >= k and ring >= 1: break scored = ( (haversine_m(lat, lon, *self.where[d][:2]), d) for d in found ) return [(d, round(m)) for m, d in heapq.nsmallest(k, scored)] idx = DriverIndex() idx.update("d1", 55.7560, 37.6170) idx.update("d2", 55.7500, 37.6300) idx.update("d3", 55.7700, 37.5900) idx.update("d4", 55.7545, 37.6215) idx.update("d5", 55.9000, 37.9000) # далеко, не попадёт print(idx.nearest(55.7539, 37.6208, k=3)) idx.update("d4", 55.8000, 37.7000) # водитель уехал print(idx.nearest(55.7539, 37.6208, k=3))
[('d4', 80), ('d1', 333), ('d2', 721)] [('d1', 333), ('d2', 721), ('d3', 2630)]

Выбор k ближайших из кандидатов — та же куча, что в задаче про top-k частых элементов, только ключ — расстояние. Остановка поиска «как только набрали k» — сознательное упрощение: водитель в углу дальнего кольца может оказаться ближе водителя из ближнего. Для точного ответа добавляют ещё одно кольцо. Для такси это неважно: кандидаты всё равно пересортируются по ETA, а прямая на карте и путь по дорогам через реку — разные вещи.

Ещё один нюанс: из индекса надо убирать водителей, которые пропали без offline — разрядился телефон, уехал в тоннель. Последняя позиция хранится с TTL в 30–60 секунд, и если обновлений не было, водитель исчезает из поиска.

Шардирование индекса

Миллион водителей помещается на одну машину, а 250 тыс. записей в секунду — уже на грани. Индекс режут по географии: город или регион — шард, крупный город — несколько шардов по ячейкам H3 или geohash низкого уровня. Поиск пассажира почти всегда попадает в один шард, а на границе шардов запрос уходит в два. Как распределять ключи, чтобы перебалансировка не была болью, описано в статьях про шардирование и репликацию и консистентное хеширование.

Реплики индекса нужны для чтения (машинки на карте у тысяч пассажиров), но строгая консистентность не нужна: отставание реплики на секунду ничего не ломает. Если шард упал, он восстанавливается за несколько секунд просто из следующих обновлений водителей — это главный аргумент за то, чтобы не делать индекс персистентным.

Шаг 6. Матчинг

Найти ближайших — половина дела. Дальше:

  1. Взять 10–20 кандидатов из геоиндекса со статусом «свободен».
  2. Спросить у ETA Service время подачи для каждого и отсортировать.
  3. Предложить заказ лучшему, подождать ответа 10–15 секунд.
  4. Отказ или тишина — следующему кандидату. Кончились кандидаты — расширить радиус или сказать «машин нет».

Главная опасность здесь — гонка: два пассажира рядом заказали одновременно, оба Matching-инстанса выбрали одного и того же водителя. Защита — блокировка на водителя на время предложения. Её проще всего сделать атомарным SET lock:driver:<id> <trip_id> NX PX 15000 в Redis; тонкости и подводные камни распределённых блокировок разобраны в отдельной статье.

locks = {} # в проде Redis: SET lock:driver:<id> <trip> NX PX 15000 def try_lock(driver_id, trip_id, ttl_s, now): owner = locks.get(driver_id) if owner and owner[1] > now: return False # водителю уже предлагают другую поездку locks[driver_id] = (trip_id, now + ttl_s) return True def dispatch(trip_id, candidates, answers, now=0.0, offer_ttl_s=15): """candidates отсортированы по ETA; answers: driver_id -> accept/decline/None.""" for driver_id, eta_s in candidates: if not try_lock(driver_id, trip_id, offer_ttl_s, now): print(f" {driver_id} занят другим предложением") continue answer = answers.get(driver_id) # None = не ответил за 15 с if answer == "accept": return driver_id, eta_s print(f" {driver_id}: {answer or 'таймаут'}") locks.pop(driver_id, None) now += offer_ttl_s if answer is None else 3 return None, None locks["d4"] = ("t0", 10.0) # d4 прямо сейчас думает над другим заказом cands = [("d4", 60), ("d1", 180), ("d2", 240), ("d3", 420)] print(dispatch("t1", cands, {"d1": "decline", "d2": None, "d3": "accept"}))
d4 занят другим предложением d1: decline d2: таймаут ('d3', 420)

Блокировка с TTL защищает от двойного предложения, но не заменяет финальную проверку. Принятие заказа записывается в Trip DB условным обновлением (об этом в следующем шаге): если за время предложения пассажир отменил поездку или водитель успел взять другую, запись не пройдёт.

Последовательно или пачкой

Последовательные предложения честны к водителям, но медленны: три отказа — и пассажир ждёт 45 секунд. Варианты ускорения, которые стоит назвать:

  • Короткий таймаут и предсказание вероятности принятия: водителю, который отказывается от коротких поездок, короткую поездку не предлагают первым.
  • Параллельное предложение двум-трём водителям, первый принявший получает заказ. Быстрее, но остальные видят «заказ уже забрали» и раздражаются.
  • Пакетный матчинг. Копить заказы и свободных водителей в районе 1–2 секунды и решать задачу о назначениях целиком, минимизируя суммарное время подачи. Жадный выбор «каждому пассажиру ближайшего» может отдать водителя тому, кому он нужен меньше. Классический алгоритм для оптимального назначения — венгерский; на практике используют эвристики, потому что точный алгоритм на тысячах пар каждые две секунды дорог.

Динамическое ценообразование

Если интервьюер спрашивает про surge: Location Service и Trip Service публикуют события в очередь, потоковый обработчик раз в минуту считает по каждой ячейке H3 число свободных водителей и число открытых запросов. Отношение спроса к предложению превращается в коэффициент цены, который кладётся в кэш рядом с геоиндексом. Пассажир видит цену до заказа, и она фиксируется в поездке, чтобы не меняться по дороге.

Шаг 7. Состояние поездки

Поездка — это конечный автомат. Каждый переход разрешён только из определённых состояний:

searching ──► driver_assigned ──► driver_arrived ──► in_progress ──► completed ──► paid │ │ │ │ ▼ ▼ └──► searching ▼ no_drivers cancelled (водитель cancelled отказался)

Конкурентные события здесь норма: пассажир жмёт «отмена» в ту же секунду, когда водитель жмёт «на месте»; запрос от приложения повторился после таймаута. Каждый переход — условное обновление с проверкой версии (optimistic locking):

from dataclasses import dataclass TRANSITIONS = { "searching": {"driver_assigned", "no_drivers", "cancelled"}, "driver_assigned": {"driver_arrived", "searching", "cancelled"}, "driver_arrived": {"in_progress", "cancelled"}, "in_progress": {"completed"}, "completed": {"paid"}, } class Conflict(Exception): pass @dataclass class Trip: id: str status: str = "searching" version: int = 0 driver_id: str | None = None def transition(trip: Trip, new_status: str, expected_version: int, **fields): # В базе это один UPDATE ... WHERE id = ? AND version = ? AND status = ? if trip.version != expected_version: raise Conflict(f"версия {trip.version}, ожидали {expected_version}") if new_status not in TRANSITIONS.get(trip.status, set()): raise Conflict(f"{trip.status} -> {new_status} запрещён") trip.status = new_status trip.version += 1 for key, value in fields.items(): setattr(trip, key, value) return trip t = Trip("t1") transition(t, "driver_assigned", 0, driver_id="d4") try: # Пассажир нажал «отмена» на старой версии экрана transition(t, "cancelled", 0) except Conflict as e: print("отказ:", e) transition(t, "driver_arrived", 1) transition(t, "in_progress", 2) try: transition(t, "cancelled", 3) except Conflict as e: print("отказ:", e) print(t)
отказ: версия 1, ожидали 0 отказ: in_progress -> cancelled запрещён Trip(id='t1', status='in_progress', version=3, driver_id='d4')

Конфликт не означает ошибку для пользователя: клиент перечитывает поездку и показывает актуальное состояние. А отмена после назначения водителя может быть платной — это бизнес-правило, которое живёт в том же переходе.

Где хранить. Поездки — сотни записей в секунду, нужны транзакции и строгая консистентность, поэтому PostgreSQL или аналог, шардированный по городу. Город — естественный ключ: поездки не пересекают континенты, а отчёты и поддержка тоже работают по городам.

Как сообщать другим сервисам. Каждый переход — событие для оплаты, уведомлений, рейтинга и аналитики. Чтобы событие не потерялось между коммитом в базу и отправкой в Kafka, используют transactional outbox. Оплата после completed — отдельный шаг с ретраями; если платёж не прошёл, поездка всё равно завершена, а долг висит на пассажире. Цепочку «завершить поездку → списать → начислить водителю» удобно описать как сагу.

Шаг 8. Пассажир следит за машиной

После назначения пассажиру нужна позиция одного конкретного водителя. Не надо для этого ходить в геоиндекс: Location Service при получении точки от водителя с активной поездкой публикует её в канал trip:<trip_id>, на который подписан Gateway пассажира. Это обычный pub/sub, похожий на доставку сообщений в мессенджере.

Точки приходят раз в 4 секунды, а машина на карте должна ехать плавно. Сглаживание и интерполяция между точками — работа клиента. Привязка к дороге (map matching), чтобы машина не ехала по крышам, делается на сервере для трека и на клиенте для отображения.

Узкие места и вопросы вглубь

Шторм переподключений. Узел Gateway упал, 50 тыс. водителей переподключаются одновременно. Клиенты ждут случайную задержку с экспоненциальным ростом, балансировщик равномерно размазывает их по живым узлам. Про алгоритмы распределения — в статье о балансировке нагрузки.

Час пик у аэропорта. Сотни водителей в одной ячейке и очередь из них. Для таких мест делают отдельную логику: виртуальная очередь водителей в зоне вместо «ближайший по прямой», иначе подъехавший последним получает заказ первым.

Поддельный GPS. Водители подделывают координаты, чтобы попасть в зону surge. Location Service проверяет физику: скорость между точками, согласованность с сотовыми вышками и акселерометром, резкие телепортации.

Отказ Matching Service посреди предложения. Состояние поиска не должно жить только в памяти одного инстанса. Поездка в статусе searching с отметкой времени — если её никто не продвигает дольше N секунд, другой инстанс подхватывает. Блокировки водителей истекают по TTL сами.

Рост в 10 раз. Геоиндекс масштабируется добавлением шардов по регионам, Gateway — горизонтально, Trip DB — дроблением городов на шарды. Самым дорогим становится ETA: запросов к графу дорог больше, чем поездок, на порядок. Его кэшируют по парам ячеек и времени суток. Общие подходы — в статье про стратегии кэширования.

Типичные ошибки

  • Хранить текущие позиции водителей в реляционной базе и обновлять строку на каждую точку.
  • Искать «рядом» по префиксу geohash без соседних ячеек и терять водителей за границей.
  • Выбирать водителя по расстоянию по прямой, а не по времени подачи.
  • Матчинг без блокировки: два заказа одному водителю.
  • Состояние поездки как набор флагов is_started, is_cancelled без явного автомата и проверки переходов.
  • Одна система для координат и для поездок: либо координаты тормозят, либо поездки теряют консистентность.
  • Забыть про водителей, которые пропали без offline, и отправлять заказы выключенным телефонам.
  • Синхронное списание денег внутри перехода completed.

Как рассказывать на собеседовании

За 45 минут успейте главное: требования с разделением на «горячие координаты» и «надёжные поездки», оценку с выводом «250 тыс. записей в секунду, но всего 100 МБ данных», схему из Gateway, Location Service, геоиндекса, Matching и Trip Service, затем геоиндекс подробно — ячейки, соседи, выбор между geohash, quadtree и H3. Оставьте 10 минут на матчинг с блокировкой и автомат поездки с проверкой версии: интервьюер почти наверняка спросит про гонки.

Surge, пакетный матчинг, аэропорты и антифрод — по вопросам, по одной-две фразы с конкретикой. Если хочется потренировать соседнюю задачу с потоком событий и fan-out, посмотрите разбор новостной ленты.

Потренироваться в спокойной обстановке

Все задачи