一致性模型

数据的一致性模型可以分成以下 3 类：

  1. 强一致性：数据更新成功后，任意时刻所有副本中的数据都是一致的，一般采用同步的方式实现。
  2. 弱一致性：数据更新成功后，系统不承诺立即可以读到最新写入的值，也不承诺具体多久之后可以读到。

  3. 最终一致性：弱一致性的一种形式，数据更新成功后，系统不承诺立即可以返回最新写入的值，但是保证最终会返回上一次更新操作的值。

    一致性算法Quorum NRW

    Quo­rum，原指为了处理事务、拥有做出决定的权力而必须出席的众议员或参议员的数量（一般指半数以上）。
    NRW 算法是基于 Quo­rum 机制的是一种 CP(Con­sis­tency&Par­tion tol­er­ance) 算法。用于在数据一致性和可靠性之间达到一种平衡。为了保证系统的正常运行，能够提供可靠的服务，分布式系统中对于数据的存储采用多份数据副本，但是这种解决方案在数据读写的过程中会造成数据的不一致性。
    我们知道要解决数据一致性问题，就是数据的处理方式采用 Read Only Write All 原则，即在分布式环境中，所有节点更新完毕后，读操作才能进行，保证数据的强一致性。这种虽然保证了数据的在某一刻的强一致性，但是极其影响系统的性能。在一个读操作非常频繁的分布式环境中，写操作的耗时，直接阻塞了读的操作。导致读和写的负载不均衡。
    基于 Quo­rum 机制的 NRW 算法就是在读和写的负载上达到一定平衡的同时，保证数据的强一致性。机制的主要思想来源于鸽巢原理。即当数据备份存在 N 份时，k 份数据已经更新，那么只要获取 N−K+1 个数据副本，至少有一个数据是更新了的。获取其中版本最高的那份数据，即最新的。这样，我们就不必等待所有数据副本全部更新后才去读取数据，使得读写能够在一定程度上达到负载均衡。
    算法规则:
    假设需要备份 N 个数据副本，读操作用 R，写操作用 W，操作副本用 V 表示。根据鸽巢原理，要保证操作能获得最新数据。则有以下制约条件。

  4. Vr+Vw>N即读操作副本量+写操作副本量必须大于数据副本量。这就即保证必定有一个副本是操作之后的值，同时保证了数据副本要么处于W写操作中，要么处于R读操作中。这里的读写状态是针对外部来讲的，分布式环境对外部来说，同一时刻只存在一种操作（容斥定理），相当于读写锁，但比加锁(一种悲观的策略)的方式更加高效。对于分布式环境内部，读和写操作只是部分节点的操作。同时限定了最小读副本数量和最小写副本数量。该策略中，只需要保证R+W>N，就可以保证强一致性。 如果R+W≤N，这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

  5. Vw>N/2 保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。如Vw<N/2的时候，就可能存在一部分数据被一个写操作修改，另一部分数据被另一个写操作修改。

一般来讲，W=N/2+1， R=N/2。

理论

CAP理论

在分布式系统中，一致性（Con­sis­tency）、可用性（Avail­abil­ity）和分区容忍性（Par­ti­tion Tol­er­ance）3 个要素最多只能同时满足两个，不可兼得。其中，分区容忍性又是不可或缺的。

  • 分区容错性：指的分布式系统中的某个节点或者网络分区出现了故障的时候，整个系统仍然能对外提供满足一致性和可用性的服务。也就是说部分故障不影响整体使用。
  • 可用性： 一直可以正常的做读写操作。简单而言就是客户端一直可以正常访问并得到系统的正常响应。用户角度来看就是不会出现系统操作失败或者访问超时等问题。

  • 一致性：在分布式系统完成某写操作后任何读操作，都应该获取到该写操作写入的那个最新的值。相当于要求分布式系统中的各节点时时刻刻保持数据的一致性。

    BASE理论

    核心思想：

  • 基本可用（Basically Available）：指分布式系统在出现故障时，允许损失部分的可用性来保证核心可用。

  • 软状态（Soft State）：指允许分布式系统存在中间状态，该中间状态不会影响到系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
  • 最终一致性（Eventual Consistency）：指分布式系统中的所有副本数据经过一定时间后，最终能够达到一致的状态。

