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

Python MySQLdb vs mysql-connector query performanc... There are a lot of python driver available for MySQL and two stand out the most. The one, traditionally everybody's choice, sort of industrial standar...
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...

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.
  • The suggested lock-less&retry implementation is problematic – you can get pretty large call stacks with returning this way.

    • Yes, I agree, in case of a heavy race condition the stack can grow quite large. To be more specific the probability of contention increases when the individual process time / concurrency is in the same order of magnitude as the time of the zrevrange and zrem command. In that case a while loop certainly would be a better option.

      I’ve updated the post to include that as well. Thank you for the comment!