Публичное System Design Interview на конференции ArchDays 2022 (задача — бронирование отелей)

В конце октября на конференции ArchDays 2022 я проводил публичное собеседование по system design. Это достаточно логично, так как эта конференция посвящена архитектуре программного обеспечения, а мы в рамках собеседования как раз ее и создавали:)

Я уже проводил такой тип интервью на C++ Russia 2022, кроме того я курирую в Tinkoff этот вид собеседований и часто рассказываю про то, как это выглядит у нас — подробнее можно прочитать в предыдущих статьях: в общем про system design в Tinkoff и больше про то, как мы оцениваем прохождение собеседования и как к нему подготовиться.

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

Надо отдельно отметить, что эту задачу я бы решал итеративно и эта пошаговость решения очень важна, так как проектирование сложной системы — это эволюционный процесс:) И его начальной точкой является

Описание задачи

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

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

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

• Система позволяет пользователю посмотреть информацию по отелю, по номеру (поиск номеров out of scope для задачи)
• Система позволяет пользователям забронировать номер онлайн (оплата в момент бронирования)
• Система позволяет пользователям отменить бронирование
• Система реализует работу с overbooking для бронирования номеров (можно забронировать на 10% больше номеров, чем их есть)

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

Решение должно обладать следующими архитектурными характеристиками

• Система должна обладать свойством высокой доступности
• Система должна поддерживать high concurrency, когда много пользователей одновременно бронируют номера
• Система должна обладать приемлемым latency на бронирование номеров — чем меньше, тем лучше, но при любых раскладах мы должны укладываться в несколько секунд при ответе на запрос бронирования

Решение задачи

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

Правильно заданный вопрос — это половина ответа

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

Формализация задачи

В этой задаче мне было бы интересно задать следующие вопросы для уточнения требований (ответы интервьюера я буду отмечать курсивом)

• Надо ли нам учитывать аутентификацию и авторизацию клиентов?
  Нет, она тут достаточно типовая и лучше не тратить на нее время
• Надо ли нам проектировать административную панель для сотрудников отелей для управления информацией об отеле, номерах и так далее
  Нет, эта часть нас в данной задаче не интересует
• Мы в задаче выкинули поиск, поэтому можно предполагать, что стандартный сценарий использования выглядит так: посмотреть отель, посмотреть комнаты в отеле, выбрать интервал дат и посмотреть доступные комнаты в этот интервал, а потом забронировать, правильно?
  В целом да — этот путь пользователя нас и интересует
• А что по оплате? Мы же не хотим хранить сами карточную информацию и попадать на соблюдение PCI DSS
  Да, мы можем считать, что у нас есть внешний платежный, через который мы проводим оплату с карты
• А как выглядит сам процесс оплаты? Пользователь каждый раз оплачивает отдельно или мы списываем с привязанной карты?
  Давай для простоты считать, что карта у пользователя привязана и мы должны просто списать с нее деньги

Отдельно зададим вопросы по нагрузке, которые влияют на то как нам потребуется масштабировать нашу систему:

• Какое количество пользователей у нашего сервиса мы ожидаем?
  Давай пойдем не от количества пользователей, а от размера рынка, который мы хотим захватить, а это вся Россия
• Ок, тогда какой размер российского рынка?
  Если ориентироваться на статистику 2021 года по России , то у нас будет порядка 20к отелей и порядка 1M номеров. Предположим, что у нас 60% заполняемость отелей и средняя длительность проживания 3 дня
• Все классно, но для того, чтобы посчитать количество пользователей, что смотрят информацию по отелям и номерам нам надо знать как будет выглядеть воронка переходов по сайт. У нас есть понимание какая она?
  Отличный вопрос. Давай предположим, что воронка выглядит так
  — просмотр страниц номера 100%
  — просмотр страницы букинга и уточнения деталей бронирования 10%
  — успешный букинг 1%
• Наши пользователи географически распределены?
  Они расположены по всей России, преимущественно в ее европейской части
• Сайты бронирования часто работают за счет красивых картинок и видео. Мы понимаем сколько у нас лимиты на видео и картинки в разрезе отелей и комнат?
  Хороший вопрос. Давай считать, что у нас будут пока только картинки и их будет до 100 на отель и до 20 на типовую комнату.

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

• Количество бронирований в день — 1M * 0.6 /3 = 200k
• Количество транзакций в секунду на бронирования 200k/ 86400 = 2.3 tps
• Количество открытий страниц с бронированием = 2.3 * 10 = 23
• Количество открытий страниц номеров = 2.3 * 100 = 230
• Отдельно стоит отметить, что нагрузка будет сильно неравномерная и у нас могут быть спайки с нагрузкой на порядок большей, чем средняя
• Плюс нам потребуется хранилище для картинок
  — 20k * 100 * 3 Mb (размер картинки) = 2 Tb хранилище для картинок по отелям
  — Плюс пусть в среднем у отеля по 10 разных видов комнат, а значит у нас еще 20k * 10 * 20 * 3 Mb = 4 Tb — это хранилище для картинок по комнатам
  — Плюс легко представить что будет, если мы решим хранить еще и видео

