周刊(第6期):《sqlite 3.36 btree实现解析》番外篇

2022-02-20
6分钟阅读时长

引言:从2021年9月份开始要探索生产级btree存储引擎的实现,到2022年2月整理完毕发布《sqlite 3.36 btree实现解析》的系列文章,我花费了小半年的时间,本期会聊聊整个过程下来我的一些想法。


《sqlite 3.36 btree实现解析》番外篇

时间回到2021年9月份。彼时,因为工作的关系,要研究一下生产级btree存储引擎的实现,在此之前我大体对btree、b+tree的数据结构和算法有个了解,见:

但是,一个生产级的产品,对比教科书的示范型代码,还是有很大的区别的,具体来说,我当时不明白以下这些生产级存储引擎的问题如何解决:

  • 如何存储变长的数据?
  • 如何存储数据大小超过一个物理页面的数据?
  • 如何利用被回收的空间?
  • 如何处理崩溃恢复?
  • 读写并发如何处理?

为了解答这些疑问,先后去翻阅InnodDB、WiredTiger、sqlite的文档,但是这些项目代码量都太大了,以我当时的程度,无法马上找到很具体的解答。

事情的突破在从网上查找文章时看到的这一篇文章:How Database B-Tree Indexing Works - DZone Database,这是一篇解释btree工作原理的文章,这篇文章同时还列出了一个项目:madushadhanushka/simple-sqlite: Code reading for sqlite backend,这个项目的作者,将sqlite2.5版本中btree的实现,单独抽取出来形成了一个独立的KV库,可以编译通过使用。

看到这个项目的时候,我的感觉就是如获至宝,因为虽然只有几千行的代码量,但是解答了很多上面提到的疑问,“麻雀虽小五脏俱全”,我花了几天的时间整体阅读了解了原理,这个项目给我打开了研究生产级btree存储引擎的突破口。

在这以后,考虑到2.5版本的sqlite已经是2002年的作品,距离现在时间太久了,还想接着了解后面做了那些改进,又接着阅读了3.6.10版本的实现,找这个版本的原因,是因为这是sqlite官方在github上同步的第一个版本,那时候仍然步子不敢迈得太大。

又花了一个多月把这个版本的btree实现了解以后,我了解到在这之后的版本里,sqlite做了另一个重大的更新:在页面管理部分引入了WAL机制,加上前面两个版本阅读下来累积的信心,就接着找当时还是最新的3.36版本的实现来阅读,这又花了一个多月的时间。

这以后,就是逐步将整理的笔记写成文档了,后续的事情不表,都在这几篇文档里。

回头看这整个流程,我自己的感受是:

  • “问题驱动”可能是效率更高的学习方式,带着问题出发、找到自己疑问的答案,能更快的学习某个知识。
  • 生产级的实现和教科书的区别很大,后者更多的是讲解原理,而生产级实现考虑更多的是各种实际生产中的边际情况。如果只了解原理,而不去具体做实现,对事情的理解最后只能浮于表面。
  • 找到那个精简实现是这个过程里的“突破口”,原因在于:如果一上来看的很成熟的版本,而且你在这个领域积累的不深,那么很可能会导致丢失了很多“上下文(context)”情景,给阅读、理解带来很大困难。下次再遇到类似的问题,我会按照这次的经验,先尝试回退到之前的更简单的版本,看看在那里能不能跟上作者的思路,攻克简单的实现之后,再尝试最新的版本。
  • 除了数据库领域以外,有一些别的领域,在教学的时候会让学生参与实现一个简单的项目。这类型的项目虽然简单,但是五脏俱全,能够让学生了解这个领域的概貌,我把这种流程称为“破解神秘感”。如我最开始提到的那些疑问,如果在这之前做过数据库相关的作业,应该会有个大体的想法。

这篇番外篇的番外篇

sqlite的注释

除了这些以外,sqlite的代码风格也很好,尤其是注释写的非常详尽。

有一种说法,“好的代码都是自解释的,无需多做注释”。我对这句话有一些不太一样的看法,因为即便再好的代码,如果只看代码的话,对整个的架构、结构很难了解。这一点sqlite就做的很好,在代码中会写上类似文档一样的注释来解释结构,比如有这么一段解释btree内部结构的注释文档:

/
** This file implements an external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
**
** The basic idea is that each page of the file contains N database
** entries and N+1 pointers to subpages.
**
**   ----------------------------------------------------------------
**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
**   ----------------------------------------------------------------
**
** All of the keys on the page that Ptr(0) points to have values less
** than Key(0).  All of the keys on page Ptr(1) and its subpages have
** values greater than Key(0) and less than Key(1).  All of the keys
** on Ptr(N) and its subpages have values greater than Key(N-1).  And
** so forth.
*/

如果不写这些注释,读者想要理解作者的思路的话,仅凭代码是很困难的。

这里只是抽取了sqlite代码注释中的一小部分,我读代码下来的感觉,sqlite的注释可以说是“保姆级别”的。“写代码是表达自己,读代码是去理解别人”(见为什么说读代码比写代码难? - 知乎),可以说sqlite的作者为了让别人更好的理解自己,尽力了。

对应的,我也看过那种几乎没有注释、变量函数名都是缩写的代码,这样的代码作者,可能就不是很像让别人读懂ta。

sqlite几个相关的链接

可以在这里(History Of SQLite Releases)找到sqlite的release历史,进而下载到对应版本的代码。以2.5版本为例,发布于2002-06-17这一天,我用代码统计工具统计了一下,代码量仅有31188行(包括注释):

sqlite2.5的代码统计

BTW:不知道sqlite 2.5版本,对比一些数据库实验课程的大作业,复杂度如何,感觉以早期sqlite代码来入门数据库学习也是足够的,前提是有足够的耐心和时间。

而3.36版本发布于2021-06-18这一天,代码量已经到了21W行,前后相隔19年:

sqlite3.36的代码统计

还可以在Release History Of SQLite看到不同版本新增的特性、bug fix等,比如可以看到WAL是在3.7.0版本引入的特性:

2010-07-21 (3.7.0)

  1. Added support for write-ahead logging.

sqlite的箴言

在每个sqlite代码文件中,开头都有这么一段注释:

** May you do good and not evil. ** May you find forgiveness for yourself and forgive others. ** May you share freely, never taking more than you give.

破解神秘感的项目

前面提到过要破解神秘感,列举几个计算机相关课程的实验大作业或项目。

操作系统

数据库

分布式系统

  • MIT的6.824:6.824 Schedule: Spring 2022,也是有随课程要完成的大作业,以前使用C++实现Paxos,后面改成了Go实现Raft。

Linux早期内核实现解析

许多年以前,赵炯博士在网上公开过一份文档,基本上逐行讲解了Linux0.11版本内核的实现,那时候的官网oldlinux.org 现在好像已经不能访问,在官网的页面Early Linux Kernel Analisys and Comments也提供了这份文档电子版的下载链接:http://www.oldlinux.org/download/clk011c-1.9.5.pdf,也有对应的公开发行物:Linux内核完全剖析 (豆瓣)

邮件订阅

微信公众号

wechat-account-qrcode