Балансировка нагрузки: кто выбирает сервер и что он в этот момент знает

Коротко: кто и когда выбирает сервер

Представьте супермаркет с шестнадцатью кассами. Запрос — это покупатель, бэкенд — касса. Вся балансировка сводится к одному вопросу: кто говорит покупателю, в какую кассу встать, и что этот кто-то видит в момент совета.

Дальше всё различие — в том, насколько рано даётся совет.

DNS: совет у входа в торговый центр

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

Это проверено на живых доменах. www.google.com отдаёт восемь адресов и каждый раз перемешивает порядок — выбор оставлен клиенту. github.com отдаёт по одному адресу, но каждый раз другой — выбор сделал сервер имён.

Главная ловушка: DNS раскладывает не запросы, а обращения за адресом. Браузер спросил адрес один раз, открыл соединение и отправил по нему тысячу запросов — все они ушли на один сервер. Поэтому DNS хорошо разводит трафик по городам и плохо выравнивает нагрузку между машинами.

Отдельно про geoDNS — «отвечать разными адресами в разных странах». Он бывает настоящий и мнимый, и это видно по одному полю в ответе. Настоящий помечает ответ как «годится только для этой части интернета»; мнимый отвечает всем одинаково. Проверены четыре сайта: у CloudFront адреса действительно разные для США, Германии, Японии и Бразилии; у Bing, Microsoft и Netflix — одинаковые для всех. У последних география тоже есть, просто сделана она не через DNS.

L4 и L7: распорядитель у входа и администратор зала

L4 смотрит только на «откуда и куда» — адреса и порты. Он направляет покупателя один раз, при входе, и дальше не вмешивается. Быстро: одна обычная машина заполняет канал в 10 гигабит.

L7 читает сам запрос: что просят, какие заголовки, какая кука. Он может направлять по-разному разные запросы одного и того же клиента и повторить неудачный запрос на другой кассе.

Разница, из-за которой чаще всего ошибаются: L4 распределяет соединения, а L7 — запросы. Если один клиент открыл одно соединение и шлёт по нему девяносто процентов всего трафика, L4 честно отправит это соединение на одну кассу — и она встанет, пока остальные пятнадцать пустуют. Поэтому обычно ставят оба: L4 впереди, чтобы раскидать соединения, L7 позади, чтобы раскладывать запросы.

Алгоритмы: чем советчик руководствуется

Для сравнения построена модель: шестнадцать касс, каждая обслуживает по одному человеку, остальные ждут в очереди. Ниже — сколько всего тратят самые невезучие (один из ста): ожидание в очереди плюс само обслуживание, в условных единицах. Меньше — лучше.

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

Когда «где меньше людей» перестаёт работать

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

Проверено и это. Пока табло обновляется мгновенно, «где меньше людей» выигрывает у всех: 6,06. Когда табло отстаёт на время двух покупок, тот же совет даёт 19,95 — хуже, чем тупое «по кругу» (17,00). Причина понятная: все советчики видят одно и то же устаревшее число, показывают на одну и ту же кассу и создают там толпу.

А совет «посмотри на две случайные, иди в ту, где короче» за то же время ухудшается всего с 8,86 до 10,52. Он не пытается найти лучшую кассу — и потому ему нечего терять, когда данные врут.

Отсюда простое правило:

• Советчик один и сам всё видит → «где меньше людей».
• Советчиков много, но каждый считает только своих → «где меньше людей» по-прежнему годится.
• Данные приходят со стороны и запаздывают → «лучшая из двух случайных».
• Данных нет вовсе → «по кругу», но тогда за настройками придётся следить руками.

Закреплённые сессии: за что платим

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

В той же модели без закрепления самые невезучие ждали 6,06. С пятью тысячами закреплённых групп — 26,90. С пятьюстами — 206,92. С пятьюдесятью — восемь тысяч, то есть балансировки просто нет.

Вывод не в том, что закрепление плохое, а в том, что это плата за состояние на сервере. Если корзину можно хранить в общем месте, платить не нужно вовсе.

Зачем это знать

