Your '100 requests per second' rate limiter probably allows 200

The first rate limiter almost everyone writes looks like this:

func Allow(key string, limit int, window time.Duration) bool {
	bucket := fmt.Sprintf("%s:%d", key, time.Now().Unix()/int64(window.Seconds()))
	count, _ := redis.Incr(ctx, bucket).Result()
	if count == 1 {
		redis.Expire(ctx, bucket, window)
	}
	return count <= int64(limit)
}

It is short, it is obviously correct at a glance, and it is wrong in a way that only shows up under load.

The boundary problem#

The bucket key is derived from wall-clock time divided by the window. With a one second window and a limit of 100, every request between 12:00:00.000 and 12:00:00.999 increments the same counter. At 12:00:01.000 the key changes and the counter resets to zero.

So consider a client that sends 100 requests at 12:00:00.999, then another 100 at 12:00:01.001. Both bursts are allowed. Two milliseconds apart, the service absorbed 200 requests against a limit of 100.

The worst case is exactly 2x the configured limit, and it is reachable at every single window boundary.

Sliding window counters#

The standard fix is to weight the previous window's count by how far into the current window you are:

func Allow(key string, limit int, window time.Duration) bool {
	now := time.Now()
	curKey := bucketKey(key, now, window)
	prevKey := bucketKey(key, now.Add(-window), window)
 
	cur, prev := mgetInts(curKey, prevKey)
 
	// How much of the current window has elapsed, 0.0 to 1.0.
	elapsed := float64(now.UnixNano()%int64(window)) / float64(window)
	// Weight the previous window by the portion still "in view".
	estimate := float64(prev)*(1-elapsed) + float64(cur)
 
	if estimate >= float64(limit) {
		return false
	}
	redis.Incr(ctx, curKey)
	return true
}

At 12:00:01.001, elapsed is roughly 0.001, so the previous window's 100 requests count for 100 * 0.999 = 99.9. The second burst is rejected almost immediately.

This is an approximation — it assumes requests were spread evenly across the previous window — but the error is small and it is bounded. Cloudflare published numbers showing well under 1% of requests misclassified against real traffic.

When you actually want a token bucket#

Sliding windows smooth out the boundary, but they still reject in a step function: you are fine until you are suddenly not. If you want callers to be able to burst deliberately and then pay for it, a token bucket is the better model.

The token bucket keeps two values per key — the current token count and the last refill timestamp — and refills lazily on read:

type Bucket struct {
	Tokens     float64
	LastRefill time.Time
}
 
func (b *Bucket) Take(rate float64, capacity float64, now time.Time) bool {
	elapsed := now.Sub(b.LastRefill).Seconds()
	b.Tokens = math.Min(capacity, b.Tokens+elapsed*rate)
	b.LastRefill = now
 
	if b.Tokens < 1 {
		return false
	}
	b.Tokens--
	return true
}

Capacity controls how large a burst you tolerate; rate controls the sustained throughput. Setting capacity equal to rate gives you something very close to a sliding window, so you can start there and open it up per-client.

What to actually do#

If you have a fixed-window limiter in production right now, the honest assessment is that your effective limit is double what the config says. You can either:

1. Halve the configured limit and accept the fixed window, which is crude but takes one line and is strictly safer than today.
2. Move to a sliding window, which is maybe thirty lines and removes the boundary problem for good.
3. Move to a token bucket if you have clients whose traffic is genuinely bursty and you would rather shape it than reject it.

Most services should do (2). The ones fronting expensive downstream systems — payment gateways, model inference, anything with per-call cost — should do (3), because there the difference between 100 and 200 requests per second is a line item.