Проектирование Uber

Постановка задачи

Функциональные требования

Основные требования

1. Пассажиры могут указать начальное и конечное местоположение и получить стоимость поездки.
2. Пассажиры могут заказать поездку.
3. После запроса пассажира система подбирает доступного водителя поблизости.
4. Водители могут принять/отклонить запрос.

За рамками задачи

1. Пассажиры могут оценивать поездку после завершения, а водители могут оценивать пассажиров.
2. Пассажиры могут заранее планировать поездки.
3. Пассажиры могут выбирать категории поездок (например, Эконом, Комфорт).

Нефункциональные требования

Основные требования

1. Система должна обеспечивать высокую скорость подбора водителя (< 1 минуты до принятия запроса или отказа).
2. Система должна обеспечивать сильную согласованность при подборе водителя, чтобы одному водителю не назначались несколько поездок одновременно.
3. Система должна выдерживать высокий трафик, особенно в пиковые периоды или во время популярных событий (100k запросов в секунду из одной локации).
4. Масштабирование - 100 млн DAU, 15 млн поездок в день

За рамками задачи

1. Система должна обеспечивать безопасность и приватность данных пользователей и водителей, соблюдая требования государственных регуляторов.
2. Система должна быть отказоустойчивой, с механизмом аварийного восстановления.
3. Система должна иметь мониторинг, логирование и уведомления для быстрого обнаружения проблем.

Подготовка

Планирование подхода

Прежде чем переходить к проектированию системы, важно на секунду остановиться и продумать стратегию. К счастью, для "продуктовых" задач план обычно простой: последовательно собирать дизайн, проходя по функциональным требованиям одно за другим. Так вы сохраните фокус и не утонете в деталях.

Когда функциональные требования удовлетворены, используйте нефункциональные требования, чтобы определить направления для погружения в детали, где это необходимо.

Проектирование API

Начнем с определения основных сущностей, это поможет спроектировать API. Пока не обязательно знать каждое поле или колонку, но если у вас уже есть представление о том, что там будет - можно это записать.

Для основных функциональных требований понадобятся следующие сущности:

1. Rider (Пассажир): пользователь, который запрашивает поездку. Содержит личные данные, контактную информацию, способы оплаты и т. п.
2. Driver (Водитель): пользователь, зарегистрированный как водитель. Содержит личные данные, информацию о машине (марка, модель, год), предпочтения и статус доступности.
3. Fare (оценка стоимости): оценка стоимости поездки. Содержит точки старта и назначения, цену и ожидаемое время поездки. Эту информацию также можно просто хранить в сущности Ride, но пока мы оставим ее отдельно (здесь нет правильного или неправильного ответа).
4. Ride (Поездка): запись о поездке от момента запроса стоимости до завершения. Содержит информацию о пассажире и водителе, машине, состоянии поездки, маршруте, конечной стоимости, а также временные метки посадки и высадки.
5. Location (Местоположение): актуальная позиция водителей с координатами и временем обновления. Эта сущность является ключевой для подбора водителя и отслеживания поездки.

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

API для получения оценки стоимости достаточно простой. Определим POST эндпоинт, который принимает текущую локацию и пункт назначения, и возвращает объект Fare с оценкой цены и времени поездки. Мы используем POST, потому что создаем новую запись о поездке в базе данных.

POST /fares -> Fare
Body: {
  pickupLocation,
  destinationLocation
}

Эндпоинт заказа поездки: после того как пользователь увидел оценку, он подтверждает поездку. Этот эндпоинт инициирует процесс подбора водителя и создает новую запись Ride.

POST /rides -> Ride
Body: {
  fareId
}

На этом этапе мы сопоставляем пассажира с доступным водителем поблизости. Этот процесс происходит на стороне сервера, поэтому отдельный эндпоинт не нужен.

Эндпоинт обновления местоположения водителя: чтобы подобрать водителя нужно знать, где он находится в данный момент. Этот эндпоинт вызывается клиентом водителя регулярно, чтобы держать его местоположение актуальным, обновляя базу данных.

POST /drivers/location -> Success/Error
Body: {
  lat, long
}

// заметим, что driverId берется из сессии или auth-токена и не передается
// в теле или параметрах пути запроса

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

PATCH /rides/:rideId -> Ride
Body: {
  accept/reject
}

Объект Ride должен содержать информацию о точках посадки и назначения, чтобы клиент водителя мог отобразить ее в интерфейсе.

Высокоуровневый дизайн

1. Пассажиры могут указать начальное и конечное местоположение и получить стоимость поездки

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

Соберем минимальный набор компонентов для расчета стоимости, добавив первый сервис - сервис поездок:

Основные компоненты для оценки стоимости:

