面向高并发民航业务的动态负载均衡设计

田　丰　倪兆阳　丁建立　王　静

1(中国民航信息网络股份有限公司研发中心　北京 100000)2(中国民航大学计算机科学与技术学院　天津 300000)



面向高并发民航业务的动态负载均衡设计

田丰1倪兆阳2丁建立2王静2

1(中国民航信息网络股份有限公司研发中心北京 100000)2(中国民航大学计算机科学与技术学院天津 300000)

针对民航业务实时并发请求多、业务功能复杂、数据量大的特点，简要介绍当前业务系统的总体结构和负载均衡机制，分析现有负载均衡算法的优点和不足。为了提高民航业务系统的鲁棒性和可靠性，根据其软硬件结构特点在原负载均衡机制的基础上提出改进的动态负载均衡策略。同时设计维护负载度量指标所需的数据结构以及在这种数据结构下维护该指标的方法，并进行实验对比验证。实验结果表明，动态负载均衡策略能够更好地应对高并发复杂网络环境，使系统的鲁棒性和可靠性得到提升。

动态负载均衡高并发民航分布式

0　引　言

随着经济社会的发展，航空运输变得越来越普及。2014年中国民航旅客运输量已经达到3.9亿人次，排名世界第二。互联网的迅猛发展也使越来越多的人从网络渠道获得关于航班的各种信息。以民航旅客服务信息系统中目前为止最大规模的服务器集群DIP(Data Integration Platform)来说，其吞吐量持续峰值已经达到10 000 TPS，日处理消息量在2亿条左右。这意味着越来越多的民航业务要由信息系统处理，系统负载量大幅增加。

民航旅客服务信息系统的运行状况不仅仅关系到提供给地面用户的服务质量，还涉及到空中的交通安全和全国各航空公司的飞行计划安排，一旦出现差错将造成大量的旅客滞留和航班延误，其损失是不可估量的。这就要求民航旅客服务信息系统能够良好地应对高并发高负载环境。提高现有信息系统对高并发、动态变化、连续高可靠性的适应能力以及对其他需求的应对能力成为当前的重要任务。

民航旅客服务信息系统属于大规模分布式系统。在分布式环境下，系统中往往有多个处理能力各不相同的节点，而且请求的到达以及请求的复杂性都是随机的。如果一味地将请求全部分配给系统内某一台服务器，则不但会造成该服务器负担过重容易崩溃而且也没有充分利用系统资源[1]。单台服务器处理能力的提高是有限度的，所以如何对请求进行分流，实现灵活的负载均衡，从而达到对整个分布式系统高效利用的目的成了企业亟需解决的问题。

1　负载均衡分类与现状

负载均衡大体上可以分为静态负载均衡和动态负载均衡两大类[2]。

静态负载均衡通常以网络流和启发式算法为理论基础，依据分布式网络中的静态指标来进行请求分流。网络流法是一种重要的计算机图论方法，使用最大流最小割算法求解[3]。Stone研究了将计算开销和服务器之间的通信开销考虑在内情况下的请求分流问题，使用最大流最小割算法给出了具有两个处理器的系统中的最优分配方案，但是没有给出具有多个处理器情况下的解决方案[4]。Bokhari研究了双处理器系统中的动态分配模型，并对Stone的研究进行了扩展，使其能够解决任务通信图为树形结构的请求分流问题。Towsley又进一步研究，将Bokhari的成果推广到了串并联通信图结构[5]。静态负载均衡算法固然有其自身的优势，但是系统静态指标或历史经验数据不能动态反映分布式系统负载情况的变化，所以静态负载均衡不能根据实际情况动态调整负载策略[6]。

动态负载均衡算法以服务器的实时负载状态信息来决定任务的分配，其负载策略由当前系统状态决定[7]。研究者在近些年提出了许多动态负载均衡算法，按照算法的控制位置特征这些算法大致可以分为分布式、集中式和混合/层次三类。分布式负载均衡算法的基本策略就是邻近法，每一台服务器与邻近的服务器交换负载，并通过多次迭代达到全局负载均衡。比如Kolb等针对MapReduce可能产生的节点瓶颈问题提出了基于块的负载均衡算法BlockSplit。集中式负载均衡算法中，处于逻辑上中心位置的节点收集所有其他节点的负载情况，根据全局的负载信息做出决策。比如GreedyLB算法在全局范围选取一个当前负载量最小的服务器，将负载分配给它。为了减小负载均衡算法的系统开销，一些算法重点研究了如何根据服务器网络的拓扑结构来构建一个层次树的问题。在此基础上将服务器划分为多个域，每一层在相邻域之间进行负载均衡，并且在层间执行负载均衡，最后达到全局负载均衡的目的，这样的负载均衡算法称为混合/层次负载均衡算法。比如Wang等根据ZEUS网络框架和云计算结构特征，提出了一种具有三级层次拓扑结构的两阶段负载均衡算法[8]。通常情况下，动态负载均衡相对于静态负载均衡能够有30%～40%的性能提升[9]。

