储佳佳,郭进伟,刘柏fl,张晨东,钱卫宁

(华东师范大学数据科学与工程研究院,上海200062)

高可用数据库系统中的分布“一致性协议

储佳佳,郭进伟,刘柏fl,张晨东,钱卫宁

(华东师范大学数据科学与工程研究院,上海200062)

可用性和一致性是分布式数据库系统中的两个重要特性和基础,需要借助分布式一致性协议来保证.保证一致性需要使用一致性协议为并发的事务更新操作确定一个全局的执行顺序,并协调局部状态和全局状态不断地达到动态一致.可用性的实现,需要一致性协议协调多副本之间的一致来实现主备节点的无缝切换.可见,分布式一致性协议是高可用数据库系统的实现基础.本文梳理、综述了经典的分布式一致性协议以及一致性协议在高可用数据库系统中的主要应用,并对分布式一致性协议的实现代价和局限性进行了分析与评估.

高可用性;一致性;分布式一致性协议;分布式数据库

0 引言

随着数据规模的不断扩大,分布式数据库系统得到了越来越广泛的运用.数据分片存储、多副本冗余和多副本并发更新这些机制为分布式数据库系统带来了可扩展、高并发等优点的同时,也引入了一致性、可用性的问题[1].

定义1实现分布式数据库系统的动态一致性,需要保证:

(1)状态一致性,事务不能破坏数据库的完整性、外键约束以及业务逻辑上的一致性.

(2)操作一致性,并发的事务在各个局部节点上串行化执行顺序和全局的串行化执行顺序是等价的.

(3)多副本一致性,主节点和冗余备份节点之间数据的更新序列是一致的.

分布式数据库系统的一致性需要确保事务的串行化执行顺序、事务的最终状态是全局一致的.保证了定义1中的状态一致性、操作一致性、多副本一致性,就可以实现全局状态和局部状态不断地从一个一致的状态到达另一个一致状态,实现一种动态的一致.可用性指数据库系统能够自动容错,持续地对外提供服务.根据CAP理论[2],分布式环境下,可用性和一致性只能保证一点.然而,一致性和可用性的权衡不必是一个达到极致,另一个完全不优化(取值不必是0或1,可以是0%至100%).一致性可分为极致一致性、强一致性、最终一致性和弱一致性等多个级别,可用性可分为较高可用性、高可用性和弱可用性等.不同级别的可用性一致性组合可满足不同的应用需求.很多互联网应用对一致性要求不高,采取最终一致和较高可用的组合,这是一种一致性换可用性的做法.对一致性要求较高的关键应用,比如银行系统和金融证券业,可以采取强一致性和高可用的组合,在保证多数派副本完全一致的前提下,将可用性尽可能地最大化[3].实现数据库系统的强一致性,关键是选取合适的分布式一致性协议(distributed consensus protocol)来保证一致性.由于数据分布在多个节点和网络的不确定性等因素,各个节点上的数据更新是相互隔离并且各自独立进行的.可能会出现的问题有:①各个节点上分布式事务的执行状态不同(对应定义1中状态一致性);②更新顺序不同(对应定义1中操作一致性);③主备副本数据不同步(对应定义1中的多副本一致性)的问题,需要使用分布式一致性协议来协调分布式事务的提交、多节点并发更新和主备节点操作序列的同步,保证分布式数据库系统的状态一致性、操作一致性和多副本一致性.

保证数据库系统的高可用性,分布式一致性协议同样至关重要,因为多副本一致性是系统进行主备切换的前提.高可用的数据库系统通常采取“主备架构”,其中主节点对外提供服务,备节点作为主节点的冗余备份,存储着和主节点相同的数据.当主节点出现故障宕机时,期望是选取某个备节点成为新的主节点.借助于分布式一致性协议,可以确保多副本一致性,使得主备节点的状态数据始终是一致的.当主节点发生故障时,备节点就可以无缝切换为主节点来接管集群,使系统持续对外提供服务.

