Distributed System

CAP 定理指出，分布式系统 不可能 同时提供下面三个要求：

• Consistency: 一致性，操作更新完成并返回客户端之后，所有节点数据完全一致
• Availability: 可用性，服务一直可用
• Partition tolerance: 分区容错性，分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务

BASE 理论作为 CAP 的延伸，其核心特点在于放弃强一致性，追求最终一致性

• Basically Available: 基本可用，指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用
• Soft State: 软状态，允许系统存在中间状态，而该中间状态不会影响系统整体可用性
• Eventual Consistency: 最终一致性，最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态

如果有一个分区（’P’），分布式系统可以在可用性和一致性（即 ’A’ 和 ’C’）之间进行权衡；

否则（’E’），当系统在没有分区的情况下正常运行时，系统可以在延迟（’L’）和一致性（’C’）之间进行权衡。

Paxos 算法解决的问题是分布式共识性问题，即一个分布式系统中的各个进程如何就某个值（决议）通过共识达成一致

角色划分：

• Proposer: 提出提案 Proposal，包含编号 + value
• Acceptor: 参与决策，回应 Proposers 的提案；当一个提案，被半数以上的 Acceptor 接受，则该提案被批准，每个 acceptor 只能批准一个提案
• Learner: 不参与决策，获取最新的提案 value

其工作流程：

1. 一个或多个提议进程 (Proposer) 可以发起提案 (Proposal)，
2. Paxos 算法使所有提案中的某一个提案，在所有进程中达成一致。
3. 系统中的多数派同时认可该提案，即达成了一致

共识算法的一种。

角色划分：

• Leader: 领导者，接受客户端请求，并向 Follower 同步请求，当数据同步到大多数节点上后告诉 Follower 提交日志
• Follow: 接受并持久化 Leader 同步的数据，在 Leader 告之日志可以提交之后，提交
• Candidate: Leader 选举过程中的临时角色，向其他节点拉选票，得到多数的晋升为 leader，选举完成之后不存在这个角色

工作流程：

1. leader 接受请求，并转发给 follow
2. 当大部分 follow 响应之后，leader 通知所有的 follow 提交请求、同时自己也提交请求并告诉调用方 ok

ZAB (Zookeeper Atomic Broadcast) 协议是为分布式协调服务 ZooKeeper 专门设计的一种支持崩溃恢复的一致性协议，基于该协议，ZooKeeper 实现了一种 主从模式的系统架构来保持集群中各个副本之间的数据一致性³。其核心思想是 Leader 再接受到事务请求之后，通过给 Follower，当半数以上的 Follower 返回 ACK 之后，Leader 提交提案，并向 Follower 发送 commit 信息。

角色划分：

• Leader: 负责整个 Zookeeper 集群工作机制中的核心
  • 事务请求的唯一调度和处理者，保证集群事务处理的顺序性
  • 集群内部各服务器的调度者
• Follower：Leader 的追随者
  • 处理客户端的非实物请求，转发事务请求给 Leader 服务器
  • 参与事务请求 Proposal 的投票
  • 参与 Leader 选举投票
• Observer：是 zookeeper 自 3.3.0 开始引入的一个角色，
  • 它不参与事务请求 Proposal 的投票，
  • 也不参与 Leader 选举投票
  • 只提供非事务的服务（查询），通常在不影响集群事务处理能力的前提下提升集群的非事务处理能力。

Two-Phase Commit Protocol，两阶段提交协议，主要是为了解决强一致性，中心化的强一致性协议。

角色划分：

• 协调节点 (coordinator)：中心化
• 参与者节点 (partcipant)：多个

工作流程：

1. 协调节点接收请求，然后向参与者节点提交 precommit
2. 当所有的参与者都回复 ok 之后，协调节点再给所有的参与者节点提交 commit
3. 所有的都返回 ok 之后，才表明这个数据确认提交

当第一个阶段，有一个参与者失败，则所有的参与者节点都回滚。

在两阶段的基础上进行扩展，将第一阶段划分两部，cancommit + precommit，第三阶段则为 docommit⁴ 。

1. cancommit，协调者会去询问各个参与者是否能够正常执行事务，参与者根据自身情况回复一个预估值，相对于真正的执行事务，这个过程是轻量的
2. precommit，协调者会根据第一阶段的询盘结果采取相应操作，若所有参与者都返回 ok，则协调者向参与者提交事务执行 （但不提交） 通知；否则通知参与者 abort 回滚
3. docommit，如果第二阶段事务未中断，那么本阶段协调者将会依据事务执行返回的结果来决定提交或回滚事务，若所有参与者正常执行，则提交；否则协调者 + 参与者回滚

在第三阶段如果因为协调者或网络问题，导致参与者迟迟不能收到来自协调者的 commit 或 rollback 请求，那么参与者将不会如两阶段提交中那样陷入阻塞，而是等待超时后继续 commit，相对于两阶段提交虽然降低了同步阻塞，但仍然无法完全避免数据的不一致

消息同步协议。 Gossip 协议，顾名思义，就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。Gossip 协议通过上面的特性，可以保证系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。⁵

