负载调度算法 负载均衡（Load Balance），又称为负载分担，就是将负载（工作任务）进行平衡、分摊到多个操作单元上进行执行，例如Web服务器、FTP服务器、企业关键应用服务器和其它关键任务服务器等，从而共同完成工作任务。负载均衡建立在现有网络结构之上，它提供了一种廉价又有效的方法来扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。 在调度器的实现技术中，IP负载均衡技术是效率最高的。在已有的IP负载均衡技术中有通过网络地址转换（Network Address Translation）将一组服务器构成一个高性能的、高可用的虚拟服务器，称之为VS/NAT技术。在分析VS/NAT 的缺点和网络服务的非对称性的基础上，提出通过IP隧道实现虚拟服务器的方法VS/TUN，和通过直接路由实现虚拟服务器的方法VS/DR，它们可以极大地提高系统的伸缩性。 在内核中的连接调度算法上，IPVS实现了以下几种调度算法： 1 轮叫调度 1.1 轮叫调度含义 轮叫调度（Round Robin Scheduling）算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行i = (i + 1) mod n，并选出第i台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。 轮叫是基站为终端分配带宽的一种处理流程，这种分配可以是针对单个终端或是一组终端的。为单个终端和一组终端连接分配带宽，实际上是定义带宽请求竞争机制，这种分配不是使用一个单独的消息，而是上行链路映射消息中包含的一系列分配机制。 1.2 轮叫调度算法流程 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N（内部服务器个数），然后重新开始循环。在系统实现时，我们引入了一个额外条件，即当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。所以，算法要作相应的改动，它的算法流程如下：假设有一组服务器S = {S0, S1, …, Sn-1}，一个指示变量i表示上一次选择的服务器，W(Si)表示服务器Si的权值。变量i被初始化为n-1，其中n > 0。 j = i; do { j = (j + 1) mod n;
几种负载均衡算法 本地流量管理技术主要有以下几种负载均衡算法： 静态负载均衡算法包括：轮询，比率，优先权 动态负载均衡算法包括: 最少连接数,最快响应速度，观察方法，预测法，动态性能分配，动态服务器补充，服务质量，服务类型，规则模式。 静态负载均衡算法 ◆轮询（Round Robin）：顺序循环将请求一次顺序循环地连接每个服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从顺序循环队列中拿出，不参加下一次的轮询，直到其恢复正常。 ◆比率（Ratio）：给每个服务器分配一个加权值为比例，根椐这个比例，把用户的请求分配到每个服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配, 直到其恢复正常。 ◆优先权（Priority）：给所有服务器分组,给每个组定义优先权，BIG-IP 用户的请求，分配给优先级最高的服务器组（在同一组内，采用轮询或比率算法，分配用户的请求）；当最高优先级中所有服务器出现故障，BIG-IP 才将请求送给次优先级的服务器组。这种方式，实际为用户提供一种热备份的方式。 动态负载均衡算法 ◆最少的连接方式（Least Connection）：传递新的连接给那些进行最少连接处理的服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配, 直到其恢复正常。 ◆最快模式（Fastest）：传递连接给那些响应最快的服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配，直到其恢复正常。 ◆观察模式（Observed）：连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP就把其从服务器队列中拿出，不参加下一次的用户请求的分配，直到其恢复正常。 ◆预测模式（Predictive）：BIG-IP利用收集到的服务器当前的性能指标，进行预测分析，选择一台服务器在下一个时间片内，其性能将达到最佳的服务器相应用户的请求。(被BIG-IP 进行检测) ◆动态性能分配(Dynamic Ratio-APM):BIG-IP 收集到的应用程序和应用服务器的各项性能参数，动态调整流量分配。 ◆动态服务器补充(Dynamic Server Act.):当主服务器群中因故障导致数量减少时，动态地将备份服务器补充至主服务器群。 ◆服务质量(QoS）:按不同的优先级对数据流进行分配。 ◆服务类型(ToS): 按不同的服务类型（在Type of Field中标识）负载均衡对数据流进行分配。 ◆规则模式：针对不同的数据流设置导向规则，用户可自行。 负载均衡对应本地的应用交换，大家可以通过对上述负载均衡算法的理解，结合实际的需求来采用合适你的负载均衡算法，我们常用到的一般是最少连接数、最快反应、或者轮询，决定选用那种算法，主要还是要结合实际的需求。
1.Rr – Round Robin 默认情况下，访问请求分配的次序为： 1, 2, 3, 4, 1, 2, 3,4 若Servers之间存在性能差异，可以通过调整分配粒度值（weight），来控制访问请求分配的次序： 1, 1, 1, 2, 2, 2, 3, 3, 3,4,4,4, 2.Lc - Least Connections 新的访问请求将分配至当前连接数最少的一台服务器上。分配粒度方法定义了两个服务器的活动连接数要有多大差别，算法里才会将它们区分为不同等级。3.Sr – Shortest Response Time 基于后台服务器的最短相应时间来分配新的访问请求。 4.Pi – Persistent IP 相同IP地址的请求将会分配到相同的服务器上 5.HI - Hash IP 这是一种基于源IP地址Hash来分发新建连接的算法。客户端发送一个请求到虚拟服务器；负载均衡设备将根据源IP地址计算出的哈希值来选择将该访问请求发送到哪一台服务器；对于哈希值相同的请求连接，都将会发送到相同的服务器上。 注意：如果一台服务器失效了，将导致负载均衡设备上的哈希值重新计算，这样对所有原已维持的会话状态都将产生影响。 在负载均衡集群的方式下，客户端到服务器端的对应关系，在其他负载均衡设备上无法维持的，因此当其中一台负载均衡设备失效以后，客户端的请求将会在其他正常的负载均衡重新进行负载分配。 6.CHI – Consistent Hash IP 这是一种基于源IP地址Hash来分发新建连接的算法。 客户端发送一个请求到虚拟服务器；负载均衡设备将根据源IP地址计算出的哈希值来选择将该访问请求发送到哪一台服务器；对于哈希值相同的请求连接，都将会发送到相同的服务器上。 注意：
集群的负载均衡技术综述 摘要：当今世界，无论在机构内部的局域网还是在广域网如Internet上，信息处理量的增长都远远超出了过去最乐观的估计，即使按照当时最优配置建设的网络，也很快会感到吃不消。如何在完成同样功能的多个网络设备之间实现合理的业务量分配，使之不致于出现一台设备过忙、而别的设备却未充分发挥处理能力的情况，负载均衡机制因此应运而生。本组在课堂上讲解了《集群监控与调度》这一课题，本人在小组内负责负载均衡部分内容，以及PPT的制作。 关键词：负载均衡集群网络计算机 一、前言 负载均衡建立在现有网络结构之上，它提供了一种廉价有效的方法扩展服务器带宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。它主要完成以下任务：解决网络拥塞问题，服务就近提供，实现地理位置无关性；为用户提供更好的访问质量；提高服务器响应速度；提高服务器及其他资源的利用效率；避免了网络关键部位出现单点失效。 其实，负载均衡并非传统意义上的“均衡”，一般来说，它只是把有可能拥塞于一个地方的负载交给多个地方分担。如果将其改称为“负载分担”，也许更好懂一些。说得通俗一点，负载均衡在网络中的作用就像轮流值日制度，把任务分给大家来完成，以免让一个人累死累活。不过，这种意义上的均衡一般是静态的，也就是事先确定的“轮值”策略。 与轮流值日制度不同的是，动态负载均衡通过一些工具实时地分析数据包，掌握网络中的数据流量状况，把任务合理分配出去。结构上分为本地负载均衡和地域负载均衡(全局负载均衡)，前一种是指对本地的服务器集群做负载均衡，后一种是指对分别放置在不同的地理位置、在不同的网络及服务器群集之间作负载均衡。 服务器群集中每个服务结点运行一个所需服务器程序的独立拷贝，诸如Web、FTP、Telnet或e-mail服务器程序。对于某些服务（如运行在Web服务器上的那些服务）而言，程序的一个拷贝运行在群集内所有的主机上，而网络负载均衡则将工作负载在这些主机间进行分配。对于其他服务（例如e-mail），只有一台主机处理工作负载，针对这些服务，网络负载均衡允许网络通讯量流到一个主机上，并在该主机发生故障时将通讯量移至其他主机。 二、负载均衡技术实现结构 在现有网络结构之上，负载均衡提供了一种廉价有效的方法扩展服务器带宽和增加吞吐量，加强网络数据处理能力，提高网络的灵活性和可用性。它主要完成以下任务： 1.解决网络拥塞问题，服务就近提供，实现地理位置无关性 2.为用户提供更好的访问质量 3.提高服务器响应速度
应用交换技术的负载均衡算法 应用交换技术里主要包括四项关键的技术： ●截获和检查流量 ●服务器监控健康检查 ●负载均衡算法 ●会话保持 截获和检查流量保证只有合适的数据包才能通过； 服务器监控和健康检查随时了解服务器群的可用性状态； 负载均衡和应用交换功能通过各种策略导向到合适的服务器； 会话的保持以实现与应用系统完美结合； F5在应用交换技术中的优势： A、截获和检查流量 –BIG-IP 有最强的数据包截获和检查引擎去检查任何数据流量包中的任何部分，可以检测16384bytes包的深度，理论上可以检测 64Kbytes的包长度 –这使得BIG-IP 明显有别于其他的厂商的产品 B、用于定制控制的iRules工具 –可用来定义如何根据报头和/或TCP有效负载信息来引导、保存和过滤流量。 –iRules增强了企业或服务提供商定根据业务需求定制应用流量的能力。 –通用检查引擎和iRules分别是应用智能和业务决策来进行应用流量管理的方法和工具。 C、服务器监控和健康检查
–服务器(Node)-Ping(ICMP) –服务(Port)-Connect –扩展的应用验证(EAV) –扩展的内容验证(ECV) –针对VOD服务器的专用健康检查机制 –针对节点的检查频率和超时频度,e.g.10seconds响应,e.g.5seconds D、负载均衡和应用交换功能 –Global Load Balancer提供17种负载均衡算法 –F5提供最优质的负载均衡和应用交换功能 静态算法 动态算法 智能算法 I –control UIE + Irules –Local Load Balancer提供12种负载均衡算法 E、持续功能 –连续性与负载平衡是相互对立的，但它对于负载平衡又是必不可少的! –简单的连续性—基于源地址 –HTTP Cookie 连续性 –SSL Session ID 连续性 –目的地址的亲合作用--caches –standby BIG-IP实现对连续性记录的镜像 –智能与第七层的内容交换组合 F5做为应用交换领域的领导厂商，一直保持着技术上的领先地位，F5已经有40多项技术申请了专利，其它的竞争合作伙伴都在购买F5的这些专利技术。接下来我们讨论一下负载均衡算法。
PS：Nginx/LVS/HAProxy是目前使用最广泛的三种负载均衡软件，本人都在多个项目中实施过，参考了一些资料，结合自己的一些使用经验，总结一下。 一般对负载均衡的使用是随着网站规模的提升根据不同的阶段来使用不同的技术。具体的应用需求还得具体分析，如果是中小型的Web应用，比如日PV小于1000万，用Nginx就完全可以了；如果机器不少，可以用DNS轮询，LVS所耗费的机器还是比较多的；大型网站或重要的服务，且服务器比较多时，可以考虑用LVS。一种是通过硬件来进行进行，常见的硬件有比较昂贵的F5和Array等商用的负载均衡器，它的优点就是有专业的维护团队来对这些服务进行维护、缺点就是花销太大，所以对于规模较小的网络服务来说暂时还没有需要使用；另外一种就是类似于Nginx/LVS/HAProxy的基于Linux的开源免费的负载均衡软件，这些都是通过软件级别来实现，所以费用非常低廉。 目前关于网站架构一般比较合理流行的架构方案：Web前端采用 Nginx/HAProxy+Keepalived作负载均衡器；后端采用MySQL数据库一主多从和读写分离，采用LVS+Keepalived的架构。当然要根据项目具体需求制定方案。 下面说说各自的特点和适用场合。 一、Nginx Nginx的优点是： 1、工作在网络的7层之上，可以针对http应用做一些分流的策略，比如针对域名、目录结构，它的正则规则比HAProxy更为强大和灵活，这也是它目前广泛流行的主要原因之一，Nginx单凭这点可利用的场合就远多于LVS了。 2、Nginx对网络稳定性的依赖非常小，理论上能ping通就就能进行负载功能，这个也是它的优势之一；相反LVS对网络稳定性依赖比较大，这点本人深有体会； 3、Nginx安装和配置比较简单，测试起来比较方便，它基本能把错误用日志打印出来。LVS的配置、测试就要花比较长的时间了，LVS对网络依赖比较大。 3、可以承担高负载压力且稳定，在硬件不差的情况下一般能支撑几万次的并发量，负载度比LVS相对小些。 4、Nginx可以通过端口检测到服务器内部的故障，比如根据服务器处理网页返回的状态码、超时等等，并且会把返回错误的请求重新提交到另一个节点，不过其中缺点就是不支持url来检测。比如用户正在上传一个文件，而处理该上传的节点刚好在上传过程中出现故障，Nginx会把上传切到另一台服务器重新处理，而LVS就直接断掉了，如果是上传一个很大的文件或者很重要的文件的话，用户可能会因此而不满。 5、Nginx不仅仅是一款优秀的负载均衡器/反向代理软件，它同时也是功能强大的Web应用服务器。LNMP也是近几年非常流行的web架构，在高流量的环境中稳定性也很好。 6、Nginx现在作为Web反向加速缓存越来越成熟了，速度比传统的Squid服务器更快，可以考虑用其作为反向代理加速器。 7、Nginx可作为中层反向代理使用，这一层面Nginx基本上无对手，唯一可以对比
应用负载均衡设计方案v1设 计方案 1．需要有支持应用的负载均衡产品，具备多种负载均衡算法。 2．能够做到根据各个Web服务器的性能，合理地分配服务器群中的每台机器所要处理的请求。 3．能够及时的发现群中的某台机器当掉，从而不对此机器发送请求。当掉机器恢复正常后，自动进行业务处理。 4．可以应对大量的服务访问；至少2, 000, 000条的TCP同时并发连接，至少每秒建立100, 000条连接。 5．有效直观的监控统计界面，包含当前时刻、过去一段时间的请求数量统计、性能统计、会话时间统计。 6．为个人业务提供SSL加密服务，可以将服务器SSL加/解密前移，并提供高效的https加/解密性能。 7．能够提供有效的机制缓解后台应用中间键服务器压力，提高业务的访问量。
一、方案建议 针对上一节提出的需求分析，F5公司充分考虑XXXX现有的实际状况，结合F5公司在 国际上网络优化案例的经验，总结出以下应用交付优化设计方案。 方案采用F5公司的新一代LTM应用交换机BIGIP3400, 提供后台Web服务器集群的负 载均衡；同时，采用另两台BIGIP 3400设备提供后台中间键服务器负载均衡，并减轻中间键服务器的压力。 在负责实现Web服务器负载均衡的BIG-IP 3400上设置两个Vlan , 分别是External Vlan 负责连接外部的防火墙系统, Internal Vlan负责连接部Web服务器集群。并且在该对BIG-IP 3400上，分别采用SSL加速模块帮助后台Web服务器实现业务的加密处理；还采用了动态智能压缩模块帮助XXXX在有限的带宽下实现访问速度的提高和访问量的增大。 在负责实现部中间键服务器负载均衡的BIG-IP 3400也设置两个Vlan，分别是External Vlan 负责连接外部的Web服务器集群, Internal Vlan负责连接部中间键服务器集群。并 且在该对BIG-IP 3400上，采用One-Connection技术降低后台中间键服务器集群的负载。
一、LVS概念 LVS（Linux Virtual Server）：Linux 虚拟服务器 LVS是个负载均衡设备，它不提供任何服务，用户请求到这里的时候，它是将客户需求转发至后端真正提供服务的服务，所以说后端的服务称作real server。LVS分为两段，前一段称为ipvsadm（管理集群服务的命令行工具），后面一段叫做ipvs（内核模块）【提示：LVS和iptables不能同时使用】。 二、LVS类型 LB（Load Balancing）：负载均衡集群 特性：为了增加能力 HA（High Availability）：高可用集群 特性：提供服务的可用性(一年在线时间达到99.999%才行) 计算方法：在线时间/(在线时间/故障处理时间) HP（[HPC]High Performance）：高性能集群 特性：提供服务的性能 三、LVS组成结构（负载均衡实现方案） 基于DNS域名轮流解析的方法 基于客户端调度访问的方法 基于应用层系统负载的调度方法 基于IP地址的调度方法 其中基于IP的负载调度算法中，IP负载均衡技术是执行效率最高的 四、LVS十种调度算法 1、静态调度： ①rr（Round Robin）:轮询调度，轮叫调度 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N(内部服务器个数)，然后重新开始循环。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。【提示：这里是不考虑每台服务器的处理能力】 ②wrr：weight,加权（以权重之间的比例实现在各主机之间进行调度） 由于每台服务器的配置、安装的业务应用等不同，其处理能力会不一样。所以，我们根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求。 ③sh:source hashing,源地址散列。主要实现会话绑定，能够将此前建立的session信息保留了 源地址散列调度算法正好与目标地址散列调度算法相反，它根据请求的源IP地址，作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的并且没有超负荷，将请求发送到该服务器，否则返回空。它采用的散列函数与目标地址散列调度算法的相同。它的算法流程与目标地址散列调度算法的基本相似，除了将请求的目标IP地址换成请求的源IP地址，所以这里不一个一个叙述。 ④Dh:Destination hashing:目标地址散列。把同一个IP地址的请求，发送给同一个server。 目标地址散列调度算法也是针对目标IP地址的负载均衡，它是一种静态映射算法，通过一个散列（Hash）函数将一个目标IP地址映射到一台服务器。目标地址散列调度算法先根据请求的目标IP地址，作为散列键（Hash Key）从静态分配的散列表找出对应的服务器，若该服务器是可用的且未超载，将请求发送到该服务器，否则返回空。 2、动态调度 ①lc（Least-Connection）：最少连接 最少连接调度算法是把新的连接请求分配到当前连接数最小的服务器，最小连接调度是一种动态调度短算法，它通过服务器当前所活跃的连接数来估计服务器的负载均衡，调度器需要记录各个服务器已建立连接的数目，当一个请求被调度到某台服务器，其连接数加1，当连接中止或超时，其连接数减一，在系统实现时，我们也引入当服务器的权值为0时，表示该服务器不可用而不被调度。 简单算法：active*256+inactive(谁的小，挑谁) ②wlc(Weighted Least-Connection Scheduling)：加权最少连接。 加权最小连接调度算法是最小连接调度的超集，各个服务器用相应的权值表示其处理性能。服务器的缺省权值为1，系统管理员可以动态地设置服务器的权限，加权最小连接调度在调度新连接时尽可能使服务器的已建立连接数和其权值成比例。 简单算法：（active*256+inactive）/weight【（活动的连接数+1）/除以权重】（谁的小，挑谁） ③sed(Shortest Expected Delay)：最短期望延迟 基于wlc算法 简单算法：（active+1)*256/weight 【（活动的连接数+1）*256/除以权重】 ④nq（never queue）:永不排队（改进的sed）
实用标准文案 几种负载均衡算法 本地流量管理技术主要有以下几种负载均衡算法： 静态负载均衡算法包括：轮询，比率，优先权 动态负载均衡算法包括: 最少连接数,最快响应速度，观察方法，预测法，动态性能分配，动态服务器补充，服务质量，服务类型，规则模式。 静态负载均衡算法 ◆轮询（Round Robin）：顺序循环将请求一次顺序循环地连接每个服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从顺序循环队列中拿出，不参加下一次的轮询，直到其恢复正常。 ◆比率（Ratio）：给每个服务器分配一个加权值为比例，根椐这个比例，把用户的请求分配到每个服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配, 直到其恢复正常。 ◆优先权（Priority）：给所有服务器分组,给每个组定义优先权，BIG-IP 用户的请求，分配给优先级最高的服务器组（在同一组内，采用轮询或比率算法，分配用户的请求）；当最高优先级中所有服务器出现故障，BIG-IP 才将请求送给次优先级的服务器组。这种方式，实际为用户提供一种热备份的方式。 动态负载均衡算法 ◆最少的连接方式（Least Connection）：传递新的连接给那些进行最少连接处理的服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配, 直到其恢复正常。
◆最快模式（Fastest）：传递连接给那些响应最快的服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP 就把其从服务器队列中拿出，不参加下一次的用户请求的分配，直精彩文档．实用标准文案 到其恢复正常。 ◆观察模式（Observed）：连接数目和响应时间以这两项的最佳平衡为依据为新的请求选择服务器。当其中某个服务器发生第二到第7 层的故障，BIG-IP就把其从服务器队列中拿出，不参加下一次的用户请求的分配，直到其恢复正常。 ◆预测模式（Predictive）：BIG-IP利用收集到的服务器当前的性能指标，进行预测分析，选择一台服务器在下一个时间片内，其性能将达到最佳的服务器相应用户的请求。(被BIG-IP 进行检测) ◆动态性能分配(Dynamic Ratio-APM):BIG-IP 收集到的应用程序和应用服务器的各项性能参数，动态调整流量分配。 ◆动态服务器补充(Dynamic Server Act.):当主服务器群中因故障导致数量减少时，动态地将备份服务器补充至主服务器群。 ◆服务质量(QoS）:按不同的优先级对数据流进行分配。 ◆服务类型(ToS): 按不同的服务类型（在Type of Field中标识）负载均衡对数据流进行分配。 ◆规则模式：针对不同的数据流设置导向规则，用户可自行。 负载均衡对应本地的应用交换，大家可以通过对上述负载均衡算法的理解，结合实际的需求来采用合适你的负载均衡算法，我们常用到的一般是最少连接数、最快反应、或者轮询，决定选用那种算法，主要还是要结合实际的需求。
静态负载均衡算法的简单说明 实现的问题： 目前有N个资源Scale1~ScaleN，且这N个资源正在处理个数不等的请求，这时发来M个请求。 如何把M个请求分发到这N个资源中，使得分发完之后这N个资源所处理的请求是均衡的。 名词定义 Scale-资源 Order-请求 compId-每个资源的唯一标识 compId数组-compIdArr 根据每个Scale目前所处理的Order个数多少，从小到大把其对应的compId记录在数组中 负载分配数组-dispatchCountArr 对于dispatchCountArr[i]，它的值表示的是可以分发的Order的个数， 分发的compId的范围是在compIdArr[0]到compIdArr[i]之间。 例，如果有3个Scale，它们的compId和当前的Order个数分别为 Scale1：1，Scale2：5，Scale3：12 那么根据这组数据可以构造一个负载分配数组 dispatchCountArr[0]=(5-1)*1=4 表示可以在Scale1上再分配4个Order dispatchCountArr[1]=(12-5)*2=14 表示可以在Scale1和Scale2上平均分配14个Order dispatchCountArr[2]=整型最大值表示可以在Scale1~Scale3上再平均分配任意个Order 当有多个Order订单，需要为每个都分配一个compId时， 1.先从dispatchCountArr[0]开始，如果dispatchCountArr[0]不为0，说明可以把这个订单指派给Scale1， 并且dispatchCountArr[0]的值减1； 2.如果发现dispatchCountArr[0]已经为0，则继续看dispatchCountArr[1]， 如果大于0，说明可以再从Scale1和Scale2中取一个进行指派，用dispatchCountArr[1] mod 2产生一个0到1 的index，意思是在Scale1和Scale2之间进行平均分配，取compIdArr[index]作为分配的compId， 同时dispatchCountArr[1]减1 3.如果dispatchCountArr[1]也被减为0，那么继续看dispatchCountArr[2]，类似2中的操作， 用dispatchCountArr[2] mod 3产生一个0到2的index，意思是在Scale1到Scale3
奈学：传授“带权重的负载均衡实现算法”独家设计思路 分布式系统中，大部分系统调用都会涉及到负载均衡，例如：客户端发往服务端的请求首先到达反向代理，然后反向代理再通过负载均衡算法将请求转发到业务系统；或者后端业务系统各模块间的调用前，也需要通过负载均衡算法选择到一个目标节点。 一般情况下，我们对负载均衡的要求就是均匀，确保调用方的请求流量能够均匀的发送到我们冗余部署的N个服务节点上，所以负载均衡的算法一般使用随机或轮询都可以保证被调用结点流量的均匀。 真实情况下，往往由于部署服务的服务器性能或资源分配等原因需要我们为服务结点设置不同的权重，权重高的结点可以分配多一些的流量，同时降低权重低的结点的流量比例。 这时负载均衡就不能简单的使用随机或者轮询了，需要添加对权重的支持。接下来我们分析几种带权重的负载均衡算法，并分析一下他们的优缺点： 一、使用随机数 设计思路如下：首先经过负载均衡后选择到一个结点，然后我们根据权重值再做一道拦截，按权重按比例放行，实现按降低结点流量的效果。例如我们规定权重的范围从0到10之间，0拒绝，10放行。权重值越高，分配的流量就越多。 最简单的实现方案，可以使用随机值，假设设置目标结点的权重值为7，当结点被负载均衡选中后，我们生成一个0到10之间的随机数，小于7放行，大于7则不向目标结点发送请求，需要从新做负载均衡计算，由此实现了将目标结点的流量降低到原来的70%。 方案实现起来很简单，但问题也很明显，我们都知道生成随机数的计算会造成CPU的开销，计算权重又发生在RPC调用过程中，所以每次RPC请求都会额外的增加一次随机数计算，累积起来对CPU额外的开销就很大了。我们可以进一步优化一下。 二、随机数组 我们可以使用一个随机数组代替上文描述的生成随机数的策略，实现同样效果的同时能够减少CPU 的计算量。接下来描述下随机数组算法，同样权重设计为0~10。 我们为每个被调用的结点都生成一个随机数组，数组长度为10。空间分配好后用0和1填充数组，0的个数与结点的权重值一样，同时要保证0在数组中出现的位置是随机的。 我们生成一个代表权重为“4”的随机数组（4个0），如下图所示： 和随机数方案类似，我们在完成负载均衡计算后，进行权重拦截。这个时候我们可以通过访问随机数组代替生成随机数的计算，方案描述如下：记录上一次访问随机数组的位置，取数组下一位置元素值，取到0则放行，1则拒绝，重新进行负载均衡计算。方案的思路是，轮询访问随机数组，到达随机效果。因为数组的内容是随机的。 这两种方案思路是一致的，都是在负载均衡计算后再加一道权重拦截。但这样的问题是流量控制不精确，无法实现精确个节点按权重比例分配流量。我们可以换个思路，实现精确的流量控制。 三、轮询加权重负载策略 设计思路如下，设计一个权重因子，初始值为所有被调用的结点中最大权重值。负载均衡使用轮询算法，被选中结点权重值大于等于权重因子则可以调用，否则用下一结点的权重值与权重因子比较，一轮
小区负载均衡算法介绍 1、小区负载均衡算法配置（针对本小区与扩容小区之间） 小区负载均衡算法分为两类PRB利用率负载平衡算法和同步态用户负载均衡算法两种。其中：PRB利用率负载平衡算法用于解决在单个小区PRB利用率受限（达到或者接近满载），同时存在与之重叠覆盖的异频邻区相对低载，算法将一部分负载转移至邻区之后，达到整体PRB利用率之和最大化，从而吞吐率最大化；同步态用户数负载平衡算法用于解决在单个小区用户数受限（由于用户数过多导致整体UE 速率受限），同时存在与之重叠覆盖的异频邻区相对低载，算法将一部分负载转移至邻区之后，达到整体用户速率平均化，从而减少差性用户的比例。笼统地说，PRB利用率负载平衡算法主要用于选大包用户，同步态用户数负载平衡算法主要用于选小包用户。 因为现网用户分布符合类正态分布的特性，即小包用户出现概率大，大包用户出现概率小。所以在现网使用同步态用户负载均衡算法。 同步态用户负载均衡算法关键参数及配置方式如下： InterFreqMlbSwitch：负载均衡总开关，在CELLALGOSWITCH设置，是进行PRB利用率负载平衡算法和同步态用户负载均衡的总开关，打开此开关才可进行复杂均衡。MML：MOD CELLALGOSWITCH:LOCALCELLID=X,MLBALGOSWITCH=InterFreqMlbSwitch-1; MlbTriggerMode：异频负载平衡触发模式，当前算法支持两种模式，三种开启方案：单独打开PRB 负载模式（PRB_ONLY）、单独打开用户数模式（UE_NUMBER_ONLY）和支持两个模式同时打开（PRB_OR_UE_NUMBER），现网配置时使用用户数模式即可。MML：MOD CELLMLB:LOCALCELLID=X,MLBTRIGGERMODE=UE_NUMBER_ONLY； InterFreqUeTrsfType：异频负载均衡转移UE类型。决定转移连接态UE还是释放态UE，区分PRB模式下转移UE连接态还是空闲态，用户数模式下转移UE连接态还是空闲态，一共4个勾选项，可以独立或者同时配置。现网设置SynchronizedUE(同步态用户)、IdleUE(空闲态用户)打开，PrbMlbSynchronizedUE(PRB模式负载均衡同步态用户)，异频空闲态小区PRB 利用率负载平衡算法PrbMlbIdleUE(PRB模式负载均衡空闲态用户)关闭即可。MML：MOD CELLMLB:LOCALCELLID=X，INTERFREQUETRSFTYPE=SynchronizedUE-1&IdleUE-1&PrbMlbSynchronizedUE-0&PrbMlbIdleUE-0； InterFreqMlbUeNumThd：异频负载均衡用户数门限；MlbUeNumOffset：负载均衡用户数偏置。算法高载触发门限，当算法未触发时如果小区同步态用户数大于等于InterFreqMlbUeNumThd + MlbUeNumOffset则触发异频连接态小区同步态用户数负载平衡算法，当算法触发时如果小区同步态用户数小于InterFreqMlbUeNumThd则退出算法。MlbUeNumOffset：负载均衡用户数偏置不需要进行配置，现网默认值20即可。InterFreqMlbUeNumThd异频负载均衡用户数门限设置为小区最大用户数的一半即可。MML：MOD CELLMLB:LOCALCELLID=X，INTERFREQMLBUENUMTHD=（最大用户数/2）; InterFreqLoadEvalPrd:异频负载评估周期，控制算法运行时序，在算法触发之后，负载
大家都知道一台服务器的处理能力，主要受限于服务器自身的可扩展硬件能力。所以，在需要处理大量用户请求的时候，通常都会引入负载均衡器，将多台普通服务器组成一个系统，来完成高并发的请求处理任务。 之前负载均衡只能通过DNS来实现，1996年之后，出现了新的网络负载均衡技术。通过设置虚拟服务地址（IP），将位于同一地域（Region）的多台服务器虚拟成一个高性能、高可用的应用服务池；再根据应用指定的方式，将来自客户端的网络请求分发到服务器池中。网络负载均衡会检查服务器池中后端服务器的健康状态，自动隔离异常状态的后端服务器，从而解决了单台后端服务器的单点问题，同时提高了应用的整体服务能力。 网络负载均衡主要有硬件与软件两种实现方式，主流负载均衡解决方案中，硬件厂商以F5为代表目前市场占有率超过50%，软件主要为NGINX与LVS。但是，无论硬件或软件实现，都逃不出基于四层交互技术的“转发”或基于七层协议的“代理”这两种方式。四
层的转发模式通常性能会更好，但七层的代理模式可以根据更多的信息做到更智能地分发流量。一般大规模应用中，这两种方式会同时存在。 2007年F5提出了ADC（Application delivery controller）的概念为传统的负载均衡 器增加了大量的功能，常用的有：SSL卸载、压缩优化和TCP连接优化。NGINX也支持很多ADC的特性，但F5的中高端型号会通过硬件加速卡来实现SSL卸载、压缩优化这一类CPU密集型的操作，从而可以提供更好的性能。 F5推出ADC以后，各种各样的功能有很多，但其实我们最常用的也就几种。这里我也简单的总结了一下，并和LVS、Nginx对比了一下。 SSL卸载和压缩优化，主要是将CPU密集型的加解密和压缩操作移到负载均衡器上进行；TCP连接优化主要指的是用户和负载均衡器短连接的同时，负载均衡器和后端服务器建立长连接。 不过我们本次主要介绍四层负载均衡，所以这些高级ADC功能不会涉及到。 F5的硬件负载均衡产品又分单机Big IP系列和集群VISRION系列，都是X86架构，配合自研的TMOS（Traffic Management Operating System），再加上硬件加速卡（Cavium 提供）处理SSL和压缩等CPU密集型操作。
为了提高服务器的性能和工作负载能力，天互云计算通常会使用DNS服务器、网络地址转换等技术来实现多服务器负载均衡，特别是目前企业对外的互联网Web 网站，许多都是通过几台服务器来完成服务器访问的负载均衡。 目前企业使用的所谓负载均衡服务器，实际上它是应用系统的一种控制服务器，所有用户的请求都首先到此服务器，然后由此服务器根据各个实际处理服务器状态将请求具体分配到某个实际处理服务器中，对外公开的域名与IP地址都是这台服务器。负载均衡控制与管理软件安装在这台服务器上，这台服务器一般只做负载均衡任务分配，但不是实际对网络请求进行处理的服务器。 一、企业实现Web服务器负载均衡 为了将负载均匀的分配给内部的多个服务器上，就需要应用一定的负载均衡策略。通过服务器负载均衡设备实现各服务器群的流量动态负载均衡，并互为冗余备份。并要求新系统应有一定的扩展性，如数据访问量继续增大，可再添加新的服务器加入负载均衡系统。 对于WEB服务应用，同时有几台机器提供服务，每台机器的状态可以设为regular(正常工作)或backup(备份状态)，或者同时设定为regular状态。负载均衡设备根据管理员事先设定的负载算法和当前网络的实际的动态的负载情况决定下一个用户的请求将被重定向到的服务器。而这一切对于用户来说是完全透明的，用户完成了对WEB服务的请求，并不用关心具体是哪台服务器完成的。 二、使用网络地址转换实现多服务器负载均衡 支持负载均衡的地址转换网关中可以将一个外部IP地址映射为多个内部IP地址，对每次TCP连接请求动态使用其中一个内部地址，达到负载均衡的目的。很多硬件厂商将这种技术集成在他们的交换机中，作为他们第四层交换的一种功能来实现，一般采用随机选择、根据服务器的连接数量或者响应时间进行选择的负载均衡策略来分配负载。然而硬件实现的负载控制器灵活性不强，不能支持更优化的负载均衡策略和更复杂的应用协议。 基于网络地址转换的负载均衡器可以有效的解决服务器端的CPU和磁盘I/O负载，然而负载均衡器本身的性能受网络I/O的限制，在一定硬件条件下具有一定的带宽限制，但可以通过改善算法和提高运行负载均衡程序的硬件性能，来提高这个带宽限制。不同的服务类型对不同的服务器资源进行占用，我们使用的负载衡量策略是使用同一个负载进行评估，这对于大多数条件是适合的，然而最好的办法是针对不同的资源，如CPU、磁盘I/O或网络I/O 等，分别监视服务器负载，由中心控制器选择最合适的服务器分发客户请求。 三、使用DNS服务器实现负载均衡
负载均衡有两方面的含义：首先，大量的并发访问或数据流量分担到多台节点设备上分别处理，减少用户等待响应的时间；其次，单个重负载的运算分担到多台节点设备上做并行处理，每个节点设备处理结束后，将结果汇总，返回给用户，系统处理能力得到大幅度提高。 算法 提供多个WAN ports可作多种负载平衡算法则，企业可依需求自行设定负载平衡规则，而网络存取可参照所设定的规则，执行网络流量负载平衡导引。算法则有： ◎依序Round Robin ◎比重Weighted Round Robin ◎流量比例Traffic ◎使用者端User ◎应用别Application ◎联机数量Session ◎服务别Service ◎自动分配Auto Mode Inbound Load Balancing 内建Inbound Load Balance 功能，可让企业透过多条ISP线路，提供给浏览者更实时、快速与稳定不断线的因特网在线服务； Inbound负载平衡算法包括：Round Robin/ Weighted Round Robin/Auto Back Up； 功能 内建DNS服务器，可维护多个网域(domain)，每个网域又可以新增多笔纪(A/CNAME/MX)，达到Inbound oad Sharing的功能。 ■Server Load Balancing AboCom服务器负载均衡提供了服务级（端口）负载均衡及备援机制。主要用于合理分配企业对外服务器的访问请求，使得各服务器之间相互进行负载和备援。 AboCom服务器负载与服务器群集差异： 一旦有服务器故障，群集技术只对服务器的硬件是否正常工作进行检查；AboCom服务器负载则对应用服务端口进行检查，一旦服务器的该应用服务端口异常则自动将访问请求转移到正常的服务器进行响应。 ■VPN Trunk 负载均衡 支持同时在多条线路上建立VPN连接，并对其多条VPN线路进行负载。不仅提高了企业总部与分支机构的VPN访问速度，也解决了因某条ISP线路断线造成无法访问的问题。进行VPN 负载均衡时VPN访问数据将同时在多条VPN线路上进传输。当一条VPN线路故障时，所有流量将自动切换到正常的VPN线路上进行传输。 QoS（带宽管理） 个人带宽管理：可实现每个人的网络带宽分配、管理，可以设置保证带宽用以保障个人应用不受整体环境影响。每日带宽配额：可以针对个人、群组或部门等分别设置带宽配额，这样可以
第33卷第10期重庆大学学报 V ol.33N o.10 2010年10月Jour nal of Cho ng qing U niv ersity Oct.2010 文章编号:1000 582X(2010)10 102 08 网格负载均衡策略及其蚁群优化算法 陈乙雄1 ,吴中福1 ,朱郑州 2 (1.重庆大学计算机学院,重庆400044;2.北京大学信息科学技术学院,北京100871) 摘 要:以重庆大学CampusGrid 建设和加入ChinaGr id 的发展规划为背景,研究了多网格环境中出现共用节点(即同时为多个网格系统服务的节点)时资源利用率下降问题,并针对该问题提出了以提高资源利用率为优化目标的负载均衡算法。主要分为问题模型建立、算法设计、以及实验评估3个部分。提出的算法能较好解决该问题,并考虑了网络通信开销对算法执行效果的影响。实验表明,提出的算法能有效防止网格中出现共用节点时资源利用率的下降,并对网格动态变化的特性具有较强的适应能力。 关键词:网格;负载均衡;蚁群优化;任务调度 中图分类号:T P393 文献标志码:A Load balancing strategy and ant optimization algorithm for grids CHEN Yi xiong 1,WU Zhong fu 1,ZH U Zheng zhou 2 (1.College o f Co mputer Science,Chongqing University,Chong qing 400044,P.R.China;2.Schoo l of Information Science and T echno logy ,Beijing Univer sity,Beijing 100871,P.R.China)Abstract:In view of the Cam pus Grid construction,w hich is also a crucial part of ChinaGr id project,the performance decline for grid scheduling algor ithms w hen no n dedicated nodes em er ge in m ulti grid environment is studied.A lo ad balancing algorithm to optimize r esource usage r ate is pro posed.T he paper invo lves three parts:problem m odeling,alg orithm design,and experiment evaluation.T he ex perimental results show that the proposed algo rithm is effectiv e fo r solving the problem o f resource usag e rate decline under the discussed grid circumstance. Key words:g rid com puting;load balance;ant colo ny optim ization;task scheduling 近年来,在高性能计算领域,网格逐渐成为超级计算机以外的另一种选择。由于网格系统中的各节点通常在地理位置上比较分散,而且具有平台异构、跨管理域等特点,因此如何将网格任务在这些节点上进行合理的分配并保证执行效率成为网格研究的1个重要方面[1] 。 1 网格及其负载均衡问题 调度算法是网格资源分配的核心。然而,由于网格动态变化的特性,即使采用了比较先进的调度算法,网格任务在各个节点上的部署仍有可能出现分布不均的情况,从而导致系统资源利用率下降。