Повтор с джиттером

Сервер упал на десять секунд, и у двух тысяч клиентов разом сорвался запрос. Сервер поднимется и будет отвечать 500 раз в секунду — то есть всем хватит четырёх секунд. Но клиенты не знают, когда он поднимется, и повторяют запрос. Как именно — решает, получат ли они ответ через полминуты или не получат никогда. Выберите правило повтора и посмотрите, сколько клиентов стучится в сервер каждые 100 мс.

«Сразу» — самый быстрый вариант, пока отказ серверу ничего не стоит: все обслужены за 13,9 с, но каждый клиент отправил в среднем 120 запросов. Пауза в секунду и пауза, которая растёт вдвое, сокращают число запросов, но превращают клиентов в строй: все две тысячи приходят в один и тот же такт, сервер принимает пятьдесят, остальные уходят ждать вместе — и снова приходят вместе. Экспонента без случайности обслуживает последнего клиента через 13 минут. Теперь включите «отказ стоит серверу десятую долю ответа»: принять соединение и ответить «занят» тоже работа. Две тысячи отказов в такт съедают всё, что сервер может сделать, и все три правила без случайности за минуту не пропускают ни одного клиента. А с джиттером — случайной долей паузы — пик нагрузки после сбоя 44–94 запроса за такт при возможностях 50, и все обслужены за 23–30 секунд.

Идея

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

Рост и случайность нужны вместе, и сцена показывает почему. Один рост без случайности сохраняет строй: две тысячи клиентов, получившие отказ в один такт, все ждут ровно две секунды, потом ровно четыре. Одна случайность без роста — пауза, скажем, от нуля до секунды — раскладывает всех по десяти тактам, по двести клиентов на такт, а сервер тянет пятьдесят: перегрузка просто размазана. А растущее окно рано или поздно становится шире, чем нужно: при N клиентах и сервере на C запросов за такт окну достаточно N/C тактов, и полный джиттер доходит до такого окна за log₂(N/C) неудач. В модели N/C = 2000/50 = 40 тактов: окно в 64 такта открывается после седьмой неудачи, и с этого момента в среднем на такт приходится меньше, чем сервер может обслужить.

Четыре правила паузы

Пусть после k-й неудачи предел g = min(cap, base·2^k−1): начальная пауза base, удвоение, потолок cap. Распространены четыре способа выбрать паузу.

• Без джиттера: пауза ровно g. Клиенты, упавшие вместе, вместе и возвращаются.
• Полный джиттер: пауза равномерно от 0 (в модели — от одного такта) до g. Самый широкий разброс.
• Равный джиттер: половина g гарантирована, вторая половина случайна — от g/2 до g. Никто не повторяет слишком рано.
• Декоррелированный джиттер: пауза случайна от base до утроенной прошлой паузы, но не выше потолка. Окно растёт не по номеру попытки, а от того, сколько выпало в прошлый раз.

Сто клиентов, у которых запрос сорвался в одно и то же мгновение, — точка на каждого, строка на каждую неудачу:

Без джиттера все сто точек в каждой строке сливаются в одну. Полный джиттер разбрасывает их по всему окну, равный — по его правой половине, декоррелированный — шире и неровнее: у каждого клиента своя история. На модели шторма три правила с джиттером близки: полный обслуживает половину клиентов к 14,9 с и всех к 29,6 с за 9,2 запроса на клиента, равный — к 16,7 и 23,1 с за 8,7, декоррелированный — к 12,2 и 26,8 с за 12,2. Марк Брукер в 2015 году сравнивал их на другой модели — клиенты наперебой обновляют одну и ту же строку базы данных — и там равный джиттер заметно отставал по времени, а полный и декоррелированный шли близко. Вывод один и тот же на любой модели: главное — чтобы случайность была, а какая из трёх, уже второстепенно.

Почему строй губит сервер

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

Такие состояния назвали метастабильными отказами: Натан Бронсон и соавторы в 2021 году описали, как система, выведенная из строя кратким сбоем, остаётся в перегрузке и после того, как причина ушла, потому что её держит обратная связь — здесь повторы. Выйти можно, только разорвав связь: сбросив очереди, отказывая быстрее, чем обслуживает, или сделав так, чтобы клиенты сами разошлись во времени. Последнее и делает джиттер.

Сколько повторять и где

Пауза — половина дела. Вторая половина — сколько раз повторять. Книга Google о надёжности сайтов советует всегда повторять со случайной экспоненциальной паузой, ограничивать число повторов на запрос и держать общий бюджет повторов на процесс — например, не больше 60 повторов в минуту. И главное — не повторять на каждом слое. Если сервис повторяет вызов четыре раза, а его вызывающий тоже четыре, и ещё один слой выше тоже, база данных под ними получает от одного действия пользователя 4³ = 64 запроса — как раз тогда, когда она и так не справляется. Посчитать эту лавину на графе сервисов — вторая задача.

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

Код

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

Сколько это стоит

Само правило — несколько арифметических действий и одно случайное число на неудачу: O(1) времени и O(1) памяти на клиента, у декоррелированного джиттера — ещё прошлая пауза. Платят за него задержкой: с ростом пауз клиент узнаёт, что сервер поднялся, не сразу, а в среднем через половину текущего окна. В модели это видно по медиане: «сразу» обслуживает половину клиентов к 12,0 с, полный джиттер — к 14,9 с. Цена в три секунды за то, чтобы не отправить лишние сотни тысяч запросов и не оказаться в перегрузке, из которой нет выхода.

Где работает

Ethernet. В старом Ethernet все станции делили один кабель, и если две начинали передавать одновременно, кадры сталкивались. После k-го столкновения станция ждала случайное число интервалов от 0 до 2^{min(k, 10)} − 1, а после шестнадцати попыток кадр выбрасывала. Это и есть экспоненциальная отсрочка с полным джиттером, только в тактах кабеля. Сам приём — случайную паузу, среднее которой удваивается после каждого столкновения, — описали Роберт Меткалф и Дэвид Боггс в статье об Ethernet 1976 года и назвали двоичной экспоненциальной отсрочкой; точные числа — до 2¹⁰ интервалов и не больше шестнадцати попыток — закрепил потом стандарт.

TCP. Если подтверждение не пришло, таймер повторной передачи удваивается после каждой потери. Случайности тут нет, но и нужды в ней меньше: соединения теряют пакеты не в одно и то же мгновение.

Клиентские библиотеки. gRPC при повторе соединения начинает с паузы в секунду, умножает её на 1,6 до потолка в 120 секунд и добавляет случайный разброс ±20 %. Клиентские библиотеки облачных сервисов умеют повторять запросы с экспоненциальной паузой и джиттером — после статьи Брукера это стало обычным выбором.

История

Случайная пауза после столкновения появилась в радиосетях начала 1970-х, где станции делили один канал. Ethernet 1976 года добавил к ней рост: станция не знает, сколько у неё соперников, а удвоение окна после каждого столкновения подстраивает паузу под их число. Для серверов и их клиентов про то же заговорили позже, когда синхронные повторы стали обычной причиной падений. Статья Марка Брукера «Exponential Backoff And Jitter» 2015 года с формулами полного, равного и декоррелированного джиттера стала для неё стандартной ссылкой; её главный вывод — «решение не в том, чтобы убрать отсрочку, а в том, чтобы добавить джиттер».

Задачи

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