Paxos的直观解释

1 .Paxos 可靠分布式系统基础：paxos的直观解释 2015-07-02 @drdrxp 

2 .背景 多个节点一起完成一件事情. 分布式中唯一的一个问题：对某事达成一致. Paxos: 分布式系统的核心算法. 

3 .目录 1. 问题 2. 复制策略 3. Paxos 算法 4. Paxos 优化 

4 .问题 对系统的需求: 持久性要达到：99.99999999% 我们可以用的基础设置: 磁盘: 4% 年损坏率 服务器宕机时间: 0.1% 或更长 IDC间丢包率: 5% ~ 30% 

5 .解决方案(可能) 多副本 x<n个副本损坏不会丢数据 多副本的可靠性: 1 副本: ~ 0.63% 2 副本: ~ 0.00395% 3 副本: < 0.000001% n 副本: = 1 - x^n /* x = 单副本损坏率 */ 

6 .解决方案. 如何实施‘复制’? 除了副本数之外，还有: 可用性 原子性 一致性 ... 

7 .基础的复制算法 主从异步复制 主从同步复制 主从半同步复制 多数派写（读） 

8 .主从异步复制 如Mysql的binlog复制. Time Client Master Slave.1 Slave.2 1. 主接到写请求. 2. 主写入本磁盘. 3. 主应答‘OK’. Disk Failure 4. 主复制数据到从库. 如果磁盘在复制前损坏： → 数据丢失. 

9 .主从同步复制 1. 主接到写请求. Time 2. 主复制日志到从库. Client Master Slave.1 Slave.2 3. 从库这时可能阻塞... 4. 客户端一直在等应答’OK’，直到 所有从库返回. 一个失联节点造成整个系统 不可用. : 没有数据丢失. : 可用性降低. 

10 .主从半同步复制 1. 主接到写请求. Time 2. 主复制日志到从库. Client Master Slave.1 Slave.2 3. 从库这时可能阻塞... 4. 如果1<=x<=n个从库返回‘OK’， 则返回客户端‘OK’. : 高可靠性. : 高可用性. : 可能任何从库都不完整 → 我们需要 多数派写(读) 

11 .多数派写 Time Dynamo / Cassandra Client Node.1 Node.2 Node.3 客户端写入W >=N/2+1个节点. 不需要主. 多数派读: W + R > N; R >= N/2+1 容忍最多(N-1)/2个节点损坏. 

12 .多数派写. 后写入优胜 最后1次写入覆盖先前写 Time 入. Client Node.1 Node.2 Node.3 所有写入操作需要有1个全 局顺序：时间戳 

13 .多数派写.. : 高可靠性. : 高可用性. : 数据完整性有保证. 够了吗？ 

14 .多数派写... W + R > N 一致性: 最终一致性 事务性: 非原子更新 脏读 更新丢失问题 http://en.wikipedia.org/wiki/Concurrency_control 

15 .一个假想存储服务 ● 一个有3个存储节点的存储服务集群. ● 使用多数派读写的策略. ● 只存储1个变量“i”. ● “i” 的每次更新对应有多个版本: i1, i2, i3… ● 这个存储系统支持3个命令: get /* 读最新的 “i” */ set <n> /* 设置下个版本的i的值为 <n> */ inc <n> /* 对“i” 加<n>，也生成1个新版本 */ 我们将用这个存储系统来演示多数派读写策略的不足， 以及如何用paxos解决这些问题. 

16 .一个假想存储服务.实现 命令实现： "set" → 直接对应多数派写. "inc" → (最简单的事务型操作): 1. 通过多数派读，读取最新的 “i”: i1 2. Let i2 = i1 + n 3. set i2 get i1=2 X 21 21 00 i2 = i1 + 1 set i2=3 X 21 32 32 get i X 21 32 32 

