Load balancing
Допустим, у вас есть 1000 серверов и много пользователей, которые суммарно посылают 1M запросов в секунду. Будем считать, что все сервера одинаковые и можно отправлять запрос на любой сервер. Как определить, куда посылать очередной запрос, чтобы максимально нагруженный сервер обрабатывал как можно меньше запросов?
Если все запросы проходят через одну прокси, то тут все просто — посчитаем сколько запросов сделали к каждому серверу и пошлем в тот, который менее всего нагружен. Так каждый сервер получит ровно по 1000 запросов. Но чаще всего мы не можем позволить себе одну центральную прокси, поэтому решения нужно принимать распределенно.
Можно посылать запрос в случайный из 1000 серверов. Как посчитать максимальную нагрузку в таком случае? Можно выписать какие-то формулы на бумажке, но здесь олимпиада по программированию, а можно написать три строки на Python, которые проэмулируют этот процесс 100 раз, и мы узнаем, что с 99% вероятностью максимальное количество запросов будет не больше 1156. По сути это обозначает, что нам нужно будет использовать на 16% больше серверов, чем если бы мы умели распределять нагрузку идеально.
Допустим, мы хотим научиться добавлять и удалять сервера "на лету". Тогда для определения сервера можно использовать https://en.wikipedia.org/wiki/Consistent_hashing#:~:text=Incomputerscience,consistenthashing,isthenumberofslots.. Он работает так. Сопоставим каждому серверу случайное число от 0 до 1. Когда хотим отправить запрос, тоже сгенерируем случайное число, а потом найдем сервер с самым близким числом к данному, и отправим в него. Идея в том, что, если удалить какой-то один сервер, то большинство запросов все еще нужно будет посылать в тот же сервер, что и раньше.
Если проэмулировать ровно этот алгоритм (даже 1 раз, а не 100 как раньше), то окажется, что самый нагруженный сервер получит >8000 запросов. Это в 8 раз больше чем средний! Что совсем не позволительно.
Чтобы починить эту проблему применяется следующий трюк. Давайте для каждого сервера сгенерируем не одно число, а сто. Тогда симуляция показывает, что максимально нагруженный сервер получит 1363 запроса. Что гораздо лучше чем 8К, но все еще обозначает, что нам нужно будет на 36% больше серверов.
Вообще, когда я начинал писать этот пост, он был про алгоритм, который позволяет сделать так, чтобы максимально нагруженный сервер обработал ~1007 запросов. Но пост и так получился длинный, так что пишите в комментариях, как бы вы улучшили алгоритм.
