1. Введение
Когда дело доходит до передвижения по городу, многие люди выбирают приложения для совместного использования, такие как Uber или Lyft. Действительно, такие приложения очень упрощают поездки на короткие расстояния, предлагая конкурентоспособные цены, достаточно короткое время ожидания и высокую доступность. С технической точки зрения такие системы очень интересны, потому что поиск ближайшего соседа затруднен. В этой статье я хочу поделиться своим дизайном крупномасштабных приложений для совместного использования, таких как Uber/Lyft.
Требования
Современные приложения для обмена поездками предлагают сложные функции, такие как совместное использование автомобилей, обмен поездками, чат в реальном времени в дополнение к подбору поездок. В этой статье я хочу сохранить краткость обсуждения и сосредоточиться только на основной функции — бронировании поездки. Ниже приведены функциональные требования нашей системы:
- Пользователи могут заказать поездку и должны быть сопоставлены с водителем в непосредственной близости.
- Пользователи могут видеть всех ближайших водителей (но не выбирая, какой из них)
- Водители могут отвечать/отклонять запросы от находящихся поблизости гонщиков.
- Когда поездка создается, обе стороны видят местоположение друг друга в реальном времени.
Излишне говорить, что система должна быть масштабируемой и высокодоступной.
Оценка трафика
Прежде чем говорить о трафике, давайте рассмотрим уникальную особенность Uber — его использование данных является локальным. В отличие от таких приложений, как Slack или Instagram, передача данных между регионами требуется редко. Если вы физически находитесь в Нью-Йорке, вы не можете заказать поездку в Лондоне. Следовательно, данные о местоположении и поездках не реплицируются в разных регионах (разумеется, менее часто используемые данные, такие как профили, реплицируются глобально). В этом смысле обсуждение глобального трафика не так важно, как регионального трафика.
Количество запросов на поездку, поступающих в нашу систему, зависит от популярности приложения. Здесь мы предполагаем значительный региональный трафик для обобщенного решения:
- Сгруппируйте города по близости в регионы. Нам нужно, может быть, дюжина регионов, чтобы охватить всю территорию США.
- Мы ожидаем около 100 тысяч активных водителей в одном регионе.
- Мы ожидаем ~1 млн активных пользователей в одном регионе.
- Общее количество пользователей по всему миру составляет 10 миллионов.
Предположим, что и водители, и пассажиры передают свое местоположение примерно через 5 секунд, причем каждое сообщение состоит из долготы, широты и дополнительных метаданных. Кроме того, водители регулярно проверяют ближайших водителей (~ 5 с) и иногда запрашивают поездку. Количество запросов в секунду и пропускная способность, которые мы можем ожидать, составляют:
- Мы ожидаем около 200 000 обновлений/записей местоположения в секунду.
- Мы ожидаем около 200 000 запросов в секунду, удвойте это значение для обработки пикового трафика.
- Каждое сообщение о местоположении состоит из идентификатора (8 байт), долготы и широты (16 байт) и другой информации (64 байта). Общая пропускная способность загрузки составляет всего 88 МБ/с.
2. Дизайн высокого уровня
Дизайн базы данных
Схема доступа нашего приложения определяет используемую схему. Давайте исследуем запросы, которые попали в базу данных:
Операции чтения
- Учитывая идентификатор пользователя, получить его профиль
- Учитывая идентификатор пользователя, получить все поездки, совершенные пользователем
- Учитывая долготу и широту, запрашивать все водители поблизости
Операции записи
- Учитывая идентификатор пользователя, обновить его местоположение
- Учитывая идентификатор поездки, водитель может либо принять, либо отклонить запрос.
Схема базы данных
Учитывая шаблоны доступа, сегментированный SQL является хорошим выбором, поскольку не выполняются сложные запросы отношений. Обратите внимание, что базы данных NoSQL, такие как Cassandra, также могут использоваться здесь, если строгая согласованность не является жестким требованием.
Таблица профиля водителя
Таблица профиля райдера
Таблица сведений о поездке
В дополнение к этим таблицам базы данных нам нужно еще одно высокопроизводительное хранилище для хранения часто обновляемых данных о местоположении. Поскольку данные о реальном местоположении по своей природе эфемерны, сохранять их на дисках не имеет смысла. Хорошей альтернативой будет использование кэша в памяти, такого как Redis или Memcache.
Схема кэша
Кэш правды о местоположении
Этот кеш является источником правды, когда речь идет о местоположении пользователя. Телефонные приложения отправляют регулярные обновления для обеспечения точности. Если пользователь отключается, его запись истекает через 30 секунд.
Кэш приближения драйвера
Кэш близости имеет решающее значение для поиска ближайших водителей. Учитывая местоположение, мы можем использовать G eoHash для вычисления его ключа местоположения и получения всех водителей в сетке. Подробнее об этом я расскажу в разделе Подробности.
Архитектура
С более четким пониманием того, какие данные хранить, пришло время для сервис-ориентированных проектов!
- Служба уведомлений: всякий раз, когда серверной части необходимо отправить информацию клиентам, для доставки сообщений используется служба уведомлений.
- Служба управления поездками. Когда начинается поездка, эта служба необходима для отслеживания местонахождения всех сторон, а также для планирования маршрутов.
- Служба сопоставления поездок. Эта служба обрабатывает запросы на поездки. Он находит ближайших водителей и сватов на основе ответов водителей (либо принимает, либо отклоняет)
- Служба определения местоположения: все пользователи должны регулярно обновлять информацию о своем местоположении с помощью этой службы.
Рабочий процесс
- Боб отправляет запрос на поездку в службу Ride Matching и надеется соединиться с водителем.
- Служба Rider Matching связывается со службой определения местоположения и находит всех доступных водителей в том же регионе.
- Затем служба Rider Matching выполняет ранжирование/фильтрацию и отправляет запрос на поездку выбранным водителям через службу уведомлений.
- Водители могут принять/отклонить запрос. После получения Ride Matching Service отправит информацию о поездке в службу управления поездками.
- Служба управления поездками отслеживает ход поездки и сообщает о местонахождении водителя и пассажира всем сторонам, участвующим в поездке.
3. Детали
Проект архитектуры высокого уровня относительно прост. Однако, если внимательно присмотреться, несколько морщин все же есть. Например, я проигнорировал такие функции, как стоимость поездки, совместное использование автомобилей и т. д. В этой статье я хочу сосредоточиться на проблемах, связанных с местоположением, поскольку они являются основой Uber/Lyft.
3.1 Как эффективно искать ближайшие водители?
Поиск ближайшего соседа — сложная задача, а масштаб нашей системы еще больше усложняет эффективный поиск. Вместо того, чтобы вычислять расстояние между гонщиком и каждым водителем в базе данных, мы можем использовать метод под названием GeoHash, чтобы преобразовать местоположение пользователя в уникальный ключ, соответствующий одной ячейке на рисунке 7, и ограничить поиск только несколькими соседними ячейками.
Рисунок 7 демонстрирует ключевое свойство GeoHash — однозначное соответствие между ключами и ячейками местоположения. Поэтому мы можем использовать следующую эвристику для быстрого поиска драйверов:
- Учитывая местоположение пользователя, вычислите его GeoHash по долготе и широте.
- Имея доступный ключ GeoHash, легко вычислить ключи для 8 соседних ячеек. (см. этот пост)
- Запросите службу определения местоположения со всеми 9 ключами; получить драйверы в этих ячейках.
Точность GeoHash определяется длиной ключа. Чем длиннее ключ, тем меньше будет каждая ячейка.
Какой размер ключа лучше использовать? На практике размер ключа определяется итеративно в зависимости от количества драйверов и райдеров. На мой взгляд, хорошей отправной точкой будет размер 6, так как он охватывает несколько городских кварталов.
Существуют физические ограничения на максимальное количество водителей и гонщиков, которые могут поместиться в одной из этих ячеек. Возвращаясь к рисунку 5, каждая ячейка будет записью в кэше Driver Proximity в Redis.
Вам может быть интересно, сможет ли Redis справиться с таким уровнем трафика. Если в регионе есть 1 млн активных райдеров, количество запросов, поступающих в кластер, составляет около 200 тыс. операций записи/с (каждый пользователь обновляет свое местоположение ~5 с) и 2 млн операций чтения/с (каждый пользователь считывает 9 ключей Redis ~5 с).
Даже с одним единственным узлом AWS c5.18xlarge с 32 потоками система может обрабатывать трафик. На практике мы можем распределить рабочую нагрузку на десятки компьютеров и достичь мощности RPS на уровне ~100 млн.
Как насчет ограничений памяти? Если мы используем геохэш размера 6, в кеше потенциально может быть 32⁶ ~=10 миллиардов ключей, что безумие. Однако мы никогда не достигнем этого количества ключей, если пустые ключи будут удалены (рис. 5). На практике количество записей кэша ограничено количеством автомобилей, потому что каждый автомобиль может находиться только в одной ячейке! Следовательно, память не является узким местом.
3.2 Обновление местоположения
Надеюсь, я убедил вас в целесообразности размещения службы определения местоположения в Redis. Теперь давайте посмотрим, как пользователи обновляют свое местоположение.
В кэше есть две таблицы — таблица истинности местоположения и таблица близости драйверов. Использование таблицы истинности местоположения просто. Мобильное приложение пользователя отправляет свое местоположение, а также идентификатор пользователя в службу определения местоположения каждые 5 секунд. Всякий раз, когда требуется точное местоположение пользователя, система может запросить эту таблицу по идентификатору пользователя.
Ближайший стол более интересен по своей природе. Водители передвигаются на своих машинах, а это значит, что они часто пересекают одну клетку в другую. Когда серверная часть получает обновления от драйвера, она не знает, какими ячейками они были в прошлом. Следовательно, трудно удалить драйверы из их старых ячеек. Смысл очевиден; один и тот же драйвер может появиться в нескольких ячейках из-за устаревших данных.
Чтобы решить эту проблему, мы могли бы ввести метку времени для каждой записи. С временными метками легко отфильтровать устаревшие данные о местоположении. На практике структура данных отсортированного набора в Redis является эффективным способом достижения такой функции.
В дополнение к местонахождению водителя мы можем хранить в кеше такую информацию, как тип транспортного средства, статус поездки (свободен, в пути). Благодаря дополнительной информации можно быстро сопоставить поездку, поскольку пропускается поездка туда и обратно в базу данных (запрос информации о транспортном средстве и статусе поездки).
3.3 Запись поездки
Еще одной важной функцией нашей системы является запись поездки. Для завершенной поездки мы хотим сохранить маршрут, пройденный водителем, и сделать его доступным для просмотра клиенту.
Есть много способов реализовать эту функцию; самым простым способом было бы полагаться на то, что водители сообщат о своем местонахождении, а также о статусе поездки. Служба определения местоположения будет пакетно записывать все обновления местоположения со статусом в поездке в базу данных для постоянного хранения.
Полагаться на клиентское приложение рискованно. Что делать, если клиентское приложение потеряет все локальные данные во время поездки? Он не будет знать статус драйвера до перезагрузки. Чтобы восстановиться после сбоя, клиентское приложение должно проверить наличие незавершенных поездок в базе данных и подтвердить их статус у водителя.
4. Резюме
В этой статье мы разработали основы приложений для совместного использования, таких как Uber/Lyft. В частности, мы подробно изучили, как может быть реализован поиск близости. Имейте в виду, что идеального ответа на собеседовании не бывает. Все решения имеют недостатки; наша работа состоит в том, чтобы придумать дизайн, который работает достаточно хорошо при заданных предположениях и ограничениях.
