Contention-Aware Lock Scheduling for Transactional
Databases
Boyu Tian

Jiamin Huang

Barzan Mozafari

Grant Schoenebeck

University of Michigan
Ann Arbor, MI, USA{bytian, jiamin, mozafari, schoeneb}@umich.edu

ABSTRACTby solving the data contention problem. For example, before a transaction accesses a database object, it has to acquire the corresponding lock; if the transaction fails to get
a lock immediately, it is blocked until the system grants it
the lock. This poses a fundamental question: when multiple
transactions are waiting for a lock on the same object, whichshould be granted first when the object becomes available?
This question, which we call lock scheduling, has received
surprisingly little attention, despite the large body of workon concurrency control and locking protocols [15, 46, 7, 68,
18, 40, 50, 54, 23]. In fact, almost all existing DBMSs1 rely
on variants of the first-in, first-out (FIFO) strategy, which
grants (all) compatible lock requests based on their arrival
time in the queue [2, 3, 4, 5, 6]. In this paper, we carefully
study the problem of lock scheduling and show that it has
significant ramifications on overall performance of a DBMS.

Lock managers are among the most studied components
in concurrency control and transactional systems. However, one question seems to have been generally overlooked:“When there are multiple lock requests on the same object,which one(s) should be granted first?”
Nearly all existing systems rely on a FIFO (first in, firstout) strategy to decide which transaction(s) to grant thelock to. In this paper, however, we show that the lock
scheduling choices have significant ramifications on the overall performance of a transactional system. Despite the large
body of research on job scheduling outside the database context, lock scheduling presents subtle but challenging requirements that render existing results on scheduling inapt fora transactional database. By carefully studying this problem, we present the concept of contention-aware scheduling,show the hardness of the problem, and propose novel lock
scheduling algorithms (LDSF and bLDSF), which guarantee
a constant factor approximation of the best scheduling. We
conduct extensive experiments using a popular database on
both TPC-C and a microbenchmark. Compared to FIFO—
the default scheduler in most database systems—our bLDSF
algorithm yields up to 300x speedup in overall transaction
latency. Alternatively, our LDSF algorithm, which is simpler and achieves comparable performance to bLDSF, hasalready been adopted by open-source community, and waschosen as the default scheduling strategy in MySQL 8.0.3+.

Related Work — There is a long history of research onscheduling in a general context [25, 42, 69, 70, 64, 41, 35,62], whereby a set of jobs is to be scheduled on a set of processors such that a goal function is minimized, e.g., the sumof (weighted) completion times [64, 41, 39] or the varianceof the completion or wait times [14, 17, 76, 49, 28]. There isalso work on scheduling in a real-time database context [75,40, 7, 36, 74], where the goal is to minimize the total tardiness or the number of transactions missing their deadlines.
In this paper, we address the problem of lock scheduling ina transactional context, where jobs are transactions and processors are locks, and the scheduling decision is about whichlocks to grant to which transactions. However, our transactional context makes this problem quite di↵erent than thewell-studied variants of the scheduling problem. First, unlike generic scheduling problems, where at most one job can
be scheduled on each processor, a lock may be held in either
exclusive or shared modes. The fact that transactions cansometimes share the same resources (i.e., shared locks) significantly complicates the problem (see Section 2.4). Moreover, once a lock is granted to a transaction, the same transaction may later request another lock (as opposed to jobs
requesting all of their needed resources upfront). Finally,in the scheduling literature, the execution time of each job
is assumed to be known upon its arrival [52, 70, 14, 76],
whereas the execution time of a transaction is often unknowna priori.
Although there are scheduling algorithms designed forreal-time databases [55, 71, 77, 13], they are not applica-

PVLDB Reference Format:
Boyu Tian, Jiamin Huang, Barzan Mozafari, Grant Schoenebeck.
Contention-Aware Lock Scheduling for Transactional Databases.
PVLDB, 11 (5): 648
x-yyyy,- 662, 2018.
DOI: https://doi.org/10.1145/3177732.3177740

1.

INTRODUCTION

Lock management forms the backbone of concurrency control in modern software, including many distributed systems
and transactional databases. A lock manager guarantees
both correctness and efficiency of a concurrent application
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Articles from this volume were invited to present
their results at The 44th International Conference on Very Large Data Bases,
August 2018, Rio de Janeiro, Brazil.
Proceedings of the VLDB Endowment, Vol. 11, No. 5
Copyright 2018 VLDB Endowment 2150-8097/18/1.
DOI: https://doi.org/10.1145/3177732.3177740

1

The only exceptions are MySQL and MariaDB, which haverecently adopted our Variance-Aware Transaction Scheduling (VATS) [44] (see Section 7).

648

ble in a general DBMS context. For example, real-time settings assume that each transaction comes with a deadline,
whereas most database workloads do not have explicit deadlines. Instead, most workloads wish to minimize latency ormaximize throughput.

as a microbenchmark. Our results confirm that, compared to the commonly-used FIFO strategy, LDSF andbLDSF reduce mean transaction latencies by up to 300x
and 290x, respectively. They also increase throughput by
up to 6.5x and 5.5x. As a result, LDSF (which is simpler
than bLDSF) has already been adopted as the defaultscheduling algorithm in MySQL [1] as of 8.0.3+.

Challenges — Several aspects of lock scheduling make ita uniquely challenging problem, particularly under the performance considerations of a real-world DBMS.
1. An online problem. At the time of granting a lockto a transaction, we do not know when the lock will be
released, since the transaction’s execution time will only
be known once it is finished.
2. Dependencies. In a DBMS, there are dependencies
among concurrent transactions when one is waiting for alock held by another. In practice, these dependencies canbe quite complex, as each transaction can hold locks onseveral objects and several transactions can hold sharedlocks on the same object.
3. Non-uniform access patterns. Not all objects in the
database are equally popular. Also, di↵erent transaction
types might each have a di↵erent access pattern.
4. Multiple locking modes. The possibility of granting
a lock to one writer exclusively or to multiple readers isa source of great complexity (see Section 2.4).

2.

PROBLEM STATEMENT

In this section, we first describe our problem setting anddefine dependency graphs. We then formally state the lock
scheduling problem.

2.1

Background: Locking Protocols

Locks are the most commonly used mechanism for ensuring consistency when a set of shared objects are concurrently
accessed by multiple transactions (or applications). In alocking system, there are two main types of locks: sharedlocks and exclusive locks. Before a transaction can readan object (e.g., a row), it must first acquire a shared lock(a.k.a. read lock) on that object. Likewise, before a transaction can write to or update an object, it must acquire an
exclusive lock (a.k.a. write lock) on that object. A shared
lock can be granted on an object as long as no exclusive
locks are currently held on that object. However, an exclusive lock on an object can be granted only if there are noother locks currently held on that object. We focus on thestrict 2-phase locking (strict 2PL) protocol: once a lock isgranted to a transaction, it is held until that transaction
ends. Once a transaction finishes execution (i.e., it commits
or gets aborted), it releases all of its locks.

Contributions — In this paper, to the best of our knowledge, we present the first formal study of lock schedulingproblem with a goal of minimizing transaction latencies ina DBMS context. Furthermore, we propose a contentionaware transaction scheduling algorithm, which captures thecontention and the dependencies among concurrent transactions. The key insight is that a transaction blocking manyothers should be scheduled earlier. We carefully study thedifficulty of lock scheduling and the optimality of our algorithm. Most importantly, we show that our results are notmerely theoretical, but lead to dramatic speedups in a realworld DBMS. Despite decades of research on all aspects oftransaction processing, lock scheduling seems to have goneunnoticed, to the extent that nearly all DBMSs still use
FIFO. Our ultimate hope is that our results draw attention
to the importance of lock scheduling on the overall performance of a transactional system.
In summary, we make the following contributions:
1. We propose a contention-aware lock scheduling algorithm,
called Largest-Dependency-Set-First (LDSF). We provethat, in the absence of shared locks, LDSF is optimal interms of the expected mean latency (Theorem 2). With
shared locks, we prove that LDSF is a constant factor
approximation of the optimal scheduling under certain
regularity constraints (Theorem 3).
2. We propose the idea of granting only some of the shared
lock requests on an object (as opposed to granting themall ). We study the difficulty of the scheduling problem under this setting (Theorem 5), and propose anotheralgorithm, called bLDSF (batched Largest-DependencySet-First), which improves upon LDSF in this setting.
We prove that bLDSF is also a constant factor approximation of the optimal scheduling (Theorem 6).
3. In addition to our theoretical analysis, we use a real-world
DBMS and extensive experiments to empirically evaluate our algorithms on the TPC-C benchmark, as well2.2

Dependency Graph

