复杂需求的终结者:简化和抽象思维
需求介绍
在 这篇文章 中讨论了在一批队列里如何对任务更好地排序。为方便说明,下面再把类定义和队列规则描述一下:
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队列中的任务按队列优先级进行排序,选择优先级最高的队列
- 如果优先级最高的队列只有一个,则从该队列中选择排队时间最长的任务
- 如果优先级最高的队列有多个,则从这多个队列中选择排队时间最长的任务
现在将需求再扩大一点,假设有一批队列,每条队列中都有一批任务。不同的队列可以组成一个队列组,消费者可以订阅队列组。其数量关系如下:
用一张图来表现这个关系:
对于消费者自身来说,也有对应的状态。消费者初态为未就绪,当消费者改变自身状态为已就绪状态时,则可以被分配任务。消费完一个任务之后,消费者进入未就绪状态。关于消费者的状态转移图如下所示:
另外还要注意的是:
- 一个队列组可能同时被多个消费者订阅,那么在这个队列组中的任务,就有可能会对应多个消费者。此时,需要按照消费者的准备时间先后进行分配。
- 消费者可以选择接受任务或不接受任务,如果消费者不接受任务,则消费者回到未就绪状态,然后再将该任务分配给订阅了所属队列组的消费者。举个例子,比如任务T1 可以分配给消费者 C1和C2,如果将T1分配给C1时,C1没有接受,则任务T1将会继续分配给C2;如果C2接受了该任务则由C2处理,如果C2不接受该任务,则任务T1继续留在队列中,等待下一次重试。
现在需要将队列中的任务,按照消费者和队列组的订阅关系,以及上述的消费规则,分配给对应的消费者。需要解决这两个问题:
- 当每个队列都有一批任务需要被分配时,如何设计分配策略以满足上述要求?
- 需求具有一定的复杂度,如何保证实现逻辑的正确性?
当然,系统的可用性也需要考虑,但不是想要说明的重点,先暂时忽略。对于这样的需求,你会如何设计呢?
下面会先讲述如何实现,对于如何保证逻辑实现正确性也相当重要,但暂且按下不表,会在另一篇文章解决。
利用简化思维拆解需求
消费者、队列组和队列,都是多对多的关系,要处理起来的确不太容易。对于这样复杂的关系,我们可以对需求进行简化。
既然消费者对应的是队列组,那么队列组里有多少条队列,对于消费者来说并不知道。队列组里可以是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);
}
当我们做出这样的简化之后,事情就变得好办了。我们可以先针对这种简化的情况,设计测试用例,先确保在特例下的正确性,然后再将范围扩大到队列组,最后确保整个需求的正确性。
利用抽象思维实现需求
上面对队列组的情况做了简化,似乎一切都挺顺利。但是当引入队列组时,情况就有所不同。比如:
- 只有一条队列时,我只需要考虑这条队列的队头元素就可以了。但是,当消费者面对的是队列组时,这个队列组还有“队头”任务吗?
- 不同的消费者可能会订阅多个队列组,且订阅的队列组可能会相同,也就是说,在跨队列组的情况下,如果沿用上面的简化方案,那要怎么找到“队头” 任务呢?
在实际需求开发的时候,我一时之间也没有很好的思路。以终为始,从最后想要的结构来反推,我们期望最终得到的结构是一个CandidateTask,但是任务只能取一个。既然原来的队列变成了可能存在多个队列的队列组,那么将一个队列组看成是一个队列呢?这样每次分配时,只需要选取在这个队列组范围内的队头任务就可以了,是不是这样就可以和简化模型贴合了?
看上去很美好,但实际上这样做还会有问题。同一个消费者可能会订阅多个队列组,当这多个队列组都选出了一个队头任务时,这些队头任务就要去匹配对应的消费者了。考虑这样一个场景:
当消费者订阅的队列组存在交叉,每个队列组都选出一个“队头”任务时,得到的结果是:
这样的结果会有几个问题:
- 队头任务之间不得不进行一次排序。假设在队列组选出的任务优先级上,QueueGroup1-Task1 > QueueGroup3-Task1 > QueueGroup2-Task1。按消费者的准备时间看,Consumer1 比 Consumer2 早准备。那么,对于任务QueueGroup1-Task1 则会优先分配给Consumer1处理。然后QueueGroup2-Task1发现Consumer1已经在处理任务了,那么就转给Consumer2处理。这样优先级较高的QueueGroup3-Task1 反而没被处理,这与需求不符。
- 每次都取队列组中的队头,但不一定每次都是在队头的任务会被优先处理。如图所示,假设在
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);
}
至此,整个核心逻辑可以满足需求了。
总结
从整个流程的分析和推导,我们可以看到简化、问题转化、抽象思维在需求实现上的作用。总结起来有几个点:
- 先简化问题,用特例降低问题复杂度,然后用测试确保逻辑的正确性。在这个例子中,就先简化了队列组的概念,保证在特例的情况下逻辑的正确性。
- 对简化后的问题,用抽象思维提炼出模型。在这个例子中,综合运用了抽象和简化思维提炼和简化了消费者和队列的对应关系,分别从队列任务的角度和消费者的角度去解决问题。
- 再转化问题,逐渐扩大问题规模,用问题验证模型的准确性。在这个例子中,从简化后的模型,逐渐扩大范围到队列组、订阅组,由于有了第一步经过验证的测试用例,因此在扩大问题之后,对于模型的验证也是非常快的。
对于这么复杂的需求,测试用例的设计是确保逻辑正确的关键。如何在面对这么复杂的需求的情况下,还能做到业务逻辑bug-free,这就留待下一篇文章解答了。
转载自:https://juejin.cn/post/7234718074983727162