Два случайных выбора

Бросьте сто шаров в сто корзин наугад — и одна корзина почти наверняка наберёт четыре-пять шаров, хотя в среднем на корзину приходится один. Теперь для каждого шара выберите наугад две корзины и положите его в ту, где меньше. Переключите «один выбор» на «два» и посмотрите, что станет с самой полной корзиной.

Снизу — то же самое для больших чисел: шаров столько же, сколько корзин, от десяти до миллиона. С одним выбором самая полная корзина растёт медленно, но заметно, и при миллионе шаров доходит до девяти. С двумя она почти лежит: от двух до четырёх шаров на всём диапазоне. Третий выбор добавляет совсем немного: самая полная корзина становится легче на шар, не больше. Весь выигрыш — в переходе от одного к двум.

Идея

Когда нужно отдать работу одному из многих исполнителей, не обязательно знать нагрузку всех. Достаточно спросить двух случайных и выбрать менее занятого. Случайный выбор держит нагрузку ровной в среднем, но его хвост — самая перегруженная корзина — растёт как ln n / ln ln n. Сравнение двух срезает этот хвост до ln ln n / ln 2: при n = 10⁶ это 3,8 против 5,3, а при n = 10¹⁰⁰ — уже 7,8 против 42. Опрос всех серверов дал бы ещё немного, но стоит n вопросов вместо двух и, как увидим, плохо переносит устаревшие сведения.

Задача «шары по корзинам» — модель многих вещей сразу. Шары — запросы, корзины — серверы. Шары — ключи, корзины — ячейки хеш-таблицы с цепочками: самая полная корзина — самая длинная цепочка, то есть худший поиск. Шары — задания, корзины — процессоры. Везде важна не средняя нагрузка (она и так ровная), а самая большая: именно на ней кончается память, растёт время ответа и ломается обещание «за константу». О том, как ведут себя цепочки при одной хеш-функции, рассказывает глава курса о хешировании; здесь — что даёт вторая.

Почему квадрат

Сначала один выбор. Корзина набирает k шаров, если на неё пришлись какие-то k из n бросков. Вероятность этого не больше, чем число способов выбрать k бросков, умноженное на вероятность, что все они попали в эту корзину:

Корзин n, поэтому самая полная наберёт k шаров с вероятностью не больше n / k!. Это меньше единицы, как только k! > n. Для n = 100 000: 8! = 40 320 ещё меньше, а 9! = 362 880 уже больше, так что оценка обещает не больше девяти — в листинге получилось восемь. Факториал растёт чуть быстрее показательной функции, отсюда и ответ ln n / ln ln n: при таком k как раз k! ≈ n. Формула с логарифмами — только первый член разложения, и сходится она медленно: для ста тысяч она даёт 4,7 при настоящих восьми. Точнее посчитал Гастон Гонне в 1981 году: ожидаемый максимум растёт как обратная гамма-функция Γ⁻¹(n), то есть как решение того же уравнения k! ≈ n.

Теперь посмотрим на корзины не по одной, а слоями: сколько корзин набрали хотя бы один шар, хотя бы два, хотя бы три. Вот что получилось в листинге при n = 100 000:

С одним выбором каждый следующий слой меньше предыдущего сначала в 2,4 раза, потом в 3,3, в 4,3, в 5 — делитель растёт примерно на единицу за слой, это и есть факториал. С двумя выборами слой падает с 22,9 % корзин до 0,9 %, а потом до одной корзины из ста тысяч. Доля не делится, а возводится в квадрат: 0,229² ≈ 0,052, и настоящая доля даже меньше этой оценки. Отсюда и всё остальное.

Из того же рассуждения видно, почему третий выбор почти ничего не даёт: он меняет степень с 2 на 3, то есть делитель ln d с 0,69 на 1,10. Это выигрыш в полтора раза у величины, которая и так растёт как двойной логарифм. От одного выбора к двум — разница экспоненциальная, от двух к трём — в константу. В таблице выше три выбора дают тройку вместо четвёрки, и это всё.

Есть и неожиданное улучшение без лишних вопросов. Бертольд Фёккинг в 1999 году разделил корзины на две половины, левую и правую, и брал по одной случайной корзине из каждой; при равенстве шар всегда шёл налево. Такое несимметричное правило даёт ln ln n / (2 ln φ) + O(1), где φ ≈ 1,618 — золотое сечение. Слои в его анализе убывают по закону чисел Фибоначчи, и 2 ln φ = ln φ² ≈ ln 2,62: два несимметричных выбора работают так, будто их 2,62 симметричных.

Очередь у кассы

