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

У ресурса есть максимальная вместимость. Бронь занимает часть этой вместимости на определенный период времени. Вам нужно ответить на обманчиво простой вопрос:

Могу ли я забронировать 2 единицы на 45 минут, и если да, то когда можно начать?

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

Это стало отправной точкой для CapacityAvailability — небольшой PHP-библиотеки, которую я недавно выпустил в версии 1.0.0.

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

Ловушка: пересечение не равно одновременному использованию

Предположим, вместимость ресурса равна 3, и в нем уже есть следующие бронирования:

Предлагаемое бронирование займет 2 единицы с 09:00 до 10:30.

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

Но существующие брони никогда не действуют одновременно. В каждый момент времени занята только одна единица. Две единицы остаются свободными на протяжении всего 90-минутного интервала. Запрос помещается.

Теперь добавим еще одно бронирование на 2 единицы с 09:45 до 10:15. Ответ меняется: в течение части интервала все 3 единицы оказываются занятыми.

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

И есть еще одна сложность: сам ресурс может иметь вместимость 2 до 10:00 и вместимость 3 после.

Явное моделирование времени

Я выбрал простую модель:

  • Интервал вместимости задает общее количество доступных единиц в течение [start, end) .
  • Бронирование потребляет положительное число единиц в течение [start, end) .
  • Запрос задает необходимое количество единиц и продолжительность, в течение которой эти единицы должны оставаться доступными.

Обозначение [start, end)  имеет значение. Начало включается в интервал (inclusive), конец — нет (exclusive). Бронь, заканчивающаяся ровно в 10:00, не конфликтует с другой бронью, начинающейся в 10:00.

Объявления вместимости являются абсолютными, а не аддитивными: если пул имеет вместимость 3, это уровень, равный 3, а не дополнительные 3 единицы к пересекающемуся объявлению. Пересекающиеся объявления вместимости отклоняются. Любой период без объявленной вместимости имеет нулевую вместимость.

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

Алгоритм сканирующей прямой: проверяем только там, где меняется состояние

В основе лежит алгоритм сканирующей прямой (sweep-line).

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

  1. Когда начинается вместимость — добавляем ее единицы.
  2. Когда вместимость заканчивается — вычитаем ее единицы.
  3. Когда начинается бронирование — увеличиваем число занятых единиц.
  4. Когда бронирование заканчивается — уменьшаем число занятых единиц.
  5. Сортируем временные метки событий и применяем все изменения, приходящиеся на один и тот же момент времени, вместе.

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

Например:

Если нам нужно 2 единицы на 45 минут, период с 09:00 до 09:30 слишком короткий. Непрерывная доступность с 10:00 до 11:00 подходит по длительности.

Результатом является не предопределенный массив 15-минутных слотов. Это непрерывное окно с достаточной остающейся вместимостью на всю запрошенную продолжительность.

Для C  интервалов вместимости и R  бронирований расчет требует O((C + R) log(C + R))  времени и O(C + R)  дополнительной памяти, причем основная доля приходится на сортировку границ событий.

Пробуем в PHP

Установите пакет:

composer require alkin/capacity-availability:^1.0

Вот тот же пример с использованием публичного API:

10:00-11:00; latest start: 10:15

Последнее поле заслуживает особого внимания: 10:15 — это допустимое время начала. 45-минутное бронирование, начинающееся в 10:15, заканчивается в 11:00, ровно на границе интервала.

Если ваш интерфейс предлагает пользователю только 15-минутные слоты, он может отображать 10:00 и 10:15. Но сам расчет не должен навязывать эту сетку.

Библиотека также предоставляет canBook()  для получения точного интервала и timeline()  для проверки вместимости, занятости и свободных единиц.

Важное отличие: доступно не значит забронировано

До сих пор мы решали детерминированную расчетную задачу. Мы не решали проблему параллельного бронирования (concurrency).

Представьте, что два запроса поступают одновременно. Каждый читает базу данных и видит два свободных места. Каждому нужны два места. Оба вызывают canBook() , оба получают true  и оба создают запись о бронировании.

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

Именно поэтому библиотека отделяет чистый алгоритм от опционального адаптера Doctrine DBAL для конкретной схемы MariaDB/InnoDB.

Процесс бронирования в адаптере, если говорить упрощенно, выглядит так:

BEGIN TRANSACTION SELECT pool_id FROM capacity_pools WHERE pool_id = :pool FOR UPDATE -- Read capacity and overlapping bookings -- Recalculate availability while holding the pool lock -- Insert only when the request fits COMMIT

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

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

Адаптер также намеренно не предоставляет идемпотентность, автоматические повторы при дедлоках или произвольные маппинги ORM. Он отклоняет вложенные транзакции; его поведение было проверено для описанной настройки MariaDB, а не для любой СУБД или конфигурации уровня изоляции.

Я предпочитаю четко задокументировать эти границы, чем прятать их за удобным на вид API.

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

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

Выдает ли алгоритм правильный ответ?

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

Релиз проверялся на 300 рандомизированных календарях с минутным разрешением, 80 календарях с секундным разрешением и 77 525 эталонных утверждениях (assertions), а также с помощью юнит-тестов и статического анализа.

Предотвращает ли адаптер базы данных состояние гонки?

Для этого требовались реальные параллельные процессы, а не два последовательных вызова методов.

В изолированной тестовой базе данных MariaDB 11.3.2 я запускал сценарии с независимыми PHP-воркерами. Набор тестов включает намеренно небезопасный пример, демонстрирующий перебронирование, за которым следуют корректно заблокированные транзакции.

Зафиксированные результаты: 12 сценариев, 43 независимых PHP-процесса и 198 утверждений. Небезопасный тест сознательно ограничен использованием одноразовых тестовых данных.

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

Почему это не Symfony-бандл

Я в основном работаю с Symfony, и ранние эксперименты включали реальное приложение на Symfony с использованием DoctrineBundle. Было искушение упаковать все в виде Symfony-бандла.

Но сам расчет не нуждается в Symfony. Ему просто нужны массивы неизменяемых объектов-значений (value objects), возвращающие результаты.

В приложении Symfony калькулятор можно зарегистрировать как обычный сервис:

# config/services.yaml services : Alkin\CapacityAvailability\AvailabilityCalculator : ~

Этого было достаточно для интеграции ядра с помощью внедрения зависимостей (dependency injection). Опциональные классы Doctrine можно зарегистрировать аналогичным образом, если приложение использует задокументированную схему персистентности.

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

Где проходят границы применимости

CapacityAvailability — это не полноценная платформа для бронирования.

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

Что она действительно предлагает, так это сфокусированное решение одного повторяющегося вопроса:

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

Сохранение этой границы в явном виде является частью дизайна.

Проект распространяется с открытым исходным кодом под лицензией MIT, поддерживает PHP 8.2+, а ядро расчетов не имеет обязательных зависимостей во время выполнения.

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

Оригинал опубликован на https://dev.to 21 октября 2026 г.