Балансировщик выглядит инфраструктурой, которую настраивают один раз. Это верно ровно до первого инцидента, в котором «нагрузка распределена равномерно», а хвост задержек утроился, — и оказывается, что равномерно распределены запросы, а не работа.

Разбор ниже устроен по одной оси: в какой момент принимается решение и что в этот момент известно. Она объясняет и то, зачем нужны сразу несколько слоёв балансировки, и то, почему алгоритмы нельзя сравнивать в отрыве от того, откуда балансировщик берёт данные.

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

Клиентская и серверная балансировка

Разделение проходит по тому, у кого лежит список бэкендов.

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

При клиентской балансировке список получает сам клиент — из service discovery, из xDS, из SRV-записей — и выбирает сервер сам. Лишнего сетевого перехода нет, отказ одного клиента не задевает остальных. Цена — в том, что логика балансировки размазана по всем клиентам сразу: чтобы поменять алгоритм, нужно выкатить их все. Отсюда и sidecar-прокси: список и алгоритм остаются рядом с клиентом, но обновляются отдельно от него.

Есть и третий случай, который клиентской балансировкой обычно не называют, а это она и есть. Когда DNS возвращает несколько адресов, выбор делает клиент.

DNS: выбор за минуты до запроса

DNS-балансировка — самый ранний и самый слепой слой. Замер на живых доменах, двадцать запросов подряд к каждому:

Видно две разные стратегии. Google отдаёт весь список и перемешивает порядок — решение оставлено клиенту. GitHub отдаёт по одному адресу, но разный: решение принято сервером имён, клиенту выбирать не из чего.

Оба приёма старше многих читателей. RFC 1794 описал их в апреле 1995 года и там же назвал ограничение, которое никуда не делось:

the DNS protocol doesn't guarantee ordering

перевод

протокол DNS не гарантирует порядок

Порядок записей — это рекомендация, а не обязательство. Резолвер провайдера, библиотека в языке и операционная система вправе его переставить, и переставляют. А главное ограничение в том же документе сформулировано ещё прямее:

There is no use in handing out information with TTLs of an hour, when the conditions for ordering the RRs changes minutely.

перевод

Нет смысла раздавать сведения с часовым TTL, когда условия, определяющие порядок записей, меняются ежеминутно.

Здесь всё противоречие DNS-балансировки. Чтобы решение было свежим, TTL должен быть маленьким. Чтобы кеширование работало, он должен быть большим. И даже маленький TTL не спасает: никто не обязан его соблюдать — ни резолвер провайдера, ни браузер с собственным кешем, ни соединение, которое уже установлено и живёт часами.

Последнее стоит проговорить отдельно, потому что оно ломает интуицию. DNS-балансировка распределяет не запросы, а обращения за адресом. Клиент, который открыл HTTP/2-соединение и держит его открытым, обратился за адресом один раз на тысячу запросов. Балансировка по DNS в этом случае разложила по серверам не нагрузку, а моменты установки соединений.

geoDNS: и как проверить, настоящий ли он

Идея geoDNS проста: отвечать разными адресами в зависимости от того, откуда пришёл вопрос. Сложность в том, что авторитетный сервер видит адрес не клиента, а резолвера — и если человек в Токио пользуется публичным резолвером в США, географическая близость определяется неправильно.

Для этого и придуман RFC 7871: резолвер добавляет к запросу кусок адреса клиента. Ответ содержит SCOPE PREFIX-LENGTH — the leftmost number of significant bits of ADDRESS that the response covers (число старших значащих бит адреса, которые покрывает ответ). Ноль означает, что ответ подходит всем.

Значит, настоящий geoDNS отличается от ненастоящего одним наблюдаемым полем. Проверка: один и тот же вопрос с подстановкой четырёх разных клиентских подсетей.

CloudFront отвечает четырьмя разными наборами адресов и честно помечает ответ /24: «этот ответ годится только для этой подсети». Остальные три отвечают одинаково и ставят /0.

