Admission Control with Response Time Objectives for Low-latency Online Data Systems

Social media, e-commerce, and other Internet companies rely on low-latency online data systems (DeCandia et al., 2007; Bronson et al., 2013; Corbett et al., 2013; Zhan et al., 2019; Corp., 2022b, 2018) to provide quick responses to their users. These large-scale systems answer queries from multiple clients demanding millisecond-scale response times (e.g., 1ms–100ms), and each of their servers can receive tens or even a few hundreds of thousand queries per second (QPS). The queries are normally of various types with different complexity and latency characteristics. Customers usually want to know the response times a system can offer to their queries to ensure their latency requirements are met. To set clear performance goals for themselves and realistic expectations for customers, system operators establish service level objectives (SLOs) (Jones et al., 2017) on query response times. These latency SLOs are typically defined in terms of percentiles (e.g., p50=10ms and p90=60ms), and having separate SLOs for different classes of queries is common.

With users driving the inbound traffic, they can cause surges in which numerous simultaneous requests exceed the maximum load a serving system can handle with the provisioned resources (LeFebvre, 2001; Kim, 2018; Purnell, 2020). Besides legitimate, well-intended users, malicious agents launching distributed denial of service (DDoS) attacks (Jonker et al., 2017; Kopp et al., 2021; Toh et al., 2022) can exacerbate the situation. Even with the inbound traffic below the tolerable limit, there are other reasons for online data systems to become overloaded. Unplanned reduction in the system’s capacity¹¹1 i.e., the maximal traffic load, in QPS, that the system is able to sustain. can result from network outages, node failures, configuration changes, and software bugs. Moreover, Internet companies typically conduct live traffic load tests (Veeraraghavan et al., 2016; Mallapur and Kehoe, 2017) on a regular basis (e.g., daily) to confirm that their system infrastructure can handle the extra load when outages in one or more data centers occur.

To ensure continued operation throughout possible load surges, online data systems (and their surrounding infrastructure) employ complementary overload management techniques (Cuervo, 2017a; Zhang et al., 2018) that tackle the problem from different angles, such as load balancing (Lewandowski, 2017; Cuervo, 2017b; Chou et al., 2019), per-client quotas and client-side throttling (Cuervo, 2017a; Szopa et al., 2016), resource scheduling (Colajanni et al., 1997; Schroeder and Harchol-Balter, 2006), and graceful degradation (Liu et al., 1994; Mittal, 2016; Agarwal et al., 2013; Ulrich, 2017). Another angle is admission control (load shedding) (Chen and Mohapatra, 2002; Welsh and Culler, 2003; Elnikety et al., 2004; Blanquer et al., 2005; Tozer et al., 2010; Xiong et al., 2011; Zhang, 2014; Ulrich, 2017; Zhou et al., 2018; Hao et al., 2017; Cho et al., 2020; Noll et al., 2019; Chapnik et al., 2022), which is the focus of this paper.

Based on the system’s load status, an admission control module decides to accept or reject client requests so that the system continues providing an acceptable service when receiving excessive traffic. Some admission control techniques (e.g., (Heiss and Wagner, 1991; Mönkeberg and Weikum, 1992; Elnikety et al., 2004)) concentrate on allowing the system to serve a sustained throughput without exceeding its capacity, protecting it from performance collapse. But, for online data systems “acceptable service” also means that admitted queries should meet or at least track closely the latency SLOs. Hence, in this paper we present Bouncer (§3), a measurement-based admission control policy whose main goal is to keep serviced queries under or close to their latency SLOs defined in terms of percentile response times. It implements early rejections (Ulrich, 2017; Hao et al., 2017; Cho et al., 2020) to help data systems avoid doing useless work and give clients more flexibility to failover promptly. It is also designed to complement other admission control policies that keep systems from exceeding their capacity. For workloads with diverse queries, Bouncer allows assigning SLOs per query type.

The main challenge here lies in estimating percentile response times quickly and effectively for query-by-query acceptance decision making. Bouncer computes estimates of percentile response times for each incoming query by combining inexpensive approximations of queue wait time and processing time from recent query executions, and compares the estimates with the objective values to decide to accept or reject the query. An additional issue is that Bouncer’s basic formulation may systematically deny service to query types, especially under heavy load. To prevent query types from receiving no service (starving), we supplement Bouncer with two alternative starvation avoidance strategies (§4).

We evaluate Bouncer and its starvation-avoiding variants against several in-house policies, in simulation (§5.3) and on LIquid, a production-grade in-memory distributed graph database (§5.4). We describe the in-house policies in §5.2 and provide an overview of LIquid (Meyer et al., 2020a, b) in §5.1. We show that Bouncer and its variants are able to make effective decisions, and allow admitted queries to meet or stay near the latency objectives when the other policies do not. They report fewer overall rejections (15%$\sim$30%) than the other policies, a small overhead (mean=18$\mu$s) for millisecond-scale queries, and with the given latency SLOs, they let the system reach high utilization. Further, we show that the proposed strategies can stop query starvation, but at the expense of a modest increase in overall rejections and causing SLO violations for serviced requests; however, our results on LIquid graph database suggest the violation counts may be acceptable in practice.

