小张笔记

存储引擎个人调查报告

对于一个初学者来说，学习存储引擎最好的办法就是亲身参与一个存储引擎的编写，但是普通人很难有机会，存储引擎不像是普通的应用程序，编写工业级别的存储引擎的机会，一般只会在数据库公司/部门或者某几个高校中，那么自己造轮子就是一个很好的办法。自己造轮子，不可能只看一些理论，必须参考现成的存储引擎，故需要对现在的存储引擎的情况做一个调查。调查从以下几个指标进行：

  • 编程语言
  • 代码规模
  • 资料丰富程度

这些指标影响着学习这些存储引擎的效率。倘若存储引擎所用的编程语言是你不擅长的语言，那么学习、使用它本身还需要额外的成本；代码规模不宜过大，让初学者去阅读上百万，上十万规模代码的项目是不现实的，到目前为止，PostrgeSQL就有135万行代码，存储引擎部分肯定也不少，直接阅读它是不现实的，我去找猫咪借8条命也不够用；资料分为文档、书本、注释，资料丰富程度也影响着学习效率，代码的很多地方浓缩了很多信息量，直接阅读代码且没有相关经验的话很难理解代码的思路，丰富易读的资料能够让学习者如虎添翼，使得学习者可以以一个更高的视角去阅读代码。

目前存储引擎所使用的语言集中在三种：C、C++和Go，其它语言的存储引擎有，但是数量偏少，比如说使用Java的HBase，我们暂且不去思考为什么，只是关注于这个事实，从而得出一个结论：学习存储引擎，最好要懂得使用C/C++或Go中的至少一个。

对于初学者，代码规模在5000行以下是比较合适的，当然这里的代码是指核心代码，不包括一些脚本、测试、benchmark代码。这里的代码规模以选择存储引擎的特定版本为主，可能一些存储引擎的代码规模已经在10000行以上了，但是它的早期可用版本，在5000行以下，那么这也是合适的。代码行数也有两种，一种是整体代码行数，一种是有效代码行数，两者的区别是后者只统计能被编译器识别的部分，还需要除去头文件，注释是不计入的。整体代码行数使用Shell[1]命令进行统计，有效代码函数使用jetbrains的Statistic插件[2]进行统计。

对于资料丰富程度，一般有文档、书本、注释，大多数成熟的存储引擎都有自己的文档，再加上互联网上其它前辈对它的研究成果，可以作为参考。有书专门讲解的存储引擎比较少，一般书本比较系统，但是未必写得好。很多开发者写代码很认真，不仅写了代码还写了许多注释，写过代码的同学都知道，写代码很爽，写注释、文档却是一件很费力的事情，注释，代表着开发者对代码思路的见解，也有很多参考价值。最后阅读知乎回答、和有相关经验的知乎用户交流，也是一种了解存储引擎的方式。

下面介绍一些开源的存储引擎项目。该文章将随着我对它们了解的深入而不断更新。**想造轮子的童鞋可以联系我，咱们互相交流交流！**文章封面来自机核网[3]。

# boltdb

boltdb是一个参考自LMDB的存储引擎，作者在早期的时候直接将LMDB的代码复杂到项目中，加上注释，然后编写成Go的代码。目前已经封存，最后的提交时间为2018年3月3日，其fork版本被etcd维护为bbolt (opens new window)，并应用与分布式存储etcd中，etcd作者是阿里巴巴90后工程师李响[4]。

它具备以下几个特征：

  • 使用B+树作为索引
  • 支持B+树嵌套（subbucket）
  • 支持事务
  • 支持持久化
  • 使用mmap从磁盘中读取数据
  • 使用freelist进行空间回收（不进行compact）

指标方面情况如下：

总结一下，boltdb代码量小，功能齐全，且其fork版本已经被应用到了工业级别的项目中，也已经封存，资料丰富，讨论研究的人也很多，故是学习的最佳对象之一，可惜我不太会go~对于熟悉go的同学来说是再好不过的项目了。

