Shinjuku: Preemptive Scheduling for μsecond-scale Tail Latency


Kostis Kaffes, Timothy Chong, and Jack Tigar Humphries, Stanford University; Adam Belay, Massachusetts Institute of Technology; David Mazières and Christos Kozyrakis, Stanford University


The recently proposed dataplanes for microsecond scale applications, such as IX and ZygOS, use non-preemptive policies to schedule requests to cores. For the many real-world scenarios where request service times follow distributions with high dispersion or a heavy tail, they allow short requests to be blocked behind long requests, which leads to poor tail latency.

Shinjuku is a single-address space operating system that uses hardware support for virtualization to make preemption practical at the microsecond scale. This allows Shinjuku to implement centralized scheduling policies that preempt requests as often as every 5µsec and work well for both light and heavy tailed request service time distributions. We demonstrate that Shinjuku provides significant tail latency and throughput improvements over IX and ZygOS for a wide range of workload scenarios. For the case of a RocksDB server processing both point and range queries, Shinjuku achieves up to 6.6× higher throughput and 88% lower tail latency.

NSDI '19 Open Access Sponsored by NetApp

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {227639,
author = {Kostis Kaffes and Timothy Chong and Jack Tigar Humphries and Adam Belay and David Mazi{\`e}res and Christos Kozyrakis},
title = {Shinjuku: Preemptive Scheduling for {μsecond-scale} Tail Latency},
booktitle = {16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19)},
year = {2019},
isbn = {978-1-931971-49-2},
address = {Boston, MA},
pages = {345--360},
url = {},
publisher = {USENIX Association},
month = feb

Presentation Video