CS
Задачник Базовый курс EN

Задача

Шторм повторов

симуляция случайность хеш-таблица расписание распределённые системы в проде

Смоделируйте шторм повторов после сбоя, как в статье. Время идёт тактами. В такт 0 у всех n клиентов (номера от 0 до n − 1) запрос срывается, и каждый повторяет его, пока не получит ответ. Первые D тактов сервер лежит: все запросы получают отказ. Потом за такт сервер тратит не больше W единиц работы: ответ стоит A единиц, отказ — R (0 ≤ R < A). Если в такт пришло x запросов, обслуживается наибольшее s ≤ x, при котором s·A + (x − s)·R ≤ W (ноль, если и это невозможно).

Пришедшие в один такт клиенты выстраиваются по номеру: первые s получают ответ и уходят, остальные по очереди получают отказ. Клиент, получивший k-й отказ, выбирает паузу p ≥ 1 и стучится снова в такт «текущий + p». Пусть g = min(cap, base·2k−1). Правила:

  • immediately: p = 1;
  • constant: p = base;
  • exponential: p = g;
  • full: p = between(1, g);
  • equal: p = g − ⌊g/2⌋ + between(0, ⌊g/2⌋);
  • decorrelated: p = min(cap, between(base, max(base, 3·q))), где q — прошлая пауза этого клиента, а перед первой — base.

between(lo, hi) — общий для всех генератор splitmix64 с начальным состоянием seed; его вызывают по мере отказов, в описанном порядке. Все действия — в 64-битных беззнаковых числах:

state = state + 0x9E3779B97F4A7C15
z = state
z = (z xor (z >> 30)) * 0xBF58476D1CE4E5B9
z = (z xor (z >> 27)) * 0x94D049BB133111EB
z = z xor (z >> 31)
between = lo + (z >> 11) mod (hi − lo + 1)

Смоделируйте такты от 0 до H − 1.

Вход

Одна строка: n, W, A, R, D, H, правило, seed, base, cap (1 ≤ n ≤ 5·104, 1 ≤ A ≤ W ≤ 106, 0 ≤ D < H ≤ 2·105, 0 ≤ seed < 263, 1 ≤ base ≤ cap ≤ 104). Всего запросов за H тактов не больше 106.

Выход

Три числа: сколько клиентов получили ответ за H тактов; такт, в который ответ получил последний из них, или −1, если ответ получили не все; сколько всего запросов пришло за H тактов.

В первом примере пять клиентов, два ответа за такт, экспонента без джиттера: все пятеро стучатся в такты 0, 1, 3, 7 и дальше вместе, отказанные — снова вместе. Во втором — полный джиттер и отказы по 2 единицы.

Примеры

Пример 1

Вход
5 20 10 0 2 50 exponential 1 1 8
Выход
5 15 19

Пример 2

Вход
5 20 10 2 2 50 full 7 1 8
Выход
5 8 19

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
10 тестов

Разбор

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

1Подсказка 1

Сколько тактов из H вообще кто-нибудь стучится в сервер? И сколько клиентов в каждом из них?

2Идея

Хранить для каждого клиента «когда он постучится» и каждый такт перебирать всех — это H·n, до 1010. Вместо этого раскладываем клиентов по корзинам: словарь «такт → список клиентов». Такт стоит столько, сколько в нём клиентов, а пустые такты почти бесплатны; всего работы — по числу запросов, не больше 106. Это та же «очередь событий», что в симуляциях: вместо словаря подойдёт и куча пар (такт, клиент) — она сама выдаст клиентов такта по номерам.

3Разбор

Дальше — аккуратность: сортировать клиентов такта по номеру, обслуживать первых, вызывать генератор строго в порядке отказов и считать паузы в целых. В Python 64-битную арифметику приходится обрезать маской 264 − 1 после каждого умножения, в Go uint64 переполняется сам — как и нужно.

Третий тест — шторм из статьи с полным джиттером: все 2000 клиентов обслужены к такту 296 (29,6 с), запросов 18 435. Четвёртый — экспонента без джиттера и отказы, которые чего-то стоят: за минуту не обслужен никто, потому что все 2000 клиентов приходят в один и тот же такт, а работы на отказ двум тысячам больше, чем сервер может потратить за такт.

3+Решение
4Сложность

O(H + Q log Q), где Q — число запросов: такты перебираются один раз, каждый запрос сортируется и кладётся в корзину.

5Типичные ошибки
  • Перебор всех клиентов каждый такт. Ответ тот же, но в длинных тестах, где не все дождутся ответа, это миллиарды проверок.
  • Порядок вызовов генератора. Случайные числа общие для всех клиентов, поэтому важен порядок: такт за тактом, внутри такта — по номерам отказанных.
  • Пауза 0. Полный джиттер берёт паузу от 1, а не от 0: клиент не может постучаться в тот же такт.
  • Переполнение 2k. После нескольких десятков отказов base·2k−1 выходит за 64 бита; степень ограничивают до сравнения с cap.

Алгоритмы задачи

SYS Приём Повтор с джиттером Пауза перед повтором растёт вдвое и выбирается случайно: клиенты расходятся во времени и не бьют по серверу волнами. O(1) на решение о паузе 2 задачи
Каталог алгоритмов