VNSWRR 算法浅解
Mathematics

前言

　　最近偶然在公司内网看到一篇文章「负载均衡算法vnswrr改进——从指定位置生成调度序列」。正好 Shaun 一直觉得调度类算法很有意思，就认真看了下，顺便写下自己的一些理解。

预备篇

　　通俗来讲负载均衡解决的是「在避免机器过载的前提下，多个请求如何分发到多台机器上」的问题，本质上是一个分布式任务调度的问题，在机器性能相同的情况下，最简单的策略就是轮询，多个机器依次轮流处理请求。Nginx 官方的 SWRR 算法解决的是「在机器性能不同的情况下，如何使请求分布更均匀，更平滑，避免短时间大量请求造成局部热点」的问题。

SWRR篇

　　在 SWRR 算法中，有两个权重，一个是初始实际权重（effective weight， ew），一个是算法迭代过程中的当前权重（current weight，cw），在负载均衡过程中，每次请求分发都选择当前权重最大的机器，同时更新每台机器的当前权重，当前权重更新策略如下：

  1. 若设定 n 台机器各自的初始权重为 \((ew_1,ew_2,...,ew_n)\)，同时 \(ew_1 \le ew_2 \le ... \le ew_n\) ，且 \(W_{total}=\sum_{i=1}^n ew_i\) ；

  2. 第一个请求来时，n 台机器各自的当前权重 \(cw_i=ew_i,　1 \le i \le n\) ，由于此时 \(cw_{max}=\max(cw_i)=cw_n\) ，则请求分发给第 n 台机器处理，同时更新机器各自的当前权重 \(cw_1=cw_1+ew_1, cw_2=cw_2+ew_2,...,cw_{n-1}=cw_{n-1}+ew_{n-1},cw_n=cw_n+ew_n-W_{total}\)，记为 \((2*ew_1,2*ew_2,...,2*ew_{n-1},2*ew_n-W_{total})\) ；

  3. 第二个请求来时，此时 n 台机器的各自权重为 \((2*ew_1,2*ew_2,...,2*ew_{n-1},2*ew_n-W_{total})\) ，选取权重值对应的机器进行处理，假设为第 n-1 台，则更新后权重为 \((3*ew_1,3*ew_2,...,3*ew_{n-1}-W_{total},3*ew_n-W_{total})\) ；

  4. 第 \(W_{total}\) 个请求来时，此时 n 台机器的各自权重应该为 \[ (W_{total}*ew_1-m_1*W_{total},W_{total}*ew_2-m_2*W_{total},...,W_{total}*ew_{n-1}-m_{n-1}*W_{total},W_{total}*ew_n-m_n*W_{total}) \\ \text{s.t.} \quad \sum_{i=1}^n m_i=W_{total}-1 \\ \quad 0 <= m_i <= ew_i \] 由于每次调度都是权重最大值减权重和，重新分配权重后权重和无变化，所以理论上此时除第 k 台机器外，每台机器的权重都为 0，第 k 台机器的权重为 \(W_{total}\) ，所以这次调度处理之后，每台机器的权重又会重新回到初始权重。

VNSWRR 篇

　　VNSWRR 算法是阿里针对 Nginx 官方的 SWRR 算法实际运行中对于部分场景下（瞬时流量大，权重更新等）均衡效果不太理想的改进算法，其最大的改进点在于预生成调度序列，以空间换时间减少调度时间，同时在权重更新后随机选取调度序列的起点，使初次请求就调度在不同的机器上，减少高权重机器的局部热点问题。具体流程如下：

  1. 首先使用 SWRR 算法生成前 n 个调度序列；
  2. 再随机选取一个位置作为调度起点，后续的请求依次从调度序列中选取；
  3. 若调度序列用完，则继续用 SWRR 算法生成后 n 个调度序列；
  4. 如此循环，直到调度序列的长度为 \(W_{total}\)，即一个周期内的全部调度序列，用完后，从头开始调度即可；
  5. 若有权重更新，则从 1 开始重新生成调度序列；

正文

