PAXOS

总结自paxos

前言

是什么

在分布式系统中保证多副本数据强一致的算法.

有什么用

没有paxos的一堆机器, 叫做分布式;
有paxos协同的一堆机器, 叫分布式系统.

分布式系统要解决的问题

背景

多个节点一起完成一件事情。
分布式中唯一的问题：对某事保持一致。
Paxos：分布式系统的核心算法。

paxos的工作, 就是把一堆运行的机器协同起来, 让多个机器成为一个整体系统. 在这个系统中, 每个机器都必须让系统中的状态达成一致, 例如三副本集群如果一个机器上上传了一张图片, 那么另外2台机器上也必须复制这张图片过来, 整个系统才处于一个一致的状态.

问题

分布式系统的一致性问题最终都归结为分布式存储的一致性. 像aws的对象存储可靠性要求是9~13个9. 而这么高的可靠性都是建立在可靠性没那么高的硬件上的.

对系统的需求：持久性要达到 99.99999999%
我们可以用的基础设施：

磁盘: 4%年损坏率
服务器宕机时间：0.1%或者更长
IDC间丢包率：5% ~ 30%

解决方案

几乎所有的分布式存储(甚至单机系统, 参考EC第一篇:原理, EC第二篇:实现, EC第三篇:极限) 都必须用某种冗余的方式在廉价硬件的基础上搭建高可靠的存储. 而冗余的基础就是多副本策略, 一份数据存多份. 多副本保证了可靠性, 而副本之间的一致, 就需要paxos这类分布式一致性算法来保证.

(可能的解决方案)
多副本：x<n个副本损坏不会丢失数据
多副本的数据丢失风险：

1 副本：~ 0.63%
2 副本：~ 0.00395%
3 副本：< 0.000001%
n 副本：~ x^n //x单副本损坏率

如何实施复制？

不太完美的复制策略

复制算法

主从异步复制
主从同步复制
主从半同步复制
多数派写(读)

主从异步复制

主从异步复制是最简单的策略之一, 它很容易实现, 但存在一个问题: 客户端收到一个数据已经安全(OK)的信息, 跟数据真正安全( 数据复制到全部的机器上)在时间上有一个空隙, 这段时间负责接收客户端请求的那个机器(master)如果被闪电击中或被陨石砸到或被打扫卫生的大姐踢断了电源, 那数据就可能会丢失. 因此它不是一个可靠的复制策略(使用主从异步复制要求你必须相信宇宙中不存在闪电陨石和扫地大姐).

如Mysql的binlog的复制

主接到写请求
主写入本磁盘
主应答ok
主复制数据到从库

如果磁盘在复制前损坏：数据丢失

txt

autonumber
Client ->> Master: 
Master ->> Client: 
Note over Master: Disk Failure
Master-->>Slave.1: 
Slave.1-->>Master: 
Master-->>Slave.2: 
Slave.2-->>Master:

主从同步复制

跟主从异步复制相比, 主从同步复制提供了完整的可靠性: 直到数据真的安全的复制到全部的机器上之后, master才告知客户端数据已经安全.

但主从同步复制有个致命的缺点就是整个系统中有任何一个机器宕机, 写入就进行不下去了. 相当于系统的可用性随着副本数量指数降低.

主接到写请求
主复制日志到从库
从库此时阻塞
客户端一直在等待ok，直到所有从库返回

一个失联节点造成整个系统不可用。

没有数据丢失
可用性降低

txt

autonumber
Client ->> Master: 
Master->>Slave.1: 
Master->>Slave.2: 
Slave.1-->>Master: 
Slave.2-->>Master: BLOCK
Master -->> Client:

半同步复制

在同步和异步之间, 做一个折中, 看起来是一个不错的方案. 这就是半同步复制. 它要求master在应答客户端之前必须把数据复制到足够多的机器上, 但不需要是全部. 这样副本数够多可以提供比较高的可靠性; 1台机器宕机也不会让整个系统停止写入.

但是它还是不完美, 例如数据a复制到slave-1, 但没有到达slave-2; 数据b复制达到了slave-2但没有到达slave-1, 这时如果master挂掉了需要从某个slave恢复出数据, 任何一个slave都不能提供完整的数据. 所以在整个系统中, 数据存在某种不一致.

主接到写请求
主复制日志到从库
从库此时阻塞
如果1<=x<=n个从库返回ok，则客户端ok

高可靠性
高可用性
可能任何从库都不完整

txt

autonumber
Client ->> Master: 
Master->>Slave.1: 
Master->>Slave.2: 
Slave.1->>Master: 
Master ->> Client: 
Slave.2-->>Master:

