How to implement non-distributed locks which expire?

Question

Meaning, they don't have to be distributed. I'm thinking about using memcached or redis for that. Probably the latter one. What I'm concerned about is "we've got to free some memory, so we'll delete this key/value before it expired" thing. But I'm open to other suggestions as well.

Answer 1

tl;dr Use ready-made solution, suggested by developers.

So, I decided not to use memcached for the purpose. Since it's a caching server. I don't see a way to ensure that it doesn't delete my keys because it's out of memory. With, redis that's not an issue as long as maxmemory-policy = noeviction.

There are 3 links I want to share with you. They are basically 3 ways, that I now know, to solve the issue. As long as you have redis >= 2.6.0 that is.

redis >= 2.6.12

If you've got redis >= 2.6.12, you're lucky and can simply use setnx command with its new options ex and nx:

$redis->set($name, <whatever>, array('nx', 'ex' => $ttl));

But we can't just delete the lock in the end, if we are to allow for critical section taking longer then we expected (>= ttl). Consider the following situation:

C1 acquires the lock
lock expires
C2 acquires the lock
C1 deletes C2's lock

For that not to happen we are going to store current timestamp as a value of the lock. Then, knowing that Lua scripts are atomic (see Atomicity of scripts):

$redis->eval('
    if redis.call("get", KEYS[1]) == KEYS[2] then
        redis.call("del", KEYS[1])
    end
', array($name, $now));

However, is it possible for two clients to have equal now values? For that all the above actions should happen within one second and ttl must be equal to 0.

Resulting code:

function get_redis() {
    static $redis;
    if ( ! $redis) {
        $redis = new Redis;
        $redis->connect('127.0.0.1');
    }
    return $redis;
}

function acquire_lock($name, $ttl) {
    if ( ! $ttl)
        return FALSE;
    $redis = get_redis();
    $now = time();
    $r = $redis->set($name, $now, array('nx', 'ex' => $ttl));
    if ( ! $r)
        return FALSE;
    $lock = new RedisLock($redis, $name, $now);
    register_shutdown_function(function() use ($lock) {
        $r = $lock->release();
        # if ( ! $r) {
            # Here we can log the fact that lock has expired too early
        # }
    });
    return $lock;
}

class RedisLock {
    var $redis;
    var $name;
    var $now;
    var $released;

    function __construct($redis, $name, $now) {
        $this->redis = get_redis();
        $this->name = $name;
        $this->now = $now;
    }

    function release() {
        if ($this->released)
            return TRUE;
        $r = $this->redis->eval('
            if redis.call("get", KEYS[1]) == KEYS[2] then
                redis.call("del", KEYS[1])
                return 1
            else
                return 0
            end
        ', array($this->name, $this->now));
        if ($r)
            $this->released = TRUE;
        return $r;
    }
}

$l1 = acquire_lock('l1', 4);
var_dump($l1 ? date('H:i:s', $l1->expires_at) : FALSE);

sleep(2);

$l2 = acquire_lock('l1', 4);
var_dump($l2 ? date('H:i:s', $l2->expires_at) : FALSE);   # FALSE

sleep(4);

$l3 = acquire_lock('l1', 4);
var_dump($l3 ? date('H:i:s', $l3->expires_at) : FALSE);

expire

The other solution I found here. You simply make the value expire with expire command:

$redis->eval('
    local r = redis.call("setnx", ARGV[1], ARGV[2])
    if r == 1 then
        redis.call("expire", ARGV[1], ARGV[3])
    end
', array($name, $now, $ttl));

So, only acquire_lock function changes:

function acquire_lock($name, $ttl) {
    if ( ! $ttl)
        return FALSE;
    $redis = get_redis();
    $now = time();
    $r = $redis->eval('
        local r = redis.call("setnx", ARGV[1], ARGV[2])
        if r == 1 then
            redis.call("expire", ARGV[1], ARGV[3])
        end
        return r
    ', array($name, $now, $ttl));
    if ( ! $r)
        return FALSE;
    $lock = new RedisLock($redis, $name, $now);
    register_shutdown_function(function() use ($lock) {
        $r = $lock->release();
        # if ( ! $r) {
            # Here we can log that lock as expired too early
        # }
    });
    return $lock;
}

getset

And the last one is described again in documentation. Marked with "left for historical reasons" note.

This time we store timestamp of the moment when the lock is to expire. We store it with setnx command. If it succeeds, we've acquired the lock. Otherwise, either someone else's holding the lock, or the lock has expired. Be it the latter, we use getset to set new value and if the old value hasn't changed, we've acquired the lock:

$r = $redis->setnx($name, $expires_at);
if ( ! $r) {
    $cur_expires_at = $redis->get($name);
    if ($cur_expires_at > time())
        return FALSE;
    $cur_expires_at_2 = $redis->getset($name, $expires_at);
    if ($cur_expires_at_2 != $cur_expires_at) 
        return FALSE;
}

What makes me uncomfortable here is that we seem to have changed someone else's expires_at value, don't we?

On a side note, you can check which redis is it that you're using this way:

function get_redis_version() {
    static $redis_version;
    if ( ! $redis_version) {
        $redis = get_redis();
        $info = $redis->info();
        $redis_version = $info['redis_version'];
    }
    return $redis_version;
}

if (version_compare(get_redis_version(), '2.6.12') >= 0) {
    ...
}

Some debugging functions:

function redis_var_dump($keys) {
    foreach (get_redis()->keys($keys) as $key) {
        $ttl = get_redis()->ttl($key);
        printf("%s: %s%s%s", $key, get_redis()->get($key),
            $ttl >= 0 ? sprintf(" (ttl: %s)", $ttl) : '',
            nl());
    }
}

function nl() {
    return PHP_SAPI == 'cli' ? "\n" : '<br>';
}