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

Технологические компании наподобие Ticketmaster, BookMyShow, Airbnb, Delta Airlines и так далее сделали бронирование делом одного клика, позволившим покупать билеты из дома.

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

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

Поэтому важно создать надёжное решение классической задачи — двойного букинга.

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

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

Как случается двойной букинг?

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

Архитектура систем бронирования

Возьмём для примера простую систему бронирования, состоящую из следующих компонентов:

• Клиент — мобильное приложение или веб-страница, бронирующая место.

• Сервис букинга — бэкенд-сервис, раскрывающий API для бронирования мест.

• База данных — реляционная база данных, управляющая состоянием места.

Бронирование билета в сервисе букинга происходит в два этапа:

1. Проверка наличия — выполняется запрос select, чтобы проверить, свободно ли место. (S1)

2. Обновление состояния — если проверка наличия выполнена успешно, то выполняется запрос update, чтобы пометить место, как забронированное. (S2)

BEGIN TRANSACTION;

# S1 
SELECT * FROM seats 
WHERE seat_id = 'A1' AND event_id = 'E123' AND status = 'AVAILABLE'

-- Если строка возвращена, обновляем её

# S2
UPDATE seats 
SET status = 'RESERVED', user_id = 'U456', reserved_at = NOW()
WHERE seat_id = 'A1' AND event_id = 'E123';
COMMIT;

SQL-запросы S1 и S2

И S1, и S2 выполняются в транзакции базы данных. В схеме ниже показан процесс с моделью данных и SQL-запросами.

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

Объяснение двойного букинга

Пусть Алиса и Боб — два пользователя, отправивших запрос в момент t=0 с. Вот, как сервис букинга будет конкурентно обрабатывать два запроса:

1. T=10 мс — S1 Алисы успешно выполнится и найдёт свободное место.

2. T=15 мс — Аналогично, S1 Боба тоже найдёт свободное место.

3. T=20 мс — S2 Алисы обновит состояние билета и привяжет его к Алисе.

4. T=25 мс — S2 Боба перепишет билет Алисы на него.

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

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

Если вы проходили многопоточность в рамках курса по Computer Science, то приведённый выше пример напомнит вам классический случай состояния гонки.

Пища для размышлений: как вы думаете, возникла бы та же самая проблема, если бы сначала выполнились S1 и S2 Алисы, а затем — S1 и S2 Боба?

Именно поэтому проблема двойного букинга возникает вследствие:

• Наличия общего ресурса — два или более сервисов/потоков конкурируют за один общий ресурс (в нашем случае билет), что приводит к состоянию гонки.

• Неатомарных обновлений — весь процесс разбит на две операции (Select и Update), не гарантирующие атомарности.

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

Пессимистическая блокировка

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

Блокировка работает со структурами данных в памяти, но сработает ли она с постоянными хранилищами? Да.

В таких базах данных, как PostgreSQL, MySQL, SQL Server и так далее есть конструкции для получения блокировки записи базы данных. Блокировка гарантирует, что изменять запись может только одна транзакция. Блокировка снимается, когда транзакция завершается, после чего блокировку могут получать другие транзакции.

Такой подход называется пессимистической блокировкой (pessimistic locking), он часто используется для решения проблемы двойного букинга. Давайте применим эту концепцию и поймём, как она работает в нашем сценарии использования.

Модифицируем запрос S1, добавив к нему FOR UPDATE, чтобы явным образом получить блокировку билета. Вот изменённая версия S1 и S2 в транзакции.

BEGIN TRANSACTION;

# S1 
SELECT * FROM seats 
WHERE seat_id = 'A1' AND event_id = 'E123' AND status = 'AVAILABLE'
FOR UPDATE

-- Если строка получена, обновляем её

# S2
UPDATE seats 
SET status = 'RESERVED', user_id = 'U456', reserved_at = NOW()
WHERE seat_id = 'A1' AND event_id = 'E123';
COMMIT;

Получение блокировки строки базы данных

Давайте пройдёмся по примеру с Алисой и Бобом, чтобы понять, как описанный выше подход решает проблему двойного букинга. Теперь сервис букинга будет обрабатывать запрос следующим образом:

1. T=10 мс — S1 Алисы выполнится и заблокирует строку базы данных.

2. T=15 мс — S1 Боба увидит, что место заблокировано, и будет ждать его.

3. T=20 мс — S1 Алисы успешно завершится и найдёт свободное место.

На схеме ниже показана последовательность событий.

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

После блокировки места S2 Алисы назначит билет Алисе, обновит состояние и снимет блокировку. Дальше S1 Боба продолжит выполнение, но обнаружит, что билет забронирован.

Такой подход предотвращает двойной букинг и гарантирует согласованность. Его преимущества:

• Простота — его легко понять и реализовать.

• Согласованность — устраняет состояние гонки.

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

Пища для размышлений: что будет, если S1 выполнится, но произойдёт разрыв соединения с базой данных? Блокировка сохранится или будет снята?

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

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

