一致性算法原理

一致性算法原理

什么是一致性CAP Theorem

对于一个分布式系统，不能同时满足以下三点：

• 一致性(Consistency)
• 可用性(Availability)
• 分区容错性(Partition Tolerance)

一致性模型

• 弱一致性(添加记录，但是查询的时候数据可能会有延迟)
  • 最终一致性
    • DNS(Domain Name System)
    • Gossip(Cassandra的通信协议)
• 强一致性
  • 同步
  • Paxos
  • Raft(multi-paxos)
  • ZAB(multi-paxos)

明确问题

数据不能存在单点上

分布式系统对fault tolorence的一般解决方案是state machine replication

paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为

强一致性-主从同步

主从同步复制

1. Master接受写请求
2. Master复制日志至slave
3. Master等待，直到所有从库返回

问题：一个节点失败，Master阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低

强一致性算法-多数派

基本思想：每次写都保证写入N/2个节点，每次读保证从大于N/2个节点读(多数派)

问题：在并发环境下，无法保证系统正确性，顺序非常重要

强一致性算法-Paxos

Lesile Lamport,Latex的发明者，为了描述Paxos算法，Lamport虚拟了一个叫Paxos的希腊城邦，这个岛按照议会民主制的政治模式指定法律，但是没有人愿意将自己的全部时间和精力放在这种事，所有无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间

Paxos有三个版本：Basic Paxos、Multi Paxos、Fast Paxos

Basic Paxos

角色介绍：

Client：系统外部角色，请求发起者，像民众

Propser：接受Client请求，向集群提出提议(propose)，并在冲突发生时，起到冲突调节的作用，像议员，替民众提出议案

Acceptor(Voter)：提议投票和接收者，只有在形成法定人数(Quorum，一般为majority多数派)时，提议才会被接受，像国会

Learner：提议接受者，backup，备份，对集群一致性没什么影响，像记录员

步骤、阶段：

1. proposer提出一个提案，编号为N，此N大于这个proposer之前提出提案编号，请求acceptors的quorum接受
2. 如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝
3. 如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容
4. 如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案，否则忽略

Multi Paxos

强一致性算法-Raft

• Raft
  • 划分成三个子问题
    • Leader Election
    • Log Replication
    • Safety
  • 重新定义角色
    • Leader
    • Follower
    • Candidate
  • 原理动画解释：http://thesecretlivesofdata.com/raft/
  • 场景测试：https://raft.github.io/