idea's blog

业界对用 Paxos 还是用 Raft 争论(讨论)非常多. 我认为有争论是有好处的, 但要弄清楚为什么争论, 以及争论的点在哪. 否则, 上升到偏见或者信仰, 就没有意义了. 例如, 隔几天来一个"我为什么抛弃XX选择YY?", 或者借助"洋大人"之口(其实就是一个普通的外国程序员)说出什么"Why we choose XX over YY?", 那就非常可笑了.

我认为, 对 Paxos 和 Raft 的争论, 大多是基于软件工程上模块职责划分的见解不同, 也就是一个系统中, 共识模块(Paxos 和 Raft 都是共识算法)应该做什么功能, 加哪些限制条件.

Paxos, 我们首先要限制必须是 Basic Paxos, 否则没有争论的意义. Basic Paxos 本身是赤裸裸的, 限制少, 灵活, 因为它是基础中的基础. 也正因为太基础了, 所以脱离群众, 离真正实用太远. 这也是为什么这么多年, 业界没有一个真正意义上的开源的 Paxos 编程语言库.

Raft 是这么多年, 对 Paxos 工程实践的总结和提炼, 以学术研究(论文)的方式加以证明, 并提供了工程指导. 所以, 这才是为什么有那么多的 Raft 开源库, 而大家的代码结构又大同小异的原因. 因为, 幸福的家庭都是相似的, 不幸的家庭各有各的不同.

我总结一下, Paxos 和 Raft 的争议点在有哪些, 这些争议点是职责划分的问题, 你很快就会发现.

1. 单主还是多主

"单主"是很多人不选择 Raft 的原因(没什么所谓选择不选择 Paxos, Paxos 就是基础). 一是多写入点, 客户端可以随机选取任何一台服务器来接收请求, 所以, 客户端的代码非常简单, 配置服务器的 ip:port 列表, 用随机算法或者 round robin 算法选一台创建 socket 连接即可. 二是故障恢复时间, Paxos 把故障恢复隐含到了每一次请求当中, 不像 Raft 那样明确的划分职责, 独立出一个选主过程. 独立的选主过程占用独立的时间片, 阻塞正常请求, 所以理论上要增加故障时间.

但是, Raft 当然可以优化成在每一次请求都选主, 工程实践上没问题, 但是, 这不就成了 Basic Paxos 了吗? 所以, 没人这么做. 大多数情况下就是这样的, Paxos 加了限制就成了 Raft, 而 Raft 做了优化就变成了 Paxos. 向谁靠拢的选择而已.

2. 顺序提交还是乱序提交

这是争论最多的地方. 事实上, 一个系统必然有乱序(并发)的地方, 同时也会存在顺序(串行)的地方, 没有任何一个大型的系统只包含并发或者只包含串行, 不可能, 我在工程上没遇见过这样的系统. 问题就在于, 你想把并发(岔路口)开在哪?

举一个例子, 网络编程中, 你可以在 accept 之后就启动线程, 每个线程处理一个 socket, 也就是你把并发的岔路口开在了这里. 你当然也可以用 IO 多路复用(如 epoll), 在一个线程中顺序地(但不阻塞)地读取 socket, 然后在读完请求之后, 启动线程处理请求, 也就是, 你把并发的岔路开在了那里.

Paxos vs Raft 就是这样的例子, Raft 认为把串行的部分交给我, 然后你(状态机)再并发. 但是用 Paxos 的人认为, 关于是串行还并行, 应该由我(状态机)来决定, 共识算法没必要加这个限制. 孰优孰劣? 任何一个理性和聪明的人都能得出答案.

用 Paxos 的人, 希望自己把控更多的东西, 所以 Paxos 非常薄, 薄得几乎不存在, 也就没有所谓的 Paxos 库了, 因为它的职责太少, 以致于根本不值得独立成一个库. 用 Raft 的人相反, 把更多的职责加给 Raft, 不重新发明轮子.

所以, 通过一两个反例来说明 Paxos 好还是 Raft 好, 在技术上非常幼稚. 正确的说法是: 某个职责不应该交给这个模块, 因为某个职责交给另一个模块可以做一些优化. PS: 工程上优化并不是唯一的考量因素.

