Про яйца и балансировщик нагрузки

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

Постоянно опрашивать сервера, это хуйня, информация будет не актуальной, все это медленно, пока мы собирали данные, ситуация уже поменялась.

На этом фоне возникает эффект «стада», когда много запросов дружно бегут туда, где вроде бы свободно и по итогу перегружают сервер еще больше.

Это можно решить проще — например перенаправлять запросы случайно.

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

Какой-то замкнутый круг, печаль и говнище.

А чё делать?

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

Вроде мелочь, но работает этот подход прям заебись! И что интересно у этого подхода есть официальная формулировка — Power of Two Choices или «Сила двух выборов».

Почему это заебись?

На просторах есть задачка «яйца и корзины», в оригинале там конечно не «яйца», а шары.

Короче. Мы случайно кидаем яйца в корзины. Если класть каждое яйцо в случайную корзину, то в итоге некоторые корзины будут переполнены.

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

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

Все просто! Тоже самое и с серверами:

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

Давай на котиках:

Представь, что у тебя есть куча серверов, и на четверти из них пришло по 4 запроса.

• Если я выбираю сервер случайно, есть 25% шанс попасть именно на сервер, которому уже пезда.
• Если я выбираю два сервера и беру менее загруженный — вероятность того, что оба окажутся с нагрузкой 4, уже всего 6,25% (1/16).

Получается, что вероятность перегрузки падает очень быстро. А дальше — ещё быстрее: чтобы нагрузка выросла до 5, 6 и так далее, нужно каждый раз «удачно» попасть в редкие перегруженные сервера, и шанс становится ничтожным.

Видишь, математика нужна не только бекендерам, но и в девопсе можно применить.

Что получаем на практике:

На практике балансировка «выбором из двух» делает распределение нагрузки по серверам почти равномерной. При этом мы не тратим кучу ресурсов на мониторинг и не пытаемся каждый раз точно узнать состояние всех серверов.

Такой подход - простой и элегантный. Как говорится — без хуйни!

Формулы и расчеты визуально можешь глянуть тут. Там как раз разбирается способ с яйцами, но уже с углубленной математикой и формулами.

Этот же принцип используют, например, в cuckoo hashing (структура данных для хранения ключей).

Cuckoo hashing (кукушкино хеширование) — алгоритм разрешения коллизий значений хеш-функций в таблице с постоянным временем выборки в худшем случае.

Как реализовать в nginx

upstream backend {
    random two; # Power of 2 Choices
    server app1.bashdays.ru;
    server app2.bashdays.ru;
    server app3.bashdays.ru;
}

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

Этот же принцип используют, например, в cuckoo hashing (структура данных для хранения ключей).

Мотай на ус, глядишь сгодится в хозяйстве.

Комментарии