Дизайн Google Maps
Tags: systemdesign, interview, google, faang
Published: 2024-04-03 22:05:42

## Требования
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, как основную технологию для этой компоненты.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3a73frdrqxepvc1zbqtl.png)



**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 для повышения точности вычисления оптимального пути с учетом пробок, скоростей автомобилей и т.д.

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

Для вычисления кратчайшего пути можно использовать [алгоритм Дейкстры](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B)
Но т.к. граф у нас гигантский (все дороги Земли), нам нужно это вычисление оптимизировать.
Для этого мы можем производить вычисления на урезанном графе. Для этого разобьем всю карту земли и соотвествующий граф дорог на сегменты. Например, 5 на 5 километров. Форма сегментов может быть полигональной. Для простоты будем предполагать, что форма сегмента - квадрат.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jopj05p30l7eu8s8jbr5.png)

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



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/m25cw1i9ehy3ad4p0ln5.png)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tc6ko83242rvddhbv57u.png)


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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hwr8w4oqwvj6s8shvwlh.png)

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

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t7ardgmbmzk5g9riixxq.png)

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