基于对象复制机制的Web服务动态容错算法

唐金辉， 钟 诚， 吴惜华， 莫英红， 李效鲁， 林 瑞

(广西大学计算机与电子信息学院，广西南宁 530004)

0 引 言

在诸如Web服务这种分布式计算环境中，许多系统采用对象复制技术来提高可用性。基于对象复制的容错算法主要分为active复制和p rimary-backup复制2类[1]。在active算法中，所有的副本同时响应客户的请求，当有副本失效时，其余副本在失效副本缺席的情况下继续正常工作;它处理请求的速度快、失效恢复时间短，但是耗费系统较多资源。在primary-backup算法中，副本分为主副本和备份副本2种，只有主副本接受和处理客户的请求，当主副本失效时，从备份副本中选一个升级为主副本，继续向客户提供服务，因此，其请求处理时间和失效恢复时间长，系统负载不平衡，但是节约了系统资源。

已有的Web服务容错算法大多只是对 active和prim ary-backup算法进行某方面的改进，很少致力于研究提高算法的性能[2]。文献[3]提出了用Sem i Active方法来解决active算法中服务状态的确定性问题。文献[4]通过改变p rimary发送更新信息的时间和频率来对 primarybackup算法进行改进。文献[2]提出的RRR算法虽然使请求处理速度变快，但它是在牺牲可用性的基础上获得的。文献[5]则探讨了基于主动复制容错技术的负载平衡层次模型。文献[6]将组合Web服务选取问题转化为最长路径选取问题，给出了一种双向动态规划的求解策略。

本文给出一种基于对象复制机制的Web服务动态容错算法(dynam ic object replication，简称DOR)，它的主要思想和贡献是:①通过动态改变执行请求的副本成员数，来缩短请求的响应时间，但又不过多地占用系统资源;②算法根据副本的系统负载和网络延时情况，动态选择副本来执行请求，既提高请求的处理速度又实现负载平衡;③在不改变算法可用性的前提下，加快请求处理速度。

1 系统模型

本文给出的算法是基于分布式面向对象系统设计的，系统中有多个相互连接的主机，主机之间通过广域网进行通信。服务有2种失效类型[7]: fail-stop类型和拜占庭类型。系统向客户提供的每一个服务对象均由分布在不同主机上的副本来实现，而这些实现同一个服务对象的各个主机上不同的副本构成一个相应副本组，组中的每个副本称为组的一个成员。

本文在文献[8]中的系统框架基础上，给出一个改进的DOR复制算法框架，它主要由Administrator、Object Manager(OM)、Rep lica Manager (RM)和Result Agent(RA)4个模块组成，如图1所示。

图1 DOR复制算法框架

图1中OM模块的主要工作是管理服务副本组、分发和管理客户请求。客户申请某个服务时向相应的OM发送服务请求，由它将请求转发给副本组中所有的成员。因此，对于客户而言，整个服务的过程是透明的。为了实现相应的管理功能，OM拥有2个列表:客户请求列表(request_ list)和副本组列表(rep lica_list)，其中客户请求列表存储了客户发送过来的请求编号、客户名、方法名、参数和请求类型等请求信息，副本组列表存储的是其管理成员的主机地址和状态信息。

RM模块的主要工作是负责接受OM发送过来的请求并根据一定的机制决定是否执行客户的请求，以及把返回的结果发送给OM。RM驻留在每一个副本组成员所在的主机上，并且含有主机当前的负载情况(current_load)、负载阈值(max_load)、网络延时情况(current_delay)和延时阈值(max_delay)以及等待执行的请求队列(instance_queue)、等待队列(w aiting_queue)和结束列表(executed_list)。当RM接受到某个请求后，根据当前主机的负载情况和网络延时情况，来决定是否马上执行此请求，并把暂时不能执行的请求放入等待队列。

Administrator模块通过不断地向 OM 和RM发送检测请求来监控整个系统以及其中各个副本和主机的情况，并对失效的OM和RM进行恢复。RA模块负责接受从OM传送过来的请求的结果，将处理的最终结果发送给客户，并把更新信息返回给OM。针对服务的拜占庭失效，RA会根据客户自定义的测试机制对结果进行处理。

2 Web服务动态容错算法

算法的核心思想是，副本组中每个成员都接受OM模块发送过来的请求，但并不是所有的副本都立即执行请求，而是根据成员的系统负载情况和网络延时情况来决定是否执行。因此，随着系统负载和网络延时的变化，副本中处理请求的成员也会动态变化。OM模块在接收到客户发送来的请求后，把请求放入客户请求列表中，并向副本组中的每个成员发送这个请求。每个成员的RM收到请求后，就根据主机的系统负载和网络延时情况决定是否执行请求，如果系统负载比较轻而且网络延时比较低，那么立即创建一个新线程来处理请求，否则就按照FIFO的顺序将请求放入等待执行请求队列中。当副本处理完请求后，将结果发送给OM，OM再把结果发送给RA统一处理，RA将处理过的最终结果发送给客户。有些客户的请求是写请求，会改变副本的状态，因此RA会返回一个更新信息来维护各个副本的状态一致性。