To sum up, the contributions of this paper are:

• •

  an admission control policy, called Bouncer, that promptly rejects queries expected to surpass their response time objectives and lets admitted queries meet or stay near theirs;

• •

  two starvation avoidance strategies – acceptance-allowance (§4.1) and helping-the-underserved (§4.2) – that complement Bouncer and protect query types from systemic service denial; and

• •

  an extensive evaluation of Bouncer and its starvation-avoiding variants in simulation and on LIquid (i.e., a real system).

The paper ends with the related work (§6), our conclusions and future work (§7). In addition, it provides a supplementary discussion about our plan to handle cold starts and traffic lulls in Bouncer (Appendix A) and practical considerations (Appendix B) related to the selection of percentiles for the latency SLOs and Bouncer’s configuration effort.

In this section, we discuss the motivation behind the main design decisions in Bouncer.

Bouncer is an admission control policy that makes acceptance decisions based on the latency SLOs of queries. It estimates percentile response times for each incoming query and compares them with the target percentile response times in the SLO to decide whether to accept or reject the query.

Bouncer is built atop a software framework that resembles a stage in the staged event-driven architecture (SEDA) with the multi-class overload controller (Welsh and Culler, 2003), and it facilitates implementing thread-safe, highly-concurrent policies. Figure 1 depicts the query processing in the framework. When a new query arrives, the policy examines it and, based on metrics gathered from recent executions, decides to admit or reject it. If admitted, the query is inserted into the FIFO queue to wait for its turn to be processed; otherwise, the policy drops it and instructs the server host to reply with an error response. A fixed number of query engine processes (or threads) dequeue the admitted queries and process each independently. The framework offers methods for the policies to record time intervals and metrics they need (e.g., queue wait time, processing time, queue length, and rejection counts) at several points in the process: Point 1, after the admission or rejection decision is made; Point 2, after a query is dequeued for processing; and Point 3, after a query has been processed and before the response is sent back to the client.

We assume that every request includes a short string indicating the type of the query it carries (e.g., part of the REST URL endpoint’s path or the name of a datalog-like rule (Abiteboul et al., 1995; Meyer et al., 2020b)). Thus, the policy is configured with strings denoting the query types and for each type, a latency SLO with the target percentile response times; for example: "Fast":{p50=10ms, p90=90ms}, "Slow":{p50=60ms, p90=270ms}, and "default":{p50=30ms, p90=400ms}.³³3 These query types are merely for illustration purpose; in practice, they often have more sensible names (e.g., GetFriends and GraphDistance). Note that default is a “catch-all” query type.

The time a query $Q$ spends in the FIFO queue is its queue wait time; i.e., $wt(Q)=t_{dequeued}(Q)-t_{enqueued}(Q)$. We define a query $Q$’s processing time, denoted as $pt(Q)$, as the time interval from the instant at which $Q$ is pulled from the head of the queue to the instant at which $Q$ has been fully processed and the response is ready to be sent back to the client; i.e., $pt(Q)=t_{completed}(Q)-t_{dequeued}(Q)$. Then, the response time of a query $Q$ is:

where $\xi$ is some additional time the server host takes (e.g., in the network stack and operating system) to handle the query. In our experience $\xi$ is often negligible and we assume $\xi=0$.

Separate query types often have different processing time distributions that vary over time. Bouncer adopts the natural approach of maintaining approximations for these distributions in histograms, one per query type (including default); it periodically updates the histograms at run time using a dual-buffer technique.⁴⁴4 While one histogram is only read, a second histogram is being populated. At the end of a time interval the new and old histograms are swapped atomically, and the old histogram is reset before being populated again.

Figure 2 illustrates Bouncer’s operation. For every query $Q$ that arrives at the host, it computes an estimate of the mean queue wait time that $Q$ will experience as:

where $QT$ is the set of query types the policy recognizes, including default; $count(type)$ is the number of queries of the given $type$ currently in the queue; $pt_{mean}(type)$ is the mean processing time for queries of the given $type$, obtained from the corresponding histogram; and $P$ is the number of query engine processes running on the host (i.e., the level of task parallelism for query processing). Bouncer maintains per-type atomic counts of the queries currently in the queue, and updates the counts as queries are enqueued and dequeued. The histograms and query counts are stored in hash maps with query types as the keys for easy and quick access.

Bouncer estimates the percentile response times of $Q$ as:

