• 2021-07-30

    为什么极少有开源的Paxos库?

    Views: 291 | No Comments

    你是不是也很奇怪, Paxos 既然被称为唯一的共识算法(分布式一致性算法), 是分布式系统的基石, 那么为什么极少看到开源的 Paxos 库呢? 反观 Raft, 有 etcd 开源的 go 语言写的库, 有 PingCap(tidb)开源的 Rust 语言写的, 还有百度, 阿里等等公司开源的各种语言的库. 既然 Paxos 那么牛逼, 为什么江湖中只有它的传说, 却从来没有人见过它的身影呢?

    原因很简单, Paxos(准确的说是 Basic Paxos) 是共识算法, 用于对一个实例的状态形成共识, 这个用途和工程上的一致性协议基本是金属铁块和汽车的关系. 工程师对 Paxos 最大的疑问经常是:

    • 什么是实例? 一整个 database 是一个实例吗? 一个 key 是实例吗?
    • 共识是什么? 是一个 key 对应的 value 吗? 形成共识之后就不能更改? 有什么用?

    所以, Basic Paxos 不是问题的解决之道. 有所谓的 Multi Paxos, Paxos 的论文中对这个模型(有人认为就是复制状态机)的定义和讨论非常不完善, 一千个人有一千种看法, 而且大多还是错的.

    Raft 提出了工程上的分布式一致性协议的核心本质: 选主和日志复制状态机.

    管你什么 Multi Paxos, Fast-Paxos, X-Paxos, ABC-Paxos, 通通都是日志复制状态机. 管你成员显式选主还是客户端认主, 通通都是选主.

    你说 Paxos 不需要 Leader, 那还不是要求客户端根据 Hash 算法认定一个节点作为 Leader? 你说你的日志序列支持空洞, 还支持乱序 Apply 日志(执行指令), 但两条指令执行的顺序不同必然导致结果不同, 结果(状态)都不相同, 你还谈什么一致性?

    做来做去, 还不是 Raft 所总结的那一套方法吗? - 就是选主和日志复制状态机!

    所以, 为什么没人开源 Paxos 库? 因为工程上要做的工作, Paxos 只占 1% 的工作量, 你把 1% 的微小工作包装成一个库? 有啥卵用? 没有人会用的, 因为这个库什么功能也没有, 什么问题也没解决(准确地说只解决了 1%).

    还要什么 Paxos 开源库? 要的是选主, 日志复制状态机, 成员变更, 就是 Raft 那个样子, 即使你心里面极度排斥 Raft, 但最终你还是会把一个 Paxos 库实现成 Raft 的样子.

    Posted by ideawu at 2021-07-30 00:24:42 Tags: ,
  • 2021-07-25

    Raft ReadIndex 有什么神奇之处?

    Views: 376 | No Comments

    其实, 工程上的一致性读, 本质是操作的先后顺序. 只要让读操作在某一个节点上发生的顺序, 在我们预想的那个写操作之后, 这时只依赖该节点, 就能保证一次正确的一致性读. 例如, 假设我们知道某次写操作的序号是 idx, 对应某条编号为 idx 的日志, 只要我们等某个节点 apply 了这条日志, 然后直接读状态机就可以了, 就能满足强一致性的定义.

    但是, 虽然可以要求客户端请求读操作时带上它所依赖的那次写操作的编号, 但工程上并不合理, 所以, 只能由集群节点自己找到那次写操作的编号.

    收到读请求的节点, 向其它节点发送一个请求, 询问最新的日志编号是多少, 如果收到全部节点的回应, 那么自然就知道了. 要求全部节点回应, 不能容忍少数节点宕机, 这种方案还需要优化. 其实, 超过半数回应就可以了.

    简单的说, 就是任何一个 Raft 成员, 无论 Leader 还是 Follower, 收到读请求时, 通过某些手段获知当前集群最大的 commit index, 然后等待自己 apply 等于或者超过这个 commit index 之后, 直接读本地状态机.

    大多数人可能并不知道, 即使是 Leader, 直接读本地状态机, 也是有可能违反"强一致性"的定义的. 因为, 除非站在上帝视角, 否则, 一个 Leader 节点只能是"自认为自己是 Leader", 既然是自认为是, 就有可能错认.

    所以, 如果读本地状态机, 就必须停止等待, 确保状态机已经 apply 了"那一条日志"之后才能读. 具体是哪一条日志? 前面说了.

    相关文章: PingCap - 线性一致性和 Raft

    Posted by ideawu at 2021-07-25 19:45:34 Tags:
  • 2021-07-24

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

    Views: 364 | 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-21

    分布式系统最重要的基础特性 – 平滑增删节点

    Views: 321 | No Comments

    对于一个多节点的分布式系统集群, 我们分析一下经常会遇到哪些问题:

    1. 因为出现网络分区或者节点关机, 客户端访问到了宕机节点
    2. 因为网络分区得到恢复或者节点启动, 客户端没有访问正确的节点
    3. 集群扩容/缩容(也就是增删节点)过程中, 客户端访问了错误的节点

    在分布式系统环境中, 客户端访问到错误的节点的情况一定会出现, 直接的后果就是请求失败, 所以, 这个问题是分布式系统高可用的核心障碍之一. 如果不解决这个问题, 一个系统一定不是高可用的.

    这3个问题, 其实是一个问题, 就是一个分布式系统, 能否支持平滑增删节点的问题. 在设计开发一个分布式系统时, 平滑增删节点必须作为一个必不可少的基础特性.

    Continue reading »

    Posted by ideawu at 2021-07-21 21:29:07
  • 2021-07-18

    Paxos 所谓的”幽灵复现”

    Views: 569 | 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: 538 | 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: ,
|<<<12345678>>>| 1/8 Pages, 47 Results.