Балансировка: почему случайный выбор двух бьёт круговой перебор

Что здесь на самом деле спрашивают

Лестница выглядит так:

1. «Какие способы балансировки вы знаете?» — разминка на перечисление.
2. «Чем плох круговой перебор?» — здесь начинается содержание, и обычный ответ «ничем, он же равномерный» уже неверен.
3. «Что такое least-connections и почему его не всегда используют?» — вопрос про цену знания.
4. «Что такое power of two choices?» — вопрос, ради которого тема и существует.
5. «Почему на нашем нагрузочном тесте разницы не было?» — вопрос-ловушка про однородные запросы.
6. «Где балансировка не поможет вовсе?» — вопрос про границы.

Этот урок стоит на модели, а не на замере: у правил балансировки нет общего стандарта — есть документация отдельных продуктов. Модель отвечает не на вопрос «сколько миллисекунд у вас», а на вопрос «от чего зависит разница».

База: кто выбирает сервер и по какому правилу

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

Правил, по которым принимается это решение, обычно называют три, и все три объясняются обычными словами.

1. По кругу. Первый запрос — первому серверу, второй — второму, и так далее по списку; дойдя до конца, начинаем сначала. Знать о серверах для этого не нужно ничего — достаточно помнить, кому отдали прошлый запрос.
2. Случайно. На каждом запросе бросаем монетку. Здесь не нужно даже помнить прошлый выбор.
3. Наименее загруженному. Смотрим на серверы и отдаём запрос тому, кто сейчас свободнее прочих. Из трёх правил только этому нужно знание о состоянии серверов.

Третье звучит правильнее всех — и в нём же прячется первая трудность: что значит «наименее загруженный»? У этой фразы нет одного значения. Загруженность меряют числом запросов, которые сервер сейчас обрабатывает; числом открытых соединений; длиной очереди перед ним; сглаженной задержкой ответа; загрузкой процессора. Это разные величины, и правило, выбирающее по одной из них, — это уже другое правило, чем правило, выбирающее по другой.

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

И вот главный вопрос урока: если первое правило раздаёт всем поровну, чем оно плохо? Ответ короткий: поровну — по числу запросов, а не по работе. Пока запросы одинаковы по стоимости, разницы между этими двумя «поровну» нет; как только один запрос дороже другого, сервер, которому достался дорогой, занят надолго — а очередь к нему всё равно приходит в свой черёд, потому что правило о его занятости не знает.

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

Механизм 1: поровну по числу — не поровну по работе

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

Проблема в том, что запросы не одинаковы. Вот что получается, когда 90 % из них стоят 10 мс, а остальные 10 % — 100 мс:

1. THE SAME REQUESTS, FOUR RULES: TIME SPENT WAITING IN A QUEUE
---------------------------------------------------------------
           rule   mean, ms   p50, ms   p99, ms   worst, ms
    round-robin      110.3      69.6     582.4      1041.2
         random      161.2     101.8     787.7      1504.8
     least-work        4.9       0.0      42.9        90.6
    two-choices       24.7      10.7     123.6       287.2

Одни и те же запросы, одни и те же серверы. Отличается только правило — и хвост двигается в разы, а не на проценты.

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

И почему случайный выбор ещё хуже — 787,7 против 582,4. Случайность не гарантирует равномерности на коротком отрезке: какой-то сервер получит подряд несколько длинных запросов просто потому, что монетка так легла. Круговой перебор от этого хотя бы защищён.

Обратите внимание на колонку p50 в строке least-work: ноль. При загрузке 0,85 и шестнадцати серверах свободный обычно есть — и правило, которое умеет его найти, находит. Остальные три его не ищут: два не смотрят на серверы вовсе, а опрос двух ищет свободного среди двух случайных.

И сразу про имя. В модели least-work выбирает сервер, который освободится раньше всех, — то есть по точному остатку работы вместе с длительностью уже идущего запроса. Настоящий least-connections считает соединения и не отличает соединение с десятимиллисекундным запросом от соединения со стомиллисекундным — то есть слеп ровно к тому разбросу, на котором всё здесь и держится. Поэтому 42,9 мс — потолок правила, которому известно всё, а не результат least-connections.

Механизм 2: цена знания

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

2. HOW MUCH EACH RULE NEEDS TO KNOW
-----------------------------------
           rule   servers inspected   p99, ms   p99 improvement
    round-robin                   0     582.4              1.0x
         random                   0     787.7              0.7x
     least-work                  16      42.9             13.6x
    two-choices                   2     123.6              4.7x

Читать надо две колонки рядом. Первые два правила не знают о серверах ничего и работают хуже всех. least-work знает про всех шестнадцать и работает лучше всех. А two-choices знает про двух — и забирает заметную часть выигрыша.

