优先级队列 --- 等级队列 vs 权重队列

队列是一种安排数据辅助程序处理的工具,常见的有fifo队列,lifo队列和priority队列。

priority队列里面根据容器实现的局限,可以分为权重队列和等级队列,其中权重队列>=等级队列。权重队列是指每一条入队列的数据的priority都有可能不同,并且priority很随机,不同的情况很多;等级队列是指所有的数据的priority可以分为有限的几类,每一类对应一个数据channel,逻辑层面个人觉得最好是不超过5吧,具体情况还得看工具支持的情况。实际上等级队列更像数据的priority分类取,权重队列则是数据的priority排序取。

权重队列

权重队列的priority基本不受约束,使用起来比较自由,只要容器支持数据的排序和数据同步,就能基于该容器实现权重队列。
例如:

  • 大顶堆和小顶堆支持堆排序,然后通过锁实现数据同步,因此程序语言实现的标准队列的priority队列都是权重队列
  • mongo是数据库,支持字段排序,并且有find_and_modify可以实现数据同步,也可以实现权重队列。
  • beanstalkd的内部协议支持排序,所以是权重队列。

等级队列

等级队列的priority在程序员编码的时候就固定了,是像常量一样执行前设定的,数的清的,不能动态添加设定之外priority数据,一般实现等级队列的容器需要支持数据channel,当然必须是数据同步。
例如:

  • redis的list可以作为数据channel使用,然后通过blpop、brpop实现数据同步,如果sorted set不支持数据同步,就可以实现权重队列。
  • rabbitmq,多么强大的队列,是通过数据channel实现等级队列,3.5.0版本以后有rabbitmq_priority_queue插件,注意设置x-max-priority属性,否则rabbitmq-server服务会crash。

权重队列比等级级队列自如,而且权重队列是可以当等级队列用的,反过来是不行的。在特殊情况权重队列无法替代等级队列,例如priority值一定要用high、low或者其他有意义的字符串来标识,而这类字符串的通用比较又不是正确的priority,除非基础环境支持良好的hack。能不能实现权重队列,就看容器里面的数据是否方便排序了。