注:转载自http://tangfeng.iteye.com/blog/433011
一 、LVS总共有8种调度算法。
1. 轮叫调度(Round Robin Scheduling)
是以轮叫的方式依次将请求调度不同的服务器,即每次调度执行i = (i + 1) % n,并选出第i台服务器。在系统实现时,引入了一个额外条件,当服务器的权值为零时,表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务(如屏蔽服务器故障,系统维护)。它的算法流程如下:
假设有一组服务器S = {S0, S1, …, Sn-1},一个指示变量i表示上一次选择的服务器,W(Si)表示服务器Si的权值。变量i被初始化为n-1,其中n > 0。
int j = i;
do {
j = (j + 1) % n;
if (W(Sj) > 0) {
i = j;
return Si;
}
} while (j != i);
return null;
轮叫调度算法假设所有服务器处理性能均相同,不管服务器的当前连接数和响应速度。该算法相对简单,
不适用于服务器组中处理性能不一的情况,而且当请求服务时间变化比较大时,轮叫调度算法容易导致服务器间的负载不平衡。
2. 加权轮叫调度(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和cw最初都被初始化为零。
while (true) {
if (i == 0) {
cw = cw - gcd(S);
if (cw <= 0) {
cw = max(S);
if (cw == 0)
return null;
}
} else i = (i + 1) % n;
if (W(Si) >= cw)
return Si;
}
例如,有三个服务器A、B和C分别有权值4、3和2,则在一个调度周期内(mod sum(W(Si)))调度序列为AABABCABC。加权轮叫调度算法还是比较简单和高效。当请求的服务时间变化很大,单独的加权轮叫调度算法依然会导致服务器间的负载不平衡。
从上面的算法流程中,我们可以看出当服务器的权值为零时,该服务器不被被调度;当所有服务器的权值为零,即对于任意i有W(Si)=0,则没有任何服务器可用,算法返回NULL,所有的新连接都会被丢掉。加权轮叫调度也无需记录当前所有连接的状态,所以它也是一种无状态调度。
3. 最小连接调度(Least-Connection Scheduling)
是把新的连接请求分配到当前连接数最小的服务器。最小连接调度是一种动态调度算法,它通过服务器当前所活跃的连接数来估计服务器的负载情况。调度器需要记录各个服务器已建立连接的数目,当一个请求被调度到某台服务器,其连接数加1;当连接中止或超时,其连接数减一。在系统实现时,也引入当服务器的权值为零时,表示该服务器不可用而不被调度,它的算法流程如下:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,
C(Si)表示服务器Si的当前连接数。
for (m = 0; m < n; m++) {
if (W(Sm) > 0) {
for (i = m+1; i < n; i++) {
if (W(Si) <= 0)
continue;
if (C(Si) < C(Sm))
m = i;
}
return Sm;
}
}
return null;
当各个服务器有相同的处理性能时,最小连接调度算法能把负载变化大的请求分布平滑到各个服务器上,所有处理时间比较长的请求不可能被发送到同一台服务器上。但是,当各个服务器的处理能力不同时,该算法并不理想,因为TCP连接处理请求后会进入TIME_WAIT状态,TCP的TIME_WAIT一般为2分钟,此时连接还占用服务器的资源,所以会出现这样情形,性能高的服务器已处理所收到的连接,连接处于TIME_WAIT状态,而性能低的服务器已经忙于处理所收到的连接,还不断地收到新的连接请求。
4. 加权最小连接调度(Weighted Least-Connection Scheduling)
是最小连接调度的超集,各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1,系统管理员可以动态地设置服务器的权值。加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。加权最小连接调度的算法流程如下:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,C(Si)表示服务器Si的当前连接数。所有服务器当前连接数的总和为
CSUM = ΣC(Si) (i=0, 1, .. , n-1)。
当前的新连接请求会被发送服务器Sm,当且仅当服务器Sm满足以下条件
(C(Sm)/CSUM)/W(Sm) = min{ (C(Si)/CSUM)/W(Si)} (i=0, 1, . , n-1) 其中W(Si)不为零
因为CSUM在这一轮查找中是个常数,所以判断条件可以简化为
C(Sm)/W(Sm) = min{ C(Si)/W(Si)} (i=0, 1, . , n-1) 其中W(Si)不为零
因为除法所需的CPU周期比乘法多,且在Linux内核中不允许浮点除法,服务器的权值都大于零,所以判断条件C(Sm)/W(Sm) > C(Si)/W(Si) 可以进一步优化为C(Sm)*W(Si) > C(Si)* W(Sm)。同时保证服务器的权值为零时,服务器不被调度。所以,算法只要执行以下流程。
for (m = 0; m < n; m++) {
if (W(Sm) > 0) {
for (i = m+1; i < n; i++) {
if (C(Sm)*W(Si) > C(Si)*W(Sm))
m = i;
}
return Sm;
}
}
return null;
5. 基于局部性的最少链接调度 (Locality-Based Least Connections Schedulin
是针对请求报文的目标IP地址的负载均衡调度,目前主要用于Cache集群系统,因为在Cache集群中客户请求报文的目标IP地址是变化的。这里假设任何后端服务器都可以处理任一请求,算法的设计目标是在服务器的负载基本平衡情况下,将相同目标IP地址的请求调度到同一台服务器,来提高各台服务器的访问局部性和主存Cache命中率,从而整个集群系统的处理能力。
LBLC 调度算法先根据请求的目标IP地址找出该目标IP地址最近使用的服务器,若该服务器是可用的且没有超载,将请求发送到该服务器;若服务器不存在,或者该服务器超载且有服务器处于其一半的工作负载,则用“最少链接”的原则选出一个可用的服务器,将请求发送到该服务器。该算法的详细流程如下:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,C(Si)表示服务器Si的当前连接数。ServerNode[dest_ip]是一个关联变量,表示目标IP地址所对应的服务器结点,一般来说它是通过Hash表实现的。WLC(S)表示在集合S中的加权最小连接服务器,即前面的加权最小连接调度。Now为当前系统时间。
if (ServerNode[dest_ip] is null) then {
n = WLC(S);
if (n is null) then return null;
ServerNode[dest_ip].server = n;
} else {
n = ServerNode[dest_ip].server;
if ((n is dead) OR
(C(n) > W(n) AND
there is a node m with C(m) < W(m)/2))) then {
n = WLC(S);
if (n is null) then return null;
ServerNode[dest_ip].server = n;
}
}
ServerNode[dest_ip].lastuse = Now;
return n;
6. 带复制的基于局部性最少链接调度
带复制的基于局部性最少链接调度(Locality-Based Least Connections with Replication Scheduling,以下简称为LBLCR)算法也是针对目标IP地址的负载均衡,目前主要用于Cache集群系统。它与LBLC算法的不同之处是它要维护从一个目标IP地址到一组服务器的映射,而LBLC算法维护从一个目标IP地址到一台服务器的映射。对于一个“热门”站点的服务请求,一台Cache 服务器可能会忙不过来处理这些请求。这时,LBLC调度算法会从所有的Cache服务器中按“最小连接”原则选出一台Cache服务器,映射该“热门”站点到这台Cache服务器,很快这台Cache服务器也会超载,就会重复上述过程选出新的Cache服务器。这样,可能会导致该“热门”站点的映像会出现在所有的Cache服务器上,降低了Cache服务器的使用效率。LBLCR调度算法将“热门”站点映射到一组Cache服务器(服务器集合),当该“热门”站点的请求负载增加时,会增加集合里的Cache服务器,来处理不断增长的负载;当该“热门”站点的请求负载降低时,会减少集合里的Cache服务器数目。这样,该“热门”站点的映像不太可能出现在所有的Cache服务器上,从而提供Cache集群系统的使用效率。
LBLCR 算法先根据请求的目标IP地址找出该目标IP地址对应的服务器组;按“最小连接”原则从该服务器组中选出一台服务器,若服务器没有超载,将请求发送到该服务器;若服务器超载;则按“最小连接”原则从整个集群中选出一台服务器,将该服务器加入到服务器组中,将请求发送到该服务器。同时,当该服务器组有一段时间没有被修改,将最忙的服务器从服务器组中删除,以降低复制的程度。LBLCR调度算法的流程如下:
假设有一组服务器S = {S0, S1, ..., Sn-1},W(Si)表示服务器Si的权值,C(Si)表示服务器Si的当前连接数。ServerSet[dest_ip]是一个关联变量,表示目标IP地址所对应的服务器集合,一般来说它是通过Hash表实现的。WLC(S)表示在集合S中的加权最小连接服务器,即前面的加权最小连接调度;WGC(S)表示在集合S中的加权最大连接服务器。Now为当前系统时间,lastmod表示集合的最近修改时间,T为对集合进行调整的设定时间。
if (ServerSet[dest_ip] is NULL) then {
n = WLC(S);
if (n is NULL) then return NULL;
add n into ServerSet[dest_ip];
} else {
n = WLC(ServerSet[dest_ip]);
if ((n is NULL) OR
(n is dead) OR
(C(n) > W(n) AND
there is a node m with C(m) < W(m)/2))) then {
n = WLC(S);
if (n is NULL) then return NULL;
add n into ServerSet[dest_ip];
} else
if (|ServerSet[dest_ip]| > 1 AND
Now - ServerSet[dest_ip].lastmod > T) then {
m = WGC(ServerSet[dest_ip]);
remove m from ServerSet[dest_ip];
}
}
ServerSet[dest_ip].lastuse = Now;
if (ServerSet[dest_ip] changed) then
ServerSet[dest_ip].lastmod = Now;
return n;
7. 目标地址散列调度
目标地址散列调度(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;
8. 源地址散列调度
源地址散列调度(Source Hashing Scheduling)算法正好与目标地址散列调度算法相反,它根据请求的源IP地址,作为散列键(Hash Key)从静态分配的散列表找出对应的服务器,若该服务器是可用的且未超载,将请求发送到该服务器,否则返回空。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与目标地址散列调度算法的基本相似,除了将请求的目标IP地址换成请求的源IP地址。
在实际应用中,源地址散列调度和目标地址散列调度可以结合使用在防火墙集群中,它们可以保证整个系统的唯一出入口。
分享到:
相关推荐
F5负载均衡器BIG-IP LTM 1500是美国F5公司出品的一种高性能的负载均衡器设备。该设备具有强大的处理能力、高速的网络传输速度和高可用性,能够满足大规模网络应用的需求。 技术参数指标 * 设备名称:F5-BIGIP-GTM-...
基于LSTM的SDN流量预测与负载均衡python源码+数据+详细注释.zip基于LSTM的SDN流量预测与负载均衡python源码+数据+详细注释.zip基于LSTM的SDN流量预测与负载均衡python源码+数据+详细注释.zip基于LSTM的SDN流量预测与...
### 基于双线路接入的网关冗余和负载均衡设计与实现 #### 引言 随着企业信息化和数字化的快速发展,确保企业网络的稳定性和连续性变得尤为重要。为应对这一挑战,许多企业采取了双链路接入策略,即通过多ISP接入或...
#========controller,负载均衡控制器======== worker.controller.type=lb worker.controller.balanced_workers=tomcat1,tomcat2 worker.controller.sticky_session=1 5 修改tomcat的端口号(3处) ...
主机名IP地址操作系统组件备注环境说明架构图目录结构配置文件docker-compose配置文件keepalived配置文件keepalived检测脚本hapr
## 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载...
系统架构设计 2.1 总体思路 为提高网站的高并发性能,提高开发效率及运营效率,主要按如下几个思路进行规划设 计: 2.1.1 负载均衡 1) 四层交换负载均衡: 采用负载均衡器来实现硬件级的四层交换负载均衡,或采用LVS来...
通过Nginx实现反向代理服务器集群,同时搭建squid集群以作为静态页面和图片的缓存 通过web服务器的配置来实现负载均衡,即通过apache或是Nginx 将客户请求均衡的分给tomcat1,tomcat2….去处理 数据存储的设计思路 1...
STP (生成树协议):就是把一个环形的结构改变成一个树形的结构。用来将物理上存在环路的网络,通过一种算法,在逻辑...备注:现在的路由器不会产生环路,配置的主要目的是选择性能较好的交换机做根网桥实现负载均衡。
负载均衡是服务器集群技术的重要功能之一。它可以将用户的请求分配到多台服务器上,以减少单台服务器的负载和提高系统的整体性能。Windows 2003 Server企业版的“集群管理器”可以用于手动平衡服务器的工作负荷,并...
- 负载均衡ELB(Elastic Load Balance):分配访问请求以提高服务器的可用性。 2. **云服务架构设计**: - 云服务模型(IaaS/PaaS/SaaS)的理解和应用。 - 微服务架构与容器化技术,如容器服务CCE(Container ...
在实际操作中,除了遵循上述步骤外,还应根据具体的硬件环境和应用需求进行适当的调整和优化,确保集群能够提供高可用性和负载均衡的能力。 总的来说,Windows Server 2003集群配置是一个涉及多方面知识的综合任务...
使用Python Web框架Django开发的一个B2C网上蔬果商城,包含用户、商品、购物车、订单等模块等等,使用了Celery异步任务队列,MySQL数据库,Redis数据库,FastDFS分布式的图片存储服 务,Nginx负载均衡服务器,uWSGI...
校园网络及综合布线 序号 产品名称 技术参数 数量 单位 备注 品牌推荐 一、校园网(计算机网络) 1 管理计算机 I3-4150/G3240/2G-DDR3/500G/intel HD/DVD 18.5LCD/音响;鼠标、键盘、19寸16:9液晶显示器; 1 台 2 ...
- 两台代理服务器(Apache服务器)负责负载均衡,将请求分发到不同的WebLogic服务器上。 - 代理服务器的配置应确保高可用性和负载均衡。 **2.2 管理服务器** - 管理服务器(Admin Server)负责集群的整体管理与...
## 基于muduo高性能网络库,可以工作在nginx负载均衡环境中的集群聊天服务器 ### 项目编译方式 cd build rm -rf * cmake .. make 或者 ./chatServer.sh 【备注】 1、该资源内项目代码都经过测试运行成功,...
1 3.1 系统拓扑图 1 3.2 负载均衡设计 2 3.3 网络存储设计 2 3.4 冗余设计 2 3.5 灾难备份设计 2 4 系统安全设计 3 4.1 网络安全设计 3 4.1.1 访问控制设计 3 4.1.2 拒绝服务攻击防护设计 3 4.1.3 嗅探(sniffer)...
在IT领域,尤其是企业级应用中,集群部署是保证高可用性和负载均衡的重要手段。本案例将详细介绍在Windows Server 2008 R2(win2008R2)操作系统上进行NC(可能是网络计算或网络连接)与WebSphere Application ...