В общем, у нас будет действительно масштабная система. Дальше будет полезно проговорить

Границы системы

Нам надо точно очертить что именно попадет в границы задачи и еще важнее что не попадает. Характерной чертой хорошо выстроенных границ является понимание основных сценариев работы системы и четко формализованного API.

Начнем с публичного API (для внешних пользователей)

— Получить информацию по отелю GET /v1/hotels/{ID}
— Получить информацию по номеру GET /v1/hotels/{ID}/rooms/{RoomID}
— Получить информацию по бронированиям пользователя GET /v1/reservations/
— Получить детальную информацию по конкретному бронированию GET /v1/reservations/{ID}
— Добавить новое бронирование POST /v1/reservations
— Отменить бронирование DELETE /v1/reservations/{ID}

Интересно показать как выглядит payload добавления бронирования

— startDate
— endDate
— hotelID
— roomID
— reservationID

Если бы нам надо было еще думать про непубличное API (для внутренних пользователей нашей админки), то у нас бы появились

— CRUD для сущности отель GET/POST/PUT/DELETE
— CRUD для сущности номер GET/POST/PUT/DELETE
— и так далее

В итоге, у нас получилась следующая схема.

Рис. “Схема с границами системы”

Слева у нас пользователь, который может получать данные по отелям и комнатам в них. Когда он находит то, что его интересует, то он может оформить резерв (методом POST), для которого мы написали базовый payload без погружения в детали. Также пользователь может посмотреть список того, что он уже забронировал в нашей системе и может отменить одну из броней. Справа у нас административный пользователь нашей системы, у которого есть CRUD доступы до сущностей hotel и room. Подробно их можно не расписывать, так как нас про это не просили.

Автоматизируемый процесс

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

Клиент выбирает отели и номера в них. В момент, когда он определился со своим выбором, он решает забронировать себе номер.
Для того, чтобы начать бронирование он должен быть залогинен.
На странице бронирования ему нужно заполнить основные параметры — количество номеров, их тип, даты заезда и выезда.
После того, как он заполняет эти данные, ему показывается стоимость бронирования и он нажимает кнопку забронировать.
Запрос уходит в наш сервис бронирования и дальше начинается самое интересное:

• Нам надо проверить, что выбранные номера можно забронировать на выбранные даты — тут проблема с конкурентностью, так как параллельно другие клиенты могли забронировать эти номер
• Надо посчитать сколько стоит бронирование номеров и сравнить с тем, что пришло в самом запросе — тут надо учесть, что у отелей есть динамическое ценообразование, которое зависит от степени их заполненности на определенную дату
• Представим, что нам удалось забронировать номера удалось, но дальше требуется оплатить — знак, что нам нужна статусная модель брони
• Для простоты давайте считать, что у пользователя есть в нашем сервисе привязанная карта, но платим мы через внешнего провайдера, чтобы самим не попадать на сложный compliance
• Если оплатить заказ получилось, то он переходит в финальное состоянии

Рис. “Workflow + доменная модель”

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

• Публичное API мы закрываем API Gateway, который реализует базовые функции, включая авторизацию
• Дальше у нас есть отдельные сервисы для hotels, rooms, rates, payments, reservations
• Раскрывать подробнее Hotel Management Service для административной части мы смотреть не будем, так как про нее рассказывать не просили

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

Дизайн модели данных

Базовый дизайн модели данных следующий

Hotel — таблица для хранения данных по отелям
— hotel_id # PK
— name
— address
— location
— …

Room — таблица для хранения номеров
— room_id # PK
— room_type_id
— hotel_id
— floor
— number
— name
— is_available
…

RoomType — тип комнаты
— room_type_id
— base_cost

Rate — таблица для хранения динамических рейтов
— hotel_id # Compound PK
— date # Compound PK
— rate # мультипликатор стоимости

Reservation — таблица для хранения информации о бронированиях
— reservation_id # PK
— room_id # reserved room id
— start_date
— end_date
— status — enum (pending, paid, canceled, rejected, refund)
— guest_id # auth user id
— cost

Дизайн системы

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

Теперь нам надо добавить таблицу с комнатами каждого типа, на каждую дату с отметкой заняты они или свободны. Мы назовем это Inventory

Inventory — таблица для хранения информации о бронированиях
— hotel_id # Compound PK
— room_type_id # Compound PK
— date # Compound PK
— total
— reserved

Ну и в табличке Reservation будут изменения, так как мы бронируем не конкретную комнату, а ее тип

Reservation — таблица для хранения информации о бронированиях
— reservation_id # PK
— room_type_id # reserved room type
— start_date
— end_date
— status — enum (pending, paid, canceled, rejected, refund)
— guest_id
— cost

В итоге, получается следующая схема

Рис. “Workflow + доменная модель с overbooking”

Как работаем с данными

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

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

