USENIX Association 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI ’14) 511 Phase Reconciliation for Contended In-Memory Transactions

Multicore main-memory database performance can col-lapse 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 intro-duce a new concurrency control technique, phase recon-ciliation, that solves this problem for many important workloads. Doppel, our phase reconciliation database, repeatedly cycles through joined, split, and reconcilia-tion phases. Joined phases use traditional concurrency control and allow any transaction to execute. When workload contention causes unnecessary serial execu-tion, Doppel switches to a split phase. There, updates to contended items modify per-core state, and thus pro-ceed in parallel on different cores. Not all transactions can execute in a split phase; for example, all modifica-tions to a contended item must commute. A reconcilia-tion 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 deter-mining which items to split, and which operations to al-low on split items. Phase reconciliation helps most when there are many updates to a few popular database records. Its through-put is up to 38 × higher than conventional concurrency control protocols on microbenchmarks, and up to 3 × on a larger application, at the cost of increased latency for some transactions.