基于MySQL 的抢占式存储引擎负载均衡简单实现

[hookokoko]

按照 #12 的方案所实现

[hookokoko]

补充下，关于这次提交实现的任务状态流转图

[flycash]

图比我画的好看 😄

[flycash]

尼玛，总有一种我会不会忽略什么并发场景的担忧=。=

[flycash]

我想到，在它放弃一个任务前，它要通知 Scheduler 停止调度。不然会引起并发问题

[hookokoko]

图比我画的好看 😄

谦虚的明佬 😀

[hookokoko]

尼玛，总有一种我会不会忽略什么并发场景的担忧=。=

下一步我计划考虑下如何写测试用例了，感觉这是个大活。明佬有并发场景测试最佳实践吗~

[flycash]

没有。并发这个东西，三分靠 review，三分靠测试，94分靠踩坑

[flycash]

记得更新最新的代码

[hookokoko]

记得更新最新的代码

👌 测试还没写完，今天摸鱼的时候先提一版

[hookokoko]

拆分了一个storage info表出来，专门记录storage的负载信息，这样就不用更新占有者负载的时候，对每一个task都更新一遍了

[Stone-afk]

mark

[hookokoko]

梳理了一下实现抢占式存储引擎的问题： 主要是针对大明提出方案，其实代码实现起来倒还好，就是测试的时候总会有一些问题，然后总有一种为了解决这一个问题又引入了很多其他的问题的感觉，导致代码越来越不可控。

先说下代码实现的逻辑： storage实现的核心就是三大块：

1. 寻找候选者，lookup()函数。这里就是遍历所有的task，如果task的占有者负载比当前的storage大，就更新候选者为当前storage。
2. 续约，refresh()函数。除了task的续约之外，还要配合进行task的丢弃，即如果task存在候选者，根据负载比较当前storage是否要放弃这个任务
3. 抢占，preempted()函数。对满足一些状态条件的task进行抢占，发送task的chan信号给scheduler执行

再说下现有的提交的问题：

1. 节点负载一致性的问题。目前每个节点在内存都会存有一个负载，同时在db中也会在storage_info表中存上storage的负载信息。很容易就会因为一些场景导致不一致，比如数据库本身更新失败，还有就是，s1在抢到了t1，更新内存之后，（在balance的场景下）s2又抢到t1同时更新到db成功，然后s1再更新db就出现不一致了。解决这种不一致，目前想到的方式： a. 可能就需要引入task锁或者让storage间能够进行通信，这些给系统增加了复杂性，代码实现起来感觉越来越不可控。 b. 另一种简单的办法，就是只存一份。将task的占有者、候选者放入task表中，查询负载的时候直接select count(*) where storage_id=xxx，这种如果是使用mysql innodb的话，性能还好。

2. 还有一个比较棘手的问题就是，task的storage很难处于一个稳定的状态。 a. 最开始也就是当前代码提交的实现，是直接基于占有者的负载进行比较决定是不是去更新候选者，这种就会导致先前很少负载的storage，经历过候选者替换之后，负载变的很大，分析如下： 假定这里有6个task（t1-t6），3个storage(s1-s3)，每个task后面的内容表示对应的占有者、候选者，初始时候选者都是空。 b. 为了解决上面的问题，很直观的一种方式，就是在比较的时候将stoage的候选者和占有者负载一起进行比较，并且如果storage节点抢占者负载+占有者负载大于等于每个节点的任务均值（6/3）不再进行候选者更新，但是仍然没有解决问题，分析如下： 还是假定这里有6个task（t1-t6），3个storage(s1-s3)，每个task后面的内容表示对应的占有者、候选者，初始时候选者都是空。 除此之外，即使这两种有问题的实现，还需要一个全局锁去保证storage在执行lookup的时候，不会被打断。

[hookokoko]

所以也想讨论下，我们是不是要继续沿着这个思路走下去，总感觉代码写起来会越来越不可控。可以借助raft这种一致性协议进行负载均衡，但是raft的“一致性”是保证每个节点内容一致，但是我们的场景需要的“一致性”是每个节点的负载一致，这还需要对raft进行更深入的调研。 或者直接换一种主从模式，通过一个主节点对task的任务进行分发，这样能解决一些并发问题和不均衡的问题了。

