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:

 

You might like these too

5 things to love about python Syntax Takes a bit of time to get used to it but after a certain point it just becomes natural. Like english. No heavy-weight operators or complicate...
Sunburnt Solr spatial filter support I've added spatial filtering to the sunburnt library. The feature is now available with filter_spatial function. Example usage Currently this will...
Stream cypher (encrypt) with digital envelope in P... Generating. storing and keeping inventory of hundreds of terabyte large database backups is a challenge by itself which we do on daily basis. It's eve...

About charlesnagy

I'm out of many things mostly automation expert, database specialist, system engineer and software architect with passion towards data, searching it, analyze it, learn from it. I learn by experimenting and this blog is a result of these experiments and some other random thought I have time to time.
Bookmark the permalink.