Yes, this is why you want to use a token bucket rate limiter (which for some reason was considered and rejected by the original post). We wrote it up here and have an open-source impl on github that's in production serving hundreds of millions of rate limits: https://medium.com/smyte/rate-limiter-df3408325846