where $Type(Q)$ returns the type of the query $Q$, and $pt_{p50}(type)$ and $pt_{p90}(type)$ are the 50th- and 90th-percentile processing times for queries of the given $type$, obtained from the corresponding histograms. Finally, after calculating $ert_{p50}$ and $ert_{p90}$, Bouncer decides to accept or reject $Q$ according to Algorithm 1.

Note that Equations 2, 3, and 4, rather than precise expressions, are inexpensive estimations we adopt to keep the policy’s overhead low. This trade-off of accuracy for speed is of practical importance because the computations Bouncer does are in the critical path of the queries. Our experiments (§5) show, however, that the policy is effective despite this accuracy loss. Moreover, this policy formulation can be easily modified to support SLOs with other percentile response times (e.g., p99) in lieu of or in addition to p50 and p90, and to adopt different logical expressions for acceptance decision making in Algorithm 1. The evaluation of alternative formulations for Bouncer is left as future work, but Appendix B offers some practical considerations about selecting percentiles for latency SLOs.

Also note that the Bouncer policy, as formulated above, suffers from two problems. The first one is query starvation since the policy may systematically deny service to query types. The second problem is that Bouncer is susceptible to cold starts and lulls in traffic as its histograms start in a blank state and may become empty for query types with intermittent patterns. We address query starvation in the next section, but leave the issue of cold starts and traffic lulls as future work and just discuss our plan in Appendix A.

Query types frequently have latency SLOs that are tighter than those of other query types (i.e., their percentile response times are closer to the values in their SLOs). Since admitted queries share the same FIFO queue, it is possible that queries with looser SLOs cause queries with tighter SLOs to be rejected in large numbers, especially at high QPS. Figure 3 illustrates the problem, which we reproduced by sending traffic at a high rate to an experimental cluster running LIquid graph database (§5.1) with basic Bouncer. We selected two types of queries, identified as FAST and SLOW, and generated traffic from a set of millions queries sampled from production. Both queries types are configured with $SLO_{p50}$=18ms and $SLO_{p90}$=50ms, shown in dotted lines; thus, the SLO is tighter for the SLOW queries than for the FAST ones. The figure reports the p50 and p90 response time estimates for both query types in a one-second interval. We can see that the FAST queries make the SLOW queries “starve” as nearly 100% of the SLOW queries exceed the SLO and get rejected in the interval. Therefore, Bouncer needs to alleviate query starvation, and we discuss two alternative strategies for that purpose next.

In this section, we evaluate Bouncer (§3) and its variants with the starvation avoidance strategies discussed in §4. We conduct two studies, one using simulation (§5.3) and the other on LIquid distributed graph database (§5.4), that compare Bouncer with other policies. We first give an overview of LIquid and then describe the policies we evaluate Bouncer against. After presenting the studies, the section ends with a summary of the results (§5.6).

Admission control has been applied to networking (Jamin et al., 1997; Nam et al., 2008; Yang et al., 2016), operating systems (Hao et al., 2017), web services (Chen and Mohapatra, 2002; Welsh and Culler, 2003; Blanquer et al., 2005; Zhou et al., 2018), complex event processing over data streams (Slo et al., 2020; Zhao et al., 2020; Chapnik et al., 2022), and databases (Elnikety et al., 2004; Tozer et al., 2010; Xiong et al., 2011; Zhang, 2014; Noll et al., 2019; SAP, 2022; IBM, 2022; Doran et al., 2022; Corp., 2022c). Here we discuss prior work closely related to Bouncer.

Admission control techniques can be divided in two groups: 1) those that distinguish between request types (e.g., (Elnikety et al., 2004; Blanquer et al., 2005; Tozer et al., 2010; Xiong et al., 2011)), and 2) those that do not (e.g., (Mönkeberg and Weikum, 1992; Schroeder et al., 2006; Zhou and Yang, 2006; Bartolini et al., 2009)). Like Bouncer, Gatekeeper (Elnikety et al., 2004) belongs to the first group and implements a measurement-based approach, but with different goals and response time estimates. Gatekeeper lets the system serve a sustained throughput without exceeding its capacity, and uses moving averages to estimate mean response times. Bouncer instead ensures that serviced requests meet or track closely their latency SLOs and maintains histograms to estimate percentile response times. While Bouncer strives for early rejections, Gatekeeper does not as it lets the requests time out in the scheduling queue. Gatekeeper implements a shortest-job-first (SJF) scheduler with an aging mechanism (Cherkasova, 1998) to reduce the overall average response time and prevent longer-running queries from starving. We also supplement Bouncer with starvation avoidance strategies that, rather than deferring query executions, make decisions on the spot at query arrival. LIquid currently processes queries in FIFO order and evaluating other scheduling disciplines is left as future work.

