分布式系统

CAP 理论

CAP 理论是分布式系统设计中的一个基本原则，它提供了一个思考和权衡一致性、可用性和分区容错性之间关系的框架。 CAP 理论的三个要素如下：

1. 一致性（Consistency）：在分布式系统中的多个副本或节点之间，保持数据的一致性。也就是说，如果有多个客户端并发地读取数据，在任何时间点上，它们都应该能够观察到相同的数据。
2. 可用性（Availability）：系统在任何时间点都能正常响应用户请求，即使部分节点挂了，如果一个系统不能提供响应或响应时间过长，则认为系统不可用。
3. 分区容忍性（Partition tolerance）：指系统在遇到网络分区或节点失效的情况下，仍能够继续工作并保持数据的一致性和可用性。

CAP 理论指出，在分布式系统中，不能同时满足一致性、可用性和分区容错性这三个特性，只能是 CP 或者是 AP（在分布式系统中，分区是无法避免的，当分区发生时，我们必须在一致性和可用性之间做出选择）。

• CP：强一致性和分区容错性设计。这样的系统要求保持数据的一致性，并能够容忍分区故障，但可用性较低，例如在分区故障期间无法提供服务。
• AP：高可用性和分区容错性设计。这样的系统追求高可用性，而对一致性的要求较低。在分区故障期间，它可以继续提供服务，但数据可能会出现部分不一致。

在 C 一致性要求下，就必须要拒绝用户的请求，而拒绝了用户的请求就违背了 A 可用性，所以 C 和 A 在分布式环境下是永无无法同时满足的，分布式系统要么是 CP 模式，要么是 AP 模式。

BASE理论

BASE 理论是对分布式系统CAP理论中一致性与可用性权衡的进一步解释，它更注重实际业务中如何通过放松一致性来获得高可用性。 BASE 是指：

1. 基本可用性（Basically Available）：系统保证在出现故障或异常情况下依然能够正常对外提供服务，尽管可能会有一定的性能损失或功能缺失。在分布式系统中，为了保证系统的可用性，有时会牺牲一致性。
2. 软状态（Soft State）：系统中的数据的状态并不是强一致的，而是柔性的。在分布式系统中，由于网络延迟、节点故障等因素，数据可能存在一段时间的不一致。
3. 最终一致性（Eventually Consistent）：系统会保证在一段时间内对数据的访问最终会达到一致的状态。即系统允许数据副本在一段时间内存在不一致的状态，但最终会在某个时间点达到一致。

BASE 理论强调系统的可用性和性能，尽可能保证系统持续提供服务，而不是追求强一致性。在实际应用中，为了降低分布式系统的复杂性和提高性能，可以采用一些方法来实现最终一致性，如版本管理、异步复制等技术手段。

CAP理论常被用于说明分布式系统设计的极限和理论上的权衡，而BASE理论则更多地指导具体实践，如何在CAP理论所描述的限制下构建灵活且健壮的系统。

分布式共识理论

共识算法如Paxos、Raft和Zab等，解决分布式系统中多节点间如何就某个值（如配置信息、状态）达成一致性的问题。

Raft算法：“任期号”（Term）和"索引"（Index）是维护一致性和日志顺序的关键概念。

任期号：是一个单调递增的整数，它标记了集群领导权变动的时间段。每次选举都会产生一个新的任期号，并且任期号随着时间推移只会增加不会减少。这个机制有助于防止“脑裂”现象，即防止多个节点同时认为自己是合法的领导者。

在Raft算法中，当一个Follower节点在一段时间内没有收到当前Leader的心跳包时，它会成为Candidate并开始新一轮的选举，此时任期号加一。如果该节点获得大多数节点的投票，那么它就会成为新的Leader，并以新的任期号开始发送心跳和日志条目给其他节点。任期号也用于解决网络分区和消息延迟问题。例如，一个过时的Leader（其身份属于旧任期）尝试向集群中的其他节点发送命令，但由于任期号比当前任期低，这些节点会拒绝执行这些命令并告知该Leader其任期已经过时。

索引：是日志条目在日志中的位置，表征了特定日志条目在整个日志序列中的顺序。索引保证了日志条目可以按照严格的顺序进行复制和应用到状态机上。

当一个Leader接收到客户端的请求时，它会生成一个带有当前任期号和唯一索引的日志条目。然后，Leader会将包含此日志条目的信息复制到集群中的其他节点。一旦条目被成功复制到大多数节点，它就可以被提交并应用到状态机上。Leader可以使用索引和任期号来确定不一致的位置，并通过发送缺失的条目来恢复日志的一致性。

日志同步的概念：服务器接收客户的数据更新/删除请求，这些请求会落地为命令日志。只要输入状态机的日志命令相同，状态机的执行结果就相同。所以Raft的核心就是leader发出日志同步请求，follower接收并同步日志，最终保证整个集群的日志一致性。

核心流程：

• 首先选出leader，leader节点负责接收外部的数据更新/删除请求；
• 然后日志复制到其他follower节点，同时通过安全性的准则来保证整个日志复制的一致性；
• 如果遇到leader故障，followers会重新发起选举出新的leader；

具体流程：

Leader接收所有客户端请求，然后转化为log复制命令，发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示leader的当前任期。

follower收到日志复制请求的处理流程：

（1）follower会使用前一个日志的任期号和日志索引来对比自己的数据：

• 如果相同，接收复制请求，回复ok；
• 否则回拒绝复制当前日志，回复error；

（2）leader收到拒绝复制的回复后，继续发送节点日志复制请求，不过这次会带上更前面的一个日志任期号和索引；

（3）如此循环往复，直到找到一个共同的任期号&日志索引。此时follower从这个索引值开始复制，最终和leader节点日志保持一致；

（4）日志复制过程中，Leader会无限重试直到成功。如果超过半数的节点复制日志成功，就可以任务当前数据请求达成了共识，即日志可以commite提交了；

两个特点：

（1）如果在不同日志中的两个条目有着相同索引和任期号，则所存储的命令是相同的，这点是由leader来保证的；

（2）如果在不同日志中的两个条目有着相同索引和任期号，则它们之间所有条目完全一样，这点是由日志复制的规则来保证的；

参考：https://zhuanlan.zhihu.com/p/610671151

应用

在设计分布式系统时，根据具体的场景和需求，可能会结合这两种理论。例如，一个电商平台可能会在订单处理系统中优先考虑一致性（CAP的C），而在商品浏览中优先保证可用性和最终一致性（BASE）。这样，即使在面对网络问题和服务器故障时，用户仍能够浏览商品，而订单处理则采取措施确保交易数据的准确性。