Doctoral Thesis: Parallel Execution for Conflicting Transactions


Event Speaker: 

Neha Narula

Event Location: 

32-G882 (Hewlett Room)

Event Date/Time: 

Monday, May 11, 2015 - 1:00pm


Multi-core main-memory databases only obtain parallel performance when

transactions do not contend on the same data.  Contending transactions

are executed serially---either through locks or through optimistic

concurrency control aborts---in order to ensure that they have

serializable effects.  Serialization on contended data leaves cores idle

and reduces throughput, so many techniques have been developed to avoid

it.  A common technique to reduce contention on shared variables

leverages per-core state.  These techniques are used in limited

contexts, such as per-core counters for network devices.  Can these

ideas fruitfully be applied in a far more general context, specifically,

serializable transactions?


This work introduces a new concurrency control technique, phase

reconciliation, that uses per-core state to greatly reduce contention on

popular database records for many important workloads.  Phase

reconciliation uses the idea of synchronized phases to amortize the cost

of combining per-core data and to extract parallelism.


Doppel, our phase reconciliation database, repeatedly cycles through

joined and split 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.

During a split phase, commutative operations on popular records act on

per-core state, and thus proceed in parallel on different cores.  By

explicitly using phases, phase reconciliation realizes two important

performance benefits: First, it amortizes the potentially high costs of

aggregating per-core state over many transactions.  Second, it can

dynamically split data or not based on observed contention, handling

challenging, varying workloads.


Phase reconciliation helps most when there are many updates to a few

popular database records.  On an 80-core machine, its throughput is up

to 38$\times$ higher than conventional concurrency control protocols on

microbenchmarks, and up to 3$\times$ on a larger application, at the

cost of increased latency for some transactions.  Doppel achieves higher

performance because it parallelizes transactions on popular data that

would be serialized by conventional concurrency control.


Thesis Supervisors: Robert Morris and Eddie Kohler