Redis SPOP Culture:

Censored Lua vs Atomic Transactions with Node.js and Redis

This is part 9 of my Node / Redis series. The previous part was Redis, set, node. The next part is Node, Redis, node_redis and NodeRedis.

Let’s say you create a Redis SET by doing this:

> SADD my-old-set 1 2 3
(integer) 3

And you want to take a member element and move it to a new set.

> SPOP my-old-set
"3"
> SADD my-new-set 3
(integer) 1

Due to the random nature of SPOP, it could actually be any one of the members of my-new-set. No problem, right? Well, it is not atomic.

Let’s say that these sets represent an inventory of unique things and it would be terrible if a member existed in more than one place: money could be lost, people could be in danger, etc. If you did the above non-atomically, then there exists a chance that another client could slip in and add the SPOP’ed member back into my-old-set between adding it to my-new-set. You need this operation to be atomic.

To make it atomic, my first thought was “Let’s write a Lua script.” I try to avoid using Lua, because, well, I’m not super familiar with the syntax and bad things™ can happen if you aren’t careful. But this should just be a two-liner. Maybe it would look something like this:

local popped = redis.call(“SPOP”,KEYS[1])
redis.call(“SADD”,KEYS[2],popped)
return popped

I tried running the script and got a very curious error message in return:

@user_script: 1: This Redis command is not allowed from scripts

Huh. My first thought was that I did something wrong with Lua. Nope — line 1 is okay syntactically. I did what any good programmer does when they get an error message: copy/paste/google. The second result was source code to Redis itself:

/* There are commands that are not allowed inside scripts. */
if (cmd->flags & REDIS_CMD_NOSCRIPT) {
luaPushError(lua, "This Redis command is not allowed from scripts");
goto cleanup;
}

Oh.. wow. Third Goolge result is a GitHub closed issue: Why is spop not an allowed script command? It seems the issue is that SPOP returns a random element — this throws a spanner in the works for replication and is, thus, blocked. Makes sense — random, by nature, can’t be replicated. The answer in the issue seems to be “don’t do it atomicly.” Yikes.

So. How does one get this done atomically? You know what they say about will’s and way’s.

The approach is to think multi not Lua. Essentially, we’re going to make a copy of the original source set (SUNIONSTORE), pop the value off the original set, compare that set to the copy of the original and store (SDIFFSTORE) the result. Finally, we’ll merge the difference into the destination (SUNIONSTORE again) and clean up the two temp keys. We can do all of this without breaking the transaction. Here is how you swing it with Node, although it should be pretty clear for any other client library / language.

Your data center has a fire extinguisher, right?

Okay. The above code illustrates that the technique works, but at what cost?This is, shall we say, not cheap. In non-working Lua version, the complexity is O(1)+O(1). Cheap.

In the working MULTI/EXEC implementation, the complexity is: O(N1)+O(1)+O((N1–1)+N1)+O(N2+1)+O(1)+O(1) where N1 is the number of elements in the source set, and N2 is the number elements in the destination set. Not cheap. In the above example — no problem, we’re talking 3 members into an empty set. Think, however, if you had 1 million members in the source and 1 million in the destination. It wouldn’t be fun.

Show your support

Clapping shows how much you appreciated Kyle’s story.