日志复制状态机模型是 Raft 协议里的一个基础概念, 用于保障多副本一致性. 这个概念并非 Raft 独创, 而是由 Raft 具体总结和推广的, 在 Raft 之前, 像 MySQL 的 binlog 等等, 都是广义的日志复制状态机模型.

采用日志复制状态机模型的系统, 把多副本一致性问题分解成两个部分(模块), 第一部分是日志本身的一致性, 第二部分是状态机(例如数据库引擎)的数据一致性. 这两个系统模式是独立运行的, 它们之间的通信(Apply)也是异步的. 由此带来了广义的可靠通信问题: 有序, 最终到达(不丢包), Exactly Once(去重).

为了解决可靠通信问题, 系统至少需要保存 Apply 进度. 但是, 由于微观上"保存进度"和"Apply 日志"是两个独立的操作, 如果系统在两个操作之间宕机再重启, 就会导致断点位置的日志被 Apply 两次(去重问题, 如果先 Apply 再保存进度), 或者没有被 Apply(丢包问题, 如果先保存进度再 Apply).

要解决这个问题, 必须把 Apply 和保存进度两个操作作为一个完整的不可分割的整体, 就跟数据事务一样, 具有原子性, 要么同时成功, 要么全部失败, 这样就解决了去重和丢包问题. 如果状态机是 LevelDB 引擎, 那么我们可以利用其 WriteBatch 功能.

仔细借鉴 WriteBatch 的实现原理, 也许我们可以扩展思路, 把 Apply 进度保存在状态机之外, 不侵入状态机.

事务原子性的本质, 可以简单概括为: 增加 commit point, 重启时回滚.

针对两个独立对象, 我们增加一个单点标记(commit point), 当读取到对象时, 去检查单点标记的状态, 以判断对象是否有效, 如果无效则丢弃(读修复, 回滚). 正应了那句话:

All problems in computer science can be solved by another level of indirection.

到了这里, 我们不要求状态机(数据库引擎)提供原子性保证, 但要求它提供回滚能力. 回滚能力必然伴随着进度, 也即序列号, 引擎内部也要有全局递增的序列号.

我们把 Apply 进度 {raft.log_index, db.seq} 保存到独立的进度文件, 如果系统重启, 从进度文件中读取最新的 db.seq, 然后要求 db 回滚, 甚至进度文件也能回滚. 这样, 就保证了 Raft 日志 Apply Excatly Once.

另外, 再提一句"读修复"技术, 这项技术的应用非常广泛, 例如 Paxos 的核心之一就是读修复. 纯朴的思维认为所见即所得, 读就是只读一个地方, 读到什么就是什么, 不应该再读其它地方, 特别最重要的是, 读操作不应该修改数据. 但是, 如果技术思维想进阶, 一定要抛弃纯朴思维, 拓展到多版本, 多副本, 读修复, 读即是写.

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

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

有一个说法比较经典:

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 »

一种区分读写操作的对工程实践友好的分布式一致性协议

摘要

流行的共识算法如 Paxos[1] 和 Raft[2] 被广泛地应用于分布式系统中, 用于实现一致性. 但是, 这些算法本质上并不区别读和写操作, 因而给工程实践带来了极大的困扰. 这种困扰导致在具体实现时, 开发者往往基于性能优化方面的考虑, 对这些算法做没有经过理论验证的更改.

我想在区分读写操作的前提下, 设计一种对工程实践友好的分布式一致性协议, 能适应读多写少或者读少写多等不同场景的需求. 这个分布式协议基于 Quorum 机制, 采用 2PC 策略和复制状态机模型, 适用于有强一致性要求的分布式数据库系统和其它分布式系统.

Continue reading »

首先, 获取"集群"的 ReadIndex. 注意, 不是某个节点上面的某个状态, 而集群的多个节点共同确定的一个变量. 这个变量如何获取, 下面说明.

func GetClusterReadIndex(){
    foreach(peers as peer){
        i = peer.rpc_GetLastIndex();
        ret = max(ret, i);
        if(recv_majority){
            break;
        }
    }
    return ret;
}

获取至少半数以上成员的 LastIndex, 也就是每个节点持久化的最新一条日志的 index. 一条日志只要在一个节点上被持久化, 那么这条日志要么被集群 commit, 要么被覆盖之后再 commit, 没有其它的选项.

