Compare and swap in Redis

Compare and swap

Compare and swap is a familiar concept of atomic operation, for dealing with race condition. Suppose we want to build a lock for multiple instances to execute some command, and only one can be executed at a given time. An instance must wait for the lock to be released before it can take.

Instance 1: Current value is empty, set it to 1 and take the lock.
Instance 2: Current value is not empty, wait.
Instance 1: Done, set it to empty and release the lock.
Instance 2: Current value is empty, set it to 2 and take the lock.

In Go, this can be implemented by sync/atomic package:

ok := CompareAndSwapInt64(addr, old, new)

// which is equivalent of the following code snippet, but atomic:
func CompareAndSwapInt64() {
    if *addr == old {
        *addr = new
        return true
    }
    return false
}

And for locking between multiple instances, we’ll need to use Redis. We can try doing that in a similar way. But keep in mind that this code snippet is not atomic:

val := exec("GET mykey")
if val == "" {
    exec("SET mykey 1")
    // execute some command
}

When multiple instances execute the commands at the same time, they can both successfully acquire the lock! And we have race condition:

Instance 1: val := exec("GET mykey")             // empty
Instance 2: val := exec("GET mykey")             // empty
Instance 1: if val == "" { exec("SET mykey 1") }
Instance 2: if val == "" { exec("SET mykey 2") } // race condition!

To implement an optimistic locking in Redis, we need to use WATCH, MULTI and EXEC for a transaction:

exec("WATCH mykey")
val := exec("GET mykey")
exec("MULTI")
if val == "" {
    exec("SET mykey 1")
}
ok := exec("EXEC")
if ok {
    // acquired the lock successfully, now execute some command
}

That is, when multiple clients try to set the key at the same between the execution of WATCH and EXEC, the transaction will be failed. And these clients can try acquiring the lock again.

There is a better way!

From Redis 7.0, there is support for compare and swap within a single command:

SET mykey 1 NX GET

The SET command can include GET to return the old value stored at mykey. And NX is there for setting the key only if it is empty.

That’s it! No need for a transaction with WATCH. Just a single command and we can have lock between multiple instances 🥳

Back Back