1、背景
PriorityQueue 是位于 Messenger 和 PG Worker 之间的队列，主要用来维护消息的优先级调度，比如客户端 IO 消息会优先出队列被处理，副本写成功回复的优先级也非常高。目前已有的算法是采用令牌向量实现，为每个客户端和每个消息作了一个 cost 控制，避免存在消息”饿死”情况。
2、实现
2.1、类结构介绍
PrioritizedQueue有两个重要的成员:SubQueues high_queue;SubQueues queue; 类图参考如下：
image.png
2.2、插入
分为严格优先级插入和非严格型， 严格型是指严格按照优先级大小进行入队和出队, 并且严格优先级大于非严格型，也即严格优先级没有元素才轮得到非严格型。
无论是严格型还是非严格型又都分为从前插入和从后插入， 具体根据业务消息的需要， 从前表示高于同等级、同连接下的其它已插入的消息。
2.3、取出
优先查看high_queue中的消息， 即严格型插入的队列， 并选择较大优先级的子队列， 针对该队列里面的多连接的消息队列按照round robin的算法轮训每个连接的消息
其次查看queue中的消息，为了避免低优先级的消息被饿死， 从较低的优先级队列开始检查是否有满足发送条件的消息，主要是检查头元素的cost 是否小于SubQueue::tokens, 如果满足即可返回， 并且重置SubQueue::tokens=tokens-cost， 把cost按照优先级重分配给所有优先级队列, 参考公式：((i->first * cost) / total_priority) + 1， 从公式看优先级越高， 能分配到的就越多， 也符合高优先级的性质，也避免了一直出高优先级导致低优先级被饿死的情况，即是把高优先级使用的cost分给了低优先级， 让低优先级又有机会得到执行， 是一个动态均衡的过程。
如果queue中没有满足要求的消息， 那么从更高优先级的队列中出队一个元素， 并且重分配cost到所有队列。
3、总结
对于普通对列， 所有元素是没有特权的， 只能先进先出，优先级队列加入了会员制，是会员的优先级更高， 优先出队， 但是为了避免普通人被饿死， 又设计了权重， 高优先级出队的时候又把一定的权重分配给了其它低优先级队列， 保证低优先级不致于被饿死。
参考
1、chrome-extension://oemmndcbldboiebfnladdacbdfmadadm/https://patentimages.storage.googleapis.com/22/8b/48/e6ec282ed2c4df/CN103986668A.pdf
2、https://www.xsky.com/tec/174/
3、https://www.liaoxuefeng.com/wiki/1252599548343744/1265120632401152
网友评论