木鸟杂记

小引

大学时，数据库学的不是很深，现在有印象的也就 SQL、ER 图、范式、事务等使用上的寥寥概念。对于其实现上一直没有过系统性的了解，但既然走上了存储这条路，数据库知识肯定要补一下。先前，知乎上很多地方看到大家推荐 cmu15445 这门课，也早就将课程主页收藏到了文件夹，但一直没得空来看。念念不忘，必有回响，到这个假期，恰逢换工作，才有点大块的时间开个头。

大纲

简单介绍下 cmu15445 的教学大纲，该课以 Database System Concepts 为辅助教材， 讲述了数据库管理系统（DBMS）设计和实现的方方面面，包括：

1. 数据模型（关系型，文档型，键值型）
2. 存储模型（n-ary，decomposition，可以理解为行式、列式）
3. 查询语言（sql，存储过程 stored procedures）
4. 存储结构（heaps，基于日志 log-structured）
5. 索引设计（排序树，哈希表）
6. 事务处理（ACID，并发控制）
7. 数据恢复（日志、快照）
8. 执行引擎（joins，排序，聚集，优化）
9. 并发架构（多核，分布式）

可以看出，内容十分翔实，课程使用一个开源的商业数据库作为案例进行讲解，以深入探讨数据库设计时，在上述各个方面进行取舍的过程。本课程十分重视编程实践，设计了一系列前后勾连但又足够简洁的代码实验。

cmu15445 是一门关于数据库管理系统（DBMS）设计与实现的经典公开课。该课程以 Database System Concepts 为教材，提供随堂讲义、笔记和视频，精心准备了几个互相勾连的小实验。该课程十分注重系统设计和编程实现，用主讲教授 Andy Pavlo 的话说，这是一门可以写在简历上、并且能帮你拿到好 offer 的课程。

这个假期得空，翻出这门课程，即被其翔实的内容、精当的组织所折服。无奈时间有限，只能以实验为主线，辅以讲义和笔记，简单跟一跟。如果再有时间，就去扫下教材和视频。从实验一开始，每个实验 autograder 跑过之后，出一篇笔记，聊以备忘。 Andy Pavlo 教授建议不要公开实验代码仓库，因此文章尽量少贴代码，多写思路。

本篇是实验一，管理文件系统的页在内存中的缓存 —— buffer pool manager。

概览

实验的目标系统 BusTub 是一个面向磁盘的 DBMS，但磁盘上的数据不支持字节粒度的访问。这就需要一个管理页的中间层，但 Andy Pavlo 教授坚持不使用 mmap 将页管理权力让渡给操作系统，因此实验一 的目标便在于主动管理磁盘中的页（page）在内存中的缓存，从而，最小化磁盘访问次数（时间上）、最大化相关数据连续（空间上）。

该实验可以分解为相对独立的两个子任务：

1. 维护替换策略的： LRU replacement policy
2. 管理缓冲池的： buffer pool manager

两个组件都要求线程安全。

本文首先从基本概念、核心数据流总体分析下实验内容，然后分别对两个子任务进行梳理。

概述

Golang 中 slice 极似其他语言中数组，但又有诸多不同，因此容易使初学者产生一些误解，并在使用时不易察觉地掉进各种坑中。本篇小文，首先从 Go 语言官方博客出发，铺陈官方给出的 slice 的相关语法；其次以图示的方式给出一种理解 slice 的模型；最后再总结分析一些特殊的使用情况，以期在多个角度对 slice 都有个更清晰侧写。

如不愿看繁琐叙述过程，可直接跳到最后小结看总结。

boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu’s LMDB 项目 ，实现的比较清爽，去掉单元测试和适配代码，核心代码大概四千多行。简单的 API、简约的实现，也是作者的意图所在。由于作者精力所限，原 boltdb 已经封版，不再更新。若想改进，提交新的 pr，建议去 etcd 维护的 fork 版本 bbolt。

为了方便，本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小，五脏俱全，仅仅四千多行代码，就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当，如果你是 go 语言爱好者、如果对 KV 库感兴趣，那 boltdb 绝对是不可错过的一个 repo。

本系列计划分成三篇文章，依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的，因此叙述时会不可避免的产生交织，读不懂时，暂时略过即可，待有全貌，再回来梳理。本文是第一篇， boltdb 数据组织。

概览

