木鸟杂记

早对 LevelDB 有所耳闻，这次心血来潮结合一些资料粗略过了遍代码，果然名不虚传。如果你对存储感兴趣、如果你想优雅使用 C++、如果你想学习如何架构项目，都推荐来观摩一下。更何况作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看过一遍如果不输出点什么，以我的记性，定会很快抛诸脑后。便想写点东西说说 LevelDB 之妙，但又不想走寻常路：从架构概览说起，以模块分析做合。读代码的这些天，一直在盘算从哪下笔比较好。在将将读完之时，印象最深的反而是 LevelDB 的各种精妙的数据结构：贴合场景、从头构建、剪裁得当、代码精到。不妨， LevelDB 系列就从这些边边角角的小构件开始吧。
本系列主要想分享 LevelDB 中用到的三个工程中常用的经典数据结构，分别是用以快速读写 memtable 的 Skip List、用以快速筛选 sstable 的 Bloom Filter 和用以部分缓存 sstable 的 LRUCache 。这是第三篇，LRUCache。

引子

LRU 是工程中多见的一个数据结构，常用于缓存场景。近年来，LRU 也是面试中一道炙手可热的考题，一来工程用的多，二来代码量较少，三来涉及的数据结构也很典型。LeetCode 中有一道相应的题目：lru-cache。相对实际场景，题目进行了简化：本质上要求维护一个按访问时间有序的 kv 集合，且 kv 皆是整数。经典解法是使用一个哈希表（unordered_map）和一个双向链表，哈希表解决索引问题，双向链表维护访问顺序。这是我当时的一个解法，特点是用了两个辅助函数，并且可以返回节点自身，以支持链式调用，从而简化了代码。

说回 LevelDB 源码，作为一个工业品，它使用 的 LRUCache 又做了哪些优化和变动呢？下面让我们一块来拆解下 LevelDB 中使用的 LRUCache，看看有什么不同。

本文首先明确 LRUCache 的使用方法，然后总览分析 LRUCache 的实现思路，最后详述相关数据结构的实现细节。

强行凑出来的五一小长假即将结束，一年一度的朋友圈晒图大赛又将起航。虽然手机自带的图片自动润色功能越来越强大，但毕竟不能满足我们程序员想掌控一切的精细化调整需求。下面就我一些浅薄的调色经验，以我在长沙游天心阁玩拍的一张图片的调色过程为例，教你一套李鬼变李逵的风景调色屠龙技。最后会给一个简单的修图原理的总结，一探图片调色背后的本质。

先来个对比

为了说明图片调色确实有奇效，先上一个对比图给大家直观感受下：

此图摄于老长沙制高点——天心阁。是日乌云密布，暴雨将至，从天心阁二层远眺，黄瓦蓝天，车水马龙，一动一静，似有雷霆之势。

下面分步骤讲解下调色过程和原理，尽量简洁一点，并且附上参考资料，留给有兴趣深挖的同学。

前一段时间由于一些原因工作变动，面了一些分布式存储的相关岗位，感觉市面上相关经验分享较少，因此拿出来和大家分享一下。由于公司隐私政策问题，不会按公司对题目进行罗列，仅仅就一些面试的方向和内容进行简单梳理。水平经验所限，谬误之处，可以留言交流指正。

相关岗位

分布式存储方向的岗位涵盖甚广，一般可以按照方向分为：

1. 分布式文件存储
2. 对象存储
3. 分布式 KV or 缓存
4. 分布式数据库（new sql）
5. 表格存储
6. 块存储

其定位方向也稍有不同：

分布式文件存储。支持 POSIX 语义或者裁剪 POSIX。可以作为存储和计算分离的存储基座，也可以直接为应用所用，比如说深度学习的一些训练，大数据处理的一些中间存储。常见产品有盘古文件系统、Polarfs、JuiceFS 等。

对象存储。一般是存储图片和视频之类的非结构化数据，通常兼容亚马逊的 S3 接口。常见产品如 Amazon S3、阿里云 OSS、腾讯云 COS。

分布式 KV or 缓存。通常兼容 redis 接口，或者更简化 KV 接口。一般求快，基于内存或者SSD，甚至可持久化内存等新硬件。用于低延迟需求的业务缓存或者存储计算分离系统的底座。产品如字节的 ABase、阿里云的 Tair、PingCAP 的 TiKV。

分布式数据库（or new sql）。通常提供 SQL 接口以及无限水平扩展能力。常见产品有 PingCAP 的 TiDB、阿里云的 PolarDB、腾讯云的 TDSQL。

表格存储。经典的接口可以参考按列存储的 HBase，大数据领域应用比较多。产品如 HBase，字节的 ByteTable。

块存储。提供块设备接口，一般用于云主机的系统盘。产品如 smartX 的超融合。

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

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

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

引子

在分析 boltd 的事务之前，我们有必要对事务概念做一个界定，以此来明确我们的讨论范围。数据库事务（简称：事务）是数据库管理系统执行过程中的一个逻辑单位，由一个有限的数据库操作序列构成^1。wiki 上的定义有点拗口，理解时只需抓住几个关键点即可：

1. 执行：计算层面
2. 逻辑单位：意味着不可分割
3. 操作序列有限：一般粒度不会太大

那为什么要有事务呢？事务出现于上世纪七十年代，是为了解放数据库用户的心智而出现的：事务帮助用户组织一组操作、并在出错时自动进行扫尾。后来，NoSQL 和一些分布式存储为了高性能而舍弃了完整事务的支持。然而，历史是螺旋上升的，事务的便利性让 NewSQL 等新一代分布式数据库又将其重新请回。

提起事务，最脍炙人口的便是 ACID 四大特性。 其实 ACID 更像一种易于记忆的口号而非严格的描述，因为他们在概念上并不怎么对称，而且依赖于一些上下文阐释。本文仍然会按照这四个方面对 boltdb 对事务的支持进行剖析，但在每个小结开始，会先参考 Martin Kleppmann 的演讲[^2]，试着从不同角度先阐释其内涵；然后在再分析 boltdb 对其实现。

北京周边的山上山桃特别多，像物种入侵一样密密麻麻的散落在山坡上、龟缩在山谷中。其他时节徒步时对此没有特别的感觉，但唯独春天，大为惊喜。远处望去，像团团粉色的烟雾般缥缈。然而疫情初定的帝都春日，雾霾又起。亲眼看着漫山的山桃，却只能凭空想象通透天空下的丽景。

本文整理自OSDI 2020 Virtual Consensus in Delos 论文演讲，探讨了分布式系统中控制面的存储系统，提出了一种基于分层抽象思想的分布式架构。其核心在于提出了一种逻辑协议层，使得物理层可以按需进行实现和移植，有点类似于单机系统中虚拟内存之于物理内存的味道。

小引

大学时，数据库学的不是很深，现在有印象的也就 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 。之后会详述原因，此处按下不表。