综上,分布式一致性协议是实现强一致性和高可用性的重要基础.本文梳理并总结了前人在设计一致性协议探索高可用数据库系统方面进行的研究工作,并给出了分析和评价.第1节简要介绍了经典的一致性协议;第2节借助成熟的分布式数据库系统来说明分布式一致性协议在高可用数据库系统中都有哪些方面的应用;第3节从消息交互次数和延迟两个方面对分布式一致性协议进行了代价评估,同时也对一致性协议运用到实际系统中的局限性进行了整理和分析;第4节对未来的研究工作进行了展望.

1 分布式一致性协议概述

为了解决分布式环境下的一致性问题,前人探讨并设计了很多策略,例如两阶段提交协议[4-6]、Paxos算法[7-9]等,这些策略很多已经成为了工业标准,在工程实践中得到了越来越广泛的运用.图1呈现了分布式一致性协议的发展简史.

图1 分布式一致性协议Fig.1A brief history of the distributed consensus protocols development

如图1所示,两阶段提交协议通过预提交阶段(投票阶段)和正式提交阶段的两轮消息交互,使得协调者和参与者可以就某项决定达成一致,该协议的详细步骤在相关论文中有具体的介绍.三阶段提交协议[10]是两阶段提交协议的优化,解决了两阶段提交协议的阻塞问题.Quorum[11]算法由Gifford于1979年提出,主要数学思想来源于鸽巢原理,通过限定读写操作最小参与的副本数目,实现读写操作的互斥来支持多副本的并发更新.Basic Paxos算法是Leslie Lamport于1998年提出的一种基于消息传递模型且具有高度容错特性的一致性算法.通过“提案阶段(Prepare)”和“接受阶段(Accept)”两个阶段使得提案者(proposer)和接受者(acceptor)就某项决议达成一致.除了Basic Paxos,Lamport还研究了多个变种算法,如Cheap Paxos[12]、Fast Paxos[13]和Vertical Paxos[14]等.Raft算法[15]是斯坦福大学的Diego Ongaro和John Ousterhout研究的一个管理日志复制的一致性算法.表1中呈现了上述一致性协议的特性.

综合考虑分布式一致性协议的发展历程和特性,可以发现它们之间存在着微妙的继承关系和相关性.比如Paxos算法融合了两阶段提交协议和Quorum算法的思想,通过Quorum算法W＞N/2(W为参与更新操作的最小副本数;N为系统中的总副本数)的“多数派”思想来实现更新操作的互斥性,使得只有一个决议值会被“多数派”节点认可.两个阶段(提案阶段和接受阶段)的消息交互借鉴了两阶段提交的思路,保证多个节点之间更新操作的一致性.通过两轮信息交互,多数派达成一致的决议值,其状态一定是确定的(要么是已提交状态,要么是失败状态).引入“多数派”的思想,减小了系统阻塞问题的发生概率,不需要确保系统中所有节点通信状况良好,只要保证至少存在多数派节点的通信状况正常,系统就是可用的,“多数派”的策略一定程度上提高了系统的可用性.

相较于两阶段提交协议,Paxos增加了一种“学习者”角色,将“参与者”的功能一分为二,即“参与决策”交由“接受者”,“知晓决定”交由“学习者”.“接受者”和“学习者”的角色可以由同一节点来担任(此时等同于两阶段提交协议中的“参与者”),也可以由不同节点来承担.这种更灵活和细化的角色分工,使得“参与决策”和“知晓决定”两个功能彼此分开,从某种意义上减少了系统阻塞的发生概率.

Raft算法是Paxos算法的变种,使用更加严格的消息传递方式以及选举规则,使得算法更加易于理解和工程实现.Raft算法引入了选举期(term)的概念,用于标识从当前轮次的选举开始至下一轮选举开始的这段时期.每个选举期内,所有的伴随者只能投票给一个候选者,这种“先到先得”的投票规则,相较于Paxos算法中的接受者可以多次投票、每次需要回复已接收到的最大决议值的做法,要更加清晰和简单.

