Implement Token Bucket Algorithm

[shalarewicz]

Implement a Token Bucket algorithm using TDD which limits requests based on a user's IP address and allows developers to provide the desired CAPACITY and REFILL_RATE (in milliseconds).

The algorithm should consider each request to consume exactly 1 token. It should not consider GraphQL query complexity when limiting requests.

The TokenBucket instance of a RateLimiter limits requests based on a unique user ID.
Whenever a user makes a request the following steps are performed:

1. Refill the bucket based on time elapsed since the previous request
2. Update the timestamp of the last request.
3. Allow the request and remove the requested amount of tokens from the bucket if the user has enough.
4. Otherwise, disallow the request and do not update the token total.

For more information on implementing a Token Bucket Algorithm see the following resources:

• https://www.alibabacloud.com/blog/throttling-solutions-in-standalone-and-distributed-scenarios_596984#:~:text=Redis%20can%20easily%20implement%20the,hash%20data%20structure%20of%20Redis.
• https://en.wikipedia.org/wiki/Token_bucket
• page 54 of System Design interview (pinned in Slack)

[shalarewicz]

Expected input is some form of user id and the number of tokens used in the request. The output is a boolean indicating if the request is allowed