Abstract
In this paper,
we propose a method to implement any concurrent
data structure.
Our method produces implementations that work particularly well
in non-uniform memory access (NUMA) machines.
Due to recent architecture trends, highly concurrent servers
today are NUMA machines, where the cost of accessing a memory location
is not the same across every core.
To fully leverage these machines, programmers need efficient concurrent
data structures that are aware of the NUMA performance artifacts.
We propose Node Replication (NR), a black-box approach to obtaining such data structures.
NR takes an arbitrary sequential data structure and automatically transforms it into
a NUMA-aware concurrent data structure satisfying linearizability.
Using NR requires no expertise in
concurrent
data structure design, and the result is free of concurrency
bugs.
NR draws ideas from two disciplines:
shared-memory algorithms and distributed systems.
Briefly, NR implements a NUMA-aware shared
log, and then uses the log to replicate data structures
consistently across NUMA nodes.
The cost of NR is additional memory for its
log and replicas.