本期关键词：Paxos、InfluxDB IOx、16bit 音乐
Paxos Made Live - An Engineering Perspective
在第 2 期曾经介绍过 Raft 算法，作为目前可能最成功、影响最深远的共识算法，Paxos 是一个不可能绕开的话题。Paxos 的作者是大名鼎鼎的 Leslie Lamport，大神目前在微软研究院工作。Paxos 的诞生起源于 The Part-Time Parliament 这篇论文，虽然论文是 1998 年发表，但是早在 1990 年就已经提交过，关于这段有趣的历史可以从 Leslie 的个人网站上了解。
因为 The Part-Time Parliament 过于晦涩，2001 年 Leslie 又发表了 Paxos Made Simple，尝试用更直白的叙述来解释什么是 Paxos。但如果你是第一次了解 Paxos，这篇论文其实也不是很好理解。本期并不是零基础 Paxos 入门指南（还没有这个资格），但会尝试让你尽量多地了解 Paxos 以及它的众多衍生者。如果你只是想在工程中实际使用一个共识算法，建议直接了解 Raft。
这篇 Paxos Made Live 来自 Google，2007 年发表，正如副标题所说，是一篇从工程实现角度来介绍 Paxos 的论文。Leslie 的论文更专注在从数学角度进行理论推理和论证，而如何在工程上实现 Paxos 并没有细讲（关于这一点 Raft 的论文中也有所提及）。因此本篇论文就显得格外珍贵，可以帮助有兴趣实现 Paxos 算法的人了解背后的「艰辛」。
为什么 Google 要自己实现 Paxos 算法还得追溯到 GFS（第 8 期曾经介绍过）和 Bigtable 的设计，这些分布式系统的实现都依赖分布式锁这个特性，因此 Google 的工程师们设计了 Chubby。Chubby 也是一个分布式系统，主要作用就是提供分布式锁功能以及存储少量的元数据。正如 Google 的很多系统，Chubby 的设计也影响了后续很多开源项目（如 ZooKeeper、etcd），以后可以再详细介绍。
第一版 Chubby 是基于某个第三方的商用容错数据库实现的，论文中称之为 3DB（感觉是在影射 Oracle 的 DB2）。这个数据库有很多与数据复制有关的历史 bug，它的复制机制也不是基于一个经过严格论证的复制算法实现。因此 Google 的工程师们才决定基于 Paxos 来重构 Chubby。
Chubby 的架构很简单，所有数据复制都会通过最底层的容错日志复制来实现，而如何复制这些容错日志即是 Paxos 算法要完成的。本篇论文简单介绍了完成一次 Paxos 算法（Paxos 的术语是一个「instance」）的流程：
- 从所有节点中选举一个 coordinator（在 Paxos 中这个过程中涉及的请求被称作「Prepare/Propose」及「Promise」）；
- Coordinator 选择一个值并通过一个消息广播给所有节点，这个消息（或者请求）被称作「Accept」，其它节点可以选择确认（acknowledge）或者拒绝（reject）；
- 一旦大多数节点确认了这个消息，那么就可以认为一致已经达成，coordinator 会再广播一个「Commit」消息给所有节点。
严格意义上来说上面的这段描述并不完全匹配 Paxos 原始论文的步骤和术语，但大体上是一致的。是不是看起来很像 Raft？Paxos 和 Raft 最大的不同其实在于并不存在一个中心的 leader（注意 coordinator 并不等价于 leader），上面这个流程是任意一个节点在任何时候都可以发起的（发起者被称作「Proposer」），但是每一轮流程都会有一个唯一的「编号」，Paxos 通过限定这个编号是有序的来保证数据的一致性。去中心化的一个好处是没有单点问题，缺点也很明显，每次数据更新都要完整重复整个流程，写性能是很差的。
因此有了「Multi-Paxos」这个优化方案，注意它和第 2 期介绍过的 Multi-Raft 没有任何关联。各种资料显示 Multi-Paxos 这个概念似乎最早出自「Paxos Made Simple」这篇论文，但你在其中并搜不到 Multi-Paxos 这个词汇。Multi-Paxos 的核心思想是如果一段时间内 coordinator 是不变的，那么其实可以省略第一阶段的「Prepare/Propose」消息，直接进入第二阶段的「Accept」，大大减少需要通信的请求量以及处理时延。那要如何保证一段时间内 coordinator 不变呢？熟悉 Raft 的同学可能要说了那就先选举一个 leader，只要 leader 存活就代表 coordinator 不变。Paxos 的做法是并不需要真的「选举」一个 leader 出来，前面也介绍过了，Paxos 并不存在一个真正意义上的中心化的 leader，coordinator 是可以随时被改变的。因此要做的就是除 coordinator 以外的其它节点在一段时间内「拒绝」新的 proposer 发起的「Prepare/Propose」请求，这个「固定」的 coordinator 就这样无形地被产生出来了，并不需要刻意去「选举」。
Multi-Paxos 只是实践 Paxos 算法中的一个挑战，本篇论文还列举了其它一些。
例如该如何检测和应对磁盘损坏。因为 Paxos 的状态需要持久化到磁盘上，当磁盘损坏时有可能出现两种现象：文件内容产生了变动，或者文件无法访问。为了应对第一种现象，Chubby 保存了每个文件的 checksum，因此当文件内容有变动时可以及时发现。对于后者，因为无法区分文件无法访问是因为磁盘损坏还是因为这是一个新的副本节点（此时磁盘是空的），Chubby 选择当新的副本节点正常启动以后在 GFS 上保存一个标记符（marker），因此当出现文件无法访问且标记符已经存在，就表示一定是因为磁盘损坏导致。为了自动修复破损的文件，节点会作为一个「非投票成员（non-voting member）」加入 Paxos（Raft 也有这个概念），在追赶上完整数据之前不会处理「Prepare/Propose」以及「Accept」请求。
再比如该如何优化读请求的性能。为了保证读的强一致性，每次读请求也需要完整走一遍 Paxos 的算法流程，对于读请求占比高的场景开销很大。一种变通的解决方案是「主节点租约（master lease）」。在一段时间内有且仅有一个节点能获得主节点租约（这个节点可以称作 master），其它节点将不能处理请求，因此获得主节点租约的节点将持有最新的数据，它可以直接在本地完成读请求的处理而不用发起一次完整的 Paxos 算法。既然叫做租约那一定有时间限制（timeout），master 会定期续约以保证租约可以长期有效，在实践中 Chubby 系统的一个租约可以最长保持数天。Master 的超时时间比其它节点稍短一些，这是为了防止时钟漂移（clock drift）。以上描述看起来都很像 Raft，只不过在 Raft 中主节点被叫做 leader，前面讲到的 Paxos 没有中心化 leader 的「优点」似乎也不复存在。
讲完了实践 Paxos 的挑战，接下来把关注点放在如何实现一个健壮（robust）的算法。Paxos 的核心算法看起来很「简单」，可能用很少的代码就能实现，但是如何确保实现的算法是可靠的呢？Google 的一些经验值得借鉴和学习。
因为容错算法很难准确表达，即使是用伪代码也是如此。因此 Google 的工程师们设计了一种状态机描述语言（specification language），通过这个描述语言构建了两个状态机，最终用于描述 Paxos 的核心算法。同时有一个特定的编译器来将这个描述语言翻译成 C++ 代码，翻译的过程中还能自动生成一些日志以及辅助调试和测试的逻辑。有了这个描述语言，1 个屏幕就能完整展示 Paxos 的核心算法，可见语言足够精简。为什么要如此折腾搞这么一套东西呢？Google 的工程师们相信当需要对核心算法做调整时这种方式能更有效率，并举了一个实际的例子，他们曾经需要将成员关系（group membership）的状态机从 3 个状态改成 2 个，仅仅用了 1 个小时就完成了逻辑变更，以及用了 3 天来完成测试调整。如果没有这套东西，整个核心算法实现是跟其它逻辑混杂在一起的，可能就没有这么快完成了。
验证一个系统是否可靠的另一个好方法就是「测试」。Chubby 从设计之初就确保整个系统是可测试的（testable），所有测试都有两种运行模式：安全模式（safety mode）和在线模式（liveness mode），当运行在安全模式时允许系统不可用，而在线模式不允许。每个测试都会先运行在安全模式并随机注入一段时间的故障，然后等待系统自动恢复，再切换到在线模式去验证系统是否已经处于正常状态。注入的故障类似于：网络中断、消息延迟、超时、进程崩溃、文件损坏、让某个节点宕机、让某个节点与其它节点断开一段时间的连接、让一个节点假装它不再是主节点等等。这个测试方法跟现在很火的「混沌工程」非常类似，但是比 Netflix 提出整整早了 4 年。
论文的最后指出了目前容错算法领域的一些「问题」，比如 Paxos 理论知识和工程实践中的巨大鸿沟、没有合适的工具来帮助实现一个容错算法、对测试没有足够的重视。相比之下编译器领域就好很多，虽然编译器的理论知识也很复杂，但是已经积累了众多工具来帮助工程师进行日常开发（例如 Yacc、ANTLR、Coco/R）。众人拾柴火焰高，前人的经验不断通过各种工具沉淀下来，后来者的开发效率自然会提高不少，也能避免很多已知的错误。
时至今日，不管是 Paxos 还是 Raft 在工程上都有了各种各样的实践，实现一个容错算法已经不再像以前一样困难重重或者遥不可及，CS 专业的分布式系统课程也开始教授各种容错算法，变成了一种专业基础知识。
Paxos 理论介绍
这是一个介绍 Paxos 的系列文章，发表在「微信后台团队」的公众号，文章发布时间是 2016 年，如果你回看那段时间这个公众号的文章，会发现微信刚刚开源了 PhxPaxos 库。这是一个由微信后台团队自研的 Paxos C++ 库，之后开源的 MySQL 集群 PhxSQL 即是基于这个库开发（微信开源了一系列以 Phx 命名的项目）。这一系列的文章即包含了 Paxos 的基础理论介绍（可以作为 Paxos Made Simple 的补充），也类似前面介绍的 Paxos Made Live 一样包含微信团队在 Paxos 工程实践中的宝贵经验。作为中文领域介绍 Paxos 且来自一线工程师的内容，值得一读。
Paxosmon: Gotta Consensus Them All
Paxos 起源于 The Part-Time Parliament，但并没有止于此。在 Paxos 诞生后的近 30 年间，众多学术界的研究人员围绕着 Paxos 进行了各种理论和实践上的探索，这篇文章按照时间线梳理了各种 Paxos 算法的「变种」，并总结了每种算法的优缺点。这其中包含如 Multi-Paxos、FastPaxos、Multicoordinated Paxos、SPaxos、Ring Paxos、Flexible Paxos（第 10 期也介绍过）等等各种你可能从来没听过的 Paxos 算法，虽然这其中的每个算法不一定都能直接应用在工程中，但对于了解 Paxos 算法家族的发展历史来说很有意义。
Announcing InfluxDB IOx: The Future of InfluxDB Built with Rust & Arrow
每个服务端开发者对于 InfluxDB 应该都不会陌生，作为可能是最流行的时序数据库（TSDB）之一，是每个公司都会拥有的基础设施。这篇文章来自 InfluxDB 创始人 Paul Dix，发表时间是 2020 年 11 月。同样是 11 月，倒回到 7 年前，Paul Dix 首次对外公开了 InfluxDB 项目。InfluxDB 的核心数据模型可以理解为 tag 和 field。Tag 是可索引的字段，即能够用于过滤查询，常见的 tag 如主机名、请求类型等，tag 的限制是不能将某个有大量取值的字段作为一个 tag（比如用户 ID），否则对于 InfluxDB 来说会造成负面影响。Field 是具体的数值，不可索引，也没有类似 tag 的取值限制。随着 InfluxDB 的应用越来越广泛，这个最初的数据模型设计也遇到了挑战，比如分布式 tracing 场景，每一条 trace 信息都会包含一个唯一的 ID，这个 trace ID 也会频繁用于数据查询，但因为 trace ID 的数量级过于庞大，当前的 InfluxDB 设计没法承载这种类型的数据。InfluxDB 诞生至今也没有提供开源版本的分布式实现（在早期版本中曾经有过，但是后来就没有了），分布式存储作为了 InfluxDB 商业版的一个重要特性，之所以这样选择也是为了维持 InfluxDB 开源版本持续开发的「无奈之举」。以上种种因素使得 Paul Dix 开始思考未来的 InfluxDB 会是什么样的呢，这篇文章即是他的思考结果。从文章标题里也能看到，核心关键词是 Rust 和 Apache Arrow（上一期介绍过），但 InfluxDB IOx 并不仅限于此。文章中关于开源软件协议的见解也很有意思，InfluxDB IOx 目前已经开源并持续迭代中。
MEGA DRIVE-黑色的 16bit 传奇 Vol.3 16bit 音乐探秘
这是一期播客，来自「竟然还能聊游戏」的机核，嘉宾是我非常喜欢的重轻老师，有兴趣的同学也可以听听他以前在机核的播客节目，推荐聊《西部世界》、吹哥（Jonathan Blow）、乐理的这几期。作为上一期聊 8bit 音乐的非正式续集，这一期也是从音乐的角度聊聊我们那些曾经的游戏时光（并没有聊具体的游戏）。如果你和我一样是从红白机时代经历过来的，那一定对于其中列举的各种场景深有感触，每一段作为示例的音乐也是听得热血沸腾。即使你没有经历过早期的游戏机时代，也会惊叹于那个年代音乐创作者（亦或音乐工程师？）的艰辛与才华，特别是 16bit 这一期的音乐，就算放到今天将之列为顶尖音乐的行列也绝不为过。