logseq/pages/分布式系统.md

• https://www.youtube.com/watch?v=BhosKsE8up8
• 什么是一致性
  • CAP therorem
    • 一个分布式系统，不能同时满足以下三点
      • 一致性（Consistency）
      • 可用性（Availability）
      • 分区容错性（Partition Tolerence）
    • CA
      • RDBMS
    • CP
      • MongoDB
      • HBase
      • Redis
    • AP
      • CouchDB
      • Cassandra
      • DynamoDB
      • Riak
  • 一致性模型
    • 弱一致性
      • 最终一致性
      • DBS
      • Gossip
• 一致性
  • 数据不能存在单点上
  • 分布式系统对fault tolerence的一般解决方案是state machine replication
    • log，通过log复制将数据存储到各个节点上
  • 今天我们讨论的应该是state machine replication的共识（consensus）算法
  • paxos其实是一个共识算法，系统的最终一致性，不仅需要达成共识，还会取决于client的行为
• 强一致性算法
  • 主从同步
    • 一个节点失败，Master阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低
  • 多数派
    • 在并发环境下，无法保证系统正确性，顺序非常重要
  • Paxos
    • Basic Paxos
      • 角色
        • Client：系统外部角色
        • Proposer：接受Client请求，向集群提出提议
        • Acceptor（Voter）：提议投票和接收者
        • Learner：提议接受者，backup
      • 阶段
        • Phase 1a：Prepare
          • proposer提出一个提案，编号为N，此N大于这个proposer之前提出提案编号，请求acceptors的quorum接受
        • Phase 1b：Promise
          • 如果N大于此acceptor之前接受的任何提案编号者接受，否则拒绝
        • Phase 2a：Accept
          • 如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容
        • Phase 2b：Accepted
          • 如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略
        • 
      • 潜在问题
        • 活锁（liveness）
          • 两个Proposer不停提出提案，之前的提案都被覆盖
          • 使用Random Timeout解决
        • 难实现
        • 效率低（2轮RPC）
    • Multi Paxos
      • Leader：唯一的proposer，所有请求都需要经过此Leader
      • 减少角色，进步一简化
    • Fast Paxos
  • Raft
    • Multi Paxos的简化版本
    • 划分为三个字问题
      • Leader Eleciton
      • Log Replication
      • Safety
    • 重定义角色：
      • Leader
      • Follower
      • Candidate
    • 一致性并不一定代表完全正确性
      • 三个结果
        • 成功
        • 失败
        • unknown
      • 5个节点，3个节点失败，2个节点存活
  • ZAB
    • 基本与raft一致
    • 有些名词有区别，leader周期称谓epoch，raft中为term
    • raft心跳为leader向follower，ZAB则相反
• 项目实践
  • ZooKeeper
    • 类似文件系统，可以写入Key Value
  • etcd
    • 比zookeepre文档更全