表1 分布“一致性协议的特性简析Tab.1A brief analysis of the distributed consensus protocols

2 分布式一致性协议在高可用数据库系统中的应用

实现分布式数据库的强一致性和高可用性,需要引入分布式一致性协议,来协调分布式事务的提交(状态一致性)、多节点并发更新(操作一致性)和主备节点操作序列的同步(多副本一致性).这些落实到具体系统中,需要实现“分布式事务提交”、“主节点选举”和“日志同步”三个模块.本节首先简要介绍了上述三个模块的通用设计思路,并在2.2节中借助GoogleSpanner和OceanBase进行了具体的探讨.

2.1 应用概述

分布式事务的一致性提交,保证了分布式事务的原子性.分布式事务的相关节点需要就事务的最终状态(提交或失败)达成一致,不能出现某些节点局部提交事务的情况.如果违背了事务的原子性,状态一致性则无法保证.通用的分布式事务提交策略通过两阶段提交协议来实现,经过投票阶段和提交阶段的信息交互,使得协调者和参与者看到的事务最终状态是一致的.

主节点的选举,指的是从系统中的所有节点中选取领导者,如图2所示.领导者可以是整个系统的管理者、主副本或是分布式事务的协调者.领导者往往是全局唯一的,并且能被所有节点感知到的节点,选领导者的问题是分布式节点就“领导者信息”达成一致的问题.根据选举规则的不同,选举可分为“不基于节点状态”和“基于节点状态”的两类.若领导者的选取,对节点的状态和功能无特殊要求,可选取任意活跃的节点成为领导者,选举则是“不基于节点状态”的.“不基于节点状态”的选举,可以采取Raft中“先到先得”,或是欺负算法和环算法[16]中“进程号最大优先”的策略来制定选举规则.若选举需要考量节点的状态,即对节点的状态、通信状况和功能等有一定的要求时,往往需要采取基于消息传递的一致性算法,比如Paxos算法,让竞选者通过消息交互,针对某些属性值进行较量,来进行选举.

图2 主节点选举Fig.2Election of the master-node

日志同步,或称为日志数据的复制,用于主备节点之间同步更新操作的序列,如图3所示.主节点将更新操作以日志记录的方式发送给备份节点,备节点通过执行这些日志记录中的更新操作,达到和主节点一致的状态.主备节点的日志记录必须是相同和确定的,日志同步问题即是分布式节点就“每个日志号对应的日志内容”达成一致的问题.主备节点的日志同步,主要包括两种策略,立即复制(Eager replication)和延迟复制(Lazy replication)[17].立即复制将同步到备机的操作并入事务的更新操作中,在立即复制模式下,主节点需要收到备份节点关于日志同步操作的回复之后,才能提交事务并答复客户端,确保已提交的事务在备节点中一定有相应的日志记录,实现主备节点之间的强一致性.在延迟复制的模式下,主节点执行更新操作,同时异步地向所有备机发送日志,主节点不用等到备机回复即可提交事务.

图3 日志同步Fig.3Log synchronization

2.2 新型DBMS中分布式一致性的实现

为了实现系统的高可用性,分布式一致性协议已经被广泛地应用到很多成熟的数据库产品中,本节通过介绍Google Spanner和OceanBase系统中处理分布式事务、主节点选举和日志同步的设计思路,来分析新型分布式数据库系统的高可用策略,并在表2中呈现结论.

表2 主流数据库系统的高可用策略Tab.2High availability strategies for popular database systems

Spanner[18]是由Google公司研发的一个全球分布式的、多版本、支持同步复制的可扩展数据库.采用两阶段提交协议来协调分布式事务的提交,主节点选举和日志同步都是基于Paxos算法的.Spanner以基于时间戳的方式实现了数据读写的全局一致性,在TrueTime API提供的精确时间戳的基础上,通过Paxos选举产生领导者来协调、管理事务提交的绝对时间和提交次序,进而保证数据的读写一致性.关于日志同步,主节点向多个备份节点同步redo日志,同步流程和Paxos的两个阶段类似,通过Paxos协议保证主备节点之间日志序列的确定性和一致性,从而保证数据在多个副本上是一致的.

