Adding a SADDX command to Redis using Lua

A popular use case for Redis is as an in-memory cache. Most see it as an advanced memcached on steroids. The advanced part is right there in its description on redis.io : advanced key-value store that can contain strings, hashes, lists, sets and sorted sets. If you don't know about the data structure server called Redis, then read about it at redis.io.

Why add if exists?

An add if exists pattern is useful when using Redis as a memory cache server. Suppose you have a blog that has posts and those posts have tags. One day you introduce a new Redis memory cache into production. When a post is read you neatly get all of the tags associated with the blog post. You of course are caching those tags using a Redis set. The cache is empty so you grab the tags from the database and perform SADD's to populate the cache. Good Work! But consider what happens when the first action is adding a new tag to an existing post. You write the new tag to the database and SADD it into the cache. Now the cached set just has the single tag in it and is missing any previous tags. Now when a post is viewed the cached set exists and your incomplete list of tags is shown. Zoiks !

Solutions

There are a few ways to solve this, but the easiest is to only SADD the new value if the set already exists. To accompany this, on reads when the cache is empty you repopulate the full list from your permanent datastore and everything works as expected.

Atomicity

Knowing that we should be checking for the set first, lets look at a potential implementation.

key = "post:11:tags"  // Lets assume the post id is 11
tag = "code"

if (redis.exists(key)) {
   redis.sadd(key, tag)
}

Another option would be to use SCARD and check for a > 0 result. The real issue though is there is a race condition. Any number of things can occur between the check for existence and the SADD. Another client could delete the set, you could hit a memory limit and Redis expires the key or an admin trying to be funny executes a FLUSHALL at the wrong time. Any of those (and others) would cause the issue illustrated above to occur. This is because the EXISTS and SADD when executed by a client do not run in an atomic way, other commands can get executed in between. Redis does have the concept of transactions, but the result of one command in the transaction can not be used to influence another command in the same transaction.

The closest commands Redis has at the moment are LPUSHX and RPUSHX, but both only operate on lists so they don't currently help us. There is also a WATCH command but if you are using Redis 2.6+ a simple Lua solution is much easier to understand.

Enter SADDX and Lua

According to the Redis documentation each Lua script command is executed atomically. That is to say no other script or Redis command will be executed while a script is being executed. This will protect us against our race condition. Yeah!

I started with the following Lua script.

if redis.call('type', KEYS[1]) == 'set' then
   return redis.call('sadd', KEYS[1], ARGV[1])
else
   return nil
end

I changed the check to use the TYPE command to check for the existence and type of the key. This script would support the following usage:

    EVALSHA 1c3bc2f2cae54a34f52206df01a549a07f240115 1 post:11:tags code

This however didn't work as expected and since this is also my first attempt with any Lua scripting the answer wasn't obvious for me at first. After a bit I found the type function so I could determine what the redis.call was returing since it apparently wasn't a string. Turns out it was of type table, which in Lua is an aggregate data type used for storing any type of collection (lists, sets, arrays, hashes etc.). If you look at the TYPE command its return value is indicated as a status reply. The EVAL command documentation has a section on converting from Redis response types to Lua types and it indicates a status reply gets converted to a Lua table with a single ok field containing the status. Ah ha!

Now we can alter our Lua script to get to a working implementation.

if redis.call('type', KEYS[1]).ok == 'set' then
   return redis.call('sadd', KEYS[1], ARGV[1])
else
   return nil
end

We have successfully created an atomic SADDX command using Lua and can safely add if exists our tags.

For completeness sake, the SCARD command returns an integer so its implementation would look like:

if redis.call('scard', KEYS[1]) > 0 then
   return redis.call('sadd', KEYS[1], ARGV[1])
else
   return nil
end

Closing notes

As both have a O(1) time complexity (they'll each run at a consistent speed no matter how many keys or set members) you would just have to benchmark each using a simple scenario to determine which is faster.

This is generally a fire and forget type statement, so for either you could safely remove the else portion. It seems the script returns a nil anyway, but I would favour leaving the return of the SADD command. This allows you to check the return if required where a nil (or null, depending on your client language of choice) is returned when the set doesn't exist, a 0 if the value already exists in the set and a 1 if the value was added.

This leaves our final implementation as:

if redis.call('scard', KEYS[1]) > 0 then
   return redis.call('sadd', KEYS[1], ARGV[1])
end