Из этого не следует, что Bing и Netflix не умеют в географию. Следует ровно одно: они не используют для этого EDNS Client Subnet. Anycast решает ту же задачу на уровне маршрутизации, и тогда одному адресу соответствуют разные машины в разных точках мира — а DNS-ответ действительно один на всех.

Стоит помнить и то, что сам RFC 7871 относится к своему механизму без энтузиазма: он рекомендует выключать его по умолчанию и усекать адрес до /24, потому что иначе запрос к DNS начинает рассказывать о местоположении пользователя больше, чем нужно.

L4 и L7: сколько балансировщик видит и сколько за это платит

Оба слоя стоят между клиентом и бэкендом, но смотрят на разное.

L4 работает с транспортом: адрес, порт, флаги. Он не разбирает HTTP-запрос — часто и не может, потому что тот зашифрован. Решение принимается один раз, при установке соединения, и все последующие пакеты идут по уже выбранному пути. Отсюда и производительность: Maglev, балансировщик Google, is able to saturate a 10Gbps link with small packets (способен насытить канал 10 Гбит/с мелкими пакетами) на одной обычной машине без специального железа.

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

Разница, которую чаще всего упускают, — единица балансировки.

На L4 единица — соединение. Клиент с одним долгим HTTP/2-соединением попадает на один бэкенд и остаётся там навсегда, сколько бы запросов он ни отправил. Десять клиентов, из которых один шлёт 90% трафика, разложатся по десяти бэкендам поровну — по соединению на каждый, и один бэкенд получит девять десятых работы.

На L7 единица — запрос, и та же нагрузка разложится ровно. Цена — расшифровка, разбор и повторная сборка каждого запроса.

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

Алгоритмы: модель и что она показывает

Дальше числа из модели. Устройство её такое: шестнадцать бэкендов, каждый — одна очередь FIFO с одним обслуживающим прибором. Это классическая модель G/G/1: запросы ждут своей очереди и обрабатываются по одному. Никакой придуманной «формулы деградации» здесь нет — замедление под нагрузкой возникает само, из ожидания.

Поток заявок пуассоновский, время обработки логнормальное (тяжёлый хвост — обычная форма для веб-запросов). Балансировщик видит ровно то, что видел бы настоящий: число незавершённых запросов и скользящее среднее времени ответа. Будущего он не знает. Отброшены первые 20 000 запросов из 300 000, результат усреднён по пяти прогонам.

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

Как читать числа в таблицах ниже. В ячейке — полное время запроса в системе: сколько он ждал в очереди плюс сколько обрабатывался, — измеренное в единицах одной средней обработки. Значит, 1,0 — это «столько, сколько в среднем занимает обработать один запрос»; 0,83 — быстрее средней обработки (запрос почти не стоял в очереди), 25,07 — в двадцать пять раз дольше. Абсолютные секунды тут не нужны: в этих единицах числа не зависят от того, быстрое железо или медленное.

Столбцы — это перцентили, а не среднее. p50 — медиана: половина запросов уложилась быстрее этого значения. p95 — девяносто пятый перцентиль: медленнее оказался только каждый двадцатый. p99 — девяносто девятый: медленнее только каждый сотый. Среднее здесь бесполезно нарочно: балансировщик выбирают по хвосту — по тем немногим запросам, которым не повезло, — а хвост виден именно в p95 и p99, а не в среднем.

Одинаковые серверы, загрузка 80%

Первое, что стоит заметить: разброс вчетверо на одинаковых серверах. Обычное объяснение «если серверы одинаковые, сойдёт и round robin» неверно, и причина не в серверах, а в запросах: они разной длины. Round robin распределяет их поровну по счёту, а не по работе, и сервер, которому подряд достались три длинных запроса, встаёт в очередь, пока сосед простаивает. Least connections этого не допускает, потому что смотрит на то, что ещё не завершилось.

Случайный выбор хуже round robin ровно по той причине, по которой шары падают в корзины неравномерно, — к этому вернёмся в разделе про выбор из двух.

Взвешенный round robin и цена ошибки в весе

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

