PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking serializable multiversion concurrency control

Jose M. Faleiro, Daniel J. Abadi

arXiv:1412.2324v3cs.DB

TL;DR

Serializable multiversion systems often sacrifice read-write concurrency or incur synchronization costs, motivating a more scalable design. BOHM preorders transactions and separates concurrency control from execution, achieving serializable execution with reads that never block writes. Experiments report strong multicore scalability and performance, including linear scaling to at least 20 million record accesses per second.

  • Problem

    Serializable multiversion systems often restrict read-write concurrency or require costly coordination, weakening their multicore performance advantage over single-version systems.

  • Method

    BOHM assigns transactions a total order and separates concurrency control from execution, preparing versions before transaction logic runs.

  • Results

    BOHM maintains serializability while reads do not block writes and achieves linear scalability up to at least 20 million record accesses per second across dozens of cores.

  • Takeaways & Limitations

    BOHM provides a scalable multiversion concurrency-control alternative that preserves serializability and outperforms other multiversion systems in the reported experiments.

  • Takeaways & Limitations

    BOHM’s concurrency-control design requires advance write-set knowledge and can face diminishing scalability because every concurrency-control thread examines every transaction.

Abstract

from arXiv · show

Multi-versioned database systems have the potential to significantly increase the amount of concurrency in transaction processing because they can avoid read-write conflicts. Unfortunately, the increase in concurrency usually comes at the cost of transaction serializability. If a database user requests full serializability, modern multi-versioned systems significantly constrain read-write concurrency among conflicting transactions and employ expensive synchronization patterns in their design. In main-memory multi-core settings, these additional constraints are so burdensome that multi-versioned systems are often significantly outperformed by single-version systems. We propose Bohm, a new concurrency control protocol for main-memory multi-versioned database systems. Bohm guarantees serializable execution while ensuring that reads never block writes. In addition, Bohm does not require reads to perform any book-keeping whatsoever, thereby avoiding the overhead of tracking reads via contended writes to shared memory. This leads to excellent scalability and performance in multi-core settings. Bohm has all the above characteristics without performing validation based concurrency control. Instead, it is pessimistic, and is therefore not prone to excessive aborts in the presence of contention. An experimental evaluation shows that Bohm performs well in both high contention and low contention settings, and is able to dramatically outperform state-of-the-art multi-versioned systems despite maintaining the full set of serializability guarantees.

1. INTRODUCTION

Multi-versioning enables concurrent reads and writes, but achieving serializability can sharply reduce that concurrency or add costly coordination. BOHM separates concurrency control from execution to preserve serializability and read-write concurrency while scaling across cores.

  • Motivation: Multi-versioned systems let reads proceed alongside writes, but serializable designs often restrict read-write concurrency or add coordination overhead.Reads can use older versions while writes proceed, yet existing serializable approaches may perform little better than single-version systems or incur poorer multicore performance.
  • BOHM: BOHM determines transaction order and creates write versions before execution, guaranteeing serializability while ensuring reads never block writes.The protocol avoids the additional coordination and bookkeeping used by other serializable multiversion methods.
  • Trade-offs: BOHM requires complete transaction submission and advance knowledge of each transaction’s write-set, so traditional cursor-oriented access is unsupported.Write-sets may be declared, analyzed, or predicted optimistically before execution.
  • Evaluation: BOHM supports stored-procedure workloads and achieves linear scalability up to at least 20 million record accesses per second across dozens of cores.The paper presents this performance as the cost-benefit trade-off of requiring complete transactions with deducible write-sets in advance.
  • BOHM: BOHM separates concurrency control from transaction processing, using distinct threads so execution proceeds without concern for concurrent transactions.The modular design improves database-engine maintainability and reduces database-administrator complexity.

2. MOTIVATION

