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

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

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

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

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

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

На схеме выше изображена архитектура высокого уровня фулфилмент-сервиса предыдущего поколения компании 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 предоставляет функции для эффективного преобразования данных местоположения (долготы и широты) в идентификатор ячейки 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 использует Pod [6]. Согласованное хеширование используется для разделения работы по разным инстансам сервиса. Согласованное хеширование также улучшает коэффициент попадания в in-memory кэш. Помимо in-memory кеша, еще один уровень кеширования предоставляется Redis.

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

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

Рекомендовано к прочтению

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

Перевожд статьи подготовлен в преддверии старта курса "Microservice Architecture".

• Узнать подробнее о курсе