　　从上面的逻辑中，可看出 SWRR 算法调度序列是以 \(W_{total}\) 为周期的一个循环序列，只需要知道一个周期内的调度序列，就可以推算出后续的调度机器（除非权重有变更或者有机器增删）。计算一个周期内的调度序列也比较简单，取当前调度权重中最大值对应机器，同时更新每台机器的当前权重，作为下次调度的权重，简而言之，就是从上次调度结果推出下次调度结果，是一个递推式。那有没有办法不从上次结果推下次结果，直接计算当前的调度结果，简化 VNSWRR 的第一步每次都从头开始预生成前 n 个调度序列，直接从任意位置开始生成调度序列，内网中这篇文章就给出了一个看似“可行的”解决方案，直接计算第 q 个请求的调度结果，具体方案如下：

在 SWRR 算法中，第 q 个请求时，全部机器的当前权重序列应该为 \[ (q*ew_1-m_1*W_{total},q*ew_2-m_2*W_{total},...,q*ew_{n-1}-m_{n-1}*W_{total},q*ew_n-m_n*W_{total}) \\ \text{s.t.} \quad \sum_{i=1}^n m_i=q-1 \\ \quad 0 <= m_i <= ew_i \] 即权重序列中共减去了 \(q-1\) 个 \(W_{total}\) ，平均上 \(m_i=ew_i/W_{total}*(q-1)\)，区分 \(m_i\) 的整数部分 \(mz_i\) 和小数部分 \(mx_i\)，\(\sum_{i=1}^n m z_i\) 代表减去的 \(W_{total}\) 个数，计算差值 \(d=q-1-\sum_{i=1}^n mz_i\)，即还剩 d 个 \(W_{total}\) 待减，对小数部分 \(mx_i\) 从大到小排序，取前 d 个对应的机器再减 \(W_{total}\)，即可得到第 q 个请求时的当前权重序列，取最大权重对应的机器即为调度结果，后续调度结果可通过递推式得出。

　　初次看到这个方案的时候，就想动手实现一下，因为思路也比较清晰简单，实现完之后，简单测试一下，也确实没啥问题，后面再深度测试了一下，就发现该方案确实有点小小的问题，在大部分情况下，该方案确实能得到很正确的结果，但还是存在一些错误结果，就因为有少量错误结果，所以该方案不要在生产环境下应用。该方案错在了将 \(q*ew_i\) 看成最后一个整体进行处理排序，忽略了分步执行结果，导致小部分场景下的错误排序结果，进而生成错误调度权重，调度错误。

　　现在再回到初始问题「如何生成 SWRR 算法中指定轮次的调度结果？」，抽象来看，该问题是个数学问题「如何从数列的递推式计算数列求通项公式」， 但 SWRR 的递推式相对复杂，中间还有取最大值这个不稳定变量，实际很难得到通项公式，直接计算指定调度解果，Shaun 问了 ChatGPT，也自己想了很久，搜了很久，但都没有答案，内网中的这个方案算是最接近的一个答案。

后记

　　在内网中看到这个方案的思路很有意思，将整数和小数部分拆开，再单独对小数部分排序，所以就自己测试了一下，顺便学习了下负载均衡 SWRR 算法，虽然问题依旧还在，但总归是有点收获。

附录

　　附代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
import random


def ouput_schedule(rs_arr, schedule_num):
    all_rs_weight_str = ";\t".join(["rs:%s,cw:%s" % (rs["rs_name"], rs["cw"]) for rs in rs_arr])
    schedule_rs = max(rs_arr, key=lambda x:x["cw"])
    print("%s:\t%s\t===>\trs:%s,cw:%s" % (schedule_num, all_rs_weight_str, schedule_rs["rs_name"], schedule_rs["cw"]))

    return schedule_rs

def swrr(rs_arr, weight_total):
    schedule_rs = rs_arr[0]
    max_weight = schedule_rs["cw"]
    for rs in rs_arr:
        if rs["cw"] > max_weight:
            schedule_rs = rs
            max_weight = rs["cw"]

        rs["cw"] += rs["ew"]
    
    schedule_rs["cw"] -= weight_total

    return schedule_rs