数据库中常用的索引设计有两种，一个是 B+ 树，一个是 LSM-tree。B+ 树比较经典，比如说传统单机数据库 mysql 就是 B+ 树索引，它对快速读取和范围查询（range query）比较友好。 LSM-tree 是近年来比较流行的索引结构，Bigtable、LevelDB、RocksDB 都有它的影子；前面文章也有提到，LSM-tree 使用 WAL 和多级数据组织以牺牲部分读性能，换来强悍的随机写性能。因此，这也是一个经典的取舍问题。

BoltDB 在逻辑上以桶来组织数据，一个桶可以看做一个命名空间，是一组 KV 对的集合，和对象存储的桶概念类似。每个桶对应一棵 B+ 树，命名空间是可以嵌套的，因此 BoltDB 的 Bucket 间也是允许嵌套的。在实现上来说，子 bucket 的 root node 的 page id 保存在父 bucket 叶子节点上实现嵌套。

每个 db 文件，是一组树形组织的 B+ 树。我们知道对于 B+ 树来说，分支节点用于查找，叶子节点存数据。

1. 顶层 B+ 树，比较特殊，称为 root bucket，其所有叶子节点保存的都是子 bucket B+ 树根的 page id 。
2. 其他 B+ 树，不妨称之为 data bucket，其叶子节点可能是正常用户数据，也可能是子 bucket B+ 树根的 page id。

相比普通 B+ 树，boltdb 的 B+ 树有几点特殊之处：

2. 节点的分支个数不是一个固定范围，而是依据其所存元素大小之和来限制的，这个上限即为页大小。
3. 其分支节点（branch node）所存分支的 key，是其所指向分支的最小 key。
4. 所有叶子节点并没有通过链表首尾相接起来。
5. 没有保证所有的叶子节点都在同一层。

在代码组织上，boltdb 索引相关的源文件如下：

1. bucket.go：对 bucket 操作的高层封装。包括kv 的增删改查、子bucket 的增删改查以及 B+ 树拆分和合并。
2. node.go：对 node 所存元素和 node 间关系的相关操作。节点内所存元素的增删、加载和落盘，访问孩子兄弟元素、拆分与合并的详细逻辑。
3. cursor.go：实现了类似迭代器的功能，可以在 B+ 树上的叶子节点上进行随意游走。

本文主要分三部分，由局部到整体来一步步揭示 BoltDB 是如何进行索引设计的。首先会拆解树的基本单元，其次剖析 bucket 的遍历实现，最后分析树的生长和平衡过程。

boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu’s LMDB 项目 ，实现的比较清爽，去掉单元测试和适配代码，核心代码大概四千多行。简单的 API、简约的实现，也是作者的意图所在。由于作者精力所限，原 boltdb 已经封版，不再更新。若想改进，提交新的 pr，建议去 etcd 维护的 fork 版本 bbolt。

为了方便，本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小，五脏俱全，仅仅四千多行代码，就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当，如果你是 go 语言爱好者、如果对 KV 库感兴趣，那 boltdb 绝对是不可错过的一个 repo。

本系列计划分成三篇文章，依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的，因此叙述时会不可避免的产生交织，读不懂时，暂时略过即可，待有全貌，再回来梳理。本文是第一篇， boltdb 数据组织。

引子

一个存储引擎最底层的构成，就是处理数据在各种物理介质（比如在磁盘上、在内存里）上的组织。而这些数据组织也体现了该存储引擎在设计上的取舍哲学。

在文件系统上，boltdb 采用页（page）的组织方式，将一切数据都对齐到页；在内存中，boltdb 按 B+ 树组织数据，其基本单元是节点（node），一个内存中的树节点对应文件系统上一个或者多个连续的页。boltdb 就在数据组织上就只有这两种核心抽象，可谓设计简洁。当然，这种简洁必然是有代价的，后面文章会进行详细分析。

本文首先对节点和页的关系进行总体说明，然后逐一分析四种页的格式及其载入内存后的表示，最后按照 db 的生命周期串一下 db 文件的增长过程以及载入内存的策略。

早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。

看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路：从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。

本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第二篇，Bloom Filter。

引子

LevelDB 是一个单机的 KV 存储引擎，但没有使用传统的平衡查找树以平衡读写性能，而是使用了 LSM-tree 结构来组织数据，牺牲部分读性能来换取较高的写吞吐。下面来对照一张图来介绍 LSM-tree 在不同存储介质上的组织方式。

