Дизайн Google Maps

Требования

Google Maps обладают гигантским спектром возможностей. Мы состедоточимся только лишь на части из них.

Функциональные требования

• Определение текущего местоположения. Пользователи должны иметь возможность определять свое текущее местоположение на карте (latitude и longitude).
• Рекомендация самого быстрого маршрута. Пользователь должен иметь возможность указать начало и конец маршрута и система должна предложить оптимальный путь по времени и расстоянию в зависимости от типа транспорта.
• После того, как пользователь выбрал маршрут, система должна составить список указаний в текстовом формате, где каждый элемент списка помогает пользователю повернуть или продолжить движение в определенном направлении, чтобы добраться до пункта назначения.

Нефункциональные требования

• High Availability: система должна быть highly available.
• Scalability: Система должна быть масштабируемой, т.к. ей будет пользоваться огромное число пользователей, как обычных, так и различные бизнесы типа Uber или Lyft для поиска маршрутов.
• Рассчет ожидаемого времени прибытия (ETA) не должен занимать много времени. Максимум 3 секунды при заданных начальной и конечной точке пути.
• Точность. Ожидаемое время прибытия (ETA) не должно сильно отличаться от реального времени, требуемого на дорогу.

То, каким образом собираются данные о карте местности, дорогах, перекрестках и т.д., не является частью данного дизайна. Этим занимается как сам Google (при помощи специальных автомобилей), так и государственные организации. Мы будем предполагать, что у нас в расспоряжении есть вся дорожная сеть в виде взвешенного графа. Пересечения дорог - это вершины в таком графе, а дороги - взвешенные ребра.

Челенджи

• Scalability. Наша система должна работать с миллиардами пользователей, которые посылают миллионы запросов в секунду на поиск оптимального маршрута. При этом поиск оптимального маршрута должен осуществляться в гигантском графе с миллиардом вершин. Запуск алгоритма Дейкстры по поиску оптимального маршрута в таком графе займет много времени. А нам нужно обрабатывать миллионы таких запросов в секунду. Поэтому нам нужно придумать масштабируемого решение.
• Рассчет ETA. На время пути будет влиять ряд фактором, таких как пробки, стройка, качество дороги. Нам нужно учитывать эти факторы, если мы хотим достичь нужной точности.

Оценка требуемых ресурсов

Число серверов

Допустим, у нас число daily active users - 500 миллионов (можно взять другое число или уточнить у интервьюера).
Тогда пиковую нагрузку можно оценить в 500 миллионов запросов в секунду (все они одновременно отправляют запрос).

Оценим максимальное число запросов, которое может обработать один сервер. Тут все зависит от множества факторов. Для простоты оценим это следующим образом:

Время выполнения одного запроса = сколько инструкций процессора, которые нужно выполнить в рамках одного запроса * время выполнения одной инструкции

Пусть сколько инструкций процессора, которые нужно выполнить в рамках одного запроса ~ нескольких миллионов.

время выполнения одной инструкции = 1 / частота процессора = 1 / 3.5 * 10^9

Тогда Время выполнения одного запроса ~ 10^6 / 10^9 ~ 10^(-3) секунд

Тогда число запросов, которые может обработать одно ядро за 1 секунду = 1 / (10^(-3)) ~ 1000

На 64 ядрах мы можем выполнить ~ 64k запросов.

Тогда нам нужно 500 миллионов / 64k ~ 8k серверов.

Storage

Для требуемого функционала нам нужно хранить только временные данные в рамках запроса. Поэтому дополнительного хранилища, кроме данных о дорогах, нам не требуется. Но данные о дорогах всей планеты очень объемные. Они могут занимать десятки петабайт.

Network

Если брать среднюю нагрузку за день, то нужно умножить число daily active users * среднее число запросов в день.
Пусть среднее число запросов в день ~ 50.
Средняя нагрузка ~ 500 M * 50 = 25000 M запросов в день.
Или 25000 M / 86400 = 290k запросов в секунду.
Пусть на каждый запрос мы передаем параметры на 200B и возвращаем кроме инструкций по маршруту еще какие-то картинки ~2 MB, то исходящий bandwidth сети должен быть 290k * 2 MB ~ 580 GB/s = 4640 Gb/s

High Level Design

Нам потребуются следующие основные компоненты:

