Дизайн Uber/Яндекс Такси
Tags: systemdesign
Published: 2023-07-27 23:43:17

## Задача. 
Нужно сделать дизайн сервиса по типу Uber или Яндекс Такси.

## Решение.
Uber позволяет пассажирам заказывать такси через приложение в телефоне. Водители используют свои или арендованные автомобили для того, чтобы подвозить пассажиров. Пассажиры и водители взаимодействуют друг с другом через приложение Uber.

## Уточнение требований.
У нас два типа клиентов: пассажиры и водители.

- Водители должны периодически передавать свое местоположение и свой текущую доступность (могут ли они сейчас взять нового пассажира или нет)

- Пассажиры могут видеть всех ближайших доступных водителей.

- Пассажир может заказать поездку; Ближайшие водители уведомляются о том, что пассажир заказал поездку.

- Как только водитель и пассажир зааксептили поездку, они могут видеть местоположение друг друга пока не закончится поездка.

- Как только автомобиль прибудет в конечную точку, водитель помечает поездку завершенной и становится доступным для следующих поездок.

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

- Пусть у нас 300M пассажиров и 1M водителей. Ежедневная активность: 1M пассажиров и 0.5M водителей.

- Предположим у нас 1M ежедневных поездок.

- Пусть мы получаем текущее местоположение водителя каждых 3 секунды.

## Основная идея и высокоуровневый дизайн

Одной из ключевых проблем в данном приложении  - это то, как определить ближайшие к пассажиру автомобили такси. Так называемый Proximity Service. 

Можно хранить данные о местоположении такси в некой базе с latitude и longitude. Тогда нам надо каждые **три секунды апдейтить** эту базу текущим местоположением всех активных водителей. А также делать запросы к этой базе, для поиска ближайших такси. 
SQL может быть типа:

> Select * from taxi_positions where latitude between X-D and X+D and longitude between Y-D and Y+D

В силу того, что у нас 500k активных водителей, то нам надо делать 500k/3s = 166k обновлений базы в секунду. 
Еще нам нужно выполнять 1M/(24 * 3600) = 11 запросов в секунду по поиску ближайших такси.
Т.к. в запросе мы фильтруем по диапазону значений для двух колонок, для базы с 1M водителей и нам нужно найти их пересечение, такой запрос может работать очень долго.

**Поэтому рассмотрим альтернативную структуру данных, где мы будем хранить местоположение таксистов.**

Можно разбить карту всего мира на маленькие квадратики, называемые гридами (grids).

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

Далее поместим местоположение всех таксистов в дерево, которое называется **[Дерево квадрантов](https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D0%BD%D1%82%D0%BE%D0%B2) (Quad Tree)**

Корнем дерева является карта всего мира. У него 4 дочерних вершины. Которые делят всю карту на 4 части. У каждой из такой вершин есть 4 другие дочерние вершины, которые также делят текущую часть карты на 4 части и т.д. Листовыми вершинами будут гриды минимального размера. Этот размер можно выбрать исходя из предположения, что мы хотим искать таксистов в рамках одного или максимум нескольких гридов.

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

Нам нужно постоянно апдейтить это дерево текущим местоположением таксистов. Поиск ближайших таксистов будем поиском в таком дереве. Высота такого дерева будет ~20-30. Поиск по такому дереву работает за логарифмическое время и требует ~20-30 операций сравнения. Т.е. такой поиск работает практически мгновенно, особенно, если дерево будет хранится в памяти, а не на диске.

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

**Как работает операция апдейта локейшена такси?** 
Запрос на апдейт проходит через Load Balancer и попадает на один из серверов с Quad Tree. Выполняя поиск по дереву мы найдем нужный нам грид и его GridId. Также будем хранить мапинг таксистов на GridId. Нам нужно или изменить этот мапинг или оставить его таким как есть, если таксист все еще в рамках того же грида. Этот мапинг можно хранить в In-Memory кэше для ускорения доступа.

**Как работает операция поиска ближайших такси?** 
Запрос на поиск проходит через Load Balancer и попадает на один из серверов с Quad Tree. Поиск по дереву выдает нам нужные GridId.
По GridId мы получаем из кэша маппинга списка таксистов в этом гриде. Далее ранжируем их по расстоянию, рейтингу и т.д.

**Сколько нужно памяти для хранения такого дерева?**
Пусть у нас грид размером 5 на 5 км. Площадь земли: 4 * pi * R^2 = 514 M км^2. 
Число гридов ~ 4 * pi * R^2 / (5 * 5) = **20M гридов**. Размер одного грида ~ (8 (GridId) + 4 * 8 (References to childs) + 4 * 8 (Location ranges)) ~72B. Поэтому объем памяти для хранения дерева 72 * 20M **~1.5 GB.**

Также нам нужно хранить маппинг GridId на список таксистов и их местоположение:
1M * (8 (DriverId) + 2 * 8 (Location)) + 20M * 8 (GridId) **~200MB**
Этот маппинг можно хранить также в In-Memory кэше.

На практике лучше делать гриды разного размера. Потому что некоторые области Земли почти не населены. А некоторые наоборот, очень густо населены. Гриды для густонаселенных областей можно делать очень маленького размера, а для малонаселенных областей большего размера.

Проблема лишь в том, что нам нужно очень часто апдейтить это дерево текущим местоположение таксистов, чтобы добавить их в нужный грид.

Это можно упростить, если мы будем апдейтить дерево не раз в 3 секунды, а раз в 15 секунд, например. А текущее местоположение хранить в некой hash таблице, для отслеживания местоположения в режиме реального времени, когда водитель уже принял заказ или во время поездки. 

**Какого размера эта hash таблица?**

1M * (8 bytes (DriverID) + 4 * 8 bytes (old and new longitudes and latitudes)) = 40 MB.

Это достаточно мало и может поместиться на одном сервере.

Но для reliability, scalability можем распределить эти данные между несколькими серверами на основе hash(DriverID).

Назовем сервис, который менеджит эту hash таблицу с мгновенным местоположением таксистов, **Driver Location Service**.
Он может хранить текущее местоположение таксистов в In-memory кэше.

Какой требуемый network bandwith для Driver Location Service?

(8 * 2 + 8) * 500k / 3s ~ 4MB/s = 32 Mbits/s

Это достаточно небольшое значение для современных серверов.

Также добавим персистент слой. Будем персистить данные из Driver Location Service на диск, на случай падения серверов, чтобы можно было восстановиться с диска.

Эти hash таблицы мы будем апдейтить каждые 3 секунды. И нотифицировать всех подписанных клиентов. Например, тех кто осуществляет поиск и уже нашли нужный грид для поиска. Или те, кто уже едет в машине, чтобы видеть текущее местоположение. Такого типа нотификации можно сделать при помощи pub-sub сервиса, которые будет читать данные из Driver Location Service, а также хранить текущие подписки на обновление местоположения. Назовем эту компоненту **Notification Service**.

### Архитектура приложения:



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



**Как будет работать запрос такси (request ride)?**

Пассажир через мобильное приложение запросит поездку. Он отправит свое текущее местоположение одному из серверов Ride Service. Он запросит у Quad Tree Service ближайшие такси, далее Ride Service отсортирует эти такси по какому-то принципу (например, рейтингу) и отправит запросы на поездку к какому-то числу таксистов. Первый, кто зааксептит запрос на поездку, будет заасайнен на поезку. Остальные получат cancel. Если никто не зааксаптит поездку, то Ride Serivice отправит запросы следующим таксистам. Все коммуникации и нотификации будут происходить через Notification Service. Через него они также будут получать обновления местоположения автомобиля.