加权调度算法是一种很常见的调度算法. 如果只有两个后端, 调度的顺序很容易, 但是如果后端多于 2 个, 可能就不像想象中那样的顺序进行调度.
所以, 本文揭秘加权调度算法到底是怎么进行调度的.
1. 加权调度算法公式
首先, 给一个 LVS 官方手册给的加权调度算法公式:
假设有一组服务器 S = {S0, S1, ..., Sn-1},W(Si) 表示服务器 Si 的权值, 一个
指示变量 i 表示上一次选择的服务器, 指示变量 cw 表示当前调度的权值, max(S)
表示集合 S 中所有服务器的最大权值, gcd(S) 表示集合 S 中所有服务器权值的最大
公约数. 变量 i 初始化为 - 1,cw 初始化为零.
- while (true) {
- i = (i + 1) mod n;
- if (i == 0) {
- cw = cw - gcd(S);
- if (cw <= 0) {
- cw = max(S);
- if (cw == 0)
- return NULL;
- }
- }
- if (W(Si)>= cw)
- return Si;
- }
比如, A,B,C 三个后端的权重比是 2:3:4, 那么一个调度循环内的调度顺序是 CBCABCABC.
如果你不想从算法公式里找规律, 那么看下面.
2. 加权调度通俗规律
记住三个权重调度规则:
1. 先约分
2. 从最大权重开始调度
3. 同权重的后端, 从前向后调度
例如, 三台后端 A:B:C=2:3:4. 这里没法约分.
调度 C
调度之后, 比率变成 A:B:C=2:3:3,B 和 C 权重相同, 从 B 开始调度
调度 B
调度之后, 比率变成 A:B:C=2:2:3, 所以下次调度 C
调度 C
调度之后, 比率变成 A:B:C=2:2:2, 下次从 A 开始
当权重全部调整到相同值时, 就按照先后顺序不断循环, 直到调度完所有权重
调度 A, 调度之后, 比率变成 A:B:C=1:2:2
调度 B, 调度之后, 比率变成 A:B:C=1:1:2
调度 C, 调度之后, 比率变成 A:B:C=1:1:1
调度 A, 调度之后, 比率变成 A:B:C=0:1:1
调度 B, 调度之后, 比率变成 A:B:C=0:0:1
调度 C, 调度之后, 比率变成 A:B:C=0:0:0
进入下一个调度循环, 顺序是: CBCABCABC
所以, 每个调度循环的调度顺序为: CBCABCABC
调度过程如下图:
再给个示例, A:B:C:D=2:4:6:8
首先约分, 得到 A:B:C:D=1:2:3:4
调度 D
调度 C
调度 D
调度 B
调度 C
调度 D
调度 A
调度 B
调度 C
调度 D
所以, 调度顺序是 DCDBCDABCD.
来源: https://www.cnblogs.com/f-ck-need-u/p/9490629.html