На скрине показано 40 минут графиков с балансировки некоторого эндпоинта. На выделенном участке видно 129.01 рпс успехов и 7.27 ошибок 4xx, которые являлись 429 от рпс-лимитера. Настройка рпс-лимитера находилась на уровне “не более 150 запросов с интервалом в 1 секунду”. Не странно ли видеть такое уверенное и постоянное превышение лимита?

На соседнем эндпоинте в прошлый раз уже замечал, что пуассоновское распределение неплохо справляется с описанием поведения объёма потока в интервал времени (*). Давайте попробуем, используя его же, попробовать объяснить наблюдаемое.

Во-первых, давайте прикинем - какова вероятность что у нас на интервале в 1 секунду будет хотя бы 151 запрос:

def get_prob_at_least(border, lmbd):
    sum = 1
    mult = 1
    for i in range(1, border):
        mult = mult * lmbd / i
        sum += mult
    return 1 - sum * math.exp(-lmbd)

get_prob_at_least(151, 129.01 + 7.27)
0.1127

То есть - где-то 11%, но это на 1-секундный интервал. На скрине график имеет 15-секундный шаг, что даёт > 1 интервала с превышением в среднем на точке графика. Уже неплохо: нам хотя бы не удивительно что график уверенно показывает положительное число 429.

Давайте попробуем теперь объяснить наблюдаемый рпс ошибок. Посчитаем условное мат-ожидание (**) числа запросов, при условии что у нас их пришло хотя бы 151:

def get_expectation_via_conditional_at_least(border, lmbd):
    sum_prob = 0
    exp_sum = 0
    mult = 1
    for i in range(1, 10000):
        mult = mult * lmbd / i
        if (i >= border):
            exp_sum += i * mult
            sum_prob += mult
    return exp_sum / sum_prob

def get_expected_errors_num(events, border):
    return (get_expectation_via_conditional_at_least(border, events) - border) * get_prob_at_least(border, events)

get_expectation_via_conditional_at_least(151, 129.01 + 7.27) даёт 156.4, а ожидаемое число ошибок выходит всего лишь 0.6 рпс - существенная разница с 7.27, которые мы хотели бы объяснить.

Я стал искать причины смещений. Первое что я нашёл - скорее всего клиентская сторона делает безусловный 1 ретрай. То есть надо исходный рпс событий считать 129.01 + 7.27/2, а результат числа ошибок удваивать. Эта поправка почти ничего не даёт - 0.72 рпс ошибок.

Далее, порядок ошибки и проверка некоторых графиков заставили меня вспомнить что данный сервис рпс-лимитера - это 6-подовый сервис (стандартная история - по 2 пода на 3 дц). Распределённые рпс-лимитеры можно реализовывать по разному, а также можно сильно по разному делать логику раздачи разрешений (Leaky-Bucket, сброс в начале секунды и другие).

Давайте предположим, что рпс-лимитер работает так:

каждый лимитер раз в икс времени узнаёт число живых соседей, и делит разрешённый лимит на найденное число соседей
синхронизации числа не выданных разрешений не происходит
сброс счётчика разрешённых запросов в начале периода

В такой ситуации - у нас 6 независимых точек принятия решения, и формулы выходят такими

limiters_num = 6
retry_num = 2
rps_one_limiter=(129.01 + 7.27 / 2)/limiters_num
border_one_limiter=int(150/limiters_num) + 1

one_limiter_erros = get_expected_errors_num(rps_one_limiter, border_one_limiter)
limited_num = one_limiter_erros * limiters_num * retry_num

Один лимитер при таких числах имеет ожидаемое число ошибок в 0.57, а общее число ошибок (умножением на 12) получается 6.85.

Кажется, на этом можно успокоиться и считать что поведение (на уровне принципов) объяснено, возможно лимитер действительно примерно предположенным образом и работает.

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

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

(*) Имхо, это работает потому, что здесь идёт речь о достаточно чистом консьюмерском трафике (без роботного трафика) - действительно “около бесконечное число монеток” (юзеров) решают в каждый момент времени “воспользоваться ли сервисом”, то есть примерно условия предельного перехода для пуассоновского распределения и получаются.

(**) Даже мне немного неожиданно, как-то редко умо применяется в чисто прикладных историях

Почему при 136 рпс и 150 рпс лимита наблюдалось 7 рпс ошибок 429