distributed systems
- Has known properties of capacity ($C$), inflow rate ($R_{in}$), and outflow rate ($R_{out}$).
- As requests come in, check if the bucket is full, and drop it
- Good for avoiding bursts of requests downstream
- Slow processing will stall the entire queue
1.2. Token Bucket Algorithm
- Bucket has predefined capacity of tokens, each bucket is periodically filled with tokens at a constant rate. Checks for tokens in a bucket every time we recieve a request
- Similar to leaky bucket, but allows for bursts of traffic to come in, and space efficient. At time cutoffs for token refills, however, it could slightly exceed
- Same as the others, but has problems like the token one where edges can allow for more requests than normal.
- Biggest danger is that a consistent burst of traffic at the window edges could overflow
- LB keeps track of timestamps when things arrive, whenever a request arrives, we look back and count how many are available.
- Avoids the issue of edges, but requires extra memory
1.5. Sliding Window Counter
- Divide time into various windows. Keep a sliding window over them, and count how many.
- Avoids the issue edges, but has problems in that it assumes previous window requests are distributed evenly across the window time
- Smoothes out the burst
2. Distribution Algorithms