Шары не уходят из корзин, а запросы уходят: сервер их отрабатывает. Майкл Митценмахер в диссертации 1996 года рассмотрел так называемую модель супермаркета: n касс, покупатели приходят случайным потоком, каждый смотрит на две случайные кассы и встаёт в более короткую очередь. Пусть кассы заняты на долю λ < 1. При случайном выборе одной кассы доля касс, у которых хотя бы i покупателей (вместе с тем, кого обслуживают), равна λⁱ. При выборе из двух, когда касс очень много, — λ²ⁱ⁻¹. Та же картина, что у шаров: показатель удваивается со слоем. Независимо и в том же году к этому результату пришли Никита Введенская, Роланд Добрушин и Фридрих Карпелевич.

При загрузке 90 % и случайной кассе треть касс держит очередь хотя бы в десять человек. При лучшей из двух очередь в десять человек практически не встречается: её доля — 10⁻⁴⁷. Если сложить эти доли, получится средняя длина очереди, а поделив её на λ, — среднее время в системе: 10 времён обслуживания при одной кассе и 2,6 — при лучшей из двух. Почти вчетверо.

Модель супермаркета считает, что касс бесконечно много и время обслуживания распределено показательно. Настоящие запросы устроены иначе, и проверить идею лучше на них. Ниже десять серверов отдают файлы этого сайта — 20 000 настоящих размеров из истории правок. Отдача стоит 50 мкс плюс 1 мкс на каждые 100 байт, и запросы приходят так часто, что серверы заняты на 90 %. Размеры очень неровные: медианный файл отдаётся за 0,15 мс, средний — за 0,47 мс, самый большой — за 84 мс, а на один процент самых тяжёлых запросов приходится 27 % всей работы.

Таблица под сценой — времена ответа из листинга. Лучший из двух вдвое сокращает среднее время и медиану по сравнению со случайным сервером и почти не уступает опросу всех: 19,5 мс против 18,4. Хвост у опроса всех в этом прогоне даже чуть длиннее, но это уже в пределах разброса одного опыта. «По кругу» раздаёт запросы идеально поровну по числу, но не смотрит на очереди: сервер, которому достался файл на 84 мс, продолжает получать свою десятую долю запросов, и они стоят за этим файлом.

Почему выигрыш вдвое, а не вчетверо, как в модели супермаркета? Десять серверов — не бесконечность, но главное не это. Если в той же модели заменить настоящие размеры случайными с показательным распределением и тем же средним, случайный сервер даёт около 4,6 мс, лучший из двух — около 1,3 мс: разница примерно в 3,4 раза. Мешают неровные размеры. Число заданий ничего не говорит об их размере: сервер с одним огромным файлом выглядит свободнее, чем сервер с тремя крошечными, и новый запрос встаёт за огромным. Тяжёлый хвост размеров делает очереди длиннее при любом правиле: средний ответ при случайном сервере — 86 времён обслуживания, а не десять, как обещает модель с показательным временем. Против этого помогает смотреть не на число заданий, а на оставшуюся работу или на измеренное время ответа — об этом ниже, в разделе о тонкостях.

Старые сведения

До сих пор балансировщик знал длины очередей точно, в момент прихода запроса. В жизни так не бывает. Сведения идут по сети и устаревают; у каждого из многих балансировщиков своя, неполная картина. Митценмахер в 1997 году изучил крайний случай — доску объявлений: серверы раз в T единиц времени пишут на неё длины своих очередей, а балансировщики читают только доску.

Что сделает «самый свободный» со старой доской? Доска говорит, что сервер 4 пуст, — и все запросы до следующего обновления уходят на сервер 4. Он тонет, остальные простаивают. На следующем обновлении доска покажет пустым другой сервер, и стадо побежит туда. Лучший из двух страдает куда меньше: пары случайные, и запросы расходятся по всем серверам, которые на доске числятся в нижней половине.

При доске раз в 10 мс посмотрите на «самого свободного»: очереди в сотню-две заданий у серверов, которые доска недавно объявила пустыми, а рядом — пустые серверы, которые она считает занятыми. В среднем по прогону самая длинная из десяти очередей у него — 181 задание, у лучшего из двух — 67. Времена ответа из листинга:

При доске раз в 10 мс опрос всех уже хуже случайного сервера (40,3 мс), который вообще ничего не спрашивает. При 50 мс — в пять с половиной раз хуже. Лучший из двух за то же время сдаёт с 19,5 до 27,9 мс и всё ещё заметно лучше случайного сервера. Это и есть главный практический довод за два случайных выбора. Дело не в том, что они почти так же хороши, как опрос всех, при точных сведениях, а в том, что они не превращают устаревшие сведения в стадо. Такой случай встречается постоянно: у nginx несколько рабочих процессов, и без общей зоны памяти каждый считает соединения сам; в сети сервисов у каждого клиента свой балансировщик, который знает только о своих запросах.

