需求介绍

在 这篇文章 中讨论了在一批队列里如何对任务更好地排序。为方便说明，下面再把类定义和队列规则描述一下：

public class Task implements Comparable<Task> {

	/**
	* 任务id
	*/
	private long id;

	/**
	* 入队时间
	*/
	private long addTime;

	/**  
	* 是否处于专属队列中  
	*/  
	private boolean inPrivateQueue;  
	  
	/**  
	* 是否处于vip队列中
	*/  
	private boolean inVipQueue;  
	  
	/**  
	* 所处队列的优先级
	*/  
	private int priority;

	// 比较函数
	// 如果task1 < task2, 则返回-1；
	// 如果task1 == task2, 则返回0；
	// 如果task1 > task2, 则返回1
	@Override
	public int compareTo(Task o) {  
		// TODO
		return 0;
	}
}

消费者的消费规则：

• 如果专属队列有任务，则从专属队列中选择排队时间最长的任务

• 如果专属队列无任务，VIP队列中有任务，则选择VIP队列中的任务

  • 对VIP队列中的任务按队列优先级进行排序，选择优先级最高的队列
  • 如果优先级最高的队列只有一个，则从该队列中选择排队时间最长的任务
  • 如果优先级最高的队列有多个，则从这多个队列中选择排队时间最长的任务

• 如果专属队列无任务，VIP队列中无任务，则选择非VIP队列中的任务

  • 对非VIP队列中的任务按队列优先级进行排序，选择优先级最高的队列
  • 如果优先级最高的队列只有一个，则从该队列中选择排队时间最长的任务
  • 如果优先级最高的队列有多个，则从这多个队列中选择排队时间最长的任务

现在将需求再扩大一点，假设有一批队列，每条队列中都有一批任务。不同的队列可以组成一个队列组，消费者可以订阅队列组。其数量关系如下：

用一张图来表现这个关系：

对于消费者自身来说，也有对应的状态。消费者初态为未就绪，当消费者改变自身状态为已就绪状态时，则可以被分配任务。消费完一个任务之后，消费者进入未就绪状态。关于消费者的状态转移图如下所示：

另外还要注意的是：

1. 一个队列组可能同时被多个消费者订阅，那么在这个队列组中的任务，就有可能会对应多个消费者。此时，需要按照消费者的准备时间先后进行分配。
2. 消费者可以选择接受任务或不接受任务，如果消费者不接受任务，则消费者回到未就绪状态，然后再将该任务分配给订阅了所属队列组的消费者。举个例子，比如任务T1 可以分配给消费者 C1和C2，如果将T1分配给C1时，C1没有接受，则任务T1将会继续分配给C2；如果C2接受了该任务则由C2处理，如果C2不接受该任务，则任务T1继续留在队列中，等待下一次重试。

现在需要将队列中的任务，按照消费者和队列组的订阅关系，以及上述的消费规则，分配给对应的消费者。需要解决这两个问题：

1. 当每个队列都有一批任务需要被分配时，如何设计分配策略以满足上述要求？
2. 需求具有一定的复杂度，如何保证实现逻辑的正确性？

当然，系统的可用性也需要考虑，但不是想要说明的重点，先暂时忽略。对于这样的需求，你会如何设计呢？

下面会先讲述如何实现，对于如何保证逻辑实现正确性也相当重要，但暂且按下不表，会在另一篇文章解决。

利用简化思维拆解需求

消费者、队列组和队列，都是多对多的关系，要处理起来的确不太容易。对于这样复杂的关系，我们可以对需求进行简化。

既然消费者对应的是队列组，那么队列组里有多少条队列，对于消费者来说并不知道。队列组里可以是100条队列，也可以只有1条队列，那么假如每个队列组里面只有1条队列呢？是不是也符合现在的需求？这样的话，队列组本身起到的作用就并不大了，甚至可以直接去掉队列组，将模型简化成下面这样：

这样消费者直接和队列打交道，看起来就简单多了。这样的话，我们可以从队列中的任务视角出发，找到这个任务都有哪些消费者，然后逐一尝试就可以了。