• Клиент пассажира: мобильное приложение на смартфоне пассажира, которое взаимодействует с бэкендом.
• API-шлюз: точка входа для запросов от клиентов, отвечает за маршрутизацию, аутентификацию, ограничение запросов и т.д.
• Сервис поездок: управляет состоянием поездки, начиная с расчета стоимости. Он взаимодействует со сторонними картографическими API для определения расстояния и времени в пути между точками и применяет модель ценообразования компании для расчета стоимости проезда. Для целей данного интервью мы абстрагируемся от деталей этого алгоритма.
• Сторонний сервис Maps API: сторонний картографический API сервис (например, Google Maps) для расчета расстояния и времени в пути.
• База данных: сохраняет объекты Fare.

Рассмотрим как эти компоненты взаимодействуют когда пассажир запрашивает стоимость поездки:

1. Пользователь вводит начальное и конечное местоположение и отправляет POST запрос на /fares.
2. API-шлюз принимает запрос, проверяет аутентификацию и ограничения, и маршрутизирует его в сервис поездок.
3. Сервис поездок запрашивает картографический API для получения расстояния и времени и вычисляет стоимость поездки.
4. Сервис поездок сохраняет объект Fare в базе данных.
5. Fare возвращается через API-шлюз, и пользователь решает, делать ли заказ.

2. Пассажиры могут заказать поездку

После получения стоимости и времени поездки пользователь заказывает поездку. Это действие просто расширяет существующий дизайн - мы добавляем таблицу rides.

Когда заказ на поездку приходит мы обрабатываем его следующим образом:

1. Пользователь заказывает поездку, отправляя POST запрос с fareId.
2. API-шлюз после проверок отправляет запрос в сервис поездок.
3. Сервис поездок создает запись Ride, ссылаясь на оценку стоимости Fare, и устанавливает для поездки статус requested.
4. Затем запускается процесс подбора водителя (см. ниже).

3. После запроса пассажира система подбирает доступного водителя поблизости

Для реализации механизма подбора водителя в наш дизайн необходимо добавить несколько новых компонентов:

• Клиент водителя: принимает запросы на поездки и отправляет обновления локации в сервис локаций.
• Сервис локаций: принимает обновления локаций, сохраняет их в базу данных.
• Сервис подбора водителя: обрабатывает запросы на новые поездки и выбирает оптимального водителя (по близости, рейтингу и другим факторам).

Водители постоянно (например, раз в 5 секунд) отправляют свое текущее местоположение в сервис локаций, и мы обновляем базу данных с указанием их последнего местоположения по широте и долготе. Сервис подбора водителей использует эти данные когда приходит запрос на новую поездку для поиска оптимального соответствия.

4. Водители могут принять/отклонить запрос

Как только водитель будет сопоставлен с пассажиром, он сможет принять запрос на поездку. Добавим в дизайн новый компонент:

• Сервис нотификаций: Отвечает за отправку уведомлений в режиме реального времени водителям, когда им подобран новый запрос на поездку. Уведомления отправляются через APN (Apple Push Notification) и FCM (Firebase Cloud Messaging) для устройств iOS и Android соответственно.

Последовательность событий при этом следующая:

1. Сервис подбора водителя формирует список подходящих водителей и отправляет уведомление первому в списке через APN/FCM.
2. Водитель открывает приложение и принимает запрос, отправляя PATCH запрос с rideId. Если водитель отклоняет запрос, сервис уведомляет следующего.
3. API Gateway маршрутизирует запрос в сервис поездок.
4. Сервис поездок обновляет статус поездки на accepted, устанавливает для поездки driverId и возвращает водителю координаты точки посадки.
5. Водитель использует GPS своего клиента, чтобы построить маршрут до точки посадки.

Потенциальные погружения в детали

Когда основные функциональные требования закрыты, мы можем перейти к нефункциональным требованиям, углубляя наш дизайн там, где это необходимо.

1. Как обрабатывать частые обновления локаций водителей и эффективный поиск по близости?

Управлять потоком обновлений локаций и выполнять быстрые запросы на поиск по локации сложно, и текущий high-level дизайн с этим не справляется. Есть две основные проблемы:

• Высокая частота записей: если у нас около 5 млн водителей и они отправляют локации каждые 5 секунд, это ~1 млн обновлений в секунду. Независимо от того, выберем ли мы что-то вроде DynamoDB или PostgreSQL (оба являются отличным выбором для остальной части системы), они либо не выдержат такую нагрузку, либо их придется масштабировать настолько, что они станут слишком дорогими.
• Эффективность запросов: без оптимизаций запросы по координатам (proximity search) требуют полного сканирования таблицы и вычисления расстояния до каждого водителя. Даже с B‑tree индексами это плохо работает для многомерных данных вроде координат.

Что можно сделать чтобы разобраться с этими проблемами?

2. Как снизить перегрузку из‑за частых обновлений локаций без потери точности?

