木鸟杂记

目标

充分利用现代存储 SSD 的性能，在提供同样 API 的情况下，显著降低 LSMTree 的读写放大，以提高其性能。

背景

在传统磁盘上，顺序 IO 的性能大概是随机 IO 的 100 多倍，LSMTree 基于此，将海量 KV 的随机读写实现为内存随机读写+顺序刷盘+定期归并（compact），以提高读写性能，尤其适用于写多于读且时效性比较强（最近数据最常访问）的场景。

博客本来用的是 github pages，但貌似由于百度爬虫太疯狂，被 github 给 ban 掉了。根据 marketmechian 的数据，在中国大陆搜索引擎界，百度还是占了半壁江山：

• Baidu: 67.09%
• Sogou: 18.75%
• Shenma: 6.84%
• Google: 2.64%
• bing: 2.6%
• Other: 2.08%

而作为一个中文博客，还是希望能够被更多的国内用户看到，因此一直在寻求一个使得百度爬虫自动爬取博客的方法。偶然间在浏览博客时，看到了有人在推荐 zeit.co 这个托管平台，使用了下，发现真是个非常棒的静态代码托管+CI Serverless Function 平台，在这里推荐给大家。

MIT 今年终于主动在 Youtube 上放出了随堂视频资料，之前跟过一半这门课，今年打算刷一下视频，写写随堂笔记。该课程以分布式基础理论：容错、备份、一致性为脉络，以精选的工业级系统论文为主线，再填充上翔实的阅读材料和精到的课程实验，贯通学术理论和工业实践，实在是一门不可多得的分布式系统佳课。课程视频: Youtube，B站。课程资料：6.824主页。本篇是第三节课笔记，GFS。

概述

存储（Storage）是一个非常关键的抽象，用途广泛。

GFS 论文还提到了很多关于容错、备份和一致性的问题。

GFS 本身是 Google 内部一个很成功的实用系统，其关键点被很好的组织到一块发表成为了学术论文，从硬件到软件，涵盖了很多问题，值得我们学习。

想详细了解 GFS，也可以看我之前的 GFS 论文笔记。

MIT 今年终于主动在 Youtube 上放出了随堂视频资料，之前跟过一半这门课，今年打算刷一下视频，写写随堂笔记。该课程以分布式基础理论：容错、备份、一致性为脉络，以精选的工业级系统论文为主线，再填充上翔实的阅读材料和精到的课程实验，贯通学术理论和工业实践，实在是一门不可多得的分布式系统佳课。课程视频: Youtube，B站。课程资料：6.824主页。本篇是第二节课笔记，RPC 和线程。

为什么用 Go

1. 语法先进。在语言层面支持线程（goroutine）和管道（channel）。对线程间的加锁、同步支持良好。
2. 类型安全（type safe）。内存访问安全（memory safe），很难写出像 C++ 一样内存越界访问等 bug。
3. 支持垃圾回收（GC）。不需要用户手动管理内存，这一点在多线程编程中尤为重要，因为在多线程中你很容易引用某块内存，然后忘记了在哪引用过。
4. 简洁直观。没 C++ 那么多复杂的语言特性，并且在报错上很友好。

MIT 今年终于主动在 Youtube 上放出了随堂视频资料，之前跟过一半这门课，今年打算刷一下视频，写写随堂笔记。该课程以分布式基础理论：容错、备份、一致性为脉络，以精选的工业级系统论文为主线，再填充上翔实的阅读材料和精到的课程实验，贯通学术理论和工业实践，实在是一门不可多得的分布式系统佳课。课程视频: Youtube，B站。课程资料：6.824主页。本篇是第一节课笔记，绪论。

课程背景

构建分布式系统的原因：

1. Parallelism，资源并行（提高效率）。
2. Fault tolerance，容错。
3. Physical，系统内在的物理分散。
4. Security，不可信对端（区块链）。

分布式系统面临的挑战：

1. Concurrency，系统构件很多，并行繁杂，交互复杂。
2. Partial failure，存在部分失败，而不是像单机一样要么正常运行，要么完全宕机。
3. Performance，精巧设计才能获取与机器数量线性相关的性能。