LevelDB 将数据分为两大部分，分别存放在内存和文件系统中。主要数据模块包括 WAL log，memtable，immutable memtable，sstable。按照数据流向依次如下：

1. 当 LevelDB 收到一个写入请求 put(k, v) ，会首先将其操作日志追加到日志文件（WAL）中，以备节点意外宕机恢复。
2. 写完 WAL 后，LevelDB 将该条 kv 插入内存中的查找结构：memtable。
3. 在 memtable 积累到一定程度后，会 rotate 为一个只读 memtable，即 immutable memtable；同时生成一个新的 memtable 以供写入。
4. 当内存有压力后，会将 immutable memtable 顺序写入文件系统，生成一个 level0 层的 sstable（sorted strings table） 文件。该过程称为一次 minor compaction。
5. 由于查询操作需要按层次遍历 memtable、immutable 和 sstable。当 sstable 文件生成的越来越多之后，查询性能必然越来越差，因此需要将不同的 sstable 进行归并，称为 major compaction。

LevelDB 层次组织

所有在文件系统中的 sstable 文件，被 LevelDB 在逻辑上组织成多个层次（一般是 7层），并且满足以下性质：

1. 层次越大说明其数据写入越早，即先往上层进行“放”（minor compaction），上层“满”（达到容量限制）之后“溢”（major compaction）到下层进行合并。
2. 每层文件总大小都有一定限制，并且成指数级增长。比如 level0 层文件总大小上限为10MB，level1 层为100MB，依次类推，最高层（level6层）没有限制。
3. 由于 level0 每个 sstable 文件都是直接由 memtable 落盘而来， 因此多个 sstable 文件的 key 范围可能会有交叠。而其他层的多个 sstable 文件则通过一些规则保证没有交叠。

对于 LevelDB 的一次读取操作，需要首先去 memtable、immutable memtable 查找，然后依次去文件系统中各层查找。可以看出，相比写入操作，读取操作实在有点效率低下。我们这种客户端进行一次读请求，进入系统后被变成多次读请求的现象为读放大。

为了减小读放大，LevelDB 采取了几方面措施：

1. 通过 major compaction 尽量减少 sstable 文件
2. 使用快速筛选的办法，快速判断 key 是否在某个 sstable 文件中

而快速判断某个 key 是否在某个 key 集合中，LevelDB 用的正是布隆过滤器。当然，布隆过滤器只能快速判断 key 一定不在某个 sstable 中，从而在层层查找时跳过某些 sstable 。之后会详述原因，此处按下不表。

概述

Context 是 Go 中一个比较独特而常用的概念，用好了往往能事半功倍。但如果不知其然而滥用，则往往变成 “为赋新词强说愁”，轻则影响代码结构，重则埋下许多bug。

Golang 使用树形派生的方式构造 Context，通过在不同过程 [1] 中传递 deadline 和 cancel 信号，来管理处理某个任务所涉及到的一组 goroutine 的生命周期，防止 goroutine 泄露。并且可以通过附加在 Context 上的 Value 来传递/共享一些跨越整个请求间的数据。

Context 最常用来追踪 RPC/HTTP 等耗时的、跨进程的 IO 请求的生命周期，从而让外层调用者可以主动地或者自动地取消该请求，进而告诉子过程回收用到的所有 goroutine 和相关资源。

Context 本质上是一种在 API 间树形嵌套调用时传递信号的机制。本文将从接口、派生、源码分析、使用等几个方面来逐一解析 Context。

早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。

看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路，从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。

本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第一篇，Skip List。

需求

LevelDB 是一个单机的 KV 存储引擎。KV 引擎在本质上可认为只提供对数据条目（key，val） Put(key, val), Get(key) val, Delete(key) 操作的三个接口。而在实现上，LevelDB 在收到删除请求时不会真正删除数据，而是为该 Key 写一个特殊标记，以备读取时发现该 Key 不存在，从而将 Delete 转为 Put ，进而将三个接口简化为两个。砍完这一刀后，剩下的就是在 Put 和 Get 间进行性能取舍，LevelDB 的选择是：**牺牲部分 Get 性能，换取强悍 Put 性能，再极力优化 Get**。

我们知道，在存储层次体系（Memory hierarchy）中，内存访问远快于磁盘，因此 LevelDB 为了达到目标做了以下设计：