系统中共有5种信息类型:

(1)request_message(RequestId，M ethod-Name，parmeters，Reqest_Type)，表示客户发送给OM和OM发送给RM的请求信息。

(2)reponse_message(RequestId，Result，Reqest_Type，update)，这是副本组成员发送给OM和OM发送给RA的信息。

(3)receipt_message(RequestId，Reqest_ Type，update)，这是将处理结果发送给客户后，RA发送给OM的确认信息。

(4)executed_message((RequestId)，表示OM发送给RM的请求执行结束的信息。

(5)update_message(RequestId，update)，表示OM发送给RM的状态更新信息。

2.1 OM模块算法

OM模块的主要工作是管理服务副本组、分发和管理客户请求:

(1)当接收到客户发送过来的请求信息后，先在request_list中添加一个记录，然后把请求广播给所有的副本组成员。

(2)当接收到某个副本发送过来的应答信息，直接发送给RA处理。

(3)当接收到RA发送过来的确认信息后，如果请求类型是写操作，那么生成一个更新信息并发送给所有的副本组成员;否则，生成一个结束信息发送给所有的成员。

OM模块算法如下:

2.2 RM模块算法

RM模块在接受到信息后，根据不同的信息做出相应的处理:

(1)当接收到OM发送过来的请求信息后，根据主机的系统负载和网络延时情况，决定把请求信息放入等待队列还是执行等待队列。也就是说，如果主机系统负载值小于负载阈值，并且网络延时值也小于延时阈值，那么将请求放入执行等待队列;否则，将请求放入等待队列。

(2)当接收到副本发送过来的请求处理结果后，搜索结束列表是否有与其相同ID的结束信息。如果有，那么丢弃这个结果;否则，在列表中添加一个新的结束信息并将结果发送回OM。

(3)当接收到OM发送过来的结束信息后，搜索等待队列是否有与其相同ID的结束信息。如果有，那么删除此请求信息并添加新的结束信息到结束队列;否则，搜索结束列表是否有与其相同ID的结束信息，如果有则丢弃该结束信息，若没有则将该结束信息添加进结束队列。

(4)当接收到OM发送过来的更新信息后，搜索等待队列是否有与其相同ID的结束信息。若有则将更新信息替换此请求信息;否则搜索结束列表是否有与其相同ID的结束信息，如果有则丢弃该更新信息，没有则将新的结束信息添进结束队列。

RM模块算法如下:

2.3 组成员失效的处理

因为DOR复制算法中每一个副本都可以参与客户请求的处理，所以个别或部分副本组成员的失效并不会影响整个算法的执行，只有当所有的成员同时都失效时，才会对算法的进程有影响，但是并不影响算法的正确性。当检测到某个副本失效时，Administrator将根据其它副本的状态和请求列表对失效副本进行恢复。

2.4 算法分析

2.4.1 一致性分析

副本组中成员的状态都由它处理过的请求来决定，在算法中每个成员都按照相同的顺序接收OM发送过来的请求，并按照相同的顺序处理请求。RA在选举出最终结果后，会返回一个确认信息receip t_message给OM。本算法对写操作和读操作分别进行处理，当请求是读操作时，OM在接收到确认信息后只返回一个结束信息executed_message给每个成员;而如果是写操作时，OM返回一个更新信息update_message给每个成员。因为读操作并不会改变成员的状态，所以只对处理写操作的部分进行分析。在成员接收到更新信息时，它可能处于正在、已经或者尚未处理该请求3种情况。当成员正在处理该请求时收到更新信息，添加一个结束信息到结束队列。请求处理完毕后，若发现结束队列中存在该请求的结束信息，则丢弃该处理结果，此时该成员与其它成员状态一致。对于已经处理完请求的情况，算法直接丢弃该更新信息，此时该成员与其它成员状态一致。当成员尚未处理该请求时，算法将更新替换请求信息，成员执行完更新信息后，也与其它成员状态一致。综上所述，本文的算法能够保证副本组中的每个成员状态保持一致。

2.4.2 性能分析

主要对DOR复制算法与active复制算法、primary-backup复制算法的平均响应时间进行分析比较。

假设系统中副本组有n个成员，成员失效的概率为f，检测失效的时间为t t，恢复失效副本的时间为t r，正常成员执行一个请求的平均时间为t e。这样，Web服务容错复制算法的平均响应时间为:

其中，f n为系统正常工作的概率;t为请求的平均执行时间;ff为系统出现故障的概率。

在active复制算法中，每个副本都响应客户的请求，系统中只要有一个正常成员，客户请求就可以得到响应，因此，系统正常工作的概率为1-f n;t a为active算法中正常执行请求的平均响应时间，因此，active复制算法中请求的平均响应时间为:

在p rim ary-backup复制算法中，所有请求都由主副本串行执行，系统正常工作的概率为1-f，t p为primary-backup算法中正常执行请求的平均响应时间，因此primary-backup复制算法中请求的平均响应时间为:

在DOR复制算法中，系统正常工作的概率与active复制算法一样，t d为DOR复制算法中正常执行请求的平均响应时间，因此DOR复制算法请求的平均响应时间为:

通过以上的分析比较可知，¯t p≥¯t a和¯t p≥¯t d;而¯t a和¯t d之间的关系可以通过比较 t a和t d得出。对于active复制算法，t a是由所有成员处理请求所需时间的最大值决定，因为结果的协调需要等待所有的成员都处理完请求之后才能进行。DOR复制算法根据系统的负载和网络延时的情况选择轻载的成员处理请求，并把处理结果返回给客户，而不必等待所有成员都处理完请求，因此t d是由这些被选择的成员的处理时间最大值决定的。这些表明，t a≥t d，即¯t a≥¯t d。因此，DOR复制算法的请求平均响应时间是以上3种复制算法中最短的。

3 实 验

实验平台为Pentium IV CPU 3.0 GH z、512M B RAM的HP个人计算机，运行的操作系统是Red Hat Linux 9.0，使用NS2对DOR复制算法进行仿真实验。在实验中，利用NS2的网络组件进行广域网的仿真，并直接从TclOb ject类继承类ObjectRep lication来表示对象复制算法的组件，通过继承App lication类来生成客户端与服务器端程序的仿真程序。在此基础上，分别对DOR复制算法、active复制算法和primary-backup复制算法进行仿真实验性能对比。

在副本冗余为3且无失效的情况下，DOR复制算法、active复制算法和primary-backup复制算法的平均响应时间随请求频率变化的结果，如图2所示。

从图2可以看出，随着请求频率的增加，请求的响应时间也逐渐加大，与active复制算法、pri-mary-backup复制算法相比，DOR复制算法无论在轻载还是重载的情况下，其响应速度最快、所需的响应时间最短，这与性能分析的结果一致。

图2 3种算法响应时间随请求频率的变化

当请求频率为20/s且副本冗余为5时，DOR复制算法、active复制算法和primary-backup复制算法的平均响应时间随副本失效率变化的情况，如图3所示。

图3 3种算法响应时间随副本失效率的变化

从图3可以看出，随着副本失效率的增长，3种算法的请求响应时间也逐渐加大，其中本文的DOR复制算法的响应时间最低，p rimary-backup复制算法受失效率的影响最大，这与性能分析中各算法平均响应时间的结果是一致的。

当请求频率为20/s且副本冗余为5时，DOR复制算法、active复制算法和primary-backup复制算法的平均响应时间随失效副本数量变化的情况，如图4所示。

图4的结果表明，随着失效副本数量的增加，p rim ary-backup复制算法响应时间增幅最大。这是因为primary-backup复制算法需恢复失效副本进行才能正常工作，而其它2个算法不需要对失效副本进行恢复也能正常工作，因此，副本的失效对DOR复制算法和active复制算法响应时间的影响较小。

图4 3种算法响应时间随失效副本数量的变化

4 结束语

本文提出的基于对象复制机制的Web服务动态容错算法，能根据副本的系统负载和网络延时情况，动态改变执行请求的副本成员数，在不浪费系统资源和不改变算法的可用性的前提下，缩短了请求的响应时间。下一步的工作是研究拓展本文提出的算法，使其适用于Web服务组合。

本文初稿首次刊登于《计算机技术与应用进展◦2010》。

[1] Rachid G，Andre S.Software-based replication for fault tolerance[J].IEEE Compu ter，1997，30(4):68-74.

[2] 孟玉明，张修如，刘玲霞.一种基于主动复制的动态容错算法[J].计算机技术与发展.2007，17(12):48-52.

[3] Pow ell D.Delta 4:a generic architecture for dependable distribu ted computing[M].New York:Springer-Verlag，1991:1-484.

[4] 周明辉，郭长国，吴泉源，等.基于CORBA的容错对象复制算法[J].计算机研究与发展，2002，39(3):290-294.

[5] 王俊岭，汪 芸.基于主动复制容错技术的负载平衡模型[J].计算机工程，2005，31(11):56-58.

[6] 袁小玲，李心科.基于双向动态规划质量有保障的组合服务选取[J].合肥工业大学学报:自然科学版，2009，32(4): 465-469，499.

[7] Birman K P.Building secu re and reliable netw ork applications[M].New York:Mannning Publication Co，1997: 162-164.

[8] 钱 方，贾 焰，黄 杰，等.提高冗余服务性能的动态容错算法[J].软件学报，2001，12(6):928-935.