Как Uber эффективно обрабатывает свои миллионы заказов такси и еды. Часть 1

Подробный разбор фулфилмент-архитектуры компании Uber.

Как описано в [1], фулфилмент-сервис должен “получить намерение клиента и воплотить его путем подбора правильного набора провайдеров (исполнителей)”. Например, одно из возможных намерений клиента — это поездка из одной точки в другую, а провайдером в этом случае будет являться свободный водитель такси, находящийся как можно ближе к клиенту. Конечная цель фулфилмент-сервиса — это эффективный поиск свободных водителей рядом с клиентом.

В этой серии из двух статей мы подробно рассмотрим архитектуру фулфилмент-сервиса компании Uber, и каким образом происходит ее масштабирование по мере увеличения числа пользователей. В этой статье мы рассмотрим моделирование данных и архитектуру фулфилмент-сервиса предыдущего поколения, а в следующей мы поговорим о том, почему с увеличением числа пользователей компания Uber перенесла фулфилмент-сервис в Google Cloud Spanner и каким образом она осуществила этот переход.

Вторую часть статьи можно найти по ссылке

Обзор архитектуры высокого уровня

Архитектура высокого уровня, источник: [1]

На схеме выше изображена архитектура высокого уровня фулфилмент-сервиса предыдущего поколения компании Uber. В его основе лежат две модели данных: сущность доставки (Supply) и сущность поездки (Trip). Сущность поездки представляет единицу работы, а именно поездку из одной точки в другую, в то время как сущность доставки представляет человека, который может выполнить эту работу.

Сущность поездки

Сущность поездки моделируется как список путевых точек, где путевая точка (Waypoint) содержит информацию о местоположении (Location) и ряде задач (Task), которые мы можем выполнить в этой локации. Ниже приведен пример определения сущности поездки.

Дисклеймер: код в этой статье — это то, как я бы реализовал фулфилмент-сервисы Uber на основе информации из [1] и [2]. Я не работаю в Uber и не знаю, каким образом они реализованы на самом деле.

enum Task {   PICK_UP   DROP_OFF  } class Location {   long longitude;   long latitude; } class WayPoint {   Location location;   Task task; } class Trip {   List<WayPoint> points; } // Простая поездка может содержать две путевые точки, одну с задачей PICK_UP  // и одну с задачей DROP_OFF.

Сущность доставки

Сущность доставки представляет собой ряд задач, которые необходимо выполнить водителю. Например, если водитель везет клиента в пункт назначения и принял запрос от нового клиента, сущность доставки для водителя будет иметь две путевые точки: одну для текущего клиента — DROP_OFF и одну для нового клиента — PICK_UP.

Сервисы такси и доставки

Сущности поездки и доставки управляются сервисам такси и доставки соответственно. Эти два сервиса представляют собой независимые микросервисы, синхронизация данных которых происходит на уровне хранилища. Дополнительную информацию об этом можно найти в разделе о инфраструктуре ниже.

Геопространственный индекс

Геопространственный индекс хранит информацию о местоположении водителей и клиентов. Он используется для сопоставления местоположения клиента с местоположением водителей, то есть для поиска ближайших доступных водителей для конкретного клиента. Геопространственный индекс лежит в основе процесса сопоставления (matching process), поэтому его производительность крайне важна.

В компании Uber используется геолокационная кодировка под названием H3 [2]. Как показано на рисунке ниже, вся карта разделена на шестиугольники, так называемые ячейки. Каждой шестиугольной ячейке присваивается уникальный идентификатор в виде строки.

H3 делит карту на шестиугольные ячейки, источник: [2]

Библиотека H3 предоставляет функции для эффективного преобразования данных местоположения (долготы и широты) в идентификатор ячейки H3 и преобразования идентификатора ячейки H3 обратно в местоположение. [3]. Ниже приведен пример использования библиотеки H3.

function example() {   const lat = 37.7955;   const lng = -122.3937;   const res = 10;   return h3.geoToH3(lat, lng, res); } // output: "8a283082a677fff"

С геопространственным индексом нам не нужно никакое специальное обслуживание хранения или извлечения данных из базы данных. Следовательно, любая база данных может удовлетворить наши функциональные требования (но не обязательно требования к производительности!). Если бы мы использовали реляционную базу данных, мы могли бы определить следующую схему для хранения информации о водителе. В поле “location” хранится идентификатор ячейки h3.

create table driver (   driver_id INT NOT NULL,   given_name VARCHAR(100),   surname VARCHAR(100),   location VARCHAR(30),   available BOOLEAN,   ... ); create index driver_by_location_and_availability on table driver (location, available);

Если местоположение водителя обновляется, то реализация этого в сервисе сущности доставки может быть не сложнее оператора обновления базы данных, меняющего местоположение.

Сопоставление

Сопоставление (matching) — это процесс поиска доступных водителей для клиента. При использовании геопространственных кодировок процесс сопоставления предполагает выполнение двух шагов.

Шаг 1: найдите интересующие нас ячейки

На рисунке справа показаны пользователь и интересующая нас область (район).

Предположим, клиент находится на Рынковой улице, и мы хотим найти всех свободных водителей в этой области (выделенной красным кругом). Наши первые действия — это вызов функции h3.geoToH3() для получения идентификатора ячейки местоположения клиента. Затем мы вызываем функцию h3.kRing(), чтобы найти идентификаторы 6-ти шестиугольников, примыкающих к ячейке клиента. (Определение функции kRing() показано ниже.) Всего у нас будет 7 строк, покрывающих область внутри красного круга, и мы сохраним их в массиве под названием cells_of_interest.

Определение функции kRing:

List<String> kRing(String origin, int k);

Шаг 2: поиск в базе данных

Мы могли бы просто использовать запрос к базе данных, чтобы найти подходящих водителей.

SELECT driver_id FROM driver USING INDEX (driver_by_location_and_availability) WHERE available AND location IN cells_of_interest;

Инфраструктура

Инфраструктура Uber, источник: [1]

На изображении выше показана инфраструктура фулфилмент-сервиса. Она состоит из трех основных компонентов: сервиса для запуска логики приложения, базы данных для хранения данных и диспетчера транзакций для обеспечения согласованности.

Для запуска своих независимых микросервисов компания Uber использует Pod [6]. Согласованное хеширование используется для разделения работы по разным инстансам сервиса. Согласованное хеширование также улучшает коэффициент попадания в in-memory кэш. Помимо in-memory кеша, еще один уровень кеширования предоставляется Redis.

Данные хранятся в Cassandra [7] — NoSQL базе данных. Учитывая объем данных компании Uber и частоту их обновления, NoSQL больше соответствует их требованиям к производительности. А также сервис ведет реплей-логи в Kafka. Реплей-логи записывают, какие изменения были внесены в базу данных. Например, в одной записи можно отметить, что местоположение водителя меняется с “axxx” на “ayyy”. Если запись в базу данных завершается неудачно, мы можем просто повторно запустить команды, хранящиеся в Kafka, чтобы привести базу данных в согласованное состояние.

Для реализации транзакций поверх NoSQL базы данных работают два механизма. Последовательная очередь в каждом инстансе сервиса используется для упорядочивания входящих запросов, а Saga [5] используется для реализации распределенных транзакций. Распределенные транзакции необходимы, когда нам нужно обновить несколько записей атомарно. Например, когда водитель принимает заказ, нам необходимо обновить сущность водителя и сущность поездки у клиента в рамках одной транзакции. В противном случае база данных может остаться в несогласованном состоянии, на стороне клиента запрос принимается водителем, а на стороне водителя запрос не принимается.