数据一致性理论

数据一致性理论第1页，共14页，2023年，2月20日，星期六2.1CAP理论CAP理论由EricBrewer在ACMPODC会议上的主题报告中提出，这个理论是NoSQL数据库管理系统构建的基础，如下图所示：第2页，共14页，2023年，2月20日，星期六其中字母“C”,”A”,”P”分别代表以下三个特征：强一致性（Consistency）。系统在执行过某项操作后仍然处于一致的状态。在分布式系统中，更新操作执行成功后所有的用户都应该读取到最新值。可用性（Availability）。每一个操作总是能够在一定时间内返回结果。需要注意“一定时间”和“返回结果”。“一定时间”是指，系统结果必须在给定时间内返回。“返回结果”是指系统返回操作成功或失败的结果。分区容错性（PartitionTolerance）。分区容错性可以理解为系统在存在网络分区的情况下仍然可以接受请求（满足一致性和可用性）。第3页，共14页，2023年，2月20日，星期六CAP是在分布式环境中设计和部署系统时所要考虑的三个重要的系统需求。根据CAP理论，数据共享系统只能满足这三个特性中两个，而不能同时满足三个条件。因此系统设计者必须在这三个特征之间做出权衡。根据CAP理论，系统满足三个条件中不同的两个条件会具有不同的特点。如下表所示：序号选择特点例子1C、A两阶段提交、缓存验证协议传统数据库、集群数据库2C、P悲观加锁分布式数据库、分布式加锁3A、P冲突处理、乐观DNS、Coda第4页，共14页，2023年，2月20日，星期六2.1数据一致性模型

一些分布式系统通过复制数据来提高系统的可靠性和容错性，并且将数据的不同的副本存放在不同的机器，由于维护数据副本的一致性代价高，因此许多系统采用若一致性来提高性能，一些不同的一致性模型也相继被提出。

强一致性：要求无论更新操作是在哪一个副本执行，之后所有的读操作都要能获得最新的数据。

弱一致性：用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。

最终一致性：是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新。第5页，共14页，2023年，2月20日，星期六2.3ACID与BASEBASE方法通过牺牲一致性和孤立性来提高可用性和系统性能，其中BASE分别代表：基本可用（BasicallyAvailable)：系统能够基本运行、一直提供服务。软状态（Soft-state)：系统不要求一直保持强一致状态。最终一致性（Eventualconsistency）：系统需要在某一时刻后达到一致性要求。第6页，共14页，2023年，2月20日，星期六事务是用户定义的一个数据库操作序列，要么全不做，要么全做，是一个不可分割的工作单位，ACID是事务所具有的特性。

原子性（Atomicity）：事务中的操作要么全做，要么不做。一致性（Consistency)：系统必须始终处在强一致状态下。

隔离性（Isolation）：一个事务的执行不能被其他事务所干扰。

持续性（Durability）：一个已提交的事务对数据库中数据的改变是永久性的。保证ACID特性是传统关系型数据库中事务管理的重要任务，也是恢复和并发控制的基本单位。第7页，共14页，2023年，2月20日，星期六

ACID和BASE的比较ACIDBASE强一致性若一致性隔离性可用性优先采用悲观、保守方法采用乐观方法难以改变适应变化、更简单、更快第8页，共14页，2023年，2月20日，星期六2.4数据一致性实现技术2.4.1Quorum系统NRW策略这个协议有三个关键值N、R、W。N表示数据所具有的副本数。R表示完成读操作所需要读取的最小副本数，即一次读操作所需参与的最小节点数目。W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。该策略中，只需要保证R+W>N，就可以保证强一致性。R和W的设置直接影响系统的性能、扩展性与一致性。第9页，共14页，2023年，2月20日，星期六下面为不同设置的几种特殊情况。1.当W=1,R=N时，系统对写操作有较高的要求，但读操作会比较慢，若N个节点中有节点发生故障，那么读操作将不能完成。2.当R=1，W=N时，系统对读操作有较高性能、高可用，但写操作性能较低，用于需要大量读操作的系统，若N个节点中有节点发生故障，那么写操作将不能完成。3.当R=Q,W=Q(Q=N/2+1)时，系统在读写性能之间取得平衡，兼顾了性能和可用性。第10页，共14页，2023年，2月20日，星期六2.4.2两阶段提交协议在两阶段提交协议中，系统包含两类机器（或节点）：一类为协调者，通常一个系统中只有一个；另一类为事务参与者，一般包含多个，在数据存储系统中可以理解为数据副本的个数。阶段1：请求阶段在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意或取消。阶段2：提交阶段协调者将第一阶段投票结果进行表决，当且仅当所有的参与者同意提交，事务协调者才通知所有的参与者提交事务。参与者在接收到协调者发来的消息后将执行相应操作。第11页，共14页，2023年，2月20日，星期六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页，共14页，2023年，2月20日，星期六逻辑时钟这里为每一进程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页，共14页，2023年，2月20日，星期六下面我们来说明该系统是如何满足C1和C2条件的。对于C1条件来说，系统需要满足下面的实现规则。IR1：对于同一节点上任意的连续事件来说，该节点上的时钟只需要保证较晚发生事件的时钟值大于较早发生事件的时钟值即可。对于C2条件来说