基础理论

CAP理论

  • 一致性 Consistency：分布式系统所有数据备份在同一时刻相同；
  • 可用性 Availability：每个请求都有相应，不管成功或失败；
  • 分区容错性 Partition：分布式系统数据丢失不影响系统继续运行。

分布式系统中，CAP不能同时满足，只能AP、CP、AC（不常用）；
分区容错是必须满足的，而一致性与可用性对立，其原因是如果保证一致性（涉及到锁），锁定期间可用性消失；如果保证可用性，就不能加锁；
选择：数据安全优先时使用CP，用户体验优先时使用AP。

一致性讨论

  • 强一致性：一次写之后，任何读都是最新的数据（Raft算法满足CP）；
  • 弱一致性：一次写之后，不保证后续所有读到的都是最新的数据；

  • 最终一致性：一次写之后，在后续不产生新的写的条件下，最终所有后续读到的都是最新的数据（Gossip协议满足AP，Quorum NWR升级为强一致性）。

    Raft算法

    节点分为以下三种：

  • Leader：接收Client的情况，任何时刻都只有一个Leader；

  • Follower：被动接收各种RPC请求；
  • Candidate：选举出新Leader的候选接点。

工作流程：

  • Leader定期向其他节点发送心跳；
  • Follower在超时没收到Leader的心跳时，转为Candidate；
  • 收到多数投票应答的Candidate转为Leader；

  • Leader和Candidate接收到更高版本的消息后转为Follower。

    Gossip算法

    三种方式：

  • 直接邮寄 Direct Mail：将数据的更新直接发送给其他指定节点；

  • 反熵 Anti-entropy：以push、pull或push与pull结合的方式修改不同节点的副本；

  • 谣言传播 Rumor mongering：有数据更新就变为活跃态向其他节点更新，被更新的也变为活跃态向其他节点更新。

    Quorum NWR算法

    由三个因子构成，可以自定义一致性级别：

  • N Replication Factor：集群中同一份数据的副本个数；

  • W Write Consistency Level：完成W个副本更新才算完成写操作；
  • R Read Consistency Level：读一个数据时需要读取R个副本中最新的数据；
  • W + R > N时，为强一致性；
  • W + R ≤ N时，为最终一致性。