Lock; distributed CC; deadlock situation

Lock

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.

Concurrency control in distributed transactions

In a distributed transaction the objects are on different servers, and each server applies its own concurrency control. All servers must agree on the serialization order, otherwise the transactions could be serial at each server but not globally.

• Locking: each server locks its own objects. Strict 2PL is used, with locks held until the commit protocol completes. A transaction's locks are held at several servers, so distributed deadlock is possible, and the servers must detect or avoid it.
• Timestamp ordering: transactions are given globally unique timestamps (a pair of the local clock value and the server id; the servers' clocks are kept roughly synchronized). Each server enforces timestamp rules; if the servers order conflicting transactions the same way, the result is globally serializable. A conflict causes an abort at any server, which aborts the whole transaction.
• Optimistic: each server validates the part of the transaction it holds, during the first phase of commit. Validation must produce a consistent order across servers, so a global or ordered validation is needed.

Situation leading to distributed deadlock

A deadlock is a state in which each transaction in a set is waiting for a lock held by another transaction in the set, so none can proceed. It is shown by a cycle in the wait-for graph (nodes are transactions, an edge T → U means T waits for U).

A distributed deadlock occurs when the wait-for cycle spans several servers. Each server sees only a part of the graph (a local wait-for graph without a local cycle), but the global graph has a cycle.

Example: T holds a lock on A at server X, and U holds a lock on B at server Y. T now requests B at Y (so T waits for U), and U requests A at X (so U waits for T).

Server X: U -> T  (U waits for T on A)
Server Y: T -> U  (T waits for U on B)
Global:   T -> U -> T   (cycle = deadlock)