Weighted Round Robin

Weighted Round Robin (WRR, взвешенный циклический алгоритм) — это алгоритм диспетчеризации (планирования) задач или распределения сетевого трафика, который является модификацией классического алгоритма Round Robin (циклический алгоритм). В отличие от Round Robin, где каждому участнику (процессу, серверу, очереди) выделяется равный квант времени или равная доля ресурсов, WRR назначает каждому участнику определённый вес, пропорционально которому и распределяется нагрузка. Это позволяет учитывать различную производительность узлов или приоритеты задач, обеспечивая более гибкое и эффективное управление ресурсами.

История

Концепция взвешенного циклического планирования возникла в контексте операционных систем и сетевых технологий в 1980-х — 1990-х годах. Классический Round Robin, известный ещё со времён ранних многозадачных систем, не мог эффективно справляться с задачами разной важности или с серверами разной мощности. Для решения этой проблемы был предложен Weighted Round Robin, который впервые был формализован в работах по теории очередей и планированию пакетов в сетях передачи данных. В частности, алгоритм Weighted Fair Queuing (WFQ), разработанный в 1990-х годах, стал более сложной и справедливой версией WRR. В современных системах WRR широко применяется в балансировщиках нагрузки (load balancers), планировщиках задач в ядрах операционных систем и в контроллерах трафика в сетях.

Принцип работы

Основная идея WRR заключается в том, что каждому участнику (например, серверу в пуле или очереди задач) назначается целое число — вес. Вес может быть произвольным положительным числом, обычно от 1 до 100. Чем больше вес, тем большую долю ресурсов (времени, пропускной способности) получает участник.

Алгоритм работает циклически, обходя всех участников по порядку. В каждом цикле участник с весом W получает W квантов работы (или W запросов). Например, если есть три сервера с весами 3, 2 и 1, то за один полный цикл первый сервер получит 3 запроса, второй — 2, третий — 1. После этого цикл повторяется.

Существует несколько вариантов реализации WRR, различающихся способом распределения квантов в рамках одного цикла:

• Последовательный WRR (Classic WRR): Участники обрабатываются строго по порядку. Сначала все кванты первого участника (3 запроса), затем все кванты второго (2 запроса), затем третьего (1 запрос). Недостаток — возможна «пульсация» нагрузки: на короткое время один сервер получает лавину запросов, а другие простаивают.
• Равномерный WRR (Interleaved WRR): Кванты распределяются более равномерно, чтобы сгладить пульсации. Например, для весов 3, 2, 1 последовательность может быть: 1-й, 2-й, 1-й, 3-й, 1-й, 2-й. Это достигается с помощью специальных алгоритмов, таких как «дефицитный циклический алгоритм» (Deficit Round Robin, DRR) или «взвешенный циклический алгоритм с минимальной задержкой» (Weighted Round Robin with minimum delay).
• Адаптивный WRR: Веса могут динамически меняться в зависимости от текущей загрузки участников или других параметров (например, времени отклика). Это позволяет системе адаптироваться к изменяющимся условиям.

Классификация

WRR можно классифицировать по нескольким признакам:

По области применения

• Планирование процессов (Process Scheduling): В операционных системах WRR используется для распределения процессорного времени между потоками или процессами с разными приоритетами. Процесс с большим весом получает больше квантов времени.
• Балансировка сетевой нагрузки (Load Balancing): В сетевых балансировщиках (например, в Nginx, HAProxy, F5) WRR распределяет входящие запросы между серверами бэкенда. Сервер с большей производительностью получает больший вес.
• Управление трафиком (Traffic Shaping): В сетевых коммутаторах и маршрутизаторах WRR используется для справедливого распределения полосы пропускания между разными классами трафика (например, голосовой трафик имеет больший вес, чем файловый обмен).

По способу учёта весов

• Статический WRR: Веса задаются администратором вручную и не меняются во время работы.
• Динамический WRR: Веса могут автоматически корректироваться на основе метрик производительности (загрузка CPU, время ответа, количество активных соединений).

Устройство и характеристики

Математическая модель

