98 COMMUNICATIONS OF THE ACM | DECEMBER 2018 | VOL. 61 | NO. 12
systems either implement a simple service (e.g., get/put)
that can partition requests across cores; 10 or they develop
sophisticated concurrent data structures from scratch to
support more complex operations, 11 and doing this requires
expertise in concurrent algorithms. This is where our black-box approach comes handy: NR provides these concurrent
data structures automatically from single-threaded implementations. For Redis, we were able to convert a single-threaded sorted set into a concurrent one with just 20 new
lines of wrapper code. The result outperforms data structures obtained from other methods by up to 14x.
Although NR is powerful, easy to use, and efficient, it
has three limitations. First, it incurs space overhead due
to replication: it consumes n times more memory, where
n is the number of nodes. Thus, NR is best suited for
smaller structures that occupy just a fraction of the available memory (e.g., up to hundreds of MB). Second, NR is
blocking: a thread that stops executing operations can
block the progress of other threads; in practice, we did
not find that to be a problem as long as threads keep executing operations on the data structure. Finding a nonblocking variant of NR is an interesting research
direction. Finally, NR may be outperformed by non-black-box algorithms crafted for a given data structure—
For example, a lock-free skip list running on
low-contention workloads, or a NUMA-aware stack. 2
Thus, the generality of black-box methods has some cost.
However, in some cases NR outperforms even the crafted
algorithms; we observe this for the same lock-free skip
list running instead on high-contention workloads.
We plan to make the source code for NR available in our
project page at https://research.vmware.com/projects/
2. 1. NUMA architectures
Our work is motivated by recent trends in computer archi-
tecture. To support a large number of cores, data center
servers have adopted a NUMA architecture with many pro-
cessor sockets or nodes (see Figure 1). Each node has
many processor cores and a shared cache, while individ-
ual cores have private caches. Sharing a cache line within
a node is more efficient than across nodes because the
cache coherence protocol operates more efficiently
within a node. Each node has some local memory, and a
core can access local memory faster than memory in a
remote node. A similar architecture—Non-Uniform
Cache Access (NUCA)—has a single shared memory but
nodes have local caches as in NUMA. Our ideas are appli-
cable to NUCA too. NUMA is everywhere now. A high-per-
formance Intel server might have eight processors
(nodes), each with 28 cores, while a typical server might
have two processors, each with 8–16 cores. AMD and
Oracle have similar machines. To best use these cores, we
need appropriate concurrent data structures.
2. 2. Concurrent data structures
Concurrent data structures permit many threads to operate
on common data using a high-level interface. When a data
structure is accessed concurrently by many threads, its
semantics are typically defined by a property called linearizability, 8 which provides strong consistency. Linearizability
requires that each operation appear to take effect instantly at
some point between the operation’s invocation and response.
The key challenge in designing concurrent data structures is dealing with operation contention, which occurs
when an operation often affects the output of another
operation. More precisely, given an execution, we say that
an operation affects another if the removal of the first
causes the second to return a different result. For example, a write of a new value affects a subsequent read. A
workload has operation contention if a large fraction of
operations affect a large fraction of operations occurring
soon after them. Examples include a storage system where
users read and write a popular object, a priority queue
where threads often remove the minimum element, a
stack where threads push and pop data, and a bounded
queue where threads enqueue and dequeue data. Non-examples include read-only workloads and write-only
workloads where writes do not return a result. Operation
contention is challenging because operations must
observe each other across cores.
Much work has been devoted to designing and implementing efficient concurrent data structures; we provide a
broad overview in Calciu, Sen et al. 3 Unfortunately, each data
structure requires its own algorithm with novel techniques,
which involve considerable work from experts in the field.
To get a sense, a new concurrent data structure often leads
to a scientific publication just for its algorithm.
Unfortunately, most existing concurrent data structures
and techniques are for Uniform Memory Access (UMA),
including some prior black-box methods. 5, 6, 16 These algorithms are not sensitive to the asymmetry and limitations of
NUMA, which hinders their performance. 9 There are some
recent NUMA-aware algorithms, 2, 12, 14 but they cover few data
structures. Moreover, these solutions are not applicable
when applications compose data structures and wish to
modify several of them with a single composed operation
(e.g., remove an item from a hash table and a skip list simultaneously). This is the case in the Redis application, which
we describe later in the paper.
Figure 1. NUMA architecture of a modern server in a data center.
The server has many processor sockets, herein called nodes. Each
node has many processor cores and some local memory. Nodes are
connected by an interconnect, so that cores in one node can access
the remote memory of another node, but these accesses come at a
cost. Typically, cores have local caches, and cores on a node share a
last level cache.