• 2021-07-24

    Paxos 算法实现和工程落地: 选主与复制状态机

    Views: 979 | No Comments

    有不少对分布式系统感兴趣的同学问我:"Paxos 算法是最基础的分布式共识算法, 但是, 我看完之后, 似懂非懂. Paxos 到底应该如何进行工程落地呢?"

    业界对 Paxos 算法有着非常高的美誉, 一方面是因为 Paxos 的开创性, 更多的原因, 至少我所知道的, 许多人之所以赞美 Paxos, 主要是因为"看不懂". 说看不懂似乎不对, 许多人有时觉得自己懂 Paxos, 有时觉得不懂, 今天懂, 明天不懂, 但是必须懂. 要命的是,没法落地, 即使看懂了学完了, 一行代码也写不出来, 写出来了, 代码也没实际意义, 说句俗话, 就是"没啥卵用".

    回复那些对分布式共识算法(Consensus)和分布式系统感兴趣的同学的话: Paxos 的落地就是选主(Leader Election)和日志复制状态机(Log Replicated State Machine). 也就是我一直说, 不想再说, 但又不得不再重复一次的话: 就是 Raft 做的那样!

    Continue reading »

    Posted by ideawu at 2021-07-24 17:54:11 Tags: ,
  • 2021-07-18

    Paxos 所谓的”幽灵复现”

    Views: 1255 | 1 Comment

    学习分布式一致性协议的程序员, 或早或晚都会面临所谓的"Paxos 日志幽灵复现"的问题. 就跟学习 TCP 总会遇到所谓的"拆包粘包"问题一样. 这类问题非常之经典, 人们对它们抱有非常顽固的似是而非的误解, 有时这些误解是对的, 但本质其实是错的. 原因就在于, 它们超过了人们的日常理解, 是一种违反常理的东西.

    比如 "TCP 粘包"问题, 你能说它不存在吗? 现象确实是这个现象, 但问题本质不是字面上的原因. "TCP 粘包"问题的本质, 是 TCP 对上层提供的是"流", 根本就没有"包"这个概念. 但是, 上层的常理认为, "TCP 应该提供报文服务". 常理如此强烈和普遍, 但 TCP 又拒绝满足常理需求, 所以造成了经典的误解.

    Paxos 所谓的"幽灵复现", 有多篇较流行的文章: 1, 2, 3.

    假设某个集群, 集群节点是 A, B, C, 用户在不同时刻访问不同的节点. 用上帝视角观察, 其内部日志序列是这样变化的:

    时间 访问点 A B C
    t0 A 1=NULL, 2=转账1 1=NULL, 2=NULL 1=NULL, 2=NULL
    t1 宕机 1=NULL, 2=NULL 1=NULL, 2=NULL
    t2 B 1=查询, 2=NULL 1=查询, 2=NULL
    t3 恢复 1=查询, 2=NULL 1=查询, 2=NULL
    t4 1=查询, 2=转账1 1=查询, 2=转账1 1=查询, 2=转账1
    t5 A 1=查询, 2=转账1, 3=转账2 1=查询, 2=转账1, 3=转账2 1=查询, 2=转账1, 3=转账2

    Continue reading »

    Posted by ideawu at 2021-07-18 13:06:29 Tags:
  • 2021-07-17

    什么是 Paxos 的日志空洞?

    Views: 1258 | No Comments

    Paxos 所谓的日志空洞, 在讨论 Paxos 和 Raft 对比时出现的频率非常高, 非常显眼. Paxos 的日志空洞是什么? "日志空洞"对线性一致性有什么影响? 我认为大多数人都对 Paxos 日志空洞有误解, 包括我之前也是.

    很多人认为 Multi Paxos 可以允许空洞, 但是 Paxos 论文提到:

    To guarantee that all servers execute the same sequence of state machine commands, we implement a sequence of separate instances of the Paxos consensus algorithm, the value chosen by the ith instance being the ith state machine command in the sequence.

    状态机必须严格按顺序执行(apply)命令, 所以, Multi Paxos 并不允许 apply 时出现所谓的日志空洞. 虽然会乱序 chosen(也即所谓的空洞), 但是, apply 一定是严格按顺序进行的. Apply 的时候, 如果不是严格按顺序的, 就不是日志复制状态机.

    但是, 因为必须严格按顺序执行日志序列, 所以, 即使 Multi Paxos 乱序 chosen 日志, 也不会影响外部一致性.

    Continue reading »

    Posted by ideawu at 2021-07-17 22:48:54 Tags: , ,
  • 2021-06-29

    分布式数据库系统的容错处理 – 100% 成功率, 超时和性能

    Views: 1119 | No Comments

    之前写过一篇文章, 介绍"可靠通信三原则". 对于一个分布式数据库, 如果想实现 100% 高可用(也即客户端的请求永远不会返回失败), 同样可以用可靠通信三原则中的重试理论和去重理论来解决. 但在实践上, 需要在成功率, 耗时(速度和性能)各方面进行取舍. 本文分享实际经验, 介绍什么样的选择是普适的, 各位可以参考.

    客户端访问数据库服务器, 发起大量的请求, 绝对不可能做到每一个请求都是成功的. 因为网络原因, 请求可能失败. 因为服务器内部处理冲突, 或者分布式节点间协调冲突, 都可能导致请求失败.

    所谓容错处理, 就是在遇到错误的时候进行重试. 因为错误必然发生, 只有重试才能消除错误的影响, 就好像 IP 层必然会丢包, 但 TCP 协议通过重传达到某种程度的可靠传输.

    某些实现了 Basic Paxos + 日志复制状态机模型的系统, 因为所谓的"Leaderless", 会产生大量冲突. 即使是使用 Raft, 在某些情况下意外发生选举, 也会导致请求冲突.

    Continue reading »

    Posted by ideawu at 2021-06-29 22:16:55 Tags: ,
  • 2021-06-27

    分布式数据库如何做到异地多活?

    Views: 2519 | 2 Comments

    前段时间写过一篇文章"分布式数据库系统如何做到平滑缩扩容?", 讲了分布式数据库在扩容(集群服务器开机关机)过程中, 如何保证服务 100% 不中断. 那篇文章主要是从客户端的角度去考虑问题, 正如该文章所说的, 一个分布式系统, 必须服务端和客户共同协作, 才能实现服务不中断. 本文从服务端, 也即狭义理解的"数据库系统"的角度, 分析一个分布式数据库系统是如何做到 100% 高可用的.

    注意, 高可用, 异地多活, 多主(Leaderless), 这些词汇, 本质上是指同一个东西, 都是指在单一节点宕机时, 客户端可以切换(切主)到其它节点访问, 或者说, 客户端在平时可以访问任意一个节点(多主) -- 切主多主是一回事, 只要可以做到足够快速地切主, 即使表面上一个系统是有 Leader Based 的, 那么它和 Leaderless 没有区别. 阅读本文之后, 相信你能加深对这些概念的理解.

    首先说一个定理: 只有强一致性的多副本系统, 才能异地多活.

    Continue reading »

    Posted by ideawu at 2021-06-27 23:24:48 Tags: ,
  • 2021-04-18

    再谈 Paxos 和 Raft

    Views: 1943 | No Comments

    我之前写过一些谈 Paxos 的文章[1][2], 特别是将 Paxos[3] 和 Raft[4] 进行了对比. 由于我更多的是站在工程实现的角度考虑两种技术的优缺点, 所以造成了不少读者感受到我有非常强的"贬 Paxos, 赞 Raft"的倾向. 不可否认, 从工程实现的角度, Paxos 的指导意义非常抽象且不直接, 所以我们必须""亲 Raft 远 Paxos".

    实际上, 许多人认为 PaxosRaft 不是同一层面的东西. 另一方面, 某种角度看他们又同一层面的东西, 当然要做比较. 所以, 我们在讨论这两种技术时, 要注意所设的场景和条件, 否则极易让人误会.

    有一个说法比较经典:

    Mike Burrows, inventor of the Chubby service at Google, says that “there is only one consensus protocol, and that’s Paxos” - all other approaches are just broken versions of Paxos. - [source]

    翻译便是:

    Google Chubby 的发明者 Mike Burrows, 说过"世上只有一种共识协议, 那就是 Paxos" - 其它的全是 Paxos 的残缺版本. - [来源]

    这个说法常常引申之后用来对比 Paxos 和 Raft, 然后把 Raft 归结为所谓的"残缺版本", 以获得无知而且猥琐的心理满足感. 根据来源网址, 似乎 Mike 只说 Paxos 是唯一一种共识协议, 后面那句轻浮的, 狡黠的, 稚儿指点江山似的说法 - 其它的全是 Paxos 的残缺版本 - 估计是文章的作者加上的, 并非 Mike 本话.
    Continue reading »

    Posted by ideawu at 2021-04-18 11:59:48 Tags: ,
|<<<1234>>>| 2/4 Pages, 24 Results.