Concurrency control goals and mechanisms

Concurrency control and its need

Concurrency control is the activity of coordinating concurrent transactions that access shared data so that their combined effect is correct, as if they ran one at a time (serial equivalence), while allowing as much parallelism as possible.

Need: without it, interleaved transactions cause

• Lost update: one transaction overwrites another's update.
• Inconsistent retrieval: a transaction reads some values before and others after another transaction's update.
• Dirty read and cascading abort: reading uncommitted data of a transaction that later aborts.
• Premature writes: wrong restoring of old values after aborts.

Goals

• Isolation of transactions (serializability).
• Preserve consistency of the data (ACID).
• Maximize concurrency and throughput, and reduce response time.
• Prevent or resolve deadlock and starvation.
• Make aborts safe: avoid cascading aborts (recoverability).

Mechanisms

1. Locking (pessimistic): a transaction locks data before access and holds it (strict 2PL) until commit. Conflicts cause waiting; deadlock is possible.
2. Timestamp ordering: each transaction gets a timestamp; conflicting operations must be executed in timestamp order; late operations abort the transaction. No deadlock.
3. Optimistic concurrency control: work on private copies, validate at commit time, and abort if there was a conflict.

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.

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.