Quantcast APIs can receive short traffic bursts that should be tolerated without allowing sustained overload. Implement a per-client token bucket rate limiter for a chronologically ordered request stream.
Each client has a bucket with a maximum capacity of capacity tokens. Initially, every client's bucket is full. Tokens are replenished continuously at refill_rate tokens per second, but the bucket cannot exceed its capacity. Processing one request consumes one token. A request is allowed only when its client's bucket contains at least one token after replenishment.
Implement rate_limit(requests, capacity, refill_rate), where requests is a list of [timestamp, client_id] pairs. timestamp is a nonnegative number of seconds, and client_id is a string. Return a list of booleans in request order, where True means allowed and False means rejected. Requests are globally ordered by nondecreasing timestamp. Each client's state must be independent.
def rate_limit(requests, capacity, refill_rate):