Числа в тысячах — не задержка, а отсутствие устойчивости. Арифметика простая: шестнадцать серверов при загрузке 80% дают 0,8 запроса на сервер за время одной средней обработки; медленному серверу каждый запрос обходится вчетверо дороже, то есть его собственная загрузка — 3,2. Больше единицы. Очередь на нём растёт без предела, и напечатанное число говорит лишь о том, где остановилась модель, а не о том, сколько ждал бы читатель.

Дальше видно две вещи. Правильно выставленный вес чинит устойчивость, но проигрывает least connections втрое по p99 — статический вес не знает, что происходит прямо сейчас. А вес, выставленный неточно, — худший из вариантов: p95 выглядит здоровым (16,13), и только p99 показывает, что сервер балансирует на грани. Мониторинг по среднему и по p95 такую настройку не поймает.

Least connections и least response time

Least connections в nginx описан дословно так: запрос идёт to the server with the least number of active connections, taking into account weights of servers (серверу с наименьшим числом активных соединений, с учётом весов серверов). Least response time добавляет к этому время: у nginx это least_time с выбором, считать ли время до заголовка (header) или до последнего байта (last_byte).

В модели выше разница между ними невелика: 6,06 против 5,50 по p99 на одинаковых серверах и 7,70 против 6,48 на кластере с медленным сервером. Least response time чуть лучше — и это ожидаемо: число соединений не отличает быстрый бэкенд от медленного, а время отличает.

Разница вырастает там, где число соединений вообще перестаёт быть мерой работы. Соединение, по которому качают файл на гигабайт, и соединение с пустым health-check выглядят для least connections одинаково.

Least bandwidth и least packets

Это уже не про очереди, а про канал. NetScaler определяет least bandwidth как выбор сервиса, that is currently serving the least amount of traffic, measured in megabits per seconds (который в данный момент обслуживает наименьший объём трафика, измеряемый в мегабитах в секунду), а least packets — the least packets in the last 14 seconds (наименьшее число пакетов за последние 14 секунд).

Мерить стоит то, что кончается первым. Для API, где ответ — килобайт JSON, кончится процессор, и мерить надо очереди. Для раздачи видео кончится полоса, и там least connections введёт в заблуждение: десять соединений с битрейтом 100 кбит/с и одно соединение на 50 Мбит/с — это не «десять против одного», это «один против пятидесяти».

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

Sticky sessions: сколько стоит закрепление

Закрепление сессии за бэкендом нужно, когда состояние лежит на сервере. Цена — балансировщик перестаёт балансировать: он раскладывает не запросы, а сессии.

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

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

Технически закрепление делают по-разному, и разница существенна. ip_hash в nginx берёт the first three octets of the client IPv4 address (первые три октета IPv4-адреса клиента) — то есть все клиенты за одним NAT попадают на один бэкенд. Закрепление по куке точнее, но работает только для браузеров. Consistent hashing (hash ... consistent в nginx, ring hash и Maglev в Envoy) отличается от обычного хеша тем, что при добавлении или удалении сервера переезжает малая часть ключей, а не почти все: в документации nginx это сказано прямо — only a few keys will be remapped (переотображены будут лишь немногие ключи).

Power of two choices: почему два, а не все

Начнём с чистой задачи: n шаров бросают в n корзин. Если каждый шар летит в случайную корзину, максимальная загрузка is approximately log n / log log n (составляет примерно log n / log log n). Если каждый шар смотрит на две случайные корзины и падает в менее полную, она становится log log n / log d + O(1). Считаем на модели шаров и корзин — пятнадцать прогонов на каждое n, среднее и стандартное отклонение:

В ячейке — максимальная загрузка: сколько шаров оказалось в самой полной корзине (среднее по пятнадцати прогонам; число после ± — стандартное отклонение). n — это и число шаров, и число корзин сразу. Первые два столбца — два способа бросать шар: в случайную корзину и в менее полную из двух случайных. Последние два — асимптотические формулы из обзора, посчитанные по натуральному логарифму: с ними сравниваем.