Multiversion systems must manage timestamps and anti-dependencies without sacrificing the concurrency that motivates multiple versions. BOHM addresses these problems by assigning a total order before execution and avoiding read tracking or validation.

  • Timestamp bottlenecks: Global timestamp counters require shared atomic updates and do not scale well to high core counts.This bottleneck affects multiversion systems broadly, including systems using weaker isolation levels.
  • BOHM’s approach: BOHM assigns transactions a total order before execution, using each transaction’s position in that order as its timestamp.Execution then produces a database state identical to serial execution in the assigned order.
  • Serializability: Unrestrained concurrent reads and writes can create cyclic serialization graphs, producing non-serializable executions such as snapshot isolation’s write-skew anomaly.The example contains opposing anti-dependency edges between the two transactions.
  • Existing approaches: Serializable multiversion protocols commonly track reads or validate them, but tracking causes shared-memory contention while validation can abort readers.Both costs reduce concurrency between readers and writers.
  • BOHM’s approach: BOHM targets read-write concurrency by ensuring reads neither block nor abort concurrent writers and by requiring no shared-memory writes for record reads.These goals directly address the coordination and concurrency costs of tracking and validating reads.

3. DESIGN

BOHM separates concurrency-control planning from transaction execution so threads can make decisions locally or amortize coordination across batches. This design improves concurrency but requires complete transactions and advance write-set knowledge.

  • Architecture: BOHM processes transactions in separate concurrency-control and execution phases.The first phase determines serialization order and prepares execution data structures; the second runs transaction logic.
  • Requirement: The concurrency-control phase requires advance knowledge of each transaction’s write-set to plan execution correctly.Write-sets may be declared, derived, or predicted speculatively, but the entire transaction must still be submitted at once.

3.1 System Overview

BOHM logs transactions to establish an uncontended order, prepares version placeholders before execution, and lets execution threads resolve reads against those placeholders. Reads therefore never block writes, although writes may block reads.

  • Execution pipeline: Concurrency-control threads prepare the transaction log and version structures before execution threads perform reads and fill preallocated write locations.The execution phase begins only after the corresponding batch has been prepared.
  • Read-write behavior: Reads navigate version placeholders to find the serializable version, so reads never block writes, although an uninitialized required version can block a read.The architecture avoids record- or transaction-granularity synchronization during execution.

3.2 Concurrency Control

BOHM separates concurrency control from transaction execution: it assigns timestamps, creates write versions, and prepares execution before transaction logic runs. Partitioned concurrency-control threads process write-sets without coordination, while reads avoid contended shared-memory bookkeeping.

  • Timestamp assignment: The concurrency control layer determines serialization order and creates a safe environment for concurrent transaction execution.Transactions are inserted into a main-memory log before processing; their log positions provide uncontended timestamps.
  • Timestamp assignment: BOHM assigns each transaction one timestamp that determines both its read visibility and when its writes become visible.This single timestamp combines the logical roles played by begin and end timestamps in prior schemes.
  • Version creation: The concurrency control layer inserts placeholder versions for every record in a transaction’s write-set before execution produces their data.Each version records timestamps, a transaction pointer, data storage, and a pointer to the preceding version.
  • Intra-transaction parallelism: Several concurrency-control threads cooperatively process one transaction by partitioning responsibility for its written records.For transaction 200, CC1 handles a, CC2 handles b and c, and CC3 handles d.
  • Intra-transaction parallelism: Fixed record ownership lets concurrency-control threads process transactions without coordinating on individual records, reducing cache-coherence traffic and supporting multicore scalability.Adding threads increases intra-transaction parallelism, although examining every transaction can eventually impose an Amdahl’s-law bottleneck.
  • Read processing: BOHM does not track reads in the database, so transaction reads require no contended writes to shared memory.The concurrency-control layer supplies references to the latest visible versions, while any optional reference writes target pre-allocated transaction-local space.

3.3 Transaction Execution

After concurrency control creates ordered version placeholders, BOHM’s execution layer evaluates transaction logic and resolves dependencies. It also supports version garbage collection while preserving the serialization order established by timestamps.

  • Execution: The execution layer receives ordered transaction batches, evaluates transaction logic, and can incrementally garbage collect obsolete versions.Transactions are distributed among execution threads, with ownership obligations preserved across batches.
  • Dependencies: Overlapping write-sets do not by themselves require coordinated execution when the concurrency-control layer has already fixed update order.Read-modify-write operations still wait for the earlier version, and aborted transactions may also depend on that version’s value.
  • Dependencies: Execution threads recursively evaluate prerequisite transactions when a needed version’s data has not yet been produced.A transaction may wait for a dependency to finish before its own execution can complete.
  • Garbage collection: BOHM can reclaim a preceding version after all transactions with lower timestamps finish, using a conservative condition instead of tracking every reader.This avoids per-version reader metadata but requires a global low-watermark timestamp.
  • Garbage collection: Batch ordering provides an alternative garbage-collection condition: a preceding version can be reclaimed after every execution thread finishes the updating transaction’s batch.Transactions are naturally ordered across batches, making batch completion sufficient for this condition.
  • Correctness: BOHM preserves timestamp order in the serialization graph: if ts0 < ts1, the graph contains no dependency from T1 to T0.The invariant applies to write-write, write-read, and read-write dependencies.