def swrr_test():
    real_servers = [{"rs_name": chr(i+64), "ew": i, "cw": i} for i in range(1, 6)]
    weight_total = sum([rs["ew"] for rs in real_servers])
    schedule_count = weight_total
    swrr_seq = []
    for i in range(1, schedule_count+1):
        ouput_schedule(real_servers, i)
        schedule_rs = swrr(real_servers, weight_total)

        swrr_seq.append(schedule_rs["rs_name"])
    
    print(swrr_seq)

# swrr_test()
# print("---------")

def swrr_n(rs_arr, weight_total, schedule_num):
    ms = [(rs["ew"] / float(weight_total)) * (schedule_num-1) for rs in rs_arr]
    mzs = [int(m) for m in ms]
    mxs = [(i, m-int(m)) for i, m in enumerate(ms)]
    mxs = sorted(mxs, key=lambda x:x[1], reverse=True)
    for i, rs in enumerate(rs_arr):
        rs["cw"] = schedule_num * rs["ew"]
        rs["cw"] -= mzs[i] * weight_total

    d = (schedule_num-1) - sum(mzs)
    for i in range(d):
        rs_arr[mxs[i][0]]["cw"] -= weight_total

    schedule_rs = ouput_schedule(rs_arr, schedule_num)

    return schedule_rs

def swrr_n_test():
    real_servers = [{"rs_name": chr(i+64), "ew": i, "cw": i} for i in range(1, 6)]
    weight_total = sum([rs["ew"] for rs in real_servers])

    schedule_rs_seq = []
    for i in range(1, weight_total+1):
        schedule_rs = swrr_n(real_servers, weight_total, i)

        schedule_rs_seq.append(schedule_rs["rs_name"])
    # swrr_n(real_servers, weight_total, 9) # err schedule rs
    print(schedule_rs_seq)

# swrr_n_test()

def vnswrr_preschedule(rs_arr, weight_total, N, schedule_rs_seq):
    for i in range(1, N+1):
        schedule_rs = swrr(rs_arr, weight_total)
        if len(schedule_rs_seq) >= weight_total:
            break
        schedule_rs_seq.append(schedule_rs)

def vnswrr(rs_arr, rs_count, weight_total, prev_schedule_idx, schedule_rs_seq):
    N = min(rs_count, weight_total)
    
    schedule_idx = prev_schedule_idx + 1
    schedule_idx %= weight_total
    
    if schedule_idx >= len(schedule_rs_seq)-1:
        vnswrr_preschedule(rs_arr, weight_total, N, schedule_rs_seq)
    
    return schedule_idx

def vnswrr_test():
    all_schedule_rs_seq = []
    real_servers = [{"rs_name": chr(i+64), "ew": i, "cw": i} for i in range(1, 6)]
    rs_count = len(real_servers)
    weight_total = sum([rs["ew"] for rs in real_servers])

    N = min(rs_count, weight_total)
    schedule_rs_seq = []
    # 预生成调度序列
    vnswrr_preschedule(real_servers, weight_total, N, schedule_rs_seq)
    # 随机取调度结果
    prev_schedule_idx = random.randint(0, N-1)-1

    for i in range(1, 2*weight_total+1):
        schedule_idx = vnswrr(real_servers, rs_count, weight_total, prev_schedule_idx, schedule_rs_seq)
        all_schedule_rs_seq.append(schedule_rs_seq[schedule_idx]["rs_name"])
        prev_schedule_idx = schedule_idx
    
    print([rs["rs_name"] for rs in schedule_rs_seq])
    print(all_schedule_rs_seq)

vnswrr_test()

参考资料

1、QPS 提升60%，揭秘阿里巴巴轻量级开源 Web 服务器 Tengine 负载均衡算法

2、Nginx SWRR 算法解读

本文标题： VNSWRR 算法浅解

文章作者： Shaun

发布时间： 2024年02月07日 - 22时31分

最后更新： 2024年10月15日 - 00时45分

原始链接： http://cniter.github.io/posts/619020f7.html

许可协议： "署名-非商业性使用-相同方式共享 4.0 国际" 转载请保留原文链接及作者。