Тысячекратный рост числа корзин почти удваивает максимум при случайном выборе — и практически не двигает его при выборе из двух: 2,60 → 3,53. Асимптотическая формула на конечных n занижает оценку для случайного выбора (она асимптотическая, это нормально), а для выбора из двух держится рядом с моделью и на ста тысячах корзин сходится с ней вплотную: 3,53 против 3,53.

Почему берут именно два, а не три и не десять, сказано в том же обзоре: each additional choice beyond two decreases the maximum load by just a constant factor (каждый следующий выбор сверх двух уменьшает максимальную загрузку лишь на постоянный множитель). Первый шаг от одного к двум меняет асимптотику, все следующие — только множитель. HAProxy это и закрепил: число жеребьёвок настраивается, а по умолчанию равно двум. Envoy формулирует так же: selects N random available hosts as specified in the configuration (2 by default) and picks the host which has the fewest active requests (выбирает N случайных доступных узлов, как задано в настройках (по умолчанию два), и берёт тот, у которого меньше всего активных запросов).

Но в очередях, а не в корзинах, картина другая — и в этом главная неожиданность всего разбора. Вернитесь к первой таблице: p99 у power of two — 8,86, у least connections — 6,06. Выбор из двух проигрывает. И это не артефакт модели: автор HAProxy, измеряя на живом стенде из шести машин, получил тот же знак — least connections дал about 4% higher (примерно на 4 % выше) запросов в секунду, а пики соединений у него оказались about 30% lower (примерно на 30 % ниже).

Так зачем тогда power of two?

Главный результат: свежесть сигнала важнее алгоритма

Least connections требует знать, сколько запросов сейчас в работе у каждого бэкенда. Пока балансировщик один, он это знает точно — он сам их и отправил. Как только балансировщиков много, точного знания нет ни у кого.

Обычное объяснение — стадный эффект: все балансировщики видят один и тот же «самый свободный» сервер и одновременно бросаются на него. Owen Garrett описывает это через очередь на паспортном контроле: all the guides notice that one queue is momentarily shorter and faster, and all send travelers to that queue (все сотрудники разом замечают, что одна очередь сейчас короче и движется быстрее, и все направляют людей именно в неё). Envoy называет ту же причину как основание для выбора: resistance to herding behavior (устойчивость к стадному эффекту).

Объяснение звучит убедительно, поэтому оно проверено двумя опытами. Верным оно оказалось наполовину.

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

В ячейках — p99 в тех же единицах средней обработки, что и выше; строка — сколько независимых балансировщиков работает одновременно.

Стада нет. Least connections плавно теряет преимущество и к шестидесяти четырём балансировщикам сравнивается с round robin — 18,38 против 19,72, — но ни разу не становится хуже него. Причина понятна, если сформулировать: приватный счётчик — это несмещённая выборка из общей картины. Балансировщик судит по неполным данным, но не по неправильным, и ошибки разных балансировщиков не сговариваются.

Опыт второй: общий снимок состояния с задержкой. Теперь балансировщики читают одну общую картину, которая обновляется раз в refresh (в единицах среднего времени обработки) — так устроены схемы, где метрики бэкендов собираются и раздаются.

В ячейках снова p99; строка — насколько устарел общий снимок: 0 — мгновенный, 2,0 — отстаёт на две средние обработки.

Вот теперь видно всё. При задержке в две средние обработки least connections даёт p99 = 19,95 — хуже round robin и почти на уровне случайного выбора. Power of two за то же время сдвигается с 8,86 до 10,52, то есть на пятую часть.

Значит, дело не в количестве балансировщиков как таковом. Разрушает least connections общий устаревший сигнал: все читают одно и то же неверное число и делают одну и ту же ошибку одновременно. Приватные неполные счётчики такого не дают, а общий снимок — даёт, и чем он старше, тем хуже.

Отсюда правило, которое сформулировано в терминах данных, а не в терминах названий алгоритмов:

