Concurrency Control and Optimistic Locking Mechanisms in Distributed Systems

Concurrency Control and Optimistic Locking Mechanisms in Distributed Systems

Problem Description: In distributed systems, multiple clients or service nodes may access and modify the same data simultaneously. How to ensure the correctness and consistency of data operations in such a high-concurrency environment, avoiding issues like data races and lost updates, is the core problem addressed by concurrency control. Optimistic locking is a common concurrency control mechanism. It assumes that the probability of conflicts between multiple operations is low, thus allowing parallel execution of operations without locking, and only checking for conflicts when committing updates. We will explore the principles, implementation methods, and applications of optimistic locking in distributed systems in detail.

1. Problem Introduction: Lost Update Scenario

Imagine a distributed e-commerce scenario where product inventory is 10. User A and User B place orders for this product simultaneously:

  • User A reads the inventory as 10 and calculates new inventory = 10 - 1 = 9
  • User B also reads the inventory as 10 and calculates new inventory = 10 - 1 = 9
  • User A and B submit their updates almost simultaneously, resulting in the final inventory being set to 9 instead of the correct 8.

This is a typical "lost update" problem. Traditional pessimistic locking (e.g., database row locks) avoids this issue by serializing access. However, in distributed environments, pessimistic locking can lead to performance bottlenecks and deadlock risks.

2. Basic Idea of Optimistic Locking

Optimistic locking adopts a "execute first, check later" strategy:

  • Phase 1: Read - The client reads the data and records its current version number (or timestamp, hash value, etc.).
  • Phase 2: Modify - The client modifies the data locally.
  • Phase 3: Verify and Write - When submitting the update, the client checks if the current version of the data matches the version read earlier. If they match, the new value is written and the version number is updated; otherwise, a conflict is detected, and the operation fails.

3. Key Implementation Mechanisms of Optimistic Locking

3.1 Version Number Control

  • Each data item carries a version number (e.g., integer, timestamp).
  • When reading data, the current version number is also retrieved.
  • When updating data, specify in the SQL or update condition: "WHERE id = ? AND version = ?".
  • If the number of affected rows is 0, it indicates the version number has changed, implying a conflict.

Example SQL:

-- Read phase
SELECT stock, version FROM products WHERE id = 1; -- Suppose stock=10, version=5 is obtained

-- Update phase (User A)
UPDATE products SET stock = 9, version = 6 WHERE id = 1 AND version = 5;
-- If successful, version becomes 6

-- User B attempts to update using the same version=5, but version is now 6, so the update fails

3.2 Conditional Update (Compare-and-Set, CAS)

  • Distributed key-value stores (e.g., Etcd, Redis) often provide atomic CAS operations.
  • The client carries the expected old value, and the server atomically compares and sets the new value.

Example Redis commands:

> GET stock:1
"10"
> GET version:1
"5"

-- User A executes CAS, expecting to set the new value when version is 5
> CAS stock:1 10 9 IF version:1 = 5
SUCCESS  -- Successful, version is updated

-- User B's CAS fails due to version mismatch
> CAS stock:1 10 9 IF version:1 = 5
FAIL

4. Conflict Resolution Strategies

When optimistic locking detects a conflict, common handling methods include:

  • Retry Mechanism: Automatically retry the entire operation (re-read, recalculate, re-write), suitable for scenarios with low conflict probability.
  • Abort Operation: Directly return an error, letting the client decide the next step (e.g., prompt the user to resubmit).
  • Custom Merge: Handle conflicts at the business logic layer, such as through Operational Transformation (OT) or conflict resolution algorithms (e.g., Last Writer Wins - LWW, which may lose data).

5. Challenges and Optimizations in Distributed Systems

5.1 Version Number Generation

  • In distributed environments, version numbers must be globally unique and ordered. Logical clocks (e.g., vector clocks), distributed sequence generators, or time services (e.g., TrueTime) can be used for generation.

5.2 Performance Considerations

  • Optimistic locking performs excellently in low-conflict scenarios, avoiding lock overhead.
  • However, in high-conflict scenarios (e.g., flash sales), numerous retries may consume resources. Mechanisms like token buckets or queues can be combined for rate limiting.

5.3 Integration with Transactions

  • In distributed databases, optimistic locking is often combined with Multi-Version Concurrency Control (MVCC). For example, Spanner uses TrueTime to generate version numbers, implementing optimistic transactions across nodes.

6. Practical Application Cases

  • Distributed Databases: Google Spanner and CockroachDB use MVCC and optimistic concurrency control.
  • Version Control Systems: Git's merge operations are essentially optimistic locking, prompting manual resolution upon conflict detection.
  • Caching Systems: Redis implements optimistic locking via WATCH/MULTI/EXEC, monitoring key changes.

Summary: Optimistic locking detects conflicts at commit time through version numbers or CAS operations, making it suitable for distributed scenarios with more reads than writes and low conflict probability. Its core advantage lies in the high concurrency of lock-free reads, but it requires designing reasonable conflict handling strategies. In practical systems, it is often combined with retry mechanisms and rate-limiting strategies to balance performance and consistency.