多数派读写

为了解决半同步复制中数据不一致的问题, 可以将这个复制策略再做一改进: 多数派读写: 每条数据必须写入到半数以上的机器上. 每次读取数据都必须检查半数以上的机器上是否有这条数据.

在这种策略下, 数据可靠性足够, 宕机容忍足够, 任一机器故障也能读到全部数据.

Dynamo/Cassandra

客户端写入 $W >= \frac{N}{2} + 1$ 个节点
不需要主

$W + R > N; R >= \frac{N}{2} + 1$

容忍最多 $\frac{N - 1}{2}$ 个节点损坏

txt

autonumber
Client ->> Node.1: 
Client ->> Node.2: 
Client ->> Node.3: 
Node.1->>Client: 
Node.2->>Client: 
Node.3-->>Client:

多数派读写的策略也有个但是, 就是对于一条数据的更新时, 会产生不一致的状态. 例如:

node-1, node-2都写入了a=x, 下一次更新时node-2, node-3写入了a=y. 这时, 一个要进行读取a的客户端如果联系到了node-1和node-2, 它将看到2条不同的数据.

为了不产生歧义, 多数派读写还必须给每笔写入增加一个全局递增的时间戳. 更大时间戳的记录如果被看见, 就应该忽略小时间戳的记录. 这样在读取过程中, 客户端就会看到a=x₁, a=y₂ 这2条数据, 通过比较时间戳1和2, 发现y是更新的数据, 所以忽略a=x₁. 这样保证多次更新一条数据不产生歧义.

后写入优胜

最后一次写入覆盖先前写入
所有写入操作需要一个全局顺序，时间戳
高可靠性
高可用性
数据完整性有保证

是的, 但是又来了. 这种带时间戳的多数派读写依然有问题. 就是在客户端没有完成一次完整的多数派写的时候: 例如, 上面的例子中写入, a=x₁写入了node-1和node-2, a=y₂时只有node-3 写成功了, 然后客户端进程就挂掉了, 留下系统中的状态如下:

node-1: a=x₁
node-2: a=x₁
node-3: a=y₂

这时另一个读取的客户端来了,

如果它联系到node-1和node-2, 那它得到的结果是a=x₁.
如果它联系到node-2和node-3, 那它得到的结果是a=y₂.

整个系统对外部提供的信息仍然是不一致的.

paxos中通过2次原本并不严谨的多数派读写, 实现了严谨的强一致consensus算法.

W + R > N

一致性：

最终一致性

事务性：

非原子更新
脏读
更新丢失问题

https://en.wikipedia.org/wiki/Concurrency_control

从多数派读写到paxos的推导

一个假想存储服务

一个有3个存储节点的存储服务集群
使用多数派读写的策略
只存储一个变量i
i的每次更新对应有多个版本：i1,i2,i3...
这个存储系统支持3个命令
- get：读最新的i
- set<n>：设置下个版本的i的值为<n>
- inc<n>：对i加<n>，也生成1个新版本

命令实现

set：直接对应多数派写
inc：(最简单的事务型操作)

问题: 如果有2个并发的客户端进程同时做这个inc的操作, 在多数派读写的实现中, 必然会产生一个Y客户端覆盖X客户端的问题. 从而产生了数据更新点的丢失.

而paxos就是为了解决这类问题提出的, 它需要让Y能检测到这种并发冲突, 进而采取措施避免更新丢失

1c9a7e01b88e4cdc9cf99061d5a78ed

提取一下上面提到的问题: 让Y去更新的时候不能直接更新i₂, 而是应该能检测到i₂的存在, 进而将自己的结果保存在下一个版本i₃中, 再写回系统中.

而这个问题可以转化成: i的每个版本只能被写入一次, 不允许修改. 如果系统设计能满足这个要求, 那么X和Y的inc操作就都可以正确被执行了.

于是我们的问题就转化成一个更简单, 更基础的问题: 如何确定一个值(例如iⱼ)已经被写入了.

直观来看, 解决方法也很简单, 在X或Y写之前先做一次多数派读, 以便确认是否有其他客户端进程已经在写了, 如果有, 则放弃.

PAXOS ​

前言 ​

是什么 ​

有什么用 ​

分布式系统要解决的问题 ​

背景 ​

问题 ​

解决方案 ​

不太完美的复制策略 ​

主从异步复制 ​

主从同步复制 ​

半同步复制 ​

多数派读写 ​

从多数派读写到paxos的推导 ​