Location finder: сервис, используемый для определения текущего местоположения пользователя и отображения его на карте.

Route finder: Сервис поиска маршрутов используется для нахождения путей между двумя точками.

Navigator: Предложение маршрута через Route finder недостаточно. Пользователь может отклониться от оптимального пути. В этом случае используется сервис Navigator. Этот сервис отслеживает путь пользователей и отправляет обновленный маршрут и уведомления пользователям, как только они отклоняются от предложенного маршрута.

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

Area search service: Этот сервис эффективно вычисляет кратчайший путь между двумя точками. Для этого он сокращает область поиска в графе, сокращая ее до области вокруг начальной и конечной точки. Он делает вызов в Distributed search для получения координат начальной и конечной точки маршрута по их названию. Сокращает область поиска в графе и делает вызов Graph processing service для поиска кратчайшего пути между двумя заданными точками.

Graph processing service: Отвечает за поиск кратчайшего пути в урезанном графе, которые охватывает область вокруг начальной и конечной точки.

Graph DB: Хранит карту в виде взвешенного графа, где вершины - это пересечения дорог, а ребра - это дороги.

Graph Building: Получает данные о картах и дорогах, преобразует эти данные в граф и сохраняет в Graph DB.

Pub/Sub: Процессит поток данных о положении пользователей. В случае, если пользователь отклонился от марштура, система это обнаружит и вызовет Area search service для перестройки марштура. Также может использовать данные о положении для прогнозирования пробок и получения даннных о скорости и пробках на конкретных дорогах. Можно использовать Kafka, как основную технологию для этой компоненты.

Workflow

• Пользователь в приложении указывает в качестве начальной точки свое текущее местоположение, а также название конечной точки маршрута.
• При наборе названия конечной точки маршрута можно использовать Typeahead для подсказок названий мест и для предотвращения ошибок написания.
• После указания начальной и конечной точки, пользователь нажимает кнопку для поиска оптимального маршрута.
• Этот запрос перенаправляется в Route finder сервис, который в свою очередь вызывает Area search service.
• Area search service использует Distributed search для поиска координат начальной и конечной точки по их названию. Полученные значения координат используются для вычисления урезанного графа для поиска. Далее запрос на вычисление кратчайшего пути перенаправляется в Graph processing service.
• Graph processing service находит кратчайший путь в учезанном графе.
• Route finder занимается визуализацией вычесленного оптимального маршрута
• Navigator постоянно получает текущее положение пользователя и проверяет, что пользователь находится на маршруте. Как только он обнаруживает, что пользователь отклонился от маршрута, он отправляет event в Kafka для перестройки маршрута.
• Navigator также отправляет данные о текущем местоположении через Kafka в Graph Building сервис для обновления информации в Graph DB для повышения точности вычисления оптимального пути с учетом пробок, скоростей автомобилей и т.д.

Вычисление кратчайшего пути

Для вычисления кратчайшего пути можно использовать алгоритм Дейкстры
Но т.к. граф у нас гигантский (все дороги Земли), нам нужно это вычисление оптимизировать.
Для этого мы можем производить вычисления на урезанном графе. Для этого разобьем всю карту земли и соотвествующий граф дорог на сегменты. Например, 5 на 5 километров. Форма сегментов может быть полигональной. Для простоты будем предполагать, что форма сегмента - квадрат.

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

Что делать, если начальная и конечные точки лежат не в вершинах дорожного графа, а где-то между?

В этом случае мы вычисляем расстояние до ближайших вершин от начальной и конечной точки и проводим вычисление кратчайшего пути используя тот же алгоритм Дейкстры.

Хорошо, мы обсудили как вычислять кратчайшее расстояние, если у нас начальная и конечная точка лежат в рамках одного сегмента. Но что делать, если они лежат в разных сегментах?

В таком случаем мы можем измерить кратчайшее расстояние между двумя точками на шаре (если предположить, что Земля не плоская) при помощи Haversine formula. Допустим оно получилось 10 км. Когда мы включим в наш поиск сегменты, которые лежат на расстоянии до 10 км во всех направлениях от начальной и конечной точки.
Более того, мы можем еще больше упростить наш граф. Для каждого сегмента мы можем учитывать только выходные/пограничные точки графа, которые являются общими для двух смежных сегментов.

Продолжение следует. Дополню High Level Design частью про менеджмент сегментов.