分布式理论

CAP 理论

CAP理论是一个很好的思考框架，它对分布式系统的特性做了高度抽象，比如抽象成了一致性、可用性和分区容错性，并对特性间的冲突（也就是CAP不可能三角）做了总结。

CAP理论对分布式系统的特性做了高度抽象，形成了三个指标：

  • 一致性（Consistency）
  • 可用性（Availability）
  • 分区容错性（Partition Tolerance）

一致性说的是

BASE 理论

分布式共识算法

Paxos

在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如Raft算法、ZAB协议等等。

Raft

不同于Paxos算法直接从分布式一致性问题出发推导出来，Raft算法则是从多副本状态机的角度提出，用于管理多副本状态机的日志复制。Raft实现了和Paxos相同的功能，它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Membership change）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。

如果要用一句话概括Raft算法，我觉得是这样的：从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和个节点日志的一致。

选举

Raft将系统中的角色分为领导者（Leader）、跟随者（Follower）和候选人（Candidate）

  • 跟随者：相当于普通群众，默默地接收和处理来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
  • 候选人：候选人将向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
  • 领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是3部分，处理写请求、管理日志复制和不断地发送心跳信息。通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”

  1. 首先在初始状态下，集群中所有的节点都是跟随者的状态

    Raft算法实现了随机超时时间的特性。也就是说，二秘阁节点等待领导者节点心跳信息的超时时间间隔是随机的。若集群中没有领导者，而节点A的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。

  2. 这个时候，节点A就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票RPC消息，请它们推举自己为领导者。

  3. 如果其他节点接收到候选人A的请求投票RPC消息，在编号为1的这届任期内，也还没有进行过投票，那么它将把选票投给节点A，并增加自己的任期编号。

  4. 如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。

  5. 节点A当选领导者后，它将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举。

日志

在Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和提交日志项的过程。

如何理解日志

如何复制日志

如何实现日志的一致

安全性

Raft增加了如下两条限制以保证安全性：

  • 拥有最新的已提交的log entry的Follower才有资格成为Leader。

这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。

  • Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。

之所以要这样，是因为可能会出现已提交的日志又被覆盖的情况：

成员变更

在集群中进行成员变更的最大风险是，可能会同时出现2个领导者。破坏了Raft的领导者的唯一性原则，影响了集群的稳定运行。

在这里，最常用的方法就是单节点变更。

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，安妮需要执行多次单节点变更。比如将3节点集群扩容为5节点集群，这时你需要执行2次单节点变更，先将3节点集群变更为4节点集群，然后再将4节点集群变更为5节点集群。

问题

节点间如何通讯

在Raft算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的RPC：

  1. 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
  2. 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

这里，我想强调的是，日志复制RPC只能由领导者发起，这时实现强领导者模型的关键之一。

分布式事务

DTM 官方文档

