The Partner Whose Retry Loop Took Down Everyone Else

Your public partner API sits behind 12 stateless gateway instances behind a load balancer, and every partner is contractually capped at 1,000 requests/minute per API key. One integration partner shipped a bug: their client retries every failed request immediately with no backoff, and when your API had a brief 30-second blip, their retry storm hit 40,000 requests/minute. Because the current rate limiter increments an in-memory counter local to whichever gateway instance handles each request, no single instance ever saw more than a few thousand requests/minute from that key, so nothing tripped -- but in aggregate that partner consumed enough capacity to push p99 latency for every other partner from 60ms to 900ms for 10 minutes. You're asked to design a rate limiter that actually enforces the 1,000 req/min cap per API key across all 12 instances, and to pick and defend a specific algorithm (token bucket, leaky bucket, fixed window, or sliding window) for this traffic shape.