背景
多个节点一起完成一件事情.
分布式中唯一的一个问题：对某事达成一致.
Paxos: 分布式系统的核心算法.
目录
1. 问题
2. 复制策略
3. Paxos 算法
4. Paxos 优化
问题
对系统的需求:
持久性要达到：99.99999999%
我们可以用的基础设置:
磁盘: 4% 年损坏率
服务器宕机时间: 0.1% 或更长
IDC间丢包率: 5% ~ 30%
解决方案(可能)
多副本
x<n个副本损坏不会丢数据
多副本的可靠性:
1 副本: ~ 0.63%
2 副本: ~ 0.00395%
3 副本: < 0.000001%
n 副本: = 1 - x^n /* x = 单副本损坏率 */
解决方案.
如何实施‘复制’?
除了副本数之外，还有:
可用性
原子性
一致性
...
基础的复制算法
主从异步复制
主从同步复制
主从半同步复制
多数派写（读）
如Mysql的binlog复制.
1. 主接到写请求.
2. 主写入本磁盘.
3. 主应答‘OK’.
4. 主复制数据到从库.
如果磁盘在复制前损坏：
→ 数据丢失.
主从异步复制
Time
MasterClient Slave.1 Slave.2
Disk Failure
主从同步复制
1. 主接到写请求.
2. 主复制日志到从库.
3. 从库这时可能阻塞...
4. 客户端一直在等应答’OK’，直到
所有从库返回.
一个失联节点造成整个系统
不可用.
: 没有数据丢失.
: 可用性降低.
Time
MasterClient Slave.1 Slave.2
主从半同步复制
1. 主接到写请求.
2. 主复制日志到从库.
3. 从库这时可能阻塞...
4. 如果1<=x<=n个从库返回‘OK’，
则返回客户端‘OK’.
: 高可靠性.
: 高可用性.
: 可能任何从库都不完整
→ 我们需要 多数派写(读)
Time
MasterClient Slave.1 Slave.2
多数派写
Dynamo / Cassandra
客户端写入W >=N/2+1个节点.
不需要主.
多数派读:
W + R > N; R >= N/2+1
容忍最多(N-1)/2个节点损坏.
Time
Node.1Client Node.2 Node.3
多数派写. 后写入优胜
最后1次写入覆盖先前写
入.
所有写入操作需要有1个全
局顺序：时间戳
Time
Node.1Client Node.2 Node.3
: 高可靠性.
: 高可用性.
: 数据完整性有保证.
够了吗？
多数派写..
一个假想存储服务
● 一个有3个存储节点的存储服务集群.
● 使用多数派读写的策略.
● 只存储1个变量“i”.
● “i” 的每次更新对应有多个版本: i1, i2, i3…
● 这个存储系统支持3个命令:
get /* 读最新的 “i” */
set <n> /* 设置下个版本的i的值为 <n> */
inc <n> /* 对“i” 加<n>，也生成1个新版本 */
我们将用这个存储系统来演示多数派读写策略的不足，
以及如何用paxos解决这些问题.
一个假想存储服务.实现
命令实现：
"set" → 直接对应多数派写.
"inc" → (最简单的事务型操作):
1. 通过多数派读，读取最新的 “i”: i1
2. Let i2 = i1 + n
3. set i2
X
set i2=3
X
get i
2
1
2
1
0
0
3
2
2
1
3
2
X
get i1=2
i2 = i1 + 1
3
2
2
1
3
2
set i2=3
OK
set i2=4
一个假想存储服务..并发问题
X
X
get i
2
1
2
1
0
0
3
2
2
1
3
2
5
3
2
1
5
3
X
get i1=2
i2 = i1 + 1
我们期待最终X可以读到i3=5,
这需要Y能知道X已经写入了i2。如何实现这个机制？
Y
get i1=2
Y
i2 = i1 + 2
3
2
2
1
3
2
此 时为了保证正确，Y必须重新运行多数派 读，然后再进行一次多数派写
这1步Y必须失
败。
否 则X写入的值
会 丢失。
一个假想存储服务...
在X和Y的2次“inc”操作后，为了得到正确的i3：
整个系统里对i的某个版本(i2)，只能有1次成功写入.
推广为:
在存储系统中，一个值(1个变量的1个版本)在被认为确定
(客户端接到OK)之后，就不允许被修改().
如何定义“被确定的”?
如何避免修改“被确定的”值?
如何确定一个值
X
Y
Any value set?
X
No
XX -
---
Any value set?
---
Y
Yes, Y gives up
X
XX -
XX -
方案: 每次写入一个值前，先运行一次多数派读，来确认是
否这个值（可能）已经被写过了.