动力

什么是分布式系统？

当数据量和计算量非常大时，我们需要将计算机规模化（Scale）。规模化有两个方向：竖直和水平。竖直指提升单个计算机的性能；而水平指将计算量分摊到很多的计算机上，通过增加计算机的数量来暴力破解，又称为分布式系统。在计算机发明的初期主要依靠竖直提升，而从上世纪进入互联网爆发期之后，由于数据量猛增，单机的性能跟不上数据量的增长，所以互联网公司开始探索另一条路：水平规模化，而其中尤以谷歌出名。比如谷歌创业初期购置了大量便宜的 x86 服务器来搭建分布式系统撑起谷歌的全球流量。

竖直化的例子包括计算机 CPU 缓存、指令预测、提升芯片执行指令的速度、提升 RAM 容量、提升硬盘读写速度等等，既有软件层面又有硬件层面，CMU 教材 CSAPP 里面提供了大量的例子，感兴趣的读者可以深入阅读此书；水平化的例子简单的比如使用 NGINX 进行负载均衡，复杂的有基于 Map Reduce 进行分布式计算、Redis 集群模式、ZooKeeper 或者 etcd 这样的分布式 KV 存储等等，更多是在软件层面做工作，熟悉 web 服务器编程的读者一定不会陌生。

MIT6.824 的内容就是围绕分布式系统做一次 T 型的学习，T 型顾名思义就是广度和深度兼具。课程选取了过去二十年最有代表性的分布式系统论文，此为广度；此外课程的编程作业选取了 Map Reduce 和 Raft 两个系统进行复现，这两个系统分别代表了分布式系统的两个方向：分布式计算和分布式存储。后者是现在分布式系统的难点和热点，所以 Raft 论文的复现完成度非常高，我在本课的时间投入上有大概八周，其中七周都是在实现 Raft，而且课程甚至对于 Raft 进行了拓展，实现了动态切片的功能。

为什么要学习这门课程？

首先如果要做服务器编程，剥离开任何软件都会遇到的问题比如管理复杂度、自动化等等，分布式系统是这个领域唯一独特且硬核的领域知识，如果绕过它服务器编程就没有什么独特性了，任何一个服务器领域有野心的程序员都应该起码入门这个领域；其次这个领域本身非常有趣，既需要优雅强大的算法（保证强一致性），又需要扎实的工程实现（保证性能和无 bug）。

此外学习任何一个领域，最恐怖的事情就是”不知道你不知道“，即缺乏眼界和品味。而这门课程无论是老师水平、程序精湛度、测试丰富度、工具链使用都是一流的，在这个过程中能够见到真正的高手如何做事，本身就是一种熏陶。比如谷歌的 Map Reduce 论文让我感受到了很强的溢出效应，之前工作中遇到的一些问题有了新的思路。

前置知识

有以下几点：

  1. 对于分布式系统想要做什么有个大致的概念，最好了解或接触过流行的一些分布式系统，比如 Redis 集群、ZooKeeper、etcd 等等。
  2. 熟练使用起码一种编程语言比如 Python、Java、CPP，不会 Go 的话可以快速掌握。
  3. 能比较舒服地从零实现两千行左右的系统。
  4. 最好有过复杂程序的 debug 经验，如果没有的话需要多投入一些时间。

其实它前置的领域知识相对比较浅，更多的是需要比较强的 debug 能力。

学完整门课程我用了两个月时间，平均大概每周五天，每天四小时浮动。

Raft 到底是什么

当我们想要实现一个分布式数据库时，最重要的就是实现强一致性和自动容错。也就是说在不断有机器崩溃的情况下存储的状态机在不同机器上值一定是相同的。Raft 利用了操作日志和 Leader 选举来实现这一点。Leader 作为和外部通信的机器，会把状态机以操作日志的形式传输给其他机器（follower），在 Leader 挂掉时，会从其他 follower 里面选举出来日志最新、同步程度和 leader 一致的成员作为新的 leader，这样就实现了上文所述的两点。当前比较流行的用来存储关键配置信息的 etcd 正是基于 Raft 实现的。

在选举时最值得注意的就是 figure8，这里咋一看似乎非常难理解，为什么日志已经同步过去了还不能 commit？抽象的概念最适合利用具体例子来理解，我们只需要以下的例子就能理解：

