PaperlayerView exact revision on arXiv

Source-linked AI summary

High-Performance Concurrency Control Mechanisms for Main-Memory Databases

Per-Åke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M. Patel, Mike Zwilling

arXiv:1201.0228v1cs.DB

TL;DR

Main-memory systems create a need for concurrency control that scales beyond conventional locking under high transaction rates, contention, and long transactions. The paper introduces optimistic and pessimistic MVCC methods, compares them with optimized single-version locking, and finds that MVCC is more robust while optimistic MVCC achieves higher throughput. The study also identifies deadlock-detection imprecision and asynchronous logging as supported scope considerations.

  • Problem

    Conventional concurrency-control methods do not scale reliably to high transaction rates in main-memory databases, especially with contention or long read-only transactions.

  • Method

    The paper develops optimistic and pessimistic MVCC mechanisms for main-memory databases, redesigns single-version locking, and evaluates all three approaches across workloads.

  • Results

    MVCC methods are more robust than single-version locking, retaining good throughput with hotspots and long read-only transactions; optimistic MVCC consistently outperforms pessimistic MVCC.

  • Takeaways & Limitations

    Single-version locking is suitable mainly for short, low-contention transactions, whereas more demanding workloads favor multiversion methods.

  • Takeaways & Limitations

    Deadlock detection may produce false deadlocks because normal processing continues during graph construction, requiring verification; the experiments also focus on asynchronous logging.

Abstract

from arXiv · show

A database system optimized for in-memory storage can support much higher transaction rates than current systems. However, standard concurrency control methods used today do not scale to the high transaction rates achievable by such systems. In this paper we introduce two efficient concurrency control methods specifically designed for main-memory databases. Both use multiversioning to isolate read-only transactions from updates but differ in how atomicity is ensured: one is optimistic and one is pessimistic. To avoid expensive context switching, transactions never block during normal processing but they may have to wait before commit to ensure correct serialization ordering. We also implemented a main-memory optimized version of single-version locking. Experimental results show that while single-version locking works well when transactions are short and contention is low performance degrades under more demanding conditions. The multiversion schemes have higher overhead but are much less sensitive to hotspots and the presence of long-running transactions.

1. INTRODUCTION

Main-memory databases can deliver very high transaction rates, but conventional locking struggles with scalability, contention, and long read-only transactions. The paper develops and evaluates optimized single-version and multiversion concurrency-control mechanisms for these conditions.

  • Motivation: Declining memory prices make it increasingly feasible for OLTP databases to fit entirely, or largely, in main memory.The paper notes a tenfold price decrease every five years over the preceding 30 years and the availability of systems with 2TB of main memory.
  • Motivation: High transaction rates make isolation difficult because traditional lock managers can bottleneck, while long read-only transactions may block writers.These problems motivate concurrency-control mechanisms designed specifically for many-core, in-memory systems.
  • Findings: Single-version locking works well with short transactions and low contention but degrades rapidly under high contention or even one long transaction.The authors characterize this behavior as fragile.
  • Approach: The paper designs optimistic and pessimistic MVCC mechanisms for main-memory settings and evaluates them alongside redesigned single-version locking.The MVCC methods are mutually compatible, allowing optimistic and pessimistic transactions to access the same database concurrently.
  • Findings: Higher contention or workloads with long transactions favor multiversion methods, while the optimistic method achieves higher throughput than the pessimistic method.The paper presents these conclusions as directly applicable to high-performance main-memory databases.

2. MV STORAGE ENGINE

The storage engine represents records with time-bounded versions and uses logical read times to determine visibility. Transactions progress through nonblocking normal processing, then complete serialization-related work before commit.

  • Serializability: Serializable execution requires read stability and phantom avoidance, which can be implemented through locking or validation.Read stability preserves versions observed during processing, while phantom avoidance prevents scans from gaining additional versions.
  • Version Visibility: A read sees only the version whose valid-time interval overlaps its logical read time, so at most one version of a record is visible.The read time may lie between the transaction’s begin time and the current time, depending on the concurrency-control method and isolation level.
  • Version Storage: Each record update creates a new version, with Begin and End fields recording validity boundaries and temporary transaction ownership.Committed versions receive timestamps; transaction IDs in these fields identify uncommitted ownership or write locks.
  • Transaction Phases: A transaction is Active, Preparing, Committed, or Aborted, and it never blocks during normal processing.Updates install transaction IDs in new and old versions; aborted transactions skip directly to finalization.
  • Version Visibility: When Begin and End contain timestamps, a version is visible exactly when the logical read time falls between those timestamps.If a field contains a transaction ID, visibility additionally depends on that transaction’s state and end timestamp.

3. OPTIMISTIC TRANSACTIONS