# sqlite

著名嵌入式关系型数据库，被大量应用于Android系统中，纯C编写，代码注释很齐全，准确地说这不是一个存储引擎，是一个完整的项目，但是可以抽取其中后端的部分来学习。作者写的一篇关于为什么sqlite使用C进行编写的文章，Why Is SQLite Coded In C (opens new window) 写的很好。下面是sqlite的架构：

img

它具备以下特性：

  • 采用B树作为索引，但是听说LSM也可，有模块可选择，不过是比较新的版本
  • 支持持久化，具体机制不了解
  • 支持事务
  • 支持WAL

各个指标方面：

总结一下，相比boltdb，SQLite更有名，即使不是数据库、分布式行业从业者，也听过SQLite的鼎鼎大名，其代码质量是经受过考验的。缺点是代码规模略大，优点是资料比较多，讨论研究的人也挺多的吧，想学习当前的SQLite是不可能的，从第一个版本看起还是有可能的。

# key-value-system

这不是什么著名存储引擎，这只是一个玩具项目，应该是用作毕设的，我在我的Github的活动时间线[8]中发现了它，那个时候我正愁毕设写什么，看见它就对存储引擎起了兴趣，它索引数据结构落后，甚至没有完备的持久化机制和压缩操作，但是它还是给了我很多启发。虽然没有封存，但是作者已不再开发，且很难联系上作者。

它具备以下特性：

  • 采用hashtable作为索引数据结构
  • 在索引下设计了一个缓冲池
  • 缓冲池支持持久化（索引不支持）

各个指标方面：

  • 编程语言：纯C编写（C：100%）

  • 代码行数，没有发布过版本：

    • 最后的commit (opens new window)提交与2012年2月26日

      • 整体行数：3925[.c] + 653[.h] = 4578
      • 有效行数：3061[.c] + 165[.h] = 3226

    • 去掉测试代码：

      • 整体行数：941[.c] + 181[.h] = 1122
      • 有效行数：735[.c] + 51[.h] = 786

  • 资料方面

总结一下，这是一个很简单，甚至有些过时的存储引擎，但是它很简单，代码量住够小，但是缓冲池的设计理解起来还是有点难度的。另我吃惊的是，测试代码所占的比重是如此之高，在75%以上！！着实让我感叹，测试才是数据库最重要的部分！这里推荐一下我的毕设成果EdithDB (opens new window)，由于本人水平有限，写的项目漏洞百出，文档的话就是我的毕业论文，暂时没有公布，因为觉得没有人会看~

# 接下来的更新计划

  1. LMDB (opens new window)
  2. leveldb (opens new window)
  3. nessdb (opens new window)
  4. redis (opens new window)
  5. badger (opens new window)
  6. rosedb (opens new window)
  7. Tokyo Cabinet (opens new window)

# 参考

  1. ^find . -name "*.c"|xargs wc -l|grep "total"|awk '{print $1}'
  2. ^Statistic是一个专门用来统计代码行数的插件 https://plugins.jetbrains.com/plugin/4509-statistic
  3. ^游戏开发设计心得分享专题封面 https://www.gcores.com/collections/64
  4. ^阿里巴巴李响加入 CNCF 技术监督委员会 https://www.infoq.cn/article/z1fl-LX3o2yGdIqG12S1
  5. ^SQLite源代码时间线 https://www.sqlite.org/cgi/src/timeline
  6. ^bookstack：[英文] DB Tutorial https://www.bookstack.cn/read/db_tutorial/README.md
  7. ^还是来源于张原嘉的回答 https://www.zhihu.com/question/22819578/answer/62544197
  8. ^当你进入github.com时，会推荐关注的人的收藏动态

发布于 07-22

# 文章被以下专栏收录

​

Last Updated: 2022/7/8 下午2:41:42
小张头条