假设有三个 Server,列出其中每个日志 index 对应的日志的 term：

index 1 2 3 4 
-----------------
S1    1 2 4
-----------------
S2    1 2
-----------------
S3    1 3
-----------------

可以看到 term4 的 leader 是 S1，term3 的 leader 是 S3。假设 S1 成为 leader 之后，S2 落后很多，需要从 index1 开始一条条同步。index2 时 S1 看似已经把这条日志同步到了大多数，如果直接 commit 这条日志，之后 S2 挂掉了，那么 S3 按照选举的规则是可以选上的，index2 对应的日志就会被覆盖掉。

总结一下，就是在满足频繁选举、其中一个 follower 落后很多这两个条件的 edge case 中，S1 这个宝座没有坐稳的 leader 是随时有被颠覆政权的可能性的，而我们利用”只有 index3 也就是当前 term 的日志才能 commit“，来保证下一任不会把它 commit 的日志推翻掉。

此外我觉得最初论文给出的 Raft 五条性质是论文的基石，如果在阅读论文过程中不断联系这五条性质，建立深入的理解，对于掌握 Raft 有极大的好处。

编程作业

编程作业主要有四个，如果不是仔细阅读每篇论文甚至尝试自己复现的话，那么编程作业应该占课程投入的绝大部分。

  1. 复现 Map Reduce。线上运行的 MR 是有很多的性能优化细节的，还包括一个完整的可视化监控系统，但是作业复现的只包括最核心的逻辑，所以工作量较小，我连读论文加复现用了大概五天。

  2. 复现 Raft。这个 lab 包括了 Raft 除 Membership Change之外所有的特性，包括性能上的优化点。也是我最耗费时间的 lab。虽然自认为对于 debug 有心得，但面对分布式系统很独特的场景刚开始还是措手不及，足足耗费了一个月时间。还有可能是我没有读助教写的指引，回过头读指引发现自己犯的很多错误其实助教都讲了，总之中间不断优化和改进，终于渡过难关。但是也因为基于论文直接硬磕，锻炼了我的 debug 能力和对于 Raft 的理解度，导致接下来的两个 lab 格外顺利。

  3. 基于 Raft 实现一个 KV 数据库。因为深入理解了 Raft 和分布式 bug，所以用了五天时间波澜不惊地写完。中间如何同步化拿到异步的 Raft 同步结果是一个难点，我选择了 Condition Variable 加上高频轮询一秒钟来实现，回过头看单独使用轮询即可。网上有些同学使用 channel 来实现，我觉得对于 lab 来说有些过于复杂了。

  4. 基于 lab3 实现一个动态切片的集群数据库，即将不同的 key 映射到不同的集群，而且集群会在数据库运行时动态的加入或者退出。这样可以提升整个数据库的性能。大概花了八天实现。最大的难点主要是切片变更时怎么实现一次操作的唯一性，在并发的情况下不会写到多个切片里面。比如操作 A 写到服务器 S1 和切片配置变更（将 A 所属的切片从 S1移动到了 S2）同时发生，此时如果前者成功了但是客户端没有拿到正确相应，那么客户端会在 S2 上面再操作一次。避免这个问题的思路主要就是在变更时先把 S1 和 S2 要移动的切片关闭，等到移动完了再接受客户端的操作，而且值得注意的是在移动时也要把标记操作执行与否的状态值一并移动过去，在新的服务器 S2 上进行去重校验，防止一个操作执行两次。简单说就是通过一小段不可用时间加上同步去重状态机来实现操作的唯一性。和 web 服务实现无损发布有相似之处。

并发编程以及 channel 不是银弹

并发编程一直是我很好奇的一个领域，各个 talk 中都提到并发编程的困难，但是之前一直没有这个场景，这一次终于通过 6.824 狠狠过了一把瘾。Go 最常用的并发控制工具我全部用了一遍，包括 Lock、Channel、Condition Variable、Wait Group、Race Detector 等等。

