基于MySQL 的抢占式存储引擎实现 任务3：负载均衡解决方案

[flycash]

场景

我们在 #10 和 #11 里面都提到了，抢占式的 MySQL 设计最大的问题就是负载均衡不太好搞。

• 在灰度发布的时候，我们通常会考虑先发布少量机器，这少量机器在启动之后就会不断抢占任务，最终导致所有的任务被这些少量机器全部抢占掉；
• 当某一台机器下线的时候，它的任务会被其它机器抢占，但是问题在于我们的抢占都是轮询的，也就是最先触发轮询的那个机器会抢占掉全部，那么在这种场景下，某一台特定的机器就可能抢占了非常多的任务；
• 在一些特定的场景下，比如说监控中发现了某个节点负载非常高，那么这个时候需要立刻触发一下负载均衡。这个负载均衡可能是所有的节点完全重新分配任务，也可能就是该节点放弃一些任务，也可能是通知负载最低的几个节点来窃取一些任务。但是从 MySQL 的角度来说，只有放弃一些任务是比较容易实现的。剩余两个方案，都可能需要在主从模式下，由主节点来协调。对等结构的话，则是需要协商机制。这其实意味着我们需要暴露一些接口，能够允许用户触发任务重新分配，或者说重新抢占；

设计

最基本的思想是，在抢占任务的逻辑里面加上一条规则：如果一个节点的负载比另外一个节点的负载更加低，那么我们就可以允许该节点抢占掉另外一个节点的任务。那么我们可以预期经过几轮续约、抢占，最终在所有的节点上的负载比较均匀的。 那么我们要考虑的问题就是：

• 如何表达一个节点的负载
• 别的节点如何知道别的节点的负载，或者说知道调度了某个特定任务的节点的负载
• 如果避免抖动问题：假设说 A 节点的负载是 11，另外一个 B 节点的负载是 10，那么按照道理 B 节点就可以抢占，抢占之后 A 节点的负载变成 10，B 节点的负载变成 11。那么接下来 A 又会抢占，如此循环往复，这也就是所谓的抖动
• 一个节点怎么知道自己的任务被别人抢占了。如果一个节点的任务被人抢占了，那么它应该放弃调度这个任务。正在调度的则不受影响，只是在调度结束之后就会放弃这个任务

方案一

一种比较简单的做法是采用近似于协商的机制，假如说现在 A 节点已经抢占了任务1，B 节点上的负载更加轻，试图从 A 节点上抢占任务1，那么基本的思路就是：

• A 节点在抢占任务1的时候，往数据库写入（占有者负载=11）
• B 节点在定时扫描数据库，希望能够抢占一些任务的时候，发现 A 节点抢占任务1 留下的信息，它比较了一下自己的负载（9），于是在任务1 的信息里面增加（占有者负载=11，候选者负载 = 9）
• 等 A 节点下一次续约的时候，发现里面写了一个候选者负载 = 9，意思就是它知道有一个负载更低的节点想要抢占了，于是它就会放弃续约，并且主动释放掉这个任务，即把状态更新为可抢占状态
• B 节点下一次轮询数据库的时候发现了 A 节点已经放弃了任务，那么就会直接抢占，并且将信息更新为（占有者负载=（9+1），候选者负载=NULL）

这样下来，B 就成功凭借着负载比较低的优势，抢占了任务1，获得了调度任务1 的权力。

场景分析

在这种方案之下，还是有很多场景需要审慎思考，确保没有遗漏掉任何的东西。

B 节点标记之后 A 节点宕机了

B 节点在数据库中写入自己的信息，即表达了自己想要抢占的意向，这个时候 A 节点就宕机了。此时 A 无法主动发现有人想抢占任务 1 并且释放掉 任务1。

所以我们需要引入一个兜底的机制：如果一个任务很久没被抢占（或者说很久没有续约），那么剩下的节点就可以抢占它。

基于这条原则，节点 C（ B 也可以） 就会抢占掉它。

A 释放了任务 1 之后 B 节点宕机了

这种情况下， B 节点已经不可能继续抢占了，那么就需要考虑有别的节点之后会抢走任务 1.

节点 C（A 也可以） 轮询到了任务 1，发现虽然 B 节点想要抢占，但是一直没有抢占，于是节点 C 就会抢占掉它。

总结

我们只需要引入一个候选者-主动放弃机制，就可以保证任务朝着负载轻的节点转移。在这种形态下，演变成：

• 如果一个任务长期没有被人抢占、续约，那么任何节点都可以抢占；
• 一个节点在负载比较轻的情况下，可以尝试抢占别的节点的任务

那么核心就变成了要仔细设计任务的状态迁移，确保某些时刻，只有候选者可以抢占某个任务，而在其他时候任何节点都可以抢占任务。

[hookokoko]

不太好测试。

[hookokoko]

在写测试的时候发现一个问题，

A 节点在抢占任务1的时候，往数据库写入（占有者负载=11） B 节点在定时扫描数据库，希望能够抢占一些任务的时候，发现 A 节点抢占任务1 留下的信息，它比较了一下自己的负载（9），于是在任务1 的信息里面增加（占有者负载=11，候选者负载 = 9） 等 A 节点下一次续约的时候，发现里面写了一个候选者负载 = 9，意思就是它知道有一个负载更低的节点想要抢占了，于是它就会放弃续约，并且主动释放掉这个任务，即把状态更新为可抢占状态 B 节点下一次轮询数据库的时候发现了 A 节点已经放弃了任务，那么就会直接抢占，并且将信息更新为（占有者负载=（9+1），候选者负载=NULL）

也就是在这个方案里面，第一步如果A节点抢占任务1之后又抢占了任务2，那么抢占任务2的时候，需要连同任务1的占有者负载一起更新。如果任务数很多，这里会很影响性能。 如果考虑在A节点进行任务续约的时候更新，如果续约的时间间隔很久，那么其他节点在进行负载均衡的时候误差就会很大

[hookokoko]

是不是有一个中心化的地方管理所有节点的负载，相对更好一些

[flycash]

3.28 会议记录

https://www.bilibili.com/video/BV1Z24y177pR/

3.28 分布式任务调度 MySQL 实现 rebalance 设计.xlsx