Memcached - CAS

Memcached - Preventing Race Conditions with CAS

CAS (Check-And-Set) is a critical command for managing concurrency. It allows you to set a new value for a key only if it has not been modified by another client since you last fetched it. This mechanism, also known as ‘optimistic locking’, is essential for preventing data corruption from race conditions.

The Concept

Imagine two processes trying to update a counter: 1) Both read the current value ‘5’. 2) Both increment it to ‘6’. 3) Both write ‘6’ back. The final value is ‘6’, not ‘7’. CAS solves this. The workflow is: 1) Fetch the value AND a unique ‘CAS token’ using gets. 2) Perform your modifications. 3) Use cas to write the new value, providing the token. The write only succeeds if the token on the server still matches the one you provided.

Protocol Syntax

# First, fetch the value and token
gets key

# Then, attempt to update it
cas key flags exptime bytes unique_cas_token [noreply]
value

The unique_cas_token is a 64-bit integer that uniquely identifies the version of the item. You must obtain this token from a preceding gets command.

Expected Responses

The cas command can result in:

• STORED indicates the new value was stored because the CAS token matched.
• EXISTS indicates that the item was modified by another client since you fetched it (your CAS token was stale).
• NOT_FOUND indicates that the key no longer exists.
• ERROR indicates a syntax error.

Telnet Example: Preventing a Race Condition

# 1. Set an initial value for our key 'page_views'
set page_views 0 900 1
0
STORED

# 2. Use 'gets' to retrieve the value AND its unique CAS token.
gets page_views
VALUE page_views 0 1 1  <-- The '1' at the end is the CAS token.
0
END

# 3. Try to update using an INCORRECT CAS token (e.g., '99').
# This simulates another client having updated the key already.
cas page_views 0 900 1 99
1
EXISTS  <-- 'EXISTS' means the key exists, but the CAS token was wrong.

# 4. Now, use the CORRECT CAS token ('1') we got from 'gets'.
cas page_views 0 900 1 1
1
STORED  <-- Success! The value is updated.

# 5. Let's verify the new value and get the NEW CAS token.
gets page_views
VALUE page_views 0 1 2  <-- Note the CAS token is now '2'.
1
END

# 6. If we try the 'cas' again with the old token ('1'), it will fail.
cas page_views 0 900 1 1
2
EXISTS

Modern Application: Implementing a Concurrent Counter in Python

Let’s implement a safe concurrent counter using Python and pymemcache, which has built-in support for gets and cas operations.

Python Code Example

import time
from pymemcache.client.base import Client

MEMCACHED_SERVER = ('127.0.0.1', 11211)

def safe_increment(client, key, max_retries=5):
    """Safely increments a counter using a CAS retry loop."""
    for i in range(max_retries):
        # 1. Fetch the value and CAS token
        result = client.gets(key)
        if result is None:
            # Key doesn't exist, we can't increment. Maybe initialize it?
            print(f"Attempt {i+1}: Key '{key}' not found. Initializing with 1.")
            # 'add' is an atomic way to set if not exists.
            if client.add(key, '1', expire=300):
                return 1 # Successfully initialized
            else:
                # Race condition: someone else created it. Retry the loop.
                time.sleep(0.01)
                continue

        current_value, cas_token = result
        new_value = str(int(current_value) + 1)

        # 2. Attempt to set the new value with the CAS token
        # The cas method returns True on success, False on token mismatch.
        if client.cas(key, new_value, cas_token, expire=300):
            print(f"Attempt {i+1}: Successfully incremented '{key}' to {new_value}.")
            return int(new_value)
        else:
            # CAS failed, another client modified the key. Retry.
            print(f"Attempt {i+1}: CAS failed for key '{key}'. Retrying...")
            time.sleep(0.01) # Add a small delay to prevent tight-loop spinning

    raise Exception(f"Failed to increment key '{key}' after {max_retries} retries.")

def run_cas_example():
    client = Client(MEMCACHED_SERVER)
    key = 'concurrent_likes'
    print(f"--- Running CAS demo for key: {key} ---")
    client.delete(key) # Start with a clean slate

    # Simulate multiple concurrent increments
    final_value = 0
    for _ in range(5):
        final_value = safe_increment(client, key)

    print(f"\nFinal counter value is: {final_value}")
    print(f"Value in Memcached: {client.get(key).decode()}")
    client.close()

if __name__ == "__main__":
    run_cas_example()

Expected Output

--- Running CAS demo for key: concurrent_likes ---
Attempt 1: Key 'concurrent_likes' not found. Initializing with 1.
Attempt 1: Successfully incremented 'concurrent_likes' to 2.
Attempt 1: Successfully incremented 'concurrent_likes' to 3.
Attempt 1: Successfully incremented 'concurrent_likes' to 4.
Attempt 1: Successfully incremented 'concurrent_likes' to 5.

Final counter value is: 5
Value in Memcached: 5

Best Practices and Real-World Applications

• Implement Retry Logic: A CAS failure is an expected outcome in a concurrent system. Your application code MUST handle this by retrying the entire gets -> modify -> cas sequence.
• Real-World Scenario: A social media ‘like’ button is a classic example. To avoid lost ‘likes’ from race conditions, you would use this pattern to increment the like counter for a post.
• Configuration Toggles: Updating a feature flag or a configuration value stored in the cache should be done via CAS to ensure that two administrators don’t overwrite each other’s changes.
• Thundering Herd Problem: CAS can also be used to mitigate the ‘thundering herd’ problem. When a popular cache item expires, many processes might try to regenerate it at once. Using add or CAS, only one process can ‘win’ the right to regenerate the data, while others wait.