Пусть имеется N участников, каждому из которых назначен вес w_i (i = 1..N). Общий вес всех участников W = sum(w_i). Доля ресурсов, получаемая участником i, равна w_i / W. Например, если веса равны 3, 2, 1, то доли будут 3/6 = 0.5, 2/6 ≈ 0.333, 1/6 ≈ 0.167.

Основные параметры

• Вес (Weight): Целое число, определяющее приоритет или производительность участника.
• Квант (Quantum): Минимальная единица работы (например, один запрос, один такт процессора).
• Цикл (Cycle): Полный обход всех участников, в ходе которого каждый получает количество квантов, равное его весу. Длина цикла равна сумме весов всех участников.

Преимущества

• Гибкость: Позволяет учитывать разную производительность узлов или приоритеты задач.
• Простота реализации: Алгоритм легко реализуется как в программном, так и в аппаратном обеспечении.
• Предсказуемость: При статических весах распределение нагрузки является детерминированным и легко прогнозируемым.
• Справедливость: Обеспечивает пропорциональное распределение ресурсов, что более справедливо, чем равномерное распределение при неравных возможностях.

Недостатки

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

Применение

Балансировка нагрузки в веб-серверах

WRR является одним из стандартных алгоритмов балансировки в таких решениях, как Nginx, HAProxy, Apache Traffic Server. Администратор может задать веса для каждого сервера в пуле, например:

`` upstream backend { server backend1.example.com weight=3; server backend2.example.com weight=2; server backend3.example.com weight=1; } ``

В этом случае на backend1 будет направлено 50% запросов, на backend2 — 33%, на backend3 — 17%.

Планирование задач в операционных системах

В некоторых ОС (например, в Linux с планировщиком CFS) используется модифицированная версия WRR для распределения процессорного времени между процессами. Каждому процессу назначается «вес» (nice value), который влияет на долю процессорного времени.

Сетевые коммутаторы и маршрутизаторы

В коммутаторах Ethernet (например, Cisco Catalyst) WRR используется для управления очередями приоритетов. Например, голосовой трафик (VoIP) может иметь вес 10, видеотрафик — 5, а обычный трафик данных — 1. Это гарантирует, что голосовой трафик получит большую долю полосы пропускания.

Примеры

Пример 1: Балансировка запросов

Пусть есть два сервера: Server A (вес 2) и Server B (вес 1). Входящие запросы: R1, R2, R3, R4, R5, R6.

При последовательном WRR (Classic WRR) порядок будет: R1 -> A, R2 -> A, R3 -> B, R4 -> A, R5 -> A, R6 -> B. За 6 запросов A получит 4, B — 2.

При равномерном WRR (Interleaved WRR) порядок может быть: R1 -> A, R2 -> B, R3 -> A, R4 -> A, R5 -> B, R6 -> A. Результат тот же (4 и 2), но распределение более равномерное.

Пример 2: Планирование процессов

Процесс P1 имеет вес 3, P2 — вес 1, P3 — вес 2. Квант времени = 10 мс. За один цикл (6 квантов, 60 мс) P1 получит 30 мс, P2 — 10 мс, P3 — 20 мс.

Критика

Основная критика WRR связана с его неспособностью адаптироваться к динамическим изменениям. В современных распределённых системах, где нагрузка может резко меняться, статическое назначение весов часто приводит к неоптимальному использованию ресурсов. Кроме того, WRR не учитывает «состояние» участников — например, если один сервер временно недоступен, алгоритм всё равно будет пытаться направлять на него запросы, что приводит к ошибкам. Для решения этих проблем часто используются более сложные алгоритмы, такие как Least Connections (наименьшее количество соединений) или Consistent Hashing (консистентное хеширование), которые динамически учитывают текущую загрузку.

Источники

1. Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
2. Stevens, W. R. (1994). TCP/IP Illustrated, Volume 1: The Protocols. Addison-Wesley.
3. Kurose, J. F., & Ross, K. W. (2017). Computer Networking: A Top-Down Approach (7th ed.). Pearson.
4. Документация Nginx: «HTTP Load Balancing» (nginx.org).
5. Документация HAProxy: «Weighted Round Robin» (haproxy.org).