• Высокой частоты обработки — блокировка становится узким местом, замедляя выполнение и снижая отзывчивость.

• Риска взаимной блокировки — чем больше ресурсов, за которые идёт конкуренция, тем выше вероятность взаимной блокировки.

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

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

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

Оптимистическая блокировка

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

1. Чтение из базы данных — считывает запись базы данных вместе с её версией.

2. Обновление базы данных — добавляет в запрос update оператор where, чтобы убедиться, что перед обновлением версия не меняется.

3. Инкремент версии — увеличивает значение версии при каждом обновлении версии.

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

Вот обновлённый запрос для такого решения:

-- Выполняем чтение
SELECT seat_id, status, version FROM seats 
WHERE seat_id = 'A1' AND event_id = 'E123';

-- Совершаем попытку обновления
UPDATE seats 
SET status = 'RESERVED', user_id = 'U456', 
    reserved_at = NOW(), version = version + 1
WHERE seat_id = 'A1' AND event_id = 'E123' 
  AND status = 'AVAILABLE' 
  AND version = 42;
  
-- Проверяем затронутые строки, выполняем повтор, если их 0

Оптимистическая блокировка

На диаграмме ниже показана работа оптимистической блокировки.

У этой методики есть следующие преимущества:

• Повышение пропускной способности — без явной блокировки можно конкурентно выполнять больше запросов, повышая общую пропускную способность.

• Масштабируемость — решение может масштабироваться для обработки среднего объёма трафика и не очень популярных мероприятий.

• Повышение производительности чтения — в отличие от пессимистической блокировки, здесь чтение выполняется быстро.

Такое решение подходит для стабильных паттернов трафика с низкой степенью конкуренции за ресурсы. Например, для бронирования столиков в ресторанах, номеров отелей через Booking.com или Airbnb.

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

Хоть такое решение и гарантирует, что билет приобретёт только один человек, запрос остальных завершится сбоем. Поэтому другим придётся повторно пробовать бронировать себе место.

Оптимистическая блокировка обладает следующими недостатками:

• Неудобство для пользователей — в случае популярных событий могут возникать конфликты: бронирование приведёт к необходимости повторных попыток и разочарованию пользователей.

• Сложность приложений — приложения должны правильно обрабатывать ошибки конфликтов версий.

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

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

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

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

Распределённая блокировка в памяти

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

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

На диаграмме ниже показано, как распределённая блокировка в памяти предотвращает двойной букинг.

Этот подход решает проблемы предыдущих двух решений следующим образом:

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

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

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

• Утерю данных — кэш вылетает и все данные теряются.

• Недоступность кэша — может привести к скачку нагрузки на базу данных.

• Неснятые блокировки — когда блокировка не снимается, она не позволяет другим пользователям бронировать свободное место.

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

Пища для размышлений: что произойдёт, если кэш вылетит после получения блокировки места? Переопределит ли другой запрос бронирование места, что приведёт к двойному букингу?

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

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

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

Виртуальная очередь ожидания

Пользователи испытывают сложности с бронированием билетов на популярные концерты. Часто из-за высокого спроса пользователям не удаётся выкупить место.

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

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

Этот процесс работает следующим образом:

1. Система обнаруживает всплеск трафика и направляет запросы в очередь ожидания.

2. Запросы в очереди ожидания асинхронно обрабатываются приложением, а места приобретаются постепенно.

3. Пользователи способны проверять состояние мест и не могут купить ещё один билет, пока находятся в очереди ожидания.

4. После покупки билета пользователь получает уведомление (через Server-Sent Events или другой механизм).

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

Этот подход обладает следующими преимуществами:

• Масштабируемость — он не позволяет базе данных, кэшу и другим компонентам становиться узким местом. Асинхронное решение снижает нагрузку и повышает масштабируемость.

• Удобство пользования — при бронировании мест пользователи больше не видят кучу сообщений об ошибках.

• Справедливость — очередь FIFO гарантирует, что система отдаёт приоритет тем пользователям, которые вошли в очередь первыми.

Пища для размышлений: при каком количестве запросов в секунду (RPS), следует переходить к системе на основе виртуальной очереди ожидания? (10 тысяч RPS, 50 тысяч RPS или 100 тысяч RPS?)

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

• Сложностью — разработчики должны работать со слоем очереди, управлять им. Кроме того, система должна обеспечивать обновления в реальном времени при помощи SSE (Server-Sent Events). Это повышает сложность инфраструктуры и затраты на неё.

Итак, мы рассмотрели различные методики решения проблемы двойного букинга. Давайте подведём итог изученному.

Заключение

У всех систем бронирования наподобие TicketMaster, Airbnb, BookMyShow и так далее есть задача предотвращения двойного букинга. Случаи двойного букинга снижают доверие покупателей, поэтому это становится критической проблемой бизнеса.

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

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

Как вы думаете, можно ли скомбинировать разные решения и получить единую систему, подходящую для любого сценария использования, от бронирования места в самолёте до покупки билета на концерт популярной группы? Если да, то какие технические трудности вы предвидите при её разработке?