有不少对分布式系统感兴趣的同学问我:"Paxos 算法是最基础的分布式共识算法, 但是, 我看完之后, 似懂非懂. Paxos 到底应该如何进行工程落地呢?"
业界对 Paxos 算法有着非常高的美誉, 一方面是因为 Paxos 的开创性, 更多的原因, 至少我所知道的, 许多人之所以赞美 Paxos, 主要是因为"看不懂". 说看不懂似乎不对, 许多人有时觉得自己懂 Paxos, 有时觉得不懂, 今天懂, 明天不懂, 但是必须懂. 要命的是,没法落地, 即使看懂了学完了, 一行代码也写不出来, 写出来了, 代码也没实际意义, 说句俗话, 就是"没啥卵用".
回复那些对分布式共识算法(Consensus)和分布式系统感兴趣的同学的话: Paxos 的落地就是选主(Leader Election)和日志复制状态机(Log Replicated State Machine). 也就是我一直说, 不想再说, 但又不得不再重复一次的话: 就是 Raft 做的那样!
@ideawu: 过去所有的 Paxos 实现, 都是 Raft 所总结的样子. 现在很多 Paxos 实现, 都是按 Raft 说的样子来做. 未来所有的 Paxos 实现, 最终都会实现成 Raft 的样子.
选主(Leader Election)
有些初学者一听到"Leader"一词, 马上情绪就上来了, 说什么"Paxos 是无主的(Leaderless), Paxos 是多主的, Paxos 不需要 Leader!"
且听我仔细分析. 选主分成两种:
- 显式选主(服务端选主, 唯一 Leader)
- 隐式选主(客户端认定 Leader)
我所见到的 Paxos 实现, 很多都是采用客户端认定 Leader 的方式, 例如, 客户端根据哈希算法, 将不同的请求根据资源 Hash 取模, 路由到固定一个节点上. 所以, 不同的资源访问分散到不同的节点, 似乎是 Leaderless, 其实还是 Leader Based. 只要你认定一个节点是 Leader, 就是选主, 诡辩术没有意义.
隐式选主看起来有优点, 例如, 当某个服务器节点出故障后(或者客户端主观认为节点有故障), 客户端可以"立即"认定其它节点作为 Leader, 表面上没有服务中断的时间. 看起来好像是高可用的, 很牛逼.
事实上, 隐式选主的这个所谓的优点, 一点用处都没有, 反而带来许多不良后果. 隐式选主, 不同客户端的认知不一致, 因此经常出现不同节点针对同一个请求资源认定不同的 Leader, 造成所谓的"多主", 从而带来"活锁"(冲突)问题, 而且冲突无法快速收敛.
例如, 我所知道的某些采取隐式选主的用了 Paxos 算法的系统, 在集群增删节点或者偶尔网络抖动的情况下, "多主"冲突造成请求失败(Paxos 重试最多3次)的概率能达到 50%, 最终大量请求失败. 因为把选主职责交给了客户端, 导致冲突无法快速收敛, 即使增加重试次数也于事无补. 对于实际的生产环境, 用户无法使用服务, 运维人员收到的大量告警短信, 烦不胜烦!
显式选主的优势在于可控性强, 在集群增删节点之前, 通过定制选主, 将流量导到指定的节点, 远离故障点, 在后续的操作过程中可以放心运维操作, 实现系统平滑扩缩容. 当然, 显式选主也会偶尔出现多个客户端"误认"不同的 Leader 的情况, 但是, 误认的情况十分罕见, 而且这种错误可以快速收敛, 例如几毫秒(1 个网络 RTT).
显式选主的劣势在于, 在出现集群故障时, 较难及时发现并重新选主. 不过, 已经有大量的成熟的方案解决这个问题, 主导思想是客户端启发式选主.
见: 分布式系统Redirect和Proxy的区别 - ideawu.net
根据实践经验, 分布式系统增删节点操作非常频繁, 因为这是动态调度资源的手段, 显式选主, 可以让操作过程完全平滑, 没有任何请求失败. 而 Leader 故障较为罕见, 结合客户端启发式选主策略, 可实现 100% 高可用 - ideawu.net.
日志复制状态机
Basic Paxos 解决了一个实例的共识问题, 但它要求读即是写, 而且没有解决工程实践上的数据更新问题(实例共识之后的状态不可改变). Multi Paxos 引入了日志复制状态机概念, 但没有完备地定义什么是日志复制状态机. 但至少有一点是非常肯定的:
To guarantee that all servers execute the same sequence of state machine commands... - Leslie Lamport, [Paxos Made Simple]
也就是说, 严格按顺序 Apply 日志才是复制状态机, 乱序 Apply 不是日志复制状态机.
严格按顺序 Apply 是线性一致性的基础保证, 这也是"线性"一词的来源. 如果乱序 Apply, 虽然能确保离散的对象达成共识, 但这些对象之间的因果逻辑关系将无法达成一致. 例如, 对一个变量先 incr 后 set, 和先 set 后 incr, 得出的结果是不同的(不一致的).
这种多个操作之间的顺序依赖关系, 对外表现出一致性. 所以, 偶尔也能听到"外部一致性"一词.
工程上的读操作被认为不应该写任何数据, 理论上的日志复制状态机, 把读操作放在和写操作同等的地位, 也即加入日志序列中, 以实现操作串行化. 但是, 状态机的 Apply 进度本质上是逻辑时钟, 围绕其可以做工程优化, 让读操作不产生或者修改数据. 主要的技术是 Lease(租约, 带有时间期限的强制共识约定), 和 Read Index(围绕逻辑时钟通信交换共识).
Paxos 性能优化误区
《庄子 - 齐物论》：狙公赋芧，曰："朝三而暮四。" 众狙皆怒。曰："然则朝四而暮三。" 众狙皆悦。名实未亏而喜怒为用，亦因是也。
性能优化的最大误区, 是片面理解 RT(Repsonse Time, Latency)和性能之间的关系, 从而花费大量精力去裁减关键流程, 最终代码过度复杂, Bug 频出.
误区1: 不等 Apply 就返回响应
大部分的 Paxos 学习者, 往往把 Chosen/Commit 之后返回响应给客户端作为优化手段, 它们的依据是"异步地" Apply 可以减少 RT. 事实上, 大部分的写操作都需要等 Apply 之后才能知道结果, 如果还没有 Apply, 就在 Chosen 时返回响应给客户端, 除了凭空捏造响应, 我没看出他们能做什么正确的事. 例如一个 Incr 操作, 如果没有 Apply 进状态机之前, 如何把结果(也即累加之后的值)返回给客户端? 真是莫名其妙.
Apply 是关键流程, 不能被裁减, 只有极其特殊情况才能小心地进行裁减. 如果要裁减, 必须花费大量成本, 同时设置繁琐的屏障避免误用. 通过偷工减料, 把关键流程放到所谓的"异步"操作中, 只是朝三暮四的做法, 与猴子无异.
误区2: 乱序 Apply
Paxos 学习者往往极度排斥串行化, 过度追求所谓的"异步"和"并发", 因此, 对日志复制状态机严格按顺序 Apply 的要求非常抵触, 并且相互鼓气, 最终形成了非常顽固的错误理念.
正如前面分析, 顺序(串行化)才是日志复制状态机, 乱序不是日志复制状态机.
能否乱序 Apply 取决于上层应用, 但底层要不要提供顺序保证, 就跟选择 TCP 还是 UDP 一样. TCP 提供顺序(流式)数据, UDP 提供可能乱序的数据. 但事实证明, TCP 的流行度远远高于 UDP, 因为, 顺序才是普遍的, 乱序是异常的.
Paxos 所谓的乱序 Apply(违反 Multi Paxos), 虽然能减少某几个请求的 RT, 但是, 不仅无法保证正确性, 而且对系统的平均 RT 和整体吞吐量没有任何影响.
Loading ...