OceanBase[19-21]是由阿里集团研发的支持海量数据、可扩展的高性能分布式数据库.开源版本OceanBase 0.4.2中,借助第三方软件Linux HA来进行主备切换,Linux HA通过心跳监控集群管理节点(集群管理节点是整个集群的管理者和协调者,管理系统中的所有节点,并维护元数据表的信息),一旦检测到主集群管理节点故障Linux HA会将Vip漂移到备份的集群管理节点,来实现主备节点的切换.OceanBase 0.4.2的日志同步使用的是主备复制的模型,日志同步发生在主备事务管理节点之间.OceanBase系统执行更新操作时,主事务管理节点需要将操作日志发送到备机,备份事务管理节点通过回放操作日志达到和主事务管理节点一致的数据库状态. OceanBase 0.4.2同样是通过两阶段提交协议来协调分布式事务的提交.

Cedar[22]和CBase都是在OceanBase 0.4.2基础上研发的分布式数据库系统.考虑到Ocean-Base 0.4.2中的主备集群管理节点的切换机制不够灵活(需借助第三方工具LinuxHA),并且主备事务管理节点之间日志不是强同步的,Cedar设计并实现了支持三集群架构、基于Paxos的主节点选举和日志强同步.CBase中的主节点选举采取的是LEBR算法,日志同步采取的是MTS算法,LEBR和MTS算法[23]与Raft算法中的领导者选举、日志同步相类似,是Raft算法在工程实践中的一种优化.Cedar采取三集群的架构,即一个主集群,两个备集群,当主集群故障时,会触发选举,其中一个备集群可自动地切换为主集群,实现自动容错,并继续对外提供服务. CBase采取“一个逻辑大集群、多个物理小集群”的部署架构,系统中有一个主集群管理节点,多个备用管理节点,当主管理节点故障时,主节点选举会被触发,系统会自动地从多个备用管理节点中选举出新的主管理节点,来接管集群.Cedar和CBase的日志同步都是强同步、强一致的,主事务管理节点需要将日志同步到多数派备用事务管理节点,并接收到多数派的回复后才可以提交事务.

3 高可用系统中一致性协议的应用分析

不同的分布式一致性协议在具体应用过程中,会有不同的代价开销.本节将从消息数目和延迟两个方面对一致性协议进行代价分析,并结合生产环境中存在的异常干扰因素,分析一致性协议的局限性.

3.1 一致性协议的代价分析

设定系统中有N个节点,其中1个为主节点,其他N-1个节点为主节点的备份节点,各个节点之间通信状况良好并且不存在拜占庭故障[24].本节的后续分析都基于上述设定,并通过表3简要呈现了本节探究工作的结论.

表3 分布“一致性算法的代价估计Tab.3Cost estimation of the distributed consensus algorithms

结论1运用两阶段提交协议,使得各个节点就某个决议达成一致,需要的消息数目为3N-3,消息延迟为3次.

预提交阶段,协调者向系统中所有参与者发送预提交请求,消息数目为N-1.当参与者接收到协调者发来的预提交请求后,会向协调者进行回复,消息数目为N-1.如果协调者收集到所有参与者针对预提交请求的回复,可向系统中所有参与者发送提交请求,消息数目为N-1.至此,协调者已做出提交决定,并且已经和参与者达成一致.综上,协调者和参与者达成一致需要的消息数目为3N-3,消息延迟为3次[25].

结论2运用Quorum策略,使得各个节点就某个决议达成一致,需要的消息数目为2R(NWR机制中参数R的取值)或2W(NWR机制中参数W的取值),消息延迟为2次.

Quorum策略的NWR机制在第一章中已经具体介绍过,基于Quorum策略,执行读操作时,需要至少读取R个副本,执行写操作需要至少在W个副本上更新成功.分析可知,进行读操作,客户端需要询问R个副本,R个副本接收到客户端的读操作请求时会对客户端进行回复,需要的总的消息数目为2R,消息延迟为两次;进行写操作时,客户端将写操作的请求发送到W个副本,W个副本执行该写请求并对客户端进行应答,需要的消息数目为2W,消息延迟为两次.