2　JCF总体结构

2.1整体结构

JCF(Java Core Framework)中间件平台是民航旅客服务信息系统的重要组成部分，它运行于分布式环境下，面对着不同的硬件平台、操作系统和异构的网络环境。它通过适配服务的方式来解决JCF平台内部业务服务与现有企业服务总线对接的问题，以及通过企业服务总线访问JCF平台内部业务服务时所需要的负载均衡、资源隔离、故障隔离等需求。

JCF平台由开发工具、运行系统、管理工具三大部分组成，为业务服务的开发、部署、运行和维护提供完整的支持。

其中运行系统的功能可以分为两个层次，如图1所示。

图1　JCF运行系统层次

服务层为应用支撑框架，允许用户使用Java语言创建核心业务逻辑，然后使用JCF提供的流程配置工具将核心业务逻辑编排成可以独立部署和运行的业务服务。平台采用SEDA架构，其中每个服务为一个阶段，每个阶段含有一个资源控制器，根据本阶段的负载情况动态调整资源配置。阶段之间的调用由JCF系统的服务调用平台负责。

调用层为分布式服务调用平台，为服务之间的相互调用提供基本支撑，包括SEDA 异步调用、负载均衡、故障隔离、自动寻址等功能。对业务应用的开发者来说它是“透明”的。

2.2负载均衡机制

JCF的负载均衡机制位于服务调用方的拦截器中，作为拦截链的一个Handler存在，叫做LoadBalanceHandler。LoadBalanceHandler从属于服务调用者，调用负载均衡器LoadBalancer选择服务实例。LoadBalancer是独立于拦截器Handler而单独存在的，是对负载均衡算法的抽象，如图2所示。

图2　负载均衡器

每一个LoadBalancer实例都是当前服务器中的某一个被调用服务的负载均衡算法的抽象。其中主要的方法是chooseServer，用来选择一个服务器处理当前请求。ServiceInstance是对服务实例的抽象，其中封装了服务实例所在服务器的主机地址和端口。ServerMetaInfo是用来描述服务器的对象。AbstractRule是所有负载均衡算法的抽象基类。ConsistentHashingRule是一致性哈希算法。WeightedRoundRobinRule、LeastPendingRequestRule是不同策略的随机负载均衡算法。当负载均衡逻辑选择服务实例时抛出异常时，根据指定的环境变量，决定中止调用并返回错误信息，或者使用父类的随机负载均衡算法RandomRule随机选择一个服务实例。

负载均衡器是在客户端的服务器，由于在一台服务器上有可能存在多个服务作为某个服务的客户端，因此需要建立一个被调用服务的唯一的负载均衡器。JCF平台采用工厂模式创建负载均衡器，LoadBalancerFactory是负载均衡器的工厂类，便于扩展新的负载均衡策略；LoadBalanceManager作为负载均衡器的管理者，负责保存服务器内共享的唯一的负载均衡器，如图3所示。

图3　负载均衡器的管理机制

在当前JCF平台的固定比例因子负载均衡算法中，负载均衡的Handler通过LoadBalanceManager调用LoadBalanceFactory创建LoadBalancer的实例，并调用chooseServer()方法选择接收请求的服务器。而在chooseServer()方法中依赖服务注册库维护的LoadFactorMap和LoadbalancerInfo按照固定比例因子算法选择服务器。其中LoadBalanceInfo用来保存一个服务的固定比例因子的负载均衡信息，包括服务实例列表和根据比例因子计算出的最大值、最大公约数、轮转周期、轮转列表，以及表示轮转列表当前位置的的下标。LoadFactorMap是维护服务注册库信息和LoadBalanceInfo的类，当服务实例增加或减少时，重新计算固定比例因子的轮转列表，并设置到LoadBalanceInfo中。

