数据一致性理论

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,数据一致性理论,1,2.1 CAP,理论,CAP,理论由,Eric Brewer,在,ACM PODC,会议上的主题报告中提出，这个理论是,NoSQL,数据库管理系统构建的基础，如下图所示：,2,其中字母“,C,”,”A”,”P”,分别代表以下三个特征：,强一致性（,Consistency,）。系统在执行过某项操作后仍然处于一致的状态。在分布式系统中，更新操作执行成功后所有的用户都应该读取到最新值。,可用性（,Availability,）。每一个操作总是能够在一定时间内返回结果。需要注意“一定时间”和“返回结果”。,“一定时间”是指，系统结果必须在给定时间内返回。,“返回结果”是指系统返回操作成功或失败的结果。,分区容错性（,Partition Tolerance,）。分区容错性可以理解为系统在存在网络分区的情况下仍然可以接受请求（满足一致性和可用性）。,3,CAP,是在分布式环境中设计和部署系统时所要考虑的三个重要的系统需求。根据,CAP,理论，数据共享系统只能满足这三个特性中两个，而不能同时满足三个条件。因此系统设计者必须在这三个特征之间做出权衡。,根据,CAP,理论，系统满足三个条件中不同的两个条件会具有不同的特点。如下表所示：,序号,选择,特点,例子,1,C,、,A,两阶段提交、缓存验证协议,传统数据库、集群数据库,2,C,、,P,悲观加锁,分布式数据库、分布式加锁,3,A,、,P,冲突处理、乐观,DNS,、,Coda,4,2.1,数据一致性模型,一些分布式系统通过复制数据来提高系统的可靠性和容错性，并且将数据的不同的副本存放在不同的机器，由于维护数据副本的一致性代价高，因此许多系统采用若一致性来提高性能，一些不同的一致性模型也相继被提出。,强一致性：要求无论更新操作是在哪一个副本执行，之后所有的读操作都要能获得最新的数据。,弱一致性：用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。,最终一致性：是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新。,5,2.3 ACID,与,BASE,BASE,方法通过牺牲一致性和孤立性来提高可用性和系统性能，其中,BASE,分别代表：,基本可用（,Basically Available),：系统能够基本运行、一直提供服务。,软状态（,Soft-state),：系统不要求一直保持强一致状态。,最终一致性（,Eventual consistency,）：系统需要在某一时刻后达到一致性要求。,6,事务是用户定义的一个数据库操作序列，要么全不做，要么全做，是一个不可分割的工作单位，,ACID,是事务所具有的特性。,原子性（,Atomicity,）：事务中的操作要么全做，要么不做。,一致性（,Consistency),：系统必须始终处在强一致状态下。,隔离性（,Isolation,）：一个事务的执行不能被其他事务所干扰。,持续性（,Durability,）：一个已提交的事务对数据库中数据的改变是永久性的。,保证,ACID,特性是传统关系型数据库中事务管理的重要任务，也是恢复和并发控制的基本单位。,7,ACID,和,BASE,的比较,ACID,BASE,强一致性,若一致性,隔离性,可用性优先,采用悲观、保守方法,采用乐观方法,难以改变,适应变化、更简单、更快,8,2.4,数据一致性实现技术,2.4.1 Quorum,系统,NRW,策略,这个协议有三个关键值,N,、,R,、,W,。,N,表示数据所具有的副本数。,R,表示完成读操作所需要读取的最小副本数，即一次读操作所需参与的最小节点数目。,W,表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。,该策略中，只需要保证,R+WN,，就可以保证强一致性。,R,和,W,的设置直接影响系统的性能、扩展性与一致性。,9,下面为不同设置的几种特殊情况。,1.,当,W=1,R=N,时，系统对写操作有较高的要求，但读操作会比较慢，若,N,个节点中有节点发生故障，那么读操作将不能完成。,2.,当,R=1,，,W=N,时，系统对读操作有较高性能、高可用，但写操作性能较低，用于需要大量读操作的系统，若,N,个节点中有节点发生故障，那么写操作将不能完成。,3.,当,R=Q,W=Q(Q=N/2+1),时，系统在读写性能之间取得平衡，兼顾了性能和可用性。,10,2.4.2,两阶段提交协议,在两阶段提交协议中，系统包含两类机器（或节点）：一类为协调者，通常一个系统中只有一个；另一类为事务参与者，一般包含多个，在数据存储系统中可以理解为数据副本的个数。,阶段,1,：请求阶段,在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意或取消。,阶段,2,：提交阶段,协调者将第一阶段投票结果进行表决，当且仅当所有的参与者同意提交，事务协调者才通知所有的参与者提交事务。参与者在接收到协调者发来的消息后将执行相应操作。,11,2.4.3,时间戳策略,时间戳策略在关系数据库中有广泛应用，该策略主要用于关系数据库日志系统中记录事务操作，以及数据恢复时的,Undo/Redo,等操作。在并行系统中，时间戳策略有更加广泛的应用。,我们用分布式系统中事件的先后关系，用 “,-,”符号来表示，例如：若事件,a,发生在事件,b,之前，那么,a-b,。,该关系需要满足下列三个条件：,如果,a,和,b,是同一进程中的事件，,a,在,b,之前发生，则,a-b,。,如果事件,a,是消息发送方，,b,是接受方，则,a-b,。,对于事件,a,、,b,、,c,，如果有,a-b,，,b-c,，则有,a-c,。,12,逻辑时钟,这里为每一进程,Pi,定义一个时钟,Ci,该时钟能够为任意一个事件,a,分配一个时钟：,Ci(a),。在全局上，同样存在一个时钟,C,，对于事件,b,，该时钟能够分配一个时钟值,C,（,b,）,并且如果事件,b,发生在进程,Pi,上，那么,C,（,b)=Ci(b),。,时钟条件：如果对于事件,a,和事件,b,a-b,那么,C(a)C(b),。,以下两个限制条件满足实际情况。,C1,：如果事件,a,和事件,b,是同一个进程,Pi,中的事件，并且,a,在,b,之前发生，那么：,Ci(a)Ci(b),C2:,如果,a,为进程,Pi,上某消息发送事件，,b,为进程,Pj,上消息接收事件，那么：,Ci(a)Ci(b),13,下面我们来说明该系统是如何满足,C1,和,C2,条件的。,对于,C1,条件来说，系统需要满足下面的实现规则。,IR1,：对于同一节点上任意的连续事件来说，该节点上的时钟只需要保证较晚发生事件的时钟值大于较早发生事件的时钟值即可。,对于,C2,条件来说，系统需要满足下面的实现规则。,IR2,：（,a,）如果事件,a,代表节点,Ni,发送消息,m,，那么消息,m,将携带时间戳,Tm,且,Tm=Ci(a);(b),当节点,Nj,接收消息,m,后，节点将设置该事件的时钟,Cj,大于或等于该节点上一事件的时钟并且大于或等于,Tm,。,14,