Concurrency control methods compared

Concurrency control

Concurrency control coordinates concurrent transactions on shared data so that the result is equivalent to a serial execution (serial equivalence), avoiding lost updates, inconsistent retrievals and cascading aborts.

Methods

A lock is a variable associated with a data item that controls concurrent access. A transaction must obtain the lock before it reads or writes the item, and releases it when finished. Common modes are read (shared) lock and write (exclusive) lock; several transactions can hold read locks together, but a write lock excludes all others. In two-phase locking (2PL) a transaction has a growing phase (acquires locks) followed by a shrinking phase (releases locks, never acquires again). Strict 2PL holds all locks until commit or abort, which prevents dirty reads and cascading aborts.

Timestamp ordering gives each transaction a unique timestamp when it starts (a Lamport clock or a global timestamp from server id and local clock in a distributed system). Conflicting operations are executed in timestamp order, so the result is equivalent to running transactions serially in timestamp order. No locks are used, so no deadlock.

Each object keeps a write timestamp (of the last committed write) and read timestamps (of transactions that read it). For a transaction T with timestamp Tc:

• Write rule: T's write is allowed only if Tc ≥ the maximum read timestamp of the object and Tc > the write timestamp of the committed version. Otherwise T is aborted (it would invalidate a later read).
• Read rule: T's read is allowed if Tc > the write timestamp of the committed version; if a tentative version from an earlier transaction exists, T waits until it commits or aborts. If Tc is smaller than the write timestamp, T is too late and is aborted.

An aborted transaction restarts with a new, later timestamp. Timestamp ordering is deadlock-free, but it causes restarts; keeping multiple versions of objects reduces the number of aborts.

Optimistic concurrency control (Kung and Robinson) assumes conflicts are rare, so transactions proceed without locks and are checked for conflicts only when they want to commit. A transaction goes through three phases.

1. Working phase: it reads and writes tentative copies of objects (private versions). Reads see the last committed values; no locks are taken. The system records the read set and write set.
2. Validation phase: when the client requests commit, the server checks for conflicts with other transactions that overlapped in time. If validation fails, the transaction is aborted (or conflict resolution is used).
3. Update phase: if validation succeeds, tentative versions are made permanent (written to permanent storage) and the transaction commits.

Validation (backward validation): transaction Tv is checked against earlier overlapping transactions Ti that committed before Tv started validation. Rules:

• If Ti writes an object that Tv reads (Ti's write set ∩ Tv's read set ≠ ∅), validation fails, because Tv read stale data.
• Otherwise Tv passes validation. (Writes are applied in commit order, so write-write conflicts cannot occur.)

Forward validation checks Tv's write set against the read sets of still-active transactions; it allows a choice of aborting Tv or the others.

In a distributed system, each server validates its own part of the transaction during the first phase of two-phase commit, and all servers must validate in the same global order to avoid commitment deadlock and inconsistent serial orders.

Advantages

• No locking, so no deadlock and no lock overhead.
• High concurrency when conflicts are rare; with forward validation, read-only transactions always pass validation.
• Abort is cheap because nothing was written permanently.

Disadvantages

• Under heavy conflicts many transactions abort and restart; starvation is possible.
• Wasted work for aborted transactions.

Comparison