• Балансировщик один и считает сам — least connections или least response time, и ничего лучше не нужно.
• Балансировщиков много, но каждый считает свои запросы — least connections всё ещё разумен; его преимущество тает, но до round robin он не опускается.
• Состояние приходит со стороны и с задержкой — выбор лучшего из двух, и чем больше задержка, тем очевиднее выигрыш.
• Состояния нет вовсе — взвешенный round robin, и тогда за весами придётся следить руками; ошибка в весе стоит дороже, чем кажется.

Когда балансировать уже нечего: отбрасывать нагрузку

Модель выше показала точку, за которой алгоритм перестаёт что-либо решать: загрузка больше единицы, очередь растёт без предела. Это не край модели, а рабочая ситуация, и у неё есть отдельный ответ, к балансировке отношения не имеющий.

Avoiding overload is a goal of load balancing policies. But no matter how efficient your load balancing policy, eventually some part of your system will become overloaded. Gracefully handling overload conditions is fundamental to running a reliable serving system.

перевод

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

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

Load shedding drops some proportion of load by dropping traffic as the server approaches overload conditions.

перевод

Отбрасывание нагрузки сбрасывает некоторую долю нагрузки, отбрасывая трафик по мере приближения сервера к условиям перегрузки.

Зачем отказывать, если можно поставить в очередь, объясняет вторая половина нашей же модели. Очередь — это не бесплатное ожидание, а потраченная память и добавленная задержка:

Queued requests consume memory and increase latency. For example, if the queue size is 10x the number of threads, the time to handle the request on a thread is 100 milliseconds. If the queue is full, then a request will take 1.1 seconds to handle, most of which time is spent on the queue.

перевод

Запросы в очереди потребляют память и увеличивают задержку. Например, если размер очереди в 10 раз больше числа потоков, а время обработки запроса потоком — 100 миллисекунд, то при полной очереди обработка запроса займёт 1,1 секунды, бо́льшая часть которых проведена в очереди.

И — главное — работа в такой очереди уже никому не нужна: If a user's web search is slow because an RPC has been queued for 10 seconds, there's a good chance the user has given up and refreshed their browser, issuing another request: there's no point in responding to the first one, since it will be ignored (Если пользовательский веб-поиск медленный, потому что RPC простоял в очереди 10 секунд, велика вероятность, что пользователь сдался и обновил браузер, отправив новый запрос: отвечать на первый нет смысла — ответ проигнорируют). То есть за порогом сервер тратит ресурсы на ответы, которые никто не прочтёт. Отброс возвращает их тем, кто ещё ждёт:

The goal of load shedding is to keep latency low for the requests that the server decides to accept so that the service replies before the client times out.

перевод

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

Механика. Она использует ровно ту величину, которой уже оперирует least connections из таблицы выше — число незавершённых запросов:

One straightforward way to shed load is to do per-task throttling based on CPU, memory, or queue length […] For example, one effective approach is to return an HTTP 503 (service unavailable) to any incoming request when there are more than a given number of client requests in flight.

перевод

Прямолинейный способ отбрасывать нагрузку — ограничивать её на уровне задачи по процессору, памяти или длине очереди […] Например, один действенный подход — возвращать HTTP 503 (сервис недоступен) на любой входящий запрос, когда число клиентских запросов в работе превышает заданное.

В Envoy это два разных механизма, и различать их стоит. Размыкание цепи — max_requests и max_pending_requests на кластер — защищает того, к кому идут. Менеджер перегрузки — того, кто стоит посередине: This is distinct from circuit breaking which is primarily aimed at protecting upstream services (Это отличается от размыкания цепи, которое нацелено прежде всего на защиту вышестоящих сервисов). У второго пороги заданы по давлению ресурса: сливать соединения при 92 % использования кучи, прекращать принимать запросы при 95 %.

Порог можно и не выбирать вручную. Адаптивная конкурентность выводит его из задержки: измеряет идеальное время обхода minRTT, сравнивает с текущим и двигает предел по градиенту — This gradient value has a useful property, such that it decreases as the sampled latencies increase (У этого градиента есть полезное свойство: он уменьшается по мере роста измеренных задержек). Цена честно названа там же: во время окна измерения возможен заметный рост числа 503, потому что предел на это время прижимается к минимуму.