在讨论 Paxos 之前, 我想抛出几个包括我在内很多人都会提出的问题:

* 如何更新一个 key?
* 如何让两个数据库完全相同(最终一致)?

先不管最终一致性, 强一致性, 或者什么时间线性一致性顺序一致性. 我的需求是让两台或者更多台机器上的数据库的数据是完全相同的. 经过对隐晦的 Paxos 协议和其相关的资料的来来回回的阅读和理解, 我又一次得出了新的结论...

Paxos 用来确定一个 instance 的值, 一旦确定, 不可更改!

什么? 不可更新? 不可修改? 太违反常理了吧? 这样, 有个鸟用? 我今天终于在 stackoverflow 上看到了这个说法, 然后再回头阅读 Paxos made simple, 我不得不得出同样的理解. 所以, 我昨天"关于 Paxos 论文中的迷惑之处"的问题也得到了解答. 如果你把 instance 当作 key, 用 Paxos 来对 key 的值达成共识, 确实只能是一次性的, 确定之后你就不能再更新它的值了.

如果 Paxos 是这样, 那它几乎没有任何实践意义, 一个不能更新的 key 有什么用? 一个只能写一次的数据库? 问题就在于, 你把 instance 当做什么. 如果要更新 key, 你就不能把 instance 对应成 key, 你应该把 instance 对应成对这个 key 做的一次操作(一条 binlog)... 再看论文最后提到状态机, 这才发觉, 原来, Paxos 天生就是复制状态机模型. 所以, 那些 multi paxos 到底在扯什么鬼?

只要把 instance 对应成对整个数据库做的一次操作, 然后对多次操作指定顺序, 就是我们常见的 binlog 同步.

一致性分为访问一致性和数据一致性. 访问一致性, 是指从观察者的角度, 其访问结果是可预期的. 数据一致性是指从上帝视角看, 多个副本的数据是完全相同的.

Paxos 协议, 这里指的是原始(Basic) Paxos, 其本质是解决访问一致性, 并不解决数据一致性, 它不保证多个副本数据现在是(或者将来是)完全相同的, 它只是在可能不一致的多个副本上提供可预期(一致性)的服务. 这个说法不代表不能使用 Paxos 来保证数据一致性, 而是说, Paxos 的设计目的不在于此.

Raft 同时解决访问一致性和数据一致性. 使用了 Raft 协议的分布式存储系统, 既能提供可预期的数据访问服务, 也能在时间维度上保证多副本数据一致性. 例如, 在系统隔断外部输入的情况下(不再接受写请求), 经过一定的时间(一般从几毫秒到数秒)之后, 使用了 Raft 协议的集群内的多个副本的数据将是完全相同的.

Paxos 协议本身并不能保证系统级的数据的最终一致性, 因为它是基于外界触发的消极全量数据拷贝协议. 如果没有外界输入触发, Paxos 就不拷贝数据, 所以它是消极的. 当需要拷贝时, 它拷贝的是全量的数据, 如果你需要保证整个数据库在多台机器上相同, 你应该拷贝整个数据库, 这显然没有实际意义. 另外, 当拷贝结束时, Paxos 并不保证数据被拷贝到所有节点, 这是第二个消极. 所以, 仅仅使用 Paxos 协议的系统, 在隔断外部输入的情况下, 如果数据不一致, 那么过一百年, 多个副本的数据仍然不一致.

相对比, Raft 的数据拷贝是自动的, 不仅仅依赖外界输入触发, 还依赖时间触发, 所以, Raft 是积极的. 同时, 拷贝结束时, Raft 保证数据被拷贝到了所有节点, 从而实现所有副本是完全相同, 如果达不到这个目的, Raft 就不会停止(不达目的绝不罢休), 这是第二个积极.

前面说过, 你一定要区分就充分和必要. 所以, 我不是说用了 Paxos 就必须是消极的, 而是 Paxos 本身是消极的, 如果你用了 Paxos, 你自己要积极起来, 不能只依赖 Paxos. 例如, 你必须引入日志复制状态机模型, 避免全量拷贝. 另外, 你还必须引入超时重传机制, 主动积极拷贝. 为了优化, 避免读请求也要走完整的 Paxos 流程, 你还要引入 Leader. 天啊, 你在重新发明 Raft!