По-факту, если мы разместим таблицы Reservation и Inventory в одной базе, то сможем делать резервирование номеров и менять количество доступных для резервирования в рамках одной транзакции, что гарантирует нам ACID. Но остается вопрос с уровнями изоляции транзакций. Но для начала нам стоит написать как будет выглядеть запрос для получения информации есть ли доступные для бронирования номера

SELECT hotel_id, room_type_id, total, reserved FROM Inventory WHERE
(hotel_id = :hotel_id) AND
(room_type_id = :room_type_id) AND
(date BETWEEN :start_date AND :end_date)

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

По-факту, если все ок, то нам надо сделать два изменения в одной транзакции. Сначала вставить бронь в табличку бронирований

INSERT INTO Reservation (reservation_id, room_type_id, start_date, end_date, status, guest_id, cost) VALUES (:reservation_id, :room_type_id, :start_date, :end_date, 'pending', :guest_id, :cost)

А потом обновить табличку с Inventory

UPDATE Inventory SET reserved = reserved + 1 WHERE
(hotel_id = :hotel_id) AND
(room_type_id = :room_type_id) AND
(date BETWEEN :start_date AND :end_date)

Вроде бы все просто, но … есть нюансы.

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

У нас есть 3 варианта решения этой проблемы:

• пессимистичные блокировки
• оптимистические блокировки
• constraints на уровне базы данных

Первый вариант можно реализовать через логику SELECT * FOR UPDATE;В этом случае кто первый пришел за этими номерами, того и тапки. Другим пользователям остается только ждать. В принципе, это рабочий вариант, но он при усложнении логики может привести к deadlocks и плохо масштабироваться под нагрузкой, особенно для долгих транзакций.

Второй вариант с оптимистичными блокировками может быть реализован на уровне базы данных, например, Postgres, если мы выставим уровень изоляции Repeatable Read Isolation Level
В этом случае у нас выпадет ошибка вида “ERROR: could not serialize access due to concurrent update”, если в параллельном запросе были изменены строки, которые мы тоже хотели бы поменять.

Третий вариант с constraints работает похоже на второй, но там суть в том, чтобы на уровне базы проверять, что total * overbooking_rate >= reserved для всех строк внутри Inventory на момент окончания транзакции.

При нашей нагрузке кажется, что оптимистические блокировки — это наш выбор. Они классно работают пока у нас не слишком высокий contention, то есть мы не налетаем на слишком большое количество retries.

Нагрузка и масштабирование базы данных

Давайте посчитаем размер наших табличек

• Hotels → 20k
• Rooms → 1M
• RoomType → NumberOfHotels * TypesOfRoomPerHotel ~ 20K * 10 → 200K
• Reservation → NumbersOfReservationPerDay * 2 years = 200K * 365 * 2 ~ 150M
• Inventory → NumbersOfHotels * TypesOfRoomPerHotel * 2 years = 20K * 10 * 365 * 2 ~ 150M

В принципе, мы можем для облегчения работы базы

• партиционировать данные по бронирования и inventory по времени — у нас там есть обычно интервал за который мы ищем + у нас есть относительно горячие и холодные данные
• но красивее вариант шардировать по hotel_id, так как у нас этот ключ встречается во всех запросах и отели независимы друг относительно друга

Дополнительные вопросы

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

— Историю с распределенной транзакцией бронирования и списания денег и что будет, если что-то пойдет не так
— или историю с повторными заказами с клиента в случае, если он не получит ответ об успешном бронировании

Но обычно на подробное обсуждение дополнительных вопросов не хватает времени и максимум можно успеть обсудить основную концепцию:)

P.S.

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

1. “Зачем вы задаете такие задачи?”
2. “Действительно ли придется внутри решать похожие задачи?”
3. “В какую команду или в какой продукт меня смотрят?”
4. “Как выглядит процесс работы внутри команд?”

Отвечу тут по пунктам

1. На первый вопрос я подробно отвечал в статье в части “Зачем мы проверяем навыки дизайна систем?” и если сократить, то мы идем в сторону децентрализации принятия архитектурных решений — инженеры в командах должны сами уметь в проектирование систем
2. Ответ на этот вопрос зависит от команды, куда попадет кандидат и сложности их задач, но с учетом ответа из первого пункта кажется, что архитектурные решения придется принимать в любом случае
3. Это интересный вопрос, но на этапе system design interview на него не ответить, так как мы нанимаем в компанию, а не в команду — это значит, что узнать какая именно команда приглашает кандидата на финальное интервью можно будет только после прохождения всех технических секций
4. И этот вопрос сильно зависит от финальной команды, в которую попадет кандидат, но у нас дефолтом являются agile подходы с выраженным продуктовым подходом в управлении как бизнес-продуктами, так и командами разработки

P.P.S

Внимательные читатели заметят, что мы не все изначальные требования выполнили в рамках нашей системы — обычно в реальном мире так и бывает и никто и никогда в рамках часового интервью не успевает закрыть все вопросы. Так что и в этой статье я хотел показать, что “не боги горшки обжигают” и что хорошая система сейчас лучше, чем идеальная когда-то:)

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

Рис.5 “Финальная схема со всеми итерациями”