Optimistic transactions track reads, scans, and writes, then validate visibility and phantoms before waiting on dependencies and completing commit processing.

  • Normal Processing Phase: Optimistic transactions maintain ReadSet, ScanSet, and WriteSet structures to record reads, scans, and version changes.The WriteSet tracks old and new versions for updates, old versions for deletes, and new versions for insertions.
  • Normal Processing Phase: Index scans record their index, predicates, and logical read time, then filter versions by predicate and visibility.Serializable scans use the transaction’s begin time as the logical read time.
  • Normal Processing Phase: Reads add visible versions to ReadSet, while updates create new versions and atomically mark old versions with the transaction ID.A failed atomic update indicates a write-write conflict and forces the transaction to abort.
  • Preparation Phase: At precommit, optimistic validation checks that read versions remain visible and that repeated scans find no visible phantoms.The transaction aborts if either read validation or phantom detection fails.
  • Preparation Phase: A version created during the transaction and visible at its end is a phantom, whereas a version invisible at the end is not.The figure’s cases distinguish versions that pass or fail read validation from versions detected as phantoms.
  • Preparation Phase: After validation, the transaction waits for commit dependencies, logs its writes in end-timestamp order, and finalizes committed or aborted versions.Committed transactions propagate timestamps; aborted transactions make their new versions invisible and attempt to restore old versions.

4. PESSIMISTIC TRANSACTIONS

Pessimistic transactions use multiversion locking to prevent read invalidation while tracking read, bucket, and write state needed for serializable execution.

  • PESSIMISTIC TRANSACTIONS: Pessimistic transactions prevent read invalidation by acquiring read locks on versions.Serializable transactions also track scanned hash buckets and their new and old versions.

4.1 Lock Types

The pessimistic design uses record locks for read stability and bucket locks for phantom prevention, with locks embedded or maintained in lightweight structures.

  • Lock Types: Record locks protect versions from read invalidation, while bucket locks prevent phantoms during serializable scans.Range locks for ordered indexes can use analogous tree-node or skip-list tower locking.
  • Record Locks: Updates and deletes target only the latest record version, so older versions never require locks.This design needs an efficient many-readers-single-writer lock for the latest version.
  • Record Locks: Record locks are embedded in each version’s 64-bit End field rather than stored in a separate table.The field encodes either a timestamp or a record-lock structure.
  • Record Locks: Transactions record their ReadSets instead of explicitly identifying readers on each version, primarily to support infrequent deadlock detection.Read-lock acquisition increments ReadLockCount and can abort when the count reaches 255 or NoMoreReadLocks is set.
  • Bucket Locks: A write lock atomically stores the owning transaction ID in the version’s WriteLock field.Bucket locks similarly maintain a count and a list of serializable transactions holding each bucket.

4.2 Eager Updates, Wait-For Dependencies

Eager updates avoid blocking during normal processing, while wait-for dependencies postpone precommit until conflicting read or bucket locks are released.

  • Eager Updates, Wait-For Dependencies: Traditional multiversion locking can block updates on read-locked versions or locked buckets, causing expensive thread switches.The paper notes that a thread switch costs several thousand instructions.
  • Eager Updates: Eager updates allow transactions to modify read-locked versions, but precommit waits until all relevant read locks are released.Readers may also lock a version already write-locked, forcing the writer to wait before precommit.
  • Eager Updates: Updates into locked buckets are allowed, but precommit waits until every serializable bucket locker completes and releases its lock.The same rule preserves serialization for phantom-sensitive scans.
  • Wait-For Dependencies: Wait-for dependencies delay acquiring an end timestamp and come in read-lock and bucket-lock forms.Transactions track both incoming dependencies they await and outgoing dependencies held by transactions waiting on them.
  • Read Lock Dependencies: A writer with read-lock dependencies waits while ReadLockCount remains nonzero, and the final reader releases the dependency before the writer can commit.NoMoreReadLocks prevents new readers from postponing a writer after its dependencies are otherwise cleared.
  • Bucket Lock Dependencies: Bucket dependencies are installed when updates encounter locked buckets or when scans encounter active invisible versions that could become phantoms.Transactions abort if NoMoreWaitFors prevents installing a required dependency.
  • Wait-For Dependencies: After precommit and timestamp acquisition, a serializable transaction releases outgoing dependencies by decrementing waiting transactions’ counters.This allows dependent transactions to continue when their counters reach zero.

4.3 Processing Phases

Pessimistic transactions perform scans according to isolation level, using locks for protection and dependencies when conflicts arise. They avoid validation but may wait before committing.

  • Pessimistic scans use transaction-begin time for snapshot isolation and current time for other isolation levels.
  • Serializable scans take bucket locks to prevent phantoms; other isolation levels do not take them.
  • Serializable or repeatable-read scans attempt read locks on latest versions and abort if those locks cannot be acquired.
  • Updates create new versions, set write locks, add index entries, and create wait-for dependencies when conflicting locks exist.
  • Pessimistic transactions skip validation, but wait for outstanding commit dependencies before logging and committing; failed dependencies cause aborts.

4.4 Deadlock Detection

