使用redis构造优先级队列

redis作者@antirez在其blogHow to take advantage of Redis just adding it to your stack中提到：“Similarly using sorted sets it is possible to implement priority queues easily.”。

本文将会探讨下如何使用redis提供的sorted sets数据结构，构造高效率的优先级队列。

什么是sorted sets

以下段落来自reids.io->Data types。

Redis Sorted Sets are, similarly to Redis Sets, non repeating collections of Strings. The difference is that every member of a Sorted Set is associated with score, that is used in order to take the sorted set ordered, from the smallest to the greatest score. While members are unique, scores may be repeated.

With sorted sets you can add, remove, or update elements in a very fast way (in a time proportional to the logarithm of the number of elements). Since elements are taken in order and not ordered afterwards, you can also get ranges by score or by rank (position) in a very fast way. Accessing the middle of a sorted set is also very fast, so you can use Sorted Sets as a smart list of non repeating elements where you can quickly access everything you need: elements in order, fast existence test, fast access to elements in the middle!

In short with sorted sets you can do a lot of tasks with great performance that are really hard to model in other kind of databases.

With Sorted Sets you can:

Take a leader board in a massive online game, where every time a new score is submitted you update it using ZADD. You can easily take the top users using ZRANGE, you can also, given an user name, return its rank in the listing using ZRANK. Using ZRANK and ZRANGE together you can show users with a score similar to a given user. All very quickly.
Sorted Sets are often used in order to index data that is stored inside Redis. For instance if you have many hashes representing users, you can use a sorted set with elements having the age of the user as the score and the ID of the user as the value. So using ZRANGEBYSCORE it will be trivial and fast to retrieve all the users with a given interval of ages.
Sorted Sets are probably the most advanced Redis data types, so take some time to check the full list of Sorted Set commands to discover what you can do with Redis!

使用sorted sets构造优先级队列

sorted sets有如下三个命令：

1.ZADD key score member [score] [member]

以O(log(N))的复杂度，向集合中加入一个元素。如下所示：

redis 127.0.0.1:6379> ZADD "www.baidu.com" 1 "first_page" 2 "second_page" 3 "third_page" 3 "another_page"
(integer) 4

2.ZREVRANGE key start stop [WITHSCORES]

以O(log(N)+M)的复杂度，取元素。N是集合中元素个数，M是返回值的元素个数。使用WITHSCORES，将会同时返回对应元素的SCORE。在优先级队列中，我们只取最高优先级的一个元素，如下所示：

redis 127.0.0.1:6379> ZREVRANGE "www.baidu.com" 0 0
1) "third_page"
redis 127.0.0.1:6379> ZREVRANGE "www.baidu.com" 0 0 WITHSCORES
1) "third_page"
2) "3"

3.ZREM key member [member]

以O(log(N))的复杂度，删除sorted set中的特定元素。这里的member为ZREVRANGE中的返回值即可，如下所示：

redis 127.0.0.1:6379> ZREM "www.baidu.com" "third_page"
(integer) 1

删除元素前后，优先级队列中的元素对比如下：

redis 127.0.0.1:6379> ZREVRANGE "www.baidu.com" 0 -1 WITHSCORES
1) "third_page"
2) "3"
3) "another_page"
4) "3"
5) "second_page"
6) "2"
7) "first_page"
8) "1"
redis 127.0.0.1:6379> ZREVRANGE "www.baidu.com" 0 -1 WITHSCORES
1) "another_page"
2) "3"
3) "second_page"
4) "2"
5) "first_page"
6) "1"

据此，一个高效（O（logN）的复杂度）的优先级队列就可以使用了。

事件通知模式

参照上述方法构造的优先级队列是非阻塞模式的，这样，如果当前Sorted Sets为空，要求调用方不断轮循（polling），这对使用者来说是非常不方便的。redis并未提供阻塞版本的ZREVRANGE，但是使用blpop命令，可以实现优先级队列的阻塞语义。

参考：Pattern: Event notification

消费者（consumer）如下：

LOOP forever
    WHILE ZREVRANGE(key,0,0) returns elements
        ... process elements ...
        ZREM(key, elements)
    END
    BRPOP helper_key
END

生产者（producer）如下：

MULTI
ZADD key element
LPUSH helper_key x
EXEC