1. 介绍

zookeeper的分布式一致性算法zab来源于paxos。为了更好的理解zookeeper以及分布式一致性的解决算法paxos,我做了一番调研。最终决定以可靠分布式系统基础 Paxos 的直观解释这篇PPT的阅读分析作为我学习paxos的入门资料,详细阅读。

之所以需要学习概算法是因为它实在十分重要,它是分布式系统的核心算法。分布式中最主要的一个问题就是: 多节点如何对某件事情达成一致

本文是一篇paxos入门教程, 从基本的分布式中的问题: 主从复制,quorum-rw等算法出发, 通过逐步解决和完善这几个问题, 最后推导出paxos的算法.

本文分为2个部分:

  1. 前1部分是分布式一致性问题的讨论和解决方案的逐步完善, 用比较通俗的语言得出paxos算法的过程. 如果你只希望理解paxos而不打算花太多时间深入细节, 只阅读这1部分就可以啦.

  2. 第2部分是paxos算法和协议的严格描述. 这部分可以作为paxos原paper的实现部分的概括. 如果你打算实现自己的paxos或类似协议, 需要仔细了解协议细节, 希望这部分内容可以帮你节省阅读原paper的时间.

2. 实际的高可用问题

2.1 问题背景和需求

2.2 多副本来解决可用性的方案

多副本下的可靠性(作者使用环境经验值):

下图说明了几种依靠多副本来保证高可用的方式:

这几种方式的简单说明见:最终一致性的保证策略

3 基础的复制算法

3.1 主从异步复制

3.2 主从同步复制

3.3 主从半同步复制

3.4 多数派读写

多数派读写的意思就是少数服从多数,在读的时候以多数派为准。

多数派写相比于之前的几种方式保证了最终一致性,但是仍然存在以下事务性问题:

  1. 非原子更新
  2. 脏读 3.更新丢失问题

4. 多数派写问题实例

通过一个假想的分布式存储服务的例子来引入paxos

4.1 实现

可以看到读取的时候以多数派为准。

4.2 并发问题

可以看到i2=i1+2即为4,然后会将Y的值更新到i2,这时候如果写入成功就会丢失数据了。

4.4 改进办法

为了避免这种并发问题,需要保证某个版本只能由1次成功写入:

确定1个值是否被写过,可以通过先进行一次多数派读来判断该版本是否被写过。

注意,这里存储节点做的标记,以最后1次为准哦。所以节点2,在Y尝试写前读取后被覆盖。


这就是传说中的paxos的简单说明。本质上是一个分布式场景多数派读写时候的一致性控制。