由此可见, ReadIndex 不一定已经被 commit, 但一定会被 commit, 最终也将会 apply. 所以, 拿到集群的 ReadIndex 之后, 我们只需要等, 等它被任意一个节点 apply 即可.

ReadIndex = cluster.GetReadIndex();
while(1){
    foreach(peers as peer){
        if(ReadIndex <= peer.LastApplied()){
            return peer.GetValue();
        }
    }
}

不断地重复轮询全部节点, 如果谁 apply 了, 就以谁的值为准. 还有一种方案, 那就是等本地的状态机 apply, 这样避免网络传输.

ReadIndex = cluster.GetReadIndex();
while(1){
    if(ReadIndex <= self.LastApplied()){
        return self.GetValue();
    }
}

还有一种优化方案, 是客户端判断. 客户端请求多数节点, 获取 max pending 和 max committed, 如果 committed 大于等于 pending, 那么取对应的 value. 如果 pending 大于 committed, 说明集群中有"脏写"(未决的数据), 客户端要做的就是等待. 如果不等待, 那就做 Paxos phase 2 所讲的"读修复".

没什么玄幻的, 道理非常简单: 第一步, 查询集群的状态; 第二步, 根据状态判断没有脏数据就返回, 有的话要么主动修复, 要么等待; 这是一致性的基础, 也是一致性的全部.

在优化之前, 我们先分析原始的能保证正确性的做法是什么, 然后分析问题在哪, 最后再讨论怎么优化.

* Paxos 读流程: 针对要读取的对象, 在其操作序列中追加一条 read 共识.
* Raft 读流程: 在 Raft 日志序列中写一条 read 日志, 等 commit.

两者其实是一样的, 都是复制状态机模型, 都要复制一条 read 日志, 然后 apply 之后才能返回结果. 问题在哪呢? 很显然, 大部分系统是读多写少, 每一次读都需要达成共识, 而达成共识的过程无论是 Paxos 还是 Raft, 成本都太高了 - 网络写 IO, 磁盘写 IO. 既然是读操作, 能否只用磁盘读 IO 就行了呢? 这个想法就是优化的方向.

一致性算法的基础是, 无论客户端是什么操作, 集群都要在全部或者部分成员参与的情况下, 达成新的共识. 优化的思路是在某些情况下, 不用每一次操作都达成新共识. 怎么做到? 1, 如果全部成员都是一致的, 客户端读操作就没必要生成新的共识. 2, 读操作不主动生成新的共识, 而是等待其它客户端写操作生成新的共识.

Linearizable Paxos Quorum Read

流程分为: Quorum-read phase, Rinse phase.

1. 读取半数以上节点的 accepted_index, 记录其中 max_accepted_index
2. 等待, 直到任意一个节点 max_accepted_index 被 apply/execute, 以那个节点上的数据返回给客户端

重要的地方就是"等待", 如果没有等待, 就会变成简单的 Quorum Read, 是错误的. 这个读优化算法的正确名字应该是: 带有停止等待的多数派读. 区别于传统意义的"读多数派中的最新者". 其实叫"Read Index"更准确.

这里面其实有个问题, 因为 Paxos 是消极的, 如果没有外界触发, 这个等待可能永远也不会返回.

Raft Read Index

Leader 的数据就是可以返回的, 唯一的问题是, 某个节点可以错误地自认为是 leader, 所以要先确认自己是不是 leader.

1. 自认是 leader 的节点询问半数以上节点自己是不是 leader
2. 如果确认自己是 leader, 等状态机 apply 到大于等于 commitIndex(这个时刻就是 readIndex) 后, 读取状态机的结果返回
3. 如果发现自己不是 leader 怎么办? 找到正确的 leader, 获取 readIndex, 然后等待自己的状态机 apply 到至少 readIndex.

因为 Raft 是积极的, 所以AppliedIndex 一定会最终等于 commitIndex, 即使没有外界触发也不会永远等待.

无论是原始在往日志序列中追加日志, 或是 Linearizable Paxos Quorum Read 或 Raft Read Index, 本质就是插入一个同步点(memory barrier), 确保这个同步点和之前的日志已经 apply.

业界对用 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: 工程上优化并不是唯一的考量因素.