4. EXPERIMENTAL EVALUATION

The evaluation shows that BOHM scales across cores and performs strongly under both high- and low-contention workloads, while preserving serializability. Its advantages arise from avoiding aborts, read-write blocking, and centralized coordination bottlenecks.

  • Concurrency control scalability: The division between concurrency-control and execution threads matters: too few concurrency-control threads underutilize execution, while too many leave insufficient execution capacity.Throughput rises until the execution and concurrency-control layers match, after which the other layer becomes the bottleneck.
  • Concurrency control scalability: BOHM’s concurrency-control and execution layers scale linearly as threads increase, reaching nearly 2 million transactions per second, or nearly 20 million RMW operations per second.The peak was measured while increasing concurrency-control and execution threads in unison.
  • YCSB workloads: Under high contention, BOHM achieves over twice the throughput of Hekaton and Snapshot Isolation because it avoids the aborts caused by conflicting writes.All multi-versioned systems incur version-management overhead on the 100% RMW workload, but BOHM avoids wasted work from aborts.
  • YCSB workloads: Under low contention, BOHM, Hekaton, and Snapshot Isolation have similar performance, while Hekaton and Snapshot Isolation marginally outperform BOHM in this implementation.The comparison is affected by the other systems’ lack of garbage collection and use of array-based indices.
  • 2RMW-8R workload: For the 2RMW-8R workload under high contention, BOHM significantly outperforms Snapshot Isolation by avoiding write-write-conflict aborts and allowing reads to avoid blocking writes.Snapshot Isolation and Hekaton suffer aborts and wasted work, whereas BOHM orders writes before execution and fills placeholders without aborting for write-write conflicts.
  • 2RMW-8R workload: Under low contention, Hekaton and Snapshot Isolation stop scaling beyond 20 cores because their global timestamp counter becomes a contention bottleneck.BOHM remains close to OCC despite the overhead of maintaining multiple versions.

5. RELATED WORK

Prior work improves serializability, scalability, or multi-version concurrency through timestamp ordering, optimistic validation, deterministic ordering, partitioning, and intra-transaction parallelism. BOHM shares some design elements with these systems but targets serializable multi-version execution and multicore scalability through a distinct combination of techniques.

  • Snapshot Isolation permits reads and writes of the same record to proceed concurrently but can violate serializability, whereas BOHM guarantees serializability.
  • Serializable Snapshot Isolation tracks anti-dependencies during execution and aborts transactions to prevent serializability violations.
  • Optimistic multi-version protocols use timestamp coordination and may abort reading transactions when read-write conflicts occur.
  • BOHM differs from Silo by avoiding optimistic concurrency control while using a low-contention technique to generate relative transaction-ordering timestamps.
  • Related scalable designs reduce synchronization through intra-transaction parallelism, modular separation, lock co-location, partitioning, or deterministic ordering, but differ from BOHM in architecture or execution strategy.

6. CONCLUSIONS

The paper concludes that BOHM combines serializable concurrency control with nonblocking reads and writes in a main-memory multicore system. Its experiments report substantial performance advantages over other multi-versioned systems and over single-versioned systems on read-write workloads where multi-versioning helps.

  • BOHM achieves serializable concurrency control while using multiple versions so reads do not block writes.
  • BOHM significantly outperforms other multi-versioned systems while preserving serializability guarantees.
  • Under high contention with mixed reads and writes, BOHM outperforms single-versioned optimistic and pessimistic systems without giving up serializability.
Loading 1412.2324v3…