Chyby 429 při RPS-limitu: Poisson a šardování

Modelování chyb 429 v distribuovaném RPS limiteru s Poissonovým tokem

Při průměrném provozu 129 úspěšných požadavků za sekundu a 7 chyb 429 s limitem 150 RPS vyvstává otázka: proč limiter funguje stabilně? Graf za 40 minut ukazuje konstantní úroveň chyb na 15sekundových intervalech. Poissonovo rozdělení objemu požadavků vysvětluje fenomén: při λ = 136,28 je pravděpodobnost překročení 150 požadavků za 1 sekundu 11,27 %.

Kód pro výpočet pravděpodobnosti:

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

Tato hodnota >1 na 15sekundovém intervalu odpovídá pozorovanému grafu.

Podmíněné matematické očekávání chyb

Jednoduchý výpočet očekávaného počtu požadavků při překročení dává 156,4 a chyb — pouze 0,6 RPS. Rozdíl oproti 7,27 RPS vyžaduje upřesnění.

Kód pro podmíněné očekávání:

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)

Úpravy modelu: opakování a sharding

Zohlednění 1 opakování na chybu (původní provoz 132,64 RPS) zvyšuje chyby na 0,72 RPS — nedostatečně.

Klíčový faktor: 6-podová služba (2 pody na 3 DC). Při shardingu každý limiter dělí 150/6 = 25 RPS, border = 26.

Výpočet pro jeden limiter:

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 vysvětluje 6,85 RPS chyb oproti 7,27 pozorovaným. Limiter funguje bez synchronizace povolení, s periodickou výměnou sousedů a resetem čítače.

Specifika implementace distribuovaného limiteru

Možné varianty:

• Leaky Bucket: konstantní únik tokenů.
• Reset na začátku sekundy: pevné období, náchylné k špičkám.
• Dynamické dělení: výměna heartbeatů pro výpočet podílu.

Ve shardovaném scénáři bez synchronizace každý pod nezávisle rozhoduje o limitu, což lineárně zvyšuje celkové odmítnutí s počtem shardů.

Co je důležité

• Poissonovo rozdělení přesně modeluje consumer-provoz bez botů (limitní případ nekonečných uživatelů).
• Sharding RPS limiterů bez synchronizace zvyšuje chyby úměrně podům.
• Opakování klienta problém zhoršuje, vyžaduje úpravy v modelech.
• Podmíněné matematické očekávání (E[X | X ≥ border]) je klíčové pro předpovídání odmítnutí.
• 11% pravděpodobnost špičky vysvětluje stabilní 429 na agregovaných grafech.

— Editorial Team