  To provide quick responses to users, Internet companies rely on online data
systems able to answer queries in milliseconds. These systems employ
complementary overload management techniques to ensure they provide a
continued, acceptable service through-out traffic surges, where 'acceptable'
partly means that serviced queries meet or track closely their response time
objectives. Thus, in this paper we present Bouncer, an admission control policy
aimed to keep admitted queries under or near their service level objectives
(SLOs) on percentile response times. It computes inexpensive estimates of
percentile response times for every incoming query and compares the estimates
against the objective values to decide whether to accept or reject the query.
Bouncer allows assigning separate SLOs to different classes of queries in the
workload, implements early rejections to let clients react promptly and to help
data systems avoid doing useless work, and complements other load shedding
policies that guard systems from exceeding their capacity. Moreover, we propose
two starvation avoidance strategies that supplement Bouncer's basic formulation
and prevent query types from receiving no service (starving).
  We evaluate Bouncer and its starvation-avoiding variants against other
policies in simulation and on a production-grade in-memory distributed graph
database. Our results show that Bouncer and its variants allow admitted queries
to meet or stay close to the SLOs when the other policies do not. They also
report fewer overall rejections, a small overhead, and with the given latency
SLOs, they let the system reach high utilization. In addition, we observe 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.
