（计算机应用技术专业论文）基于复制的状态一致性关键技术研究.pdf

摘要 摘要 人们牛产、生活等各个方面越来越依赖于计算机的，“泛使用，建立高可靠、高可用计算 机系统已成为现代社会发展的迫切要求。基于复制的容错技术，即将关键服务软件复制到分 布式系统中一组计算机节点卜运行，形成容错组，当某个( 些) 节点失败时，其它节点 ：的 服务软件能正确运行，保证服务不会中断，从而屏蔽错误，可有效提高系统可靠性和可用性。 主动复制和丰从复制是常用的复制技术。主动复制中每个服务软件称为服务器复本( 简称复 本r e p l i c a ) ，每个复本起着相同作用，都接收并执行请求；而主从复制中只有一个服务软件 执行请求，称为主服务器( p r i m a r y ) ，其它称为服务器副本( b a c k u p ) 。丰动复制具有客户 端请求响应快和可屏蔽拜占庭错误的优点，而主从复制占用较少计算资源，因此二者都获得 了，“泛应用。 复制技术关键在于维护复本( 或主服务器服务器副本) 之问状态一致，本文主要研究 维护主动复制和主从复制状态一致性关键技术。主动复制复本从相同初始状态起，为了维护 复本之间状态一致，必须保证复本以一致顺序交付并执行请求：主从复制则要求主服务器失 败后，当一个服务器副本成为新选举出的主服务器后能够进入原主服务器失败前最后的j f 确 状态。然而，复制技术面临服务器节点崩溃、报文传输延迟不确定、报文丢失、服务器执行 速度不一致以及多线程等诸多非确定性因素，维护状态一致性非常困难。针对现有工作的不 足，本文主要的工作和贡献包括： 第一，客户请求全序化是复制技术正确的前提条件，本文提出异步分布环境下的一种非 阻塞消息全序化协议n b t o p 。非阻塞表现为当主动复制容错组发生演进时，容错组中的成 员无需等待进入相同组视图后再继续计算，甚至当决定消息发生冲突时，容错组成员仍能继 续各自的计算。n b t o p 协议采用逻辑令牌环控制结构，成员利用再请求机制获得丢失的决 定消息，通过“后继确认”机制解决决定消息冲突问题。进一步证明协议n b t o p 满足伞序 性、一致性和终止性。 第二，多线程是一种重要的非确定源，即使交付了全序的请求，由于多线程并发执行， 复本之问状态仍然可能不一致。因此，主动复制一般不支持多线程但多线程能提高系统并 发度、避免死锁并方便应用开发。基于面向对象技术，本文提出三种主动复制复本执行一致 性算法a r c ao 、a r c ap 和a r c ac ，可分别支持多线程并发执行独立对象、同一对象 独立属性和语义可交换请求，并证明其满足安全性和活性性质。王种算法均为分布式确定性 算法，无需复本之间额外通信。 第三，针对主从复制状态更新频繁和主服务器失败后恢复慢的缺点，本文提出一非阻塞 主从复制执行一致性算法n b c ap b ，采用伞序多播机制，支持多线程并发执行，可有效提 高系统响应时间和失败恢复时间。同时，证明算法n b c ap b 满足终止性、全序性、更新完 整性和响应完整性。 第四，失败检测器是分布计算环境下所必需基础构件之一，作为一种重要的分布式系统 应用，复制技术同样_ 面临复本之间( 或主服务器服务器副本) 相互判定是否失败的问题。 基于概率统计，本文提出一新的q o s 自适应失败检测器解决方案f d p s ，由统计器f d s t a t 、 配置器f d c o n f 和摹于p i n g p o n g 策略协议算法f d p p 等一部分组成。f d s t a t 获得报文延 迟规律、f d c o n f 根据应用超时问隔和查询准确率q o s 需求及f d s t a t 结果动态配置f d p p 所 需参数并由f d p p 实施自适应失败检测器。同时证明f d p p 在部分同步模型下可实现一个 o p 类失败检测器。基于f d p s 失败检测器，本文还提出g m s - f d p s 组成员服务系统。它具有 可移植性好，可扩展性强，用户接口丰富，系统开销少，失败检测速度快，误判率低，自稳 定等特点。 关键词：复制技术；主动复制：主从复制；全序化；失败检测 a b s t r a c t a b s t r a c t t ob u i l dh i g h l yr e l i a b l ea n da v a i l a b l ec o m p u t e rs y s t e m sb e c o m e si n c r e a s i n g l yu r g e n ti nm o d e m s o c i e t y s o f t w a r er e p l i c a t i o ni sa ne s t a b l i s h e dw a yf o rb u i l d i n gr e l i a b l ed i s t r i b u t e da p p l i c a t i o n s t l l a tr e p l i c a t e sc r i t i c a ls e r v i c e st os e v e r n li n d e p e n d e n tn o d e si nd i s t r i b u t e ds y s t e m st of o r maf a u l t t o l e r a n tg r o u p 、m h af a i l u r eo c c u r so ns o m en o d e s s e r v i c e so no t h e r sc a ns t i l lp r o c e s sc o r r e c t l y w h i l em a s k i n g 也ef a i l u r e t h e r e 锄t w of u n d a m e n t a lc l a s s e so fr e p l i c a t i o nt e c h n i q u e s ：a c t i v e r e p l i c a t i o na n dp a s s i v er e p l i c a t i o n i na c t i v er e p l i c a t i o n , e v e r ys e r v e r ( r e p l i c a ) b e h a v e se x a c tt h e s a m ei nr e c e i v i n ga n de x e c u t i n gc l i e n tr e q u e s t s h o w e v e r , i np a s s i v er e p l i c a t i o n , o n l yo n es e r v e r , c a l l e dp r i m a r y ，e x e c u t e sc l i e n tr e q u e s t s ，w h i l eo t h e r ss e r v ea sb a c k u p s a c t i v er e p l i c a t i o ni sm o r e e f f i c i e n ti na c h i e v i n gr a p i dc l i e n tr e s p o n s et i m ea n dm a s k i n gb y z a n t i n ef a i l u r e s i nc o n t r a s t , p a s s i v er e p l i c a t i o nc o n s u m e sl e s sc o m p u t i n gr e s o u l 陀e t h u s b o t ht e c h n i q u e sa 他w i d e l y u s e d t h em a i nc h a l l e n g eo fr e p l i c a t i o ni st om a i n t a i nc o n s i s t e n c ya m o n gr e p l i c a s ( o rp r i m a r y b a c k u p s ) t h i st h e s i sa i m sa ts t u d y i n gt h ek e yt e c h n i q u e st oe n s u r es t a t ec o n s i s t e n c yf o ra c t i v er e p l i c a t i o n a n dp a s s i v er e p l i c a t i o n f o ra c t i v er e p l i c a t i o nt om a i n t a i nc o n s i s t e n c ya m o n gr e p l i c a s ，a nr e p l i c a s ， s t a r t i n gf r o mt h es a m ei n i t i a ls t a t u s m u s td e l i v e ra n de x e c u t et h es a m es e to fr e q u e s t si nt h es a m e o r d e r i np a s s i v er e p l i c a t i o n ，i ft h ep r i m a r yf a i l s ，ab a c k u pi ss e l e c t e dt ob et h en o wp r i m a r y , a n d t h e ni ts w i t c h e st ot h el a t e s tc o r r e c ts t a t eo ft h eo l dp r i m a r ya n dt a k e so v e ra l ln 郦l e s t s h o w e v e r , i ti sr a t h e rd i f f i c u l tt ok e e ps t a t ec o n s i s t e n c yd u et oan u m b e ro f p o s s i b l en o n - d e t e r m i m s r n , s u c ha s n o d ec m s km e s s a g ed e l a yu n c e r t a i n n e s s ，m e s s a g el o s s ，r e p l i c a s s p e e dm i s m a t c h , a n dm u l t i t h r e a d 1 1 圮瑚i i lc o n t r i b u t i o n so ft h i st h e s i si n c l u d e ： f i r s t , 舔c l i e n tr e q u e s t st o t a lo r d e r i n gb e i n gac o r r e c tp r e m i s eo fr e p l i c a t i o n , an o n - b l o c k i n g m e s s a g et o t a lo r d e r i n gp r o t o c o l ( n b t o p ) i na s y n c h r o n o u sd i s t r i b u t e ds y s t e m si sp r o p o s e d n o n - b l o c k i n gp r o p e r t yr e f e r st ot h a tt h em e m b e r si naf a u l tt o l e r a n tg r o u pk e e po nr u n n i n g i n d e p e n d e n t l yw i t h o u tw a i t i n gf o ri n s t a l l i n gt h es a m eg r o u pv i e ww h e naf a u l tt o l e r a n tg r o u p e v o l v e se v e nw h e nd e c i s i o nm e s s a g e sc o l l i s i o n n b t o pt a k e sa d v a n t a g eo fl o g i c a lt o k e nr i n ga s i t sc o n t r o lm e c h a n i s m m e m b e r sa d o p tr e - r e q u e s t i n gm e c h a n i s m ( 剐时t oo b t a i nt h e i rl o s t d e c i s i o n sa n df o r w a r da c k n o w l e d g e m e n tm e c h a n i s m ( f a ) i sp u tf c r t ht os o l v ed e c i s i o nc o l l i s i o n s 1 1 地t h e s i sf u r t h e rp r o v e st h a tn b t o ps a t i s f i e st h ep r o p e r t i e so ft o t a lo r d e r , a g r e e m e n t , a n d t e r m i n a t i o n s e c o n d , b e i n ga ni m p o r t a n tn o n - d e t e r m i n i s ms o u r c e ，m u l t i t h r e a de x e c u t e sr e q u e s t sc o n c u r r e n t l y a n dt h u sl e a d st od i v e r g e n c ea m o n gr e p l i c a se v e nt h o u g hd e l i v e r i n gt o t a lo r d e r e dr e q u e s t s t h u s ， c l a s s i c a la c t i v er e p l i c a t i o ne x c l u d e sm u l t i t h r c a dm e c h a n i s m n e v e r t h e l e s s ，m u l t i t h r e a di m p r o v e s c o n c u r r e n c y , a v o i d sd e a d l o c ka n df a c i l i t a t e sa p p l i c a t i o nd e v e l o p m e n t b a s e do no b j e c t - o r i e n t e d c o m p u t i n g ，t h i st h e s i sp r o p o s e st h r e ea l g o r i t h m st h a tc a nk e e ps a f e t ya n dl i v e n e s sp r o p e r t i e sa n d t h a ts u p p o r tm u l t i t h r e a dt oe x e c u t ei n d e p e n d e n to b j e c t s ，i n d e p e n d e n tp r o p e r t i e sa n ds e m a n t i c c o m m u t er e q u e s t sc o n c u r r e n t l y t h e ya l ea l ld i s t r i b u t e dd e t e r m i n i s t i ca l g o r i t h m sa n dn e e dn o e x t r ac o m m u n i c a t i o n sa m o n gr e p l i c a s t h i r d , a f t e ra n a l y z i n gt w od e f e c t so ft h ep a s s i v er e p l i c a t i o n ，f r e q u e n tu p d a t eb a c k u ps t a t e sa n d s l o wr e c o v e r ya f t e rt h ep r i m a r yf a i l s ，t h i st h e s i sp r o p o s e san o n b l o c k i n gc o n s i s t e n ta l g o r i t h m , n b c k ，b w i t ht h eh e l po ft o t a lo r d e rm u l t i c a s t 。s u p p o r t i n gm u l t i t h r e a dt h a tc a nr e d u c es y s t e m r e s p o n s et i m ea n dr e c o v e r yt i m ee f f e c t i v e l y i na d d i t i o n ，n b c a j bs a t i s f i e st e r m i n a t i o n , t o t a l o r d e r , u p d a t ei n t e g r i t y , r e s p o n s ei n t e g r i t ya r ep r o v e d f o u r t h , f 口i l u r ed e t e c t o r sh a v eb e e nac r i t i c a lb u i l d i n gb l o c kf o ra p p l i c a t i o n so v e ra s y n c h r o n o u s d i s t r i b u t e ds y s t e m ss u b j e c tt of a u l t s a sa l li m p o r t a n ta p p l i c a t i o no fd i s t r i b u t e ds y s t e m , r e p l i c a t i o n a l s of a c e sw i t hf a i l u r ed e t e c t i o np r o b l e m sa m o n gr e p l i c a so rp r i m a r ya n db a c k u p s b a s e do n p r o b a b i l i s t i ca n ds t a t i s t i c sa p p r o a c h e s ，t h i st h e s i sp r o p o s e san e wq o sa d a p t i v ef a i l u r ed e t e c t o r s o l u t i o nf d p st h a ti n c l u d e ss t a t i s t i cf d s t a t ，f a i l u r ed e t e c t o rc o n f i g u r a t i o nf d c o n f a n dt h ef d p p p r o t o c o lw i t ht h ep i n g - p o n gs t r a t e g y f i r s t 。f d s t 4 to b t a i n ss t a t i s t i cd e l a y so fm e s s a g e s t h e n , f d c o n fc o n f i g u r e sf d p pp a r a m e t e r sa c c o r d i n gt oa p p l i c a t i o nq o sr e q u i r e m e n t sa n d f d s t a t s t a t i s t i c f i n a l l y , f d p pi m p l e m e n t st h eq o sa d a p t i v ef a i l u r ed e t e c t o r m o r e o v e r , i tp r o v e st h a t w h e nt h eu n d e r l y i n gs y s t e ms a t i s f i e st h ep a r t i a ls y n c h r o n ya s s u m p t i o n , f d p pi m p l e m e n t sa l l e v e n t u a l l yp e r f e c tf a i l u r ed e t e c t o r b a s e do nf d p s ，t h i st h e s i sg i v e sg r o u pm e m b e r s h i ps e r v i c e ( g m s - f d p s ) i m p l e m e n t a t i o ni nd e t a i l g m s - f d p si sap o r t a b l e ，e x t e n s i b l e ，u s e rf r i e n d l y , l e s s r e s o u r c ec o n s u m p t i o n ，q u i c ka n da c c u r a t ef a i l u r ed e t e c t i o n , a n ds e l f - s t a b l es e r v i c e k e y w o r d s ：s o t h a r er e p l i c a t i o n ；a c t i v er e p l i c a t i o n ；p a s s i v er e p l i c a t i o n ；t o t a lo r d e r ；, f a i l u r e d e t e c t o r 论文插图索弓 论文插图索引 图1 - 1 主动复制基本交互模型 图卜2 主动复制银行帐户执行示意图 图1 - 3 主从复制基本交互模型 图1 - 4 _ 丰从复制银行帐户执行示意图 图卜5 系统层次结构示意图 图2 - 1 客户请求的状态转移图 图2 - 2 协议性能测试环境 图2 - 3 消息尺寸和消息仝序化之间的关系 图2 - 4 消息到达率与消息接受全序延迟之间的关系 图3 - 1 银行类接口定义 图3 - 2 银行类冲突关系矩阵 图3 3 计算密集型请求平均执行时间 图3 - 4 输入输出型系统吞吐率 图3 - 5 计算密集型线程数与请求平均执行时间 图3 - 6 输入输 h 型线程数与请求平均执行时问 图4 一l 非阻塞主从复制( n b c a _ p b ) 图4 - 2 半主从复制( s e m i _ p b ) 图4 - 3 局域网短更新组成员数与响应时间 图4 - 4 局域网长更新组成员数与响应时间 罔4 - 5 广域刚短吏新组成员数与响应时间 图4 - 6 广域网长更新组成员数与响应时间 图4 - 7 最坏响应时间 图4 8n b c a _ p b 冲突请求概率与响应时闻 图4 - 9 银行帐户客户端服务器模型交互序列 图4 - 1 0 综合试验示意图 图4 - 1 1 试验环境 图4 1 2n r c s 、a r c a o 、n b c a _ p b 请求响应时间 图5 - 1 ，跏组成结构 图5 - 2 用肥- 0 n 6 策略 图5 - 3 沙似) 示意图 图5 4 查询误判率和彤变化曲线 图6 1g m s 一，z 加部署实例 图6 2g m s f f f s 组成结构 图a l 系统交互图 第i 页 2 2 3化埽四凹凹们n n铊铊的的的n觇韶飘弱弱；卯 眈 盯的叭 东南大学博士学位论文 图a 一2 服务端交互图 图a 3 客户端交互图 图a 一4 服务端序列图 图a - 5 客户端序列图 图a 一6 线程交互图 图b - i 精确延迟应用示例 第i i 页 8 1 8 2 8 2 8 3 8 3 9 1 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究t 作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被套阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：玉盐型妾 导师签名：f 至垄日期：知口7 j t 易 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究t 作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被套阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：玉盐型妾 导师签名：f 至垄日期：知口7 j t 易 第一章绪论 1 1 问题的提出 第一章绪论 现代社会信息技术飞速发展，人们生产、生活等各个方面越来越依赖于计算机的广泛使 用随着网络技术的普及，分布式系统亦已深入到越来越多的应用中，包括客户端服务器 系统、事务处理系统、w e b 服务系统、科学计算等。同时，人们对其可靠性要求也u 益提高。 但是，现实中计算机系统并非完全尽人意，计算机硬件、软件在实际运行过程中也并非完全 可靠，出错后可能造成巨大损失，需要增强分布式系统的可靠性和可用性。 本文研究基于复制的容错技术，即将关键服务软件复制到分布式系统中的一组计算机节 点上运行，形成容错组，当某个( 些) 节点失败时由于其它节点上的服务软件( 称为服务器) 能正确运行，从而屏蔽错误，提高系统可靠性和可用性。主动复制1 3 7 ，8 ：m ：川；6 3 1 和主从复制 陬b i l ( 也称为被动复制) 是常用的复制技术。主动复制中每个服务器称为服务器复本( 简 称复本r e p l i c a ) ，每个复本起着相同作用，都接收并执行请求主从复制中只有一个服务器 执行请求，称为主服务器( p r i m a r y ) ，其它称为服务器副本( b a c k u p ) 。主动复制具有客户端 请求响应快和可屏蔽拜占庭错误【l 引】的优点，而主从复制占用计算资源较少，因此二者都获 得了广泛应用。 虽然复制技术概念很容易理解，但实现复制技术非常困难，表现在需要维护所复制服务 器问状态一致只有保持服务器问状态一致，当某个服务器失败时，其它j l i 务器才能保证服 务不会中断。这里给出状态一致性的非正式定义，正式定义可参见第三章和第四章。对于主 动复制，在复本具有确定性的条件下，只要复本拥有相同的初始状态，以相同顺序执行相同 客户请求后，必然进入相同的结束状态。冈此，复本状态一致性问题可以等价地表示为客户 端请求全序化问题：对于主从复制，指当主服务器失败时，一个服务器副本如果被选举成为 新的主服务器，它能够进入原主服务器失败前最后的正确状态。本文区分“复本”和“副本” 两个概念。“复本”指主动复制中起相同作用的服务器，而“副本”指主从复制中的“服务 器副本”。 ( i ) 主动复制 容锅纽 图1 - 1 主动复制基本交互模型 如图1 - 1 所示，主动复制方式下l 啪l ，所有复本起着相同作用，每个复本都接收并执行 第1 页 南大学博学论! 请求，然后返回执行结果。然而，即使假定通信链路可靠，由于阿络延迟，不同复本可能以 不吲顺序接收不同客户端发送的请求，导致执行请求后复本状态不同。 一j w f r ；1 ! 二_ l 二! j 一一- l 一 一4 。 星_ _ = j。i 雪 = 一 | 。焉荔叠孽刀 图l o 主动复制银行e 户执行示意图 以图卜2 所示主动复制银行帐户容错为例：银行帐户复本对象r 1 和r 2 形成容错组，假设 某帐户初始余额1 0 0 元。客户端a 发送r 1 请求向该银行帐户存款1 0 0 元，客户端b 旋送请求正 从同一帐户取款2 0 0 元由于网络延迟不同，复本r l 先接收请求r 1 ，然后接收请求r 2 按r i ， n 顺序执行存款操作后执行取款操作，均成功返回结果，最终帐户余额为0 元；而复奉r 2 先 接收请求n 然后接收请求r l ，按n r l 顺序执行，执行取款操作时显示余额不足后执行 存款操作最终帐户余额为2 0 0 元可见，复本r l 和r 2 执行结粜不同，最终状态也不一致。 出错原因在于复本r i ，r 2 接收请求顺序不同导致执行请求顺序不同。因此，在复本具有确 定性的条件下保持复本状态一甄( r e p l i c ac o n s i s t e n c y ) ，首先需保证每个复本以相同顺 序交付( d e l i v e r y ) 客户端请求也称为全序多播问题唧。 保持复本状态一致，还必须保证复本以一致顺序执行请求。若复本采用单线程执行机制， 全序多播协议就能满足需求：全序多播以相同顺序交付客户端请求每个复本按该顺序执行 请求。这也正是经典主动复制技术所采用的方式”“q 。多线程作为一种重要的非确定因素， 可能导致复奉状态不一致。以图1 - 2 银行复率容错为例，仍假设某帐户初始余额1 0 0 元，客 户端a 发送r l 请求向该银行帐户存款1 0 0 元客户端b 发送请求吐从同一帐户取款2 0 0 元。使用全序多播复本r l 和只2 均以r l ，r 2 顺序交付请求。若采用多线程，请求r l ，r 2 可并发执行，应用无法控制操作系统调度请求顺序。若复本r l 按f l ，n 顺序执行存故操作 后执行取款操作，均成功返回结果最终帐户采额为0 元；复本r 2 先执行r 2 然后执行r 1 ， 执行取款操作n 时显示余额不足，后执行存款操作r 1 最终帐户余额为2 0 0 元。与复本间 交付请求顺序不同类似复本r l ，r 2 执行结果不同，最终状态也不一致。然而多线程能 有效提高系统并发度、避免死锁并方便应用开发。特别是随着多核c p u 和多c p u 系统的普 疑，多线程已成为现代软件开发中不可或缺的一部分。 ( 2 ) 主从复制 1 # p t $ 2 an $ ! 删$ 5 一# $ z f 自6 - 目g p 目 图i - 3 主从复恻基奉交互模型 第2 娶 第一结论 如崮卜3 所示主从复制方式f i 删。从弈错组中选举出其中个服并器作为主服务器 其它服务器称为服务器副本，只有主服务器接收请求。主从复制可分为净蔷、暖蔷和热备三 种策略5 “j 。冷薪91 方【l = f 主服务器将状态周期性保存在非易失共享存储器巾，服势器 日q 本只有在主服务器失败情形f a 运行以替换原柬的主服务器。冷各系统主服务器失败后恢 复慢且原主服务器最后j 扶保存状态至失败捌问所有执行请求结果和状态三失，本文不做 进。步研究暖备和热备方_ 【i = f ，主服务器以任意顺序执行客广请求，将执行结果( 状态) 多播给服务器副奉并返回执行结果给客户端。与主动复制比较主从复制方式f 仅主服务器 执行客户端请求，节省了计算资源。世是，若主服务器每执行个请求状杏更新后就同步更 新服务器副本状客( 称为热番”“o 吼f 称为简单主从复制$ 1 m pp b ) ，网络开捎大，而且 主服务器只有等待所有服务器副奉状态更新确认后( 图1 - 3 中步骤4 和5 ) 才能返回结粜， 客厂1 端响应延迟增加。另一方面，i l i 于只有主服务器接收请求，当主服务器失败时，客j 、端 只有检测到其失败，并在弈错组内选举出新的丰服务器后重发束成功执行的请求系统才 能继续。返样，容错组对客，_ 端不透明且若丰服务器失败，应用恢复时问较长。因此若 所有服务器都接收容广端请求并且主服务器执行定数目请求后才将状态更新到服务器副 本上( 称为瞪备) ，当主服务器失败时，客广端不需重发请求；丰服务器也不必在执行每 请求后就同步服务器副车状卷，减少研绵通信开销，井改善客户端响应时何。 圈l - 哇主从复制银行帐户执行示意圈 然晰，采用暖备黄略，若丰服务器执行一些请求后走败，这部分请求状态更新还没有反 映到其它服务器剐牟上。当某一服务器副奉被选举为新主服务器后，该部分请求执行顺序和f 原丰服务器执行序不一定一致，可能导致系统状态更新不一致。如图1 4 所示，主服务器 r l 和服务器剐奉r 2 形成银行帐户窖锖组。某帐户初始余额1 0 0 无，客户端a 发送r l 请求 存款i 元，客户端b 技迸n 请求取款2 0 07 l 。l h 】：网络传输报文请求延迟不确定丰服 务器r l 接收请求顺序为r 1 ，口，而服务器副奉r 2 接收请求顺序为n ，r l 。丰服务器r 1 先 执行r 1 返回2 0 0 儿给客户端b 后失败。r 2 榆剥到r i 火欺后成为新丰服务器。r 2 光执行 r l 、然后执行n ，分别返回“余额不足”和2 0 0 l 给客户端b 。这样客户端b 收到的针对 r l 的执行结粜不一致应用爵义出错。因此与手动复$ 0 类似，暖鲁维略下的丰从复制l 卅 样面l 临多线程什确定性问题。这也止是现有丰从复制均仅研究热备的原因1 13 1 】。 丸论主动复制还是丰从复制都会蟛成服务暑导客锖组，对组成员进行管理显襻尤为重要。 组成员管理是分布式容错系统的重蛰部件。一个容错组的成员( 比如主动复制巾复奉成员或 丰从复制中丰服务器丰服务器副本成员) 阱作完成一特定日标。凼为新的成员可能希蠼加入 已纾存在的容错组或者一些成员希胡离开( 或者火败后必须从容错组中移睬) ，组成员动 态发牛变化。那么如，a 彤成韧始客l 昔组成员视图? 新成员加入如何进行状态l 目步? 成员退山 镕3 m 东南大学博士学位论文 后其它组成员如何同步更新组视图? 这些关于组成员管理方面的问题也是实施复制技术过 程中必然面临的问题。 除网络传输报文延迟不确定外，服务器成员还存在发生崩溃、报文丢失、执行速度不一 致性等诸多不确定凶素。那么，当组成员失败时，其它成员如何准确并迅速判定其失败? 这 涉及组成员失败检测问题。c h a n d r a 和t o u e g 3 9 】最早提出，失败检测器可作为增强异步系统 计算模型的有效手段，解决一致性问题，并给出了形式化定义。然而，如何根据组成员实际 运行环境设计高效失败检测器仍然是一难题，其难点在于如何权衡超时间隔和查询准确率。 1 2 背景和研究现状 1 2 1 术语 论文所研究复制技术的容错组成员运行于异步分布式系统中。异步分布式系统1 7 5 l 定义 为：一组服务器节点集合q = p t 。p 2 ，见 o = l ，2 ，n ) ，相互协作完成一项任务，节点之间 通过网络连接可发送消息相互通信。假设物理节点间不共享内存，它们仅仅通过网络发送消 息。并且： ( 1 ) 消息传输的延迟没有上界； ( 2 )每个节点执行一步所需时间没有上界： ( 3 ) 节点无法访问同步时钟。 关键服务软件复制到异步分布式系统中的一组计算机节点上运行，形成容错组。每个节 点上运行服务软件的一个复本( 或副本) ，称为服务器，也称为成员。除非特殊说明，本文 不区分服务器和成员两个概念。每个成员的执行对应一个节点上的一个或多个进程。程序规 范定义成员的正确行为。当成员遵从规范执行时，认为成员正确：与规范出现偏差，认为成 员出错，发生失败【8 】。根据成员运行偏离程序规范的程度分为时间失败、忽略失败、崩溃失 败和拜占庭失败1 1 0 1 1 ，拜占庭失败是最一般的失败类型。现有研究工作般通过复制技术可 屏蔽成员崩溃失败。 成员检测到失败必须修正以免分布式系统整体失败。一旦检测到成员失败，可用多种方 法进行处理，一般分为预防性( 失败补偿) 和纠正性( 失败恢复) 两种方法。预防性方法指 系统未失败时已经采取措施防止系统失败。复制技术是一种重要的预防性失败屏蔽( e r r o r m a s k i n g ) 容错技术。纠正性方法指当检测到成员失败时试图将系统再次恢复到正确状态i l 蚓， 通常可采用前向失败恢复和后向失败恢复两种方法。理想情况下【b 5 1 ，应将失败限定于成员 内部而不应该传递到外部。 实现计算机容错离不开冗余嗍( 硬件、软件、信息或时间) 。失败检测和校正代码利用 信息冗余容错f 5 0 1 。时间冗余通过不同时刻重复执行计算并比较结果的方法检测故障p 】。必须 指出，冗余是容错的必要条件，但非充分条件。将一组冗余服务器简单组合在一起远远不够。 要建立高可依赖系统，如何管理冗余部件至关重要。l a l a 等指出1 删：“仅仅冗余并不能保证 容错。为使冗余系统在故障时仍然能够正确工作，必须对冗余服务器进行有效管理。”本文 主要工作正是研究如何有效管理冗余的容错组服务器，维护服务器之间状态一致 复制技术扩展了客户端服务器架构，除客户端服务器结构中客户端发送请求、服务器 执行请求、返回执行结果等步骤外，为维护复本( 或主服务器朋厦务器副本) 之间状态一致 第4 页 第一章绪论 及组成员管理，还需增加执行前序协调和执行结果协调等步骤。表1 - 1 和表1 2 分别给出了 主动复制和主从复制的执行步骤。当然，表中所列步骤并不绝对，可根据实际作适当调整。 表l l 主动复制执行步骤 步骤操作 1 发送请求( r e q )发送给所有复本 a 协调一致决定序 2 执行前协调( p i 咂c o ) b 拥有特权( t o k e n ) 复本决定序 3 请求执行( e x e )所有复本都执行请求 4 返回( r e t ) 所有复本都返同结果给客，、端 表1 2 主从复制执行步骤 步骤操作 1 发送请求( r e q ) 只发送给土服务器 2 请求执行( e x e )只有主服务器执行请求 3 执行结果协调( p o s l o ) 土服务器更新服务器副本状态 4 返回( i 迮t ) 只有主服务器返刚结果给客户端 主动复制执行前协调一般通过请求全序化完成，而支持多线程复制技术必须保证复本 ( 或主服务器服务器副本) 执行一致，另外基于复制的容锚组还需对组成员进行管理( 主 动复制全序化选择决定者、主从复制选举土服务器等) 本节将分别介绍这些基于复制的状 态一致性关键技术的研究现状。 1 2 2 全序化协议 要讨论服务的复制，首先要解释复制技术正确的条件：线性化【嘲】，有时也称之为单拷 贝等价1 7 。线性化给客户端呈现m 的是非复制的服务器，这是一个很重要的特征，因此它 保持了程序的语义。假设一客户端进程p i 调用单一服务器x 上的方法o p ，参数为a r g ，用 o p ( a r g ) 表示。在客户端进程p i 调用0 p 之后，服务器x 发出响应以o k ( r e s ) 的形式表示，o k 表 明调用成功，r e s 中带有返刚值( r e s 可能为空) 。采用复制的方法实现容错，即将服务复制 到分布式系统的n 个不同节点上，用x l ) 【2 ，】【- i 表示。服务端复制后，必须保证客户端调用 语义保持一致：客户端仍然以o p ( a r g ) 发出调用，然后得到o k ( r e s ) 响应。但是，如果服务端 不能适当处理客户端请求，返回的结果可能发生错误。比如，假设服务端x 实现先进先出 ( f i f o ) 队列以及进队列e n q u e u e o 和出队列d e q u e u e o 两种操作。假设初始时队列为空，客户 端进程p i 和p i 分别提出请求并得到如下结果： ( 1 ) 进程p i 调用e n q u e u e ( a ) ，然后调用d e q u e u e o ，得到返回值o k ( b ) 。 ( 2 ) 进程p j 调用e n q u e u e ( b ) ，然后调用d e q u e u e o ，得到返到值o k ( b ) 。 该执行结果显然4 i 正确：b 只进队列一次却两次出队列。但是在服务端被复制的情况 下，却有可能得出这样错误的结果假设服务端x 被复制两次( x 。和x 2 ) ，并按如下步骤执行： ( 1 ) x l 首先收到进程p i 的调用请求e n q u e u e ( a ) ，然后收到p j 的调用请求e n q u e u e ( b ) 。那么进 程p i 的d e q u e u e o 调用将得到返回值o k ( a ) ，进程p j