Using Redis Lua scripting for complex queues

Redis is described by its author Salvatore Sanfilippo as a “strange project”. It’s a distributed cache, it’s an in-memory key-value store, and it’s a notification (publish/subscribe) server. A kind of all-in-one, which is actually good at everything it does. Although Redis keys and values are essentially just strings, one can group them into lists, sets, hashes and all-powerful sorted sets. It also stores numbers very efficiently, which makes such values consume less memory and enables fast numerical operations on them (like atomic increments).

However, what makes Redis really powerful and so essential to one of our projects is Lua scripting. Among many other things, this project has public web site activity moderation queues with very complex logic. When a new activity arrives, there are multitude of checks to be made and data items to be persisted. Each of these operations is subject to a potential race condition. For example, when moderators come to a specific queue, system has to “join” moderator and item queues, so that the longest waiting activity is delivered to the longest waiting moderator. Activity has to be locked for the moderator, so that it would never be possible for 2 people to work on the same item simultaneously, but locks may expire, and then the activity should retain the same priority as it once had, when it has been locked. And this is just a small fraction of logic to be executed in a high traffic, real-time environment.

Redis Lua scripting suits such needs very well. Redis is a single-threaded system, there are no parallel data read/write activities happening, including script execution. This makes it very simple to ensure data consistency in the face of complex logic. It may sound impractical to use just one thread for high-traffic systems, but it works very well in Redis, since all it does boils down to very simple and efficient data structure manipulation in memory, which is almost instantaneous.

Following is a very simple example of how Redis Lua script can be used to avoid possible race condition (when an action has to be taken based on value, which should be “locked” until action is fully executed):

local setKey = KEYS[1]

local score = ARGV[1]

local member = ARGV[2]
local currentScore = redis.call("ZSCORE", setKey, member)

if currentScore == score then

    redis.call("ZREM", setKey, member)

    return "REMOVED"

else

    return "NOT_REMOVED"

end

As any Redis script, the above example receives 2 input tables (1-based arrays) – KEYS and ARGV (for key and non-key input values). It then removes a value (member) from sorted set, but only if it hasn’t changed its score since we retrieved it and made some potentially time-consuming actions on it. That is, we can retrieve current score of the value, compare it with the score we have, and then act on the comparison result, knowing that this result will hold for the duration of the script. One can imagine these scripts grow to a hundred lines (like in the above-mentioned project), while executing in a few milliseconds and having sufficient durability guarantees. I like to call it “complex data consistency on the cheap”.

Some “gotchas”

Even though Redis is an in-memory store (its whole dataset has to fit into RAM) it has very good durability guarantees and replication capabilities. However, before using Redis as a data store, one needs to read this extensive article on Redis persistence (written by Salvatore himself) and see if it’s good enough for the project: http://oldblog.antirez.com/post/redis-persistence-demystified.html. It’s worth mentioning that the same atomicity and durability guarantees apply also to writes, happening as a result of script execution.

One also has to realize that there is no rollback in Redis. If a logical error happens in the middle of the script (like comparing number to nil or accessing set key with sorted set command), the script returns with an error immediately, but the writes, which happened before the error, are successfully persisted. This may sound like no-go for data consistency scenarios, described above. However, one has to realize that there is a very small set of such errors, which are easily avoided with appropriate guards. It’s just important to remember how essential it is to put these guards in all the necessary places throughout the script.

And don’t hesitate to contact us for any questions or comments on the topic!