Błędy 429 przy limicie RPS: Poissona i sharding

Modelowanie błędów 429 w rozproszonym limiterze RPS z rozkładem Poissona

Przy średnim ruchu 129 udanych zapytań na sekundę i 7 błędach 429 przy limicie 150 RPS pojawia się pytanie: dlaczego limiter działa stabilnie? Wykres z 40 minut pokazuje stały poziom błędów na 15-sekundowych interwałach. Rozkład Poissona liczby zapytań wyjaśnia to zjawisko: przy λ = 136,28 prawdopodobieństwo przekroczenia 150 zapytań w 1 sekundę wynosi 11,27%.

Kod do obliczenia prawdopodobieństwa:

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

Ta wartość >1 na 15-sekundowym interwale odpowiada obserwowanemu wykresowi.

Warunkowa wartość oczekiwana błędów

Proste obliczenie oczekiwanej liczby zapytań przy przekroczeniu daje 156,4, a błędów — zaledwie 0,6 RPS. Różnica w stosunku do 7,27 RPS wymaga doprecyzowania.

Kod dla wartości oczekiwanej warunkowej:

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)

Korekty modelu: ponowne próby i sharding

Uwzględnienie 1 ponownej próby na błąd (oryginalny ruch 132,64 RPS) zwiększa błędy do 0,72 RPS — to za mało.

Kluczowy czynnik: serwis z 6 podami (2 pody na 3 DC). Przy shardingu każdy limiter dzieli 150/6 = 25 RPS, border = 26.

Obliczenia dla jednego limitera:

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
# limited_num ≈ 6.85

Model wyjaśnia 6,85 RPS błędów w porównaniu z 7,27 obserwowanymi. Limiter działa bez synchronizacji uprawnień, z okresową wymianą z sąsiadami i resetem licznika.

Specyfika implementacji rozproszonego limitera

Możliwe opcje:

• Leaky Bucket: stały wyciek tokenów.
• Reset na początku sekundy: stały okres, podatny na skoki.
• Dynamiczny podział: wymiana heartbeat'ami do obliczenia udziału.

W scenariuszu z shardingiem bez synchronizacji każdy pod niezależnie decyduje o limicie, zwiększając ogólne odrzucenia liniowo z liczbą shardów.

Co jest ważne

• Rozkład Poissona dokładnie modeluje ruch konsumencki bez botów (przypadek graniczny nieskończonej liczby użytkowników).
• Sharding limiterów RPS bez synchronizacji zwiększa błędy proporcjonalnie do liczby podów.
• Ponowne próby klienta pogłębiają problem, wymagając korekty w modelach.
• Warunkowa wartość oczekiwana (E[X | X ≥ border]) jest kluczowa dla prognozowania odrzuceń.
• 11% prawdopodobieństwo skoku wyjaśnia stabilne błędy 429 na zagregowanych wykresach.

— Editorial Team