Concurrency Control Techniques

Why This Matters

Concurrency control sits at the heart of every system that handles multiple simultaneous operations—from databases serving thousands of queries to distributed applications coordinating across servers. You're being tested on your ability to understand why different techniques exist, when each approach makes sense, and what trade-offs developers face when choosing between them. The core tension you'll encounter repeatedly is the balance between consistency (ensuring correct results) and performance (maximizing throughput).

These techniques demonstrate fundamental principles in systems programming: serializability guarantees, deadlock management, isolation trade-offs, and optimistic vs. pessimistic strategies. Don't just memorize the names—know what problem each technique solves and when you'd choose one over another. If an exam question describes a scenario with high read traffic and rare conflicts, you should immediately recognize which approaches shine there.

---

Pessimistic Approaches: Lock Before You Leap

These techniques assume conflicts are likely and prevent them upfront by restricting access. The philosophy: it's better to wait than to redo work.

Two-Phase Locking (2PL)

• Guarantees serializability through a strict protocol—transactions must acquire all locks before releasing any
• Two distinct phases define the approach: the growing phase (acquiring locks) followed by the shrinking phase (releasing locks)
• Deadlock vulnerability is the primary drawback; transactions can wait indefinitely in circular dependencies

Read-Write Locks

• Differentiates access types to maximize concurrency—multiple readers can proceed simultaneously, but writers get exclusive access
• Shared locks for reads, exclusive locks for writes is the fundamental mechanism that enables this optimization
• Writer starvation can occur when continuous read traffic prevents writers from ever acquiring the lock

Lock Granularity

• Determines the scope of locking from fine-grained (row-level) to coarse-grained (table-level or database-level)
• Fine-grained locking increases concurrency but adds significant overhead from managing many locks
• Coarse-grained locking reduces overhead but creates bottlenecks when transactions compete for the same large resource

---

Optimistic Approaches: Ask Forgiveness, Not Permission

These techniques assume conflicts are rare and let transactions proceed freely, checking for problems only at commit time. The philosophy: validate at the end rather than block throughout.

Optimistic Concurrency Control (OCC)

• Three-phase execution structures the approach: read phase (execute freely), validate phase (check for conflicts), write phase (commit if valid)
• No locks during execution means transactions never block each other while working
• High abort rates under contention make this unsuitable for write-heavy or conflict-prone workloads

Multiversion Concurrency Control (MVCC)

• Maintains multiple data versions so readers see a consistent snapshot without blocking writers
• Readers never block writers and vice versa—each operates on the appropriate version of the data
• Ideal for read-heavy workloads where the overhead of version management pays off in reduced contention

---

Ordering-Based Approaches: Time as the Arbiter

These techniques use timestamps or transaction order to determine which operations should win conflicts. The philosophy: establish a total ordering and enforce it.

Timestamp Ordering

• Assigns unique timestamps at transaction start to establish a global ordering for conflict resolution
• Older transactions take precedence—if a younger transaction has already modified data, the older one must abort
• No deadlocks possible since transactions never wait; they simply abort and retry if they arrive "too late"

Conflict Serializability

• Defines correctness for concurrent schedules—a schedule is valid if it produces the same result as some serial execution
• Non-conflicting operations can be reordered freely; only read-write, write-read, and write-write pairs on the same item conflict
• Foundation for all concurrency control since every technique ultimately aims to produce conflict-serializable schedules

Serialization Graph Testing

• Constructs a directed graph where nodes are transactions and edges represent conflicts between them
• Acyclic graph confirms serializability—you can topologically sort it to find an equivalent serial order
• Cycle detection reveals problems—if the graph has cycles, the schedule cannot be serialized

---

Handling Failures: When Things Go Wrong

These techniques address what happens when concurrency control mechanisms create problems like deadlocks or when we need to tune the strictness of isolation.

Deadlock Prevention and Detection

• Prevention strategies include resource ordering (always acquire locks in the same sequence) and wait-die/wound-wait schemes
• Detection uses wait-for graphs where nodes are transactions and edges show who's waiting for whom—cycles indicate deadlock
• Resolution requires victim selection—abort one or more transactions to break the cycle, typically choosing the "cheapest" to restart

Isolation Levels

• Four standard levels define the trade-off spectrum: Read Uncommitted, Read Committed, Repeatable Read, and Serializable
• Lower levels permit anomalies like dirty reads, non-repeatable reads, or phantom reads in exchange for better performance
• Serializable is the gold standard for correctness but imposes the highest performance cost

---

Quick Reference Table

---

Self-Check Questions

1. Which two techniques guarantee serializability but differ in how they handle conflicts—one by waiting, one by aborting?

2. A system experiences high read traffic with occasional writes. Which concurrency control technique would minimize blocking, and why?

3. Compare and contrast Optimistic Concurrency Control and Two-Phase Locking: what assumptions does each make about conflict frequency, and how does this affect their performance characteristics?

4. If you construct a serialization graph and find a cycle, what does this tell you about the schedule? What are your options for resolving the problem?

5. An FRQ describes a system using Read Committed isolation that's experiencing non-repeatable reads. Explain why this anomaly occurs and what isolation level change would prevent it—along with the trade-off involved.