可能你会有这样的疑问：直接将队列组去掉了，让消费者和队列直接交互，能确保它的正确性吗？当然是可以的，因为队列组里只有一条队列，是这个需求的一个特例，既然是在需求范围内的，自然也就符合需求了。

需要注意的是，任务、队列和队列组的信息在业务系统里，都是存储在数据库里的，当有多条队列存在的时候，每条队列都需要获取队头任务，一条条队列地获取队头元素明显是不合适的。因此，在实现上，会将每条队列中的队头任务先查出来，然后再根据订阅关系，形成这样的一个待分配的任务结构：

@AllArgsConstructor
class CandidateTask {
	
	// 真正待处理的任务
	private Task task;

	// 待处理任务对应的处理人的列表，按准备时间先后排序
	private List<Consumer> consumers;
}

基本的思路有了，我们可以得到这样的伪代码：

public List<CandidateTask> findCandidateTasks() {
	// 找到队列中的队头任务列表
	List<Task> tasks = findHeadTasks();
	// 根据队头任务列表找到对应的消费者列表
	List<Subscription> subscriptions = findSubscriptionsByTasks(tasks);
	List<Consumer> consumers = findSubscribeReadyConsumersByTasks(tasks);

	
	return createCandidateTasks(tasks, consumers, subscriptions);
}

当我们做出这样的简化之后，事情就变得好办了。我们可以先针对这种简化的情况，设计测试用例，先确保在特例下的正确性，然后再将范围扩大到队列组，最后确保整个需求的正确性。

利用抽象思维实现需求

上面对队列组的情况做了简化，似乎一切都挺顺利。但是当引入队列组时，情况就有所不同。比如：

1. 只有一条队列时，我只需要考虑这条队列的队头元素就可以了。但是，当消费者面对的是队列组时，这个队列组还有“队头”任务吗？
2. 不同的消费者可能会订阅多个队列组，且订阅的队列组可能会相同，也就是说，在跨队列组的情况下，如果沿用上面的简化方案，那要怎么找到“队头” 任务呢？

在实际需求开发的时候，我一时之间也没有很好的思路。以终为始，从最后想要的结构来反推，我们期望最终得到的结构是一个CandidateTask，但是任务只能取一个。既然原来的队列变成了可能存在多个队列的队列组，那么将一个队列组看成是一个队列呢？这样每次分配时，只需要选取在这个队列组范围内的队头任务就可以了，是不是这样就可以和简化模型贴合了？

看上去很美好，但实际上这样做还会有问题。同一个消费者可能会订阅多个队列组，当这多个队列组都选出了一个队头任务时，这些队头任务就要去匹配对应的消费者了。考虑这样一个场景：

当消费者订阅的队列组存在交叉，每个队列组都选出一个“队头”任务时，得到的结果是：

这样的结果会有几个问题：

1. 队头任务之间不得不进行一次排序。假设在队列组选出的任务优先级上，QueueGroup1-Task1 > QueueGroup3-Task1 > QueueGroup2-Task1。按消费者的准备时间看，Consumer1 比 Consumer2 早准备。那么，对于任务QueueGroup1-Task1 则会优先分配给Consumer1处理。然后QueueGroup2-Task1发现Consumer1已经在处理任务了，那么就转给Consumer2处理。这样优先级较高的QueueGroup3-Task1 反而没被处理，这与需求不符。
2. 每次都取队列组中的队头，但不一定每次都是在队头的任务会被优先处理。如图所示，假设在QueueGroup1中的任务优先级都很高，而QueueGroup2中的任务优先级都很低，那么就可能在QueueGroup1中，存在一个任务QueueGroup1-Task2，它的优先级比QueueGroup2-Task1还要高。这样每次都取队头任务出来处理的话，QueueGroup2-Task1比QueueGroup1-Task2要先被处理，这也明显不符合需求。

