Your question is Secure Token Bucket Rate Limiter. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Meta Graph API services often enforce per-client request limits using a token bucket. Implement a secure in-memory rate limiter that validates a request signature and then decides whether the request is allowed under a per-key token bucket.
Write a function that processes a list of request events in timestamp order. Each event contains timestamp, key, cost, and signature. A request is valid only if its signature matches the expected signature for that key. Invalid signatures must be rejected and must not consume tokens. Valid requests consume cost tokens only if enough tokens are available at that timestamp.
Input:
capacity: integer bucket sizerefill_rate: integer tokens added per secondsecrets: map from string key to string secretrequests: list of [timestamp, key, cost, signature]Output:
The expected signature for a request is the string:
key + ":" + str(timestamp) + ":" + str(cost) + ":" + secret
Each key has its own bucket. Buckets start full at capacity. On each request, refill based on elapsed whole or fractional seconds since that key's previous valid request processing time, capped at capacity.
def secure_token_bucket(capacity, refill_rate, secrets, requests):