Katkat
Back

Implement KV Store and Token Bucket

DropboxSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to design a thread-safe in-memory key-value store and implement a rate limiter using the token bucket algorithm.

Task

Implement a thread-safe class RateLimitedKV that functions as a simple key-value store with rate-limited access.

Requirements

  1. KV Store: Implement put(key, value) and get(key) methods. If a key does not exist, get should return None.
  2. Rate Limiting: Apply a token-bucket rate limiter for each key. Each key is allowed a maximum of N requests per minute. If a request exceeds the limit, get or put should raise an Exception or return an error indicator.
  3. Thread-Safety: The implementation must handle concurrent access from multiple threads without data corruption.

Interface

class RateLimitedKV:
    def __init__(self, capacity: int, refill_rate_per_min: int):
        # capacity: Max tokens a bucket can hold
        # refill_rate_per_min: Tokens added per minute
        pass

    def put(self, key: str, value: Any) -> bool:
        # Returns True if successful, False if rate limited
        pass

    def get(self, key: str) -> Any:
        # Returns value if found and within rate limit, else None or error
        pass

Examples

Example 1: store = RateLimitedKV(capacity=2, refill_rate_per_min=1)

  • store.put("A", 10) -> True
  • store.put("A", 20) -> True
  • store.put("A", 30) -> False (Bucket empty)

Constraints

  • Use thread locks where necessary to ensure atomicity.
  • The refill logic should be lazy (calculate tokens based on elapsed time since the last request).

Hints

Hint 1

Use a dictionary to map keys to their respective token bucket objects and data values.

Hint 2

For the token bucket, store the 'last_refill_timestamp' and 'current_tokens' for each key to calculate replenishment on the fly.

Hint 3

Use a ReentrantLock or threading.Lock to synchronize access to the dictionary and individual bucket state updates.

Follow-up questions

  • How would you modify this to support a global rate limit across all keys in addition to the per-key limit?
  • If the number of keys grows to millions, what memory management strategies would you implement to prevent the store from crashing?
  • How would you adapt this design to work across multiple servers in a distributed environment?