关于分布式系统的思考（二）

摘要：收到所有参与者回应后，完成事务。不管是还是，都是通过节点间的交换消息去达到一致的状态，这也是分布式系统的常用做法。从业期间，负责过订阅系统制作云服务开源平台分布式任务调度系统等产品的设计研发工作。

接着上一篇的内容，详细介绍一些主流数据库在分布式场景下用到的算法和思想，主要提及数据一致性相关的一些策略，并分析其利弊和典型应用场景。

对于数据库来说，可能关心的最多的就是数据的一致性了，由此衍生出了不同场景下的算法和策略。
在上一篇末尾提及了两种集群结构：中心化和去中心化。

一种是中心化的，由中心节点去存储集群信息并管理集群状态，其它节点只需响应数据请求，而无需知道集群中其它节点的情况。
这种模式的核心便是选举或者指定一个节点作为集群的管理者，由管理者去协调跨节点的操作、备份数据和处理故障等。

一般的，对于跨节点的操作，为了保证事务的原子性，提出了两步提交协议或三步提交协议，下面分别介绍。

两步提交协议，顾名思义，就是将数据的提交分为两步：投票和决策。

首先，在第一阶段，

中心节点（在这里我们称之为协调者）发起事务操作请求，包含事务内容，询问是否可以执行提交操作并等待响应；

其它节点（在这里称之为参与者）执行事务操作并记录undo/redo log，最后返回是否同意提交。

然后，在第二阶段，协调者根据所有参与者的投票结果，如果是都同意则通知所有参与者提交事务，否则回滚事务。
收到所有参与者回应后，完成事务。

接着，我们考虑下两步提交过程中如果发生异常，会出现什么样的情况，会不会影响结果的一致性，并尝试解决。

在第一阶段时，有节点宕机

有参与者宕机，此时协调者接收到错误响应，可认为是失败，将中断事务。

协调者宕机，此时参与者等待协调者的操作通知，事务会阻塞直到协调者恢复。
对于此种情况，解决的办法是可以设置多个协调者，一主多从，宕机后指定一台从作为新的主。

参与者也需要记录事务的投票状态，以便新的协调者重新找回事务状态。

参与者和协调者都宕机了，如上一条，新的协调者将会获取不到参与者的事务状态（该参与者的状态只有自己和原协调者知道），会一直阻塞地等待所有参与者恢复。
其它参与者也会处于两阶段之间，直到宕机的参与者恢复。

在第二阶段，有节点宕机

有参与者宕机，此时未宕机的参与者会正常地提交／回滚事务，而由于并不知道宕机的时机，所以可能会导致数据的不一致。

协调者宕机，若是在发送通知前，那么参与者将阻塞地等待协调者恢复。可通过设置协调者的备份来解决，要求参与者记录事务状态。若是在发送通知后，不影响可忽略。

参与者与协调者都宕机了，如上两条，可能会导致数据的不一致或阻塞。

注意，以上的宕机如果替换为网络分区，也会是同样的情况。

可以看出，2pc的优点是简单直接，缺点是：

当有故障发生会阻塞事务的执行，进而影响到相关资源的释放；

协调者的单点问题；

当二阶段有参与者宕机或者网络分区时，可能会导致数据不一致。

针对这些缺陷，出现了3pc。

三步提交协议，改进了2pc的一些缺陷，它增加了一个询问是否可提交阶段。如图所示：

第一阶段时，协调者询问各参与者是否可以执行事务提交，包含事务内容，并等待参与者的响应。
参与者收到请求后，如果认为可以成功执行事务，则返回同意，否则中止事务。

第二阶段时，协调者根据第一阶段参与者的返回消息，决定是准备提交或是中止事务。如果都是同意，那么发送预提交请求。
参与者收到请求后，会执行事务操作，并记录undo/redo log, 最后返回提交／中止事务。

第三阶段时，协调者根据第二阶段的响应，决定通知参与者提交／回滚事务，收到响应后完成事务。

3pc相比于2pc的优点在于：

在协调者和参与者端都添加了超时机制，其中：参与者超时未应答均认为是失败；协调者在第二阶段超时未发送请求视为失败，而第三阶段超时未发送请求视为成功，参与者在经过了指定超时时间后提交事务。这样便具备了一定的容错性。
不仅如此，这样还可以有效减少阻塞时间。

