429 Errors with RPS Limit: Poisson and Sharding

Modeling 429 Errors in a Distributed RPS Limiter with Poisson Flow

With an average traffic of 129 successful requests per second and 7 429 errors at a limit of 150 RPS, the question arises: why does the limiter trigger consistently? A 40-minute graph shows a constant level of errors on 15-second intervals. The Poisson distribution of request volume explains the phenomenon: with λ = 136.28, the probability of exceeding 150 requests in 1 second is 11.27%.

Code for calculating the probability:

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

This value >1 on a 15-second interval corresponds to the observed graph.

Conditional Expectation of Errors

A simple calculation of the expected number of requests when exceeding the limit gives 156.4, and errors—only 0.6 RPS. The difference from 7.27 RPS requires clarification.

Code for conditional expectation:

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)

Model Adjustments: Retries and Sharding

Accounting for 1 retry per error (original traffic 132.64 RPS) increases errors to 0.72 RPS—still insufficient.

Key factor: a 6-pod service (2 pods per 3 DCs). With sharding, each limiter divides 150/6 = 25 RPS, border = 26.

Calculation for one 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

The model explains 6.85 RPS errors versus 7.27 observed. The limiter operates without permission synchronization, with periodic neighbor exchange and counter reset.

Implementation Features of a Distributed Limiter

Possible options:

• Leaky Bucket: constant token leakage.
• Reset at the start of a second: fixed period, vulnerable to spikes.
• Dynamic division: heartbeat exchange for share calculation.

In a sharded scenario without synchronization, each pod independently decides on the limit, increasing overall failures linearly with the number of shards.

Key Takeaways

• The Poisson distribution accurately models consumer traffic without bots (a limiting case of infinite users).
• Sharding RPS limiters without synchronization increases errors proportionally to pods.
• Client retries exacerbate the problem, requiring adjustments in models.
• Conditional expectation (E[X | X ≥ border]) is critical for predicting failures.
• An 11% probability of a spike explains stable 429s on aggregated graphs.

— Editorial Team