看起来这个方案还有很大的缺陷，其问题的原因在于，在分配任务时，我们都选了每个队列组的队头任务来分配，相当于处于队头的任务被认为优先级很高，但其实在其他队列组中，排在队头后面的任务可能有着更高的优先级，所以才会出现这样的问题。究其原因，还是要对任务最终的优先级在合理的范围内进行排序。

但是，将队头任务和其他队列组里的其他任务来做比较，在代码上几乎不可能这样实现，如果队列组有m个，每个队列组都有n个任务，那将队头和其他任务比较一次的时间复杂度，将会是O(mn) ，这肯定是不现实的。那还有什么方法呢？

其实，上述方案也并不是没有参考价值。我们可以借鉴的是，“队列” 既可以是我们在使用时看到的那一条条队列，也可以是在一定范围内（如队列组）的任务序列，这样也可以算是一条队列。而我们每次选择任务时，要做的就是在这个范围内选择一个任务出来，然后分配给对应的消费者。

另外，还要思考的一个问题是，选择的这个任务，必须要在全局范围内优先级最高吗？其实也不是，只要对某个消费者来说，在他订阅的所有队列组中，优先级最高即可。这相当于从原来的任务视角，转变为消费者视角来看待问题，相当于问题又转换成了，对于某个消费者，如何从他关心的一堆任务里，找到一个优先级最高的任务来处理。而这一堆任务，经过 这篇文章 的排序规则排序后，就会组成一个任务队列，然后消费者只需要从这个任务队列中取队头元素就可以了。这堆任务圈定的范围，其实就是这个消费者订阅的所有队列组，取名为订阅组。如图所示：

经过这样抽象之后，在订阅组内部还可以用一个小技巧让选举队头任务更高效。在订阅组内部会有很多条队列，每次只需要从这些队列中选出队头任务即可。注意到同一队列中的任务本身就存在一定的大小关系，在队头的任务肯定会比同一队列非队头的任务被优先分配。所以，在订阅组选举出队头任务时，只需要从订阅组内的队列的队头任务中选举一个任务即可。这样比较的量少了，效率也会得到提高。

这样处理后，模型再一次被简化，消费者和队列之间的关系就变成了 1: 1，而且消费者之间的任务可以说是隔离了，即使最终的结果可能是一个任务仍然有多个消费者对应，或者是订阅组之间是有重叠的，但是对消费者来说，只需要关心能否从这个大队列里得到一个可处理的任务就行了。

对应的伪代码如下：

public List<CandidateTask> findCandidateTasks() {
	// 依然是找到队列中的队头任务列表，但这回的队列指的是 “订阅组” 了。
	// 注意因为队列组可以被多个消费者订阅，找出来的任务可能会重复，要注意去重
	List<Task> tasks = findHeadTasksInEachSubscriptionGroup();
	// 根据队头任务列表找到对应的消费者列表，和简化方案的伪代码一致
	List<Subscription> subscriptions = findSubscriptionsByTasks(tasks);
	List<Consumer> consumers = findSubscribeReadyConsumersByTasks(tasks);
	
	return createCandidateTasks(tasks, consumers, subscriptions);
}

至此，整个核心逻辑可以满足需求了。

总结

从整个流程的分析和推导，我们可以看到简化、问题转化、抽象思维在需求实现上的作用。总结起来有几个点：

1. 先简化问题，用特例降低问题复杂度，然后用测试确保逻辑的正确性。在这个例子中，就先简化了队列组的概念，保证在特例的情况下逻辑的正确性。
2. 对简化后的问题，用抽象思维提炼出模型。在这个例子中，综合运用了抽象和简化思维提炼和简化了消费者和队列的对应关系，分别从队列任务的角度和消费者的角度去解决问题。
3. 再转化问题，逐渐扩大问题规模，用问题验证模型的准确性。在这个例子中，从简化后的模型，逐渐扩大范围到队列组、订阅组，由于有了第一步经过验证的测试用例，因此在扩大问题之后，对于模型的验证也是非常快的。

对于这么复杂的需求，测试用例的设计是确保逻辑正确的关键。如何在面对这么复杂的需求的情况下，还能做到业务逻辑bug-free，这就留待下一篇文章解答了。