BASE 是对 CAP 中一致性和可用性权衡的结果，其来源于对大规模互联网系统分布式实践的结论，是基于 CAP 定理逐步演化而来的，其核心思想是即使无法做到强一致性（Strong con­sis­tency），但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性（Even­tual con­sis­tency）。

分布式事务

2PC

中文叫两阶段提交。在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的 ACID 特性，需要引入一个作为协调者的组件来统一掌控所有节点（称作参与者）的操作结果并最终指示这些节点是否要把操作结果进行真正的提交。两阶段提交的算法如下：
第一阶段：

  • 协调者会问所有的参与者结点，是否可以执行提交操作。
  • 各个参与者开始事务执行的准备工作：如：为资源上锁，预留资源。
  • 参与者响应协调者，如果事务的准备工作成功，则回应“可以提交”，否则回应“拒绝提交”。

第二阶段：

  • 如果所有的参与者都回应“可以提交”，那么，协调者向所有的参与者发送“正式提交”的命令。参与者完成正式提交，并释放所有资源，然后回应“完成”，协调者收集各结点的“完成”回应后结束这个Global Transaction。
  • 如果有一个参与者回应“拒绝提交”，那么，协调者向所有的参与者发送“回滚操作”，并释放所有资源，然后回应“回滚完成”，协调者收集各结点的“回滚”回应后，取消这个Global Transaction。

优点：实现简单， 方便。
缺点：同步阻塞，单点问题。

3PC

CanCommit

  • 事务询问：协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后等待参与者的响应。
  • 响应反馈：参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No

PreCommit
协调者根据参与者的反应情况来决定是否可以进行事务的 Pre­Com­mit 操作。如果都收到了 YES，则进行：

  • 发送预提交请求：协调者向参与者发送PreCommit请求，并进入Prepared阶段。
  • 事务预提交：参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
  • 响应反馈：如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

如果有任一参与者向协调者发送了 NO，则执行事务中断：

  • 发送中断请求：协调者向所有参与者发送abort请求。
  • 中断事务：参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

DoCommit
该阶段进行真正的事务提交，也可以分为以下两种情况：
执行提交：

  • 发送提交请求：协调接收到参与者发送的ack响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
  • 事务提交：参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
  • 响应反馈：事务提交完之后，向协调者发送ack响应。
  • 完成事务：协调者接收到所有参与者的ack响应之后，完成事务。

中断事务：
协调者没有接收到参与者发送的 ack 响应，就会执行中断事务。

  • 发送中断请求：协调者向所有参与者发送abort请求。
  • 事务回滚：参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
  • 反馈结果：参与者完成事务回滚之后，向协调者发送ack消息。
  • 中断事务：协调者接收到参与者反馈的ack消息之后，执行事务的中断。

相对于 2PC，3PC 主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行 com­mit，而不会一直持有事务资源并处于阻塞状态。
但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的 abort 响应没有及时被参与者接收到，那么参与者在等待超时之后执行了 com­mit 操作。这样就和其他接到 abort 命令并执行回滚的参与者之间存在数据不一致的情况。要彻底从协议层面避免数据不一致，可以采用 Paxos 或者 Raft 算法。
目前两阶段提交、三阶段提交存在如下的局限性，并不适合在微服务架构体系下使用：

  • 所有的操作必须是事务性资源（比如数据库、消息队列、EJB组件等），存在使用局限性（微服务架构下多数使用HTTP协议），比较适合传统的单体应用；
  • 由于是强一致性，资源需要在事务内部等待，性能影响较大，吞吐率不高，不适合高并发与高性能的业务场景。

    TCC

    一个完整的 TCC 业务由一个主业务服务和若干个从业务服务组成，主业务服务发起并完成整个业务活动，TCC 模式要求从服务提供三个接口：Try、Con­firm、Can­cel。
  1. Try：完成所有业务检查，预留必须业务资源。
  2. Confirm：真正执行业务，不作任何业务检查；只使用Try阶段预留的业务资源；Confirm操作满足幂等性。
  3. Cancel：释放Try阶段预留的业务资源；Cancel操作满足幂等性。

