Priority queue in Redis aka ZPOP

Redis list is great to use it as a processing queue. So great that it sort of became the standard and many people using that instead of dedicated queues such as ZeroMQ or RabbitMQ because it also gives further features that are useful. It’s main idea is to provide programming structures that you would normally use in any language. Variables, lists, sets, hashes (dictionaries), etc. But it can do even more than that by taking advantage of the functions it provides.

The use case

Sometimes it’s useful to not process items in the order of inserts and/or only necessary to process once but it may be put more than once in the queue. I faced with this problem when working with Django signals. Let’s say I want to do something with my parent class on child object being saved. That’s a very common use case for the post_save signal. Now there are usually more than one child class which has a foreign key to the same parent object. I actually don’t need to process every time an object is saved. If you’re familiar with Django imagine an admin form with inline related objects. Every time I would click save my main object would be updated N + 1 times in the database (N is the number of related objects) absolutely unnecessarily. I can do that a) in the background b) only once.

Priority queue

Sorted sets (ZSET) provides perfect way to remedy both the situation. Let’s say I have a process or cron job picks up items from the queue but instead of increasing the queue size everytime a new child class is saved it simply increases the priority for the parent class to be processed. You only need three commands to do that: ZINCRBY, ZREVRANGE, ZREM

Now you have a perfect priority queue implementation using basic redis commands.

ZREM vs ZREMRANGEBYRANK

ZREM has the time complexity (quoting redio.io):

O(M*log(N)) with N being the number of elements in the sorted set and M the number of elements to be removed.

ZREMRANGEBYRANK’s time complecity:

O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements removed by the operation.

So hypothetically the latter is better because it’s the sum of the log(N) and M while ZREM has the complexity of the product of these two but in our case it doesn’t matter since we only pop one element a time from the queue it won’t make any different.

In python

Notice that we don’t need any special locking or concurrency control because we check the return value of zrem command. If it managed to remove the element it returns 1. If it didn’t it means we had a race condition and combody removed the element before our thread/process/script. In that case we retry.

Removing the top element from the sorted set is also referred to as ZPOP.  If you prefer a single eval command there is a Lua implementation also available on redisgreen: https://www.redisgreen.net/library/zpop.html

Update (2016-02-07) based on Itamar’s comment:

The above implementation uses recursion in the assumption that contention will be a rare case. However with high concurrency or fast processing time (we did the whole thing to offload some of the heavier updates from the web serving time to a background process) the probability of such collisions increases and then a while loop is a better option than a recursive call.

A while loop version would look like this: