Implementing a Leaky Bucket Rate Limiter

The leaky bucket algorithm is a common technique for rate limiting. It ensures that a system doesn't get overwhelmed by smoothing out incoming requests over time. This challenge asks you to implement a Python class that simulates a leaky bucket.

Problem Description

You need to create a Python class named LeakyBucket. This class will simulate the behavior of a leaky bucket, which has a fixed capacity and a constant leakage rate.

Here are the key requirements:

1. Initialization: The LeakyBucket class should be initialized with:

   • capacity: The maximum number of items the bucket can hold.
   • leak_rate: The number of items that leak out of the bucket per unit of time (e.g., per second).

2. Adding Items: The bucket should have a method, say add(item), which attempts to add an item to the bucket.

   • If the bucket has enough space (i.e., current_items < capacity), the item is added, and the method should return True.
   • If the bucket is full, the item is rejected, and the method should return False.

3. Leaking: The bucket's contents should "leak" out at a constant leak_rate. This leakage should be simulated over time. For simplicity in this challenge, we will consider time in discrete steps. A leak() method should be implemented. Calling leak() should decrease the number of items in the bucket by leak_rate, ensuring that the number of items doesn't go below zero.

4. Tracking Current Items: The class should maintain a count of the current number of items in the bucket.

Expected Behavior:

• When add() is called and the bucket is not full, the item count increases.
• When add() is called and the bucket is full, the item count remains unchanged.
• When leak() is called, the item count decreases by leak_rate (or to zero if the current count is less than leak_rate).

Edge Cases:

• Adding an item when the bucket is exactly full.
• Leaking when the bucket is empty or has fewer items than the leak_rate.
• Capacity being zero or negative (though we'll define constraints to avoid this).
• Leak rate being zero or negative (similarly, constraints will apply).

Examples

Example 1:

# Initializing a leaky bucket with capacity 5 and leak rate 2 per second.
bucket = LeakyBucket(capacity=5, leak_rate=2)

# Adding items
print(bucket.add(1)) # Output: True (bucket: 1)
print(bucket.add(2)) # Output: True (bucket: 2)
print(bucket.add(3)) # Output: True (bucket: 3)

# Simulating one second of leakage
bucket.leak() # bucket: 3 - 2 = 1

print(bucket.add(4)) # Output: True (bucket: 1 + 1 = 2)
print(bucket.add(5)) # Output: True (bucket: 2 + 1 = 3)
print(bucket.add(6)) # Output: True (bucket: 3 + 1 = 4)
print(bucket.add(7)) # Output: True (bucket: 4 + 1 = 5) - Bucket is now full

# Attempting to add when full
print(bucket.add(8)) # Output: False (bucket: 5)

# Simulating another second of leakage
bucket.leak() # bucket: 5 - 2 = 3

Explanation: The bucket starts empty. We add items until it's full. After a leak, there's space, allowing more items to be added until it's full again. Adding an item when full fails. Subsequent leakage reduces the count.

Example 2:

bucket = LeakyBucket(capacity=3, leak_rate=4)

print(bucket.add('a')) # Output: True (bucket: 1)
print(bucket.add('b')) # Output: True (bucket: 2)
print(bucket.add('c')) # Output: True (bucket: 3) - Bucket is full

# Attempting to add when full
print(bucket.add('d')) # Output: False (bucket: 3)

# Simulating leakage when leak_rate > current items
bucket.leak() # bucket: max(0, 3 - 4) = 0

print(bucket.add('e')) # Output: True (bucket: 1)

Explanation: This demonstrates that the leak() method correctly handles cases where the leak_rate exceeds the current number of items, preventing the count from becoming negative.

Constraints

• capacity will be an integer, 0 <= capacity <= 1000.
• leak_rate will be an integer, 0 <= leak_rate <= 100.
• The add and leak methods will be called sequentially or interleaved, but the internal state should always reflect the correct number of items.
• The internal tracking of items should not exceed the capacity.

Notes

• Consider how you will manage the internal state of the bucket (the current number of items).
• The leak_rate represents items per "time unit". In this simulation, a call to leak() represents one time unit passing.
• You can use simple integer arithmetic to manage the items.
• The item itself doesn't need to be stored in this simulation; we only need to track the count of items.