Neha Narula,
Cody Cutler,
Eddie Kohler,
Robert T. Morris
Doppel is an in-memory multicore database that implements phase reconciliation, a technique for executing transactions on contended data in parallel.
Publications
Phase Reconciliation for Contended In-Memory Transactions
Abstract PDF
Neha Narula, Cody Cutler, Eddie Kohler, and Robert T. Morris.
In the Proceedings of the Symposium on Operating Systems Design and Implementation (OSDI 2014), Broomfield, Colorado, October 2014.
Multicore main-memory database performance can collapse when many transactions contend on the same data.
Contending transactions are executed serially--either
by locks or by optimistic concurrency control aborts--in order
to ensure that they have serializable effects.
This leaves many cores idle and performance poor.
We introduce a new concurrency control technique, phase reconciliation,
that solves this problem for many important workloads.
Doppel, our phase reconciliation database, repeatedly cycles through
joined, split, and reconciliation phases.
Joined phases use traditional concurrency control and allow any transaction to execute.
When workload contention causes unnecessary
serial execution, Doppel switches to a split phase.
There, updates to contended items modify per-core state,
and thus proceed in parallel on different cores. Not all transactions can
execute in a split phase; for example, all modifications to a
contended item must commute.
A reconciliation phase merges these per-core states into the global store,
producing a complete database ready for joined phase transactions.
A key aspect of this design is determining which items to split,
and which operations to allow on split items.
Phase reconciliation helps most when there are many updates to
a few popular database records.
Its throughput is up to 38X higher than conventional
concurrency control protocols
on microbenchmarks, and up to 3X on a larger application,
at the cost of increased latency for some transactions.
Software
This code is rough and doesn't implement many features of a
production-quality database. Use at your own risk.
$ git clone git@github.com:narula/ddtxn.git