Две оговорки, без которых совет вреден.

Первая — про метрику. Считать ёмкость в запросах в секунду ненадёжно: modeling capacity as "queries per second" … often makes for a poor metric (моделирование ёмкости как „запросов в секунду“ … часто оказывается плохой метрикой). Причина та же, что в нашей модели: запросы неодинаковы по стоимости, и именно разброс стоимости, а не их число, растил хвост.

Вторая — про то, что отброс сам должен работать. Ветка, которой не пользуются, обычно сломана:

Remember that the code path you never use is the code path that (often) doesn't work. In steady-state operation, graceful degradation mode won't be used, implying that you'll have much less operational experience with this mode and any of its quirks, which increases the level of risk.

перевод

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

Повторы: почему «попробовать ещё раз» умножается

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

When failures are caused by overload, retries that increase load can make matters significantly worse. They can even delay recovery by keeping the load high long after the original issue is resolved.

перевод

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

Опаснее всего то, что повторы перемножаются по слоям, а не складываются:

Avoid amplifying retries by issuing retries at multiple levels: a single request at the highest layer may produce a number of attempts as large as the product of the number of attempts at each layer to the lowest layer. If the database can't service requests because it's overloaded, and the backend, frontend, and JavaScript layers all issue 3 retries (4 attempts), then a single user action may create 64 attempts (4^3) on the database.

перевод

Избегайте усиления повторов, выполняя их на нескольких уровнях: один запрос на верхнем слое может породить число попыток, равное произведению числа попыток на каждом слое вплоть до нижнего. Если база не может обслуживать запросы из-за перегрузки, а слои бэкенда, фронтенда и JavaScript делают по 3 повтора (4 попытки), то одно действие пользователя может создать 64 попытки (4³) к базе.

AWS считает тот же множитель на пять слоёв и получает 243: If each layer retries independently, the load on the database will increase 243x, making it unlikely to ever recover (Если каждый слой повторяет независимо, нагрузка на базу вырастет в 243 раза, и восстановиться она вряд ли сможет). Оба числа — арифметика, а не замер, и это здесь важнее замера: показатель степени равен числу слоёв, а слои в реальной системе никто не считает.

Соедините это с моделью выше. Загрузка выросла до единицы, задержки поползли, клиенты начали повторять — и нагрузка на нижний слой выросла не на проценты, а в несколько раз: множитель здесь возводится в степень числа слоёв, а не умножается на него. Три слоя по три повтора — это 64 попытки вместо одной; пять слоёв — 243. Точка невозврата, которая на графике выглядела далёкой, оказывается за этим множителем.

Три меры. Две названы первоисточниками прямо, третья из них следует.

Разнести повторы во времени. Always use randomized exponential backoff when scheduling retries (Всегда используйте рандомизированную экспоненциальную выдержку при планировании повторов). Случайность здесь не украшение: без неё повторы синхронизируются и приходят пачкой — Jitter adds some amount of randomness to the backoff to spread the retries around in time (Джиттер добавляет к выдержке некоторую случайность, чтобы разнести повторы во времени).

Ограничить повторы бюджетом, а не счётчиком на запрос. Consider having a server-wide retry budget. For example, only allow 60 retries per minute in a process, and if the retry budget is exceeded, don't retry; just fail the request (Подумайте о бюджете повторов на уровне сервера. Например, разрешайте только 60 повторов в минуту в процессе, а если бюджет исчерпан — не повторяйте, просто отказывайте в запросе). Разница принципиальна: счётчик на запрос ограничивает одного клиента, бюджет — всех сразу, а умножается именно суммарный объём.

Повторять только на одном слое. Это следствие первой цитаты, и в настройке Envoy оно записано так:

In general we recommend using retry budgets; however, if static circuit breaking is preferred it should aggressively circuit break retries. This is so that retries for sporadic failures are allowed, but the overall retry volume cannot explode and cause large scale cascading failure.

перевод

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

Близость против равномерности: маршрутизация по зонам

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

