分布式理论

CAP

一致性：在同一时刻副本一致，所有节点读到修改后的最新数据
- 强一致性、单调一致性、最终一致性
可用性：每次请求都能获取非错的响应，尽量低延迟，不保证节点数据最新
分区容忍性：出现网络分区时（节点间通信中断），系统仍能对外提供服务

BASE

Basically Available（基本可用）：分布式系统在出现不可预知故障的时候，允许损失部分可用性
Soft state（软状态）：软状态也称为弱状态，和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。
Eventually consistent（最终一致性）：最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性

BASE是对CAP中一致性和可用性权衡的结果，其基本思路就是：通过业务，牺牲强一致性而获得可用性，并允许数据在一段时间内是不一致的，但是最终达到一致性状态。

一致性协议

线性一致性

一句话概括：在分布式系统上实现寄存器语义。寄存器中的变量可以被原子地被修改，且后续对该变量的读取会返回当次修改的值，直到其被再此修改，简单来说是保证读到最近更新的值。

如何判断一个分布式系统是具备线性一致性？首先我们约定好线性一致性条件下请求之间的相互关系：

• 对于调用时间有交叠的并发请求，生效的顺序可以任意确定。比如并发读写请求时，读请求无论返回新值、旧值都可以。
• 对于调用时间有偏序的请求，比如请求B开始在A结束之后，那么B的结果不能违背A已确定的结果。

按照上述给定的请求关系，结合实际调用结果来判断有否出现结果与约定相违背的情况，没有的话整个系统就符合线性一致性。如上图所示，我们可以认为线性一致性系统仿佛有一条隐藏的全局时间轴，每个请求调用的过程中都有一个生效瞬间（如“|”竖线所示）、在全局时间轴上有具体的时间戳，如果将调用生效瞬间按顺序连接起来，所有连线都会呈现从左到右、顺序发生的关系。看图中最后3个请求，cas(x,2,4)与两个read(x)分别都是并发关系，然而两个read(x)是有偏序的，说明后一个read(x)应该能读到前一个read(x)的结果。cas(x,2,4)虽然是与最后的read(x)是并发关系，但由于它的修改结果是成功的，说明其必须发生在前一个read(x)之前，所以到最后我们没法从最后3个请求中发现合理的调用顺序，所以系统不是线性一致性的。

顺序一致性

不要求操作的时序与真实物理时间一致。两个不相关的操作，如序列 读A 写A 读B 写B，要求读A、B能读到最新值，但不要求读B到最新值时，读A也一定是最新值。

一致性解决方案

两阶段提交

1. 提交事务请求（投票阶段）
   • 协调者向参与者发送事务内容，询问是否可以执行事务提交操作，等待响应
   • 参与者执行事务操作，将undo和redo日志记录，并回复协调者执行成功Yes/No
2. 执行事务提交（执行阶段）.
   • 如果都是参与者都回复Yes，则协调者向参与者发送提交请求，否则发送回滚请求
   • 参与者根据协调者的请求执行事务提交或回滚，并向协调者发送Ack消息
   • 协调者收到所有的Ack消息过后判断事务的完成或者中断

它是一个强一致性协议，但可用性太差，存在问题：

• 阻塞与单点故障：所有参与者必须收到协调者发起的指令才会提交，否则资源会被锁定，但当网络问题或协调者宕机时会阻塞
• 一致性问题：网络原因，参与者可能没收到协调者发送的指令(commit)，导致集群数据不一致

优化：

• 超时判断：长时间未收到回复可以多播取消事务
• 互询机制：参与者回复yes后，如果迟迟收不到协调者最终的commit/abort，可以询问其他参与者来决定自身下一步操作，避免一直阻塞

2PC广泛应用于关系数据库的分布式事务处理，如mysql的内部与外部XA都是基于2PC的，一般想要把多个操作打包未原子操作也可以用2PC

三阶段提交

把2PC的第一阶段拆成两阶段：

1. 事务询问（canCommit）
   • 协调者向参与者发送一个包含事务内容的询问请求，询问是否可以执行事务并等待
2. 执行事务预提交（preCommit）
   • 若协调者收到全是yes，就发送preCommit请求，否则发布abort请求
   • 参与者若收到preCommit则执行事务操作并记录undo和redo然后发送Ack
3. 执行事务提交（doCommit）
   • 协调者收到所有的Ack则发送doCommit请求，若收到了No或者超时则发送abort请求
   • 参与者收到doCommit就执行提交并发送Ack，否则执行回滚并发送Ack
   • 协调者收到Ack判断是完成事务还是中断事务

2PC 和 3PC 是分布式事务中两种常见的协议，3PC 可以看作是 2PC 协议的改进版本，相比于 2PC 它有两点改进：

引入了超时机制，同时在协调者和参与者中都引入超时机制（2PC 只有协调者有超时机制），所以发生阻塞的几率变小了
3PC 相比于 2PC 增加了 CanCommit 阶段，可以尽早的发现问题，从而避免了后续的阻塞和无效操作。

分布式一致性算法

一致性算法的目的是保证在分布式系统中，多数据副本节点数据一致性。主要包含一致性Hash算法，Paxos算法，Raft算法，ZAB算法等。

Raft

Paxos

ZAB

ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。基于该协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。

当 Leader 服务可以正常使用，就进入消息广播模式，当 Leader 不可用时，则进入崩溃恢复模式。

消息广播：

• 使用的是一个原子广播协议，类似一个2PC过程。对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务，将其发送给所有 Follwer ，如果超过半数成功响应，则执行 commit 操作。减小了同步阻塞，也提高了可用性
• 在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，避免同步，实现异步解耦

崩溃恢复：
ZAB定义两个原则：

• Leader 事务只要commit了，最终就会被所有服务器提交。
• Leader 提出/复制了事务但没提交，则丢弃事务。

Leader 崩溃后选举时，要保证新选举出来的 Leader 拥有集群总所有机器编号（即 ZXID 最大）的事务，即这个 Leader 一定具有所有已经提交的提案。
当 Follower 链接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID (LeaderId + 事务ID) 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

zookeeper是弱一致性模型，但是也可以支持强一致性模型，用sync()方法强制读取从leader同步数据。

分布式同步机制

1. kafka
   1. 削峰填谷、副本数量灵活、写入kafka后存储侧无需WAL带宽资源
   2. 业务方直接写则还得kafka中转、成本、Kafka partition数有限导致单个partition数据量大
2. 主从(异步)
   1. 写入延迟低、便于batch优化、副本数量灵活
   2. 业务方是kafka的话，需要额外consumer资源、宕机丢数据
3. raft
   1. 读主时强一致性
   2. 难以双副本、性能得优化、跨AZ部署时的写入延迟