1. 值的选择

Paxos 论文提到, 发起 proposal(即 accept 类型的消息)时, 用的"值" v 是之前 prepare 时收集到的, 否则就是 any value.

这个说法其实非常具有迷惑性, 并导致了大量奇怪的说法. 如果用的是收集到的旧值, 那我(用户)要更新数据怎么更新?

所以, 大家实现 Paxos 时, 这里就变成了用的是用户请求的值回复自己发出的 prepare. 这其实违反了论文, 因为论文提到, 收集到的值必须是曾经 accepted 的值, 但是, 用户的请求还没有开始呢, 何来已接受?

另一个迷惑的地方是"any value", 很多人都翻译成"随机/随意选取一个值". 这属于不严谨. 怎么能随意呢? 选择哪个值的依据(算法或者逻辑)是确定的, 两个集群做了同样的操作, 一个选择 a, 另一个选择 b? 当然, 实际的意思并不是"随机", 而是"决定", 实践上, 就是决定使用客户端所请求的那个值(如果进度相同的话).

2. Proposal number

Paxos 要求每个节点使用不同的 number 来 prepare, 但是, 即使使用相同的 number 来 prepare 似乎也没有问题? 因为只有唯一的一个能 prepare 成功.

所以, 如果有人知道, 请告诉我, 两个 proposer 使用同一个 number 来 prepare 会导致什么问题? prepare 不就是要解决 number 分配的问题(同时交换最新值)的吗?

我们一般很喜欢把函数的参数定义为 const&, 这样即能传引用减少内存拷贝, 也能限定参数为 const 类型不可修改, 似乎很美好. 但是, 如果把对象的属性传给函数, 而对象又被删除时, 就会出错.

struct C
{
    std::string id;
};

class S
{
    C *c = NULL;

    void f1(){
        c = new C();
        c->id = "a";
        f2(c->id);
    }

    void f2(const std::string &id){
        delete c;
        c = new C();
        c->id = "b";
        printf("deleted %s\n", id.c_str()); // core
    }
};

当然, 理论上是写代码的人的错误. 但是, 这确实是一个大坑. 我相信, 这种 case 在实际中还是有不少的. 函数的编写者可能仅仅把参数当作一个无害的对象, 完全没有意识到, 参数变量是和某个要销毁的对象是绑定的. 但是, 又不能强制规定 string 类型只能传值, 然后期待编译器能优化 string 类.

真是坑.

我在遇到"接口与实现分离"这个编程领域的概念时, 感到非常模糊. 随着编程经验的积累, 才明白了"接口与实现分离". 用 Java 的程序员应该天天用到 interfalce 和 class, 不过, 即使是 Java 程序员, 可能偶尔也会违反广义的分离原则.

我最近接触到的一个违反"接口与实现分离"原则的例子, 可以分享一下.

RTT(round trip time)是一个非常重要的时间概念, 这会让程序变得很"慢". 例如:

func(1);
func(2);
func(3);

如果每一次函数调用要花 100ms 的话, 那么做完 3 件事要花 300ms. 有经验的程序员立即就做了代码"优化":

func([1,2,3]);

把函数参数改成数组, 一次传入 3 个任务, 利用了 batch 机制, 做完 3 件事也仅需要 100 ms. 看起来完美解决问题. 但是, 工程上这样做带来了缺点, 那就是改变了接口(interface). 这是一个经典的违反"接口与实现分离"原则的例子, 接口因实现而被迫改变.

如果函数执行是放在网络服务器上面, 而调用者是所谓的客户端, 一般的网络编程都是可以并发处理的, 例如在 3 个线程中调用函数. 这时, 接口改变之后, 反而没有用. 因为任务是不同的客户端发起的, 除非你增加一层抽象来积累请求. 这个优化看起来美好, 但是却增加了使用者的成本.

所以, 工程上应该由 func() 函数的实现者来做请求积累, 在函数内部把并发的请求合并成一个 batch, 减少 RTT.