算法基础¶
CAP定理¶
CAP本身是三个单词的缩写：
- Consistency：一致性
- Availability：可用性
- Partition-tolerance：分区容错性
CAP定理指出，在异步网络模型中，不存在一个系统同时满足上述三种属性，即分布式系统必须舍弃其中一个属性。
共识算法¶
共识的意思就是指所有的参与者都有相同的认识（可以理解为强一致性）。共识算法可以依据是否有恶意节点分为两类，即是否有恶意节点。
Paxos算法¶
Paxos算法是Leslie Lamport在1998年《The Part-Time Parliament》中所提出。
Paxos算法中存在三种角色：
- Proposer：参与提案，并向Acceptor发送提案
- Acceptor：参与决策，回应提案。如果提案获得多数（过半）Acceptor接受，则认为提案被批准
- Learner：不参与决策，只学习最新达成一致的提案
Paxos算法的决议过程分为两种：
- Basic Paxos:针对单个value的决议过程
- Multi Paxos：针对连续多个value的决议过程