17 .一个假想存储服务..并发问题 get i1=2 get i1=2 X 21 21 00 Y i2 = i1 + 1 i2 = i1 + 2 set i2=3 X OK 21 32 32 set i2=4 这1步Y必须失 败。 21 32 32 Y 否则X写入的值 会丢失。 此时为了保证正确，Y必须重新运行多数派 读，然后再进行一次多数派写 get i X 21 53 53 我们期待最终X可以读到i3=5, 这需要Y能知道X已经写入了i2。如何实现这个机制？ 

18 .一个假想存储服务... 在X和Y的2次“inc”操作后，为了得到正确的i3： 整个系统里对i的某个版本(i2)，只能有1次成功写入. 推广为: 在存储系统中，一个值(1个变量的1个版本)在被认为确定 (客户端接到OK)之后，就不允许被修改(). 如何定义“被确定的”? 如何避免修改“被确定的”值? 

19 .如何确定一个值 方案: 每次写入一个值前，先运行一次多数派读，来确认是 否这个值（可能）已经被写过了. Any value set? X - - - No X - - - X X X - Any value set? X X - Y Yes, Y gives up X X - Y 

20 .如何确定一个值.并发问题 但是，X和Y可能同时以为还没有值被写入过，然后同时开始 写。 Any value set? Any value set? X - - - Y No No X - - - Y X X X - X Y Y Y 更新丢失 

21 .如何确定一个值.. 方案改进:让存储节点记住谁最后1次做过“写前读取”，并拒 绝之前其他的“写前读取”的写入操作。 Any value set? X - - - No 现在节点1、2只接受X的写入 X - - - 多数派读的同时写入：X是最后读的。 Any value set? - - - Y No 现在节点2、3只接受Y的写入 - - - Y 多数派读的同时写入：Y是最后读的 X X - - X Y Y Y 

22 .如何确定一个值... 使用这个策略，一个值(i的每个版本)可以被安全的存储. Leslie Lamport 写了个这个算法的paper. 

23 .Paxos 

24 .Paxos是什么 ● 一个可靠的存储系统: 基于多数派读写. ● 每个paxos实例用来存储一个值. ● 用2轮RPC来确定一个值. ● 一个值‘确定’后不能被修改. ● ‘确定’指被多数派接受写入. ● 强一致性. 

25 .Paxos Classic Paxos 1个实例(确定1个值)写入需要2轮RPC. Multi Paxos 约为1轮RPC，确定1个值(第1次RPC做了合并). Fast Paxos 没冲突：1轮RPC确定一个值. 有冲突：2轮RPC确定一个值. 

26 .Paxos: 执行的条件 存储必须是可靠的: 没有数据丢失和错误 /* 否则需要用Byzantine Paxos */ 容忍: 消息丢失(节点不可达) 消息乱序 

27 .Paxos: 概念 Proposer: 发起paxos的进程. Acceptor: 存储节点，接受、处理和存储消息. Quorum(Acceptor的多数派) : n/2+1个Acceptors. Round：1轮包含2个阶段：Phase-1 & Phase-2 每1轮的编号 (rnd): 单调递增；后写胜出；全局唯一(用于区分Proposer); 

28 .Paxos: 概念. Acceptor看到的最大rnd (last_rnd): Acceptor记住这个值来识别哪个proposer可以写。 Value (v): Acceptor接受的值. Value round number (vrnd): Acceptor接受的v的时候的rnd 值‘被确定的’定义： 有多数(多于半数)个Acceptor接受了这个值. 

29 .Paxos: Classic - phase 1 Proposer X Acceptor 1,2,3 rnd=1 X - - - last_rnd=0, v=nil, vrnd=0 Phase 1 last_rnd=0, v=nil, vrnd=0.. X 1, 1, - 当Acceptor收到phase-1的请求时： ● 如果请求中rnd比Acceptor的last_rnd小，则拒绝请求 ● 将请求中的rnd保存到本地的last_rnd. 从此这个Acceptor只接受带有这个last_rnd的phase-2请求。 ● 返回应答，带上自己之前的last_rnd和之前已接受的v.