Round-Robin负载均衡算法及其实现原理
【IT专家网独家】概述
毫无疑问,随着互联网、移动网络接入成本的降低,互联网正在日益深入地走入我们的生活,越来越成为人们获取信息的高效平台,ICP行业也顺势呈现出强劲的成长趋势,成为互联网迅猛发展形势下最大的受益者,也直接促成了从web1.0到web2.0以及社区、博客、视频等一系列互联网时代的更迭和运营模式的变动。
但是随着各站点访问量和信息交流量的迅猛增长,如何使用最小的资源成本,提高网络的效率,最优化用户体验,已经成为网络管理人员不得不面对的挑战。
从技术上讲,就是ICP行业面临的网络资源有效利用问题,也就是如何进行对网络的访问分流,以便能够快速响应用户反应,即:负载均衡。
从这篇文章起,我们将讲述在负载均衡技术实现中的核心技术:负载均衡算法(算法)的原理及其实现,使大家对负载均衡底层技术有一个深刻的了解。这些算法是负载均衡设备中的核心实现基础。
本篇文章先讲述轮询调度算法 (Round-Robin)及其在此基础上改进型的权重轮询算法 (Weighted Round-Robin)。
轮询调度算法(Round-Robin Scheduling)
轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器,从1开始,直到N(内部服务器个数),然后重新开始循环。
算法的优点是其简洁性,它无需记录当前所有连接的状态,所以它是一种无状态调度。
轮询调度算法流程
假设有一组服务器N台,S = {S1, S2, …, Sn},一个指示变量i表示上一次选择的服务器ID。变量i被初始化为N-1。其算法如下:
j = i; do { j = (j + 1) mod n; i = j; return Si; } while (j != i); return NULL; |
这种算法的逻辑实现如图1所示:
图1 轮询调度实现逻辑图示
轮询调度算法假设所有服务器的处理性能都相同,不关心每台服务器的当前连接数和响应速度。当请求服务间隔时间变化比较大时,轮询调度算法容易导致服务器间的负载不平衡。
所以此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。
权重轮询调度算法(Weighted Round-Robin Scheduling)
上面所讲的轮询调度算法并没有考虑每台服务器的处理能力,在实际情况中,可能并不是这种情况。由于每台服务器的配置、安装的业务应用等不同,其处理能力会不一样。所以,我们根据服务器的不同处理能力,给每个服务器分配不同的权值,使其能够接受相应权值数的服务请求。
权重轮询调度算法流程
假设有一组服务器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; } |
这种算法的逻辑实现如图2所示,图中我们假定四台服务器的处理能力为3:1:1:1。
图2 权重轮询调度实现逻辑图示
由于权重轮询调度算法考虑到了不同服务器的处理能力,所以这种均衡算法能确保高性能的服务器得到更多的使用率,避免低性能的服务器负载过重。所以,在实际应用中比较常见。
总结
轮询调度算法以及权重轮询调度算法的特点是实现起来比较简洁,并且实用。目前几乎所有的负载均衡设备均提供这种功能。
相关推荐
基于螺旋线的Round-Robin Crossbar调度算法
基于两优先级Round-robin算法PCI仲裁扩展器的设计与实现,陈晓飞,李红信,PCI总线凭借高带宽、高性能、高可靠性、即插即用等多方面的优越性获得了迅速的发展。当PCI总线上挂载多个设备时,为保证多个设备能
Laravel开发-round-robin Laravel 5.4 的循环。
安装 $ npm install vdemedes/round-robin --save用法 const roundrobin = require ( 'round-robin' ) ;let servers = ['192.168.0.1' ,'192.168.0.2' ,'192.168.0.3'] ;let next = roundrobin ( servers ) ;next ( ...
Round-Robin Scheduling module.
基于专家系统和Round-Robin算法的芯片编程系统.pdf
Verilog Round Robin Arbiter Model
Round-Robin-Scheduler:the用于流程调度的Round Robin Scheduler算法的C ++实现
2/4/8输入RR调度verilog代码,
Round-robin path selector for Linux v2.13.6.
时间片轮转法:程序模拟进程的时间片轮转RR调度过程。Time slice Round-Robin: program to simulate the process time slice rotation RR scheduling process.
适用于虚通道路由器的高性能round-robin仲裁器.pdf
An Asynchronous Adaptive Priority Round-Robin Arbiter Based on Four-Phase Dual-rail Protocol
。。。
$ cd flume-round-robin-channel-selector $ mvn clean package $ ls target flume-round-robin-channel-selector-1.0.jar 将JAR添加到Flume类路径 $ cp /etc/flume-ng/conf/flume-env.sh.template /etc/flume-...
带权重的优先级轮转算法的verilog实现
介绍了Round Robin(RR),Weighted Round Robin(WRR),Least Connection(LC)和Weighted Least Connection(WLC)四种负载均衡算法,对这四种算法进行性能仿真。根据模拟得到的相关数据绘制各个算法的负载均衡度...
Round-robin scheduling algorithm is one of the simplest scheduling algorithms. It is designed especially for time-sharing systems. The ready queue is treated as a circular queue. The algorithm assigns...
Nginx的特点是: ... 2、Nginx对网络的依赖比较小; 3、Nginx安装和配置比较简单,测试起来比较方便; 4、也可以承担高的负载压力且稳定,一般能支撑超过1万... 另外默认的只有Round-robin和IP-hash两种负载均衡算法。
循环负载均衡器Go中实现的一个简单的循环负载均衡器在这里,我们提供了到服务器的路由列表,这些服务器生成了一个负载均衡器,该负载均衡器使用循环选择将请求路由到每个服务器。 例子从/ server运行任意数量的...