本文缘起于Lu Pan 的个人博客文章：https://blog.the-pans.com/cap/ ，是他经过 Martin Kleppmann 授权并且翻译的博文”Please stop calling databases CP or AP”中文版本。但译文中不少句子读来颇为古怪，我对照英文原文，按照自己理解，逐句校验、重译了一遍。这篇文章探讨了为什么不应该滥用 CAP定理 这个概念，旁征博引，入木三分，值得一读。更值得称道的是，Martin 文中所有关键观点都给出了来源，并在最后推荐了一些学习资料，都是不错的阅读材料。以下是正文。

在 Jeff Hodges 的精彩博文给年轻人关于分布式系统的笔记 中，他建议我们用CAP定理来评判系统。不少人听从了这个建议，将他们的系统称为”CP” （提供一致性但在网络分区时不可用），“AP”（高可用但是在网络分区时不一致） 或者干脆 “CA” （说明还没有读过Coda的五年前的文章）。

我同意 Jeff 的所有其他观点，但其关于 CAP 定理的使用建议，我不能表示赞同。CAP 定理本身太过简化而且存在广泛的误解，以至于在界定系统时不能有效的起到作用。因此我请求大家不要再引用CAP定理， 不要再讨论CAP定理。取而代之，我们应该用更精确的术语来表述我们对系统的取舍。

（当然，讽刺的是我不希望别人再讨论这个话题，自己却正在写一篇关于这个话题的文章。不过至少以后别人问我为什么不喜欢讨论CAP定理的时候，我可以把这篇文章的链接给他。还有，抱歉这篇文章会有些吐槽，但是至少这些吐槽给出了文献引用）

小引

曾经在一个面试中让谈谈对 CAP 的理解，当时凭着准备面试时谷歌到的N手资料，类似于小学生背书一样，生挤出只言片语。面试官无奈的笑笑，简练的概括出他想要听到的要点，听的我心下惭愧。面试自然是挂了，后来工作时偶尔接触到这个词汇，初不得要领，后通过不同资料的多侧面理解、印证，渐渐拼凑出了一个轮廓，在这里梳理下，将影子撵到纸上，以供日后索引。

面试官大约是这么概括的：在分布式系统中，失败必然的，分区容错（P）是一定需要的，因此设计系统时需要在可用性（A）和一致性（C）间进行权衡。当时被教育印象很深，现在看来，这句概括是点出了小荷才露尖尖角的那个角。

初冬一个晴朗的午后，从地坛出发，经交道口三条，过圆恩寺胡同，一路走到什刹海。当天天气出奇的好，在太阳的透照下，整个胡同片区懒洋洋的，心里也不由的很轻快。

研究生毕业时，去网易游戏实习攒了点钱，便想入手垂涎了好久的程序员生产力工具—— MacBook Pro。适逢新版发售，等到 2016 年底，新版甫一上市，便从官网下单了一台 pro 入门版：13 寸两口不带 bar 。不过哪怕是入门版，也要一万多大洋，还两个口，还不带 bar。

不带 bar 尚可接受，毕竟 vim 党还是喜欢能按的下去的 Esc 。但两个口——于是默默了去京东下单了几个扩展口，彼时 tpye c 尚不流行，选择无几。

到货后满心欢喜打开，惊艳异常，是醉人的新配色——深空灰、是史无前例的轻薄、是类 Unix 系统加上舒服的 UI。于是将之前的小嘀咕抛诸脑后，嗯，真香。

引子

18年的时候做过一些 6.824，旧文在此，无奈做到 Part 2C，无论如何也跑不过测试，便一直搁置起来。但在后来的日子，却时时念起此门神课，心下伤感。拖到今日，终于可以来还愿了。

这次能跑过所有测试，原因有三：一来，之前做过一次，很多原理还留有印象；二来，这一年多在工作上有了很多分布式系统的实践；三来，golang 的驾驭上也精进了一些。但是在做的过程中，仍然遇到了大量令人纠结的细节，为了方便日后回顾，将这些细节梳理一下，记在此处。若能好巧对其他做此门课的人有些微启发，则又是快事一件了。

6.824 与 Raft

