思考题：

  • 分布式处理的不一致情况有哪些
  • 有哪些原因造成了分布式处理的不一致
  • quorum protocol是什么
  • 主从机制下主和从的任务特点是什么
  • 数据库主从机制有哪些
  • Paxos算法过程是什么
  • PBFT算法过程是什么

  • Gossip算法过程和典型架构是什么

    CAP理论

  • 一致性Consistency：在分布是系统中，所有数据备份在同一时刻的值是否相同

  • 可用性Availability：在集群一部分节点故障后，集群整体是否还能相应客户端的读写请求
  • 分区容忍性Partition tolerance：集群中的某些节点在无法联系后，整体是否还能继续进行服务。
  • 需要通过某种机制保障CAP的实现，通过冗余和容错机制，保障系统能够继续工作
    • 一主多辅的架构，主节点的热备，定期写检查点
    • 辅节点交叉冗余
    • 心跳与容错
  • 容错机制
    • 冗余：主从
    • 备份：定期复制、镜像、快照
    • 再现：追加写、操作日志、恢复策略
  • 一致性保持问题
    • 正确的写：写的内容被记录在案，后写一定覆盖先写
    • 正确的读：并发读不会不一致，有写有读的时候保证次序问题
  • 最简单的机制：全复制
  • 常见的一致性保持策略
    • All
    • One：定期备份，如快照或检查点，对修改操作进行记录，不能保证强一致性，保证最终一致性
    • Quorum：要求W+R>N，W>N/2
      • 分布式条件下，不必等待所有反馈都到来才认为是成功，以第K快为准
      • 有效避免了因为某一个节点失效造成整体集群不可用

  • 强一致性 vs. 最终一致性

    • 强一致性 ：写复杂，用时慢；读简单，从任意单一节点读即可
    • 最终一致性 ：写简单，速度快；读复杂，需要从多个节点读并且进行判定

      主从机制

  • 主从机制概述

    • 主节点：只有一个，负责管理，是主要瓶颈，一般保存元数据，调度和任务分配。
    • 从节点：数量众多，负责任务的执行，
    • 主节点容错：备份＋日志（快照+AOF）
    • 从节点容错：主节点调度，心跳机制让主节点了解从节点情况
  • 数据库主从机制
    • 半同步复制
    • 中间件控制
    • 缓存策略

下面介绍三种无主控环境下的共识机制。

Paxos

Paxos概述

Paxos是一种分布式环境下保持一致性的协议。这是一篇比较好的介绍Paxos的博客，可以作为参考。

Paxos选举机制示例

  • 考虑A1~A5五个节点，这些节点地位相等，下面以例子的形式说明Paxos。
  • 节点A1发布一个提案，如果没有竞争，其他人给出该提案的反馈，没有意见，作为给A1的回复，等待批准结果；A1收集了足够的反馈之后，发布决议，通知所有人，产生结果；
  • 如果A1和A5同时发布了提案，由于Quorum的存在，决定权其实在收到多个提案的人手中，那些收到多个提案的人的反馈决定了谁的提案将会被批准，最终成为决议；
  • 告知机制：先收到A1的反馈，并且已经给出反馈，之后收到了A5的提案：
    • 如果还未收到A1的反馈决议，A3可以告知A5别人的提案，也可以置之不理，但不能两个提案都同意；
    • 如果已经收到A1的反馈决议，A3需要告知投票之后的结果（即A1的提案已经通过）；

  • 超时机制：假设A4提案过程中（比如收到提案给出反馈，但未收到决议）或者提案已经产生结果后重新上线

    • 即已经知道有提案的存在，但是没有结果；可能是A1失效，也有可能是A4自己的问题。
    • A4此时会向提案者询问，或者自己发起提案；
    • 如果A1正常，A1会告诉A4决议结果，算法结束；如果A1掉线且A1的提案已经超时，大家则会针对A4的提案进行投票。

      Paxos两阶段

  • Phase1.准备阶段：

    • proposer 选择一个提案编号 n 并将 prepare 请求发送 给acceptors中的一个多数派；
    • acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上 次的批准回复给 proposer，并承诺不再批准小于 n 的提 案；
  • Phase2. 批准阶段：
    • 当一个 proposor 收到了多数 acceptors 对 prepare的回复后，就进入批准阶段。它要向回复 prepare 请求的 acceptors 发送 accept 请求，包括编号n和根据 P2c 决 定的 value（如果根据 P2c 没有决定 value，那么它可以 自由决定 value）。
    • 在不违背自己向其他 proposer 的承诺的前提下， acceptor 收到 accept 请求后即批准这个请求。
  • Paxos的关键
    • proposer提出proposal，被批准后称为决议value
    • 在一次paxos算法的执行实例中，只批准choose一个value
    • learners只能获得被批准的value

  • 这个过程中发生任何中断都可能保证一致性，但Paxos效率并不高，两次两两节点之间的网络通信；

    PBFT

    PBFT概述

  • PBFT可以在多项式时间内实现拜占庭容错，要求正常节点大于三分之二

  • client：发起请求的客户端节点；
  • primary：发起者
  • backup：验证者
  • view：一个primary和多个backup产生一个view，相当于是一个共识
  • checkpoint：如果某个信息收到了超过2/3的确认，则称为一个checkpoint

  • 很多区块链都采用了PBFT作为共识机制。

    PBFT三阶段协议

  • prep-prepare：client向primary发起请求，primary收到请求，形成新消息并广播；

  • prepare：backup收到消息后，广播消息验证结果，同时等待接收超过2/3的节点的广播；
    • 广播：“我已收到消息”
    • 等待：这是为了确认“已经有超过2/3的节点收到消息”

  • commit：收到2/3的节点广播或超时后，再次发送广播，同时再次等待接收超过2/3的节点的广播。

    • 广播：“我已确认（有超过2/3的节点收到消息）”
    • 等待：为了确认“已经有超过2/3的节点确认（有超过2/3的节点收到消息）”，达成共识。

      Gossip

      Gossip概述

      两个节点如果存在数据不一致，该如何“对齐”。
      Gossip支持两种原子操作，Push操作和Pull操作

  • Push：A节点将数据(key, value, version)推送给B节点，B节点更新A中比自己新的数据，相当于以A节点的数据为准进行更新；

  • Pull：A仅将数据(key, version)推送给B，B将比A新的数据(key, value, verison)推送给A，A更新那些B中比A新的数据。

  • 任何一个节点先pull然后push就可以两节点的数据同步。

    传染病算法

  • 双节点对齐容易，多个节点怎么办呢？

  • 数据对齐（消息传递）类比疾病的传染过程
  • 节点状态：易感、感染、恢复和免疫状态
    • 尚未收到过消息的称为易感人群
    • 接收消息相当于被感染，被感染后可以继续感染别人
    • 收到过消息后再收到可能不被感染，或者不转发消息，这称为恢复和免疫
  • 怎样保证时钟的一致性
  • Gossip可以保证系统的最终一致性，基于版本号（时间戳），Gossip的基本架构如下
    • 查询操作时产生查询版本号 ，查询版本号<=副本内容中对应的值的版本号时可以查询，否则需要等待；
    • 更新操作时产生更新版本号 ，更新操作发给一个或多个副本，副本收到更新请求后对操作表和日志进行查找 ，该请求如果已经被处理过则丢弃，否则更新版本号并进行修改