例如某个JCF域内含有3台JCF服务器，负载均衡因子分别设置为1、2、3。假设请求处理速度远远小于请求到达速度，当有60个请求同时到达时这些请求将会以3∶2∶1 的比例被分配给域内3台服务器。

该算法属于静态负载均衡算法，实现简单且复杂度低，符合算法设计原则。但是其比例因子只能根据机器性能和以往经验由人工设定，在运行过程中不能根据负载情况的变化实时调整策略。如果运行过程中某台服务器负载过大，该状况并不能为负载均衡算法所察觉，仍然会按照固定比例向其发送请求，而不能让其他运行状况尚良好的服务器多分担请求。所以该算法的灵活性欠佳，需要对其进行改进。

3　动态负载均衡设计

为了改善负载均衡算法的灵活性，新的算法采用动态负载均衡策略，以未完成请求数为负载度量指标，循环服务列表中的每一个服务实例，选择未完成请求数最低的服务实例处理请求。

3.1未完成请求数的维护

国际民航系统间报文交互基于IATA所定义的国际规范,该规范分TYPE-A和TYPE-B两种类型，其中TYPE-A属于Request-Reply模式，TYPE-B属于One-way模式。JCF平台提供了基于这两种模式的负载均衡机制。未完成请求数的维护方式取决于消息传输模式：

1) 在One-way模式下，使用服务端的队列深度。当收到服务端的Signal信号时，将相应服务实例的指标值更新为信号中携带的请求队列深度。

2) 在Request-Reply模式下，使用客户端维护的指标。当负载均衡Handler选出服务器后，对该服务实例的未完成请求数加1；当收到服务端的应答消息时，对相应服务实例的未完成请求数减1；当收到超时信号时，由于同一个请求消息收到超时信号后就不会再收到应答消息，所以对相应服务实例的未完成请求数减1。

在Request-Reply模式下客户端需要按照一定的时间窗口进行计数。只计算指定长度时间窗口内的请求数，在时间窗口内分为不同的刻度分别统计，每过一个刻度，就抛弃窗口外的计数，这样就完成了对超时请求数的抛弃。

3.2未完成请求数的统计

统计过去s个时间单位的未完成请求数的算法，可以表述为获取当前时间t以前s个时间单位(μ)的未完成请求数reqno之和：

未完成请求数的统计需要使用一个适当的数据结构，然后处理好三个问题：

1) 当请求发出时，使未完成请求数加1；

2) 当应答收到时，使未完成请求数减1；

3) 当需要统计时，统计出指定时间范围内的未完成请求数之和。

3.3数据结构

在计算机中模拟这一统计过程只需关心s个时间单位内的未完成请求数，所以给每个服务实例定义一个包含s个结点的线性表。每个结点代表一个时间窗口，即一个时间单位，其中保存建立该结点时的时刻time以及一个时间单位内的未完成请求数reqno(使用原子数据类型)。新的结点加在后面，当加入新的结点时，各结点依次前移，把时间最久远的结点抛弃，如图4为一个s=5的数据结构。

图4　数据结构

3.4增加未完成请求数

假设采用结构数组方式实现该数据结构，命名为cell。同时假设当前时刻为t，如果t-cell[s-1].time<μ，则cell[s-1].reqno=cell[s-1].reqno+1。

设μ=1,t=25.74时，格子的内容如下所示：

判断条件25.74-25<1成立，则cell[4].reqno=1+1=2。

如果t-cell[s-1].time≥μ，则首先需要滑动时间窗口，再进行未完成请求数的累计。

3.5滑动时间窗口

再按照t-cell[s-1].time<μ的情况进行增加请求数操作，如下所示：

3.6减少未完成请求数

对于非血运重建患者，基于多项临床试验及荟萃分析[3-5]显示：SCAD患者若无禁忌证，建议阿司匹林100mg/d长期治疗，若不能耐受阿司匹林，建议服用氯吡格雷75mg/d或替格瑞洛 60mg 2次/d～90mg 2次/d；血栓高危患者如心肌梗死病史且伴有1项危险因素：年龄65岁以上、糖尿病、2次心肌梗死、多支病变、肾功能异常(肌酐清除率<60ml/min)，且出血风险较低的患者可考虑采用阿司匹林联合替格瑞洛(60mg 2次/d)长期治疗，治疗期间严密监测出血。

假设μ=1,t=27时窗口的内容如下所示：

3.7统计未完成请求数

设当前时间为t，如果t-cell[s-1].time<μ，那么只需要对当前的数据结构进行累积：

