From Static Rate Limiting to Adaptive Traffic Management in Airbnb’s Key-Value Store
Airbnb's key-value store, Mussel, originally used simple QPS rate-limiting to prevent single clients from overwhelming the system. As traffic grew and became more complex, this approach proved insufficient due to cost variance and traffic skew. To address this, Mussel evolved to implement a multi-layered quality of service (QoS) system. The first layer, Resource-Aware Rate Control (RARC), charges requests in Request Units (RU) that account for rows, bytes, and latency, reflecting the actual backend cost. This system uses token buckets with static RU quotas for each caller.The second layer, load shedding, provides real-time protection when capacity is strained or hotspots develop. It combines traffic criticality, a latency ratio indicating system stress, and a CoDel-inspired queueing policy. This allows high-priority traffic to remain responsive and gracefully backs off other traffic when latency increases. The third layer, hot-key detection and DDoS defense, identifies and mitigates surges of identical requests targeting specific data. It uses an in-memory top-k counter for real-time detection, local caching on dispatcher pods, and request coalescing to send only one request to the storage layer for duplicate hot-key lookups.These layered controls have significantly improved Mussel's ability to handle traffic spikes and maintain reliability. Key takeaways include the value of early impact for validating concepts, preferring local control loops for scalability, and employing mechanisms that operate on different time scales. This sophisticated QoS stack ensures Mussel remains fast and dependable, even under extreme and volatile traffic conditions.