6.824 是一门关于分布式系统的非常棒的公开课，做课程实验的过程中时时惊叹于其构思之精巧、材料准备之翔实。MIT 的大师们能将这样精华的课程开放出来，实乃名校和大师们的气度，更是我们计算机人的幸事。

Raft 是一个面向理解的分布式共识（consensus）协议。分布式共识算法是分布式领域非常非常经典的问题，同时也是分布式系统中非常难的一块，直观的说，就如同流沙上打下分布式系统大楼的地基。不可靠的网络、易故障的主机，造成的状态变化之复杂，实在不是一般人能在脑中模拟得了的。本人愚钝，只能是感性把握加细节堆叠，堪堪有些认识。说回 Raft，有同领域 Paxos 珠玉在前，何以 Raft 仍能脱颖而出？应该是抓住了以下两点：

1. 易于理解。Paxos 是出了名的难以理解，因此也就难以飞入寻常百姓家。而 Raft 通过解耦出多个模块，将算法复杂度进行降维，大大降低了一般人的理解难度。此外，Raft 还有很多精巧的设计，以尽可能避免引入复杂度，从而进一步减轻大家的心智负担。
2. 易于实现。易于理解客观上会导致利于实现，但不等同于就能据此产出优秀系统。如果理解流于感性，则实现成空中楼阁。Raft 论文的厉害之处就在于既有感性把握又有细节组织，几乎就是一个系统的设计文档，还是详细设计文档。

要想做好该实验，需要涉猎大量的材料，我把实验中提到的和我看到的汇总在文末。当然，还有英文劝退。虽然我最后测试用例都过了，但仍有很多没实现好的点以及不理解之处。

注：后续，2023 年又做了一次，终于理清楚了大部分点。

小引

最近在写 Go 代码时需要给某个 struct 定制一个字符串转换方法

1

func (ms MyStruct) String() string

但是在实现是考虑选用 value methods 还是 pointer methods 方式时纠结了起来。

Go 的语法糖使得这两种方式在调用上是一致的，这让我一时难以抉择孰优孰劣，于是决定深入探究一下其背后原理以便之后能写出更地道（idiomatic）的 Go 代码。

概览

Kafka （该论文发表于2011年6月**[1]**）是日志处理和消息队列系统的集大成者。较低的延迟、极高的容量和吞吐，使其可以应用于在线服务和离线业务。为了兼顾性能和可扩展性，Kafka 做了一些看起来反直觉但是却很实用的设计。例行总结一下其设计特点：

1. 面向存储的消息队列：意味在近实时的情况下能够将传统消息队列的存储增加几个数量级。实现原理是充分利用了磁盘的顺序写和操作系统自身的缓存；此外为了提高访盘、传输效率，使用了文件分段、段首索引、零拷贝和批量拉取等技术。

2. 灵活的生产消费方式：总体而言是基于主题粒度的发布订阅式架构，并且既支持组内多消费者互斥消费，也支持不同消费者组间的重复消费。这里面涉及到消息队列的两个核心设计选择：pull 式消费以及客户端侧存储消费进度。拉式消费可能会导致空轮询以及稍微的延迟，好处在于灵活；客户端存储消费进度可以使的 broker 无状态，以进行灵活伸缩和容错。为了简化实现，消费时，每个分区最多为一个消费者所消费。

3. Zookeeper 存储元信息：利用分布式一致性组件 Zookeeper 以注册表的形式存储系统元信息，包括 broker 和消费者的存活信息、消费者和分区间的对应关系、每个分区的消费进度等等。Zookeeper 作为一个前缀树形式组织 KV、支持发布订阅的高可用组件，可以满足 Kafka 进行消费协调和进度保存的协作需求。

4. 分区级别的多副本设计：这一点在论文中还没实现，应该是后来系统开源演进时加上的。利用该条可以实现对 broker 的容错。

5. 简洁强大的消费接口：Kafka 的客户端一般提供两层接口抽象。包括无需关注分区和偏移量信息的高层（high-level）简单读写接口，以及可以灵活控制分区组织和消费进度的低层（low-level）接口。论文中只提到了前者，以表现其简洁。