1. 写入（Put）：让所有写入都发生在内存中，然后达到一定尺寸后将其批量刷磁盘。
2. 读取（Get）：随着时间推移，数据不断写入，内存中会有一小部分数据，磁盘中有剩余大部分数据。读取时，如果在内存中没命中，就需要去磁盘查找。

为了保证写入性能，同时优化读取性能，需要内存中的存储结构能够同时支持高效的插入和查找。

之前听说 LevelDB 时，最自然的想法，以为该内存结构（memtable）为是平衡树，比如红黑树、AVL 树等，可以保证插入和查找的时间复杂度都是 lg(n)，看源码才知道用了跳表。相比平衡树，跳表优势在于，在保证读写性能的同时，大大简化了实现。

此外，为了将数据定期 dump 到磁盘，还需要该数据结构支持高效的顺序遍历。总结一下 LevelDB 内存数据结构（memtable）需求点：

1. 高效查找
2. 高效插入
3. 高效顺序遍历

概览

Dynamo 是一个高可用的 KV 存储系统。为了保证高可用和高性能，Dynamo 采用了最终一致性模型，它对开发人员提供一种新型 API，使用了版本机制，并通过用户侧辅助解决冲突。Dynamo 目标是提供不间断的服务，同时保证性能和可扩展性。由于亚马逊大量采用了去中心化、高度解耦微服务架构，因此对微服务状态的存储系统的可用性要求尤其高。

S3 （Simple Storage Service）是 Amazon 另一款有名的存储服务，虽然也可以理解为 KV 存储，但它和 Dynamo 的目标场景并不一致。S3 是面向大文件的对象存储服务，主要存储二进制文件，不提供跨对象的事务。而 Dynamo 是一款面向小文件的文档存储服务，主要存储结构化数据（如 json），并且可以对数据设置索引，且支持跨数据条目的事务。

相对于传统的关系型数据库，Dynamo 可以认为是只提供主键索引，从而获取更高的性能和更好的扩展性。

为了实现可扩展性和高可用性，并保证最终一致性，Dynamo 综合使用了以下技术：

1. 使用一致性哈希对数据进行分片（partition）和备份（replicate）。
2. 使用版本号机制（Vector Clock）处理数据一致性问题。
3. 使用多数票（Quorum）和去中心化同步协议来维持副本间的一致性（Merkle Tree）。
4. 基于 Gossip Protocol 进行失败检测和副本维持。

实现上来说，Dynamo 有以下特点：

1. 完全去中心化，没有中心节点，所有节点关系对等。
2. 采用最终一致性，使用版本号解决冲突，甚至要求用户参与解决冲突。
3. 使用哈希值进行数据分片，组织数据分布，均衡数据负载。

儿时初学“让我们荡起双桨”，只感觉旋律朗朗；年岁稍长，偶尔哼起，三言两语，味出千万意境；后来，求学帝都，游北海，正是“湖面倒映着美丽的白塔，四周环绕着绿树红墙”，光阴荏苒，不变的是文字的生命力。

歌词为乔羽先生所做，很多脍炙人口的名作皆出自其手：《我的祖国》、《难忘今宵》、《爱我中华》。词分三段，层层递进。第一段写划船之景，寥寥几句，首尾勾连、推近及远、勾勒出四合景象。第二段写欢快之情，童真昂扬，心情轻快，描绘出饱满的童趣。第三段继而升华，设问如此美景、如此生活、如此时代，如何得来？尔后戛然而止，语已尽而意无穷。

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

MIT 今年终于主动在 Youtube 上放出了随堂视频资料，之前跟过一半这门课，今年打算刷一下视频，写写随堂笔记。该课程以分布式基础理论：容错、备份、一致性为脉络，以精选的工业级系统论文为主线，再填充上翔实的阅读材料和精到的课程实验，贯通学术理论和工业实践，实在是一门不可多得的分布式系统佳课。课程视频: Youtube，B站。课程资料：6.824主页。本篇是第五节课笔记，包括两部分：第一部分由一个助教讲了 lab2 中将会用到的一些 go 的源语、设计模式和实践技巧，包括内存模型、goroutine和闭包、时间库、锁、条件变量、channel、信号、并行和一些常用工具等等。第二部分是由另两个助教梳理了下 raft 中常遇到的一些 bug 和调试方法。