Priority Queue

Зачем нужно знать

Priority queue нужна, когда порядок обработки не должен совпадать с порядком прихода. FIFO честна по времени, но не по бизнес-ценности: premium ticket может ждать за бесплатным batch, password reset email за newsletter, payment webhook за nightly report. В системном дизайне это быстро превращается в SLO-проблему: важный запрос формально «в очереди», но пользователь или бизнес уже считают его просроченным.

Очередь с приоритетами вводит явную scheduling policy. Consumer выбирает следующую job не только по enqueued_at, но и по важности, дедлайну, tenant fairness и доступной емкости. Это связывает паттерн с message-queues, load-shedding, rate-limiting, dead-letter-queue, back-pressure. Priority queue полезна не потому, что high всегда должен побеждать, а потому, что система перестает делать вид, будто все jobs одинаковы.

Mental model

Представьте отдел поддержки с несколькими линиями: critical incidents, paid support, обычные вопросы, low-priority feedback. Если оператор всегда берет самое старое письмо из общей папки, SLA для critical будет случайностью. Если оператор берет только critical, обычные обращения никогда не закончатся. Правильная priority queue похожа на диспетчера: она продвигает срочное вперед, но резервирует часть capacity для менее срочного и повышает приоритет задач, которые ждут слишком долго.

Ключевая мысль: priority queue это не просто три физических очереди high, normal, low. Это контракт dequeue. Он отвечает на вопросы: какой priority wins, есть ли aging, какие веса у bucket'ов, как не дать одному tenant забить весь high, что делать при overload, как менять priority после enqueue.

Что показывает диаграмма

Диаграмма показывает free-клиентов, premium-клиента, три очереди (q-high, q-normal, q-low) и worker, который poll'ит по приоритету. В FIFO-сценарии все попадают в обычную очередь, поэтому premium оказывается в хвосте за двумя free jobs. В priority-сценарии premium идет в q-high, free jobs в q-low, и worker сначала берет high. Затем диаграмма показывает starvation: если high постоянно пополняется, low может ждать часами. Финальный сценарий показывает Redis ZSET как практическую структуру для приоритетов.

Топология намеренно не скрывает проблему за брокером. Даже если у вас RabbitMQ, Redis, Postgres или SQS workaround, главный риск остается тот же: как именно consumer выбирает следующую работу. Поэтому сценарии показывают и happy path, и failure mode.

Сценарии и что они учат

fifo-unfair учит, что FIFO может нарушать SLA, хотя работает «правильно». Premium job пришла позже и ждет, потому что две бесплатные задачи уже в очереди. ADR-вывод: если бизнес различает классы обслуживания, этот факт должен быть представлен в queue contract, а не только в UI или billing.

priority-queue-fixes показывает отдельные очереди по priority. Worker берет high раньше low, и premium не блокируется за free batch. ADR-вывод: multiple queues + weighted polling являются простым и понятным вариантом, особенно для Sidekiq/Celery/RabbitMQ-подобных систем. Но strict high-first нельзя оставлять без защиты от starvation.

starvation-bug показывает главную ловушку: постоянный high traffic навсегда вытесняет low. Low queue растет, старые jobs становятся бесполезными, система может прийти к OOM. Диаграмма предлагает два решения: weighted draw, где low получает гарантированные 5-10% capacity, и aging, где старые low jobs постепенно повышаются. ADR-вывод: любой strict priority design должен иметь fairness-механизм.

real-impl-redis-zset показывает sorted set: ZADD с score и atomic pop через Lua. Урок: ZRANGE плюс ZREM двумя командами создает race между workers. ADR-вывод: priority queue на Redis требует atomic pop, visibility timeout/retry semantics и мониторинга pending jobs; иначе вы получите lost или duplicated jobs.

Trade-offs

