探寻多机任务分配机制

3,153 阅读7分钟

近期在后台任务应用上遇到多机消费同一个任务队列的场景,需要引入一定的任务分配机制解决,因为之前也遇到过类似的问题,在此整理一下几种可能的想法,也希望和大家交流讨论更合理、更高效的方案。

背景

假设我们有一个集群,用于处理一系列不同的任务,这时候我们需要对任务进行的一定的分配,使得集群中的每台机器都负责一部分任务。

一般来说会有如下几个要求:

  • 一个任务最多只能被执行一次(换言之,只能被分配到一台机器上)
  • 执行任务时集群中每台机器的负载能够保持平衡

在这种场景下,该如何设计任务的分配方案?

为了方便后续的展开,先约束一些表达:

  • Source: 用于表示任务的来源
  • Cluster: 用于表示整个集群
  • Task: 用于表示抽象的任务
  • Worker: 用于表示实际执行任务的具体单元(如物理机)

四者之间的关系可以用下图表示:

undefined

思路1:简单取模分配

最简单,但也是非常有效的方案,在进行任务分配前需要提前确定机器数量N,为每个任务进行编号(或直接使用其id),同时为每个执行任务的机器实例进行编号(0,1,2...)。

即使用下面的公式:

Worker = TaskId % Cluster.size()

如果任务没有id标识,那么可以通过随机数的方式来分配任务,在任务数量足够多的情况下,可以保证分配的均衡性,即:

Worker = random.nextInt() % Cluster.size()

简单取模分配的优点是足够简单,虽然负载均衡的效果比较粗糙,但可以很快达到想要的效果,在做紧急任务分机分流的时候比较有用。但从长期上看,需要维护机器数量N的实时更新和推送,并且在机器数量发生变动的时候,可能会出现集群内部的短暂不一致,如果业务对这个比较敏感,还需要进一步优化。

undefined

思路2:分布式锁控

为了达到“每个任务只被一台机器执行”的目标,可以考虑使用分布式锁机制,当有多个Worker去消费Task时,只有第一个争抢到锁的Worker才能够执行该Task。

理论上讲,每次抢到锁的Worker都是随机的,那么也就近似的实现了负载均衡;在有成熟中间件依赖的前提下,实现一个分布式锁也并不难(可以借助缓存系统的并发控制实现),并且不用考虑机器数量变化的问题。

undefined

但这个方案也有着很多的缺陷,首先争抢锁的过程本身就会消耗Worker的资源,另外由于无法预测究竟哪个Worker能够争抢到Task的锁,所以基本不能保证整个集群的负载均衡。

我个人认为这种方案只适合于内容非常简单、数量比较多,同时执行频率非常高的任务分发(类比多线程读写缓存的场景)。

思路3:中心路由调度

如果要做到比较精细的负载均衡,那么最好的方式就是根据集群的状态、以及任务本身的特性去量身定制一套任务分配的规则,然后通过一个中心的路由层来实现任务的调度,即:

  • Source将任务发送给Router
  • Router根据规则进行决策,并将Task调度到某台Worker
  • (如果任务需要返回结果)Router将对应Worker返回的结果转发给Source

undefined

一个简单可行的分配规则是在调度前,计算Worker的CPU、内存等负载,计算一个权重,选择压力最小的机器去运行任务;再进一步可以根据任务本身的复杂度做更精细的拆分。

该方案最大的问题在于,自主去实现一个路由层的成本比较高,另外有出现单点问题的风险(如果路由层挂了,整个任务调度就全部瘫痪了)。

思路4:基于消息队列

这个是类比之前看到的,基于消息队列的分布式数据库解决方案(原文),借助一个可靠的Broker,我们可以很容易构建出一个生产者-消费者模型。

undefined

Source产出的Task将全部投入消息队列中,下游的Worker接收Task,并执行(消费)。这样的好处是减少了阻塞,同时可以根据Worker的执行结果,配置重试策略(如果执行失败,再次放回到队列中)。但单单依赖Broker做任务分发的话,并不能解决我们开头的两个问题,因此还需要:

  1. 防止消息被重复消费的机制

    因为绝大多数的消息队列Broker的传输逻辑都是“保证消息至少被送达一次”,所以很有可能出现某个Task被多个Worker获取到的现象,如果要确保“每个任务都只被执行一次”,那么这时候可能需要引入一下上面提到的锁机制来防止重复消费。

    不过如果你选择NSQ作为Broker的话,就不用考虑这个问题。NSQ的特性保证了某个消息在同一个channel下,一定只能被一个消费者消费。

  2. 任务分发

    构建了生产者-消费者模型后,依然不好回答“哪个Task要在哪个Worker上运行”,也就是任务分发的机制,本质上还是依赖于消费者消费动作的随机性,如果要做更精细的调控,大致想一下有两种方案。

    一是在放入队列前就根据所需规则计算好映射关系,然后对Task做一下标记,最后Worker可以设置成只对含有特定标记的Task生效,或者根据Task的标记做不同Topic来分发。

    而是在取出队列的时候再进行计算,这样的话可能下游又需要维护一个路由层来做转发,感觉有些得不偿失。

    就大多数实际情况而言,依赖Broker本身的消息分发机制即可。

思路5:流式背压

参考响应式编程中的背压概念。把Source端推送(Push)任务的过程改为Worker端拉取(Pull)任务,“反客为主”,来实现流速控制和负载均衡。

undefined

简单的说,我们需要Worker(也可能是Cluster)能够根据自身的情况来预估自己接下来能够承接的任务量,并将其反馈给Source,然后Source生产Task并传送给Worker(或者Cluster)。

设想一个可行的方案,将Source视为Server,Worker视为Client,那么便形成了一种反向的C/S模式。

其中Worker端的行为是不断重复“请求获取Task -> 运行Task -> 请求获取Task”这个循环。每当Worker评估自身处于“空闲”状态时,就向Source端发送请求,来获取Task并运行。

Source端则相对比较简单,只需要实现一个接口,每当有请求过来时,返回一个Task,并标记该Task被消费即可。

这种思路虽然可以较好的保证每台Worker机器负载处于可控范围,但也存在几个问题。

首先是流速问题,因为整个任务队列的消费速度在此模式下完全由Worker本身调控,而任务队列的状态(还有多少任务需要处理、哪些任务比较紧急..)对Worker是不可见的,所以有可能导致任务在Source端的堆积。

其次是任务调度的延时问题,因为Source端完全无法预知下一个Worker的请求会在什么时候到来,所以对于任何一个被提交的Task,都无法保证其在什么时间被执行。对于后台任务而言这个问题倒不是很大,但对于前台任务就非常致命了。

要解决上面两个问题,需要在Source端引入一个合理的任务分配机制,在极端情况下可能还需要Source端能够强制进行Task的分发。