Почему выбор двух работает. Из двух правило берёт того, кто освободится раньше, поэтому запрос ждёт столько, сколько заставил бы ждать менее загруженный из двух. Долго — только если загружены оба. Это следствие самого правила, а не отдельный замер: вероятностей модель не считает.

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

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

Отсюда и правило, которым стоит отвечать: опрос двух — это не «почти least-connections», а другой размен. Он меняет часть выигрыша на то, что стоимость решения перестаёт зависеть от размера системы.

Механизм 3: почему на нагрузочном тесте разницы не видно

Третий уровень объясняет, откуда у кругового перебора репутация. Уберём из модели одну вещь — разброс времени обслуживания:

3. WITH UNIFORM REQUESTS, ROUND-ROBIN TIES WITH THE BEST RULE
-------------------------------------------------------------
  round-robin: p99 with even service, ms       16.1
  random: p99 with even service, ms            272.7
  least-work: p99 with even service, ms        16.1
  two-choices: p99 with even service, ms       42.3

Круговой перебор дал ровно то же, что и опрос всех шестнадцати: 16,1 против 16,1. И это не совпадение: когда каждый запрос стоит одинаково, «взять того, кто освободится раньше» — это и есть обход по кругу. Серверы освобождаются в том порядке, в каком получали работу, поэтому least-work раз за разом указывает на тот сервер, до которого очередь дошла бы и так.

А случайный выбор остался плохим — 272,7. Ему разброс запросов не нужен, чтобы промахиваться: он промахивается сам по себе.

И обратите внимание на опрос двух: 42,3 — хуже кругового перебора. Две случайные попытки не дают того, что даёт гарантированный обход, когда выбирать не из чего.

Отсюда граница, от которой и надо формулировать правило. Опрос двух случайных серверов выигрывает не «вообще», а там, где текущая загрузка серверов несёт полезную информацию, — то есть там, где серверы в момент решения действительно заняты по-разному. Уберите разброс времени обслуживания — и сообщать становится нечего: правило, сравнивающее двух наугад, проигрывает правилу, которое просто обходит всех по очереди, а само знание о состоянии всех не даёт ничего сверх обхода. Это и есть третий блок целиком: 42,3 у опроса двух против 16,1 у кругового перебора и ровно тех же 16,1 у опроса всех. Верное утверждение звучит поэтому не «выбор двух лучше кругового перебора», а «выбор двух лучше там, где загрузка серверов различается».

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

Настоящая же нагрузка почти никогда не однородна: запрос за одной записью и запрос за отчётом за год идут в один и тот же обработчик.

Глубже: чего в модели нет

Последний уровень — про границы самой модели, и назвать их стоит самому.

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

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

Ни отказов, ни повторов. Сервер в модели не падает, а клиент не повторяет. Оба добавляют нагрузку именно тогда, когда она и так велика; про это отдельный урок про повторы и джиттер.

Нет цены самой балансировки. Опрос двух серверов в модели бесплатен. В настоящей системе состояние надо откуда-то знать, и у этого знания есть задержка: балансировщик действует по данным, которые уже устарели.

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

Как отвечать на собеседовании

Короткий ответ: круговой перебор раздаёт поровну число запросов, а не работу, поэтому он проигрывает, как только запросы неоднородны. Опрос двух случайных серверов забирает заметную часть выигрыша полного опроса, но его цена не растёт с размером парка. Модель: p99 ожидания 582,4 мс у кругового перебора, 123,6 у опроса двух и 42,9 у опроса всех.

Этого достаточно, чтобы ответить верно. Дальше — то, что добавляют, если собеседник копает.

Если интервьюер копает глубже

Хороший ответ отличают три вещи. Первая — вы говорите, что различие правил проявляется только на неоднородной нагрузке, и приводите свой же контрпример: при одинаковых запросах круговой перебор сравнялся с лучшим правилом, а опрос двух ему проиграл — 42,3 против 16,1. Вторая — вы называете цену полного опроса не «сложностью», а конкретно: надо знать состояние всех, это знание растёт с парком и устаревает, пока его собирают, а least-connections вдобавок считает соединения, а не работу — и стоит сразу сказать, что «наименее загруженный» вообще меряют по-разному: числом запросов в работе, числом соединений, длиной очереди, сглаженной задержкой, загрузкой процессора. Третья — вы упоминаете, что случайный выбор хуже кругового перебора, а не лучше: это проверка на то, думали вы или пересказываете.

Чего говорить не стоит: «мы поставили least-connections, стало лучше на столько-то процентов». Без описания разброса запросов это число ничего не значит — на однородной нагрузке его бы не было вовсе.

Дальше спросят

Частые заблуждения

Практика

Две задачи. Сначала ответьте, потом сверьтесь с настоящим выводом: в обеих правильный ответ печатает сам скрипт модели.

print(inspected["round-robin"])
print(inspected["least-work"])
print(inspected["two-choices"])

0
16
2

1
16
2

0
1
2

16
16
2

Проверка знаний