Первый trade-off: latency high-priority против completion low-priority. Чем агрессивнее high-first, тем лучше SLA для premium и critical, но тем выше риск starvation. Weighted polling сглаживает риск, но иногда high будет ждать за low job. Aging решает starvation, но может неожиданно поднять старую низкую задачу выше свежей важной задачи. ADR-решение зависит от смысла low: если low можно потерять, используйте shedding; если low обязан завершиться, резервируйте capacity.

Второй trade-off: multiple queues против sorted structure. Multiple queues просты, быстры и хорошо ложатся на брокеры, но priority уровни дискретны, а изменение priority после enqueue сложнее. Sorted set/heap гибче, поддерживает score и deadlines, но дает O(log N), требует atomic операций и внимательной конкуренции consumers.

Третий trade-off: global priority против per-tenant fairness. Один крупный premium tenant может заполнить весь high bucket, оставив маленьких premium-клиентов без SLA. ADR-подход: внутри priority bucket иметь per-tenant subqueues и round-robin/weighted fair queueing.

Четвертый trade-off: priority против ordering. Как только вы вводите приоритет, общий FIFO-порядок ломается. Если порядок внутри entity критичен, нужен MessageGroupId, partition key или отдельная последовательность для конкретного aggregate.

Реальные системы

Sidekiq поддерживает очереди с весами и порядком polling; это простой путь для Ruby/Rails. BullMQ использует Redis и поддерживает prioritized jobs через sorted structures. RabbitMQ имеет native priority queues через x-max-priority, но слишком много уровней ухудшает эффективность и ясность. AWS SQS не дает настоящую priority queue напрямую, поэтому обычно делают несколько очередей и weighted consumers; FIFO MessageGroupId помогает с ordering внутри группы. Kafka не имеет встроенного priority dequeue, поэтому приоритеты моделируют отдельными topics или consumer groups. Postgres-вариант строят на таблице jobs с ORDER BY priority, enqueued_at LIMIT 1 FOR UPDATE SKIP LOCKED.

В production priority часто комбинируется с delay, retry, DLQ и rate limits. Например, security alert идет high и immediate, marketing email идет low и может быть delayed, retry может получать отдельный приоритет, чтобы не копить unfinished work.

Anti-patterns и типичные ошибки

Strict priority без aging или weights приводит к starvation. Слишком много уровней приоритета превращает систему в спор о числах: 37 важнее 42 или наоборот. Priority в payload опасен, если broker/worker не может по нему сортировать. Еще одна ошибка: общий worker pool для всех типов jobs, где долгий low job занимает worker и мешает high; иногда нужны separate pools или preemption.

Нельзя делать dequeue через «вытащим все, отсортируем в приложении». Это O(N log N), дорого и ломается при конкуренции. Нельзя забывать idempotency: приоритетные retry могут выполнить действие повторно. Нельзя считать priority queue заменой load shedding: при overload низкий приоритет может быть не просто отложен, а явно отброшен по политике.

Когда НЕ использовать

Priority queue не нужна, если все jobs имеют одинаковую ценность и одинаковый deadline. Она вредна, если бизнес не может объяснить уровни приоритета: тогда система станет произвольной и трудной для поддержки. Не стоит вводить priority для строгого ordered event log, где важно сохранить порядок всех событий. Не стоит использовать priority queue как способ «ускорить» систему, если реальная проблема в недостатке workers, медленной базе или внешнем API.

Для маленького сервиса иногда достаточно двух очередей: online и batch. Для critical sync path лучше вообще не отправлять работу в очередь, если пользователь должен получить ответ прямо сейчас; тогда нужны timeout, bulkhead и capacity planning.

Дальше читать

В CloudArch продолжайте с message-queues, load-shedding, rate-limiting, dead-letter-queue, back-pressure, payment-system, notification-system. Из внешних источников полезны Sidekiq Advanced Options, RabbitMQ Priority Queue Support, BullMQ prioritized jobs, AWS SQS FIFO docs, PostgreSQL FOR UPDATE SKIP LOCKED, материалы по operating systems scheduling: multilevel feedback queues, aging и weighted fair queueing.