The purpose of zone aware routing is to send as much traffic to the local zone in the upstream cluster as possible while roughly maintaining the same number of requests per second across all upstream hosts (depending on load balancing policy).

перевод

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

«Как можно больше» и «примерно одинаково» — это две цели, и вторая ограничивает первую. Что происходит, когда они расходятся, описано конкретно:

The originating cluster local zone percentage is greater than the one in the upstream cluster. In this case we cannot route all requests from the local zone of the originating cluster to the local zone of the upstream cluster because that will lead to request imbalance across all upstream hosts. Instead, Envoy calculates the percentage of requests that can be routed directly to the local zone of the upstream cluster. The rest of the requests are routed cross zone.

перевод

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

То есть локальность — не переключатель, а доля, и считается она из соотношения ёмкостей зон.

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

This approach is mutually exclusive with zone aware routing, since in the case of locality aware LB, we rely on the management server to provide the locality weighting, rather than the Envoy-side heuristics used in zone aware routing.

перевод

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

Здесь важно, как веса ведут себя при отказах. Вес корректируется не сразу, а с запасом — коэффициент избыточного выделения 1,4, — и таблица из документации показывает, где именно начинается перелив (расположение X с весом 1 против Y с весом 2):

Между 100 % и 70 % не меняется ничего: коэффициент 1,4 и означает «пока недоступно меньше 30 %, считаем расположение целым». Дальше доля падает пропорционально. Это числа документации Envoy, не наш замер.

И самое важное для главной оси статьи — про момент решения. Алгоритм из таблицы выше выбирает узел не первым, а третьим:

1. Pick priority level. 2. Pick locality (as described in this section) within priority level from (1). 3. Pick endpoint using cluster specified load balancer within locality from (2).

перевод

1. Выбрать уровень приоритета. 2. Выбрать расположение внутри уровня приоритета из (1). 3. Выбрать конечную точку заданным для кластера балансировщиком внутри расположения из (2).

То есть спор «round-robin или least connections», которому посвящена модель, разыгрывается внутри уже выбранного расположения. Два предыдущих шага отсекают большую часть узлов до того, как алгоритм вообще получит слово, — и влияют на итоговое распределение сильнее, чем выбор между ним и соседним.

Немного истории

Что здесь стандарт, а что решение конкретного продукта

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

Стандарт, на который можно опираться: формат DNS-ответа и семантика TTL (RFC 1035, RFC 1794); формат EDNS Client Subnet и смысл SCOPE PREFIX-LENGTH (RFC 7871); теоретические границы для случайного выбора и выбора из двух — это математика, она не зависит от продукта.

Решение конкретного продукта, которое меняется от версии к версии: набор алгоритмов и их названия; что именно nginx считает «активным соединением»; сколько жеребьёвок делает HAProxy по умолчанию (два — но это настройка); формула Envoy для неравных весов; то, что ip_hash берёт первые три октета; размер таблицы Maglev (65537). Ни одно из этих чисел не свойство балансировки как таковой — все они выбраны авторами и записаны в документации, на которую стоит ссылаться при споре.

Как воспроизвести числа

Все числа в статье получены тремя способами.

Живые DNS-замеры — обычными запросами к резолверу, с подстановкой EDNS Client Subnet для четырёх подсетей; результат зависит от того, где вы находитесь и через какой резолвер ходите, поэтому у вас адреса будут другие, а поле scope — тем же: именно оно и проверяется. Скрипты: bench/load-balancing/dns2.py и bench/load-balancing/ecs.py.

Модель очередей — дискретное событийное моделирование, описанное выше: шестнадцать очередей FIFO, пуассоновский поток, логнормальное время обработки, 300 000 запросов, первые 20 000 отброшены, пять прогонов с разными зёрнами. Алгоритмы считает bench/load-balancing/sim2.py, веса и закрепление — bench/load-balancing/sim3.py, много балансировщиков сразу — bench/load-balancing/herd.py и bench/load-balancing/herd2.py.

Задача о шарах и корзинах — bench/load-balancing/bins.py.

Числа из модели воспроизводимы точно; числа из DNS — только по смыслу.