值得一提的是在实现 Raft 时老师明确提出最好不要用 channel 来做并发控制，而我偏偏不信邪。因为 channel 一直是 Go 官方的一大卖点，而我之前一直对其懵懵懂懂，只是看了 Erlang 发明人的文章后觉得用通信方式来做并发控制很炫酷，所以决定全程使用 channel。

首先我看完了 Rob Pike 给出的 channel 教程，写得简洁有力，直击重点(https://www.youtube.com/watch?v=f6kdp27TYZs)；接下来我用 channel 改写了 Map Reduce，发现 channel 非常好用，甚至误认为是并发领域的银弹；但是接下来写 Raft 就陷入了一个大沼泽，到了后面寸步难行。

软件有一个大原则：永远不要轻易添加抽象层。一个新的抽象层意味着多个维度的重负，包括设计、编程程序、debug、沟通、自动化测试。比如我之前工作过的项目组喜欢把请求接到一个入口的服务，这个服务再把请求转发到其他服务，这个操作看起来多余但是不算费劲，但是因为接口太多，每个接口又字段很多，每次就算复制粘贴出了很小的 bug 也要查很久，而且这个服务没有调数据库的函数，后期再加工作量又很大，所以涉及数据库的校验甚至又会拖延到大后方的服务，然后把错误码和错误信息一层层回传，使得程序成了经典的烂泥球。编程的效率和乐趣也就在这种烂泥球的削减中所剩无几。

Raft 的特性就是有很多的后台线程更新同一个复杂的状态，包括多个 RPC Handler、心跳检测线程、通知外部 Raft 日志同步结果的线程等等，如果想要基于 channel 让多个线程去同步修改同一个状态，就要创建一个单独的线程（Event Handler）来修改状态，其他的线程每次修改状态都要通过 channel 来发送请求给 Event Handler，这个 Event Handler 再把结构返回；就像是起了一个毫无必要的服务，中间还要定义一个又一个的结构体作为请求和相应，而且这个线程作为中心后考虑 channel 阻塞的特性，还要考虑是否在 kill Raft 实例时没有线程泄露。

channel 让整个实现复杂度提升了很多，到了后面越来越不堪重负，所以我最后选择了用锁来改写。回过头看，channel 更适合的场景还是一个主线程发起各种子线程，从子线程拿到结果，尤其需要利用 channel 的阻塞特性。可以省略锁的使用，让程序简洁。Rob Pike 的视频里有大量这样的例子。如果遇到各种线程试图和一个后台线程通信，最好它们之间的交互复杂度有限，Raft 的例子里面交互的事件类型和交互方实在太多了，所以不适合使用 channel 来做。

channel 不是银弹，让我觉得是银弹的反而是 Go Race Detector。

Debug

2020 年工作时，我做了一个小实验：统计了一个月里每天的工作内容。本意是想提升自己的工作效率，通过测量来发现瓶颈，最后倒是真的得到了让我意外的结论：我花在 debug 上的时间远远超出我的预期。

现实和预期的差距有多大？我原本以为 debug 是饭后甜点，没想到它才是正餐。是的，很多时候 debug 时间是接近写程序的时间的。于是我花了很多心思在优化 debug 效率上面，最后导致我的工作效率大幅度提升，配合上我拒绝不合理加班的性格最后成为了项目组极少数到点下班的大熊猫之一。

而到了实现分布式系统，debug 的时间又在我之前的预期上提升了几乎一倍，大部分 bug 定位时间都是一小时起步的。也就是说 debug 时间是远远超过写程序时间的。有个拳王阿里的段子说”我做仰卧起坐从腹肌疼痛时开始计数“，那么我可以说 ”6.824 的 debug 从过了第一遍测试才刚刚开始“。因为分布式系统最难缠的 bug 都是不稳定复现的，我实现 Raft 不乏遇到运行一百次复现一次的 bug，复现一次就需要半到一小时。复现太耗费时间本身也是 debug 困难的重要原因。可以说 6.824 没有写完之说，只有”过了多少遍测试“。我的 lab1 lab2 过了一百遍测试，lab3 lab4 对于不同的单元测试大概有十到几十遍。

此外，分布式系统的 bug 还有一个特征就是信息量大。分布式系统典型特性是多个程序并发地更新同一个状态。所以当一个状态更新出问题时，它的上下文信息量非常之大，以至于需要额外写工具去解析日志，并且详略得当地阅读日志，否则就会”淹没在几百个线程更新一个结构体的十几个 field 之中“。于是结合之前工作总结出的 debug 方法，结合分布式系统的特性，我改进出了一套 debug 方法助我平安落地：

  1. 对日志建立一种协议（Protocol）。有没有协议的概念几乎是程序员入门的分水岭。”你要自动化“，这句话人人都会说，但是落实到手上就只有少数人能做到。建立自动化的基础就是建立具有一致性的协议。比如 Django 可以用很少的程序自动生成一套 CRUD 接口，就是因为这个接口是基于 RESTful 的。如果不同接口的 delete 方法分别通过 HTTP body 或者 URL 去传参，那么自动化生成无从谈起。回到 6.824，我为日志设计了一套格式，包括从零计数的时间点（时间线在分布式系统里面是非常重要的 debug 信息）、主题、日志的主体以及其从属的 Replica Group，后面是发生的事件和需要关注的状态值。具体是这样的： 000025 EXCUTE G100 S0 execute cmd: xWSuqTRyhVMWYGJFaNtQMAcF当具备了这个协议之后，就可以利用脚本做一些自动化。比如做 lab4 时不同 Replica Group 的不同 Server 日志混在一起非常难以阅读，我就可以轻松写出一个脚本来把不同 Server 的日志解析到不同的文件中。未来需要的话还可以为 VSCode 写一个插件对日志进行高亮。
  2. 对同一个事件建立一个全局唯一的追踪 ID。面对浩如烟海的日志，最重要的是把关心的日志找出来，其中最好的方法就是生成全局性 ID 串起一个事件。比如 Raft 选举时我就会把 RPC 发送方和接收方请求、响应、更新前后的状态值都用同一个 ID 关联。这样整个事件哪一步出了错一目了然。
  3. 千里之堤毁于蚁穴，利用单元测试缩短数据流。debug 最大的敌人就是巨大的上下文。一个很小的 bug 放入分布式系统的背景中，都会演变成一个复杂的毛线团。如果针对复杂状态的程序先用单元测试把 bug 早早暴露出来，那么后期做集成测试时就能节省大量的时间。比如我在 lab4 设计 join 和 leave 的算法，以及 Raft 设计日志的数据结构时都写了尽可能多的单元测试 case，为我后来过集成测试节省了大量时间。
  4. 抽象封装。把关联性很强的状态、程序抽象成函数或者方法是管理软件复杂度的核心。在实现 Raft 日志数据结构时我很自然地封装出了一个数据结构，把各种操作写成了接口，而不是直接读写内部的数据结构，这为我后续的 lab 节省了大量时间。最初的内部实现是很直接的数组，到了实现快照压缩日志时，发现 Go 的数组无法满足我的需求，需要在内部封装一些状态值来标记是否做了截断。因为做了封装，所以外部的调用方完全不需要改动，只是把内部改好，保证过了之前写好的单元测试，就得到了安全性的保证。
  5. Let it crash。在容易出错的地方加上状态值校验，同样是为了减少上下文。这一点最让我受启发的就是 Go Race Detector，简单说就是这个软件会在 Go 运行时额外记录线程获取变量的信息，牺牲了时间和空间，但是一旦遇到 Data Race 就会暴露出来。用锁和 channel都会有一个很 trick 的地方，就是把一个深度嵌套的指针传递给调用方，我的很多这样的 Data Race 都是用 Race Detector 暴露出来的。如果爆出了运行时的 Data Race 再去定位原因，那么耗费的时间和枯燥程度是我不敢想象的。

关于 Race Detector 还有一些题外话：使用它的时候我很唏嘘，因为回想起了之前工作待过的一个项目组，那是一个整体抗拒打日志，更抗拒自动化测试的地方。每次出了线上 bug，复盘听到最多的就是”你要多想“、”你要让人 review“、”我们再加一道（手工去做的）流程“。我不禁想起了明朝因为人力太便宜所以不愿意大规模推广纺织机的段子。而 Race Detector 背后站立的更多是一种编程的理念，也是推动人类科技进步的力量：”让人来做人适合做的事，让程序来做程序适合做的事“，或者说”自动化“。