IPVS调度算法之WRR

WRR（Weighted Round-Robin），即带权重的轮询算法。

调度器注册

WRR调度器的定义结构为ip_vs_wrr_scheduler，使用函数register_ip_vs_scheduler注册到IPVS的调度器系统中。

static struct ip_vs_scheduler ip_vs_wrr_scheduler = {
    .name =                 "wrr",
    .refcnt =               ATOMIC_INIT(0),
    .module =               THIS_MODULE,
    .n_list =               LIST_HEAD_INIT(ip_vs_wrr_scheduler.n_list),
    .init_service =         ip_vs_wrr_init_svc,
    .done_service =         ip_vs_wrr_done_svc,
    .add_dest =             ip_vs_wrr_dest_changed,
    .del_dest =             ip_vs_wrr_dest_changed,
    .upd_dest =             ip_vs_wrr_dest_changed,
    .schedule =             ip_vs_wrr_schedule,
};

static int __init ip_vs_wrr_init(void)
{
    return register_ip_vs_scheduler(&ip_vs_wrr_scheduler) ;
}

虚拟服务初始化

如下命令，在添加虚拟服务时，指定使用WRR调度器：

# ipvsadm -A -t 207.175.44.110:80 -s wrr

内核在虚拟服务（ip_vs_bind_scheduler函数）绑定调度器时，调用调度器的init_service函数指针。对于WRR调度器，即以下的ip_vs_wrr_init_svc函数。在此函数中，分配一个ip_vs_wrr_mark结构作为虚拟服务的调度私有数据（sched_data）。

static int ip_vs_wrr_init_svc(struct ip_vs_service *svc)
{
    struct ip_vs_wrr_mark *mark;

    /* Allocate the mark variable for WRR scheduling
     */
    mark = kmalloc(sizeof(struct ip_vs_wrr_mark), GFP_KERNEL);
    if (mark == NULL)
        return -ENOMEM;

    mark->cl = list_entry(&svc->destinations, struct ip_vs_dest, n_list);
    mark->di = ip_vs_wrr_gcd_weight(svc);
    mark->mw = ip_vs_wrr_max_weight(svc) - (mark->di - 1);
    mark->cw = mark->mw;
    svc->sched_data = mark;

    return 0;
}

WRR的私有调度数据结构为ip_vs_wrr_mark，其成员cl表示当前所选的真实服务器。cw、mw和di分别为当前权重（Current Weight）、最大权重（Maximum Weight）和递减量级（greatest common Divisor）。

struct ip_vs_wrr_mark {
    struct ip_vs_dest *cl;  /* current dest or head */
    int cw;                 /* current weight */
    int mw;                 /* maximum weight */
    int di;                 /* decreasing interval */
    struct rcu_head         rcu_head;
};

递减量级di的初始化由函数ip_vs_wrr_gcd_weight完成。通过计算虚拟服务关联的所有真实服务器的权重值的最大公约数得到（greatest common Divisor）。

static int ip_vs_wrr_gcd_weight(struct ip_vs_service *svc)
{
    struct ip_vs_dest *dest;
    int weight;
    int g = 0;

    list_for_each_entry(dest, &svc->destinations, n_list) {
        weight = atomic_read(&dest->weight);
        if (weight > 0) {
            if (g > 0)
                g = gcd(weight, g);
            else
                g = weight;
        }
    }
    return g ? g : 1;
}

最大权重（mw值）的计算由函数ip_vs_wrr_max_weight完成。其遍历虚拟服务所关联的真实服务器链表，找到最大的权重值。

static int ip_vs_wrr_max_weight(struct ip_vs_service *svc)
{
    struct ip_vs_dest *dest;
    int new_weight, weight = 0;

    list_for_each_entry(dest, &svc->destinations, n_list) {
        new_weight = atomic_read(&dest->weight);
        if (new_weight > weight)
            weight = new_weight;
    }
    return weight;
}

最后，在初始情况下cw值等于最大权重值mw。

在删除虚拟服务或者修改虚拟服务所使用的调度器时，内核需在函数ip_vs_unbind_scheduler中解绑调度器，此时如果调度器实现了done_service回调指针函数，将在此函数中被调用。对于WRR调度器，为以下函数：

static void ip_vs_wrr_done_svc(struct ip_vs_service *svc)
{
    struct ip_vs_wrr_mark *mark = svc->sched_data;
    kfree_rcu(mark, rcu_head);
}

其释放在初始函数ip_vs_wrr_init_svc中分配的ip_vs_wrr_mark结构。

