Tales of the Tail: Hardware, OS, and Application-level Sources of Tail Latency

Abstract. Interactive services often have large-scale par-allel implementations. To deliver fast responses, the me-dian and tail latencies of a service’s components must be low. In this paper, we explore the hardware, OS, and application-level sources of poor tail latency in high throughput servers executing on multi-core machines. We first review the basic queuing theory that governs service latency. Using fine-grained measurements of three different servers (a null RPC service, Memcached, and Nginx) on Linux, we then explore why these servers ex-hibit significantly worse tail latencies than queuing mod-els alone predict. The underlying causes include inter-ference from background processes, request re-ordering caused by poor scheduling or constrained concurrency models, suboptimal interrupt routing, CPU power saving mechanisms, and NUMA effects. We systematically eliminate these factors and show that Memcached can achieve a median latency of 11 µs and a 99.9th percentile latency of 32 µs at 75 % utilization. In comparison, a naı̈ve deployment of Memcached has a median latency of 33 µs and a 99.9th percentile latency of 14 ms. Finally, we demonstrate that a tradeoff often exists between throughput and tail latency.