结论3运用Paxos算法,使得各个节点就某个决议达成一致,需要的消息数目为2k×N,消息延迟为4次.

假设系统中有k个提案者,提案阶段,提案者(proposer)向系统中多数派节点发送提案请求,消息数目为,当接受者(acceptor)接收到提案请求时,会向提案者进行承诺(具体可参考第一章Paxos算法的介绍),消息数目为.在接受阶段,提案者向多数派节点发送决议,消息数目为,接受者接收到决议值时,会对提案者进行回复,消息数目为.可知,总共需要的消息数目为2k×N,消息延迟为4次.

结论4运用Raft算法,使得各个节点就某项决议达成一致,选举leader需要的消息数目为(k+1)×N一2k,消息延迟为2次,日志同步需要的消息数目为3N一3,消息延迟为3次.

Raft算法将节点之间达成一致的问题分为了领导者选举和日志同步两个独立的子问题.领导者选举过程中,假设有k个候选者(candidate),候选者向系统中所有的参与者(follower)发送投票请求,消息数目为k×(N一1).参与者接收到候选者的投票请求后,会向候选者进行投票回复,消息数目为N一k.可知,总共需要的消息数目为(k+1)×N一2k,消息延迟为2次.

对于领导者和参与者之间的日志同步,领导者需要将日志发送给系统中所有参与者,消息数目为N一1.参与者接收到日志信息后,向Leader进行回复,消息数目为N一1.当领导者接收到多数派参与者关于某条日志的应答消息后,会提交该日志,将提交日志号写入下一批日志记录中,发送给参与者,消息数目为N一1.可知,总共需要的消息数目为3N一3,消息延迟为3次.

结论5运用LEBR算法,选举Leader需要的消息数目为(k+3)×N一2k一2,消息延迟为4次.

LEBR算法将主节点的选举分为了投票和广播两个阶段,假设共有k个备选者(Candidate).投票阶段,备选者会向所有追随者(Follower)发送投票请求,消息数目为k×(N一1).参与者接收到备选者的投票请求后,会向候选者进行投票回复,消息数目为N一k.在广播阶段,获得多数派支持票的备选者可以向所有的追随者发送广播请求,消息数目为N一1,追随者接收到备选者的当选广播请求时,会更新领导者的信息,并对备选者进行回复,消息数目为N一1,接收到多数派追随者对于当选广播的回复后,备选者才会进行身份切换,成为领导者,至此,选举结束.可知,总共需要的消息数目为(k+3)×N一2k一2,消息延迟为4次.

结论6运用MTS算法,使得主备事务节点就某条日志信息达成一致,需要的消息数目为3N-3,消息延迟为3次.

MTS算法中,进行一次日志同步,主TNode首先需要将日志发送给系统中所有备TNode,消息数目为N一1.备TNode接收到日志信息后,向主TNode进行响应,消息数目为N一1.当主TNode接收到多数派备TNode关于某条日志的应答消息后,会提交该日志,将提交日志号写入下一批日志记录中,发送给参与者,消息数目为N一1.可知,总共需要的消息数目为3N一3,消息延迟为3次.

3.2 分布式一致性协议的应用局限性分析

分布式一致性协议都不可避免得具有一定的局限性.实际的系统需要从工程角度,针对不同的应用场景,对协议进行一些调整和优化.

两阶段提交协议在运用到实际系统中时,若出现了协调者宕机或是协调者和参与者网络通信故障,系统会进入阻塞状态.阻塞问题已经在表1中详细介绍,此处不再赘述.在系统实现过程中,往往通过引入“超时机制”和“多副本机制”解决阻塞问题,超时机制保证节点不会永久等待,多副本机制消除了单节点故障导致的系统阻塞.

