Content Entry

Paxos 导读, 工程实现

任何分布式系统,都需要“锁”,用于持久化全局配置,协调分布式应用逻辑,保证所有系统高可用,它是分布式高可用系统的基石.

Paxos 算法用于实现分布式锁, 它在这个领域至关重要:
all working protocols for asynchronous consensus we have so far encountered have Paxos at their core. (Google Chubby Paper)

分布式锁的应用场景
http://timyang.net/distributed/paxos-scenarios

算法导读


中文,中文算法描述限于 choose value,有相当多翻译错误
http://zh.wikipedia.org/wiki/Paxos算法
英文,完整描诉
http://en.wikipedia.org/wiki/Paxos_algorithm

以下3篇是对算法的注解,帮助阅读


Paxos算法1-算法形成理论
http://blog.csdn.net/chen77716/article/details/6166675
Paxos算法2-算法过程
http://blog.csdn.net/chen77716/article/details/6170235
Paxos算法3-实现探讨
http://blog.csdn.net/chen77716/article/details/6172392
PaxosLease: 锁服务自身的 Leader 选举
http://blog.csdn.net/chen77716/article/details/6265394

已实现的项目


1. 最好的工程实现 Google Chubby
http://research.google.com/archive/chubby.html
周知的 Google GFS/MapReduce/BigTable 服务都基于 Chubby,它的论文必须要读!

2. 开源的,而且满足企业级稳定性的目前只有 ZooKeeper
http://zookeeper.apache.org
它用户众多,是目前最流行的分布式锁服务,基于 JRE, 提供 Java/C 两种API接入.

3. 其它类似的开源项目
OpenReplica: Python
http://openreplica.org/
Doozer: Golang (主分支长久不活跃,但 fork 分支有人持续维护)
https://github.com/ha/doozerd

Paxos 工程实现的几个要点


1. 多数派(Majority)
提案必须达成半数以上的 Accept, 及满足多数派(Majority), 这是全局状态的一致性的保证

2. 永远递增的 Proposal Number
永远递增的 Proposal Number, 如果无法 Majority, 则继续递增 Number 再提交, 如此重复直到 Majority.

3. 引入 Paxos Lease
Paxos Lease 负责为锁服务自身选举一个 Leader, 是为解决上面 Proposal Number 递增产生的活锁问题. Paxos Lease 本身也存在活锁,最简单有效的解决办法就是在每次提案间隔随机 Sleep().

4. 性能优化
引入 Paxos Lease 后, 提案递交由 Leader 单点负责,这虽然解决了活锁问题,但也使性能受限.
可以采用分区(Google Chubby 有介绍), 按照提案Key值 hash 均衡到整个Paxos服务集群, 这样不需要依赖全局 Proposal Number,只需要本地检查 Number 就可以递交提案, 这里需要处理本地主机异常离线而转换set/get主机的问题.

优化会使系统变复杂,这个地方有争议, 是否应该优化? 从 Google Chubby 定义来看,它的功能定位是强一致性,只持久化最重要最核心的少量状态信息,而不是高性能,大数据量,如果有系统存在这样的需求,则建议拆离解偶到子系统. 所以, 要注意优化子系统, 合理使用锁服务.

5. 并发写的全局一致性保证
当客户端并发修改一个 Value 时可能冲突,解决的办法是为每个 Value 记录 Number. 新的 Value 修改操作需要携带当前的 Number 和当前 MaxNumber, 如果修改成功将 Value 更新到 MaxNumber, 这是一次事务操作,同一个 Number/Value 只允许修改一次,要再次修改必须取新的Number再次提交, 配合 Majority 可以保证对 Value 修改的全局一致性.

6. 使用 Redis
自主实现 Paxos 锁服务可以尝试用 Redis 记录各种数据信息, 它的 expire, incrby, setex, pub/sub 功能可以为你节省大量编码时间,并且使代码量极度精简,同时它具备高性能,可以持久化数据到硬盘, 它绝对是数据结构的 “瑞士军刀”.

--EOF--

comments loading