轮询调度

轮询调度非常简单，就是每次选择下一个节点进行调度。比如{a, b, c}三个节点，第一次选择a， 第二次选择b，第三次选择c，接下来又从头开始。 这样的算法有一个问题，在负载均衡中，每台机器的性能是不一样的，对于16核的机器跟4核的机器， 使用一样的调度次数，这样对于16核的机器的负载就会很低。这时，就引出了基于权重的轮询算法。 基于权重的轮询调度是在基本的轮询调度上，给每个节点加上权重，这样对于权重大的节点， 其被调度的次数会更多。比如a, b, c三台机器的负载能力分别是4:2:1，则可以给它们分配的权限为4, 2, 1。 这样轮询完一次后，a被调用4次，b被调用2次，c被调用1次。 对于普通的基于权重的轮询算法，可能会产生以下的调度顺序{a, a, a, a, b, b, c}。 这样的调度顺序其实并不友好，它会一下子把大压力压到同一台机器上，这样会产生一个机器一下子很忙的情况。 于是乎，就有了平滑的基于权重的轮询算法。 所谓平滑就是调度不会集中压在同一台权重比较高的机器上。这样对所有机器都更加公平。 比如，对于{a:5, b:1, c:1}，产生{a, a, b, a, c, a, a}的调度序列就比{c, b, a, a, a, a, a} 更加平滑。

nginx平滑的基于权重轮询算法

nginx平滑的基于权重轮询算法其实很简单。算法原文 描述为：

Algorithm is as follows: on each peer selection we increase current_weight of each eligible peer by its weight, select peer with greatest current_weight and reduce its current_weight by total number of weight points distributed among peers.

算法执行2步，选择出1个当前节点。

1. 每个节点，用它们的当前值加上它们自己的权重。
2. 选择当前值最大的节点为选中节点，并把它的当前值减去所有节点的权重总和。

例如{a:5, b:1, c:1}三个节点。一开始我们初始化三个节点的当前值为{0, 0, 0}。 选择过程如下表：

我们可以发现，a, b, c选择的次数符合5:1:1，而且权重大的不会被连接选择。7轮选择后， 当前值又回到{0, 0, 0}，以上操作可以一直循环，一样符合平滑和基于权重。

一个go版本实现

type Node struct {
    Name    string
    Current int
    Weight  int
}

func SmoothWrr(nodes []*Node) (best *Node) {
    if len(nodes) == 0 {
        return
    }
    total := 0
    for _, node := range nodes {
        if node == nil {
            continue
        }
        total += node.Weight
        node.Current += node.Weight
        if best == nil || node.Current > best.Current {
            best = node
        }
    }
    if best == nil {
        return
    }
    best.Current -= total
    return
}

func example() {
    nodes := []*Node{
        &Node{"a", 0, 5},
        &Node{"b", 0, 1},
        &Node{"c", 0, 1},
    }

    for i := 0; i < 7; i++ {
        best := SmoothWrr(nodes)
        if best != nil {
            fmt.Println(best.Name)
        }
    }
}

• 本文作者：tenfy zhong
• 本文链接：https://tenfy.cn/2018/11/12/smooth-weighted-round-robin/

平滑的基于权重的轮询算法（Smooth Weighted Round Robin Algorithm）是一种用于选择节点并生成序列的算法，它根据节点的权重进行选择，并通过调整节点的当前权重来实现平滑的轮询。 算法的步骤如下：

1. 初始化：将每个节点的当前权重设置为0。
2. 选择节点：遍历所有节点，选择当前权重最大的节点作为选定节点。
3. 更新权重：将选定节点的当前权重减去节点权重的总和。
4. 增加权重：将所有节点的当前权重增加它们的权重值。
5. 重复步骤2至步骤4，直到生成所需的序列。

通过这个算法，节点的当前权重会根据其权重值进行调整，从而实现平滑的轮询。较大权重的节点会更频繁地被选择，但它们的当前权重也会相应减少，使得其他节点有机会被选中。 以下是一个示例，展示了如何使用平滑的基于权重的轮询算法生成序列： 假设有三个节点，它们的权重分别为5、1和1。初始状态下，它们的当前权重都为0。

1. 选择节点：根据当前权重选择节点。初始状态下，选定节点为节点A。
2. 更新权重：将节点A的当前权重减去节点权重的总和，即-2。
3. 增加权重：将所有节点的当前权重增加它们的权重值。节点A的当前权重变为3，节点B和节点C的当前权重都变为1。
4. 选择节点：根据当前权重选择节点。此时，节点A的当前权重最大，因此选定节点为节点A。
5. 更新权重：将节点A的当前权重减去节点权重的总和，即-4。
6. 增加权重：将所有节点的当前权重增加它们的权重值。节点A的当前权重变为1，节点B和节点C的当前权重都变为2。
7. 重复步骤4至步骤6，直到生成所需的序列。

通过这个算法，最终生成的序列为 {A, A, B, A, C, A, A}。 这种算法可以确保节点按照其权重进行平滑的轮询，并且在节点故障时能够保持权重的减少。它在负载均衡和其他需要根据权重选择节点的场景中被广泛使用。

平滑的基于权重的轮询算法是一种在网络负载均衡中广泛使用的调度算法。它的主要思想是根据服务器的实际处理能力（即权重）来分配任务，而不是简单地按照顺序或随机的方式进行分配。

具体来说，该算法首先计算出每个服务器的权重值，这个权重值可以反映服务器的处理能力，例如CPU利用率、内存使用率等。然后，算法会为每个服务器分配一个虚拟队列，这个队列的长度与服务器的权重成正比。在实际分配任务时，算法会选择虚拟队列最长的服务器来处理下一个任务。

这样做的好处是可以确保处理能力强的服务器得到更多的任务，而处理能力弱的服务器则只处理较少的任务，从而提高了整体的系统效率。

举个例子，假设我们有三台服务器，它们的权重分别为1、2和3。那么，我们可以为这三台服务器分别分配长度为1、2和3的虚拟队列。当有一个新的任务需要处理时，我们会选择虚拟队列最长的服务器（即权重为3的服务器）来处理这个任务。然后，我们会将这个服务器的虚拟队列长度减一，并重新计算各个服务器的虚拟队列长度。这样，我们就实现了基于权重的轮询算法。