Datacenter networks and in-memory systems increasingly have (single) microsecond [10] latencies. These latencies are critical for today's complex cloud applications to meet SLOs while fanning out to hundreds of datacenter backend servers [21,72]. At microsecond-scale, the distribution of request processing times can be especially extreme; for example, Redis can process GET/PUT requests in 2`s [74] but more complex SCAN and EVAL requests can take hundreds of microseconds or milliseconds to complete. As a result, a single long-running request can block hundreds or thousands of shorter requests.
To bound tail latency, especially for short requests, modern datacenter servers run at low utilization to keep queues short and reduce the likelihood that a short request will block behind long requests. For instance, Google reports that machines spend most of their time in the 10-50% utilization range [11]. Unfortunately, this approach wastes precious CPU cycles and does not guarantee that microsecond datacenter systems will always meet SLOs for short requests.
Recent kernel-bypass schedulers have improved utilization with shared queues [62] and work-stealing [73,75] but these techniques only work for uniform and lightly-tailed workloads. For workloads with a wide distribution of response times, Shinjuku [48] leverages interrupts for processor sharing; however, Shinjuku's interrupts impose nonnegligible delays for single digit microsecond requests and are too expensive to run frequently (our experiments saw ⇡2us per interrupt and preempting as often as every 5`s had a high penalty on sustainable load). Furthermore, Shinjuku's non-standard use of hardware virtualization features makes it dicult to use in the datacenter [62] and public clouds, e.g., Google Cloud, Microsoft Azure, AWS, etc.
Recent congestion control schemes [3,68], similarly, optimize network utilization and reduce ow completion times by approximating Shortest-Remaining-Processing-Time (SRPT), which is optimal for minimizing the average waiting time [79]. Unlike CPU scheduling, though, switch packet schedulers have a physical 'preemption' unit, which is the MTU in the worst case; they process packet headers that include the actual message size; and leverage trac classes that can prioritize packets based on the size of the ow they belong to, which makes scheduling decisions and policy enforcement easier. A CPU scheduler cannot know in advance for how long each request will occupy the CPU and there is no upper limit on execution time, which makes the implementation of SRPT-like policies, or generally policies that prioritize short requests, hard to implement at the microsecond scale.
The unifying factor between congestion control schemes, such as Homa [68] and CPU schedulers, such as Shinjuku, that deal with heavy-tail ow and request distributions, respectively, is that they both temporarily multiplex the shared resource. This paper takes a dierent approach to CPU scheduling for heavy-tailed service time distributions by taking advantage of parallelism and the abundance of cores on a modern multicore server through application-aware [52] spatial isolation of CPU resources.
First, we observe that a kernel-bypass scheduler can, with a little help from programmers, identify the type of incoming requests. For many cloud applications, the messaging protocol exposes the required mechanisms to declare request types: Memcached request types are part of the protocol's header [63]; Redis uses a serialization protocol specifying commands [86]; Protobuf denes Message Types [35]; Next, we observe that requests of the same type often have similar processing types, so, given the ability to identify types, we can track past per-type process times to predict future processing times. Finally, we carefully leave cores idle to prevent short requests from queuing behind arbitrarily longer ones.
Inspired by prior research in networking [2], our approach goes against the grain for OS schedulers, which commonly prioritize work conservation. We show that by making a minor sacrice in the maximum achievable throughput, we can increase the achievable throughput under an aggressive latency SLO and as a result, increase the overall CPU utilization of the datacenter.
To implement this approach, we need to tackle two challenges: (1) predict how long each request type will occupy a CPU and (2) eciently partition CPU resources among types while retaining the ability to handle bursts of arrivals and minimizing CPU waste. To this end, we introduce Perséphone, an application-aware kernel-bypass scheduler. Perséphone lets applications dene request classiers and uses these classiers to dynamically prole the workload. Using these proles, Perséphone implements a new scheduling policy, Dynamic, Application-aware Reserved Cores (DARC) that leverages work conservation for short requests only and is not work conserving for long requests. DARC prioritizes short requests at a small cost in throughput -5% in our experiments -and is best suited for applications that value microsecond responses. For other applications, existing kernel-bypass scheduler work well, though we believe there is a large set of datacenter workloads that can benet from DARC.
We prototype Perséphone using DPDK and compare it to two state-of-the-art kernel-bypass schedulers: Shinjuku [48] and Shenango [73]. Using a diverse set of workloads, we show that Perséphone with DARC can drastically improve requests tail latency and sustain up to 2.3x and 1.3x more load than Shenango and Shinjuku, respectively, at a target SLO. In addition, these improvements come at a lower cost to long requests than Shinjuku's preemption technique, highlighting the challenges of traditional OS scheduling techniques at microsecond scale.
For workloads with wide service time distribution, long requests can block short requests even when queues are short because long requests can easily occupy all workers for a long time. We refer to this eect as dispersion-based headof-line blocking. To better understand how dispersion-based blocking aects short requests, we look beyond request latency and study slowdown: the ratio of total time spent at the server over the time spent doing pure application processing [40].
Slowdown better reects the impact of long requests on short requests. For heavy-tailed workloads, short requests experience a slowdown proportional to the length of the tail. More concretely, consider the following workload, similar to Zygos' "bimodal-2" [75], a mix of 99.5% short requests running for 0.5`s and 0.5% long requests executing in 500`s. A short request blocked behind a long one can experience a slowdown of up to 1001, while a long request blocked behind a short request will see a slowdown of 1.001. As a result, a few short requests blocked by long requests will drive the slowdown distribution and increase tail latency.
Using this workload, we simulate four scheduling policies, including DARC, listed in Table 1. Decentralized rst come, rst served (d-FCFS) models Receive Side Scaling, widely used in the datacenter today [27,60] and by IX [14] and Arrakis [74]. With d-FCFS, each worker has a local queue and receives an even share of all incoming trac. Centralized rst come, rst served (c-FCFS) uses a single queue to receive all requests and send them to idle workers. c-FCFS is usually used at the application level -for example, web servers (e.g., NGINX) often use a single dispatch thread -and captures recent research on kernel-bypass systems [73,75], which simulate c-FCFS with per-worker queues and work stealing. Time Sharing (TS) is used in the Shinjuku system [48], with multiple queues for dierent request types and interrupts at the microsecond scale using Dune [13]. We simulate TS with a 5`s preemption frequency and 1`s overhead per preemption, matching Shinjuku's reported ⇡ 2000 cycles overhead on a 2GHz machine.
Figure 1 shows our simulation results assuming, an ideal system with no network overheads. We use 16 workers, simulate 1 second of requests distributed under Poisson, and report the observed slowdown for the 99.9th percentile of Figure 1. Simulated achievable throughput as a function of 99.9th percentile slowdown for the policies listed in Table 1 on a 16 cores system and a workload composed of 99.5% short requests (0.5`s) and 0.5% long requests (500`s). For a target SLO of 10 times the average service time for each request type, c-FCFS and TS can only handle 2.1 and 3.7 Millions requests per second (Mrps), respectively. DARC can sustain 5.1 Mrps for the same objective. The Y axis represents the total achievable throughput for the entire workload. each type of requests -to capture the impact of the 0.5% long requests on the tail -at varying utilizations, up to a maximum of 5.3 million requests per second (Mrps). d-FCFS performs poorly; it oers an uncontrolled form of non work conservation where workers sit idle while requests wait in other queues. Additionally, d-FCFS has no sense of request types: workers might process a long request ahead of a short one if it arrived rst. c-FCFS performs better because it is work conserving but short requests will block when all workers are busy processing long requests. To meet a target SLO of 10x slowdown for each type of requests, c-FCFS must run the server at 2.1 Mrps, 40% of the peak load. Shinjuku's TS policy fares better than c-FCFS and d-FCFS, being both work conserving and able to preempt long requests: it maintains slowdown below 10 up to 3.7 Mrps, 70% of the peak load. However, this simulation accounts for an optimistic 1`s preemption overhead and overlooks the practicality of supporting preemption at the microsecond scale (c.f., Sec. 6). The DARC way: Our key insight is that prioritizing short requests is critical to protect their service time, an observation the networking community has already made when designing datacenter congestion control schemes [2,3,68]. However, using trac classes and bounded buers do not work for CPU scheduling since schedulers do not know how long a request may occupy a CPU and preemption is unaffordable at single-digit microsecond scales. We observe that leaving certain cores idle for readily handling potential future (bursts of) short requests is highly benecial at microsecond scale. For a request that takes 1 `s or less, even preempting as frequently as every 5`s introduces a 6x slowdown. Instead, given an understanding of each request's potential processing time, an application aware, not work conserving policy can reduce slowdown for short requests by estimating their CPU demand and dedicating workers to them. These workers will be idle in the absence of short requests, but when they do, they are guaranteed to not be blocked behind long requests.
As seen in Figure 1, DARC can meet the 10x slowdown SLO target for both type of requests at 5.1 Mrps. This represents 2.5x and 1.4x more sustainable throughput than c-FCFS and an optimistically cheap time sharing policy. At this load, short requests experience 9.87`s p99.9th tail latency, 3 and 1 orders of magnitude smaller than c-FCFS and TS with 7738`s and 161`s, respectively. To achieve this, DARC asks programmers for a request classier to identify types and uses this classier to dynamically estimate requests' CPU demand. In this example, DARC reserves 1 worker for short requests at a small penalty of 5% achievable throughput.
Counter-intuitively, although DARC wastes cycles idling, it reduces the overall number of machines needed to serve this workload because servers can run at much higher utilization while retaining good tail latencies for short and long requests.
The objective of DARC is to improve tail latency for singledigit microsecond requests in cloud workloads without preemption. Like recent networking techniques that co-design the network protocol and the management of network switches' priority queue [2,3,68] to favor small messages, we protect short requests at backend servers by extracting their type, understanding their CPU demand, and dedicating enough resources to satisfy their demand.
In this section, we describe the challenges associated with implementing these techniques as a CPU scheduling policy, then present the DARC scheduling model, how to compute reservations and when to update them. Table 2 describes the notation used throughout this section.
Challenges. Protecting short requests in a dynamic way through priority queues and non work conservation is dicult because we need to (1) predict how long each request type will occupy a CPU and (2) partition CPU resources among types while retaining the ability to handle bursts of arrivals and minimizing CPU waste.
The rst challenge stems from the granularity of operation DARC is targeting, microsecond scales, and from the need to react to changes in workload. We tackle this challenge with a combination of low-overhead workload proling and queuing delay monitoring, using the former to build a ngerprint of requests' CPU demand and the latter as a signal that this ngerprint might have signicantly changed. This section describes the technique and Sec. 4 its implementation.
The second challenge can be detailed in two parts: bursttolerance and CPU waste. First, though reducing the number of cores available to a given request type forbids it from negatively impacting other types, it also reduces its ability to absorb bursts of arrivals [57]. We solve this tension by enabling cycles stealing from shorter types to longer ones, a mechanism in which short requests can execute on cores otherwise reserved for longer types -but not the opposite. The rationale for stealing is that shorter requests comparatively cause less slowdown to long requests. Note that cycle stealing is a similar concept to work stealing [73,75] but is dierent in practice, as it is performed from the DARC dispatcher rather than from application workers (thus does not require expensive cross-worker coordination).
Second, and similarly to message types and priority queues in network devices, the number of request types can be different than the number of CPU cores on the machine, so very likely the demand for each request type will be fractional -i.e., a request type could require 2.5 workers on Scheduling model. DARC presents a single queue abstraction to application workers: it iterates over typed queues sorted by average service time and dequeues them in a rst come, rst served fashion. Requests of a given type can be scheduled not only on their reserved cores but also steal cycles from cores allocated to longer types -a concept used in Cycle Stealing with Central Queue (CSCQ), a job dispatching policy for compute clusters [42]. Algorithm 1 describes the process of worker selection. For each request type registered in the system, if there is a pending request in that type's queue, DARC greedily searches the list of reserved workers for an idle worker. If none is found, DARC searches for a stealable worker. If a free worker is found, the head of the typed queue is dispatched to this worker. When a worker completes a request, it signals completion to the DARC dispatcher.
DARC reservation mechanism. The number of workers to dedicate to a given request type is based on the average CPU demand of the type at peak load. We use average demand because it is a provable indicator of stability [40] for the system. In addition, workloads can have performance outliers that should not necessarily drive SLOs [22]. We compute average CPU demand using the workload's composition, normalizing the contribution of each request type's average service time to the entire workload's average service time. The contribution of a given request type is its average service time multiplied by its occurrence ratio as a percentage of the
Given a system with , workers, this means that we should attribute 8 ⇤ , workers to g 8 .
Because CPU demand can be fractional and given the non-preemptive requirement we set for the system, we need a strategy to attribute fractions of CPUs to request types. For each such "fractional tie", we have to make a choice: either ceil fractions and always grant entire cores or floor fractions and consolidate fractional CPU demands on shared cores. The former risks over-provisioning certain types, at the cost of others, while the latter risks creating dispersionbased blocking by mixing long and short requests onto the same core(s).
Our approach combines the two: rst we decrease the number of "fractional ties" by grouping request types of similar processing times and computing a CPU demand for the entire group; second we round this demand. As a result, for ⌧ groups, if 5 8 is the fractional demand of group 8, the average CPU waste for DARC across all ⌧ groups is:
across all 5 8 that are greater or equal to 0.5 -otherwise it is 0 for group 8. In practice, during bursts, because we selectively enable work conservation through work stealing for shorter requests, CPU waste is smaller. Algorithm 2 describes the reservation process. First, we identify similar types whose average service time falls within a factor X of each other. Next, we compute the demand for each group and accordingly attribute workers to meet it, rounding fractional demands in the process. We always assign at least one worker to a group. DARC grouping strategy can still result in earlier groups -of shorter requests -consuming all CPU cores. For example, a group of long requests with a CPU demand smaller than 0.5 will not nd any free CPU core. To provide service to these groups, we set aside "spillway" cores. If there are no more free workers, next_free_worker() returns a spillway core. In our experiments (Sec. 5), we use a single spillway core.
Finally, we selectively enable work conservation for shorter requests and let each group steal from workers not yet reserved, i.e., workers that are to be dedicated to longer request types. This lets DARC better tolerate bursts of shorter requests with little impact on the overall tail latency of the workload.
As we process groups in order of ascending service time, we favor shorter requests, and it is possible for our algorithm to under-provision long requests -but never deny them service thanks to spillway cores. Operators can tune the X grouping factor to adjust non work conservation to their desired SLOs. Grouping lets DARC handle workloads where the number of distinct types is higher than the number of workers.
Proling the workload and updating reservations. At runtime, the DARC dispatcher uses proling windows to maintain two pieces of information about each request type: a moving average of service time and an occurrence ratio. These are the ( 8 and ' 8 of equation 1. The dispatcher gathers them when application workers signal work completions. The dispatcher uses queuing delay and variation in CPU demand as performance signals. If the former goes beyond a target slowdown SLO and the latter deviates signicantly from the current demand, the dispatcher proceeds to update reservations and transition to the next windows. During the rst windows, at startup, the system starts using c-FCFS, gathers samples, then transitions to DARC. This technique lets DARC cope with changing workloads where a type's prole changes (eectively, misclassication). During a proling window, unknown or unexpected requests can use the spillway core(s) to execute. We discuss the sensitivity of this mechanism in Sec. 4.3.3.
We implement DARC within a kernel-bypass scheduler called Perséphone. Though DARC requires no special hardware or major application modications, Perséphone must meet the following requirements to support microsecond-scale kernel-bypass applications: (1) the networking stack must be able to eciently sort requests by type in the data path, (2) the scheduler must be able to quickly make per-request scheduling decisions, and (3) workload proling for updating DARC reservation must present low overheads.
Perséphone meets the rst requirement with a request classiers API for capturing request types. Using request classiers, programmers provide a way for the system to classify requests based on types as they enter the system. Perséphone meets the remaining two requirements with a carefully architected networking stack, proler, and scheduler packaged in a user-level library.
Perséphone is designed for datacenter services that must handle large volumes of trac at microsecond latencies. Examples include key-value stores, fast inference engines [54], web search engines and RESTful micro-services. We assume the application uses kernel-bypass for low latency I/O (e.g., with DPDK [26] or RDMA [80]) and performs all application and network processing through Perséphone. Our current prototype is designed for UDP networking, but our technique also works for a stateful dispatcher (c.f., Sec. 6 for a more elaborate discussion).
Perséphone relies on user-dened functions, i.e., "request classiers" to group incoming requests. A request classier accepts a pointer to an application payload (Layer 4 and above) and returns a request type. If the classier cannot recognize a request, Perséphone categorizes it as UNKNOWN and places it in a low priority queue. There is at most one classier active at a time in our current design. Though most of our target applications use optimized protocols such as Redis' RESP [86] that allow a classier to look-up for a header eld to parse the request type, we opted for generality and allowing users to write arbitrarily complex classiers. There is, of course, a performance trade-o: a non-optimized request classier will impact the dispatcher's performance because request classiers are "bumps-in-the-wire" on the dispatching critical path. We leave it to users to quantify this trade o based on the performance they wish to obtain from the dispatcher (i.e., how many requests per second it should be able to sustain). While a complete study of classier performance is out of scope for this paper, we found that for standard protocols where the request type's position is known in the header, our dispatcher can process up to 7 millions packets per second on our testbed, a number competitive with existing kernel-bypass schedulers.
Perséphone consists of three components, shown in Figure 2: one or many net workers dequeueing packets from the network card, a dispatcher applying request classiers and performing DARC scheduling, and application workers performing application processing (e.g., fetching the value from the key-value store). These components operate as an eventdriven pipeline and process packets as follows. 1 On the ingress path, the net worker takes packets from the network card and pushes them to the dispatcher, which 2 classies incoming requests using a user-dened request classier and 3 stores them in typed queues, i.e., buers specialized for a single request type. 4 The dispatcher, running DARC, selects a request from a typed queue and pushes it to a free application worker. 5 The worker processes the request, formats a response buer, and 6 pushes a pointer to that buer to the NIC. In addition, 7 the application worker noties the dispatcher that it has completed the request.
Both the net worker and application workers receive a network context at initialization. This context gives them unique access to receive and transmit queues in the NIC. Perséphone registers a statically allocated memory pool with the NIC for contexts to quickly allocate new buers when receiving packets. This memory pool is backed by a multi-producer, single-consumer ring so workers can release buers after transmission. Both the net and application workers use a thread-local buer cache to decrease interactions with the main memory pool. For requests contained in a single application-level buer, we perform zerocopy and pass along to workers a pointer to the network buer. To issue a response on the transmit path -and if the request holds in a single packet -the worker reuses the ingress network buer to host the egress packet, reducing the number of distinct network buers in use (with the goal of allowing all buers to t in the Last Level Cache space used by DDIO [25] -usually 10% of the LLC). Our current implementation requires copy if the request spans multiple packets.
The dispatcher uses single-producer, single-consumer circular buers to share requests and commands with application workers in a lockless interaction pattern. We use a lightweight RPC design inspired by Barrelsh [12], where both sender and receiver synchronize their send/read heads using a shared variable. To reduce cache coherence trac between cores, the sender synchronizes with the receiver -to update the read head and avoid overows -only when its local state shows the buer to be full. In our prototype, operations on that channel take 88 cycles on average.
The dispatcher maintains three main data structures: a list of RequestType objects, which contains type information such as the type ID and instrumentation data; typed request queues; and a list of free workers. In addition, the dispatcher holds a pointer to a user-dened request classier. The list of free workers is updated whenever a request is dispatched and each time application workers notify the dispatcher about work completion; this is done using a specic control message on the memory channel shared between dispatcher and each worker. Finally, the dispatcher maintains proling windows, during which it computes a moving average of service times by request type and increment a counter for each type seen so far. DARC uses these proling windows to compute resource allocation (Sec. 3) and adjust to changes in the workload's composition. In our prototype, at the median, updating the prole of a request takes 75 cycles, checking whether an update is required takes about 300 cycles, and performing a reservation update takes about 1000 cycles.
To control the sensitivity of the update mechanism in face of bursty arrivals, we set a lower bound on the number of samples required to transition -50000 in our experimentsand the minimum deviation in CPU demand from the current allocation -10% in our experiments. As a measure of ow control, when the system is under pressure and workers cannot process requests as fast as they arrive, the dispatcher drops requests from typed queues that are full. This allows to shed load only for overloaded types without impacting the rest of the workload.
We built a prototype of Perséphone, in 3700 lines of C++ codefoot_0 , to evaluate DARC scheduling against policies provided by Shenango [73] and Shinjuku [48]:
• For a workload with 100x dispersion between short and long requests, Perséphone can sustain 2.35x and 1.3x more throughput compared to Shenango and Shinjuku, respectively (Sec. 5.4.1) • For a workload with 1000x dispersion, Perséphone can sustain 1.4x more throughput than Shenango and improve slowdown by up to 1.4x over Shinjuku for short requests. (Sec. 5.4.2) • For a workload modeled on the TPC-C benchmark, Perséphone reduces slowdown by up to 4.6x over Shenango and up to 3.1x over Shinjuku. (Sec. 5.4.3) • For a RocksDB application, DARC can sustain 2.3x and 1.3x higher throughput than Shenango and Shinjuku, respectively (Sec. 5.4.4) In addition, we demonstrate that Perséphone can handle adversarial situations where workloads changes swiftly and where programmers provide an incorrect request classier.
Workloads. We model workloads exhibiting dierent service time dispersion after examples found in academic and industry references. Often such workloads exhibit n-modal distributions with either an equal amount of short and long requests (e.g., workload A in the YCSB benchmark [20]) or a majority of short requests with a small amount of very long requests (e.g., Facebook's USR workload [7]). Dispersion between shorter and longer requests is commonly found to be two orders of magnitude or more [5,18,66]. We evaluate High Bimodal and Extreme Bimodal (Table 3), two workloads that exhibit large service time dispersion, and TPC-C (Table 4), which models requests in the eponymous benchmarking suite [84], a standardized OLTP model for e-commerce. Finally, we evaluate DARC with an in-memory store built over RocksDB, a database engine used at Facebook [32].
With High Bimodal, long requests represent 50% of the workload but "only" exhibit 100x dispersion. With Extreme Bimodal, long requests are much slower -1000x slower -but very infrequent (0.5% of the mix). We prole TPC-C transactions with an in-memory database [85] and run it as a synthetic workload. Our goal with TPC-C is to evaluate how Perséphone performs with an n-modal request distribution. The workload consists of ve request types with moderate service time dispersion -at most 17.5x between infrequent StockLevel requests and frequent Payment requests. We assume that requests are not dependent on each other. Finally, the RocksDB workload is made of 50% GETs and 50% SCANs requests, executing for 1.5`s and 635`s, respectively, and exhibiting a 420x dispersion factor. This workload strikes a balance between High Bimodal and Extreme Bimodal. Performance metrics. We present two performance views: (i) the slowdown at the tail taken across all requests in the experiment, and (ii) the typed tail latency, i.e., a selected percentile over only the type's response times' distribution. These views help us to understand the various trade-os oered by the systems and policies under evaluation. For both metrics, we use the 99.9th percentile and plot them as a function of the total load on the system. Client. The client is a C++ open loop load generator that models the behavior of bursty production trac. It generates requests under a Poisson process centered at the workloads' average service time. Each experiment runs for 20 seconds and we discard the rst 10% of samples to remove warmup eects. We ran our experiments for several minutes and found the results similar. To interact with the server, we use a simple protocol where TPC-C transaction ID, RocksDB query ID, and synthetic workload request types are located in the requests' header. We accordingly register a request classier on the server to map these IDs to request types. This request classier adds a one-time ⇡ 100 nanoseconds overhead to each request. Systems. In addition to Perséphone, we compare two stateof-the-art systems: Shenango and Shinjuku. Shenango's IOKernel uses RSS hashes to steer packets to application cores, which perform work stealing to balance load and avoid dispersion-based blocking, in a fashion similar to ZygOS [75]. within Perséphone. The rst column is p99.9 overall slowdown, the second and third p99.9 latency for short and long requests, respectively. For all columns, the X axis is the total load on the system. DARC improves slowdown over c-FCFS by up to 15.7x, at a cost of up to 4.2x increased latency for long requests.
We also compare to a version of Shenango with work stealing disabled, to evaluate d-FCFS. We choose Shenango over ZygOS due to its more recent implementation and its support for UDP. Shinjuku implements microsecond-scale, user-level preemption by exploiting Dune's virtualization features [13] at up to 5`s frequency. Leveraging this ability to preempt, Shinjuku implements a single queue policy, where preempted requests are enqueued at the tail of the queue, and a multiqueue policy with a queue per request type and where preempted requests are enqueued at the head of their respective queue. The multi-queue policy selects the next queue to dequeue using a variant of Borrowed Virtual Time [29]. Across experiments, DARC updates reservations whenever a request experiences queuing delays of ten times its average proled service time. Lastly, all systems use UDP networking. Testbed. We use 7 Cloudlab [30] c6420 nodes (6 clients, 1 server), each equipped with a 16-core (32-thread) Intel Xeon Gold 6142 CPU running at 2.60GHz, 376GB of RAM, and an Intel X710 10 Gigabit NIC. The average network round trip time between machines is 10`s. We disabled TurboBoost and set isolcpu. Shinjuku and Perséphone run on Ubuntu 16.04 with Linux kernel version 4.4.0. Shenango runs on Ubuntu 18.04 with Linux kernel version 5.0. Shinjuku uses one hyperthread for the net worker and another for the dispatcher, collocated on the same physical core. Shenango runs its IOKernel on a single core, and Perséphone runs both its net worker and dispatcher on the same hardware thread. All systems use 14 worker threads running on dedicated physical cores. For Shenango, we provision all cores at startup and disable dynamic core allocation since we want to evaluate performance for a single application and Shenango otherwise re-assign cores to multiple applications running on the same machine.
To validate that DARC improves performance of short requests compared to c-FCFS and d-FCFS, we run these policies on High Bimodal in Perséphone. Figure 3 presents our results. c-FCFS improves the tail latency of short requests over d-FCFS by eliminating local hotspots at workers, a result consistent with previous work [75]. However, because c-FCFS does not protect the service time distribution of short requests, they experience dispersion-based blocking from long requests. With c-FCFS, short requests experience 309`s p99.9 latency at 260kRPS, driving slowdown for the entire workload to 283x. In contrast, DARC reserves 1 core for short requests and schedules them rst, reducing slowdown upon c-FCFS by a factor of 15.7 2 and can sustain 2.3x higher throughput for a SLO of 20`s for short requests. This comes at the cost of up to a 4.2x increase in tail latency for long requests. The average CPU waste occasioned by DARC is 0.86 core. Because slowdown is driven by short requests and the two graphs are very similar, we omit short requests in the next sections and focus on overall slowdown and tail latency for long requests.
We empirically validate DARC's reservation mechanism (Sec. 3) by manually conguring the number of workers dedicated to short requests from 0 to 14. We call this version "DARC-static". It schedules short requests rst and let them execute on all the cores. When the number of reserved workers is 0, DARC-static is equivalent to a simple Fixed Priority 2 The network contributes 10`s to response time. At 260kRPS, short requests experience 309`s end-to-end latency with c-FCFS and 18`s with DARC. This means that server-side slowdown is 37x better with DARC.
policy favoring short requests. Figure 4 presents the overall slowdown experienced by High Bimodal (a) and Extreme Bimodal (b) at 95% load. We observe that for the former, the best slowdown -a 4.4x improvement -is achieved with 1 core, and for the latter with 2 cores -a 1.5x improvement. Those settings validate DARC's selection, as described in Sec. 5.2 and Sec. 5.4.
For comparison, we draw the slowdown line oered by c-FCFS on Perséphone. Reserving too many workers results in long requests being starved. Simple Fixed Priority scheduling results in dispersion-based blocking for short requests.
Figures 6a and6b show the performance experienced by High Bimodal and Extreme Bimodal in all three systems. Figure 6 presents TPC-C performance, and Figure 8 RocksDB performance. Shenango implements d-FCFS and c-FCFS. Shinjuku uses its multi-queue policy for High Bimodal, TPC-C, and RocksDB; and its single queue policy for Extreme Bimodal (per the Shinjuku paper [48]). We invested signicant eorts in tuning Shinjuku for short requests performance and preempting as frequently as possible. We could only sustain 75% for High Bimodal (5`s interrupts) and RocksDB (15`s interrupts), and 55% load for Extreme Bimodal (5`s interrupts), after which the system starts dropping packets and eventually crashes (despite sustaining close to 4.5 million 1`s RPS without preemption on our testbed). We found that reducing the frequency of preemption helped sustain higher loads at the expense of shorter requests. TPC-C is most favorable to Shinjuku because the services times are higher and dispersion smaller. Shinjuku can handle 85% of this load when preempting every 10`s.
5.4.1 High Bimodal. Shinjuku improves the tail latency of short requests over Shenango's c-FCFS by preempting long requests. However, Shinjuku aggressively preempts every 5`s to maintain good latency for short requests and adds a constant overhead -at least 20% in this experiment -to preempted requests. As a result, it can sustain only 75% of the load before dropping requests. In comparison, DARC reserves 1 core for short requests and can sustain 2.35x and 1.3x more load than Shenango and Shinjuku, respectively, for a target slowdown of 20x. At 75% load, DARC reduces slowdown by 10.2x and 1.75x over Shenango and Shinjuku, respectively. Perhaps more importantly, compared to Shinjuku's preemption system, DARC consistently provides better tail latency for long requests. We also observe that Perséphone's centralized scheduling oers better performance for long requests than Shenango -compared to the c-FCFS line in gure 3 -because Perséphone does not have to approximate centralization with work stealing.
Bimodal. We observe similar trends for this workload. For a target 50x slowdown, both Shinjuku and Perséphone can sustain 1.4x higher throughput than The rst column is the p99.9 slowdown across all transactions. Each subsequent column is the p99.9 latency for a given transaction. Transactions are presented in ascending average service time. Note the dierent Y axis for slowdown and latency. At 85% load, Perséphone oers 9.2x, 7x, and 3.6x improved p99.9 latency to Payment (b), OrderStatus (c) and NewOrder (d) transactions, compared to Shenango's c-FCFS, reducing overall slowdown by up to 4.6x (a). For a slowdown target of 10x, Perséphone can sustain 1.2x and 1.05x more throughput than Shenango and Shinjuku, respectively. Shenango. However, past 55% load, the overheads of aggressively preempting every 5`s is too expensive and Shinjuku starts dropping packets. For long requests, preemption overheads are always at least 24% (620`s for 500`s requests). In contrast, Perséphone reserves 2 cores to maintain good tail latency for short requests and can sustain 1.25x more load while reducing slowdown up to 1.4x over Shinjuku. All the while, Perséphone provides tail latency for long requests competitive with Shenango. For this workload the CPU waste occasioned by DARC is, on average, 0.67 core. Given a 10x overall slowdown target, Perséphone can sustain 1.2x and 1.05x higher throughput than Shenango and Shinjuku, respectively. 5.4.4 RocksDB. We use Perséphone to build a service running RocksDB and create a Shenango application running a similar RocksDB service. Shinjuku already implements a RocksDB service. The database is backed by a le pinned in memory. We use the same workload as Shinjuku's: 50% GET requests and 50% SCAN requests over 5000 keys. On our testbed, GETs execute in 1.5`s and SCANs in 635`s. Consistently with previous experiments, we were able to sustain only about 75% of the theoretical peak load with Shinjuku using a 15`s preemption timer and its multi-queue policy. We omit d-FCFS because it oers poor performances. DARC reserves 1 core for GET requests, idling 0.96 core on average. Figure 8 presents slowdown for this experiment: for a 20x slowdown QoS objective, DARC can sustain 2.3x and 1.3x higher throughput than Shenango and Shinjuku, respectively.
In this section, we demonstrate Perséphone capacity to react to sudden changes in workload composition. For comparison with a baseline, we include c-FCFS performance. The experiment studies three phase changes: (1) fast requests suddenly become slow and vice-versa (2) the ratio of each type change and (3) the workload becomes only fast requests. Across this experiment, we keep the server at 80% utilization. Each phase lasts for 5 seconds. Figure 7 presents the results. Green boxes describe phases. The rst row is the 99.9th percentile latency and the second row the number of cores guaranteed to each type (not including stealable cores).
At rst, B requests can run on all 14 cores -1 dedicated core and 13 stealable cores -and A requests are allowed to run on 13 cores. Latency is slightly higher for B requests and slightly slower for A requests at the beginning of the experiment because the system starts in c-FCFS before proceeding to the rst reservation. In the second phase, we inverse the service time of A and B to evaluate how DARC can handle miss-classication. During the transition, which takes about 500ms, "B-fast" requests observe increased latency -up to 50`s-as "A-slow" requests are allowed to run on all cores before the reservation update. The graph shows latency increase before the transition because these "B-fast" requests were already in the system and the X axis is the sending time. During the second transition, we change the ratio of each type: A requests now make up 99.5% of the mix. As a result, their CPU demand increases and DARC reserves them 2 cores. For this new composition, 80% utilization on the server results in increased throughput, and latency becomes slightly higher for both types of requests as all queues grow larger.
Finally, we change the workload to be only made of A requests. Despite A requests being able to run on all 14 cores, pending B requests can be serviced on the spillway core.
Finally, we evaluate DARC's behavior when users fail to provide a correct request classier. We modify the dispatcher to push incoming requests to a random typed queue. We expect each typed queue to hold an equal share of each request type, thus converging to c-FCFS. We run High-bimodal on a two nodes setup (one server with 8 worker threads and one client, both running on Silver 4114 Xeon CPUs and using Mellanox Connectx-5 cards). Figure 9 presents the results. DARC-random uses the random classier. As expected, DARC-random and c-FCFS exhibit similar behaviors.
Networking model. In the current implementation, the net worker is a layer 2 forwarder and performs simple checks on Ethernet and IP headers. Application workers handle layers 4 and above and directly perform TX. This design intends to maximize our dispatcher's performance -the main bottleneck in Perséphone-and make it competitive with existing systems. Shenango and Shinjuku separate roles in a similar way. There is no fundamental reason, though, for not having the net worker handle more of the network stack Using a stateful network stack would preclude ooading TX to the workers since shared state between the net worker and application workers would hinder performance. For TCP, this problem is partly addressed by TAS [53] and Snap [62]. Interrupts at `s scale. Though desirable in theory because it enables a better approximation to SRPT, interrupts at the microsecond scale are challenging to implement. In addition to operating overheads, adequate timing is also critical for protecting short requests. Consider the simulation from section 2. We extend this analysis with a set of single queue preemptive systems with dierent interrupt overheads and delay. We assume a preemption event can be triggered as soon as a short request is blocked in the queue by long requests running on workers. The rst system, "TS 4`s" takes 2`s to propagate a preemption event to a worker, and 2 additional `s to preempt the running request. "TS 2`s" and "TS 1`s" operate similarly. "TS 0`s" represents an ideal system with instant preemption and no overheads. Figure 10 shows their impact on requests slowdown, compared to DARC. Unsurprisingly, the ideal system performs similarly or better than DARC. As preemption speed increases, short requests are better protected and long requests suer less in the process. However, at the microsecond scale, even 1`s overheads result in 30% less sustainable load, for a slowdown target of 10 for the short requests. In response to implementation and tuning challenges for preemption at the `s scale, DARC proposes a complementary resource partitioning technique that alleviates the need for interrupts. Finally, preemption comes with a second class of challenges related to practicality. One has to carefully re-work existing applications to ensure preemption cannot happen during critical sectionsmemory management, interaction with thread local storage, etc. -or non re-entrant functions. This represents considerable eorts and encourages other designs trade-o such as semi-cooperative scheduling [17]. DARC in the datacenter ecosystem. Though not a focus of this paper, DARC can cooperate with an allocator to obtain and release cores, adapting to load changes and updating reservations during such events. In the event of a system overload, DARC will keep prioritizing short requests as far as possible, triggering ow control for longer requests rst.
Kernel-bypass. Bypassing a general-purpose kernel to provide application-tailored services has been revisited regularly over the past fty years. Some notable examples include the RC 4000 multi-programming system [37], Hydra [88], Mach [1], Chorus [77], SPIN [16], and Exokernel [31].
More recently, faster networks and stagnating CPU speeds have led researchers to look more closely at user-level network stacks [47,53], to provide high-performance storage systems [19,55,58,71], access to disaggregated memory [4], user-level network services [53] such as eRPC [49], and fast I/O processing (e.g., IX [14] and Chronos [50]). Similarly, user-level scheduling has been explored with ZygOS [75] and Shinjuku [48], which focus on improving tail latency by implementing centralized dispatch policies and user-level preemption, both of which outperform current decentralized oerings, as is well understood by theory [57,87,90]. DARC builds on this recent line of work with a more applicationcustomized solution, motivated by recent insights when observing performance gain from sharing application-level information with the dataplane [23,52,61], and "common case service acceleration", which can improve tail latency for important requests [64]. DARC multi-queue policy could be integrated with existing kernel-bypass schedulers [48,73,75], with the merit that programmers could decide whether providing request classiers is worthwhile for their workload. In fact, we originally designed Perséphone for the Demikernel Library OS Architecture [89], with the goal of integrating user-level insights to a wide range of datapaths.
Scheduling Policies: Recent works on kernel-bypass and microsecond-scale applications have revived research interest in scheduling policies, specically for tail-tolerance. We compare DARC with existing policies proposed for process or packet scheduling, and identied the best t for each. Table 5 summarizes our ndings. DARC shares ideas with Fixed Priority (FP) scheduling without suering from head-of-line blocking and with Cycle Stealing with Central Queue (CSCQ [42]), but does not impose limits on stealing for shorter requests. It also shares ideas with Static Partitioning (SP) without being as work conservation avoidant, thus being able to absorb bursts. DARC targets applications with high service time dispersion similarly to Processor Sharing policies, implemented as the Completely Fair Scheduler [67], Borrowed Virtual Time [29], and Multi-Level Feedback Queue [6] in commodity operating systems and variants of these on datacenter operating systems [48]. Processor sharing policies, despite being application agnostic, are expensive or impossible to implement in many environments, e.g., the public cloud. DARC is, to our best knowledge, the rst application-aware and non-preemptive policy that classies requests to improve RPC tail latency and can be implemented on a kernel-bypassed system serving microsecond-scale requests. We note that existing work has specically made use of non work conservation to reduce resource contention in SMT architectures [33,76,82], though with a focus on instruction throughput rather than tail latency for datacenter workloads.
In-network end-host scheduling. R2P2 [56] and Metron [51] propose to integrate core scheduling in the network. Loom [83] proposes a novel NIC design and OS/NIC abstraction to express rich hierarchies of network scheduling and trac shaping policies across tenants. Our work is orthogonal since request classiers can be ooaded to the network. eRSS [78] scaling groups oer the possibility to schedule request groups, which works only on network headers and requires a specic programming model from the NIC. RSS++ [9] addresses RSS vulnerability to trac imbalance but cannot handle variability in application-request processing times. Intel recently introduced Application Device Queues (ADQ) [44], a feature for applications to reserve NIC hardware queues. ADQ requires specic network interfaces (currently Intel's Ethernet 800 Series) and does not allow applications to further partition reserved queues by request type. Finally, recent progress in network hardware could enable instantiating DARC either in a programmable switch using a PIFO scheduling transaction [81], or directly in the end-host hardware using the NanoPU hardware thread scheduler [43] or a SmartNIC.
Network scheduling for tail latency. Prioritizing packets to improve tail latency has been extensively studied in the networking literature [3,8,34,36,59,68,69]. As analyzed by Mushtaq et al. [70], this line of work uses priority queues in switches to approximate Shortest Remaining Processing Time (SRPT) scheduling and avoid head-of-line blocking caused by FIFO policies. Dedicating more CPU resources to short requests is similar to prioritizing packets belonging to short ows, but whereas network devices schedule at the granularity of packets -bounded by MTU sizes -and preempt long ows by not sending their packets, there is no aordable way to preempt a long request once dispatched at a CPU core within microseconds. DARC eciently partitions CPU resources among requests by proling their CPU demand and enabling work conservation only for short requests, capping resources allocated to long requests and resulting in a similar trade o than Homa [68], pFabric [3], or HULL [2].
Other eorts to improve tail latency. Haque et al. [39] exploit DVFS and heterogeneous CPUs to speed up long requests in latency sensitive workloads at the expense of short requests, with the goal of improving overall tail latency. Our technique is orthogonal to such optimization, since DARC denes a clear target to congure power and core settings for given request types. Another line of work adapts the degree of parallelism of long requests and improves overall tail latency [38,46], but this comes at the cost of shorter requests This paper proposes Perséphone, a new kernel-bypass OS scheduler implementing DARC, an application aware, non work conserving policy. DARC maintains good tail latency for shorter requests in heavy-tailed workloads that cannot aord the overheads of existing techniques such as work stealing and preemption. DARC proles requests and dedicates cores to shorter requests, guaranteeing they will not be blocked behind long requests. Our prototype of Perséphone maintains good tail latency for shorter requests and can handle higher loads with the same amount of cores than state-of-the-art kernel-bypass schedulers, overall better utilizing datacenter resources.
https://github.com/maxdml/psp