如何使用c#实现加权循环？

Question

如果我有一些服务器：192.168.100.1、192.168.100.2、192.168.100.3、192.168.100.4... 它们的权重是：5,1,2,3

我想实现负载均衡，但是如何使用C#实现加权循环？

Answer 1

假设您有服务器 a、b、c、d。并且您有相应的权重 5、1、2、3。您可以通过以下方式进行加权循环：

Random rand = new Random(seed);

void processRequest(Request r){

    // assume rand.next() returns a uniformly distributed integer >= 0
    int i = rand.next() % 11; // 11 is sum of weights

    if(i <= 4)      // process r with server a
    else if(i == 5) // process r with server b
    else if(i <= 7) // process r with server c
    else            // process r with server d
}

rand.next() % 11 返回[0, 10]（含）范围内的均匀分布整数。我们使用服务器 a 处理请求，获取五个可能的值 [0, 4]。我们使用服务器 b 处理请求，仅获取一个可能的值 5，依此类推。

请特别注意您使用的特定随机方法和种子值。

Answer 2

随机加权选择算法

// returns the index of the chosen one, note that the index starting with 0
static int randomWeightedSelect(List<int> colls) {
    int lucky = rand.Next(1, colls.Sum());
    for (int i = 0; i < colls.Count(); ++i) {
        lucky -= colls[i];
        if (lucky <= 0)
            return i;
    }
    // should never reach here
    return -1;
}

加权循环算法 https://dotnetfiddle.net/71Sft0

public class WRRScheduler
{
    // A list of node name/label -> weight
    List<Tuple<string, int>> nodes;
    int maxWeight;
    int step;

    int idx;
    int quantum;

    // for testing purpose
    public static void Main()
    {
        var colls = new List<Tuple<string, int>> {
            Tuple.Create("A", 5), Tuple.Create("B", 1),
            Tuple.Create("C", 7), Tuple.Create("D", 3)
        };
        var s = new WRRScheduler(colls);

        for (int i = 0; i < colls.Sum(e => e.Item2); ++i)
            Console.WriteLine("choose {0}", s.next());
    }

    public WRRScheduler(List<Tuple<string, int>> nodes) {
        this.nodes = nodes;

        this.maxWeight = nodes.Max(e => e.Item2);
        // use gcd as a optimization
        this.step = nodes.Select(e => e.Item2).Aggregate(gcd);

        this.idx = -1;
        this.quantum = 0;
    }

    string next() {
        while (true) {
            this.idx = (this.idx + 1) % this.nodes.Count;
            if (this.idx == 0) {
                // start a new round, decrement current quantum
                this.quantum -= this.step;
                if (this.quantum <= 0) {
                    this.quantum = this.maxWeight;
                }
            }

            // pick the node if its weight greater than current quantum
            if (this.nodes[this.idx].Item2 >= this.quantum) {
                return this.nodes[this.idx].Item1;
            }
        }
    }

    private static int gcd(int a, int b)
    {
        while (a != 0 && b != 0) {
            if (a > b)
                a %= b;
            else
                b %= a;
        }
        return a == 0 ? b : a;
    }
}