Балансировка нагрузки с общими очередями приоритетов

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

  • У меня есть очередь запросов queue_a, которые обрабатываются worker_a.
  • Существует вторая очередь запросов queue_b, которые обрабатываются worker_b.
  • И у меня есть третья очередь запросов queue_c, которая может идти к любому из рабочих

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

Я собирался реализовать это, используя 3 экземпляра C5 IntervalHeap. Каждый работник будет иметь доступ к своей локальной очереди + к общим очередям, частью которых он является (например, worker_a может видеть queue_a и queue_c).

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

РЕДАКТИРОВАТЬ: я обнаружил, что IntervalHeap не работает в порядке очереди с запросами с одинаковым приоритетом!

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

Надеюсь, что это объясняет это достаточно ясно!


c# priority-queue c5
person mike    schedule 10.07.2012    source источник
comment
Взгляните на поток данных TPL, он предоставляет общие решения для вашей заявленной проблемы. В этом случае вам, возможно, придется отказаться от использования C5.   -  person Polity    schedule 10.07.2012
comment
У вас есть дополнительная информация по этому поводу? например, как я могу использовать TPL в этом сценарии? Я немного погуглил, но не ясно, как я мог бы использовать это в моей ситуации.   -  person mike    schedule 10.07.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

Вот две идеи:

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

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

ХТН

person Monroe Thomas    schedule 10.07.2012
comment
да, у каждого решения есть ограничения. Я подумал об одном, где общие очереди вставляют своего рода маркер в другие очереди, чтобы представить доступную работу. Когда рабочий видит эти токены в своей локальной очереди, он пытается получить запрос из общей очереди. Если он больше не существует, они просто продолжают. В противном случае он обрабатывается нормально. Это просто приводит к накладным расходам, если у вас есть общие очереди в большом количестве других очередей, поскольку каждая очередь должна проверять каждый запрос общей очереди. - person mike; 10.07.2012
comment
Я не согласен с этим ответом. Безусловно, существует разница в приоритетах между личными и общими элементами. Все зависит от состояния разных очередей. Смотрите мой ответ. - person Polity; 11.07.2012
comment
@Polity ОП прямо заявил, что приоритет элементов в начале очередей одинаков. Сказать, что частная очередь имеет более высокий приоритет, может быть вполне допустимым способом решения проблемы, но это не оценочное суждение, поддерживаемое исходным вопросом, который, по сути, сводится к следующему: у меня есть две задачи с одинаковым приоритетом, но только один рабочий - что выбрать? Должен быть какой-то механизм разрыва связей, и среди множества вариантов выбор частной очереди не более и не менее действителен, чем выбор случайным образом или выбор самой длинной очереди. - person Monroe Thomas; 12.07.2012

arrow_upward
1
arrow_downward

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

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

Все зависит от ваших требований.

person Polity    schedule 11.07.2012
comment
В настоящее время я реализовал его, поэтому общая очередь является не очередью, а скорее списком поиска. Когда общая очередь получает работу, она помещает работу во все нижележащие очереди со специальным флагом, указывающим, что это общая работа. Когда рабочий процесс получает рабочую нагрузку с этими специальными флагами, он сверяется с общей очередью, чтобы убедиться, что работу все еще нужно выполнить. Если он больше не действителен, он просто отбрасывает и берет следующий элемент в своей очереди. Если он действителен, он продолжает его обработку. Это приводит к паре дополнительных проверок, но сохраняет функциональность, которую я искал. - person mike; 12.07.2012