（计算机科学与技术专业论文）数据库集群故障切换技术的研究与实现.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着不间断关键任务需求的不断增强，数据库管理系统这一核心部件的高可 用性越来越受到业界的重视。当前数据冗余和集群设计成为数据库高可用方案的 首选，但集群系统的故障切换效率影响了系统的高可用性。因此实现一个具有高 故障切换效率的集群系统具有很好的使用价值，杖基于m y s q l 数据库系统设计 实现了事务完整的故障切换模型p r o n t op f 。 本文详细分析了当前数据库集群采用的两种体系结构( 无共享存储体系结构 和共享存储体系结构) 的特点，无共享结构的故障切换效率和集群可扩展性高， 但结构的故障处理能力较弱，共享结构的故障处理能力强，但故障切换效率较低。 引进故障预测机制提高故障切换的效率，并对基于预测的故障切换算法的正确性 和合理性进行了证明。然后根据故障切换的需要引入了事务i d 属性，设计实现了 扩展的二进制日志文件中的事件结构：h al o g 。最后基于故障预测和扩展的event 事件结构构建故障切换模型p r o n t op f ，p r o n t op f 主要由三个模块组成，节点切 换模块在预测节点发生故障时召集选举协议，根据事务i d 属性选择合适的协调者； 事务读写模块引入事务信息表的概念，将系统执行事务的情况记录在事务信息表， 根据事务信息表和节点日志文件的事件信息进行比较分析判断节点事务是否丢 失；事务分析模块根据节点读写模块执行事务的撤销与重做实现系统事务的完整。 本文在扩展日志的基础上实现了p r o n t op f ，并根据其体系结构深入分析并实 现了三个组成模块，其中应用了r o w a a 策略，心跳检测策略和重做日志策略等 多种策略，论文最后对p r o n t op f 进行了性能评测，并与现有高可用集群进行比较， 结果表明模型的故障切换效率和事务完整性功能符合高可用需求。 主题词：高可用，集群，故障切换，事务完整性 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t r a c t w i t ht h ei n c r e a s i n gr e q u i r e m e n to fc r i t i c a la n dc o n t i n u o u st a s k ，h i g ha v a i l a b i l i t yo f d a t a b a s em a n a g e m e n ts y s t e mi sp a i dm o r ea t t e n t i o nb yi n d u s t r y d a t ar e d u n d a n c ya n d c l u s t e ri st h ef i r s tc h o i c et oa c h i e v eh i g ha v a i l a b i l i t y b u tf a i l o v e re m c i e n c yo fc l u s t e r s y s t e ma f f e c tt h es y s t e m sh i g ha v a i l a b i l i t y t h e r e f o r e ，t oa c h i e v eo n ec l u s t e rs y s t e mo f l l i g hf a i l o v e re f f i c i e n c yh a sh i g hp r a c t i c a lv a l u e t h ef a i l o v e rm o d e lp r o n t op ff o c u s e d o nt r a n s a c t i o ni n t e g r i t yb a s e do nm y s q li si m p l e m e n t e d t h e s i sd e t a i l e da n a l y z es h a r e dn o t h i n ga n ds h a r e ds t o r a g ea r c h i t e c t u r e t h ef o r m e r h a sh i g hf a i l o v e re f f i c i e n c ya n ds c a l a b l ep e r f o r m a n c e ，b u tt h ef a u l th a n d l i n gc a p a c i t yi s w e a k h o w e v e r ，s h a r e ds t o r a g ea r c h i t e c t u r eh a ss t r o n gc a p a c i t yo ff a u l th a n d l i n ga n d l e s se 伍c i e n tf a i l o v e r a n dt h e ni n t r o d u c et h ef a i l u r ep r e d i c a t i o nm e c h a n i s mt op r o m o t e t h ee f f i c i e n c yo ft h ef a i l o v e r , a n dp r o v et h ec o r r e c t n e s sa n dr a t i o n a l i t yo ft h ef a i l o v e r a l g o r i t h mb a s e do np r e d i c a t i o n a n di n t r o d u c e dt h et r a n s a c t i o ni da t t r i b u t ef o rf a i l o v e r , d e s i g n e da n di m p l e m e n t e dt h ee x t e n d e de v e n t s t r u c t u r ei nt h eb i n a r y l o g f i l e ： h al o ge v e n t f i n a l l yb a s e do nf a i l u r ep r e d i c a t i o na n dt h ee x t e n d e de v e n ts t r u c t u r ew e b u i l d i n gaf a i l o v e rm o d e lp r o n t op f ，w h i c hm a i n l yc o n s i s t so ft h r e em o d u l e s ，t h en o d e s w i t c hm o d u l ec o n v e n et h ee l e c t i o na g r e e m e n td u r i n gt h en o d ef a i l u r ep r e d i c a t i o na n d s e l e c tt h ea p p r o p r i a t ec o o r d i n a t o ra c c o r d i n gt ot r a n s a c t i o ni da t t r i b u t e ；t h et r a n s a c t i o n r e a d w r i t em o d u l ei n t r o d u c et h ec o n e e p to ft h et r a n s a c t i o ni n f o r m a t i o nt a b l ea n dr e c o r d t h ei m p l e m e n t a t i o ni n f o r m a t i o no ft r a n s a c t i o ni nt h es y s t e m a n dd e t e r m i n ew h e t h e rt h e l o s so ft h en o d ea f f a i r sa c c o r d i n gt ot h ea n a l y s i sa n dc o m p a r i s o no ft h ei n f o r m a t i o ni n t h et r a n s a c t i o ni n f o r m a t i o nt a b l ea n db i n a r yl o gf i l ei nt h en o d e ；t h et r a n s a c t i o na n a l y s i s m o d u l er e a l i z et h et r a n s a c t i o ni n t e g r i t ya c c o r d i n gt ot h et r a n s a c t i o nr e a d w r i t em o d u l e b vu n d o i n ga n dr e d o i n gt h et r a n s a c t i o n i nt h i sp a p e r ，w ec o n s t r u c tt h ef a i l o v e rm o d e lp r o n t o 翼b a s e do nt h ee x t e n dl o g ， t h e na n a l y z ea n di m p l e m e n tt h et h r e em o d u l e si na c c o r d a n c ew i t hi t sa r c h i t e c t u r e w h i c ha p p l i e dt h er o w a - as t r a t e g y ，h e a r t b e a td e t e c t i o ns t r a t e g ya n dr e d ol o g ss t r a t e g y f i n a l l y ，p r o n t q j f ? sp e r f o r m a n c ee v a l u a t i o na n dc o m p a r i s o nw i t he x i s t i n gh i g h a v a i l a b i l i t yc l u s t e r s h o wt h a tt h ef a i l o v e r e f f i c i e n c y a n dt r a n s a c t i o ni n t e g r a l i t y c a p a b i l i t i e so f t h em o d e lm e e tt h eh i g ha v a i l a b i l i t yr e q u i r e m e n t s k e yw o r d s ：h i g ha v a i l a b i l i t y ，c l u s t e r ，f a i l o v e r 。t r a n s a c t i o ni n t e g r a l i t y 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1系统不同可用性级别的停机时间2 表3 1共享存储与无共享存储结构性能比较2 2 表4 1二进制日志事件类型及编码3 3 表4 2 事件结构、域及偏移量3 4 表4 3h a 表5 1事务信息表属性描述4 7 表6 1 硬件配置5 3 表6 2 软件测试环境5 3 表6 3 请求的事务操作分析一5 4 第l i l 页 国防科学技术大学研究生院硕士学位论文 图目录 图1 1不同计算机系统的可扩展性l 图2 1心跳检测机制的实现形式7 图2 2 心跳框架及状态转换图8 图2 3c l u s t e r r a 事务处理过程。l5 图2 4m y s q l 复制机制15 图3 1无共享存储体系结构l8 图3 2o r a c l er a c 体系结构1 9 图3 3混合结构模型2 2 图3 4 服务器状态转换。2 3 图3 5 故障预测时间序2 4 图3 6 基于预测的故障切换的消息交互图2 5 图4 1 主从复制。3 l 图4 2 对等复制3 2 图4 4 服务器写二进制日志流程图3 6 图4 5 二进制日志写操作函数调用层次图3 6 图4 6 写二进制日志文件的伪码描述3 7 图5 1系统维护周期4 1 图5 2 双机集群系统的m a r k o v 过程4 2 图5 3 p r o n t op f 模型框图4 3 图5 4m y s q lp r o x y 嵌入式脚本数据结构4 4 图6 。l模拟应用的数据结构5 4 图6 2 系统故障切换性能测试5 7 图6 3 事务完整性测试5 8 图6 4 系统可扩展性测试5 8 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目：熬量崖篡登邀隍塑逸拔苤鲍珏究复塞理 学位论文作者签名： s 羁 日期：乒钐口年乡月多日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名： 作者指导教师签名： 日期：桫1 啤多月多日 日期：a 朋口年多月，1 ，e l 国防科学技术大学研究生院硕士学位论文 第一章绪论 1 1 引言 如今，计算机系统在促进社会经济发展的同时，也对自身可用性和稳定性提 出了更高的要求。譬如金融，证券，电信等行业的服务器承载着很多关键信息的 存储，传递和处理，一旦服务器发生崩溃，将会带来不可估量的影响。因此，保 证服务器连续、稳定的运行已成为计算机应用的迫切需要，高可用数据库集群系 统以提供持续稳定的服务为目的而成为当前热门的研究课题。 1 1 1 集群技术的发展 集群是一种计算机系统，它通过一组松散集成的计算机软件和硬件连接起来 协作完成计算工作，系统中的单个计算机称为节点，集群通常用来改善系统的计 算速度和可用性i i 】。 集群并不是全新的概念，早在2 0 世纪7 0 年代i t 厂商和研究机构就开始了对 集群系统的研究和开发。集群的研究起源于其良好的性能可扩展性，1 9 6 7 年i b m 的g e n ea m d a h l 发表的阿姆达尔定律奠定了集群研究和发展的基础【2 l ，最初提高计 算机性能的方法是靠提高主频和总线带宽，根据阿姆达尔定律发现这对提高系统 性能是有限的，进而出现了增加c p u 和内存容量来提高性能，于是对称多处理机 ( s m p ) 应运而生，但c p u 的数量超过阈值时系统的性能反而变得越差( 如图1 1 所示) ，主要是因为系统访问内存和总线带宽不能随着c p u 数目的增加而有效增 长，但集群的性能却能随着c p u 的增加几乎呈线性增长1 3 】。 图1 1 不同计算机系统的可扩展性 始于1 9 6 9 年的a d 志p a n e t 网的建设成功以及后续i n t e r a c t 的出现为集群的发 展提供了契机，可以说i n t e m e t 网就是一个广义的集群。d a t a p o i n t 公司于1 9 7 7 年 开发的a r c n e t 是第一个商业集群产品，随着v a x v m s 操作系统的出现，d e c 在1 9 8 4 年发布了v a j i ( c l u s t c r 集群产品，a r c n e t 和v o ( c l u s t e r 不仅支持并行计算还共享 第1 页 国防科学技术大学研究生院硕士学位论文 文件系统和外围设备，v m s c l u s t e r ( v a x c l u s t e r 的后续产品) 仍被h p 应用在基于 a l p h a 微处理器以及i t a n i u m 处理器的o p e n v m s 系统之上【4 】。1 9 8 9 年开发的并行虚 拟机( p v m ) 利用t c p i p 连接的计算机系统能迅速组成一个虚拟超级计算机一高性 能计算集群，其计算能力超过i b m 的”b i gi r o n ，这些直接导致了n a s a 在1 9 9 3 年利用p v m 和廉价p c 构建集群来取代巨型机1 2 1 。而于1 9 9 4 年开发成功的两个高可 用集群产品t a n d e mh i m a l a y a 和i b ms 3 9 0p a r a l l e ls y s p l e x 是近代集群发展的里程 碑，n c s a 在d e l lp o w e r e d g e18 5 5 刀片服务器上运行w i n d o w sc o m p u t ec l u s t e r s e r v e r2 0 0 3 构成的集群系统在2 0 0 6 年的计算机5 0 0 强排名中名列前茅【5 1 。 当前集群技术呈现百花齐放的趋势，各大公司都提供了集群技术的解决方案： i b m 的h a c m p ( h i g ha v a i l a b i l i t yc l u s t e rm u l t i p r o c e s s i n g ) ，h p 的s e r v i c e g u a r d ， 微软的故障切换集群m s c s ( m i c r o s o f lc l u s t e rs e r v e r ) ，o r a c l e 的真正应用集群 ( r a c ) ，r e d h a t 的l i n u x h a ，v m w a r e 的小忱r eh a 等。每种集群技术都有各 自的特点，例如l i n u x - h a 采用基于策略的资源管理机制来管理系统资源的配置和 部署，并能利用隔离机制将失效节点从集群中删除，而使其他可用节点不受影响。 1 1 2 集群技术的优势 i n t e r n e t 的飞速发展给服务器带来了前所未有的挑战，大部分企业都需要提供 2 4 * 7 的服务，任何服务中断都会造成直接的商业损失。根据调查表明，对客户服 务系统来说服务中断一分钟就会损失2 7 0 0 0 美元【6 】，所有这些都对网络服务的可用 性和稳定性提出了很高的要求。计算机系统的可用性指的是系统正常运行时间与 系统总运行时间之比，反映的是一年内系统正常工作时间或宕机时间【3 】，表1 1 列 出了服务可用性等级与系统停机时间之间的关系。据表得知系统的可用性如果只 有9 9 5 的话，那么系统的年宕机时间会达到4 4 个小时，而如果达到9 9 9 9 9 的 话，系统的年宕机时间就会缩小到5 分钟。行业专家认为系统要提供可靠和持续 的服务，系统的可用性必须达到9 9 9 9 9 ，也就是所谓的“五个九 标准。但环境 的剧烈变化，软硬件设计时潜在的缺陷以及系统应用时人为的错误都会导致系统 发生故障，如何在故障发生时依然保持系统的高可用性成为学界研究的热点。 表1 1系统不同可用性级别的停机时间 可用比例年停机时间 a v a i l a b i l i t ye r c e n t a g e d o w n t i m e ( m i n u t e s y e a r ) 9 9 5 2 6 4 0 9 9 9 5 2 8 9 9 9 9 5 3 9 9 9 9 9 5 9 9 9 9 9 9 0 5 第2 页 国防科学技术大学研究生院硕士学位论文 单机数据库系统在早期为提高系统吞吐量和可用性做出了贡献，但由于是紧 耦合结构，很难满足高可用系统的需求，随着负载的增加会导致不断升级服务器， 这种方法存在以下缺点：一是升级繁琐且造成服务中断；二是高端服务器代价很 大；三是服务器是单一故障点，单点故障会造成整个系统失效【2 j 。而通过高性能网 络互联的数据库集群能有效避开这些缺陷成为高可用网络服务的有效结构，数据 库集群系统的松耦合结构为企业级应用带来的具体优势在于： 提高系统性能。网络服务的工作负载通常是大量相互独立的任务，通过一组 服务器分而治之，实现读写分离和负载均衡，可以获得很高的整体性能1 5 】。 提高性价比。组成集群系统的服务器和标准网络设备因为大规模生产降低成 本，价格低，具有很高的性能价格比。集群整体性能随着结点数的增长而 接近线性增加，系统的性能价格比接近于服务器。所以，这种松耦合结构 比紧耦合系统具有更好的性价比。 提高使用灵活性。在数据库集群系统中可根据节点数目的变化实现资源的动 态部署和重配置，满足不断变化的业务需求。 更高的可用性。数据库集群在硬件和软件上都有冗余，通过系统资源和故障 的监测和处理，当发现模块失效时，将故障屏蔽，自动迁移到可用存活结点 提供服务，实现更高可用性。 1 2 课题背景与研究意义 本课题的背景源自于国家8 6 3 课题“高端容错计算机系统项目”。 高端容错计算机通常指处理器数量为8 颗至6 4 颗的服务器系统，一方面性能 强大，能够承担大型数据库、海量数据处理等超大规模的计算任务；另一方面具 有很高的可用性，每年系统停机时间不超过5 分钟，专门面向高端商业应用，承 载着金融、电信、税务、财政等关键行业的核心业务系统1 8 】。从日常生活中的银行 证券交易、税务到国家经济管理都离不开高端服务器的支持，这技术关乎国家 经济运行安全和国家战略安全，被列入国家信息系统建设的重大关键装备。 目前来看，高端容错计算机所面向的中国高端商用市场基本由国外厂商垄断。 由于高端容错计算机在关键应用领域的不可替代性，银行业务数据库、大型证券 交易系统等关系国家经济命脉的信息化系统一直依赖进口设备，客户不仅要付出 高昂的硬件成本，而且后续运营维护成本更加惊人，国外厂商由此从中国市场攫 取了高额垄断利润。同时，大部分产品采用独有或封闭技术，只能由产品供应商 独家提供技术服务，客户没有修改维护产品的技术许可，国外厂商的技术封锁不 利于国内计算机产业的发展和进步1 3 】。 更为重要的是，由于该类产品技术的缺失，使得我国信息安全难以保障。高 第3 页 国防科学技术大学研究生院硕士学位论文 端容错计算机具备远程维护功能，可以实现远程系统开关机、远程监控系统状态、 远程配置系统等功能，这些功能无疑会增加系统敏感信息的泄露隐患，甚至可能 使得系统被远程破坏而无法正常运行。自丰信息化平台是信息安全的基础，自主 开发容错计算机系统对于提升我国信息技术的核心竞争力具有重大意义哺j 。 数据库作为底层数据存储平台，其可用性的高低直接影响商业应用的高可用 性，课题在容错计算机项目的基础上深入研究数据库集群高可用技术的开发，为 进一步提高数据库系统乃至整个计算机系统的故障切换性能奠定基础，也为国产 数据库系统部署在高端容错计算机上做出贡献。 为保证数据库集群系统的高可用性能，数据库一般采取数据复制( 冗余技术) ， 连接迁移和故障切换技术来实现，在研究基于m y s q l 的数据库集群高可用特性的 基础上，发现还存在以下一些问题： m y s q l 数据库采取异步复制的方法实现数据的冗余，异步复制虽然能保证 应用响应时间，但存在事务丢失造成数据不一致的风险。 l d y s o l 数据库系统本身并不提供故障检测和自动故障切换的功能。 从上面的分析可以知道，数据库系统的高可用对于整个计算机系统的可用性 有着很重要的影响，开发有效提高数据库高可用性的方法成为业界的迫切需要。 针对数据库集群可用性和事务完整性方面存在的问题，课题在研究数据库集群体 系结构和复制机制的基础上，探索实现数据库集群故障切换和事务完整性的有效 方法。 1 3 论文研究内容 本课题研究了基于m y s q l 数据库集群系统故障切换机制的实现技术。课题的 工作主要包括以下几个方面： 1 、探讨分析数据库高可用集群体系结构，对比研究共享存储和无共享存储结构的 特性。 2 、研究数据库集群复制机制，重点分析同步复制和异步复制之间的差异，深入研 究两种复制机制可能存在的问题，针对其问题提出可能的改进方案。 3 、研究了故障切换机制的实现，结合无共享集群结构与异步复制的特点，引进了 故障预测的方法来预判系统故障的产牛，提高故障切换的效率。 4 、研究数据库服务器的选举策略，提出实现基于m y s q l 数据库集群的故障切换 机制，针对数据库集群服务器间可能的事务丢失提出保持事务一致性和完整性 的实现策略。 5 、测试系统性能并对比分析课题方案与其他系统高可用方案的差异，以便为下一 步的改进工作提供参考。 第4 页 国防科学技术大学研究生院硕士学位论文 本课题建立在分析研究现有故障切换机制的基础上，结合对m y s q l 数据库系 统的深入研究，建立基于m y s q l 数据库集群的自动故障切换系统，使之接近或达 到m y s q lc l u s t e r 故障切换的性能。本课题的创新点主要体现在： 在对集群故障切换机制研究的基础上，引进了故障预测的方法来判断故障切换 的时机，建立基于离散事件的故障预测模型，在故障发生前完成应用迁移的准 备工作，加快故障切换的效率。 修改当前的日志结构，引入高可用事件结构：h a l o ge v e n t ，建立一种基于混 合结构模型并能保证事务完整性的日志结构。 基于事务丢失建立一种解决机制：建立事务和服务器状态信息表，引进事务信 息表能够在故障切换之后，依据事务信息表的信息重新执行丢失和回滚的事 务，以此提高系统的稳定性和可用性。 本课题的完成为数据库集群的自动故障切换机制的设计提供了理论基础，其 原型实现具有较好的参考价值。 1 4 论文组织结构 本文是对课题研究工作的总结，全文共分为7 章，结构如下： 第一章：绪论。本章介绍了数据库集群系统实现容错和高可用的必要性，论 述了集群技术的发展历程以及应用的优势，说明了本次课题的研究背景以及研究 意义，为本文的研究工作进行定位，并讨论了课题的主要工作和创新点。 第二章：相关工作。本章对比分析了现今不同应用系统实现高可用性能采用 的一些技术措施和算法。首先介绍了故障检测机制中的心跳检测机制，然后就连 接迁移技术中的基于客户端，基于i p 层以及基于t c p 连接迁移技术进行详细论述， 接着介绍了服务器的选举机制：b u l l y 算法和环选举算法，最后对状态一致的同步 和异步方法进行了探讨。 第三章：数据库集群高可用性研究。该章主要分析现有数据库集群的体系结 构：无共享体系结构和共享体系结构，并就两种结构在高可用方面的特性进行了 深入的比较分析。然后分析了集群故障切换机制，根据课题需要提出了基于故障 预测的故障切换算法，并对算法的合理性进行了证明阐释。 第四章：二迸制日志结构的研究。本章分析数据库集群系统复制机制和用于 m y s q l 异步复制机制的二进制日志结构，在现有日志结构的基础上结合课题故障 切换和事务完整性的需求扩展实现了高可用事件结构，并提出了用于标识事务的 事务i d 属性。 第五章：数据库集群故障切换模型的实现。本章分析集群系统的可用性度量 公式，并针对度量公式的变量构建基于故障预测和扩展日志结构的故障切换模型， 第5 页 国防科学技术大学研究生院硕士学位论文 并实现组成模型的三个主要模块：节点切换模块，事务读写模块和事务分析模块。 第六章：评测与分析。本章给出测试系统的软硬件环境和测试指标：故障切 换效率，事务完整性概率和系统可扩展性。根据指标设计了评测路线来测试系统 模型，并对其性能进行分析。 第七章：结束语。本章对论文工作进行总结分析，并对下一步的工作进行部 署和展望。 第6 页 国防科学技术大学研究生院硕士学位论文 第二章相关工作 为提高系统的高可用性能，各大i t 公司都提供了自己的故障解决策略，多数 高可用系统都需要实现故障切换功能。故障切换工作主要涉及以下几个方面：故 障检测，连接迁移，选举机制，状态一致。本章拟从这四个方面来阐述故障切换 技术的相关研究进展和现状。 2 1 故障检测 故障检测是在系统内部的故障未引起失效发生之前，通过对运行系统的实时 监控信息进行分析，及时发现系统内部的故障和故障苗头，并采驭相应手段避免 失效带来的停机开销和风险。 现在大多数系统利用心跳机制实现故障检测一1 ，其中很多采用的是利用报警信 号来激发心跳，这个方法的缺点是该信号不能严格的按照周期生成，因为操作系 统会发生进程调度，这样备份节点可能要等待很长时间才能获取主节点发生故障 的信息。第二个缺点就是上下文切换的开销太大以至于限制了心跳的频率。微软 的集群服务其心跳周期是1 2 秒，但是检测周期却是7 2 秒【i 】。 心跳( h e a r t b e a t ) 检测机制 心跳检测机制实现两种不同的形式：环形心跳( 图2 1 左) 和广播心跳( 图 2 1 右) i l o l 。在环形心跳中，所有节点组织成一个环形，系统中的节点从右邻居获 取心跳信息并向左邻居发送心跳信息。不相邻的节点必须依靠中间节点才能获得 对方的心跳信息，在多于四个节点的集群中，如果有两个以上节点发生故障，集 群很可能会被分割成两个或多个不同的子网。而在广播心跳方式中，每个节点将 工作状态封装在数据包中，通过网络广播给集群中的其他所有节点，该方式使得 节点不需要通过任何中介节点就能获得任意节点的心跳信息，所以不会产生网络 分割的问题，但是广播的数据包数量n 木( n - 1 ) 远大于环形心跳的n 。 图2 1 心跳检测机制的实现形式 第7 页 国防科学技术大学研究生院硕士学位论文 高可用集群中的心跳模块通常包含以下一些进程：主进程( m a s t e rp r o c e s s ) ，读 进程( r e a dp r o c e s s ) ，写进程( w r i t ep r o c e s s ) ，f i f o 进程( f i f op r o c e s s ) 以及通信管道 ( c o m m u n i c a t i o np i p e ) 和主状态管道( m a s t e rs t a t u sp i p e ) t 】。其进程工作过程( 如图2 2 左) 为主进程启动后，设置时钟周期并将本地节点信息写入f i f o 。控制进程从f i f o 获取数据包，将信息写入通信管道和主状态管道。写进程从通信管道获取数据包， 并通过心跳传输介质传递给读进程。读进程获取从心跳传输介质传输过来的数据 包并将其写入主状态进程。 主状态进程获取节点状态信息时将节点的时间信息更新为当前时间t i ，在集 群中其他节点获取心跳信息时利用时间差来判定节点是否失效，公式为： r = r r r d ， 其中t i 为当前时间，t d 为主状态进程设置的时钟周期，也就是节点的失效周期。 如果t 乏t 则认为节点正常，否则判定节点失效【1 2 1 。图2 2 右为基于心跳的集群节 点的状态转换图，心跳启动时节点进入初始状态，当主状态进程启动后节点进入 u p 状态，当相互通信的两个节点收到心跳信息时进入激活状态，如果节点在时钟 周期内没有收到另外节点的心跳信息则判定该节点失效【】。 心跳检测机制采用两种监控模式：推模式和拉模式【1 0 1 。在推模型中，被监控 目标是活动的，它周期性的向监控者发送心跳信号表明自己是活跃的，如果监控 者在一定的时间间隔内没有收到被监控目标发来的信号就通知客户被监控目标已 经失效。在拉模型中则是监控者向被监控目标发送心跳信号，如果在规定的间隔 内收到了被监控目标的响应信息就说明被监控目标是活跃的否则宣告其死亡。由 于心跳机制实现了消息重传协议来保证消息的可靠传递，在推模型中由于被监控 目标的消息都需要确认，使得目标发送的数据包成倍增长，造成n a c k 内爆。在拉 模型中监控目标检测到数据包丢失就会请求监控者重新发送数据包，采用这种模 型容易造成a c k 内爆。 图2 2 心跳框图及状态转换图 v m m c ( v i r t u a lm e m o r y m a p p e dc o m m u n i c a t i o n ) 中主节点周期性地向备份节点 第8 页 国防科学技术大学研究生院硕士学位论文 发送信号【1 3 】，如果备份节点在一定间隔内没有收到主节点发送的连续信号，就会 质疑主节点已经发生故障，进而激发选举协议来确定主节点发生故障或是应用进 程受到损坏，抑或是主节点与备份节点之间的连接被破坏。他们实现的主要方法 是利用网络接口来实现故障检测，网络接口周期性地向网络注入心跳信号，备份 节点的网络接口在一定时间内没有收到心跳信号就认为主节点发生故障，该方法 的优点是心跳的频率会更快，时效性高，但需要专门的网络接口支持。 c l u s t e r r a 系统中采用的是环形心跳检测机制4 1 ，系统中每个节点负责从邻居 节点接收信号并向邻居节点传递存活信号，该检测机制除用于节点状态的检测外 还能检测到节点提供的服务集合状态的改变。其分布式结构决定了不存在关于所 有节点的信息，从而引进虚拟节点集协议来维护可用节点的一致性状态。如果节 点集合中的某个节点连续丢失了心跳信号则会激活虚拟节点集协议，节点协调者 负责向所有节点发送建立节点集的信号，如果某个节点在规定的时限内未能发送 响应信号，则认为该节点发生故障，继而从可用节点集合中删除该节点。该系统 在激活虚拟节点集合之前减少缺失信号检测的数量，这样能缩短节点故障到重新 激活的时间，但该方案的执行可能增加错误判定节点故障的风险，譬如网络的不 稳定性使存活信号丢失，但节点却没有发生故障【l6 1 。为减少备份服务器升级为主 服务器的宕机时间，系统使用锁机制维护热备份副本，同时为减少二次故障对系 统造成的影响，系统将重做日志传递到不同站点的节点上，这样当备份发生故障 时能利用非本地站点的重做日志恢复本地数据。c l u s t e r r a 系统为提高系统的可用 性采用无共享结构，系统将数据进行分区，分区的数据存储在不同的节点，这样 一个节点的故障只能影响到原来应用的1 n ( n 为分区数据存储的节点数) ，节点的 恢复时间也较原来要短。 随着心跳机制应用的推广，适应不同应用需求的改进心跳机制也在不断发展 完善。对时效性很高的系统来说，时钟周期较长则会使得系统需要较长时间才能 发现节点的故障，从而降低了系统响应请求的时效性。而在服务请求的间隔较长 但时钟周期设置较小时，服务处于主服务器的等待队列中，系统很可能因为偶然 的网络不稳定性而错误的认为主服务器发生故障而将服务切换到从服务器，上下 文切换的开销使得系统响应服务的时效性大大降低，更严重的是系统很有可能在 服务器间来回切换使得服务得不到响应。根据应用的动态变化研究人员采用了一 种动态的方法设置时钟周期，时钟周期的设置根据当时的负载和应用的执行周期 而定 6 1 。系统截获前5 个请求的时钟周期，并取平均值来设定当前请求的时钟值。 如果平均时钟比较密集则将时钟周期设定为正常时钟周期的一半，如果是非常密 集则设定为1 4 1 2 】，这样系统就能根据请求的特性来设定当前的时钟周期值，大大 提高了系统响应服务的时效性。 第9 页 国防科学技术大学研究生院硕士学位论文 根据心跳机制监控模式带来的内爆现象，研究人员采取限制消息包的重发频 率来有效减少甚至消除内爆的产生【l o j 。同时为确定消息包丢失的时间间隔，系统 采取心跳信息和普通信息以相同渠道和方式发送的方法。为了增强心跳机制对应 用检测的精确性，k y li n 系统对应用进行分级检测，第一级为操作系统查找进程表； 第二级为应用调用系统设置检查点；第三级为系统发送信号给进程以中断进程， 使进程进行一定的处理，三个级别能提供不同的应用检测精确度。 2 2 连接迁移 连接迁移是实现故障切换的中心环节，连接迁移技术的最初研究不是基于故 障切换而是解决负载均衡的问题，当前关于连接迁移的技术主要有以下几种： 基于客户端的连接迁移技术：该方法需要客户端拥有关于所有服务器的信息， 当发现一台服务器过载或是发生故障的时候，客户主动绕过该服务器进而实现负 载均衡和故障切换。b e r k e l e y 研究的s m a r tc l i e n t1 1 6 】是一种基于客户端的解决方法。 j a v aa p p l e t 服务在客户方浏览器中运行，a p p l e t 向各个服务器发请求来收集服务 器的负载等信息，再根据这些信息将客户的请求发送到相应的服务器。高可用性 也在a p p l e t 中实现，当服务器没有响应时，a p p l e t 向另一个服务器转发请求【l 丌。 该方法的缺点是对客户的透明性不好。 基于i p 层的连接迁移技术：该方法主要利用虚拟i p 的技术来实现。客户通过 虚拟i p 访问服务时，虚拟服务器主机会截获到这些信息，虚拟服务器主机通过一 定的策略从真实的服务器中选择一个来作为响应服务器i l 引。虚拟服务器会将客户 请求报文的目标地址换成真实服务器的地址，而选定服务器的响应报文经过虚拟 服务器时就会由它修改其原地址为虚拟服务器的地址，再转发给客户【l9 1 。该方法 的优点是对客户透明，但需要设置虚拟服务器。 基于t c p 迁移的技术：其丰要思想是通过对t c p 协议栈的修改，使客户端和 服务器端能通过协商的方式完成连接的迁移1 1 8 】。修改后的t c p 协议是对标准协议 的扩充，所以两者兼容，并且可以进行互操作。如果客户端和服务器端都安装扩 展t c p 协议则可进行连接迁移，如果任意一端没有安装扩展协议，则只能按标准 协议进行通信，此时系统不具有连接迁移的功能【2 0 1 。扩充的t c p 协议是在原协议 上增加同步标志和连接标志，同步标志( s y n ) 字段可作为先前建立的连接部分， 而连接标志则标识【地址，端口】建立的连接，系统初始化时必须利用连接迁移选项 初始化该标志1 2 1 1 。当成功创建连接时，t c p 就能利用【源地址，源端口，连接标志】 建立连接f l9 1 。这样当主服务器发牛故障后，可以从备份服务器获得先前建立的t c p 连接信息，通过发送能标志连接的迁移s y n 来获得备份服务器与客户端的同步连 接，这样客户端的请求通过连接迁移之后全部转发给备份服务器。其优点是系统 第1 0 页 国防科学技术大学研究生院硕士学位论文 的前端( f r o n t e n d ) 能根据客户请求的内容按照定的策略将请求透明地调度到可 用的后台( b a c k e n d ) 服务器上1 1 6 】。后台服务器经响应直接发送给客户，减少了延 迟 5 1 。m i t 设计和实现了一个细粒度，连接级的故障切换机制旧，该项目( t h e m i g r a t ei n t e r n e tm o b i l i t yp r o j e c t ) 改进基于t c p 迁移的技术，没有利用传统的前端 应用层和传输层交换技术，从而消除了前端性能瓶颈问题。该技术能很好的应用 到集群的连接迁移过程之中，最终的测试结果显示这是一种对应用透明的鲁棒性 好，快速的以及细粒度的故障切换机制，但他们的方法需要修改操作系统的协议 栈。 连接迁移的技术还有很多，譬如基于d n s 解析的技术【2 ，但是该技术需要一 个d n s 服务器做域名解析，开销相对较大，所以关于其著述所涉不多。另外还有 一些正在开展的项目，l a r d 1 6 】是美国r i c e 大学与i b m 合作的一个关于连接迁移 的项目，他们是在b s d 上实现t c p 迁移并提出了l a r d 算法。 2 3 分布式选举机制 选举( e l e c t i o n ) 是集群系统中常用的计算类型，它从节点集中选出一个节点执行 特别的任务1 2 2 1 。例如，在集群系统节点出现故障后，通常需要重新组织活动的节 点使它们继续执行任务。选举过程分两个阶段：( a ) 选择一个具有最高优先级的协 调者；( b ) 通知其他进程谁是协调者。同时必须保证：( 1 ) 参与节点的协调者标识 为空或者在算法运行结束时具有最大标识的非崩溃节点。( 2 ) 所有节点都参加选举 并置协调者标识为非空，或者节点崩溃f 6 】，本节主要分析两种经典的选举算法。 2 3 1 b u l l y 算法 b u l l