分布式事务涉及多个节点，是一个典型的分布式系统，与单机系统有非常大的差别。一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项，这被称为[CAP 理论](#CAP 理论)。

对于多数大型互联网应用的场景，主机众多、部署分散，而且现在的集群规模越来越大，所以节点故障、网络故障是常态，而且要保证服务可用性达到N个9，即保证P和A，舍弃C。

[BASE 理论](#BASE 理论)是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的简写，BASE是对CAP中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于CAP定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong consistency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性。

总的来说，BASE理论面向的是大型高可用可扩展的分布式系统，提出通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。

银行跨行转账业务是一个典型分布式事务场景，假设A需要跨行转账给B，那么就涉及两个银行的数据，无法通过一个数据库的本地事务保证转账的ACID，只能够通过分布式事务来解决。

分布式事务就是指事务的发起者、资源及资源管理器和事务协调者分别位于分布式系统的不同节点之上。在上述转账的业务中，用户A-100操作和用户B+100操作不是位于同一个节点上。本质上来说，分布式事务就是为了保证在分布式场景下，数据操作的正确执行。

分布式事务可以分为两类：

  • 第一类为：NewSQL的内部分布式事务，这类事务不是我们今天讨论的重点，仅做简单叙述
  • 第二类为：跨数据库、跨服务的分布式事务，这类事务是DTM主要研究的对象，后面会详细讲解

NewSQL的分布式事务

以Spanner、TiDB为代表的NewSQL，在内部集群多节点间，实现了ACID的事务，即提供给用户的事务接口与普通本地事务无差别，但是在内部，一个事务是支持多个节点多条数据的写入，此时无法采用本地ACID的MVCC技术，而是会采用一套复杂的分布式MVCC来做到ACID。大多数的NewSQL分布式事务技术都采用这篇论文Percolator介绍的核心技术。

那么从CAP的角度看，三者不能同时兼备，那么NewSQL选择了什么，牺牲了什么呢？

首先我们看C（一致性），这是数据库类的应用必须具备的。只要数据写入了，后续的读，一定能获取到最新写入的结果。你可以想象如果不是这样，那么你的应用处理关键事务如订单时，如果读到的结果不是最新的，那么你就无法确定订单的当前准确状态，就无法进行正确处理，更无从谈起ACID特性。

然后我们看P（分区），只要是分布式系统，那么P就是必然有概率发生的，因此P是分布式系统必须处理，必须具备的特性。

那么我们再看A（可用性），由于架构的发展，系统出现网络分区的频率可以大幅降低。另外分布式共识算法的发展，可以在较短的时间，正确的达成共识，从而从分区故障中恢复。谷歌分布式锁Chubby的公开数据显示，集群能提供99.99958％的平均可用性，一年也就130s的运行中断。这样的可用性相当高，对实际应用的影响微乎其微。

也就是说随着现代工程和共识算法的发展，可以构造出满足CP的系统，同时接近于满足A，可以称之为CP+HA，这里HA代表的是非100%的A，而是很高的可用性。

公开的数据显示，谷歌的Spanner支持ACID的事务特性，同时提供了高达的5个9的可用性，因此这是一个CP+HA。

既然NewSQL已经达到了CP+HA，那么从CAP的角度看，前面介绍BASE中的典型DynamoDB系统等，只达到了AP，他们是否就可以退出历史舞台了呢？不会！NewSQL和BASE的系统之间，性能上差异可能是巨大的，因此在实际高性能高并发应用上，BASE也是有不少的应用场景的。

跨服务跨库的分布式事务

分布式事务

虽然分布式事务分为两类，一类是前面介绍的NewSQL的分布式事务，不是DTM研究的重点，另一类是DTM重点研究的跨服务跨库分布式事务，为了简化描述，本教程如果无特殊说明，关键词：分布式事务指的是跨库跨服务更新数据的分布式事务

DTM主要研究跨服务，跨数据库的分布式事务，这类分布式事务只是部分遵循 ACID 规范的：

  • 原子性：严格遵循
  • 一致性：事务完成后的一致性严格遵循；事务中的一致性可适当放宽
  • 隔离性：并行事务间不可影响；事务中间结果可见性允许安全放宽
  • 持久性：严格遵循

这里面一致性和隔离性都没有严格遵守，但是ACID这四个特性中，AID这三个特性其实是数据库实现的人非常关心，而对于使用数据库的人，最终的用户，最关心的则是C，即用户视角看，分布式事务的一致性是什么样的？

对于这里面的C（一致性），我们以一个非常具体的业务例子，来进行解释。假如我们正在处理一个转账业务，假设是A转给B 30元，在本地事务的支持下，我们的用户看到A+B的总金额，在整个转账前后，以及转账过程中，都是保持不变的。那么这个时候用户认为他看到的数据是一致的，符合业务约束的。

当我们业务变复杂，引入多个数据库和大量微服务时，上述本地事务的一致性，依旧是业务非常关心。假如一个业务更新操作，跨库或者跨服务时，那么此时业务关心的一致性问题，就变成了 分布式事务中的一致性问题。

在单机本地事务中，A+B的总金额在任何时刻去查（以常见的ReadCommitted或ReadRepeatable隔离级别），都是不变的，也就是业务约束一直都保持的这种一致性，我们称之为强一致性。

无法强一致

目前在跨库、跨服务的分布式实际应用中，尚未看到有强一致性的方案。

一致性级别最高的XA事务（读者如果还不了解，可以参考XA事务），是无法强一致的。

从理论上分析，由于是分布式系统，那么一定是无法保证两个commit同时结束，只要两个commit中间有时间差，那么无论如何我们都无法保证强一致性。

最终一致性

从前面的分析中可以看到，在分布式事务进行的过程中，一致性是无法得到保证的，但是分布式事务完成之后，一致性是没问题的，严格遵守的。因此我们将分布式事务方案称为最终一致性方案，这个最终一致性，与CAP中的最终一致性用了同样的词语，但他们的具体含义是不一样的，在CAP中是指读取操作最终能够读取到最后一次写入的结果，在分布式事务中是指最终事务完成后，数据严格满足业务约束。

既然现有的各种分布式事务方案都无法做到强一致，那么最终一致性之间是否有差别呢？我们进行了以下关于一致性强弱的分类：

一致性由强到弱分别是：

XA事务>TCC>二阶段消息>SAGA

他们的分类为：

c-classify

  • 不一致窗口短：XA和TCC在理想的情况下，可以做到不一致的窗口时间很短
  • 不一致窗口长：SAGA和MSG则缺少控制不一致窗口时间的方法，相对来说会更长
  • XA：XA虽然不是强一致，但是XA的一致性是多种分布式事务中，一致性最好的，因为他处于不一致的状态时间很短，只有一部分分支开始commit，但还没有全部commit的这个时间窗口，数据是不一致的。因为数据库的commit操作耗时，通常是10ms内，因此不一致的窗口期很短。
  • TCC：理论上，TCC可以用XA来实现，例如Try-Prepare，Confirm-Commit，Cancel-Rollback。但绝大多数时候，TCC会在业务层自己实现Try|Confirm|Cancel，因此Confirm操作耗时，通常高于XA中的Commit，不一致的窗口时间比XA长
  • MSG：二阶段消息型事务在第一个操作完成后，在所有操作完成之前，这个时间窗口是不一致的，持续时长一般比前两者更久。
  • SAGA：SAGA的不一致窗口时长与消息接近，但是如果发生回滚，而子事务中正向操作修改的数据又会被用户看到，这部分数据就是错误数据，容易给用户带来较差的体验，因此一致性是最差的。

我们这里的分类仅仅从我们关心的几个维度进行了归纳，适用于多数场景，但并不一定适用所有情况。