真实服务器操作

内核在处理添加真实服务器（__ip_vs_update_dest）操作时，将调用虚拟服务绑定的调度器的add_dest回调函数指针，如果是编辑真实服务器，将调用upd_dest函数指针。对于WRR算法，这两个函数指针都是以下函数：

static int ip_vs_wrr_dest_changed(struct ip_vs_service *svc, struct ip_vs_dest *dest)
{
    struct ip_vs_wrr_mark *mark = svc->sched_data;

    mark->cl = list_entry(&svc->destinations, struct ip_vs_dest, n_list);
    mark->di = ip_vs_wrr_gcd_weight(svc);
    mark->mw = ip_vs_wrr_max_weight(svc) - (mark->di - 1);
	
    if (mark->cw > mark->mw || !mark->cw)
        mark->cw = mark->mw;
    else if (mark->di > 1)
        mark->cw = (mark->cw / mark->di) * mark->di + 1;

在真实服务器修改后，需要重新计算di和mw的值。如果当前权重值cw大于更新之后的最大权重值mw，将cw重新复制为mw的值。否则，如果更新后的di值大于1，使用新的di值，重新计算cw的值。后一种情况，相当于延续修改之前的路径。

调度处理

WRR调度器调度函数如下ip_vs_wrr_schedule，首先遍历虚拟服务所关联的真实服务器链表，找到第一个未过载并且其权重值大于等于mark记录的cw值的真实服务器。返回此真实服务器。

static struct ip_vs_dest *ip_vs_wrr_schedule(struct ip_vs_service *svc, const struct sk_buff *skb, struct ip_vs_iphdr *iph)
{
    struct ip_vs_dest *dest, *last, *stop = NULL;
    struct ip_vs_wrr_mark *mark = svc->sched_data;
    bool last_pass = false, restarted = false;

    spin_lock_bh(&svc->sched_lock);
    dest = mark->cl;

    if (mark->mw == 0)
        goto err_noavail;
    last = dest;
    /* Stop only after all dests were checked for weight >= 1 (last pass) */
    while (1) {
        list_for_each_entry_continue_rcu(dest, &svc->destinations, n_list) {
            if (!(dest->flags & IP_VS_DEST_F_OVERLOAD) && atomic_read(&dest->weight) >= mark->cw)
                goto found;
            if (dest == stop)
                goto err_over;
        }

如果没有符合以上条件的真实服务器，降低当前mark记录的权重值一个档位（di），再次遍历真实服务器链表，查找符合条件的真实服务器。

如果直到mark记录的cw值小于等于零时（遍历结束），还没有找到合适的真实服务器，将cw值恢复为最大权重值（mw），此时如果已经是最后一次(last_pass)遍历，或者上一次调度的真实服务器位于链表的头部，说明遍历完成而且没有找到合适的真实服务器。否则置位restarted标志，重新启动查找操作。last_pass置位时mark的cw值为1，进行最后一次查找，如果没有找到权重值大于1的可用真实服务器，退出循环。

最后，如果在cw小于mark的di时，即倒数第二次查找时，还没有找到合适的真实服务器，将stop设置为上一次调度的真实服务器，之后进行最后一次查找，如果在遍历到stop表示的真实服务器之前，还没有找到合适的服务器，退出循环。

        mark->cw -= mark->di;
        if (mark->cw <= 0) {
            mark->cw = mark->mw;
            /* Stop if we tried last pass from first dest:
             * 1. last_pass: we started checks when cw > di but then all dests were checked for w >= 1
             * 2. last was head: the first and only traversal was for weight >= 1, for all dests.
             */
            if (last_pass || &last->n_list == &svc->destinations)
                goto err_over;
            restarted = true;
        }
        last_pass = mark->cw <= mark->di;
        if (last_pass && restarted && &last->n_list != &svc->destinations) {
            /* First traversal was for w >= 1 but only for dests after 'last', now do the same for all dests up to 'last'. */
            stop = last;
        }
    }

found:
    mark->cl = dest;
out:
    spin_unlock_bh(&svc->sched_lock);
    return dest;
}

关于mark中最大权重值mw的设置，参见ip_vs_wrr_init_svc和ip_vs_wrr_dest_changed函数中的代码，mw实际上等于计算得到的最大权重值减去di，再加一，由于cw的值初始等于mw，之后每次遍历是减少di，以上运算保证了在cw最后一次的值为1。这样在遍历时就可选择到权重值低于di值的真实服务器。

内核版本 4.15