Код

Листинг воспроизводит все три опыта: шары по корзинам для тысячи, десяти тысяч и ста тысяч корзин с профилем слоёв, очередь из десяти серверов на настоящих размерах файлов и ту же очередь со старой доской. Функция queue одна на всё: доска в ней есть всегда, а «свежие сведения» — это доска, которую переписывают перед каждым запросом. Число незаконченных заданий сервер узнаёт лениво: из очереди моментов окончания выбрасываются прошедшие только тогда, когда о сервере спрашивают.

Сколько это стоит

Решение стоит d вопросов о нагрузке и d − 1 сравнения — константа, сколько бы ни было серверов. Опрос всех стоит n вопросов; на одной машине со счётчиками в памяти это дёшево, но между машинами каждый вопрос — сообщение по сети, а сведения о сотне серверов успевают устареть раньше, чем их соберёшь. Случайный выбор и «по кругу» не спрашивают ничего.

Памяти правило двух не требует сверх того, что балансировщик и так хранит: счётчика активных соединений на сервер. Время листинга почти целиком уходит на моделирование; само решение — два вызова генератора и одно сравнение.

Тонкости

• Два разных. В листинге оба кандидата выбираются независимо и могут совпасть; при десяти серверах это каждый десятый запрос, и тогда он фактически уходит случайному серверу. Можно брать двух разных, но выигрыш невелик: в нашей очереди на восьми прогонах с разными зёрнами среднее время ответа стало лучше примерно на 2 %.
• Равенство. Если у обоих поровну, всё равно, кого брать, лишь бы не всегда одного и того же по номеру: правило «при равенстве — сервер с меньшим номером» чаще нагружает первые серверы (так поступает «самый свободный» в листинге). Брать первого из случайной пары, как делает в листинге лучший из двух, честно — пара и так случайна.
• Разные серверы. Если один сервер вдвое мощнее другого, сравнивают не число соединений, а число соединений, делённое на вес. nginx в режиме random учитывает веса уже при выборе кандидатов.
• Что считать нагрузкой. Число активных соединений дёшево, но не видит размера работы — отсюда двукратный, а не четырёхкратный выигрыш в нашем опыте. Linkerd и Envoy умеют сравнивать пару по сглаженному времени ответа с поправкой на очередь (peak EWMA). Осторожно с сервером, который быстро отвечает ошибками: по времени ответа он выглядит лучшим.
• Холодный старт. Только что включённый сервер пуст, и правило двух будет выбирать его в каждой паре, где он оказался. Это нормально — он и правда свободен, — но если серверу нужен прогрев (кеши, JIT), нагрузку на него наращивают постепенно.

Где работает

Балансировщики. В nginx с версии 1.15.1 есть директива random two least_conn: два случайных сервера с учётом весов, из них тот, у кого меньше активных соединений. В HAProxy — balance random с числом попыток, по умолчанию двумя; в описании изменения прямо сказано, что это сила двух случайных выборов, и что с ростом числа попыток поведение медленно приближается к leastconn. В Envoy и gRPC политика LEAST_REQUEST при равных весах берёт два случайных хоста (параметр choice_count, по умолчанию 2) и выбирает тот, где меньше незавершённых запросов. Linkerd первой версии выбирал так по умолчанию.

Хеш-таблицы. Если у каждого ключа две ячейки и ключ кладут в менее заполненную корзину, самая длинная цепочка падает до ln ln n / ln 2. Хеширование кукушки идёт дальше: в ячейке один ключ, а уже положенные ключи можно перекладывать в их вторую ячейку. Оно работает, пока ключей заметно меньше половины ячеек; за этой границей граф «ячейки — вершины, ключи — рёбра» почти наверняка получает компоненту, где рёбер больше, чем вершин, и разложить ключи становится невозможно. Это вторая задача ниже.

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

История

Йосси Азар, Андрей Бродер, Анна Карлин и Эли Упфаль доказали теорему о шарах и корзинах в статье «Balanced Allocations» в 1994 году; журнальная версия вышла в 1999-м. В 1996 году Майкл Митценмахер в диссертации «The Power of Two Choices in Randomized Load Balancing» перенёс идею на очереди, а Никита Введенская, Роланд Добрушин и Фридрих Карпелевич независимо получили тот же ответ для очереди с выбором кратчайшей из двух. В 1999 году Бертольд Фёккинг показал, что несимметричное правило «при равенстве — налево» ещё лучше. Азар, Бродер, Карлин, Митценмахер и Упфаль получили премию ACM Paris Kanellakis за 2020 год «за открытие и анализ сбалансированного распределения, известного как сила двух выборов, и его многочисленные применения на практике».

Задачи