В мире динамического выделения ресурсов и балансировки нагрузки есть много интересных алгоритмов, но один из самых известных и занимательных – так называемый «метод двух случайных выборов». Он привносит очень простое изменение в процедуру случайного выделения ресурсов, а качество результатов от этого улучшается экспоненциально. Мне посчастливилось реализовать именно эту технику в гигантском масштабе, чтобы оптимизировать использование ресурсов в AWS Lambda, но мне всё равно долго не удавалось «прочувствовать» этот метод интуитивно. В этом посте хочу познакомить вас с той метафорической картиной этого алгоритма, которую я для себя составил, и которая очень удобна для понимания других продвинутых техник в этой области.

Что такое балансировка нагрузки?

Допустим, вы пишете крупермасштабный сервис, в котором используются боты с искусственным интеллектом; сервис похож на ChatGPT. У вас тысячи серверов с дорогими графическими процессорами, генерирующими текст на основе пользовательских подсказок. В таком случае, если ваш алгоритм маршрутизирует примерно 80% входящих запросов всего на 20% серверов, то, вероятно, эти серверы будут сильно загружены, а попадающим на них запросам придётся подолгу стоять в очереди, прежде, чем попасть на GPU. С другой стороны, 80% недозагруженных серверов используются неоптимально и впустую тратят множество драгоценных часов работы GPU. Именно так и выглядит плохая балансировка нагрузки.

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

Метод двух случайных выборов – в чём его сила

Вот как можно упрощённо представить балансировку нагрузку. На вас бесконечным потоком валятся шарики (это запросы), и у вас есть N вёдер (это серверы). Ваша задача – определить каждый из входящих шариков в одно из вёдер, так, чтобы все вёдра по возможности заполнялись шариками как можно равномернее. Реалистичные проблемы гораздо сложнее этой, но пока нам хватит и этой упрощённой модели.

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

Другой подход – выбираете случайным образом не одно ведро, а два, и кладёте шарик в то, где сейчас шариков меньше. Это и есть «метод двух случайных выборов». Коротко его можно назвать «лучшее из двух».

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


Размещение по случайному принципу даёт широкое распределение, при котором количество шариков в ведре варьируется от 900 до 1200, тогда как размещение по методу двух случайных выборов обеспечивает значительно более плотное распределение между 995 и 1002.

Что не так с простым случайным распределением?

Вероятно, в курсе математики вам доводилось слышать о центральной предельной теореме (ЦПТ). Она имеет фундаментальное значение для статистики и в целом постулирует, что сумма достаточно большого количества случайных величин, имеющих примерно одинаковые масштабы, имеет распределение, близкое к нормальному.

Давайте попытаемся получше понять её (интуитивно). У вас 10 вёдер, и все они сначала пусты. Вы берёте первый шарик, бросаете десятигранную кость и получаете 1. Итак, в ведре №1 теперь 1 шарик, а остальные пусты. Теперь нужно определить, куда положить второй шарик. Вновь бросаете кость. Поскольку второй бросок кости совершенного не зависит от первого и не обладает какой-либо «памятью», все исходы остаются равновероятными, пусть даже вёдра теперь заполнены несбалансированно.

Теперь, чтобы не усугублять проблему с ведром №1, куда может попасть второй шарик, пока остальные несколько вёдер будут пустовать, мы исключаем вариант «1», не допуская его при следующих 9 бросках кости. Вероятность случая (9/10)⁹ составляет всего 39%, поэтому, скорее всего, мы выбросили бы единицу за следующие 9 попыток, и ситуация стала бы ещё более разбалансированной.

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

Посмотрим на это с другой стороны: историю попадания шариков в каждое ведро можно представить как список «X»-ов, где каждый шар из потока помещается в ведро номер «X». Разница между следующими друг за другом «X»-ами в этом списке может быть менее 10, более 10 или ровно 10. В результате длина списка может быть менее 10, более 10 или ровно 10. Правда, поскольку мы разложили всего 10 шариков, область «менее 10» будет равна области «более 10» — то есть, мы получим значение «10» с симметричным распределением вокруг него. Такой паттерн попаданий – это хорошо известное распределение, называемое «геометрическим».


График на рис. 2 представляет в форме геометрического распределения множество данных из нашего предыдущего примера, где 1000 шариков раскладывались в 10 вёдер. У геометрического распределения есть длинная хвостовая часть – то есть, более высока вероятность попасть в диапазон [0, среднее], но далее к хвосту значения получаются гораздо выше среднего, правда, встречаются всё с меньшей вероятностью. Среднее в данном случае равно 1000, но нам потребуется целых 8000 попыток, прежде, чем этот результат выпадет нам повторно!

Хорошие и плохие варианты размещения

Прежде, чем перейти к оптимизации, давайте попытаемся определить целевую функцию для хороших вариантов размещения. На практике сделать это невероятно сложно, но в нашем игрушечном примере – достаточно легко. Начнём с N вёдер, в которые собираемся разложить M шариков. Определим число шариков в n-ном ведре как Sn. Глобально мы определим Smin и Smax как число шаров в наиболее пустом и наиболее заполненном ведре соответственно.