Deadlock detection constructs a wait-for graph from blocked transactions and dependency edges, then searches for cycles. Because processing continues during construction, the graph can be imprecise and false detections are possible.

  • Commit dependencies cannot cause or participate in deadlocks, whereas wait-for dependencies can.
  • The wait-for graph represents transactions as nodes and waiting relationships as directed edges.
  • Graph construction creates nodes for blocked transactions and adds edges from explicit bucket-lock and implicit read-lock dependencies.
  • Normal processing continues while the graph is built, so the resulting graph may differ from a stopped-processing graph.
  • False deadlocks are possible, but the prototype verifies that participating transactions remain blocked and dependencies remain unresolved.

4.5 Peaceful Coexistence

Optimistic and pessimistic transactions can coexist and access the same database concurrently. Optimistic updates must honor the locks used by pessimistic transactions.

  • Optimistic and pessimistic transactions can be mixed while accessing the same database concurrently.
  • Optimistic update transactions honor read locks and bucket locks to coexist with pessimistic transactions.
  • Optimistic updates on read-locked versions and locked index buckets create wait-for dependencies as needed.

5. EXPERIMENTAL RESULTS

The experiments compare optimized single-version locking with optimistic and pessimistic multiversion control on a many-core main-memory system. Single-version locking has the highest low-contention throughput, while multiversion schemes are less sensitive to contention but incur overhead.

  • Experimental setup: The system uses partitioned lock tables embedded in indexes rather than a central lock manager, avoiding a potential bottleneck.
  • Experimental setup: The experiments run on a two-socket, six-core-per-socket Intel Xeon X5650 system with NUMA memory latency asymmetry.
  • Experimental setup: The prototype compares single-version locking (1V), optimistic multiversion control (MV/O), and pessimistic multiversion control (MV/L).
  • Scalability: Under low contention, all three schemes scale linearly through six threads; NUMA effects appear afterward and HyperThreading effects beyond twelve threads.
  • Scalability: 1V reaches over 2M transactions/sec, while multiversion schemes have lower throughput because of version management and garbage collection overhead.
  • Scalability: MV/L has 30% lower performance than MV/O, with extra dependency and lock writes causing more memory traffic.
  • Contention: Under extreme contention, all schemes exceed one million transactions/sec, with MV/O slightly ahead of both locking schemes.
  • Higher isolation levels: At higher isolation, repeatable-read overhead is below 2% for both locking schemes, while serializable multiversion execution costs 10%–19% throughput.

5.2 Heterogeneous Workload

Heterogeneous workloads reveal that multiversion schemes become increasingly advantageous as read-only transactions, contention, or transaction duration increase. In a realistic OLTP benchmark, all three methods sustain several million transactions per second.

  • Impact of Short Read Transactions: As read-only transactions increase, throughput differences narrow because reduced update activity lowers garbage-collection overhead.
  • Impact of Short Read Transactions: Multiversion schemes outperform single-version locking when most transactions are read-only.Read-only multiversion transactions use consistent snapshots without locking or validation, whereas single-version locking uses short read locks for cursor stability.
  • Impact of Short Read Transactions: Under high contention with 80% read-only transactions, MVCC achieves 63% and 73% higher throughput than single-version locking.
  • Impact of Long Read Transactions: With one long read-only transaction, single-version update throughput drops 75%, while multiversion throughput drops only 5%.At equal conditions, multiversion becomes twice as fast as single-version locking.
  • TATP Results: The TATP benchmark sustains several million committed transactions per second on a low-end server, an order of magnitude above previously published results.The benchmark uses seven short transaction types across four tables and includes mostly query transactions.

6. RELATED WORK

Related work covers the history of concurrency control, multiversion methods, optimistic validation, snapshot isolation, and commercial main-memory systems. It positions this paper's main-memory MVCC methods against prior approaches and implementations.

  • Prior multiversion work includes timestamp ordering, two-version two-phase locking, mixed methods, and numerous other MVCC schemes.
  • Optimistic concurrency control originated in single-version databases, while only a small number of prior MVCC schemes used optimistic validation.
  • Snapshot isolation is widely used to isolate read-only transactions but is not serializable without additional techniques.Prior serializable approaches check read-write dependencies or validate repeatability of reads and predicates.
  • Oracle TimesTen and IBM solidDB provide commercial main-memory systems using single-version locking with multiple lock types or granularities.

7. CONCLUDING REMARKS

The paper designs and evaluates optimistic and pessimistic MVCC methods alongside main-memory single-version locking. The experiments find that single-version locking is conditionally effective, whereas MVCC is more resilient to demanding workloads.

  • The study implements optimistic MVCC with validation, pessimistic MVCC with locking, and a main-memory-optimized single-version locking variant.
  • Single-version locking avoids lock-acquisition bottlenecks and performs well when transactions are short and contention is low.
  • Multiversion schemes incur higher overhead but retain good throughput under hotspots and long read-only transactions.
  • The optimistic MVCC scheme consistently achieves higher throughput than the pessimistic scheme.
Loading 1201.0228v1…