19.5.1 Locking Protocols in Distributed Databases

Context: Adapts centralized locking schemes (Chapter 15) for use in a distributed environment. The primary goal is still to ensure serializability of transactions. The key difference is handling data that might be replicated across multiple sites.
Assumption: Each site participates in a commit protocol (like 2PC) to guarantee global atomicity.
Basic Lock Modes: We assume the existence of shared (read) and exclusive (write) locks, as in centralized systems.

Key Challenge: Lock Management

The main issue is how and where to manage locks, especially when data is replicated. Different approaches have different trade-offs in terms of:

Availability: if sites/replicas containing the data item are not accessible.

Mechanism:
- A single designated site ( $S_{i}$ ) acts as the lock manager for all data items (regardless of where the data resides).
- All lock and unlock requests are sent to $S_{i}$ .
- If a lock can be granted, $S_{i}$ sends a grant message to the requesting site.
- If a lock cannot be granted (conflict), the request is queued.
- Reads can access any replica.
- Writes must update all replicas.
Advantages:
- Simple implementation.
- Easy deadlock handling (all lock information is at one site, so centralized deadlock detection algorithms can be used).
Disadvantages:
- $S_{i}$ becomes a bottleneck. All requests go through it.
- Vulnerable: If $S_{i}$ fails, the entire locking mechanism is lost (unless a backup/recovery scheme is used).

Mechanism:
- The lock manager functionality is distributed across multiple sites.
- Each site manages locks for data items stored at that site.
- For non-replicated data at site $S_{i}$ , lock requests are sent to $S_{i}$ ‘s lock manager.
- Handling of replicated data is determined by the specific protocol such as Primary copy, Majority Protocol, Biased Protocol, and Quorum Consensus Protocol.
Advantages:
- Reduces the bottleneck problem compared to the single lock-manager approach.
- Lower overhead than centralized approach (for non-replicated data).
Disadvantages:
- Deadlock handling is more complex. Deadlocks can span multiple sites, requiring distributed deadlock detection algorithms.

Mechanism:
- For each data item Q, one replica is designated as the primary copy.
- All lock requests for Q are sent to the primary site of Q.
- This effectively reduces replicated data locking to non-replicated data locking (from the lock manager’s perspective).
Advantages:
- Simple implementation (similar to non-replicated data).
- Concurrency control similar to that of unreplicated data.
Disadvantages:
- Vulnerability: If the primary site of Q fails, Q becomes inaccessible, even if other replicas exist.

Mechanism:
- If data item Q is replicated at n sites, a lock request must be sent to more than half of the n sites (i.e., a majority).
- Each lock manager independently decides whether to grant the lock (based on local lock information).
- A transaction can proceed only after obtaining a lock on a majority of the replicas.
- Writes are performed on all replicas.
Advantages:
- Decentralized: Avoids the single point of failure of the primary copy approach.
- Can tolerate some site failures (as long as a majority of replicas are accessible).
Disadvantages:
- Higher overhead: Requires more messages than primary copy (at least $2 (\frac{n}{2} + 1)$ for lock requests, $(\frac{n}{2} + 1)$ for unlock requests).
- Complex deadlock handling:
  - Distributed deadlock detection is needed.
  - Deadlocks can occur even when locking a single data item (example provided in the PDF). This can be avoided by having all sites request locks on replicas in the same predetermined order.

Mechanism:
- Treats shared (read) and exclusive (write) locks differently:
  - Shared Locks: A transaction needs to lock only one replica of Q.
  - Exclusive Locks: A transaction needs to lock all replicas of Q.
Advantages:
- Lower overhead for read operations (compared to majority protocol), which are often more frequent.
Disadvantages:
- Higher overhead for write operations.
- Complex deadlock handling (like majority protocol).

Mechanism:
- A generalization of the majority protocol.
- Each site is assigned a non-negative weight.
- For data item x, let S be the sum of weights of all sites where x is replicated.
- Two integers are defined:
  - Read quorum ( $Q_{r}$ )
  - Write quorum ( $Q_{w}$ )
- Constraints that need to be satisfied:
  - $Q_{r} + Q_{w} > S$
  - $2 * Q_{w} > S$
- To read, a transaction must lock enough replicas so that the sum of their weights is $\geq Q_{r}$ .
- To write, a transaction must lock enough replicas so that the sum of their weights is $\geq Q_{w}$ .
- Writes are performed on all locked replicas.
Advantages:
- Flexibility: Can simulate majority and biased protocols by appropriate choice of weights and quorums.
- Can tune performance for read/write ratios.
- Can tolerate some site failures.
Disadvantages:
- Complexity in choosing optimal weights.
- Complex deadlock handling (like majority protocol).

Protocol	Read Lock Requirement	Write Lock Requirement	Advantages	Disadvantages
Single Lock Manager	Any one replica	All replicas	Simple, easy deadlock handling.	Bottleneck at lock manager, vulnerable to lock-manager failure.
Distributed Lock Manager	Depends on protocol.	Depends on protocol.	Reduced Bottleneck.	More complex deadlock handling.
Primary Copy	Primary copy	Primary copy	Simple, like non-replicated data.	Vulnerable to primary site failure.
Majority Protocol	Majority of replicas	Majority of replicas	Decentralized, fault-tolerant.	Higher overhead, complex deadlock handling (even for single item).
Biased Protocol	Any one replica	All replicas	Low read overhead.	High write overhead, complex deadlock handling.
Quorum Consensus	Enough replicas to meet read quorum ( $Q_{r}$ )	Enough replicas to meet write quorum ( $Q_{w}$ )	Flexible, can simulate other protocols, fault-tolerant.	Complex parameter tuning, complex deadlock handling, requires careful weight assignment.