整个 TCC 业务分成两个阶段完成：
第一阶段：主业务服务分别调用所有从业务的 try 操作，并在活动管理器中登记所有从业务服务。当所有从业务服务的 try 操作都调用成功或者某个从业务服务的 try 操作失败，进入第二阶段。
第二阶段：活动管理器根据第一阶段的执行结果来执行 con­firm 或 can­cel 操作。如果第一阶段所有 try 操作都成功，则活动管理器调用所有从业务活动的 con­firm 操作。否则调用所有从业务服务的 can­cel 操作。
与 2PC 比较：

  • 位于业务服务层而非资源层。
  • 没有单独的准备（prepare）阶段，Try操作兼备资源操作与准备能力。
  • Try操作可以灵活选择业务资源的锁定粒度。
  • 开发成本较高。

缺点：

  • Canfirm和Cancel的幂等性很难保证。
  • 这种方式缺点比较多，通常在复杂场景下是不推荐使用的，除非是非常简单的场景，非常容易提供回滚Cancel，而且依赖的服务也非常少的情况。

  • 这种实现方式会造成代码量庞大，耦合性高。而且非常有局限性，因为有很多的业务是无法很简单的实现回滚的，如果串行的服务很多，回滚的成本实在太高。

    基于消息的分布式事务

    它的核心思想是将需要分布式处理的任务通过消息或者日志的方式来异步执行，消息或日志可以存到本地文件、数据库或消息队列，再通过业务规则进行失败重试，它要求各服务的接口是幂等的。
    该种模式的难点在于解决本地事务执行和消息发送的一致性：两者要同时执行成功或者同时取消执行。
    实现上主要有两种方式：

  • 基于事务消息的方案

  • 基于本地消息的方案

    基于事务消息的分布式事务

    普通消息是无法解决本地事务执行和消息发送的一致性问题的。因为消息发送是一个网络通信的过程，发送消息的过程就有可能出现发送失败、或者超时的情况。超时有可能发送成功了，有可能发送失败了，消息的发送方是无法确定的，所以此时消息发送方无论是提交事务还是回滚事务，都有可能不一致性出现。
    解决这个问题，需要引入事务消息，事务消息和普通消息的区别在于事务消息发送成功后，处于 pre­pared 状态，不能被订阅者消费，等到事务消息的状态更改为可消费状态后，下游订阅者才可以监听到次消息。
    本地事务和事务消息的发送的处理流程如下：

  • 事务发起者预先发送一个事务消息。

  • MQ 系统收到事务消息后，将消息持久化，消息的状态是“待发送”，并给发送者一个 ACK 消息。
  • 事务发起者如果没有收到 ACK 消息，则取消本地事务的执行；如果收到了 ACK 消息，则执行本地事务，并给 MQ 系统再发送一个消息，通知本地事务的执行情况。
  • MQ 系统收到消息通知后，根据本地事务的执行情况更改事务消息的状态，如果成功执行，则将消息更改为“可消费”并择机下发给订阅者；如果事务执行失败，则删除该事务消息。
  • 本地事务执行完毕后，发给 MQ 的通知消息有可能丢失了。所以支持事务消息的 MQ 系统有一个定时扫描逻辑，扫描出状态仍然是“待发送”状态的消息，并向消息的发送方发起询问，询问这条事务消息的最终状态如何并根据结果更新事务消息的状态。因此事务的发起方需要给 MQ 系统提供一个事务消息状态查询接口。
  • 如果事务消息的状态是“可发送”，则 MQ 系统向下游参与者推送消息，推送失败会不停重试。

  • 下游参与者收到消息后，执行本地事务，本地事务如果执行成功，则给 MQ 系统发送 ACK 消息；如果执行失败，则不发送 ACK 消息，MQ 系统会持续推送给消息。

    基于本地消息的分布式事务

    基于事务消息的模式对 MQ 系统要求较高，并不是所有 MQ 系统都支持事务消息的，Rock­etMQ 是目前为数不多的支持事务消息的 MQ 系统。如果所依赖的 MQ 系统不支持事务消息，那么可以采用本地消息的分布式模式。
    该种模式的核心思想是：
    上游服务：

  • 事务的发起方维护一个本地消息表，业务执行和本地消息表的执行处在同一个本地事务中。业务执行成功，则同时记录一条“待发送”状态的消息到本地消息表中。

  • 系统中启动一个定时任务定时扫描本地消息表中状态为“待发送”的记录，并将其发送到 MQ 系统中，如果发送失败或者超时，则一直发送，直到发送成功后，从本地消息表中删除该记录（或修改状态为“已发送”）。
  • 消息会重试发送，可能会重复，所以每条消息需要一个唯一ID。