int acc = 0;

for(int i = 0; i < s; i++) {

acc += cell[i].reqno

}

如果t-cell[s-1].time≥μ，也就是说没有最近一个时间单位的未完成请求数，那么首先需要滑动时间窗口，然后再按上述方式进行统计。

3.8负载均衡算法

对上述未完成请求数维护方法进行分析，发现不论是发出请求还是收到应答均需要判断是否需要滑动时间窗口。如果滑动了时间窗口，还需要对每个服务实例的总体未完成请求数进行更新以提供负载均衡操作所需要的最新参考指标。对各种操作归纳总结，提炼出公共操作后绘制出算法流程如图5所示。

图5　算法流程图

针对上述数据结构特点，分析负载均衡流程，设计出Request-Reply模式下的动态负载均衡算法：

a) 计算当前时刻t与最近的时间窗口所记录的时刻的差值Δt=t-cell[s-1].time；

b) 判断Δt是否大于一个时间单位μ，若是则转到步骤c)，否则转到步骤e)；

e) 判断事件类型，若为发出服务请求则转步骤f)，否则转步骤h)；

f) 遍历所有服务实例的未完成请求数，选择其中的最小值summin；

g) 对第min个服务实例的最近一个时间窗口的未完成请求数加1，即cell[s-1].reqno=cell[s-1].reqno+1，然后对summin加1，算法结束；

i) 判断pos是否大于0，若是则转步骤j)，否则算法结束；

j) 从应答消息中得到服务实例编号back，对第back个服务实例的第pos个时间窗口的未完成请求数减1，即cell[pos].reqno=cell[pos].reqno-1，然后对sumback进行减1操作，算法结束。

4　实　验

本节给出了采用动态负载均衡算法的服务器集群和采用固定比例因子负载均衡算法的服务器集群的性能对比实验结果。两个服务器集群cluster1和cluster2均部署JCF平台，通过适配服务接收服务总线上的请求消息。两个集群内均含有3台业务服务器和1台适配服务器，其中业务服务器上均部署有serviceA和serviceB两种业务服务，适配服务器上部署适配服务adapterService。serviceA用来模拟简单业务服务，不设置延迟；serviceB用来模拟复杂业务服务，其延迟时间设置为3秒。如图6所示。

图6　实验场景

两个集群的服务器配置相同，具体配置信息如下：

• Intel(R) Xeon(R) CPU X7550 @ 2.00 GHz；

• 8 GB RAM；

• Red Hat Enterprise Linux Server release 6.3 (Santiago)；

• SUN JDK Version 1.6.0_10。

其中cluster1采用动态负载均衡算法，cluster2采用固定比例因子负载均衡算法，比例因子设置为1∶1∶1。按照JCF平台的处理机制，当请求消息在服务总线上出现后，将由适配服务负责获取该消息，然后执行负载均衡算法选择集群内的一台服务器，将请求交由该服务器进行处理。

实验环境搭建完成后用客户端程序向服务总线持续发送serviceA的请求消息，发送间隔为3毫秒，该操作模拟民航请求中并发量大，同时处理速度较快的航班可售库存查询。第30秒钟时发送一条serviceB的请求消息，模拟民航请求中随时可能出现的业务功能复杂的运价搜索或航班计划创建请求。运价搜索请求的处理需要在多条航路中综合判断以返回符合搜索条件的结果，该过程会涉及到多航段排列组合进行运价计算；而航班计划创建会对原有航班计划产生连锁影响，需要进行大量计算以安排出新的计划表。这两种请求都会耗费大量服务器资源，降低服务器吞吐率。实验过程持续90秒钟，结束后统计出两个服务器集群的TPS数和集群内各台服务器的TPS数，截取其中15秒钟的数据绘制成如图7-图9所示。

图7　cluster1内各服务器TPS

图8　cluster2内各服务器TPS

图9　集群TPS

从图中可以看出，在第30秒时两个集群中均有一台服务器的TPS数突然下降，这是由于请求消息中出现了对serviceB的请求，该请求会占用大量服务器资源，导致其TPS数下降。不同的是cluster1内另外两台服务器的TPS数在此种情况下出现了上升，集群TPS保持稳定；而cluster2内另外两台服务器的TPS数没有明显变化，集群TPS出现下降的情况。这说明动态负载均衡起到了应有的作用，在集群内某台服务器执行了运价搜索或航班计划创建之类的复杂请求。队列中出现积压请求消息的情况后，动态负载均衡算法根据各台服务器未完成请求数的情况自动将新接收到的请求多分发给另外两台负载较小的服务器，从而使集群TPS不受影响或受影响较小。而固定比例因子负载均衡算法则不论服务器负载情况变化，只能按照设定好的比例因子将请求按比例发送给各台服务器，集群TPS会因此受到业务复杂程度的影响。