Given the set T of transactions currently in the system,and the set O of objects in the database, we define thedependency graph of the system as an edge-labeled graph
G = (V, E, L). The vertices of the graph V = T [ O consist of the current transactions and objects. The edges of
the graph E ✓ T ⇥ O [ O ⇥ T describe the locking relationships among the objects and transactions. Specifically, fortransaction t 2 T and object o 2 O,
• (t, o) 2 E if t is waiting for a lock on o;• (o, t) 2 E if t already holds a lock on o.
The label L : E ! {S, X} indicates the lock type:• L(t, o) = X if t is waiting for an exclusive lock on o;• L(t, o) = S if t is waiting for a shared lock on o;• L(o, t) = X if t already holds an exclusive lock on o;• L(o, t) = S if t already holds a shared lock on o.
We assume that deadlocks are rare and are handled by an
external process (e.g., a deadlock detection and resolution
module). Thus, for simplicity, we assume that the dependency graph G is always a directed acyclic graph (DAG).

2.3

Lock Scheduling

A lock scheduler makes decisions about which transactions
are granted locks upon one or both of the following events:(i) when a transaction requests a lock, and (ii) when a lockis released by a transaction.2 Let G be the set of all possible
2

These are the only situations in which the dependency
graph changes. If a scheduler grants locks at other times,
the same decision could have been made upon the previous

649

Notation
T
O
G
V
E
L
A
lA (t)¯lA (t)¯l(A)Description
the set of transactions in the system
the set of objects in the databasethe dependency graph of the system
vertices in the dependency graphedges in the dependency graphlabels of the edges indicating the lock typea scheduling algorithm
the latency of transaction t under A
the expectation of lA (t)the expected transaction latency under A

Theorem 1. Given a dependency graph G, when a transaction t releases a lock (S or X) on object o, it is NP-hard todetermine which pending lock requests to grant, in order tominimize the expected transaction latency. The result holds
even if all transactions have the same execution time, andno transaction requests additional locks in the future.3
Given the NP-hardness of the problem in general, in therest of this paper, we propose algorithms that guarantee aconstant-factor approximation of the optimal scheduling interms of the expected transaction latency.

3.

Table 1: Table of Notations.
dependency graphs of the system. A scheduling algorithm
A = (Areq , Arel ) is a pair of functions Areq , Arel : G ⇥ O ⇥T ⇥ {S, X} ! 2T . For example, when transaction t requests
an exclusive lock on object o, Areq (G, o, t, X) determines
which of the transactions currently waiting for a lock on o(including t itself) should be granted their requested lockon o, given the dependency graph G of the system. (Notethat the types of locks requested by transactions other thant are captured in G.) Likewise, when transaction t releases ashared lock on object o, Arel (G, o, t, S) determines which of
the transactions currently waiting for a lock on o should be
granted their requested lock, given the dependency graph G.
When all transactions holding a lock on an object o release
the lock, we say that o has become available. When thelock request of a transaction t is granted, we say that t isscheduled.
Since the execution time of each transaction is typicallyunknown in advance, we model their execution time usinga random variable with expectation R. Given a particularscheduling algorithm A, we define the latency of a transaction t, denoted by lA (t), as its execution time plus the total
time it has been blocked waiting for various locks. SincelA (t) is a random variable, we denote its expectation as¯
lA (t). We use ¯l(A) to denote the expected transaction latency under algorithm A, which is defined as the average ofthe expected
P latencies of all transactions in the system, i.e.,¯l(A) = |T1 | t2T ¯lA (t).
Our goal is to find a lock scheduling algorithm underwhich the expected transaction latency is minimized. To
ensure consistency and isolation, in most database systems
Areq simply grants a lock to the requesting transaction only
when (i) no lock is held on the object, or (ii) the currently
held lock and the requested lock are compatible and notransaction in the queue has an incompatible lock request.
This choice of Areq also ensures that transactions requestingexclusive locks are not starved. The key challenge in lock
scheduling, then, is choosing an Arel such that the expectedtransaction latency is minimized.

2.4

CONTENTION-AWARE SCHEDULINGWe define contention-aware scheduling as any algorithm
that prioritizes transactions based on their impact on theoverall contention in the system. First, we study several
heuristics for comparing the contribution of di↵erent transactions to the overall contention, and illustrate their shortcomings through intuitive examples. We then propose a particular contention-aware scheduling that formally quantifies
this contribution, and guarantees a constant-factor approximation of the optimal scheduling when shared locks are notheld by too many transactions. (Later, in Section 4, we generalize this algorithm for situations where this assumption
does not hold.)

3.1

Capturing Contention

The degree of contention in a database system is directly
related to the number of transactions concurrently requesting conflicting locks on the same objects.
For example, a transaction holding an exclusive lock on a
popular object will naturally block many other transactions
requesting a lock on that same object. If such a transaction
is itself blocked (e.g., waiting for a lock on a di↵erent object),
it will negatively a↵ect the latency of many transactions, increasing overall contention in the system. Thus, our goal incontention-aware scheduling is to determine which transactions have a more important role in reducing the overall
contention in the system, so that they can be given higher
priority when granting a lock. Next, we discuss heuristics
for measuring the priority of a transaction in reducing theoverall contention.
Number of locks held — The simplest criterion for prioritizing transactions is the number of locks they currently
hold. We refer to this heuristic as Most Locks First (MLF).
The intuition is that a transaction with more locks is more
likely to block other transactions in the system. However,this approach does not account for the popularity of objects
in the system. In other words, a transaction might be holding many locks but on unpopular objects, which are unlikely
to be requested by other transactions. Prioritizing such atransaction will not necessarily reduce contention in the system. Figure 1 demonstrates an example where transaction
t1 holds the most number of locks, but on unpopular objects. It is therefore better to keep t1 waiting and insteadschedule t2 first, which holds fewer but more popular locks.

NP-Hardness

Minimizing the expected transaction latency under thescheduling algorithm is, in general, an NP-hard problem.
Intuitively, the hardness is due to the presence of sharedlocks, which cause the system’s dependency graph to be a
DAG, but not necessarily a tree.

Number of locks that block other transactions — An
improvement over the previous criterion is to only countthose locks that have at least one transaction waiting on
them. This approach disregards transactions that hold many

event, i.e., a transaction was unnecessarily blocked. A lock
scheduler is thus an event-driven scheduler.

3

650

All missing proofs can be found in our technical report [72].

o1

X

t1

ObjectTransaction
Transaction holds
a lock on object
Transaction waits
for a lock on object

X

t2

1

o1
t1
t3

X

t2

X

o1

X

t2

ObjectTransaction
Transaction holds
a lock on object
Transaction waits
for a lock on object

2

Figure 1: Transaction t1 holds the greatest number oflocks, but many of them on unpopular objects.
X

t1

3

Figure 3: Transaction t1 has a deeper dependency subgraph, but granting the lock to t2 will unblock more transactions which can run concurrently.

ObjectTransaction
Transaction holds
a lock on object
Transaction waits
for a lock on object

Later, in Section 6.4, we empirically evaluate these heuristics. While none of these heuristics alone are able to guarantee an optimal lock scheduling strategy, they o↵er valuable
insight in understanding the relationship between schedulingand overall contention. In particular, the first two heuristics focus on what we call horizontal contention, whereby atransaction holds locks on many objects directly needed byother transactions. In contrast, the third heuristic focuses
on reducing vertical contention, whereby a chain of dependencies causes a series of transactions to block each other.
Next, we present an algorithm which is capable of resolving
both horizontal and vertical aspects of contention.

Figure 2: Transaction t2 holds two locks that are waited
on by other transactions. Although only one of t1 ’s locks
is blocking other transactions, the blocked transaction (i.e.,t3 ) is itself blocking three others.
locks, but on these locks no other transactions are waiting.
We call this heuristic Most Blocking Locks First (MBLF).
The issue with this criterion is that it treats all blocked
transactions as the same, even if they contribute unequallyto the overall contention. Figure 2 shows an example inwhich the scheduler must decide between transactions t1
and t2 when the object o1 becomes available. Here, this criterion would choose t2 , which currently holds two locks, eachat least blocking one other transaction. However, although
t1 holds only one blocking lock, it is blocking t3 which itself
is blocking three other transactions. Thus, by scheduling t2
first, t3 and its three subsequent transactions will remain
blocked in the system for a longer period of time than if t1
had been scheduled first.

3.2

Largest-Dependency-Set-FirstIn this section, we propose an algorithm, called LargestDependency-Set-First (LDSF), which provides formal guarantees on the expected mean latency.
Consider two transactions t1 and t2 in the system. If
there is a path from t1 to t2 in the dependency graph, we
say that t1 is dependent on t2 (i.e., t1 depends on t2 ’s completion/abortion for at least one of its required locks). We
define the dependency set of t, denoted by g(t), as the set of
all transactions that are dependent on t (i.e., the set of transactions in t’s dependency subgraph). Our LDSF algorithm
uses the size of the dependency sets of di↵erent transactions
to decide which one(s) to schedule first. For example, in
Figure 4, there are five transactions in the dependency setof transaction t1 (including t1 itself) while there are fourtransactions in t2 ’s dependency set. Thus, in a situation
where both t1 and t2 have requested an exclusive lock on
object o1 , LDSF grants the lock to t1 (instead of t2 ) as soon
as o1 becomes available.
Now, we can formally present our LDSF algorithm. Suppose an object o becomes available (i.e., all previous locks ono are released), and there are m + n transactions currently
waiting for a lock on o: m transactions ti1 , ti2 , · · · , tim arerequesting a shared lock o, and n transactions tx1 , tx2 , · · · , txn
are requesting an exclusive lock on object o. Our LDSF algorithm defines the priority of each transaction txi requesting
an exclusive lock as the size of its dependency set, |g(txi )|.
However, LDSF treats all transactions requesting a shared
lock on o, namely ti1 , ti2 , · · · , tim , as a single transaction—
if LDSF decides to grant a shared lock, it will be granted
to all of them. The priority of the shared lock requests isthus definedas the size of the union of their dependency
Sm
i
ˆx
sets,
g(t
i ) . LDSF then finds the transaction t with
i=1
x x
x
x
the highest priority among t1 , t2 , · · · , tn . If tˆ ’s priority ishigher than the collective priority of the transactions requesting a shared lock, LDSF grants the exclusive lock totˆx . Otherwise, a shared lock is granted to all transactions

Depth of the dependency subgraph — A more sophisticated criterion is the depth of a transaction’s dependency
subgraph. For a transaction t, this is defined as the subgraphof the dependency graph comprised of all vertices that canreach t (and all edges between such vertices). The depthof t’s dependency subgraph is characterized by the numberof transactions on the longest path in the subgraph that
ends in t. We refer to this heuristic as Deepest Dependency
First (DDF). Figure 3 shows an example, where the depthof the dependency subgraph of transaction t1 is 3, whilethat of transaction t2 is only 2. Thus, based on this criterion, the exclusive lock on object o1 should be granted tot1 . The idea behind this heuristic is that a longer path indicates a larger number of transactions sequentially blocked.
Thus, to unblock such transactions sooner, the schedulingalgorithm must start with a transaction with deeper dependency graph. However, considering only the depth of thissubgraph can limit the overall degree of concurrency in thesystem. For example, in Figure 3, if the exclusive lock on
o1 is granted to t1 , upon its completion only one transaction in its dependency subgraph will be unblocked. On theother hand, if the lock is granted to t2 , upon its completion
two other transactions in its dependency subgraph will be
unblocked, which can run concurrently.

651

X

t1

o1

X

t2

ObjectTransaction
Transaction holds
a lock on object
Transaction waits
for a lock on object

ObjectTransaction
Transaction holds
a lock on object
Transaction waits
for a lock on object

t2

t3

t4

o1

o2

t5

t6
o3
t1

Figure 5: The critical objects of t1 are o1 and o2 , as they
are locked by transactions t2 and t3 . Note that, althougho3 is reachable from t1 , it is not a critical object of t1 since
it is locked by transactions that are not currently running,i.e., t5 and t6 which themselves are waiting for other locks.

Figure 4: Lock scheduling based on the size of the dependency sets.
Input : The dependency graph of the system G = (V, E, L),transaction t, object o, label L 2 {X, S}// meaning t has just released a lock of type L on o
Output: The set of transactions whose requested lock on oshould be granted

The intuition here is that if a transaction t1 is dependent
on t2 , any progress in the execution of t2 can also be considered as t1 ’s progress since t1 cannot receive its lock unless t2
finishes execution. Thus, by granting the lock to the transaction with the largest dependency set, LDSF allows themost transactions to make progress toward completion.
However, this does not necessarily hold true with the existence of shared locks. Even if transaction t1 is dependent
on t2 , the execution of t2 does not necessarily contributeto t1 ’s progress. Specifically, consider the set of all objects
that are reachable from t1 in the dependency graph, but arelocked (shared or exclusively) by currently running transactions. We call these objects the critical objects of t1 , anddenote them as C(t1 ).5 For example, in Figure 5, we haveC(t1 ) = {o1 , o2 }. Note that not all transactions that holda lock on a critical object of t1 contribute to t1 ’s progress.
Rather, only the transaction that releases the last lock onthat critical object allows for the progress of t1 . In the example of Figure 5, t2 ’s execution does not contribute to t1 ’s
progress, unless t3 releases the lock before t2 .
Nonetheless, when the number of transactions waiting foreach shared lock is bounded, LDSF is a constant-factor approximation of the optimal scheduler.

if there are other transactions still holding a lock on o then2
return ;;3 Obtain the set of transactions waiting for a shared lock on o,Ti{ti 2 V : (ti , o) 2 E and L(ti , o) = S} ={ti1 , ti2 , · · · , tim };4 Obtain the set of transactions waiting for an exclusive lockon o, T x
{tx 2 V : (tx , o) 2 E and L(tx , o) = X} =x , · · · , tx };
{tx
,
t
n
1 2
S
n
i
i
5 Let ⌧ (T ) =i=1 g(ti ) ;xxx )| = max xˆ
6 Find a transaction t 2 W s.t. |g(tˆti 2T x g(ti ) ;ixˆ
7 if ⌧ (T ) < g(t ) then8
return T i ;9 else10
return {tˆx };1

Algorithm 1: Largest-Dependency-Set-First Algorithm

ti1 , ti2 , · · · , tim . The pseudo-code of the LDSF algorithm isprovided in Algorithm 1.
Analysis — We do not make any assumptions about the future behavior of a transaction, as they may request various
locks throughout their lifetime. Furthermore, since we cannot predict new transactions arriving in the future, in our
analysis, we only consider the transactions that are alreadyin the system. Since the system does not know the execution
time of a transaction a priori, we model the execution timeof each transaction as a memoryless random variable. Thatis, the time a transaction has already spent in execution
does not necessarily reveal any information about the transaction’s remaining execution time. We denote the remaining
execution time as a random variable R with expectation R̄.
We also assume that the execution time of a transaction is
not a↵ected by the scheduling.4 Transactions whose behavior depends on the actual wall-clock time (e.g., stop if run
before 2pm, otherwise run for a long time) are also excluded
from our discussion.
We first study a simplified scenario in which there are
only exclusive locks in the system (we relax this assumptionin Theorem 3). The following theorem states that LDSF
minimizes the expected latency in this scenario.

Theorem 3. Let the maximum number of critical objects
for any transaction in the system be c. Assume that the
number of transactions waiting for a shared lock on the same
object is bounded by u. The LDSF algorithm is a (c · u)approximation of the optimal scheduling (among strategies
that grant all shared locks simultaneously) in terms of the
expected latency.

4.

SPLITTING SHARED LOCKSIn the LDSF algorithm, when a shared lock is granted, it isgranted to all transactions waiting for it. In Section 4.1, weshow why this may not be the best strategy. Then, in Section 4.2, we propose a modification to our LDSF algorithm,
called bLDSF, which improves upon LDSF by exploiting theidea of not granting all shared locks simultaneously.

4.1

The Benefits and Challenges

As noted earlier, when the LDSF algorithm grants a sharedlock, it grants the lock to all transactions waiting for it.
However, this may not be the optimal strategy. In general,
granting a larger number of shared locks on the same object
increases the probability that at least one of them will take

Theorem 2. When there are only exclusive locks in thesystem, the LDSF algorithm is the optimal scheduling algorithm in terms of the expected latency.
4

For example, scheduling causes context switches, which
may a↵ect performance. For simplicity, in our formal analysis, we assume that their overall e↵ect is not significant.

5
Note that the critical objects of a transaction may change
throughout its lifetime.

652

a long time before releasing the lock. Until the last transaction completes and releases its lock, no exclusive locks canbe granted on that object. In other words, the expected duration that the slowest transaction holds a shared lock grows
with the number of transactions sharing the lock. This is thewell-known problem of stragglers [21, 27, 31, 63, 79], which isexacerbated as the number of independent processes grows.
To illustrate this more formally, consider the following
example. Suppose that a set of m transactions, t1 , · · · , tm ,remare sharing a shared lock. Let R1rem , R2rem , · · · , Rm
be a
set of random variables representing the remaining timesof these transactions. Then, the time needed before an
exclusive lock can be granted on the same object is theremaining time of the the slowest transaction, denoted asrem
remRmax,m= max{R1rem , · · · , Rm}, which itself is a randomrem
remvariable. Let R̄max,m be the expectation of Rmax,m. As longrem
as the Rirem ’s have non-zero variance6 (i.e., i2 > 0), R̄max,mstrictly increases with m, as stated next.

S

S

t1
6

S

t2
1

X

t3
1

t4
5

x

ObjectTransaction
Transaction waits
for a lock on obect
Dependency set of size x

Figure 6: Assume that f (2) = 1.5 and f (3) = 2. If we first
grant a shared lock to all of t1 , t2 , and t3 , all transactions in
t4 ’s dependency set will wait for at least 2R̄. The total wait
time will be 10R̄. However, if we only grant t1 ’s lock, thent4 ’s lock, and then grant t2 ’s and t3 ’s locks together, thetransactions in t4 ’s dependency set will only wait R̄, while
those in t2 ’s and t3 ’s dependency sets will wait 2R̄. Thus,
the total wait time in this case will be only 9R̄.
According to this theorem, any algorithm that does notrely on knowing the delay factor is not competitive: it performs arbitrarily poor, compared to the optimal scheduling.
Thus, in the next section, we take the delay factor f (k) as
an input, and propose an algorithm that adopts the idea ofgranting shared locks only to a subset of the transactions
requesting it. We also discuss the criteria for choosing delay
factors that can yield good performance in practice.

Lemma 4. Suppose that R1rem , R2rem , · · · are random vari2
ables with the same range of values. If k+1> 0, thenrem
remR̄max,k<R̄max,k+1
for 1  k < m.
remR̄max,m. AccordingR̄rem
to Lemma 4, f (m) is strictly monotonically increasing withrespect to m. The exact formula for f (m) will depend on thespecific distribution of Ri ’s. For example, if Ri ’s are exponentially distributed (i.e., a memoryless distribution) withrem
mean R̄, then their CDF is given by F (x) = 1 e x/R̄.
Pm 1
Then, f (m) can be computed as f (m) = i=1 However,iregardless of the distribution of the latencies, f (m) is guaranteed to satisfy the following three properties:
C1. f (1) = 1;C2. f (m) < f (m + 1);
C3. f (m)  m.
The first property is trivial: granting the lock to only one
transaction at a time does not incur any delays. The second
property is based on Lemma 4. The third is based on thefact that sharing a lock between a group of m transactions
cannot be slower than granting the lock to them one after
another and sequentially.
Since granting a shared lock to more transactions can delay the exclusive lock requests, it is conceivable that granting
a shared lock to only a subset of the transactions waiting
for it might reduce the overall latency in the system. Intuitively, when many transactions are waiting for the same
shared lock, it would be better to grant the shared lock only
to a few that have a higher priority (i.e., a larger dependencyset), and leave the rest until the next time. This strategy
can therefore reduce the time that other transactions have to
wait for an exclusive lock, as illustrated in Figure 6. However, lock scheduling in this situation becomes extremely
difficult. We have the following negative result.

We define the delay factor as f (m) =4.2

The bLDSF Algorithm

In this section, we present a simple algorithm, called bLDSF,
which inherits the intuition behind the LDSF algorithm, butalso exploits the idea that a shared lock does not have to be
granted to all transactions waiting for it.
While LDSF measures the progress enabled by di↵erent
scheduling decisions, our bLDSF algorithm measures the
speed of progress. If a transaction tx waiting for an exclusive lock is scheduled, |g(tx )| transactions will make progressover the next R̄ (expected) units of time. Thus, the speed of|g(tx )|
progress can be measured as. On the other hand, byR̄
scheduling a batch of transactions
ti1 , ti2 , · · · , tik waiting forSa shared lock together, | ki=1 g(tii )| transactions will makeprogress over the next f (k) · R̄ units of time. The speed ofS| ki=1 g(tii )|progress can then be measured as.
f (k)R̄The bLDSF algorithm works as follows. First, it finds thetransaction waiting for an exclusive lock with the largest
dependency set, denoted as tˆx . Denote the size of its dependency set as p = g(tˆx ) . Then, bLDSF finds the batchof transactions, tˆi1 , tˆi2 , · · · , tˆik , waiting for a shared lock suchS| ki=1 g(tˆii )|that q =is maximized. When q < p, the sysf (k)tem will make faster progress if tˆx is scheduled first, in whichcase bLDSF will grant an exclusive lock to tˆx . Conversely,
when q > p, the system will make faster progress if the batchof tˆi1 , tˆi2 , · · · , tˆik is scheduled first, in which case bLDSF will
grant shared locks to tˆi1 , tˆi2 , · · · , tˆik simultaneously. Whenq = p, the speed of progress in the system will be the sameunder both scheduling decisions. In this case, bLDSF grants
shared locks to the batch, in order to increase the overall
degree of concurrency in the system. The pseudocode for
bLDSF is provided in Algorithm 2.
We show that, when the number of transactions waiting
for shared locks on the same object is bounded, the bLDSF
algorithm is a constant factor approximation of the optimalscheduling algorithm in terms of the expected wait time.

Theorem 5. Let A¬f be the set of scheduling algorithms
that do not use the knowledge of the delay factor f (k) intheir decisions. For any algorithm A¬f 2 A¬f , there existsw̄(A¬f )an algorithm A, such that= !(1) for some delayw̄(A)factor f (k).
6This assumption holds unless all instances of a transaction
type take exactly the same time, which is unlikely.

653

Input : The dependency graph of the system G = (V, E, L),transaction t, object o, label L 2 {X, S}// meaning t has just released a lock of type L on o
Output: The set of transactions whose requested lock on oshould be granted

5

t1
x

t2 2

if there are other transactions still holding a lock on o then2
return ;;3 Obtain the set of transactions waiting for a shared lock on o,Ti{ti 2 V : (ti , o) 2 E and L(ti , o) = S} ={ti1 , ti2 , · · · , tim };4 Obtain the set of transactions waiting for an exclusive lockon o, T x
{tx 2 V : (tx , o) 2 E and L(tx , o) = X} =x , · · · , tx };
{tx
,
t
n
1 2
ˆi ˆi
ˆi
i
5 Let t , t , · · · , t be the set of transactions in T such that
1 2
k
Sk
ˆ
| i=1 g(tii )|is maximized ;
f (k)
x
ˆ
6 Let tbe the transaction in T x with the largest dependency
set;
Sk
ˆi
x ) · f (k) 
7 if g(tˆ
i=1 g(t ) then

2 t3

1

1 t4

ObjectTransaction with approximate
dependency set size x
Transaction holds
a lock on object
Transaction waits
for a lock on object

Figure 7: The e↵ective size of t1 ’s dependency set is 5. But
its exact size is only 4.
a transaction performing a table scan will request a large
number of locks, and will not make any progress until all of
its locks can be granted. Thus, knowing a transaction’s lockpattern in advance would also be beneficial. We leave suchextensions of our algorithms (e.g., to hybrid workloads [60])to future work.

ireturn {tˆi1 , tˆi2 , · · · , tˆik };9 else10
return tˆx ;5.

8Algorithm 2: The bLDSF Algorithm
Theorem 6. Let the maximum number of critical objects
for any transaction in the system be c. Assume that the
number of transactions waiting for shared locks on the same
object is bounded by v. Then, given a delay factor of f (k),the bLDSF algorithm is an h-approximation of the optimal scheduling algorithm in terms of the expected wait time,
where h = cv 2 · f (v).
Unlike the LDSF algorithm, bLDSF requires a delay factor for its analysis. However, since the remaining times oftransactions can be modeled as random variables, the exact
form of the delay factor f (k) will also depend on the distribution of these random variables. For example, the delay factor for exponential random variables is f (k) = O(log k) [22],for geometric random variables is f (k) p= O(log k) [29], forGaussian random variables is f (k) = O( log k) [47], andpfor
power law random variables with exponent 3 is f (k) = k.
In Section 6.7, we empirically show that bLDSF’s performance is not sensitive to the specific choice of the delay factor, as long as it is a sub-linear function that grows
monotonically with k (conditions C1, C2, and C3 from Section 4.1). This is because, when the batch size is small,the di↵erence between all sub-linear
functions is also small.
p
For example, when b = 10, b ⇡ 3.16 and log2 (1 + b) ⇡3.46, leading to similar scheduling decisions. Even thoughplog2 (1 + b) ⇡ 1.86 is smaller than the other two, it canstill capture condition C2 quite well.

4.3

IMPLEMENTATION

We have implemented our scheduling algorithm in MySQL.
Similar to all major DBMSs, the default lock scheduling policy in MySQL was FIFO.7 Specifically, all pending lock requests on an object are placed in a queue. A lock request
is granted immediately upon its arrival only if one of thesetwo conditions holds: (i) there are no other locks currently
held on the object, or (ii) the requested lock type is compatible with all of the locks currently held on the object andthere are no incompatible requests ahead of it waiting in thequeue. Similarly, whenever a lock is released on an object,
MySQL’s scheduler scans the entire queue from beginningto the end. It grants any waiting requests as long as oneof these conditions holds. As soon as the scheduler encounters the first lock request that cannot be granted, it stops
scanning the rest of the queue.
One challenge in implementing LDSF and bLDSF is keeping track of the sizes of the dependency sets. Exact calculation would require either (i) searching down the reverse
edges in the dependency graph in real-time, whenever ascheduling decision is to be made, or (ii) storing the dependency sets for all transactions and maintaining them eachtime a transaction is blocked or a lock is granted. Both options are relatively costly. Therefore, in our implementation,
we rely on an approximation of the sizes of the dependency
sets, rather than computing their exact values. When atransaction t holds no locks that block other transactions,|g(t)| = 1. Otherwise, let Tt be the set of transactions waiting for an
P object currently held by transaction t. Then,|g(t)| ⇡ t0 2Tt |g(t0 )| + 1. The reason this method is only
an approximation of |g(t)| is that the dependency graph is a
DAG (but not necessarily a tree), which means the dependency sets of di↵erent transactions may overlap. Figure 7
illustrates an example, where the dependency set of t1 is{t1 , t2 , t3 , t4 } and is therefore of size 4. However, its e↵ective size is calculated as one plus the sum of the e↵ective
sizes of t2 and t3 ’s dependency sets, resulting in 5. To ensure that transactions appearing on multiple paths will not
be updated multiple times, we also keep track of those thathave already been updated.
Another implementation challenge lies in the difficulty offinding the desired batch of transactions in bLDSF. Calculating the size of the union of several dependency sets

Discussion

In our analysis, we have assumed no additional information regarding a transaction’s remaining execution time, or
its lock access pattern. However, with the recent progress
on incorporating machine learning models into DBMS technology [58, 11], one might be able to predict transaction
latencies [78, 59] in the near future. When such information
is available, a lock scheduling algorithm could take that into
account when maximizing the speed of progress: a transaction that will take longer should be given less priority. The
priority of a transaction would then be the size of its dependency set divided by its estimated execution time. Likewise,

7654

Now, our LDSF algorithm is the default (MySQL 8.0.3+).

6.

requires detailed information about the elements in each dependency set (since the dependency sets may overlap due toshared locks). Therefore, we rely on the following approximation in our implementation. We first sort all transactions
waiting for a shared lock in the decreasing order of their dependency set sizes. Then, for k = 1, 2, · · · , we calculate theq value (see Section 4.2) for the first k transactions. Here,we approximate the size of the union of the dependency sets
as the sum of their individual sizes. Let k⇤ be the k valuethat maximizes q. We then take the first k⇤ transactions as
our batch, which we consider for granting a shared lock to.
In Section 6, we show that, despite using these approximations in our implementation, our algorithms remain quitee↵ective in practice.

EXPERIMENTS

Our experiments aim to answer several key questions:• How do our scheduling algorithms (LDSF and bLDSF)
a↵ect the overall throughput of the system?
• How do our algorithms compare against FIFO (thedefault policy in nearly all databases) and VATS (recently adopted by MySQL), in terms of reducing average and tail transaction latencies?
• How do our scheduling algorithms compare against
various heuristics?
• How much overhead do our algorithms incur, compared to the latency of a transaction?
• How does the e↵ectiveness of our algorithms vary withdi↵erent levels of contention?
• What is the impact of the choice of delay factor on thee↵ectiveness of bLDSF?
• What is the impact of approximating the dependency
sets (Section 5) on reducing the overhead?
In summary, our experiments show the following:
1. By resolving contention much more e↵ectively than FIFO
and VATS, bLDSF improves throughput by up to 6.5x
(by 4.5x on average) over FIFO, and by up to 2x (1.5x
on average) over VATS. (Section 6.2)
2. bLDSF can reduce mean transaction latencies by up to
300x and 80x (30x and 3.5x, on average) compared to
FIFO and VATS, respectively. It also reduces the 99th
percentile latency by up to 190x and 16x, compared to
FIFO and VATS, respectively. (Section 6.3)
3. Both bLDSF and LDSF outperform various heuristics by
2.5x in terms of throughput, and by up to 100x (8x onavg.) in terms of transaction latency. (Section 6.4)
4. Our algorithms reduce queue length by reducing contention, and thus incur much less overhead than FIFO.
However, their overhead is larger than VATS. (Section 6.5)
5. As the degree of contention rises in the system, bLDSF’s
improvement over both FIFO and VATS increases. (Section 6.6)
6. bLDSF is not sensitive to the specific choice of delay factor, as long as it is chosen to be an increasing and sublinear function. (Section 6.7)
7. Our approximation technique reduces scheduling overhead by up to 80x.

Starvation Avoidance — In MySQL’s implementation of
FIFO, when there is an exclusive lock request in the queue,
it serves as a conceptual barrier: later requests for sharedlocks cannot be granted, even if they are compatible with thecurrently held locks on the object. This mechanism prevents
starvation when using FIFO. In our algorithms, starvation
is prevented using a similar mechanism. We place a barrierat the end of the current wait queue. Lock requests that
arrive later are placed behind this barrier and are not considered for scheduling. In other words, the only requests
that are considered are those that are ahead of the barrier.
Once all such requests are granted, this barrier is lifted, anda new barrier is added to the end of the current queue, i.e.,
those requests that were previously behind a barrier are now
ahead of one. This mechanism prevents a transaction witha small dependency set from waiting indefinitely behind an
infinite stream of newly arrived transactions with larger dependency sets. An alternative strategy to avoid starvation
is to simply add a fraction of the transaction’s age to its
dependency set size when making scheduling decisions. A
third strategy is to replace a transaction’s dependency set
size with a sufficiently large number once its wait time has
exceeded a certain timeout threshold.
Space Complexity — Given the approximation methods
mentioned above, both LDSF and bLDSF only require maintaining the approximate size of the dependency set of eachtransaction. Therefore, the overall space overhead of ouralgorithms is only O(|T |).
Time Complexity — In MySQL, all lock requests on an
object (either granted or not) are stored in a linked list.
Whenever a transaction releases a lock on the object, thescheduler scans this list for requests that are not granted
yet. For each of these requests, the scheduler scans thelist again to check compatibility with granted requests. If
the request is found compatible with all existing locks, it isgranted, and the scheduler checks the compatibility of thenext request. Otherwise, the request is not granted, and thescheduler stops granting further locks. Let N be the number of lock requests on an object (either granted or not).
Then, FIFO takes O(N 2 ) time in the worst case. LDSF
and bLDSF both use the same procedure as FIFO to findcompatible requests that are not granted yet, which takesO(N 2 ) time. For bLDSF, we also sort all transactions waiting for a shared lock by the size of their dependency sets,
which takes O(N log N ) time. Thus, the time complexity of
LDSF and bLDSF is still O(N 2 ).

6.1

Experimental Setup

Hardware & Software — All experiments were performed
using a 5 GB bu↵er pool on a Linux server with 16 Intel(R)Xeon(R) CPU E5-2450 processors and 2.10GHz cores. The
clients were run on a separate machine, submitting transactions to MySQL 5.7 running on the server.
Methodology — We used the OLTP-Bench tool [24] to run
the TPC-C workload. We also modified this tool to run a microbenchmark (explained below). OLTP-Bench generated
transactions at a specified rate, and client threads issued
these transactions to MySQL. The latency of each transaction was calculated as the time from when it was issued until
it finished. In all experiments, we controlled the number oftransactions issued per second within a safe range to prevent
MySQL from falling into a thrashing regime. We also noticed that the number of deadlocks was negligible compared655

Figure 8: Throughput improvement Figure 9: Avg. latency improvement Figure 10: Tail latency improvementwith bLDSF (TPC-C).
with bLDSF (under the same TPC-C w/ bLDSF (under the same number oftransactions per second).
TPC-C transactions per second).
to the total number of transactions, across all experiments
and algorithms.

tion that holds the most locks which block at least one
other transaction (introduced in Section 3.1).
6. Deepest Dependency First (DDF). When an object
becomes available, grant a lock on it to the transaction
with the deepest dependency subgraph (Section 3.1).
For MLF, MBLF, and DDF, if a shared lock is granted,
all shared locks on that object are granted. For LDSF andbLDSF, we use the barriers explained in Section 5 to prevent
starvation. For FIFO and VATS, if a shared lock is granted,
they continue to grant shared locks to other transactions
waiting in the queue until they encounter an exclusive lock,at which point they stop granting more locks.

TPC-C Workload — We used a 32-warehouse configuration for the TPC-C benchmark. To simulate a system withdi↵erent levels of contention, we relied on changing the following two parameters: (i) number of clients, and (ii) number of submitted transactions per second (a.k.a. throughput). Each of our client threads issued a new transaction assoon as its previous transaction finished. Thus, by creatinga specified number of client threads, we e↵ectively controlled
the number of in-flight transactions. To control the systemthroughput, we created client threads that issued transactions at a specific rate.

6.2 Throughput
Microbenchmark — We created a microbenchmark for amore thorough evaluation of our algorithm under di↵erent
We compared the system throughput when using FIFO
degrees of contention. Specifically, we created a database
and VATS versus bLDSF, given an equal number of clientswith only one table that had 20,000 records in it. The clients(i.e., in-flight transactions). We varied the number of clientswould send transactions to the server, each comprised of 5
from 100 to 900. The results of this experiment for TPC-C
queries. Each query was randomly chosen to be either a “SEare presented in Figure 8.
LECT” query (acquiring a shared lock) or an “UPDATE”
In both cases, the throughput dropped as the number ofquery (acquiring an exclusive lock). The records in the tableclients increased. This is expected, as more transactions inwere accessed by the queries according to a Zipfian distrithe system lead to more objects being locked. Thus, whenbution. To generate di↵erent levels of contention, we varieda transaction requests a lock, it is more likely to be blocked.
the following two parameters in our microbenchmark:In other words, the number of transactions that can makeprogress decreases, which leads to a decrease in throughput.
1. skew of the access pattern (the parameter ✓ of the Zipfian
However, the throughput decreased more rapidly when
distribution)
using
FIFO or VATS than bLDSF. For example, when there
2. fraction of exclusive locks (probability of “UPDATE” queries).
were only 100 clients, bLDSF outperformed FIFO by only
1.4x and VATS by 1.1x. However, with 900 clients, bLDSF
Baselines — We compared the performance of our bLDSF
achieved 6.5x higher throughput than FIFO and 2x higher
algorithm (with f (k)=log2 (1 + k) as default) against thethroughput than VATS. As discussed in Section 4.2, bLDSF
following baselines:
always schedules transactions that maximize the speed of
1. First In First Out (FIFO). FIFO is the default schedprogress in the system. This is why it allows for more transuler in MySQL and nearly all other DBMSs. When an
actions to be processed in a certain amount of time.
object becomes available, FIFO grants the lock to thetransaction that has waited the longest.
2. Variance-Aware Transaction Scheduling (VATS).
6.3 Average and Tail Transaction Latency
This is the strategy proposed by Huang et al. [44]. When
We compared transaction latencies of FIFO, VATS, andan object becomes available, VATS grants the lock to thebLDSF under an equal number of transactions per second
eldest transaction in the queue.
(i.e, throughput). We varied the number of clients (and3. Largest Dependency Set First (LDSF). This is thehence, the number of in-flight transactions) from 100 to
strategy described in Algorithm 1, which is equivalent to
900 for FIFO and VATS, and then ran bLDSF at the samebLDSF with b = inf, and f (k) = 1.
throughput as VATS, which is higher than the throughputof FIFO. This means that we compare bLDSF with FIFO
4. Most Locks First (MLF). When an object becomesat a higher throughput. The result is shown in Figure 9.
available, grant a lock on it to the transaction that holds
Our bLDSF algorithm dramatically outperformed FIFO by
the most locks (introduced in Section 3.1).
a factor of up to 300x and VATS by 80x. This outstanding
5. Most Blocking Locks First (MBLF). When an obimprovement confirms our Theorems 3 and 6, as our algoject becomes available, grant a lock on it to the transacrithm is designed to minimize average transaction latencies.

656

Figure 11: Maximum throughput un- Figure 12: Transaction latency under Figure 13: Scheduling overhead of varder various algorithms (TPC-C).
various algorithms (TPC-C).
ious algorithms (TPC-C).

Figure 14: Average number of transac- Figure 15: Average transaction la- Figure 16: Average latency for diftions waiting in the queue under various tency for di↵erent degrees of skewness ferent numbers of exclusive locks (mialgorithms (TPC-C).
(microbenchmark).
crobenchmark).
We also report the 99th percentile latencies in Figure 10.
Here, bLDSF outperformed FIFO by up to 190x. Interestingly, bLDSF outperformed VATS too (by up to 16x), eventhough the latter is specifically designed to reduce tail latencies. This is because bLDSF causes all transactions tofinish faster on average, and thus, those transactions waitingat the end of the queue will also wait less, leading to lower
tail latencies.

6.4

Comparison with Other Heuristics

In this section, we report our comparison of both bLDSF
and LDSF algorithms against the heuristic methods introduced in Section 3, i.e., MLF, MBLF, and DDF. Moreover,
we compare our algorithms with VATS too.
First, we compared their throughput given an equal number of clients. We varied the number of clients from 100
to 900. The results are shown in Figure 11. LDSF andbLDSF achieve up to 2x and 2.5x improvement over theother heuristics in terms of throughput, respectively.
We also measured transaction latencies under an equal
number of transactions per second (i.e, throughput). We
varied the number of clients from 100 to 900 for the heuristics, and then ran bLDSF and LDSF at the maximum throughput achieved by any of the heuristics. For those heuristics which were not able to achieve this throughput, we
compared our algorithms at a higher throughput than they
achieved. The results are shown in Figure 12, indicating that
MLF, MBLF, and DDF outperformed FIFO by almost 2.5x
in terms of average latency, while our algorithms achieved up
to 100x improvement over the best heuristics (MBLF with
900 transactions). Furthermore, bLDSF was better thanLDSF by a small margin.

6.5

Scheduling Overhead

We also compared the overhead of our algorithms (LDSF
and bLDSF) against both FIFO and VATS: the overhead of657

a scheduling algorithm is the time needed by the algorithm
to decide which lock(s) to grant.
In this experiment, we fixed the number of clients to 100
while varying throughput from 200 to 1000. The result isshown in Figure 13. We can see that, although all threealgorithms have the same time complexity in terms of thequeue length (Section 5), ours resulted in much less overhead than FIFO because they led to much shorter queues
for the same throughput. This is because our algorithms effectively resolve contention, and thus, reduce the number of
waiting transactions in the queue. To illustrate this, we alsomeasured the average number of waiting transactions whenever an object becomes available. As shown in Figure 14,
this number was much smaller for LDSF and bLDSF. However, VATS incurred less overhead than LDSF and bLDSF,
despite having longer queues. This is because VATS does
not compute the sizes of the dependency sets.

6.6

Studying Different Levels of Contention

In this section, we study the impact of di↵erent levelsof contention on the e↵ectiveness of our bLDSF algorithm.
Contention in a workload is a result of two factors: (i) skew
in the data access pattern (e.g., popular tuples), and (ii) alarge number of exclusive locks. There is more contention
when the pattern is more skewed, as transactions will request a lock on the same records more often. Likewise, exclusive lock requests cause more contention, as they cannot
be granted together and result in blocking more transactions. We studied the e↵ectiveness of our algorithm underdi↵erent degrees of contention by varying these two factors
using our microbenchmark:1. We fixed the fraction of exclusive locks to be 60% of alllock requests, and varied the ✓ parameter of the Zipfian
distribution of our access distribution between 0.5 and
0.9 (larger ✓, more skew).

Figure 17: The impact of delay factor Figure 18: Scheduling overhead with Figure 19: CCDF of the relative error
on average latency.
and without our approximation heuristic of the approximation of the sizes of thefor choosing a batch.
dependency sets.
2. We fixed the ✓ parameter to be 0.8 and varied the probability of an “UPDATE” query in our microbenchmark
between 20% and 100%. The larger this probability, thelarger the fraction of exclusive locks.
First, we ran FIFO using 300 clients, and then ran both
VATS and bLDSF at the same throughput as FIFO. The
results of these experiments are shown in Figures 15 and 16.
Figure 15 shows that when there is no skew, there is nocontention, and thus most queues are either empty or only
have a single transaction waiting. Since there is no scheduling decision to be made in this situation, FIFO, VATS andbLDSF become equivalent and exhibit a similar performance.
However, the gap between bLDSF and the other two algorithms widens as skew (and thereby contention) increases.
For example, when the data access is highly skewed (✓ =0.9), bLDSF outperforms FIFO by more than 50x and VATS
by 38x. Figure 16 reveals a similar trend: as more exclusive
locks are requested, bLDSF achieves greater improvement.
Specifically, when 20% of the lock requests are exclusive,bLDSF outperforms FIFO by 20x and VATS by 9x. However, when all the locks are exclusive, the improvement iseven more dramatic, i.e., 70x over FIFO and 25x over VATS.
Note that, although VATS guarantees optimality when there
are only exclusive locks [44], it fails to account for transaction dependencies in its analysis (see Section 7 for a discussion of the assumptions made in VATS versus bLDSF). In
summary, when there is no contention in the system, there
are no scheduling decisions to be made, and all schedulingalgorithms are equivalent. However, as contention rises, sodoes the need for better scheduling decisions, and so does
the gap between bLDSF and other algorithms.

6.7

Understandably, f1 did not perform well, as it did not satisfy
condition C2 from Section 4.1. Functions f5 and f6 did not
perform well either, since linear functions overestimate thedelay. For example, two transactions running concurrently
take less time than if they ran one after another.

6.8 Approximating Sizes of Dependency Sets
We studied the e↵ectiveness of our approximation heuristic from Section 5 for choosing a batch of shared requests.
Computing the optimal batch accurately was costly, and significantly lowered the throughput. However, we measured
the scheduling overhead, and compared it to when we used
an approximation. We ran TPC-C, and varied the numberof clients from 100 to 900. As shown in Figure 18, our approximation reduced the scheduling overhead by up to 80x.
We also measured the error of our approximation technique for estimating the dependency set sizes—the deviationfrom the actual sizes of the dependency sets—for varying ratios of shared locks in the workload. Figure 19 shows thecomplementary cumulative distribution function (CCDF) of
the relative error of approximating the dependency set sizes.
The error grew with the ratio of shared locks; this was expected, as shared locks are the cause of error in our approximation. However, the errors remained within a reasonable
range, e.g., even with 80% shared locks, we observed a 2approximation of the exact sizes in 99% of the cases.

7.

Choice of Delay Factor

To better understand the impact of delay factors on bLDSF,
we experimented with several functions of di↵erent growth
rates, ranging from the lower bound of all functions thatsatisfy conditions C1, C2, and C3 (i.e., f (k) = 1) to their
upper bound (i.e., f (k) = k). Specifically, we used eachof the following delay factors in our bLDSF algorithm, andmeasured the average transaction latency:• f1 (k) = 1;p
• f2 (k) = log2 (1 + k);• f3 (k) = log2 (1 + k);p• f4 (k) = k;
• f5 (k) = 0.5(1 + k);• f6 (k) = k.
The results are shown in Figure 17. We can see that all sublinear functions (i.e., f2 , f3 , and f4 ) performed comparably,
and that they performed better than the other functions.

658

RELATED WORKIn short, the large body of work on traditional job scheduling is unsuitable in a database context due to the uniquerequirements of locking protocols deployed in databases. Although there is some work on lock scheduling for real-time
databases, they aim at supporting explicit deadlines rather
than minimizing the mean latency of transactions.
Job Scheduling — Outside the database community, there
has been extensive research on scheduling problems in general. Here, the duration (and sometimes the weight andarrival time) of each task is known a priori, and a typicalgoal is to minimize (i) the sum of (weighted) completion
times (SCT) [64, 41, 39], (ii) the latest completion time [20,34, 67], (iii) the completion time variance (CTV) [14, 17,76, 49], or even (iv) the waiting time variance (WTV) [28].
The o✏ine SCT problem can be optimally solved using a
Shortest-Weighted-Execution-Time approach, whereby jobs
are scheduled in the non-decreasing order of their ratio ofexecution time to weight [70], if they all arrive at the sametime. However, when the jobs arrive at di↵erent times, thescheduling becomes NP-hard [52].
None of these results are applicable to our setting, mainly
because of their assumption that each processor/worker canbe used by only one job at a time, whereas in a database,locks can be held in shared and exclusive modes. Moreover,they assume the execution time of each job is known, which
is not the case in a database (i.e., the database does notknow when the application/user will commit and release its
locks). Finally, with the exception of [64, 41], prior work onscheduling either assumes that all tasks are available at the
beginning, or that their arrival time is known. In a database,however, such information is unavailable.

contrast, the current paper proves the optimality of bLDSF
in terms of minimizing mean latency. More importantly, ouranalysis of VATS uses a simplifying assumption that models the latency of a transaction t as l(t) = A(t) + U (t) +R · (N (t) + 1), where A(t) is the age of t (i.e., time sincearrival), U (t) is the time since t arrives in the current queue
until the lock becomes available, and N (t) is the numberof transactions in the current queue that will be scheduled
before t. However, VATS does not account for the fact that
U (t) itself can be a↵ected by the scheduling decision. In
this paper, in our analysis of bLDSF, we have been able toremove both assumptions and hence, prove optimality under a more realistic setting. We consider both shared andexclusive locks, and account for the impact of our scheduling decision on the wait times of other transactions waitingfor other objects in the system. Our experiments show thatbLDSF’s more realistic assumptions lead to better decisions(see Section 6).

Dependency-based Scheduling — Scheduling tasks withdependencies among them has been studied for both single
machines [69, 42] and multiprocessors [25, 26, 30, 61]. Here,each job only needs one processor and once scheduled, it will
not be blocked again. However, in a database, a transaction
can request many locks, and thus, can be blocked even after
it is granted some locks.
Real-time Databases (RTDB) — There is some work onlock scheduling in the context of RTDBs, where transactions
are scheduled to meet a set of user-given deadlines [75, 7, 55,
71, 77, 13, 36, 74, 73, 38, 33, 8, 53, 66, 19, 40]. It is shownthat the First-In-First-Out (FIFO) policy performs poorly inthis setting [33, 7, 8, 53], compared to the Earliest-DeadlineFirst policy [55, 71, 77], which is also used in practice [13].
Unfortunately, the work in this area is not applicable togeneral-purpose database systems. First, in an RTDB, eachtransaction comes with a pre-specified deadline, while in a
general-purpose database such deadlines are not provided.
Second, a key assumption in this line of work is that the execution time of each transaction is known in advance, whereas
in a general database the execution time of a transaction
is only known once it is finished. Finally, the schedulinggoal in an RTDB is to minimize the total tardiness or thenumber of missed deadlines. In other words, as long as atransaction meets its deadline, RTDBs do not care whether
it finishes right before the deadline or much earlier. In contrast, general databases aim to execute transactions as fast
as possible.

Deadlock Resolution — The problem of deadlock resolution is about deciding which transaction(s) to abort in orderto resolve a deadlock [65, 37, 56, 43, 32]. Typically, transactions with lower priority are aborted, in order to reduce
the amount of work wasted. Here, transactions are prioritized based on their age [32, 10], deadline [48], or numberof held locks [57]. Franaszek et al. [32] empirically showthat an age-based priority improves concurrency, and reduces the amount of work wasted. Agrawal et al. [10] argue
that choosing victims based on their age and number of heldlocks leads to fewer rollbacks, than (i) choosing a transaction randomly, or (ii) aborting the most recently blocked
transaction. These proposals take contention into accountonly for deadlock resolution. In contrast, we focus on lock
scheduling and show that contention-aware scheduling yields
significant performance benefits in practice.

8.

CONCLUSION

We study a fundamental (yet, surprisingly overlooked)
problem: lock scheduling in a database system. Despite themassive body of work on transactional databases, the astonishing impact of lock scheduling on overall performance ofa transactional system seems to have been largely underrecognized—to the extent that every DBMS to date has
simply relied on FIFO. To our knowledge, we are the firstto propose the idea of contention-aware lock scheduling,
and present efficient algorithms that are guaranteed to reduce mean transaction latencies down to a constant-factorapproximation of the optimal scheduling. We also empirically confirm our theoretical analysis by modifying a realworld DBMS. Our extensive experiments show that our algorithms reduce transaction latencies by up to two orders ofmagnitude, while delivering 6.5x higher throughput. More
importantly, our algorithm has already been adopted by
MySQL, and has started to impact real world applications.

Scheduling in Existing DBMS — For simplicity andfairness [12], the First-In-First-Out (FIFO) policy and its
variants are the most widely adopted scheduling policies
in many of today’s databases [9], operating systems [16],and communication networks [51]. FIFO is the default lock
scheduling policy in MySQL [3], MS SQL Server [6], Postgres [5], Teradata [4], and DB2 [2]. Despite its popularity,
FIFO does not provide any guarantees in terms of averageor percentile latencies. Huang et al. [44] propose a scheduling algorithm, called Variance-Aware Transaction Scheduling (VATS), which aims at minimizing the variance of transaction latencies, and its optimality holds only when there
are no shared locks in the system. In contrast, we focus
on minimizing mean latency, and allow for both shared andexclusive locks. In short, designing optimal lock schedulingalgorithms for databases has remained an open problem.

9.

VATS — Based on the findings of a new profiler, called
VProfiler [45], we have previously proposed Variance-Aware
Transaction Scheduling (VATS) [44]. VATS prioritizes transactions according to their arrival time in the system, as opposed to FIFO, which prioritizes them according to theirarrival time in the current queue. Our prior work proves the
optimality of VATS in terms of minimizing the Lp -norm oftransaction latencies [44], when there are no shared locks. In

ACKNOWLEDGEMENT

This work is supported in part by National Science Foundation (grants 1544844, 1553169, and 1629397). The authors are grateful to Mark Callaghan, Jan Lindström, Sunny
Bains, and Laurynas Biveinis (for integrating our algorithm
into MySQL, MariaDB, and Percona Server), to Shengqi Wu(for his early contributions), and to Morgan Lovay (for hercomments).

659

10.

REFERENCES[20] B.-C. Choi, S.-H. Yoon, and S.-J. Chung. Minimizing
maximum completion time in a proportionate flow
shop with one machine of di↵erent speed. EJOR,
pages 964–974, 2007.
[21] J. Cipar, Q. Ho, J. K. Kim, S. Lee, G. R. Ganger,
G. Gibson, K. Keeton, and E. P. Xing. Solving thestraggler problem with bounded staleness. In HotOS,
pages 22–22, 2013.
[22] A. DasGupta. Finite sample theory of order statistics
and extremes. In Probability for Statistics andMachine Learning, pages 221–248. 2011.
[23] L. Daynès, O. Gruber, and P. Valduriez. Locking inoodbms client supporting nested transactions. In
ICDE, pages 316–323, 1995.
[24] D. E. Difallah, A. Pavlo, C. Curino, andP. Cudre-Mauroux. Oltp-bench: An extensible testbed
for benchmarking relational databases. PVLDB,
7(4):277–288, 2013.
[25] J. Du and J. Y.-T. Leung. Scheduling tree-structured
tasks with restricted execution times. Information
processing letters, pages 183–188, 1988.
[26] J. Du and J. Y.-T. Leung. Scheduling tree-structured
tasks on two processors to minimize schedule length.
SIDMA, pages 176–196, 1989.
[27] A. C. Dusseau, R. H. Arpaci, and D. E. Culler.
E↵ective distributed scheduling of parallel workloads.
ACM SIGMETRICS Performance Evaluation Review,
pages 25–36, 1996.
[28] S. Eilon and I. Chowdhury. Minimising waiting time
variance in the single machine problem. Management
Science, pages 567–575, 1977.
[29] B. Eisenberg. On the expectation of the maximum ofiid geometric random variables. Statistics &Probability Letters, pages 135–143, 2008.
[30] A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng.
Optimal online scheduling of parallel jobs withdependencies. In STOC, pages 642–651, 1993.
[31] K. B. Ferreira, P. G. Bridges, R. Brightwell, and K. T.
Pedretti. The impact of system design parameters on
application noise sensitivity. Cluster computing, pages
117–129, 2013.
[32] P. Franaszek and J. T. Robinson. Limitations ofconcurrency in transaction processing. TODS, 1985.
[33] L. George and P. Minet. A fifo worst case analysis fora hard real-time distributed problem with consistency
constraints. In ICDCS, pages 441–448, 1997.
[34] A. Guinet and M. Solomon. Scheduling hybrid
flowshops to minimize maximum tardiness or
maximum completion time. IJPR, pages 1643–1654,
1996.
[35] L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling tominimize average completion time: O↵-line andon-line algorithms. In SODA, pages 142–151, 1996.
[36] J. R. Haritsa, M. J. Canrey, and M. Livny.
Value-based scheduling in real-time database systems.
VLDBJ, pages 117–152, 1993.
[37] J. R. Haritsa, M. J. Carey, and M. Livny. Data accessscheduling in firm real-time database systems. RTSS,
pages 203–241, 1992.
[38] J. R. Haritsa, M. Livny, and M. J. Carey. Earliest
deadline scheduling for real-time database systems. In[1] Contention-aware transaction scheduling arriving in
InnoDB to boost performance. http://
mysqlserverteam.com/contention-aware-transactionscheduling-arriving-in-innodb-to-boost-performance/.
[2] Db2 documentation. https://www.ibm.com/support/
knowledgecenter/en/SSEPEK 12.0.0/perf/src/tpc/
db2z lockcontention.html.
[3] Mysql source code. https://github.com/mysql/mysqlserver/blob/5.7/storage/innobase/lock/lock0lock.cc.
[4] Overview of teradata database locking. http://info.teradata.com/HTMLPubs/DB TTU 16 00/
index.html#page/General Reference%2FB035-1091160K%2Fmtg1472241438567.html.
[5] Postgres documentation.
https://github.com/postgres/postgres/blob/master/
src/backend/storage/lmgr/README.
[6] Sql server, lock manager, and relaxed fifo.
https://blogs.msdn.microsoft.com/psssql/2009/06/02/
sql-server-lock-manager-and-relaxed-fifo/.
[7] R. Abbott and H. Garcia-Molina. Scheduling real-timetransactions. SIGMOD Rec., pages 71–81, 1988.
[8] R. K. Abbott and H. Garcia-Molina. Scheduling
real-time transactions: A performance evaluation.
TODS, pages 513–560, 1992.
[9] B. Adelberg, B. Kao, and H. Garcia-Molina. Databasesupport for efficiently maintaining derived data. In
EDBT, pages 223–240, 1996.
[10] R. Agrawal, M. J. Carey, and L. W. McVoy. The
performance of alternative strategies for dealing withdeadlocks in database management systems. TSE,
pages 1348–1363, 1987.
[11] D. V. Aken, A. Pavlo, G. J. Gordon, and B. Zhang.
Automatic database management system tuning
through large-scale machine learning. In SIGMOD,
pages 1009–1024, 2017.
[12] S. Altmeyer, S. M. Sundharam, and N. Navet. The
case for fifo real-time scheduling. Technical report,
2016.
[13] R. F. Aranha, V. Ganti, S. Narayanan,
C. Muthukrishnan, S. Prasad, and K. Ramamritham.
Implementation of a real-time database system.
Information Systems, pages 55–74, 1996.
[14] C. Bector, Y. P. Gupta, and M. C. Gupta. V-shapeproperty of optimal sequence of jobs about a common
due date on a single machine. Computers & operations
research, pages 583–588, 1989.
[15] P. A. Bernstein and N. Goodman. Concurrency
control in distributed database systems. ACM
Computing Surveys, pages 185–221, 1981.
[16] D. P. Bovet and M. Cesati. Understanding the Linuxkernel. 2005.
[17] X. Cai. V-shape property for job sequences thatminimize the expected completion time variance.
EJOR, 1996.
[18] M. J. Carey and M. Stonebraker. The performance ofconcurrency control algorithms for databasemanagement systems. In VLDB, pages 107–118, 1984.
[19] S. Chakravarthy, D.-K. Hong, and T. Johnson.
Real-time transaction scheduling: A framework forsynthesizing static and dynamic factors. RTSS, pages
135–170, 1998.

660

RTSS, pages 232–242, 1991.
algorithm for deadlock detection and resolution. In
PODC, pages 282–284, 1984.
[39] C. He, J. Y.-T. Leung, K. Lee, and M. L. Pinedo.
Improved algorithms for single machine scheduling[58] B. Mozafari, C. Curino, A. Jindal, and S. Madden.
with release dates and rejections. 4OR, pages 41–55,
Performance and resource modeling in
2016.
highly-concurrent OLTP workloads. In SIGMOD,
2013.
[40] D. Hong, T. Johnson, and S. Chakravarthy. Real-timetransaction scheduling: a cost conscious approach.
[59] B. Mozafari, C. Curino, and S. Madden. DBSeer:
1993.
Resource and performance prediction for building anext generation database cloud. In CIDR, 2013.
[41] J. A. Hoogeveen and A. P. Vestjens. Optimal on-line
algorithms for single-machine scheduling. In[60] B. Mozafari, J. Ramnarayan, S. Menon, Y. Mahajan,
International Conference on Integer Programming and
S. Chakraborty, H. Bhanawat, and K. Bachhav.
Combinatorial Optimization, pages 404–414, 1996.
Snappydata: A unified cluster for streaming,
transactions, and interactive analytics. In CIDR, 2017.
[42] W. Horn. Single-machine job sequencing with treelike
precedence ordering and linear delay penalties. SIAP,[61] R. R. Muntz and E. G. Co↵man Jr. Preemptive
pages 189–202, 1972.
scheduling of real-time tasks on multiprocessor
systems. JACM, pages 324–338, 1970.
[43] J. Huang. Real-time transaction processing: design,
implementation, and performance evaluation. PhD[62] J. Pei, X. Liu, P. M. Pardalos, W. Fan, and S. Yang.
thesis, University of Massachusetts, 1991.
Scheduling deteriorating jobs on a single
serial-batching machine with multiple job types and[44] J. Huang, B. Mozafari, G. Schoenebeck, andsequence-dependent setup times. Annals of Operations
T. Wenisch. A top-down approach to achieving
Research, pages 175–195, 2017.
performance predictability in database systems. In
SIGMOD, 2017.
[63] F. Petrini, D. J. Kerbyson, and S. Pakin. The case of
the missing supercomputer performance: Achieving[45] J. Huang, B. Mozafari, and T. Wenisch. Statisticaloptimal performance on the 8,192 processors of asci q.
analysis of latency through semantic profiling. In
In Supercomputing, 2003 ACM/IEEE Conference,
EuroSys, 2017.
pages 55–55, 2003.
[46] T. Ibaraki, T. Kameda, and N. Katoh. Cautious[64] C. Phillips, C. Stein, and J. Wein. Scheduling jobs
transaction schedulers for database concurrency
that arrive over time. In WADS, pages 86–97, 1995.
control. TSE, pages 997–1009, 1988.
[65] K. Ramamritham. Real-time databases. Distributed[47] G. C. Kamath. Bounds on the expectation of theand parallel databases, pages 199–226, 1993.
maximum of samples from a gaussian. URL
http://www.gautamkamath.com/writings/gaussian max.pdf, [66] R. Rastogi, S. Seshadri, P. Bohannon, D. Leinbaugh,
2015.
A. Silberschatz, and S. Sudarshan. Improving
predictability of transaction execution times in[48] B. Kao and H. Garcia-Molina. An overview ofreal-time databases. RTSS, pages 283–302, 2000.
real-time database systems. In Real Time Computing,pages 261–282. 1994.
[67] A. J. Ruiz-Torres and G. Centeno. Scheduling withflexible resources in parallel workcenters to minimize[49] A. M. Krieger and M. Raghavachari. V-shapemaximum completion time. Computers & operations
property for optimal schedules with monotone penalty
research, pages 48–69, 2007.
functions. Computers & operations research, pages
533–534, 1992.
[68] L. Sha, R. Rajkumar, and J. P. Lehooczky.
Concurrency control for distributed real-time[50] J. Lee and S. H. Son. Performance of concurrency
databases. SIGMOD Rec., 1988.
control algorithms for real-time database systems.,
1996.
[69] J. B. Sidney. Decomposition algorithms for
single-machine sequencing with precedence relations[51] J. P. Lehoczky. Scheduling communication networks
and deferral costs. Operations Research, pages
carrying real-time traffic. In RTSS, pages 470–479,
283–298, 1975.
1998.
[70]
W. E. Smith. Various optimizers for single-stage[52] J. K. Lenstra, A. R. Kan, and P. Brucker. Complexity
production. Naval Research Logistics Quarterly, pagesof machine scheduling problems. Annals of discrete
59–66, 1956.
mathematics, pages 343–362, 1977.
[71] J. A. Stankovic, M. Spuri, K. Ramamritham, and[53] H. Leontyev and J. H. Anderson. Tardiness bounds for
G. C. Buttazzo. Deadline scheduling for real-time
fifo scheduling on multiprocessors. In ECRTS, pages
systems: EDF and related algorithms. 2012.
71–71, 2007.
[72] B. Tian, J. Huang, B. Mozafari, and G. Schoenebeck.
[54] Q. Lin, P. Chang, G. Chen, B. C. Ooi, K.-L. Tan, andContention-aware lock scheduling for transactional
Z. Wang. Towards a non-2pc transaction management
databases. Technical Report,
in distributed database systems. In SIGMOD, pages
https://web.eecs.umich.edu/⇠mozafari/php/data/
1659–1674, 2016.
uploads/lock-schd-report.pdf, 2017.
[55] C. L. Liu and J. W. Layland. Scheduling algorithms[73] D. Towsley and S. Panwar. On the optimality offor multiprogramming in a hard-real-timeminimum laxity and earliest deadline scheduling forenvironment. JACM, pages 46–61, 1973.
real-time multiprocessors. In Workshop on Real Time,[56] P. P. Macri. Deadlock detection and resolution in apages 17–24, 1990.
codasyl based data management system. In SIGMOD,[74] S.-M. Tseng, Y.-H. Chin, and W.-P. Yang. Schedulingpages 45–49, 1976.
[57] D. P. Mitchell and M. J. Merritt. A distributed661

real-time transactions with dynamic values: aperformance evaluation. In Workshop on Real-Time
Computing Systems and Applications, pages 60–67,
1995.
[75] Ö. Ulusoy and G. G. Belford. Real-time transaction
scheduling in database systems. Information Systems,
pages 559–580, 1993.
[76] V. Vani and M. Raghavachari. Deterministic andrandom single machine sequencing with varianceminimization. Operations Research, pages 111–120,
1987.

[77] M. Xiong, Q. Wang, and K. Ramamritham. On
earliest deadline first scheduling for temporalconsistency maintenance. RTSS, pages 208–237, 2008.
[78] D. Y. Yoon, B. Mozafari, and D. P. Brown. Dbseer:
Pain-free database administration through workload
intelligence. PVLDB, 8(12):2036–2039, 2015.
[79] R. Zajcew, P. Roy, D. L. Black, C. Peak, P. Guedes,
B. Kemp, J. LoVerso, M. Leibensperger, M. Barnett,
F. Rabii, et al. An osf/1 unix for massively parallel
multicomputers. In USENIX Winter, pages 449–468,
1993.

662