Частые обновления локаций перегружают сеть и серверы, что может замедлять работу системы и ухудшать пользовательский опыт. Большинство кандидатов предлагают обновлять локацию водителя каждые 5 секунд или около того. Можем ли мы разумно уменьшить количество обновлений, сохраняя при этом точность?

3. Как предотвратить назначение нескольких поездок одному водителю?

Мы определили сильную согласованность при подборе водителя как ключевое нефункциональное требование. Это означает что каждый заказ посылается на рассмотрение только одному водителю, И один водитель в каждый момент времени имеет только один заказ на рассмотрении. У водителя есть 10-15 секунд на принятие/отклонение заказа, после чего система переходит к следующему водителю. Если вы рассматривали задачу проектирования Ticketmaster, это очень похоже, поскольку мы гарантируем что билет продается только один раз, и он зарезервирован на определенное время при оформлении заказа.

4. Как гарантировать, что запросы поездок не теряются в пиковые периоды?

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

5. Что делать, если водитель не отвечает вовремя?

Наша система прекрасно работает, когда водители либо принимают, либо отклоняют заявку на поездку. Но если водитель сделал перерыв и не реагирует на запросы, мы должны гарантировать, что запрос на поездку будет продолжать обрабатываться, перенаправляя запрос следующему водителю.

6. Как дальше масштабировать систему, снижая задержку и повышая пропускную способность?

Итоговая архитектура нашей системы может выглядеть примерно так:

Что ожидается на каждом уровне?

Хорошо, мы обсудили много всего. Возникает резонный вопрос: "сколько из этого реально ожидается от меня на интервью?" Разберем по уровням.

Middle

Ширина vs глубина: от Middle кандидата чаще ожидается ширина кругозора и знаний (примерно 80% vs 20%). Вы должны собрать понятный высокоуровневый дизайн, закрывающий все функциональные требования, но многие компоненты могут оставаться абстракциями, которые вы проработали и обсудили с интервьюером на поверхностном уровне.

Проверка базовых знаний: интервьюер будет прощупывать базу, чтобы удостовериться, что вы понимаете, что делает каждый компонент. Например, добавив API Gateway, ожидайте вопрос "что он делает" и "как работает".

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

Задача Uber: от Middle кандидата ожидается четко определенный API и модель данных, а также высокоуровневый дизайн покрывающий функциональные требования. Кандидат должен указать на необходимость использования гео-пространственного индекса для ускорения поиска по местоположению, а также реализовать, по крайней мере, "хорошее решение" проблемы блокировки запроса на поездку.

Senior

Глубина экспертизы: от Senior кандидата ожидания смещаются к глубине - примерно 60% ширины и 40% глубины. Нужно уметь уходить в детали там, где у вас есть практический опыт.

Продвинутый дизайн системы: вы должны быть знакомы с современными принципами проектирования систем: различными технологиями, вариантами их использования и тем, как они сочетаются друг с другом.

Аргументация решений: вы должны уметь ясно объяснять плюсы/минусы архитектурных решений и их влияние на масштабирование, производительность и поддерживаемость, проговаривая компромиссы.

Проактивность и решение проблем: вы должны продемонстрировать сильные навыки решения проблем и проактивный подход. Это подразумевает обнаружение потенциальных проблем в ваших проектах и предложение улучшений. Вам необходимо уметь выявлять и устранять узкие места, оптимизировать производительность и обеспечивать надежность системы.

Задача Uber: от Senior кандидата ожидается, что вы быстро пройдете высокоуровневый дизайн и потратите время на детальное обсуждение как минимум двух из проблем: ускорение proximity-поиска, проблему блокировки запроса на поездку или проблему пиковых нагрузок. Вы также должны быть в состоянии обсудить плюсы и минусы различных вариантов архитектуры, особенно то, как они влияют на масштабируемость, производительность и удобство обслуживания.

Staff+

Акцент на глубину: от Staff+ кандидата ожидается глубокий разбор нюансов - примерно 40% ширины и 60% глубины. Важна демонстрация того, что, даже если вы не решали именно эту задачу раньше, вы решали достаточно похожих задач в реальном мире, чтобы уверенно спроектировать решение, опираясь на опыт.

Интервьюер понимает, что вы знаете основы (REST, нормализация данных и т. п.), так что вы можете быстро пройти это на high-level дизайне и перейти к самому интересному.

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

Практическое применение технологий: важно уметь говорить о применяемых технологиях не только в теории, но и как это делается на практике - конфигурации, эксплуатационные нюансы, типичные проблемы.

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

Задача Uber: от Staff+ кандидата ожидается высокое качество решений по сложным проблемам, которые обсуждались выше. Хорошие кандидаты глубоко погружаются как минимум в 3+ ключевых области, демонстрируя не только профессионализм, но и инновационное мышление и способности находить оптимальные решения. Хорошим показателем вашей экспертизы является то, что интервьюер завершает дискуссию, обретя новое понимание или точку зрения.