【raft】万字长文解析raft算法原理
万字长文解析raft算法原理
https://zhuanlan.zhihu.com/p/600147978
2d7c2be1e37f0ec650c2fdca377851ae_v2-803ca43b7a2a178514d0ff3d66bdefd6_720w_source=172ae18b.jpg
数量关系之容斥原理
https://zhuanlan.zhihu.com/p/511851903
为什么 raft 算法中 大多数节点同意就行，背后的原理是什么？
Raft 算法中的核心构造是一种一致性模型，每个节点都会通过相互通信来达成一致，从而使整个系统的数据达到一致性。当一些节点提议一个值时，需要获得大多数节点的同意才能生效。这一原则有以下原因：
-
数据一致性：为了保证整个系统的数据达到一致性，只有得到大多数节点的同意，才能确保提议的值已经被持久化，不能再被更改。如果只是其中一部分节点的同意，就不能保证整个系统的数据达到一致性。
-
系统容错性：在分布式系统中，有可能会发生节点故障的情况。如果一个提议只得到了少数节点的同意，一旦其中一个节点故障，那么提议的值就不能被持久化，整个系统的数据就会出现分歧，无法达成一致性。而如果得到了大多数节点的同意，即使其中一个节点故障，仍然可以得到新的节点来取代它，从而达到系统的容错性。
-
性能优化：在 Raft 算法中，如果只是其中一部分节点的同意，那么需要继续等待其他节点的同意，这会导致系统的响应时间变长、吞吐量下降，从而影响系统的性能。而如果只需要大多数节点的同意，那么可以快速地得出提议的结果，提高系统的性能。
Raft 算法中大多数节点同意指的是在 Raft 的 Leader 副本向 Follower 副本发送 Append Entries 请求时，只有超过半数以上的 Follower 副本（即大多数）响应了 Append Entries 请求，并返回了成功响应，Leader 副本才确定该 Log 已经提交。
背后的数学原理是基于分布式系统中的 CAP 原理。CAP 原理指的是分布式系统中无法同时满足三个要素：一致性（Consistency）、可用性（Availability）和分区容错性（Partition Tolerance）。在 Raft 算法中，强一致性是首要目标，因此在发生网络分区时会保证一定时间内不可用，但是能够保证集群内的数据一致性。
而在分布式系统中，网络分区是无法避免的，因此需要采取某些机制来保证数据一致性。在 Raft 算法中，只有当大多数节点同意之后才能提交 Log，保证了数据的一致性。这是因为如果只有少数节点同意并提交 Log，那么在节点复原之后就会导致数据不一致的情况出现。
因此，大多数节点同意是 Raft 算法中保障强一致性的基本原理之一，使用基于它的数学原理保证数据在所有节点间保持一致。
Raft算法中，当大多数节点同意一个提案时，该提案就会被提交并被认为是已经被所有节点接受了。这是因为Raft算法采用了多数派原则，即只有在大多数节点同意时才能进行提交，从而保证系统的一致性和可靠性。
多数派原则的数学原理是基于拜占庭将军问题和分布式系统一致性理论的基础上。
在拜占庭将军问题中，一组将军需要达成一致的决策，但是其中一些将军可能是叛徒，会发送错误信息，导致其他将军做出错误的决策。
在分布式系统中，节点之间的通信也可能会出现错误，导致节点之间的数据不一致。
多数派原则的数学原理是基于以下两个假设：
- 大多数节点是正确的，即不会出现错误的节点发送错误的信息。
在Raft算法中，所有节点都会发送消息以达成共识，例如，选举新的领导者或提交新的日志条目等。
这些消息必须是正确的，否则可能会导致错误的结果。
例如，如果一个节点发送了错误的选举消息，可能会导致选出错误的领导者，从而影响整个系统的运行。
因此，为了保证Raft算法的正确性和可靠性，我们假设大多数节点是正确的，即它们不会发送错误的消息。
这样，当大多数节点同意一个提案时，我们可以认为这个提案是正确的，从而保证系统的一致性和可靠性。
如果一个节点出现了错误，但它不是大多数中的一员，那么它的错误不会影响整个系统的正确性。
- 如果一个节点已经知道了大多数节点的决策，那么它也能够得出正确的决策。
根据这两个假设，当大多数节点同意一个提案时，可以认为这个提案是正确的。
因为大多数节点都是正确的，所以他们发送的信息是正确的；根据第二个假设，如果一个节点知道了大多数节点的决策，那么它也能够得出正确的决策。
因此，当大多数节点同意一个提案时，可以认为这个提案是已经被所有节点接受了，从而保证了系统的一致性和可靠性。
容斥原理与多数派原则之间的关系在于，多数派原则可以被看作是一种特殊的容斥原理。
在多数派原则中，我们需要大多数节点同意才能进行提交，这相当于求出了所有节点的交集。
容斥原理则可以用来计算所有节点的并集和交集大小，从而帮助我们判断是否满足多数派原则。
参考
万字长文解析raft算法原理
https://zhuanlan.zhihu.com/p/600147978
数量关系之容斥原理
https://zhuanlan.zhihu.com/p/511851903
