Задача.
Нужно сделать дизайн сервиса по типу 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).
Далее поместим местоположение всех таксистов в дерево, которое называется Дерево квадрантов (Quad Tree)
Корнем дерева является карта всего мира. У него 4 дочерних вершины. Которые делят всю карту на 4 части. У каждой из такой вершин есть 4 другие дочерние вершины, которые также делят текущую часть карты на 4 части и т.д. Листовыми вершинами будут гриды минимального размера. Этот размер можно выбрать исходя из предположения, что мы хотим искать таксистов в рамках одного или максимум нескольких гридов.
Нам нужно постоянно апдейтить это дерево текущим местоположением таксистов. Поиск ближайших таксистов будем поиском в таком дереве. Высота такого дерева будет ~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.
Архитектура приложения:
Как будет работать запрос такси (request ride)?
Пассажир через мобильное приложение запросит поездку. Он отправит свое текущее местоположение одному из серверов Ride Service. Он запросит у Quad Tree Service ближайшие такси, далее Ride Service отсортирует эти такси по какому-то принципу (например, рейтингу) и отправит запросы на поездку к какому-то числу таксистов. Первый, кто зааксептит запрос на поездку, будет заасайнен на поезку. Остальные получат cancel. Если никто не зааксаптит поездку, то Ride Serivice отправит запросы следующим таксистам. Все коммуникации и нотификации будут происходить через Notification Service. Через него они также будут получать обновления местоположения автомобиля.
Top comments (0)