429-Fehler mit RPS-Limit: Poisson und Sharding

Modellierung von 429-Fehlern in einem verteilten RPS-Limiter mit Poisson-Fluss

Bei einem durchschnittlichen Traffic von 129 erfolgreichen Anfragen pro Sekunde und 7,429-Fehlern bei einem Limit von 150 RPS stellt sich die Frage: Warum löst der Limiter konsistent aus? Ein 40-minütiges Diagramm zeigt ein konstantes Fehlerniveau in 15-Sekunden-Intervallen. Die Poisson-Verteilung des Anfragevolumens erklärt das Phänomen: Mit λ = 136,28 beträgt die Wahrscheinlichkeit, 150 Anfragen in 1 Sekunde zu überschreiten, 11,27 %.

Code zur Berechnung der Wahrscheinlichkeit:

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

Dieser Wert >1 in einem 15-Sekunden-Intervall entspricht dem beobachteten Diagramm.

Bedingte Erwartung von Fehlern

Eine einfache Berechnung der erwarteten Anzahl von Anfragen bei Überschreitung des Limits ergibt 156,4, und Fehler – nur 0,6 RPS. Die Abweichung von 7,27 RPS bedarf einer Klärung.

Code für bedingte Erwartung:

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)

Modellanpassungen: Wiederholungen und Sharding

Die Berücksichtigung von 1 Wiederholung pro Fehler (ursprünglicher Traffic 132,64 RPS) erhöht die Fehler auf 0,72 RPS – immer noch unzureichend.

Schlüsselfaktor: ein 6-Pod-Service (2 Pods pro 3 DCs). Mit Sharding teilt jeder Limiter 150/6 = 25 RPS, Grenze = 26.

Berechnung für einen 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

Das Modell erklärt 6,85 RPS Fehler gegenüber 7,27 beobachteten. Der Limiter arbeitet ohne Berechtigungssynchronisation, mit periodischem Nachrichtenaustausch und Zählerrücksetzung.

Implementierungsmerkmale eines verteilten Limiters

Mögliche Optionen:

• Leaky Bucket: konstantes Token-Leck.
• Reset zu Beginn einer Sekunde: fester Zeitraum, anfällig für Spitzen.
• Dynamische Aufteilung: Heartbeat-Austausch für Anteilsberechnung.

In einem Sharding-Szenario ohne Synchronisation entscheidet jeder Pod unabhängig über das Limit, was die Gesamtfehler linear mit der Anzahl der Shards erhöht.

Wichtige Erkenntnisse

• Die Poisson-Verteilung modelliert Consumer-Traffic ohne Bots genau (ein Grenzfall unendlicher Benutzer).
• Sharding von RPS-Limitern ohne Synchronisation erhöht Fehler proportional zu Pods.
• Client-Wiederholungen verschärfen das Problem und erfordern Anpassungen in Modellen.
• Bedingte Erwartung (E[X | X ≥ Grenze]) ist entscheidend für die Vorhersage von Fehlern.
• Eine 11 %-ige Wahrscheinlichkeit einer Spitze erklärt stabile 429s in aggregierten Diagrammen.

— Editorial Team