Проектируем Google Maps
Проектируем Maps: тайлы из CDN, маршрутизация по дорожному графу с Dijkstra/A* и contraction hierarchies, ETA по приёму трафика, геокодинг — с опорой на партиционирование континентального дорожного графа, чтобы маршрутизация была быстрой.
Спросите маршрут через страну — и учебник скажет «запусти Dijkstra». Попробуйте на реальном дорожном графе — десятки миллионов перекрёстков, сотни миллионов сегментов дорог — и один запрос исследует половину континента, прежде чем найдёт цель, отнимая секунды на запрос, когда нужны миллисекунды на планетарном QPS. Maps — это на самом деле три тяжёлые системы в одном приложении: сервис тайлов, рисующий мир, маршрутизатор, отвечающий «быстрейший путь» быстрее, чем позволяет перебор, и пайплайн трафика, держащий ответ честным, пока дороги встают в пробки. Объединяющий трюк всех трёх — предвычисление: сделать работу масштаба континента один раз, офлайн, чтобы каждый живой запрос трогал лишь её осколок.
После этого урока ты поймёшь, почему «просто запусти Dijkstra» рушится на планетарном масштабе, как офлайн-предвычисление делает маршрутизацию в реальном времени возможной и почему данные трафика нужно отделить от структуры графа, чтобы не перестраивать всё каждую минуту.
Требования
- Функциональные: рисовать карту (пан/зум), находить быстрейший маршрут между двумя точками, показывать ETA с учётом текущего трафика и превращать адрес в координаты (геокодинг) и обратно.
- Нефункциональные: очень read-heavy и глобально распределённая; тайлы и маршруты запрашиваются везде разом. Тайлы почти статичны и должны быть быстры (с края). Маршрутизация должна быть низколатентной несмотря на граф, слишком большой для наивного поиска. ETA должны отслеживать реальность, так что приём трафика — непрерывный высокообъёмный поток.
Сквозная мысль — почти ничто нельзя считать с нуля на запрос на таком масштабе. Базовая карта меняется редко, дорожный граф — медленно, а трафик меняется быстро, но разделяется всеми пользователями на дороге — поэтому схема определяется тем, что вы предвычисляете и где кэшируете.
Оценки
Карта — пирамида тайлов: на уровне зума z мир — сетка 2^z × 2^z картинок по 256 пикселей. Это 1 тайл на z0, 4 на z1 и примерно 4^z на уровне z — так что полная пирамида до z20 — сотни миллиардов тайлов, терабайты-петабайты в основном статичных изображений. Они пишутся один раз (на обновление карты) и читаются миллиарды раз: учебниковая CDN-нагрузка. Маршрутизация — другая крайность: малые данные (дорожный граф страны влезает в память, единицы ГБ), но дорогое вычисление, где наивный поиск посещает миллионы узлов. Так что две половины Maps нагружают совершенно разные ресурсы: тайлы — хранилище и трафик края, маршрутизация — CPU и хитрые алгоритмы.
Высокоуровневая схема
Тайлы текут из объектного хранилища через CDN к клиенту. Запрос маршрута идёт в сервис маршрутизации, держащий предобработанный дорожный граф; он сверяется с последними весами трафика и возвращает путь. Геокодинг — отдельный сервис, переводящий текст в координаты.
Важные глубокие погружения — как маршрутизация уходит от перебора и как трафик перевзвешивает граф без обесценивания предвычисления.
Глубокое погружение
Тайлы и CDN
Тайл адресуется (z, x, y) — уровень зума и координаты сетки — так что клиент вычисляет, какие именно тайлы нужны его вьюпорту, и запрашивает по имени. Так как контент тайла идентичен для каждого пользователя и меняется лишь при обновлении карты, это идеальный объект CDN: предвычислить пирамиду в объектное хранилище, прикрыть CDN и отдавать с края-POP, ближайшего к пользователю. Ключи кэша неизменны на версию карты, так что инвалидация редка, а бамп версии чисто ротирует всё. Векторные тайлы (геометрия плюс стиль, рисуются на клиенте) идут дальше: меньше пейлоад, перестилизуемы без серверного ре-рендера и чёткие на любом зуме. Суть в том, что весь опыт базовой карты — задача распределения статичного контента, полностью отдельная от динамического движка маршрутизации.
Маршрутизация: почему наивный Dijkstra проигрывает
Dijkstra и A* корректны, но исследуют слишком много. Dijkstra расходится во все стороны, пока не достигнет цели; на континентальном графе это миллионы раскрытий узлов на запрос. A* с эвристикой по прямой помогает, но всё равно исследует широкий конус. На QPS Maps ни один не по карману. Продакшен-ответ — предобработка: потратить часы офлайн на преобразование графа, чтобы онлайн-запросы были дёшевы.
Contraction hierarchies (CH) — каноническая техника. Ранжируем каждый узел по важности, затем «сжимаем» их от наименее к наиболее важному: убирая узел, добавляем рёбра-сокращения между его соседями, сохраняющие кратчайшие расстояния. После сжатия запрос бежит двунаправленным поиском, который движется только вверх по иерархии — от истока вверх к важным узлам-магистралям и от цели вверх навстречу. Длинные маршруты едут на горстке высокоуровневых сокращений (выехать на магистраль, ехать по ней, съехать у цели) вместо проползания по каждой местной улице. Итог — запросы трогают тысячи узлов вместо миллионов — на порядки быстрее, при этом возвращая точный кратчайший путь.
▸Почему это работает
Почему сжатие узлов в сокращения ускоряет запросы, не меняя ответ? Потому что бо́льшая часть длинной поездки проходит по нескольким крупным дорогам, а запрос снова и снова переоткрывает этот очевидный факт. Ребро-сокращение запекает «дешевейший путь от этого въезда до того съезда уже известен и стоит X», так что поиск никогда не переисследует улицы между ними. Иерархия гарантирует свойство: для любого кратчайшего пути есть эквивалентный, который сначала идёт только «вверх» по важности, а потом только «вниз», так что поиск, отказывающийся спускаться, пока два фронта не встретятся, может игнорировать огромную низкоуровневую внутренность. Вы меняете время предобработки и лишние рёбра-сокращения (больше памяти) на скорость запроса — ровно та сделка предвычисления, что проходит через весь Maps. CH также объясняет, почему перекрытие дороги неудобно: оно может обесценить сокращения, так что трафик, меняющий веса рёбер, нуждается в схеме, не вынуждающей полное пересжатие.
Трафик, ETA и перевзвешивание
Маршрут хорош ровно настолько, насколько верны веса его рёбер, а реальное время поездки зависит от живого трафика. Maps принимает непрерывный поток анонимизированных GPS-зондов от движущихся телефонов, агрегирует скорость по сегменту дороги и обновляет текущий вес-время-в-пути каждого ребра. ETA тогда — сумма (возможно скорректированных трафиком) времён рёбер вдоль выбранного пути, часто уточнённая моделью, учитывающей паттерны времени суток и исторические кривые, а не только мгновенный снимок. Архитектурное напряжение — чистые contraction hierarchies запекают веса в сокращения, так что смена весов под трафик потребовала бы перезапуска дорогого сжатия. Продакшен разделяет медленно меняющуюся структуру графа (предобрабатывается редко) и быстро меняющиеся веса (обновляются непрерывно), используя техники семейства customizable-route-planning, позволяющие живому трафику перевзвешивать рёбра без перестройки всей иерархии. Урок: партиционируйте предвычисление вдоль его скорости изменения.
Узкие места и компромиссы
Первая трудная задача — партиционирование графа. Континентальный дорожный граф не шардится чисто: разбейте его на регионы — и маршруты, пересекающие границу, нуждаются в аккуратной сшивке на рёбрах-разрезах (граничные узлы), а плохое партиционирование кладёт горячие, часто пересекаемые магистрали на шов. Хорошие партиции режут вдоль естественных малотрафиковых границ, минимизируя кросс-шардовые маршруты — тот же инстинкт «минимизируй пересекающее границу», что в дизайне ячеек урока близости, теперь на разрез графа. Вторая — напряжение предвычисление-против-свежести: тяжелее предобработка — быстрее запросы, но труднее свернуть обновления (новая дорога, перекрытие, всплеск трафика), поэтому структуру и веса держат на разных каденциях. Третья — разделение двух нагрузок: тайлы хотят жирный глобальный CDN и почти ноль вычислений; маршрутизация хочет мощный CPU рядом с графом и почти ноль трафика — так что их масштабируют и даже размещают независимо, а не как один ярус.
Команда строит континентальную маршрутизацию наивным Dijkstra. Корректно, но каждый запрос отнимает секунды, раскрывая миллионы узлов. Какая предобработка заставит запросы трогать лишь тысячи узлов, всё ещё возвращая точный кратчайший путь?
Maps использует contraction hierarchies, запекающие веса рёбер в сокращения. Теперь надо обновлять времена в пути каждую минуту из живого трафика. Какая архитектура верна?
Объединяющая техника тайлов, маршрутизации и ETA — это _______: сделать работу масштаба континента один раз, офлайн — запечь пирамиду тайлов, сжать дорожный граф в сокращения — чтобы каждый живой запрос трогал лишь малый осколок результата, а не пересчитывал с нуля.
- 01Почему тайлы карты — задача CDN, и как они адресуются и кэшируются?
- 02Почему наивный Dijkstra проваливается на континентальной маршрутизации, и как contraction hierarchies чинят это?
- 03Как живой трафик питает ETA без полного пересжатия, и в чём задача партиционирования?
Maps — это три системы в одном приложении, объединённые предвычислением. Тайлы — задача CDN статичного контента: мир — пирамида адресуемых (z, x, y) изображений по 256 пикселей, предвычисленных в объектное хранилище и отдаваемых с края, с неизменными на версию ключами кэша. Маршрутизация не может использовать наивный Dijkstra на планетарном масштабе — он раскрывает миллионы узлов — так что граф предобрабатывается в contraction hierarchies: узлы ранжированы по важности и сжаты с сохраняющими расстояния рёбрами-сокращениями, позволяя двунаправленному запросу двигаться только вверх и трогать тысячи узлов, всё ещё возвращая точный кратчайший путь. Трафик — непрерывный поток GPS-зондов, перевзвешивающий рёбра для ETA, и так как сжатие запекает веса в сокращения, схема разделяет медленную структуру и быстрые веса, чтобы живой трафик не вынуждал пересжатие. Повторяющиеся трудные задачи — партиционирование графа (резать вдоль естественных малотрафиковых границ, минимизируя кросс-шардовые маршруты), напряжение предвычисление-против-свежести (тяжелее предобработка — труднее обновления) и разделение двух нагрузок (тайлы хотят CDN; маршрутизация хочет CPU), масштабируемых независимо. Теперь, встретив задачу маршрутизации на ревью схемы — медленные запросы, устаревшие ETA или задание переиндексации, длящееся часами — ты знаешь, что спросить: отделена ли структура графа от весов и делается ли офлайн-работа действительно офлайн?
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.