Исходно Sn для всех вёдер равно 0. Следовательно, Smin и Smax также равны 0. Как только мы положим шарик в любое ведро, скажем, в ведро #1, S1 станет равно 1, Smin останется равно 0, а Smax будет 1. Теперь при оптимальном размещении наше Smax никогда не должно превосходить Smin + 1. Например, если n = 10, S1 = 1 и от S2 до S10 все равны 0, нет никаких причин делать S1 = 2 прежде, чем положить шарики в 9 пока пустующих вёдер. Только когда Smin = 1 (это произойдёт, когда в каждом ведре окажется минимум по 1 шару) оптимальный алгоритм поднимет Smax до 2. Следовательно, Smax — Smin > 1 – признак плохого размещения. Эту ситуацию можно визуализировать как несколько концентрических кругов или орбит. Smin находится в центре, а Smax увеличивается на 1 от орбиты к орбите. Чем дальше находится ваша орбита, тем хуже вы разместили образцы.


Иными словами, хорошее размещение гарантирует любой алгоритм, серьёзно мешающий Smax отдалиться на несколько орбит от Smin.

Анализ размещения по принципу «лучшее из двух»

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

Вернёмся к рассмотренному ранее примеру с 10 пустыми вёдрами. Сначала мы кладём шарик в ведро №1 и, следовательно, оказываемся на орбите 1. При случайном подходе к размещению есть 10% вероятность попасть на орбиту 2 (т.e., снова выбрать ведро “1” ). Когда вы окажетесь на орбите 2, у вас останется всё тот же 10%-й шанс попасть на орбиту 3. В принципе, при случайном размещении мы можем ухудшить расположение шариков в вёдрах на 1 с вероятностью 1/n.

Теперь давайте проанализируем наилучший из двух вариантов – когда всего 1 ведро непустое, такой алгоритм вообще не позволяет дойти до орбиты 2, поэтому давайте предположим, что второй шар оказался в ведре “2”. Вот какова теперь вероятность подняться до орбиты 2:
1. Нам придётся первым ходом выбрать одно из двух непустых вёдер, вероятность 2/10.
2. Вторым ходом придётся выбрать второе непустое ведро, вероятность 1/9.

Скомбинировав два этих подхода, получим вероятность 1/45 или примерно 0,02 против 0,1, достигаемых при размещении по случайному принципу. Это хорошо, но меня пока не впечатляет, так что давайте подумаем, как дойти до орбиты 3.

Чтобы попасть на орбиту 2, пользуясь случайным размещением, то понадобится попасть в ведро “1” для прохождения на орбиту 2 и ещё раз в то же ведро, чтобы попасть на орбиту 3. Поэтому вероятность пройти кратчайшим путём к орбите 3 составляет 0,01.

Если использовать алгоритм с выбором двух наилучших вариантов, давайте, опять же, начнём с вёдер “1” и “2”, в каждом из которых лежит по 1 шарику. Следующие события иллюстрируют скорейший путь к орбите 3:
1. Выбрать одно из непустых вёдер: 2/10
2. Выбрать второе: 1/9 — точно как и ранее мы остались на орбите 2.
3. На следующем шаге мы получаем возможность перейти на орбиту 2: 1/10
4. Затем мы попадаем в единственное ведро с первой орбиты: 1/9 — в результате оба ведра оказываются на орбите 2.
5. Теперь, опять же, попадаем в оба этих ведра: 2/10 * 1/9 — в результате одно из вёдер переходит на орбиту 3.

Если перемножить все эти вероятности, то получим 0,0000054 против 0,01. Теперь просматривается тот лабиринт, о котором я говорил выше. Обратите внимание: это вероятность пойти по кратчайшему пути, но могут быть и другие пути. Они длиннее, но вероятность попасть на них и пойти по ним – выше. Думаю, идею вы уловили.

Я бы хотел продолжить этот пример и показать вам вероятности пройти на орбиты 4, 5 и т.д., но мне для этого не хватает математической подготовки. Я просто программист. Если вы, как и я, оцениваете свои навыки программирования гораздо выше, чем математические, то, вероятно, подружитесь с симуляциями метода Монте-Карло. Симуляция Монте-Карло позволяет не решать задачу математически, а много-много раз прогнать задачу на компьютере, закладывая в неё случайный ввод. Благодаря закону больших чисел, при наличии достаточно большой выборки вы получите результаты, достаточно близкие для истинно математических, достаточные для доказательства вашей точки зрения.

В данном случае мы не имеем дело с вероятностями, а проводим 10 000 экспериментов и смотрим, сколько в среднем размещений требуется, чтобы попасть на орбиту 2, 3…11 с любым из алгоритмов.


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

Чтобы можно было сравнить два паттерна роста, давайте нанесём вариант с выбором двух лучших на логарифмической шкале, а размещение случайным образом давайте оставим на линейной шкале.

Заключение

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