下游服务：

  • 后续的消息订阅者从MQ消费消息，进行下游的本地事务操作。
  • 为了避免消息重复消费，下游服务可以维护一个本地的“消息记录表”记录已经处理消费过的消息，每次处理消息前通过该表检查消息是否消费过。

基于消息的分布式事务可以将分布式系统之间更有效的解耦，各个事务参与方之间的调用不再是同步调用。
对 MQ 系统的要求较高，对业务实现也有一定的侵入性，要么提供事务消息状态查询接口，要么需要维护本地消息表。并且原则上只接受下游分支事务的成功，不接受事务的回滚，如果失败就要一直重试，适用于对最终一致性敏感度较低的业务场景，例如跨企业的系统间的调用，适用的场景有限。

分布式算法

Paxos

Paxos 算法解决的是一个分布式系统如何就某个值（决议）达成一致。
一个典型的场景是，在一个分布式数据库系统中，如果各个节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能够得到一个一致的状态。为了保证每个节点执行相同的命令序列，需要在每一条指令上执行一个 “一致性算法” 以保证每个节点看到的指令一致。zookeeper 使用的 zab 算法是该算法的一个实现。在 Paxos 算法中，有三种角色：Pro­poser (提议者),Ac­cep­tor（接受者），Learn­ers（记录员）

  • Proposer提议者：只要Proposer发的提案Propose被半数以上的Acceptor接受，Proposer就认为该提案例的value被选定了。
  • Acceptor接受者：只要Acceptor接受了某个提案，Acceptor就认为该提案例的value被选定了
  • Learner记录员：Acceptor告诉Learner哪个value就是提议者的提案被选定，Learner就认为哪个value被选定。

Paxos 算法分为两个阶段，具体如下：
阶段一 （准 leader 确定 ）：
(a) Pro­poser 选择一个提案编号 N，然后向半数以上的 Ac­cep­tor 发送编号为 N 的 Pre­pare 请求。
(b) 如果一个 Ac­cep­tor 收到一个编号为 N 的 Pre­pare 请求，且 N 大于该 Ac­cep­tor 已经响应过的所有 Pre­pare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Pro­poser，同时该 Ac­cep­tor 承诺不再接受任何编号小于 N 的提案。
阶段二 （leader 确认）：
(a) 如果 Pro­poser 收到半数以上 Ac­cep­tor 对其发出的编号为 N 的 Pre­pare 请求的响应，那么它就会发送一个针对 [N,V] 提案的 Ac­cept 请求给半数以上的 Ac­cep­tor。注意：V 就是收到的响应中编号最大的提案的 value ，如果响应中不包含任何提案，那么 V 就由 Pro­poser 自己决定。
(b) 如果 Ac­cep­tor 收到一个针对编号为 N 的提案的 Ac­cept 请求，只要该 Ac­cep­tor 没有对编号大于 N 的 Pre­pare 请求做出过响应，它就接受该提案。

Raft算法

与 Paxos 不同 Raft 强调的是易懂（Un­der­stand­abil­ity），Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务；众所周知但问题较为复杂时可以把问题分解为几个小问题来处理，Raft 也使用了分而治之的思想。
Raft 算法由 leader 节点来处理一致性问题。leader 节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，leader 节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到 raft 状态机中执行。通过以上方式，Raft 算法将要解决的一致性问题分为了以下几个子问题：

  • leader选举：集群中必须存在一个leader节点。
  • 日志复制：leader节点接收来自客户端的请求然后将这些请求序列化成日志数据再同步到集群中其它节点。
  • 安全性：如果某个节点已经将一条提交过的数据输入raft状态机执行了，那么其它节点不可能再将相同索引的另一条日志数据输入到raft状态机中执行。