Quorum (Blanquer et al., 2005) also differentiates request types and implements a non-invasive, measurement-based approach to quality of service for Internet services. Quorum and Bouncer perform admission control at the system’s entrance point, but for Quorum the system is an Internet site whereas for Bouncer a two-tier database. Quorum ensures that serviced requests of different types meet their response time guarantees, expressed as averages or percentiles. It selectively drops requests after being dequeued; by contrast, Bouncer rejects requests before being enqueued. Quorum prevents request types from starving by ensuring they get a large enough fraction of capacity to guarantee their required minimum throughput at all times. Contrarily, Bouncer does not control the capacity given to query types and applies another kind of strategies to avoid query starvation.

Q-Cop (Tozer et al., 2010), like Bouncer, focuses on admission control, but seeks to minimize the number of request timeouts. Q-Cop builds a linear regression model from offline experiments, and uses the model to predict the processing time of a newly arriving query based on the query’s type and the mix of queries being executed by the database system. Q-Cop’s model and Bouncer’s response time estimates have similar formulations, and their decision processes are alike too. But, rather than relying on a model trained offline, Bouncer estimates percentile response times based on recent processing times and the number of queries in the queue at the time. Besides, Q-Cop’s model only captures average execution times; hence, it cannot enforce latency SLOs defined in terms of percentiles. Another prediction-based approach is ActiveSLA (Xiong et al., 2011), which makes acceptance decisions to improve the profit of database-as-a-service providers while considering the service level agreements (SLA) with their clients. It uses a non-linear classification model that considers the query types and mix, among other features, to estimate the probability of a new query meeting its deadline. Then, based on the probability, ActiveSLA decides whether to admit the query with a profit optimization objective, with the expected profit derived from the SLA. In contrast, Bouncer has no notion of profit and does not seek to maximize it. Unfortunately, ActiveSLA’s overhead is much (1000x) higher than Bouncer’s and becomes prohibitive for systems like LIquid offering millisecond-scale response times. In addition, ActiveSLA continually rebuilds the model to reduce the human effort on model retraining. But, for production data systems like LIquid, queries are regularly added and retired, altering the query mix. Hence, ActiveSLA’s model, as well as Q-Cop’s, would need retraining more often than their authors anticipate, not only when the database or hardware configurations change. For Bouncer, model retraining is not a concern.

Bouncer’s overhead is low for millisecond-scale queries, which is key for request-by-request acceptance decisions. Similarly, but at the operating-system level, MittOS (Hao et al., 2017) computes latency estimates per IO operation in few $\mu$s or less, and embraces quick rejections for IOs that cannot be served by a deadline. Built within the storage stack, it exposes a SLO-aware interface to help reduce IO completion time for data-parallel applications. MittOS receives latency deadlines from applications and requires white-box knowledge of devices and resources, whereas Bouncer adopts a black-box approach and its latency SLOs are percentiles. MittOS neither considers call types nor tackles starvation, but applications could do so since IO calls are given individual deadlines. Targeting microsecond-scale remote procedure calls, Breakwater (Cho et al., 2020) implements a credit-based admission control scheme with demand speculation and overcommitment handling. While offering fast rejections, it is oblivious to query types and only considers queue wait times to determine the credits to be distributed distribution among clients. Instead, Bouncer considers queue wait times and processing times to estimate percentile response times for queries.

We presented Bouncer, an admission control policy that makes query-by-query decisions based on latency SLOs defined in terms of percentile response times. It combines inexpensive approximations of queue wait time and processing time to estimate percentile response times for each query, and compares the estimates with the objective values to decide to accept or reject the query. It takes into account that production workloads often include various types of queries with different latency characteristics, and allows assigning SLOs per query type. In addition, we studied two starvation avoidance strategies (acceptance-allowance and helping-the-underserved) that supplement Bouncer’s basic formulation to prevent query types from systematically receiving no service. We also conducted an extensive evaluation of Bouncer and its starvation-avoiding variants against several in-house policies in simulation and on LIquid graph database. A summary of our experimental results is given in §5.6.

As part of our future work, we plan to evaluate alternative formulations for Bouncer that use higher-order percentile response times, apply different logical expressions for decision making, and update processing time histograms in a sliding window, instead of non-overlapping windows. We also intend to extend Bouncer to support queries served based on priorities (rather than in FIFO order), and will consider adapting it to other query scheduling disciplines.

Bouncer is currently susceptible to cold starts and lulls in traffic because its decisions making relies on per-query-type processing time histograms, which are initially in a blank state and become empty when queries of certain types stop coming for some time. We expect Bouncer to handle these issues by itself, with no need of supplementary infrastructure and no extra burden on system’s operators. Appendix A discusses our plan in this regard.

Finally, we are interested in evaluating Bouncer against other policies in the literature as well as its applicability within more general overload management solutions, such as Quorum (Blanquer et al., 2005) (in its selective dropping module) and LinkedIn’s Hodor (Barkley, 2022).