分布式系统如何保障数据一致性

一致性保证

最终一致性（eventual consistency）：如果停止更新数据，等待一段时间（时间长度未知），则最终所有读请求将返回相同的内容。

然而最终一致性是一种非常弱的一致性保证，因为无法知道何时（when）系统会收敛。而在收敛之前，读请求都可能返回任何值。

可线性化（Linearizability）

可线性化（Lineariazability），也被称为原子一致性（atomic consistency）、强一致性（strong consistency），其基本的思想是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。有了这个保证，应用程序不需要再关心系统内部有多少个副本。

在一个可线性化的系统中，一旦客户端成功提交写请求，所有客户端的读请求一定能看到刚刚写入的值。这一保证让客户端认为只有一个副本，这样任何一次读取都能读到最新的值，而不是过期的数据。

下图来解释在一个非线性化的系统中，可能出现什么问题。

上图中，alice和bob同时等待2014年世界杯决赛的结果。在宣布最终比分之后，alice看到了最终的结果，然后将此结果告诉了bob，bob马上在自己的手机上刷新想看最新的结果，但是却返回了过期的数据，显示当前比赛还在进行中。

如何实现可线性化？

前面只是简单介绍了可线性化的思想：使系统看起来只有一个数据副本。为了更好的理解可线性化，看下面的图示例子。

在上图中，分为两种操作：针对某个值进行read和write操作。

客户端A的第一次和最后一次read操作，分别返回0和1，这没有问题，因为在这两次操作中间有客户端C的write操作将数据x更新为了1。

但是，在写操作还在进行的时候，如果读操作返回的值会来回的跳变，即某次读请求返回的是旧值，而某一次又返回的是新值，这对于一个可线性化系统而言是不可接受的。

为此，需要加入一个约束条件，如下图所示：

在上图中，箭头表示时序依赖关系。即先有客户端A的第二次read(x)操作，再有客户端B的第二次read(x)操作。客户端A的第二次读请求返回了x的新值1，而客户端B在这次读请求之后也去读x的值，此时应该返回的也是新值1。

即：在一个可线性化的系统中，有一个很重要的约束条件，在写操作开始和结束之间必然存在一个时间段，此时读到x的值会在旧值与新值之间跳变。但是，如果某个客户端的读请求返回了新值，那么即使这时写操作还未真正完成，后续的所有读请求也应该返回新值。

以下的例子进一步解释可线性化的操作，除了读写之外又引入另一种操作：

cas(x, old, new)：表示一次原子的比较-设置操作（compare-and-set，简称CAS），如果此时x的值为old，则原子设置这个值为new；否则保留原有值不变，这个操作的返回值表示这次x原有的值是否为old，即设置操作是否发生。

上图中的每个操作都有一个竖线，表示可能的执行时间点。可线性化要求，连接这些标记的竖线，必须总是按时间（即从左到右）向前移动，而不能向后移动。因此，一旦新值被写入或读取，所有后续的值读到的都是新值，直到被覆盖。

在上图中，有一些细节需要注意：

注意可线性化（Lineariazability）和可串行化（Serializability）的区别：

数据库可以同时支持可串行化与可线性化，这种组合又被称为严格的可串行化或者强的单副本可串行化（strong one-copy Serializability）。

实现线性化系统

由于线性化本质上意味着“表现的好像只有一个数据副本，其上的操作都是原子操作”。最简单的方案就是只用一个数据副本，但是这样无法容错。

系统容错最常见的方法是采用复制机制，回顾一下之前的多种复制方案：

线性化与quorum

上图中，x的初始值为0，写客户端向所有三副本（n=3，w=3）写入更新x为1。而客户端A从两个节点（r=2）读数据，其中一个节点返回1，而客户端B则从两个节点都得到了0。

显然这是违反线性化要求的：客户端B在客户端A之后读取数据，但是仍然得到了旧值。

总而言之，最安全的假定是类似Dynamo风格的无主复制系统无法保证线性化。

线性化的代价

CAP理论

在一个数据中心内部，主要存在不可靠的网络，就可能会违背线性化的风险，需要做出权衡考虑：

因此，不要求线性化的应用更能容忍网络故障。这种思路称为“CAP定理”。

CAP定理，表示一致性、可用性、分区容错性，三者之间只能同时满足两个特性。不过，这种表示具有误导性，因为网络分区是一种故障，不管喜欢与否，都可能发生分布式系统安全，而无法选择或者逃避这个问题。

网络在发生故障以后，必须从一致性和可用性之间做出选择。因此，更准确的应该是“网络分区情况下，选择一致还是可用”。