[flycash]

就 2 来说，这里候选者负载是要实时更新的。也就是说，每次它更新一条数据，候选者的负载都要预先加上去。比如说在 s2 lookup 的时候，它在将自己标记位候选者之后，它的负载就不能是 0 了，而应该是 1 了（实际负载和预期负载的问题），那么 s3 的任务 s2 就不会去碰。当然这种策略对时序还是有要求的。比如说我预期我能抢占，但是到下一个 lookup 的时候，我还是没抢到，那么我该从哪里开始计算我的预期负载呢？

[flycash]

我考虑一下这个问题，确实是有点复杂了。

[hookokoko]

就 2 来说，这里候选者负载是要实时更新的。也就是说，每次它更新一条数据，候选者的负载都要预先加上去。比如说在 s2 lookup 的时候，它在将自己标记位候选者之后，它的负载就不能是 0 了，而应该是 1 了（实际负载和预期负载的问题），那么 s3 的任务 s2 就不会去碰。当然这种策略对时序还是有要求的。比如说我预期我能抢占，但是到下一个 lookup 的时候，我还是没抢到，那么我该从哪里开始计算我的预期负载呢？

在lookup的时候没有用到预期负载，仅仅是比较（当前storage的占有者负载+候选者负载）和 这个task的占有者的占有者负载+候选者负载。然后负载的获取方式像下面这样：

我在task_info表中加了两个字段，占有者storage id，候选者storage id

    occupier_id       bigint null comment '占有该任务的storage',
    candidate_id      bigint null comment '该任务的候选storage',

在进行lookup的时候会判断是不是需要更新candidate_id为当前storage id。

当想知道这个candidate_id的候选者负载的时，就通过这种方式 select count(*) from task_info where storage_id=xxx 获取。 之所以这样就是担心Storage struct内存中存的负载和db中的不一致，索性就直接只在db中查了

[flycash]

等我约一个会议来讨论一下。这个我觉得稍微有点复杂

On Wed, Mar 22, 2023 at 11:28 AM hookokoko @.***> wrote:

就 2 来说，这里候选者负载是要实时更新的。也就是说，每次它更新一条数据，候选者的负载都要预先加上去。比如说在 s2 lookup 的时候，它在将自己标记位候选者之后，它的负载就不能是 0 了，而应该是 1 了（实际负载和预期负载的问题），那么 s3 的任务 s2 就不会去碰。当然这种策略对时序还是有要求的。比如说我预期我能抢占，但是到下一个 lookup 的时候，我还是没抢到，那么我该从哪里开始计算我的预期负载呢？

我在task_info表中加了两个字段，占有者storage id，候选者storage id

occupier_id       bigint null comment '占有该任务的storage',
candidate_id      bigint null comment '该任务的候选storage',

在进行lookup的时候会判断是不是需要更新candidate_id为当前storage id。

当想知道这个candidate_id的候选者负载的时，就通过这种方式 select count(*) from task_info where storage_id=xxx 获取。 之所以这样就是担心Storage struct内存中存的负载和db中的不一致，索性就直接只在db中查了

— Reply to this email directly, view it on GitHub https://github.com/ecodeclub/ecron/pull/13#issuecomment-1478872430, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACLWZ7QMLJQUF6RD6ATU4QTW5JWWXANCNFSM6AAAAAAVS3CP3Q . You are receiving this because you commented.Message ID: @.***>

[hookokoko]

