加权轮叫调度(Weighted Round-Robin Scheduling)算法可以解决服务器间性能不一的情况,它用相应的权值表示服务器的处理性能,服务器的缺省权值为1。假设服务器A的权值为1,B的权值为2,则表示服务器B的处理性能是A的两倍。加权轮叫调度算法是按权值的高低和轮叫方式分配请求到各服务器。权值高的服务器先收到的连接,权值高的服务器比权值低的服务器处理更多的连接,相同权值的服务器处理相同数目的连接数。加权轮叫调度算法流程如下:
加权轮叫调度算法流程:
假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个 指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S) 表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大 公约数。变量i初始化为-1,cw初始化为零。 while (true) { i = (i + 1) mod n; if (i == 0) { cw = cw - gcd(S); if (cw <= 0) { cw = max(S); if (cw == 0) return NULL; } } if (W(Si) >= cw) return Si; }例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。
从上面的算法流程中,我们可以看出当服务器的权值为零时,该服务器不被被调度;当所有服务器的权值为零,即对于任意i有W(Si)=0,则没有任何服务器可用,算法返回NULL,所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态,所以它也是一种无状态调度。
目标地址散列调度(DH)目标地址散列调度(Destination Hashing Scheduling)算法也是针对目标IP地址的负载均衡,但它是一种静态映射算法,通过一个散列(Hash)函数将一个目标IP地址映射到一台服务器。
目标地址散列调度算法先根据请求的目标IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。该算法的流程如下:
目标地址散列调度算法流程:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值, C(Si)表示服务器Si的当前连接数。ServerNode[]是一个有256个桶(Bucket)的 Hash表,一般来说服务器的数目会运小于256,当然表的大小也是可以调整的。 算法的初始化是将所有服务器顺序、循环地放置到ServerNode表中。若服务器的 连接数目大于2倍的权值,则表示服务器已超载。 n = ServerNode[hashkey(dest_ip)]; if ((n is dead) OR (W(n) == 0) OR (C(n) > 2*W(n))) then return NULL; return n;在实现时,我们采用素数乘法Hash函数,通过乘以素数使得散列键值尽可能地达到较均匀的分布。所采用的素数乘法Hash函数如下:
素数乘法Hash函数
static inline unsigned hashkey(unsigned int dest_ip) { return (dest_ip* 2654435761UL) & HASH_TAB_MASK; } 其中,2654435761UL是2到2^32 (4294967296)间接近于黄金分割的素数, (sqrt(5) - 1) / 2 = 0.618033989 2654435761 / 4294967296 = 0.618033987 源地址散列调度(SH)源地址散列调度(Source Hashing Scheduling)算法正好与目标地址散列调度算法相反,它根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回���。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与目标地址散列调度算法的基本相似,除了将请求的目标IP地址换成请求的源IP地址,所以这里不一一叙述。
在实际应用中,源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中,它们可以保证整个系统的唯一出入口。
最小连接调度(LC)