An exploration on locking and atomicity in Redis
Lately I've been doing some development of a turn based browser game using node.js and Redis. Being intended to run on multiple node.js instances and each instance also being able to "autoplay" for afk users, it was clearly lacking a semaphore of some sort to make sure only one action at the time would be processed per game across all nodes. With Redis being my central persistence component I figured this was a good time to dive a bit deeper in the capabilities of Redis when it comes to locking. As it turns out locking makes a great use-case to learn about the true power of some of the most basic Redis commands. So while this blog post is definitely about locking with Redis, its actually more about how common Redis commands can be used to solve some pretty complex issues. Generally locking patterns can be divided into pessimistic and optimistic. In this blog I'm focusing on the creation of a general purpose (pessimistic) lock/semaphore that could be used for anything that requires limiting access to a resource or piece of code really. The third example also uses the build-in optimistic locking capabilities of Redis to solve to a race condition issue. Keep in mind though, that in either case it is the client that is responsible for maintaining the relation between "the lock" and "the resource". Lets start with the oldest and most common locking pattern and work our way through from there. 1. SETNX/GETSET based locking The commands of choice for the first example (works on all Redis versions): SETNX only sets a key to a value if it does Not eXists yet. GETSET gets an old value and sets it to a new value atomically!
var redis = require('redis');
var nameOfKeyToLock = 'the_lock';
var timeout = 10000;
var retry_time = 500;
var doLocked = function(client, nameOfKeyToLock, callback){
var lock = function() {
var newLockValue = Date.now() + timeout;
//SETNX command
client.setnx(nameOfKeyToLock, newLockValue, function(err, result){
if(result === 0){
client.get(nameOfKeyToLock, function(err, currentValue){
currentValue = parseFloat(currentValue);
if(currentValue > Date.now()){
//lock still valid, retry later
return retry();
}
newLockValue = Date.now() + timeout;
//GETSET command
client.getset(nameOfKeyToLock, newLockValue, function(err, check){
if(currentValue == check){
//old value was still the same, so now the lock is ours
return callback(unlock);
}
retry();
});
});
} else {
//no lock was present, we now got it
callback(unlock);
}
});
var unlock = function(after){
if(newLockValue > Date.now()){
client.del(nameOfKeyToLock, function(){
console.log('released lock');
after();
});
} else {
after();
}
};
};
var retry = function() {
console.log('scheduling retry');
setTimeout(lock, retry_time);
}
lock();
};
Quite a bit of code, but the key part involves only the two commands listed above. The SETNX is used to create lock while taking care not to override any existing lock. If a lock was already present, it is then checked if its still valid. Another key part is the usage of GETSET to take over the lock while dealing with a race condition all in one statement. Only the first client to execute the GETSET will have its result matching the old value and successfully acquired the lock. The flaw in this pattern is however that it requires all clients to have their clocks synchronized. 2. SETEX based lock expiration Redis 2.0.0 introduced a new command that can be used to partialy solve this: SETEX can be used to have keys automatically expire after a given period. This can be used to empower redis to deal with expiring of locks.
var redis = require('redis');
var nameOfKeyToLock = 'the_lock';
var timeout = 10;
var retry_time = 500;
var latency_guard = 500;
var doLocked = function(client, nameOfKeyToLock, callback){
var lock = function() {
var token = Math.random().toString(36).substr(2),
lockPlacedTime;
//SETEX + RENAMENX commands as one transaction using MULTI
var multi = client.multi();
multi.setex(nameOfKeyToLock + ':tmp_lock', timeout, token);
multi.renamenx(nameOfKeyToLock + ':tmp_lock', nameOfKeyToLock + ':real_lock');
multi.exec(function(err, replies){
if(replies[1] === 1){
lockPlacedTime = Date.now();
callback(unlock);
} else {
retry();
}
});
var unlock = function(after){
//just let it expire if the lock duration is to near its timeout
if(Date.now() < lockPlacedTime + (timeout * 1000 - latency_guard)){
client.del(nameOfKeyToLock + ':real_lock', function(){
console.log('released lock');
after();
});
} else {
after();
}
};
};
var retry = function() {
console.log('scheduling retry');
setTimeout(lock, retry_time);
};
lock();
};
Great we now have a solid way of acquiring a lock without possible synchronization issues. However the client still needs to maintain its own timing for the conditional delete during the unlocking process. In case the lock is to near its expiration time, this example code simply chooses to let it expire to prevent possibly deleting the wrong lock. 3. WATCH/MULTI/EXEC based lock removal Redis 2.2.0 comes with optimistic locking support. Which I feel could be used to make the example above a bit more robust by using it for the conditional delete of a lock. The commands for optimistic locking / transactions: WATCH places the optimistic lock guard on a specified key MULTI marks the start of a transaction and queues all commands EXEC only executes all previously queued commands if all WATCHed keys are still untouched
var redis = require('redis');
var nameOfKeyToLock = 'the_lock';
var timeout = 10;
var retry_time = 500;
var doLocked = function(client, nameOfKeyToLock, callback){
var lock = function() {
var token = Math.random().toString(36).substr(2);
//SETEX + RENAMENX commands as one transaction using MULTI
var multi = client.multi();
multi.setex(nameOfKeyToLock + ':tmp_lock', timeout, token);
multi.renamenx(nameOfKeyToLock + ':tmp_lock', nameOfKeyToLock + ':real_lock');
multi.exec(function(err, replies){
if(replies[1] === 1){
//WATCH command, so lock removal only works if its value is still the same
client.watch(nameOfKeyToLock + ':real_lock', function(err){
callback(unlock);
});
} else {
retry();
}
});
var unlock = function(after){
//MULTI + EXEC commands only deletes the lock if it wasn't changed yet
var multi = client.multi();
multi.del(nameOfKeyToLock + ':real_lock');
multi.exec(function(err, replies){
if(replies !== null)
console.info('released lock');
after();
});
};
};
var retry = function() {
console.log('scheduling retry');
setTimeout(lock, retry_time);
};
lock();
};
Because of the WATCH, Redis will now take care that only if the lock still has the same value (owner) it will be deleted. Otherwise the multi.del command will simply not be executed at all (resulting in a 'null' replies). Moving yet another part of conditional logic out of the client and into Redis, thus freeing it from race conditions. So are we there yet? Well almost. WATCHes are placed per client (EXEC will check and destroy any WATCHes made with the same client). Effectively this means the amount of concurrent locks is now limited by amount of clients you can create (which is usually not a lot). Note that the same client can also not be used for any other MULTI commands during the lock, as that would destroy the WATCH used for the conditional delete. Still if this happens to map on your use-case I'd suggest using it over the above two. 4. SET based lock acquisition and EVAL based lock removal Starting from Redis 2.6.12 the SETEX and RENAMENX commands can be combined using the new argument enriched SET command. And while we're at it, lets substitude the delete logic from the above examples for a shorter version using Lua script. Lua scripts are supported from 2.6.0 and apart from inherent performance gains their true power comes again from garanteed atomicity. The commands of choice for the final example: SET sets a key to a value, but will now also deal with EXpiration and Not eXists conditions itself. EVAL Evaluates Lua 5.1 scripts and executes it atomically
var redis = require('redis');
var nameOfKeyToLock = 'the_lock';
var timeout = 10;
var retry_time = 500;
var lua_script = 'if redis.call("get", KEYS[1]) == ARGV[1]\n' +
'then\n' +
' return redis.call("del", KEYS[1])\n' +
'else\n' +
' return 0\n' +
'end\n';
var doLocked = function(client, nameOfKeyToLock, callback){
var lock = function() {
var token = Math.random().toString(36).substr(2);
//improved SET command
client.set(nameOfKeyToLock, token, 'NX', 'EX', timeout, function(err, result){
if (result !== null) {
callback(unlock);
} else {
retry();
}
});
var unlock = function(after){
//EVAL command for atomic conditional delete
client.eval(lua_script, 1, nameOfKeyToLock, token, function(err, result){
if(result === 1)
console.log('released lock');
after();
});
};
};
var retry = function() {
console.log('scheduling retry');
setTimeout(lock, retry_time);
};
lock();
};
Ignoring the script which is normally a separate file. Based on amount of code reduction without imposing any constraints, this solution is a clear winner. By moving the unlocking logic into a Lua script we get atomicity for free and get to write straightforward logic. Rightfully so this is also the recommended solution in the current redis documentation. It does however require a fairly new version of Redis which not all providers serve yet. Links examples on github in a ready to run format including the dummy test calls redis-lock popular lock implementation using the deprecated logic of example 1 my fork of it using the logic from example 4 for redis 2.6.12+ users. redis-scripto if you plan on doing more than examples with Lua (see also in my fork)
