最早截止时间优先调度法 Earliest Deadline First (EDF) scheduler
EDF in Wikipedia

EDF调度算法,是加权轮转调度算法(WRR,Weighted Round-Robin)的一种实现方式。
其核心思想是为每个条目截止时间赋值为当前时间加权重的倒数,然后采用最早截止时间优先的方式进行调度。
上述定义比较晦涩,我们可以透过后面例子,来说明为什么需要调度算法、如何实现调度算法、EDF调度算法的优势和劣势。

调度算法最主要的应用是操作系统调度进程,重要的调度理论基本上都是在此时涌现的。而后续反向代理对下游条目进行负载均衡,也可以参考一样的调度理论,只是进程的运行和切换转变为请求的接受与投递。

微服务架构下,请求方会获得一个服务节点列表,对服务节点的访问也可以利用同样一套负载均衡算法。它们大部分内容是可互通的,而访问负载均衡又会额外衍生出如一致性哈希等新的调度方式。

简例

假设有三个条目可供调度,分别是A、B、C,他们的权重分别是3:2:1。
设置权重的目标是相关条目被调度到的频次应该是与权重成正比。
对于这个权重来说,假设有6000次调度,那么我们希望A被调度3000次左右,B是2000次左右,C是1000次左右。

为了实现这种调度方式,我绘制了一个图,来解释这种方法:

图上有一个数轴,从0开始,到达3,以至无穷。
A条目的权重是3,我们以1/3为分隔不断重绘A,使得数轴的1/3,2/3,1,4/3等位置印上A;
B条目的权重是2,我们以1/2为分隔不断重绘B,使得数轴的1/2,1,3/2,2等位置印上B;
C条目的权重是1,我们以1为分隔不断重绘C,使得数轴的1,2,3等位置印上C;
最后,我们使用一个游标从左向右扫,扫描到的顺序就是调度的顺序,因此我们调度的顺序为A-B-A-C-B-A-A-B-A…
显而易见,调用的顺序含有一个循环节A-B-A-C-B-A,所以当调度足够多次数后,A、B、C的调度比值将会趋近于3:2:1

从数学上也很好证明。
假设有N个条目,其权重分别是a1,a2,a3…aN。
使用权重不停重绘,那么在一个周期内,第一个条目被重绘a1次,第二个条目被重绘a2次,第N个条目被重绘aN次。
因此,每个周期的调度都是按照目标比例的。

由于采用倒数进行重复,相当于对条目进行了穿插,这样可以减少了连续调度,降低了饥饿和过载的概率。
A-B-A-C-B-A-A-B-A-C-B-A的调度效果一般要比A-A-A-B-B-C-A-A-A-B-B-C更好。

WRR实现1

最简单的实现,是使用上述办法模拟一个周期,然后把周期存到数组中,用游标扫描即可。
以上述情形为例,首先我们定制一个数组 A-B-A-C-B-A,然后不断回环扫描这个数组,就可以完成加权轮转调度。
这种方法的每次调度的时间复杂度为O(1),空间复杂度为O(M*N),其中M是条目的平均权重,N是条目的数量。

分析一下这个实现的优劣:
优势:

  • 实现简单,容易理解
  • 单次调度的很快
  • 多线程共享游标index即可,协作方便
    劣势:
  • 空间复杂度高
  • 对条目修改很不友好

对于条目平均权重和条目总数比较小的情形下,这种实现其实已经比较优秀了。但是当平均权重和条目总量非常多的情形下,这种方式未免太耗内存。
在我的实际经验中,N可能超过5k,而M经常也在50左右,那么为了实现加权轮转,相当于我们需要耗费250K*Sizeof(Entry)的空间来做调度。即使Entry使用指针,64位系统下每个指针占据4字节,1M的内存就这么用出去了。
一个系统同时使用多个调度器,且条目数、条目权重还可能随着系统的运行而不断修改。
假设每隔十秒钟修改其中一个条目的权重,那么整个表需要重新构建,这对内存和CPU都是一个很大的考验。

WRR实现2

所有的条目信息必须要存储下来,因此对于存储空间来说,O(N)的内存消耗几乎不可避免,所以要想办法减少M带来的消耗。
由于 Weight > 0 且不可能等于 +♾,所以数轴上不会有单点出现多个同样的条目,所以从这个角度来看条目是可以复用的。
从这个思路出发,我们定义以下结构体。

1
2
3
4
5
6
7
// Entry is an item for load balance
type Entry struct {
deadline float64
index int64
Value string
Weight float64
}

初始时 entry.deadline = 1.0/entry.Weight
调度的时候,从中选择 deadline 最小的使用,并重新把这个条目放入优先队列中,并把 deadline 设置为 deadline + 1.0/entry.Weight,重新排布优先队列,如此往复。
复杂度分析:

  • 空间复杂度降低为 O(N)
  • 初始化的时间复杂度为 O(N),也就是堆排序的复杂度
  • 每次Pick的时间复杂度为 O(logN)
    具体实现可参考:
  • 简单Go实现
  • Envoy的C++实现

效果参考:

1
2
3
4
5
6
=== add entry A(3), B(2), C(1)
A C B A A B
=== add entry D(2)
A C B D A A B D
=== del entry B
A C D A A D

其他思考

index 的作用

当 deadline 一样的时候,index的作用才能显现出来。先加入的条目应该先出现,这样可以保证一定的稳定性。
否则,对于100个条目权重一模一样的调度来说,如果没有index的存在,那机会就变成随机调度了。
当weight不相同的时候,index也并非总是有效。
譬如 A 的 weight 为 3,C的 weight 为2 的时候,在第八轮,A有可能因deadline为精度问题比C早调度到。

存储优化

O(N)的内存消耗并非完全不可避免。
在 Service Mesh 场景下, control plane 对交给 proxy 的服务发现列表进行分片,可以使得每个 proxy 获得的条目数量减少。这种方式可以减少存储和Pick的时间消耗,同时还会有优化连接池等其他额外的优势。
关于服务发现分片的问题,未来会出一篇专门的文章详细解释。

起始随机Pick

edf.go#L106

1
2
3
4
5
6
// avoid instance flood pressure for the first entry
// start from a random one via pick random times
randomPick := rand.Intn(len(entries))
for i := 0; i < randomPick; i++ {
edf.Pick()
}

新建一个EDF的时候,开始进行了一定的随机,为什么要这么做呢?
假设有一个条目的权重较大,那么不进行随机,第一次调度选举一定会调度到这个条目。
想象这样一个场景,分布式环境下所有的调度器由于某种问题同时重启,那么第一瞬间,所有的调度器都会调度到第一个条目,这很有可能造成第一个条目被瞬间的压力打挂。