Redis As Distributed Priority Queue

Mon, Sep 28, 2020 2-minute read

In this post, I will share a way I make use of Redis sorted set which can act as distributed/centralized priority queue.

Problem

Suppose we have an application whose architecture can be viewed as below diagram

architecture

  • Controller is in charged of adding job to Job Queue. Of course, Controller can go multi instances.
  • Job has its name and its priority. Higher priority means lower value.
  • Workers always retrieve job with highest priority at the current time.

As we can easily observe, we need a distributed/centralized priority queue to resolve our problem.

Priority Queue

Let take sometime to talk about priority queue. According to wikipedia

In computer science, a priority queue is an abstract data type similar to regular queue or stack data structure in which each element additionally has a “priority” associated with it. In a priority queue, an element with high priority is served before an element with low priority.

Basic Operations

  • insert: inserts an item with given priority
  • pop: pull out the element with highest priority

Redis sorted set

Redis is one of my most favourite technology. It has really rich set of data structure that can fit in a lot of usecases. In general, Redis takes care all problems about concurrent access, centralized data structure, scaling if needed.
sorted set, the name said itself, Redis will ensure whenever the score is updated and the element reinserted at the right position to ensure the correct ordering.

insert

We use ZADD to insert element with its priority to queue. Syntax: ZADD key [NX|XX] [CH] [INCR] score member [score member ...]

Example:

127.0.0.1:6379> zadd sorted_set 2 element_1 1 element_2
(integer) 2

pop

Let’s use ZPOPMIN to get the element with highest priority). Syntax: ZPOPMIN key [count]

Example:

127.0.0.1:6379> zpopmin sorted_set
1) "element_2"
2) "1"

We can see that it pops out the element with lower priority value as expected.

Redis Sorted Set provides much more, it has a lot of commands that you can tweak those to enrich feature set for your distributed priority queue, such as:

  • blocking_pop: wait until the queue is non-empty then pull out the element with highest priority
  • remove: remove specific element in the queue
  • count: returns the queue cardinality