提供了协调者的主备方案，避免了单点问题。

缺点：

第二阶段时，参与者在接收到预提交请求后发生网络分区，此参与者在超时后提交事务，而协调者在超时后认为事务失败并通知其它参与者回滚事务，最终导致数据不一致。若发生此情况，只能通过上层去协调解决这个问题，如上一篇提到的两种解决方案。（2pc也有类似缺陷）

比2pc多了一个阶段，意味着同等情况下，耗时要多一点。

另一种则是去中心化的，由节点之间互相通信去协商一致。比较有名的算法如Paxos。

Paxos算法在分布式领域具有非常重要的地位，Google Chubby的作者Mike Burrows曾经说过，这个世界上只有一种一致性算法，那就是Paxos，其它的都是残次品。

不过这个算法实在是难理解，难实现；以后有机会我会专门总结一篇文章分享下，有兴趣的道友可以先去看看《Paxos Made Simple》，写得很不错。

此外，考虑到集群中的节点数量并不是一成不变的，所以如果使用的是一般的Hash算法，那么在集群新增节点或删除节点时，会导致节点间大量数据的迁移，进而影响可用性，故而提出了一致性Hash算法以减少数据的迁移量。

一般的Hash算法，如对key取模然后分散到不同的节点中：假设有3个节点，共有key分别为1～7的数据，分配结果如下图

现在，如果新增一个节点，那么分配结果变为：

可以发现大部分的节点都被重新分配到了不同的节点上，即迁移数据是O(n)复杂度（n为数据总量），无法平滑地扩缩容。
接下来再来看下一致性Hash，它的分配方式是对key和节点做相同的Hash运算，然后将key分配到刚好大于或等于它Hash值的节点上（若节点都比它Hash值小，则分配到最小的节点上，即形成一个“环”）；

还是上面的那个例子，对key和节点都做对7取模的Hash计算，然后分配。先是有三个节点：

新增一个节点：

可以看出，增加一个节点后只有少量数据从5节点移动到4节点，极大的减少了数据迁移量。
但是，一致性Hash也有缺陷：查找效率低。一般需要逐个去比较Hash值直到找到刚好大于等于的节点，故查找复杂度为O(k)（k为节点数量）。
可以通过在节点中冗余一份节点表来加快查找。

保证一致性，要么是通过共享存储，要么是通过消息协调。
数据库本身就是共享存储。
不管是2pc、3pc还是paxos，都是通过节点间的交换消息去达到一致的状态，这也是分布式系统的常用做法。
了解了这些策略的原理后，不管是用Zookeeper、RabbitMQ、Redis或其它消息组件（甚至是基于socket通信）去实现它，都是水到渠成的事情了。

超时是个好设计，因为它是不需询问便可以察觉错误的方式（毕竟没有错误就不会超时了），很多设计中都会将超时作为一种信号，并尝试容错／修复等操作。

在运行过程的一些错误并不能通过底层的策略完全规避，需要根据具体业务在上层做相应的容错措施。

冗余是个好设计，几乎在各种组件的设计都能见到，通过牺牲一点空间较大地提高检索效率。

有机会的话，之后的篇章我会收集并比较几种典型分布式组件的具体实现，对这些组件有个更加直观和深入的理解，以便充实和改进自己的知识结构并分享出来。

最后为方便查询，整理了下往期文章到github中：https://github.com/dengyuankai272/blog

作者信息
本文系力谱宿云LeapCloud旗下MaxLeap团队_基础服务组成员：吕舜 【原创】
力谱宿云LeapCloud 首发：https://blog.maxleap.cn/archi...
吕舜，主攻Java，对Python、数据分析也有关注。从业期间，负责过订阅系统、App制作云服务、开源BaaS平台、分布式任务调度系统等产品的设计研发工作。现任MaxLeap基础服务与架构成员，负责云服务系统相关的设计与开发。

相关文章
微服务实战：从架构到发布（一）
微服务实战：从架构到发布（二）
移动云平台的基础架构之旅（一）：云应用
从应用到平台 – 云服务架构的演进过程

作者往期佳作
RabbitMQ在分布式系统的应用
关于分布式系统的思考

欢迎扫以下二维码，关注我们的微信订阅号：