工作流程：

1. 周期性的传播（感染）消息，通常周期时间为 1s
2. 被感染的节点，随机选择 n 个相邻节点，传播消息
3. 每次传播消息都选择还没有发送过的节点进行传播
4. 收到消息的节点，不会传播给向它发送消息的节点

用来保证数据冗余和最终一致性的投票算法，其主要数学思想来源于鸽巢原理。⁶

• N ，表示副本数，又叫做复制因子（Replication Factor）。也就是说，N 表示集群中同一份数据有多少个副本
• W ，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新写入，才会视为本次写操作成功
• R ，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本，才会视为本次读操作成功

Quorum NWR 算法要求每个数据拷贝对象 都可以投 1 票，而每一个操作的执行则需要获取最小的读票数，写票数；通常来讲写票数 W 一般需要超过 N/2，即我们通常说的得到半数以上的票才表示数据写入成功

事实上当 W=N、R=1 时，即所谓的 WARO (Write All Read One)。就是 CAP 理论中 CP 模型的场景

拜占庭算法主要针对的是分布式场景下无响应，或者响应不可信的情况下的容错问题。

工作流程：

1. 客户端向主节点发起请求，主节点接受请求之后，向其他节点广播 pre-prepare 消息
2. 节点接受 pre-prepare 消息之后，若同意请求，则向其他节点广播 prepare 消息；
3. 当一个节点接受到 2f+1 个 prepare 新消息，则进入 commit 阶段，并广播 commit 消息
4. 当收到 2f+1 个 commit 消息后（包括自己），代表大多数节点已经进入 commit 阶段，这一阶段已经达成共识，于是节点就会执行请求，写入数据

相比 Raft 算法完全不适应有人作恶的场景，PBFT 算法能容忍 (n 1)/3 个恶意节点（也可以是故障节点）。另外，相比 PoW 算法，PBFT 的优点是不消耗算力。PBFT 算法是 O(n^2) 的消息复杂度的算法，所以以及随着消息数 的增加，网络时延对系统运行的影响也会越大，这些都限制了运行 PBFT 算法的分布式系统的规模，也决定了 PBFT 算法适用于中小型分布式系统。

工作量证明 (Proof Of Work，简称 PoW)，同样应用于分布式下的一致性场景，区别于前面的 Raft, PBFT, Paxos 采用投票机制达成共识方案，PoW 采用工作量证明。客户端需要做一定难度的工作才能得出一个结果，验证方却很容易通过结果来检查出客户端是不是做了相应的工作，通过消耗一定工作量，增加消息伪造的成本。

大量应用于区块链 block chain 中。

功能一致，平常由 主 提供服务，主 宕机或进程等挂掉后，备 由待机状态快速转为服务状态。

采用冗余进行容灾，但白白浪费一半（1 主 1备）的资源。切换方式：

• 人工
• VIP + keepalive

主从一般又叫做读写分离，主提供读写能力，而从则只提供读能力。

鉴于当下的互联网应用，绝大多数都是读多写少的场景；读更容易成为性能瓶颈，所以采用读写分离，可以有效的提高整个集群的响应能力。

主从架构可以区分为：一主多从 + 一主一从再多从。

主从模式的主要特点在于：

• 添加从，源头依然是数据冗余的思想
• 读写分离：主负责读写，从只负责读，可以视为负载均衡策略
• 从需要向主同步数据，所若有的从都同步与主，对主的压力依然可能很大；所以就有了主从从的模式

需要考虑：

• 主从延迟
• 主的写瓶颈
• 主挂之后如何选主

无主节点，集群中所有的应用职能对等，没有主次之分，一个请求可以被集群中任意一个服务响应。

对于普通集群模式而言，需要考虑：

• 资源竞争：如何确保一个资源在同一时刻只能被一个业务操作，如现在同时来了申请退款和货物出库的请求，如果不对这个订单进行加锁，两个请求同时响应，将会导致发货又退款了，导致财货两失
• 数据一致性：如何确保所有的实例数据都是一致的，或者最终是一致的？如应用服务使用 jvm 缓存，那么如何确保所有实例的 jvm 缓存一致？

按照数据拆分的思路来处理，将全量的数据，通过一定规则拆分到多个系统中，每个系统包含部分的数据，减小单个节点的压力，主要用于解决数据量大的场景。

ES 的索引分片。

通过对数据项的键进行哈希处理映射其在环上的位置，然后顺时针遍历环以查找位置大于该项位置的第一个节点，将每个由键标识的数据分配给 hash 环中的一个节点，节点添加删除，对整个集群而言，仅影响其直接邻居，其他节点不受影响。

例如 A, B, C, D 四个节点，hash % 16，则：

• A -> 0,1,2,3
• B -> 4,5,6,7
• C -> 8,9,10,11
• D -> 12,13,14,15

在 10 处增加一个节点 C2，则：

• A -> 0,1,2,3
• B -> 4,5,6,7
• C -> 8,9
• C2 -> 10,11
• D -> 12,13,14,15

可以看到，就 C 受到了影响。