Token Bucket Rate Limiter II

Problem: Concurrent-Safe Token Bucket Rate Limiter

Create a rate limiter based on the Token Bucket method that remains correct when several threads invoke it simultaneously.

Requirements

1. Apply the Token Bucket approach.
2. Permit calls from multiple threads while ensuring token updates and token allocation happen atomically.
3. Explain ways to limit lock contention when concurrency is high.

API

Implement:

allow(now: float, cost: int = 1) -> bool

At logical timestamp now, attempt to deduct cost tokens. Produce True when the bucket contains enough tokens; otherwise produce False.

Input Format

Logical timestamps are supplied to make evaluation deterministic:

• Line 1 contains capacity refill_rate, where capacity is the maximum number of tokens the bucket can hold and refill_rate is the number of tokens replenished each second.
• Line 2 contains integer m, the count of operations.
• Each of the following m lines has the form ALLOW now cost.

Output Format

Write one result per ALLOW operation: either true or false.

Constraints

• 1 <= capacity <= 10^9
• 0 < refill_rate <= 10^9
• 1 <= m <= 200000
• Values of now appear in non-decreasing order.

Example

Input:
4 2
5
ALLOW 0 2
ALLOW 0 2
ALLOW 0 1
ALLOW 1 2
ALLOW 1 1

Output:
true
true
false
true
false

The bucket begins with four tokens. The first two requests consume all four at time zero, so the next request is denied. By time one, two tokens have been restored; the request costing two succeeds, leaving no token for the final request.