基于Quorum算法的NWR机制,由于支持多副本并发更新,会出现多副本之间日志顺序不一致的问题.以至于执行读操作时,从R个副本中读取数据会出现冲突.所以将Quorum算法运用到实际系统中时,需要在上层增加一些应用来协调多副本写入顺序不同的冲突.

Paxos算法支持多个Proposer交替发起提案,可能会出现长期无法就某个提案达成一致的情形(论文中提到的局限性).所以在系统实现过程中,往往会先选出一个主副本,每次仅由主副本发起提案请求,避免交替提案的情况发生.

Raft算法中的领导者选举策略在实际运用过程中,可能会出现“双领导者”和“频繁选主”的问题.“双领导者”指系统中出现了两个领导者,而“频繁选主”指的是领导者不合理得频繁发生变化.引发上述两个问题的原因是分布式环境中的网络通信故障.当选定的领导者和其他伴随者处于两个不同的网络分区中,相互之间无法通信时,其他的伴随者可能会因为超时从而选出新的领导者,旧领导者感知不到这一切的发生,依然尝试着给所有伴随者发送心跳信息,此时B出现了“双领导者”.若某个伴随者和领导者通信不上,由于接收不到领导者的心跳,该伴随者会认为系统中没有领导者存在,从而增大选举期(Term)的值发起选举操作.一旦该伴随者得到多数派节点的支持,它将成为领导者.而旧领导者接收到其他参与者的反馈的选举期信息,发现自己选举期的值较小,将切换身份变为追随者,切换为追随者的旧领导者由于接收不到新领导者的心跳(通信故障依然存在),很可能再次发起选举并赢得选举,系统就进入了“频繁换主”的不稳定状态.“双领导者”和“频繁选主”在实际生产环境中是很容易发生的两个不合理状态,所以,真正将Raft运用到实际系统中时,需要额外增加一些策略,例如CBase中就通过增加“租约机制”和“广播阶段”等策略来规避”频繁选主“和”双领导者“两个异常状况.

4 总结与展望

分布式一致性协议是实现数据库系统高可用性的基础.本文梳理和分析了流行的分布式一致性协议的特点、代价开销以及应用局限性,并借助一些成熟的数据库系统来介绍生产实践中如何通过分布式一致性协议来实现分布式事务提交、主节点选举和日志同步.随着数据规模的不断扩大,使用分布式数据库系统是必然的发展趋势.未来的研究工作,将基于学界和工业界已有的分布式一致性理论和成熟的数据库产品,探究并设计普适和完整的高可用方案来解决分布式数据库系统中的一致性和可用性问题.

［1］LAMPSON B W.How to build a highly available system using consensus[C]//International Workshop on Distributed Algorithms.Springer-Verlag,1996:1-17.

［2］GILBERT S,LYNCH N.Brewer’s conjecture and the feasibility of consistent,available,partition-tolerant web services[J].Acm Sigact News,2002,33(2):51-59.

［3］BREWER E A.Towards robust distributed systems(abstract)[C]//Nineteenth ACM Symposium on Principles of Distributed Computing.ACM,2007:7.

［4］GRAY J N.Notes on data base operating systems[C]//Advanced Course:Operating Systems.Springer-Verlag, 1978:393-481.

［5］MOHAN C,LINDSAY B,OBERMARCK R.Transaction management in the R*distributed database management system[J].ACM Transactions on Database Systems,1986,11(4):378-396.

［6］LAMPSONBW,LOMETDB.ANewPresumedCommitOptimizationforTwoPhaseCommit[C]//International Conference on Very Large Data Bases.Morgan Kaufmann Publishers Inc,1993:630-640.

［7］LAMPORT L.Paxos made simple[J].AcmSigact News,2001,32(4):1-11.

［8］CHANDRA T D,GRIESEMER R,REDSTONE J.Paxos made live:An engineering perspective[C]//Twenty-Sixth ACM Symposium on Principles of Distributed Computing.ACM,2007:398-407.

［9］LAMPORT L.The part-time parliament[J].Acm Transactions on Computer Systems,1998,16(2):133-169.

