idea's blog

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 »

很多初学者错误地认为, 像 Raft 这样的 leader based 的分布式协议不是 100% 高可用的, 因为"Raft 在选主的过程中, 不能提供服务". 初学者之所以存在这种错误认知, 完全是因为他们没有理论结合实践, 只略懂一点理论皮毛, 就胡乱引申导致的. 本文将在理论和实践结合的层面上, 分析这种错误认知.

首先, Raft 的选举过程并没有特殊的成本, 在局域网条件下, 一般只需要 5ms 的时间. 5 毫秒对于实用的分布式集群, 是微不足道的时间长度, 因为客户端对时间长度的认知是百毫秒级别的, 只要客户端在 5 毫秒之后重试[可靠通信三原则], 或者服务器先 Hold 住请求, 过 5 毫秒之后再处理, 对于客户端来说, 完全没有感受到服务不可用, 因此, 服务是 100% 高可用.

我认为, leader based 的集群, 最大的问题在于"何时发起选举?". 也就是, 如何能快速地发现当前集群失去了有效的 leader.

客户端可能发现集群无主, 但是, 我们不会把这个权限赋予客户端, 因为在 CS 理论中, 客户端是不可信的. 所以, 只能交由集群成员去发现集群是否需要发起选举.

Continue reading »

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

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

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

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

Continue reading »

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

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

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

Continue reading »

有一些文章, 包括 Raft 协议的论文, 已经从反例的角度解释了为什么不允许 Leader 直接 commit 前任的日志, 而是必须追加本任期的一条日志, 以达到隐式地 commit 前任的日志. 我想从 Raft 的几项原则的角度, 在逻辑上解释这个问题.

Raft 策略1: 节点的日志一旦 commit 便不可撤销

某个节点的一条日志, 一旦 commit 它, 那么就会对状态机造成不可逆的改变. 也许某些状态机有回滚功能, 但在 Raft 的架构中, 假设状态机不可回滚. 因此, 日志一旦 commit, 便不可撤销.

注意, 这里用的是"策略"一词, 表明这是人为规定的规则, 不是客观存在的定理.
Continue reading »

我还没有发现有人把 Raft 协议和区块链关联到一起讨论, 但是经过仔细分析, 穿透问题的本质之后, Raft 和区块链技术具有非常多的共同点. 可以整理出一个表格:

Raft 和区块链的不同概念, 其实往往对应到通用技术里面的一个共同的概念.
Continue reading »