Optimizing optimistic concurrency control for tree-structured, log-structured databases

Scaling-out a database system typically requires partitioning the
database across multiple servers. If applications do not partition
perfectly, then transactions accessing multiple partitions end up
being distributed, which has well-known scalability challenges. To
address them, we describe a high-performance transaction mechanism
that uses optimistic concurrency control on a multi-versioned
tree-structured database stored in a shared log. The system scales
out by adding servers, without partitioning the database.
Our solution is modeled on the Hyder architecture, published by
Bernstein, Reid, and Das at CIDR 2011. We present the design and
evaluation of the first full implementation of that architecture. The
core of the system is a log roll-forward algorithm, called meld, that
does optimistic concurrency control. Meld is inherently sequential
and is therefore the main bottleneck. Our main algorithmic contributions
are optimizations to meld that significantly increase transaction
throughput. They use a pipelined design that parallelizes
meld onto multiple threads. The slowest pipeline stage is much
faster than the original meld algorithm, yielding a 3x improvement
of system throughput over the original meld algorithm.