Какие алгоритмы балансировки подходят для распределенных систем без синхронизации

Что проверяют

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

Как отвечать

Разделите алгоритмы по тому, какое состояние им нужно:

• Random: не нужно ничего, каждый экземпляр решает сам. На малом потоке бывают перекосы;
• локальный Round Robin: у каждого экземпляра свой счётчик, в Go это atomic.Uint64. Стартовую позицию выбирают случайно, иначе после одновременного рестарта все экземпляры бьют в первый бэкенд;
• Power of Two Choices: берёте два случайных бэкенда и отправляете запрос туда, где меньше запросов в полёте по вашим же данным. Устаревшие данные ему почти не вредят, а перекос намного меньше, чем у Random. Так устроен least request в Envoy, похожая схема с EWMA задержек у Linkerd;
• консистентное хеширование: ring hash, rendezvous (HRW), jump consistent hash, Maglev. Маршрут определяется только списком узлов, поэтому экземпляры с одинаковым списком придут к одному решению без переговоров. При изменении состава переезжает примерно 1/N ключей, а не почти все, как у hash % N;
• взвешенные варианты: веса приходят из конфигурации или service discovery и тоже не требуют синхронизации.

Важная оговорка: координация не исчезает совсем, узлам нужно согласие о составе бэкендов. Его дают Consul, etcd, DNS или EndpointSlice в Kubernetes с конечной согласованностью, и алгоритм должен переживать моменты, когда списки у экземпляров немного разошлись.

Где спотыкаются

Называют Least Connections универсальным ответом, не замечая, что ему нужен общий счётчик: у десяти независимых балансировщиков десять разных картин нагрузки.

Предлагают hash(key) % N для привязки ключей и не видят, что добавление одного узла перетасует почти все ключи и обнулит кеши.

Забывают про согласованность списка узлов. При разных версиях списка два экземпляра отправят один ключ на разные серверы, и консистентное хеширование само это не исправит.