顺序保证

因果关系对所发生的事件施加了某种顺序：发送消息先于收到消息，问题出现在答案之前等。

如果系统满足因果关系所规定的顺序，称之为“因果一致性（causally consistent）”。

因果顺序并非全序

全序关系（total order）支持任何两个元素之间进行比较，即对于任意元素，总是可以指出哪个大哪个小。

但是有些集合并不符合全序关系，例如集合{a,b}大于集合{b,c}么？因为它们都不是对方的子集，所以无法直接进行比较。这种情况称之为不可比较（incomparable），数学集合只能是偏序关系（partially ordered）。

全序和偏序的差异也体现在数据库一致性问题中：

根据上面的定义，在可线性化的系统中不存在并发操作。一定有一个时间线将所有操作都全序执行，可能存在多个请求处于等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作，所以是单个时间轴、单个数据副本，没有并发。

并发意味着时间线会出现分支和合并，而不同分支上的操作无法直接比较，一定有一个时间线将所有操作都全序执行。

可线性化强于因果一致性

可线性化意味着一定满足因果关系，任何可线性化的系统一定能够正确满足因果关系。

在许多情况下，系统只要能够满足因果一致性就足够了，可线性化的代价太高。

序列号排序

可以使用序列号或时间戳来排序事件。时间戳不一定来自物理时钟，可以只是逻辑时钟。

特别地，还可以按照与因果关系一致的顺序来创建序列号：保证如果操作A发生在B之前，那么A的序列号一定比B更小。

在主从复制数据库中，复制日志中可以定义与因果关系一致的写全序关系，即由主节点为每个操作递增计数器，从而系统中的每个操作都赋值一个单调递增的序列号。

但是如果系统中不存在唯一的主节点，比如是多主或无主类型的数据库，可以采用以下的方式：

Lamport时间戳

如下图所示，每个节点都有唯一的标识符，且每个节点都有一个计数器来记录自己处理的请求总数，Lamport时间戳是一个值对：（计数器，节点ID），这样就能确保每个Lamport时间戳都是唯一的。

给定两个Lamport时间戳，可以这样来对比得到全序关系：计数器大的时间戳大，如果计数器相同，那么节点ID大的时间戳更大。

Lamport时间戳与版本向量的区别在于：版本向量用于区分两个操作是并发的还是因果依赖的，而Lamport时间戳用于确保全序关系。即使Lamport时间戳不能用于区分两个操作属于并发关系，还是因果依赖关系。

但是，即便有了全序的时间戳排序，有一些问题仍然无法解决。

比如注册一个网站时，要求用户名需要唯一，虽然两个同样名字的创建用户请求过来，可以根据全序关系来决定究竟哪个请求在先抢占了这个用户名，但是这并不够，因为这个是在请求写入之后才进行的判断，在应答写请求时无法立刻知道结果，因为还需要查询所有节点，如果有节点失败的情况下还需要等待，等等。

为了解决类似的问题，就需要引入”全序关系广播“这个概念了。

全序关系广播（Total Oder Broadcast）

全序关系广播指节点间交换消息的某种协议，要求满足以下两个基本安全属性：

即使节点或者网络发生故障，全序关系广播算法的正确实现也必须保证上述两条。在网络中断时发送失败的消息，在恢复之后要继续重试。

全序关系广播正是数据库复制所需要的：如果每条消息代表数据库写请求，并且每个副本都按照相同的顺序处理这些写请求，那么所有副本可以保持一致。该原则称为“状态机复制”，ZK和etcd这样的服务就实现了全序关系广播。

理解全序关系广播的另一种方式是将其视为日志（如复制日志），传递消息就像追加方式更新日志。由于所有节点必须以相同的顺序发送消息，因此所有节点都可以获取日志并看到相同的消息序列。

分布式事务与共识两阶段提交（two-phase commit，简称2PC）

以上是简单的2PC的操作示意图，图中引入了一个协调者（Coordinator）的角色。当应用程序开始提交事务时，协调者开始阶段1：发送一个准备请求给事务中的参与者，询问是否可以提交。协调者然后跟踪参与者的回应：

如果所有参与者都应答”是“，表示它们已经准备好提交，协调者接下来在阶段2发出提交请求，提交才开始执行。

如果任何参与者回答了”否“，则协调者在阶段2中向所有节点发送放弃请求。

如果参与者在2PC期间失败，那么协调者将中断事务提交；如果在第二阶段发送提交时失败，协调者将无限期重试。