［10］SKEEN D.Nonblocking commit protocols[C]//ACM SIGMOD International Conference on Management of Data, Ann Arbor,Michigan,April 29-May.1981:133-142.

［11］GIFFORD D K.Weighted voting for replicated data[C]//ACM Symposium on Operating Systems Principles. ACM,1979:150-162.

［12］LAMPORT L B,MASSA M T.Cheap paxos:IEEE,US 7249280 B2[P].2007.

［13］LAMPORT L.Fast Paxos[J].Distributed Computing,2005,19(2):79-103.

［14］LAMPORT L,MALKHI D,ZHOU L,et al.Vertical paxos and primary-backup replication[C]//Principles of Distributed Computing,2009:312-313.

［15］ONGARO D,OUSTERHOUT J.In search of an understandable consensus algorithm[R/OL].[2016-07-07]. https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf

［16］COULOURIS G,DOLLIMORE J,KINDBERG Tet al.Distrinbuted Systems Concepts and Design[M].5版.北京:机械工业出版社,2015:378-380.

［17］GRAY J.The dangers of replication and a solution[J].AcmSigmod Record,1996,25(2):173-182.［18］CORBETT J C,DEAN J,EPSTEIN M P,et al.Spanner:Google’s globally-distributed database[C].Operating Systems Design and Implementation,2012:251-264.

［19］阳振坤.OceanBase关系数据库架构[J].华东师范大学学报(自然科学版),2014(5):141-148.

［20］李凯,韩富最.OceanBase内存事务引擎[J].华东师范大学学报(自然科学版),2014(5):149-163.

［21］杨传辉.OceanBase高可用方案[J].华东师范大学学报(自然科学版),2014(5):173-179.

［22］张晨东,郭进伟,刘柏众,等.基于Raft一致性协议的高可用性实现[J].华东师范大学学报(自然科学版),2015(5):172-184.

［23］庞天泽.可扩展数据管理系统中的高可用性实现[D].上海:华东师范大学计算机科学与软件工程学院.2016.

［24］LAMPORT L,SHOSTAK R,PEASE M.The byzantine generals problem[J].Acm Transactions on Programming Languages&Systems,1995,4(3):382-401.

［25］GRAY J,LAMPORT L.Consensus on transaction commit[J].Acm Transactions on Database Systems,2010, 31(1):133-160.

(责任编辑:李万会)

On the distributed consensus protocol in high-availability database systems

CHU Jia-jia,GUO Jin-wei,LIU Bo-zhong,ZHANG Chen-dong,QIAN Wei-ning
(Institute for Data Science and Engineering,East China Normal University, Shanghai200062,China)

Availability and consistency are the two important characteristics of the distributed database systems,which need to be guaranteed by the distributed consensus protocol.Ensuring consistency requires a consensus protocol to determine a global execution sequence for concurrent transaction updates,and to coordinate the consistency between local states and the global state continuously.For the implementation of the availability,we need to coordinate the consistency between the multiple backups to achieve the seamless switch between the main and backup nodes.Visible,distributed consistency protocol is the basis for the realization of high availability database system.Distributed consensus protocol is the base of high availability database systems.This paper summarizes the classical consistency protocols and the main applications in high-availability systems of the distributed consistency protocols.Meanwhile,the implementation costs and limitations of the consistency protocols are analyzed and evaluated.

high availability;consistency;distributed consensus protocol;distributed database

TP392

A

10.3969/j.issn.1000-5641.2016.05.001

1000-5641(2016)05-0001-09

2016-05

国家自然科学基金重点项目(61332006);国家863计划项目(2015AA015307)

储佳佳,女,博士研究生,研究方向为数据库系统.E-mail:cjj25233@163.com.

钱卫宁,男,教授,博士生导师,研究方向为社交媒体数据管理与分析、互联网环境的数据管理与基准评测、基于开放信息的知识图谱构建与利用等. E-mail:wnqian@sei.ecnu.edu.cn.