最早截止时间优先调度法 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的时候，开始进行了一定的随机，为什么要这么做呢？
假设有一个条目的权重较大，那么不进行随机，第一次调度选举一定会调度到这个条目。
想象这样一个场景，分布式环境下所有的调度器由于某种问题同时重启，那么第一瞬间，所有的调度器都会调度到第一个条目，这很有可能造成第一个条目被瞬间的压力打挂。