5　结　语

在分布式系统中，负载均衡的目的是根据各台服务器的性能指标和负载情况来分配请求[10]，服务器的处理能力和当前未完成请求数是负载均衡算法所要参考的重要指标[11]。未完成请求数是一个动态变化的指标，维护该参数首先需要设计一种动态度量策略，该策略要良好地适配系统结构和工作机制，以准确地反映系统中负载的变化情况。负载均衡算法是负载均衡策略的核心，在设计时要减小复杂度，避免负载均衡算法成为系统性能瓶颈[12]。

本文针对JCF平台的结构特点设计了动态负载均衡算法。该算法用一种窗口式的数据结构维护每个业务实例的未完成请求数，并且用滑动窗口的方式完成超时请求的自动丢弃。在此基础上以业务实例的未完成请求数为度量指标，将请求分发到负载量最小的服务器上，最大程度减少民航业务复杂度的变化对集群吞吐率的影响。这增强了JCF平台的鲁棒性，使JCF平台在高并发、复杂程度动态变化的民航业务环境下保持稳定的性能。

[1] 尤天舒. 基于Agent的集群负载均衡模型及其实验研究[D].吉林大学,2014.

[2] 王红斌. Web服务器集群系统的自适应负载均衡调度策略研究[D].吉林大学,2013.

[3] 晋英豪. 异构网络中负载均衡和资源分配策略研究[D].中国科学技术大学,2015.

[4] 胡杨. 虚实结合框架下负载均衡服务集群的研究与实现[D].浙江大学,2015.

[5] 陈涛,肖侬,刘芳. 对象存储系统中自适应的元数据负载均衡机制[J]. 软件学报,2013,24(2):331-342.

[6] 弭伟. 基于DHT的分布式网络中负载均衡机制及其安全性的研究[D].北京邮电大学,2012.

[7] 吴和生. 云计算环境中多核多进程负载均衡技术的研究与应用[D].南京大学,2013.

[8] 杨际祥. 并行与分布式计算负载均衡问题研究[D].大连理工大学,2012.

[9] 周莹莲,刘甫.服务器负载均衡技术研究[J]. 计算机与数字工程,2010,38(4):11-14,35.

[10] 尚志浩.OpenFlow网络中服务器负载均衡的研究[D].兰州大学,2014.

[11] 吴宇文.基于OpenFlow的网络负载均衡算法的研究与设计[D].华东师范大学,2014.

[12] 周松泉.一种新的服务器集群负载均衡算法[D].南昌航空大学,2012.

DYNAMIC LOAD BALANCE DESIGN FOR HIGH CONCURRENCY CIVIL AVIATION BUSINESS

Tian Feng1Ni Zhaoyang2Ding Jianli2Wang Jing2

1(ResearchandDevelopmentCenter，TravelSkyTechnologyLimited,Beijing100000,China)2(SchoolofComputerScienceandTechnology，CivilAviationUniversityofChina,Tianjin300000,China)

For the features of civil aviation business such as a lot of real-time concurrent requests, complicated business functions and large data amount, we briefly introduced the overall architecture and load balance mechanism of current business system, and analysed the merits and drawbacks of existing load balance algorithm. To promote the robustness and reliability of civil aviation business system, we put forward an improved dynamic load balance strategy based on the original mechanism in accordance with the software and hardware feature. Meanwhile we designed a new data structure required for maintaining the load measurement indicators and the relative method to maintain such indicator in this structure, and carried out experiment for contrast verification. Experimental result indicated that the dynamic load balance strategy could cope well with high concurrency and complicated network environment, which promoted the robustness and reliability of the system.

DynamicLoad balanceHigh concurrencyCivil aviationDistributed

2015-07-06。民航局科技创新引导资金专项(MHRD 20130106，MHRD20140106，MHRD20150107)；中国民航大学中央高校基金项目(3122014P004，3122014C016)。田丰，工程师，主研领域：中间件及云计算架构。倪兆阳，硕士生。丁建立，教授。王静，讲师。

TP319

A

10.3969/j.issn.1000-386x.2016.10.001