Recently, in the background task application, when multiple machines consume the same task queue, it is necessary to introduce a task allocation mechanism to solve the problem. Since similar problems have been encountered before, I would like to sort out several possible ideas and discuss more reasonable and efficient solutions with you.
background
Suppose we have a cluster that works on a number of different tasks, and we need to allocate tasks so that each machine in the cluster is responsible for some of the tasks.
Generally speaking, there will be the following requirements:
- A task can only be executed once at most (in other words, assigned to one machine)
- The load on each machine in the cluster is balanced when the task is executed
In this scenario, how to design the task allocation scheme?
In order to facilitate the subsequent expansion, first restrict some expressions:
Source: Indicates the source of the taskCluster: Indicates the entire clusterTask: Used to represent abstract tasksWorker: Used to represent the specific unit (such as a physical machine) that actually performs the task
The relationship between the four can be expressed as follows:
Idea 1: Simple module allocation
The simplest, but very effective solution is to determine the number of machines N in advance before task assignment, number each task (or use its id directly), and number each machine instance that performs the task (0,1,2…). .
Use the following formula:
Worker = TaskId % Cluster.size()
Copy the codeIf the task is not identified by ID, the task can be assigned by random number. If the number of tasks is enough, the balance of assignment can be guaranteed, that is:
Worker = random.nextInt() % Cluster.size()
Copy the codeThe advantage of simple mold distribution is simple enough, although the effect of load balancing is relatively rough, but can quickly achieve the desired effect, in doing urgent tasks when the extension of the flow is more useful. However, in the long run, it is necessary to maintain the real-time update and push of the number of machines N, and when the number of machines changes, there may be temporary inconsistencies within the cluster. If the business is sensitive to this, further optimization is needed.
Idea 2: Distributed locking
In order to achieve the goal of “each Task can only be executed by one machine”, a distributed locking mechanism can be considered. When multiple workers consume tasks, only the first Worker who grabs the lock can execute the Task.
Theoretically, the Worker who grabs the lock every time is random, so the load balancing is also realized nearby. With mature middleware dependencies, it is not difficult to implement a distributed lock (with the concurrency control of a caching system) without considering the number of machines.
However, this scheme also has many defects. First, the process of scrambling for locks itself will consume Worker resources. In addition, it is impossible to predict which Worker can scramble for Task locks, so the load balance of the whole cluster cannot be guaranteed basically.
In my opinion, this scheme is only suitable for very simple, large number of tasks with very high frequency of execution (analogous to multi-threaded read/write caching).
Idea 3: Central route scheduling
If you want to achieve fine load balancing, the best way is to customize a set of task allocation rules according to the status of the cluster and the characteristics of the task itself, and then implement task scheduling through a central routing layer, that is:
- Source sends the task to the Router
- The Router makes decisions based on rules and dispatches tasks to a Worker
- (If the task needs to return results) The Router forwards the results returned by the corresponding Worker to the Source
A simple and feasible allocation rule is to calculate the load of Worker’s CPU and memory before scheduling, calculate a weight, and select the machine with the least pressure to run the task. Further, the task itself can be broken down to a finer degree based on its complexity.
The biggest problem of this scheme lies in the high cost of independently implementing a routing layer and the risk of single point of problem (if the routing layer fails, the whole task scheduling will be paralyzed).
Idea 4: Based on message queues
This is analogous to the message queue-based distributed database solution we saw earlier. With a trusted Broker, we can easily build a producer-consumer model.
All tasks produced by the Source are put into the message queue, and downstream workers receive the Task and execute (consume) it. The advantage of this is that the blocking is reduced, and the retry policy can be configured according to the execution result of the Worker (if the execution fails, it can be put back into the queue again). However, relying on the Broker for task distribution alone does not solve our first two problems, so we also need:
-
A mechanism to prevent messages from being consumed repeatedly
Because the vast majority of the transmission of message queue Broker logic is “assurance news arrived at least once,” so it was very likely a Task by multiple workers access to the phenomenon, if want to make sure that “each Task is performed only once, so this time may need to introduce the above mentioned locking mechanism to prevent repeated consumption.
However, if you choose NSQ as the Broker, you do not have to worry about this. The feature of NSQ ensures that a message can only be consumed by one consumer in the same channel.
-
Task distribution
After the producer-consumer model is built, it is still difficult to answer the question “which Task should be run on which Worker”, which is the mechanism of Task distribution. In essence, it still depends on the randomness of consumers’ consumption actions. For more detailed regulation, there are roughly two schemes.
First, the mapping relationship is calculated according to the required rules before being put into the queue, and then the Task is marked. Finally, the Worker can set it to take effect only for tasks with specific marks, or make different topics according to the marks of tasks to distribute.
Instead, the calculation is carried out when the queue is taken out, so that the downstream may need to maintain a routing layer to do forwarding, feeling that the loss is not worth the gain.
For the most part, rely on the Broker’s own message distribution mechanism.
Idea 5: Flow back pressure
Refer to the concept of back pressure in responsive programming. The process of pushing tasks on the Source end is changed to pulling tasks on the Worker end, so as to achieve flow rate control and load balancing.
To put it simply, we need the Worker(or Cluster) to be able to estimate the number of tasks it can undertake next based on its own situation and feed it back to the Source, which then produces the Task and sends it to the Worker(or Cluster).
Imagine a feasible scheme where Source is regarded as Server and Worker as Client, thus forming a reverse C/S mode.
The behavior of the Worker side is to repeatedly repeat the cycle of “request Task -> Run Task -> Request Task”. Whenever the Worker evaluates that it is in the “idle” state, it sends a request to the Source side to get the Task and run it.
On the Source side, it is relatively simple to implement an interface that returns a Task every time a request comes in and marks that Task as consumed.
Although this idea can better ensure that the load of each Worker machine is in a controllable range, it still has several problems.
The first problem is the flow rate, because the consumption speed of the whole task queue is completely regulated by the Worker in this mode, while the status of the task queue (how many tasks need to be handled and which tasks are urgent..) It is not visible to the Worker, so it may lead to the accumulation of tasks on the Source side.
The second problem is the delay of Task scheduling. Because the Source end is completely unable to predict when the next Worker’s request will come, it is impossible to guarantee the execution time of any submitted Task. This isn’t a huge problem for background tasks, but it can be fatal for foreground tasks.
To solve the above two problems, a reasonable Task allocation mechanism needs to be introduced on the Source side, and in extreme cases, the Source side may need to be able to force the distribution of tasks.