Lock Contention: The Compare-and-Swap Approach

Concurrency-related latency is one of the most fascinating and challenging topics in system architecture, especially when dealing with lock contention.

When multiple threads or processes contend for shared resources, performance can degrade significantly, leading to bottlenecks. In this article, we’ll focus on the compare-and-swap (CAS) approach, a mechanism that sidesteps traditional locks by leveraging optimistic locking.

From personal experience working on high-throughput systems, compare-and-swap has been a game-changer in reducing contention and improving performance. Let’s dig into how this works, its advantages, and how to implement it in both code and databases.

What is Compare-and-Swap

Compare-and-swap (CAS) is a low-level synchronization primitive that helps ensure atomicity in concurrent systems. Unlike traditional locking mechanisms, CAS doesn’t block other threads. Instead, it operates optimistically, assuming there won’t be conflicts.

At its core, CAS works as follows:

1. Read the current value of a resource (e.g., a variable or a database record).

2. Compare the current value against an expected value (the value you initially read).

3. If the values match, swap (or update) the value to a new one atomically. If they don’t match, the operation fails, and you can retry with the new value.

This mechanism is supported at the hardware level by modern CPUs, typically exposed to developers through language libraries or frameworks. It’s particularly useful in implementing optimistic locking.

Compare-and-Swap In Practice

To better understand CAS, let’s break it down into two practical examples:

1. Using CAS in Java and C# for maintaining atomic counters.

2. CAS in databases, particularly in NoSQL systems, where optimistic locking ensures data consistency without traditional transactions.

Examples:

In programming, CAS is commonly used for atomic operations, such as incrementing counters or managing shared state. Most modern languages provide built-in support for CAS via atomic classes.

In Java, the `AtomicInteger` class from the `java.util.concurrent.atomic` package uses CAS under the hood:

import java.util.concurrent.atomic.AtomicInteger;

public class CASExample {
    public static void main(String[] args) {
        // Initialize an atomic integer with a value of 10
        AtomicInteger atomicCounter = new AtomicInteger(10);

        // Thread 1: Attempts to update the value from 10 to 20
        boolean success = atomicCounter.compareAndSet(10, 20);

        if (success) {
            System.out.println("Thread 1: Successfully updated the value to " + atomicCounter.get());
        } else {
            System.out.println("Thread 1: Update failed. Current value: " + atomicCounter.get());
        }

        // Thread 2: Concurrently tries to update the value from 10 to 30
        boolean thread2Success = atomicCounter.compareAndSet(10, 30);

        if (thread2Success) {
            System.out.println("Thread 2: Successfully updated the value to " + atomicCounter.get());
        } else {
            System.out.println("Thread 2: Update failed. Current value: " + atomicCounter.get());
        }
    }
}

Output (depending on timing):

Thread 1: Successfully updated the value to 20
Thread 2: Update failed. Current value: 20

Here’s what happens:

1. Thread 1 reads the value as `10` and successfully updates it to `20` using `compareAndSet`.
2. Thread 2 also reads `10`, but since Thread 1 has already updated it to `20`, its CAS operation fails.

In C#, the `Interlocked` class provides atomic operations that are similar to CAS:

using System;
using System.Threading;

class CASExample {
    static void Main(string[] args) {
        int atomicCounter = 10;

        // Thread 1: Attempts to update the value from 10 to 20
        bool success = Interlocked.CompareExchange(ref atomicCounter, 20, 10) == 10;

        if (success) {
            Console.WriteLine("Thread 1: Successfully updated the value to " + atomicCounter);
        } else {
            Console.WriteLine("Thread 1: Update failed. Current value: " + atomicCounter);
        }

        // Thread 2: Concurrently tries to update the value from 10 to 30
        bool thread2Success = Interlocked.CompareExchange(ref atomicCounter, 30, 10) == 10;

        if (thread2Success) {
            Console.WriteLine("Thread 2: Successfully updated the value to " + atomicCounter);
        } else {
            Console.WriteLine("Thread 2: Update failed. Current value: " + atomicCounter);
        }
    }
}

Compare-and-Swap in Databases: While CAS is often associated with in-memory operations, its principles apply to databases as well, especially in **NoSQL databases** like Cassandra, DynamoDB, and MongoDB. These databases often lack traditional transactions, so CAS-based optimistic locking is used to maintain consistency.

Let’s assume a table called `Inventory` with the following columns:

| ProductID | Quantity |  
|-----------|----------|  
| 1         | 100      |  

In SQL, CAS-like behavior can be achieved using an `UPDATE` query with a conditional `WHERE` clause:

-- Thread 1: Updates the quantity if the current value matches 100
UPDATE Inventory
SET Quantity = 90
WHERE ProductID = 1 AND Quantity = 100;

-- Check if the update was successful
SELECT @@ROWCOUNT; -- Returns 1 if successful, 0 otherwise

Here’s what happens:

1. The query checks if the current `Quantity` is `100`.
2. If true, it updates the value to `90`.
3. If another thread has already updated the value (e.g., to `95`), the `WHERE` clause condition fails, and the update doesn’t happen.

Compare-and-Swap Key Advantages

1. Non-Blocking: Unlike traditional locks, CAS doesn’t block threads. Conflicts are resolved by retrying rather than waiting.

2. High Performance: Since it’s implemented at the hardware level, CAS is extremely fast.

3. Short-Lived Locks: CAS operations only lock the resource for the duration of the comparison, reducing contention.

4. Scalability: CAS is particularly useful in high-contention scenarios, such as incrementing counters or managing shared state in distributed systems.

When to Use Compare-and-Swap

CAS is ideal for:

• High-Throughput Systems: Systems with frequent updates to shared resources, where traditional locks would cause bottlenecks.
• Distributed Systems: Optimistic locking via CAS is widely used in NoSQL databases to avoid the overhead of distributed transactions.
• Shared Counters: For example, incrementing view counts, managing inventory, or tracking resource usage.

Drawbacks of Compare-and-Swap

While CAS is fast and efficient, it’s not without its challenges:

• Busy Waiting: In high-contention scenarios, repeated retries can lead to CPU spikes.
• Complexity: Implementing CAS-based logic can be tricky, especially when dealing with multiple variables.

Conclusion

The compare-and-swap (CAS) approach is a powerful tool for handling concurrency and reducing lock contention. By avoiding exclusive locks and leveraging optimistic locking, CAS enables high performance and scalability in both in-memory operations and databases.

Whether you’re working on shared counters in C# or managing inventory in a NoSQL database, CAS is a must-have in your concurrency toolbox. While it has its quirks, its efficiency and speed make it an invaluable mechanism for modern system architectures.