TLDR Сила метода “Двух случайных выборов”

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

Можно оптимизировать затраты используя метод «Двух случайных выборов»:

1. Выбираем два любых узла
2. Узнаем их загруженность, а не загруженность всех узлов — вот где экономия.
3. Выбираем наименее загруженный из двух

В оригинальной статье доказано, что на практике этот метод является оптимальным.

Другие примеры использования этого метода:

1. При хэшировании – равномерное распределение элементов между списками содержащими коллизии
2. Равномерное использование распределенной памяти
3. Избегание перегрузок сети при маршрутизации в виртуальных сетях