2PC的原理

以下详细分解2PC流程：

由此可见，该协议两个关键的“不归路”：首先，当参与者投票“是”时，做了肯定提交的承诺；其次，协调者做了提交的决定之后，这个决定也是不可撤销的。

正是以上两点保证了2PC的原子性，而单节点事务提交实际上将两个事件合二为一，写入事务日志即提交。

协调者发生故障

但是，如果是协调者自身发生了故障，后面的行为无法预计，如下图所示。

2PC能够顺利完成的唯一方法是等待协调者恢复，这就是为什么协调者必须在向参与者发送提交请求之前需要先写入磁盘事务的日志：这是因为一旦协调者崩溃，恢复之后可以根据读取事务日志来确定所有未决的事务。

支持容错的共识算法

所有支持容错的共识算法都有以下的性质：

协商一致性和诚实性属性定义了共识算法的核心思想：决定一致的结果，而一旦决定就不能再变更决定。 有效性属性排除了无意义的方案。

如果不考虑容错性，以上三点很容易实现：强行指定某个节点为”独裁者“，由它做出所有的决定。但是，如果该节点失败，系统就无法再继续做出任何决定。这就是在2PC时看到的：如果协调者失败了，那些处于不确定状态的参与者无从知道应该怎么做。

可终止性引入了容错的思想。它强调一个共识算法不能原地空转，永远不做事情。即使某些节点出现了故障，其它节点也必须最终做出决定。

因此，可终止性属于一种活性属性（liveness property），而其它三个性质属于安全性方面的属性。

任何共识性算法，都需要至少大部分节点正确运行才能保证终止性，这个”大多数节点“又被称为”quorum“。

因此，可终止性的前提是，发生崩溃或者不可用的节点必须小于小半数节点。另外，共识算法也界定系统不存在拜占庭错误。

共识算法与全序广播

共识算法一般都是：决定了一系列值，然后采用全序关系广播算法传播数据。

全序广播的要点是：消息按照相同的顺序发送到所有节点，有且只有一次。

所以，全序广播算法相当于持续的多轮共识：

主从复制与共识

主从复制，也是所有写入操作由主节点负责，并以相同顺序发送到从节点来保持副本数据更新，为什么那时候没有考虑共识问题？

如果主节点由人手动选择和配置，那就是一个独裁性质的一致性算法，出现故障的时候需要人工干预。

然而，共识算法由需要首先选择出一个主节点来，否则会出现脑裂问题。如何选举主节点呢？

epoch和quorum

共识算法中，每个协议会定义一个世代编号（epoch number），这个编号是递增唯一的，对应于paxos中的ballot number、vsp中的view number、raft中的term number。

当主节点失效时，马上进行一轮新的投票来选举出新的主节点。选举会赋予一个单调递增的epoch号，如果出现不同的主节点，那么就看谁的epoch号更大的胜出。

在主节点做出任何决定之前，必须首先检查是否存在比它更高的epoch号，如何检查呢？基于前面做分布式系统的一个准则”真理由多数决定“，节点不能依靠自己掌握的信息来决策，而应该从quorum节点中收集投票。节点只有当没有发现更高epoch的主节点存在的情况下，才会对当前的提议进行投票。

因此实际上这里是两轮不同的投票：首先投票决定谁是主节点，然后是对主节点的提议进行投票。

投票过程看起来像2PC，区别在于：2PC的协调者不是依靠选举产生；另外共识算法只需要收到quorum节点的应答就可以通过决议，而2PC需要所有参与者都通过才能通过决议。

欢迎移步搜索关注公众号：互联网架构师之路(hlw_architector)，获取最新架构材料。

更多阅览

《分布式应用系统架构设计与实践》

介绍：这是一本完整的阐述分布式应用系统架构设计及实践的数据，既有基础，也有实践，主要如下：

基础层面：全书通过完整的基础技术介绍，为读者充分阅读和理解后续的架构实践提供扎实的技术基础，例如常见中间件的技术原理、高性能、高可用、可伸缩的常见实现方案等。另外还有高可用场景下的多机房多活如何实现，数据如何保持全局的一致性等问题也会有详细讨论。

架构实践层面：全书通过几个完整的案例来阐述具体在分布式架构中的实际问题以及解决方案，例如账号系统下的会话粘连保持、数据一致性、以及实现安全的数据降级；以及秒杀系统下的流量金字塔优化、热点账户的冲扣性能优化以及扣款场景下的数据一致性问题等等这些在书中都会有详细介绍以及。

================线上京东地址点击这里===============

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!