load balancing [e1b7cc98]
1. Algorithms Per Server
1. Algorithms Per Server
1.1. Leaky Bucket Algorithm [e4795d65]
1.1. Leaky Bucket Algorithm [e4795d65]
- 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
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
1.3. Fixed Window
1.3. Fixed Window
- 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
1.4. Sliding Window Log
1.4. Sliding Window Log
- 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
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
3. Implementations
3. Implementations
- github.com/facebookincubator/katran?tab=readme-ov-file L4 loadbalancer (shiv/katran)
- Proxygen - github.com/facebook/proxygen