基本概念：
在 Raft 算法中，一个集群里面的所有节点有以下三种状态：

  • Leader：领导者，一个集群里只能存在一个Leader。
  • Follower：跟随者，follower是被动的，一个客户端的修改数据请求如果发送到Follower上面时，会首先由Follower重定向到Leader上。
  • Candidate：参与者，一个节点切换到这个状态时，将开始进行一次新的选举。

每一次开始一次新的选举时，称为一个 “任期”。每个任期都有一个对应的整数与之关联，称为 “任期号”，任期号用单词 “Term” 表示，这个值是一个严格递增的整数值，节点的状态切换状态机如下图所示：
image.png

  • start up：起始状态，节点刚启动的时候自动进入的是follower状态。
  • times out, starts election：follower在启动之后，将开启一个选举超时的定时器，当这个定时器到期时，将切换到candidate状态发起选举。
  • times out, new election：进入candidate 状态之后就开始进行选举，但是如果在下一次选举超时到来之前，都还没有选出一个新的leader，那么还会保持在candidate状态重新开始一次新的选举。
  • receives votes from majority of servers：当candidate状态的节点，收到了超过半数的节点选票，那么将切换状态成为新的leader。
  • discovers current leader or new term：candidate状态的节点，如果收到了来自leader的消息，或者更高任期号的消息，都表示已经有leader了，将切换回到follower状态。

  • discovers server with higher term：leader状态下如果收到来自更高任期号的消息，将切换到follower状态。这种情况大多数发生在有网络分区的状态下。

    leader选举

    raft 算法是使用心跳机制来触发 leader 选举的。
    在节点刚开始启动时，初始状态是 fol­lower 状态。一个 fol­lower 状态的节点，只要一直收到来自 leader 或者 can­di­date 的正确 RPC 消息的话，将一直保持在 fol­lower 状态。leader 节点通过周期性的发送心跳请求（一般使用带有空数据的 Ap­pen­dEn­tries RPC 来进行心跳）来维持着 leader 节点状态。每个 fol­lower 同时还有一个选举超时（elec­tion time­out）定时器，如果在这个定时器超时之前都没有收到来自 leader 的心跳请求，那么 fol­lower 将认为当前集群中没有 leader 了，将发起一次新的选举。
    发起选举时，fol­lower 将递增它的任期号然后切换到 can­di­date 状态。然后通过向集群中其它节点发送 Re­questVote RPC 请求来发起一次新的选举。一个节点将保持在该任期内的 can­di­date 状态下，直到以下情况之一发生。

  • 该candidate节点赢得选举，即收到超过半数以上集群中其它节点的投票。

  • 另一个节点成为了leader。

  • 选举超时到来时没有任何一个节点成为leader。（两个节点投票数相同）

    日志复制

    日志复制的流程大体如下：

  • 每个客户端的请求都会被重定向发送给leader，这些请求最后都会被输入到raft算法状态机中去执行。

  • leader在收到这些请求之后，会首先在自己的日志中添加一条新的日志条目。
  • 在本地添加完日志之后，leader将向集群中其他节点发送AppendEntries RPC请求同步这个日志条目，当这个日志条目被成功复制之后，leader节点将会将这条日志输入到raft状态机中，然后应答客户端。

一条日志如果被 leader 同步到集群中超过半数的节点，那么被称为 “成功复制”，这个日志条目就是 “已被提交（com­mit­ted）”。如果一条日志已被提交，那么在这条日志之前的所有日志条目也是被提交的，包括之前其他任期内的 leader 提交的日志。

安全性

Election safety
选举安全性，即任一任期内最多一个 leader 被选出。这一点非常重要，在一个复制集中任何时刻只能有一个 leader。系统中同时有多余一个 leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在 raft 中，两点保证了这个属性：

  • 一个节点某一任期内最多只能投一票；
  • 只有获得majority投票的节点才会成为leader。

因此，某一任期内一定只有一个 leader。
log matching
很有意思，log 匹配特性， 就是说如果两个节点上的某个 log en­try 的 log in­dex 相同且 term 相同，那么在该 in­dex 之前的所有 log en­try 应该都是相同的。如何做到的？依赖于以下两点

  • 如果不同日志中的两个条目具有相同的index和term，则它们存储相同的命令。
  • 如果不同日志中的两个条目具有相同的index和term，则前面所有条目中的日志都相同。