Paxos的直观解释

可靠分布式系统基础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.