等我约一个会议来讨论一下。这个我觉得稍微有点复杂 … On Wed, Mar 22, 2023 at 11:28 AM hookokoko @.> wrote: 就 2 来说，这里候选者负载是要实时更新的。也就是说，每次它更新一条数据，候选者的负载都要预先加上去。比如说在 s2 lookup 的时候，它在将自己标记位候选者之后，它的负载就不能是 0 了，而应该是 1 了（实际负载和预期负载的问题），那么 s3 的任务 s2 就不会去碰。当然这种策略对时序还是有要求的。比如说我预期我能抢占，但是到下一个 lookup 的时候，我还是没抢到，那么我该从哪里开始计算我的预期负载呢？ 我在task_info表中加了两个字段，占有者storage id，候选者storage id occupier_id bigint null comment '占有该任务的storage', candidate_id bigint null comment '该任务的候选storage', 在进行lookup的时候会判断是不是需要更新candidate_id为当前storage id。 当想知道这个candidate_id的候选者负载的时，就通过这种方式 select count() from task_info where storage_id=xxx 获取。 之所以这样就是担心Storage struct内存中存的负载和db中的不一致，索性就直接只在db中查了 — Reply to this email directly, view it on GitHub <#13 (comment)>, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACLWZ7QMLJQUF6RD6ATU4QTW5JWWXANCNFSM6AAAAAAVS3CP3Q . You are receiving this because you commented.Message ID: **@.***>

👌~

[flycash]

我想到一个比较简单的处理方式，就是控制一个循环内能够抢占的任务数量，做成一个参数。比如说，默认是 3 个。那么每一个循环，它就只会将三个任务标记为自己要抢占，而且它只会标记那些任务数量比自己多 3 * 2 的调度者的任务。这种方案足够的简单。

那么缺陷就是，如果一个调度节点真有几十万个任务，那么 3 个任务 3 个任务抢，要抢很久才能平衡。但是在这种情况下，用户应该将这个参数设置到几百或者几千。

[flycash]

另外就是如果 A 负载是 10，然后将自己标记为候选者，B 负载是 8，那么它可以覆盖了这个候选者。这样可以确保大趋势是负载轻的先偷掉别的任务。

[hookokoko]

而且它只会标记那些任务数量比自己多 3 * 2 的调度者的任务。这种方案足够的简单

这里面说的2，是指节点数量吗？

另外就是如果 A 负载是 10，然后将自己标记为候选者，B 负载是 8，那么它可以覆盖了这个候选者。这样可以确保大趋势是负载轻的先偷掉别的任务。

感觉这里还是会有任务不稳定的问题，假如在某个任务中，B在覆盖这个候选者之前，A已经更新了成为了占有者，然后可能得一种情况此时B又满足成为候选者的条件，又会把他更新成B（先更新成候选者，再成占有者）

[flycash]

这里面说的2，是指节点数量吗？

不是，是两倍。比如说一个节点负载是 16，一个节点是 10，那么节点抢走 3 个之后，大家都是 13，这个 2 就是这么来的，一增一减而已。

感觉这里还是会有任务不稳定的问题

确实会有不稳定的可能，但是并不是很严重。我们所有的节点，循环间隔都是一样的。比如说一分钟。那么假如说我 00:13 把我标记为候选者，那么在 00:13-01:13 之间，负载较低的节点至少也会启动一次。

当且仅当两个节点的循环周期完全重合，才会不稳定。

[hookokoko]

这里面说的2，是指节点数量吗？

不是，是两倍。比如说一个节点负载是 16，一个节点是 10，那么节点抢走 3 个之后，大家都是 13，这个 2 就是这么来的，一增一减而已。

感觉这里还是会有任务不稳定的问题

确实会有不稳定的可能，但是并不是很严重。我们所有的节点，循环间隔都是一样的。比如说一分钟。那么假如说我 00:13 把我标记为候选者，那么在 00:13-01:13 之间，负载较低的节点至少也会启动一次。

当且仅当两个节点的循环周期完全重合，才会不稳定。

666，我想了下，感觉这样能解决之前的问题。实现的话就得靠在lookup的时候加一把大锁了。我先实现看看之后测试会不会发现新问题

[flycash]

Updates #12

我先合并进去。我自己来修改一下。这里面比较多坑，我本地 DEBUG 来确认一下。

[hookokoko]

Updates #12

我先合并进去。我自己来修改一下。这里面比较多坑，我本地 DEBUG 来确认一下。

ok~我已经记在小本本上了