IPVS代码阅读笔记（三）：调度算法

调度算法就是，当新连接到来时，负载均衡器如何选择真实服务器的一种算法。它是负载均衡器的重要组成部分。

IPVS中实现的负载均衡算法主要有轮询-rr、加权轮询-wrr、最少连接-lc、加权最少连接-wlc。

1、ip_vs_scheduler结构

/*
 *    The scheduler object
 */
struct ip_vs_scheduler {
    struct list_head    n_list;        /* d-linked list head */
    char            *name;        /* scheduler name */
    atomic_t        refcnt;        /* reference counter */
    struct module        *module;    /* THIS_MODULE/NULL */

    /* scheduler initializing service */
    int (*init_service)(struct ip_vs_service *svc);
    /* scheduling service finish */
    int (*done_service)(struct ip_vs_service *svc);
    /* scheduler updating service */
    int (*update_service)(struct ip_vs_service *svc);

    /* selecting a server from the given service */
    struct ip_vs_dest* (*schedule)(struct ip_vs_service *svc,
                 const struct sk_buff *skb);
};


这里主要看四个函数指针。

init_service函数是与ip_vs_service对象绑定时调用的，利用ip_vs_service对象的一些数据对ip_vs_scheduler对象进行初始化。

done_service函数正好与init_service相反，它是在与ip_vs_service对象解除绑定时调用的，释放初始化时申请的内存等资源。

update_service函数是当ip_vs_service对象更新时调用，例如dest的增加/删除/修改，都会调用update_service函数。

这三个函数一般都是维护ip_vs_service对象的sched_data属性，其中包含了每个dest的信息。各种调度算法中，维护 sched_data的方式是不同的。如rr算法中，ip_vs_rr_scheduler将ip_vs_service对象的destinations 链表中的某个节点作为其sched_data，以注明当前轮询到哪台dest了。而甚至在lc算法中，其sched_data是空的。

schedule函数是最重要的，它根据输入的数据包（sk_buff结构，包含了数据包的源地址等所有信息），选择一台dest，返回一个ip_vs_dest对象。

2、调度算法

2.1、RR

其对应的ip_vs_scheduler对象为ip_vs_rr_scheduler。它的sched_data指向ip_vs_service对象的某个dest，schedule函数仅仅是在dest链表找到下一个可用的dest对象。

2.2、WRR

其sched_data为一个结构体：

/*
 * current destination pointer for weighted round-robin scheduling
 */
struct ip_vs_wrr_mark {
    struct list_head *cl;    /* current list head */
    int cw;            /* current weight */
    int mw;            /* maximum weight */
    int di;            /* decreasing interval */
};

cl为当前的dest节点，cw为当前权重（注意并不是指cl的权重），mw为最大权重，di为所有权重值的最大公约数。

设S1、S2、S3为三个dest节点。为了描述简单，假设di为1。其轮询过程中，一轮下来总共经历了W1+W2+W3次调度，其中S1被调度W1次，S2被调度W2次，S3被调度W3次。假设W1=3，W2=W3=1，

S1	S2	S3	cw	cl
			0	HEAD
		S3	3	S3
		S3	2	S3
S1			1	S1
	S2		1	S2
		S3	1	S3

先将cw设置成MAX(W)，然后从dest链表中找到权重不小于cw的节点，并依次返回。将cw减1，然后再遍历dest链表，返回权重不小于cw的节点。直到cw为0，一轮调度结束。

2.3、LC和WLC

其sched_data均为NULL。

LC算法遍历dest链表，找到连接数最少的节点，并返回。连接数的计算公式：dest->activeconns*256 + dest->inactconns。

WLC算法和LC算法基本一样，只是计算公式不同：(dest overhead) / dest->weight

3、动态反馈算法

 

这是一种基于真实服务器载荷查询的反馈调度算法，根据真实载荷动态调整权重比例。这需要IPVS和其他监控程序配合使用。