Алгоритм распределения сообщений из нескольких очередей с учётом квот и полной загрузки канала

Условие

Дано:\n1. Канал отправки полезных сообщений, обладающий фиксированной пропускной способностью n – максимальное число сообщений, которое можно передать за один цикл.\n2. Произвольное количество очередей m. Сообщения в очереди появляются асинхронно и в разных объёмах; новые очереди могут появляться в любой момент.\n3. Каждая очередь имеет уникальный идентификатор (целое число).\n4. На момент запроса известен текущий размер каждой очереди – количество ожидающих сообщений.\n5. Для каждой очереди задан положительный коэффициент quota (вес), отражающий минимальную долю канала, которую очередь должна получать.\n\nЗадача: разработать алгоритм, который на каждой итерации определяет, сколько сообщений следует взять из каждой очереди и отправить в канал, соблюдая три требования:\n1. Work‑conserving – использовать канал максимально эффективно. Если суммарное число сообщений во всех очередях превышает n, то в канал должно быть отправлено ровно n сообщений.\n2. Starvation‑free – гарантировать, что очереди с небольшими долями тоже получат сообщения. Например, если одна очередь имеет долю 1000, а другая – 0.00001, то сообщения из второй очереди всё равно должны быть отправлены.\n3. Fairness – обеспечить, чтобы каждая очередь получала доступ к каналу в соответствии со своей квотой.\n\nПример работы при пропускной способности канала 10:\n- Одна очередь, квота 0.5, 100 сообщений → отправляются 10 сообщений (квота не ограничивает, канал полностью загружен).\n- Две очереди, обе с квотой 0.5, по 100 сообщений → из каждой берётся по 5 сообщений.\n- Две очереди, квоты 0.2 и 0.8, по 100 сообщений → из первой – 2 сообщения, из второй – 8 сообщений.\n- Две очереди, квоты 0.25 и 1, по 100 сообщений → из первой – 2 сообщения, из второй – 8 сообщений.\n- Сто очередей, каждая с квотой 1 и 100 сообщений → берётся по одному сообщению из каждой десятой очереди, затем смещается на один и так далее.\n\n```php // Основной цикл отправки сообщений, на каждой итерации которого вычисляется нужное количество сообщений по каждой очереди. function dispatcher(Source $source) { $messages = ; while (true) { // Имитируем поступление сообщений в очереди $source->next(); // Рассчитываем количество сообщений которое нужно извлечь из каждой очереди $batchSizes = calculateMessageBatchSizes($source->queueSizes(), $source->queueQuotas()); $source->printStats($batchSizes); // Извлекаем нужное количество сообщений из каждой очереди и складываем их в общий массив foreach ($batchSizes as $queueId => $batchSize) { if ($batchSize <= 0) { continue; } $messages = array_merge( $messages, $source->extractMessagesFromQueue($queueId, $batchSize) ); } // Отправляем сообщения если они есть if ($messages) { sendMessages($messages); $messages = ; } } }

/**

• @param array<int, int> $queueSizes
• @param array<int, float> $queueQuotas
• @param int $bandwidth
• @return array */ function calculateMessageBatchSizes(array $queueSizes, array $queueQuotas, int $bandwidth = 20): array {

Ответ

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

Подойдёт weighted fair scheduling: у каждой активной очереди храните виртуальную стоимость следующего сообщения; выбирайте минимальную, увеличивайте её на 1/quota и повторяйте до n отправок или опустошения всех очередей. Новую активную очередь привязывайте к текущему виртуальному времени, чтобы она не получала бесконечный накопленный приоритет.

Min-heap даёт O(n log m) выборов на цикл, плюс обновление списка активных очередей. При конечном числе постоянно активных очередей и положительных весах доли соблюдаются в долгом интервале, а маленькая квота со временем получает обслуживание. Гарантировать положительную долю каждой очереди в каждом цикле при m > n невозможно; очень малый вес означает большое ожидание. Для строгого ограничения ожидания нужна отдельная минимальная квота, меняющая исходную пропорцию.

Источник: www.rfc-editor.org.