[数据库技术] 存储引擎

数据库架构可以简要分为两个部分：查询引擎和存储引擎。

本文简要梳理一下存储引擎的关键知识点。

存储引擎部分主要完成的功能：

数据访存接口事务处理日志与恢复

本文将从以下功能组件介绍存储引擎：

数据组织与索引管理 (高效数据访存)并发控制 (高效事务处理)日志与恢复缓冲池 (高效数据访存）

数据组织与索引管理

数据的存储形式：

数据在磁盘上以文件的形式存储，以定长的page管理数据，每个page都是唯一标识的。页面大小根据业务场景可设置，一般4-64KB。数据库DB会管理页面ID到物理地址的mapping关系。可以理解为，给定一个page ID, 数据库可以在磁盘找到对应的data page。

数据的组织方式：

从数据添加的角度，可分为Heap file organization和log structured file。前者对应比如MySQL, 新data tuple添加是按一定的规则找到一个物理位置添加（这个位置一般由index来决定）。后者对应比如LevelDB, RocksDB, 新的data tuple直接顺序append到当前物理位置后。从数组结构的结构，可分为不可变存储和可变储存结构。不可变存储即是不能修改旧的数据，新的数据修改添加都附加到新的文件中，数据删除则通过一些方式来标记。可变存储就是可直接在data tuple对应的物理位置上进行修改。

B+ tree是heap file organization的典型代表，LSM tree是log structured file的典型代表。接下来分别介绍两者。

B+ tree的原理就不多做介绍，简单总结的常见特点：

每个非叶子节点最后有M个，最少有M/2的叶子节点。所有数据信息都存储在叶子节点(data node)，非叶子节点(index node)作为索引功能。从根节点到叶子节点的所有路径都有相同长度。

在存储引擎汇中的B+ tree应满足：

安全的读操作: 1) 当一个node(可以是index/data node) 正在写操作修改，不应该错误地读取其中间状态。2） 如果目标data存在，不能找不到。安全的写操作：1）不能有多个写操作同时进行在一个index/data node上。无死锁：不能出现两个以上线程在等待对方互相释放资源 (循环等待)。

B+tree的广泛使用 主要原因至于在于其特别适合存放在磁盘disk上：

Disk的数据读写都是以block为单位进行的(典型block size是4KB)。把B+tree的node大小对齐为Block的size，那么load a tree node就是load一个block。Index node存放是指向child node的指针。按照64bit来算的话，一个block可以存放4KB/8B = 512个指针。所以一个index node存放大量的分支，导致整个树是3到4层。只需要3-4 index node的访问就可以定位到data node。在4层的情况下，整个B+tree已经可以index 512^3个data node，是一个很大的数字了。也就是4次IO，我们可以定位到一个很大存储量中的一个data page。B+ tree的leaf data node包含着指向邻居的叶子节点，非常方便与range search。

InnoDB中的B+tree

MySQL中的存储引擎为InnoDB, 是目前比较流行的。阿里的PolarDB也是采用的InnoDB作为基础。

InnoDB的读性能主要靠B+tree组织的index。InnoDB的写性能靠write-ahead-log WAL。写操作会更新B+tree上的index node和 data node。Redo-log记录新增内容，顺序落到磁盘中。但B+tree的更新操作不会实时地反映在磁盘中（因为太慢了），而是现在内存记录更新的dirty page, 到了实时时机在flush到磁盘中。

B+tree的index可以为clustered index和secondary index。两者的区别在于leaf node存放的是否为数据data tuple。Clustered index的leaf node存储的就是data tuple，secondary index存放的是指向data tuple的指针地址。

Cluster index的优点：

Cluster index的索引和data tuple在同一文件(e.g., innoDB中的.idb文件)，查找方便。Cluster index的leaf data node之间指针指向邻居，range search更方便。

Cluster index的缺点：

index的更新代价较高。插入数据的速度严重依赖插入顺序。顺序插入key比较相邻的数据速度更快。插入新的data tuple时，出现较慢的node split。

InnoDB中b+ tree的持久化

在InnoDB中读数据通过B+ treeindex定位到data page, load到内存读取其中的data tuple。对于写操作，采用WAL。先写日志，在写磁盘。写磁盘时，通过buffer pool，利用顺序写比随机写性能好的特点。日志写完后，对应new data page的修改并不着急落实在磁盘上，而是现在buffer pool保存对应的new data page, 这时候也成为了dirty page，因为同一个page此时内存和磁盘已经是不同的数据了。Buffer pool先保存着new data page, 看合适的时机再落盘flush dirty page。

具体总结buffer pool的功能：

在内存中保留磁盘上被缓存页的内容。对disk page的修改先缓存起来，并不直接修改disk的数据。如果请求的page在内存中，直接返回。如果请求的page不在内存 同时buffer pool有可用的空间，buffer pool从disk上load这个page。如果请求的page不在buffer pool无可用的空间，buffer pool调用缺页置换策略，以一种算法选择一些页面换出。被换出的页面如果是dirty page到flush到磁盘上。

页面置换策略:

FIFO：先进先出，简单直白LRU：最近最久未使用，淘汰cold page。CLOCK：将page的引用和与之关联的访问位(visit bit, 标志是否在过去一圈clock时间中被应用)保存在环形缓冲区中。以时钟形式更新每个page的visit bit，将为0的页面换出。核心还是淘汰cold pageLFU：最小使用频率。直觉上LRU更为合理，但实际实现中数据结构复杂内存占用过高。CLOCK往往是cost-effective的实现。

InnoDB flush dirty page的时机：

内存中的redo log写满了。系统自动停止更新操作开始落盘，腾出空间。内存不足发生缺页。想要访问的一个page在磁盘，需要load到buffer pool。但内存没空间了，所以要腾出一些空间。DB空闲时后台flush dirty page。DB关闭时，所有dirty page也自动落盘。

刚刚介绍InnoDB中对应着buffer pool，还有一个change pool，这里也介绍下：

buffer pool是管理index page， data page的更为general的内存池。change pool的场景更narrow，主要应用在非唯一普通index page (non-unique secondary index page)。当需要修改这个non-unique secondary index page，同时这个index page此刻并没有在buffer pool。正常逻辑是先从disk中load这个index page到buffer pool，然后进行修改, 修改同时写redo log, 之后找机会再落盘dirty page同步到磁盘中。正常的逻辑我们可称为in-place update，就是对于这个index page的修改，需要即刻完成。为了完成这个逻辑，需要两次disk操作（load page到buffer pool和写redo log）。change pool的作用就是打破这个正常逻辑，我先记录这个page上的修改，但是并不load到buffer pool, 而是之后找合适机会再load，可以理解为是一种lazy update。好处是，只需要一次disk操作（写redo log）。

详细描述下这个好处：

时刻time 0

想要update一个non-unique secondary index page x。在change pool中记录这个修改（一次内存操作）。同时写入redo log（为了安全恢复，一次disk操作）。在时刻time 0后，写index page的操作就可以提交返回了。

时刻time 1

有对index page x的访问需求，这时候必须要load到buffer pool了（一次disk操作）。从change pool中读取对应的修改，合并操作。

继续回到InnoDB的buffer pool，其主要的实现结构是feel 链，双向链表，维护data page的信息。

介绍两个小优化知识点：

预读失效

预读read-ahead, 提前把一些page放到buffer pool，预判后面会用到。但最终没有被用到，就是预读失效。

优化思路是，让预读失败的页，尽可能早地从buffer pool中置换出去。当真正被用到的page, 挪到buffer pool的链表头部。将链表分为两部分，new sublist取和old sublist区。两区首尾相连。new page（预读page）加入到缓冲池，只先加入到old sublist。只有当这个预读page真的被用到了，再移动到new sublist。如果这个预读page没被用到，直接移出去。

2. buffer pool污染

当SQL查询执行，需要扫描大量数据时，可能会把缓冲池的所有page都给置换出去，导致大量热数据被换出，性能下降。

优化思路是：1) 不让批量扫描的page进入new sublist，而是先放入old sublist。2）一个page真的后面(比如1s之后)又被用到，才挪到new sublist。3）对于old sublist中设定一个停留时间 （old_blocks_time=1s），在这个时间内的数据访问，并不会导致page被认为hot而挪到new sublist。

举个全表扫描的例子：

扫描中，需要load的page，都先放到old区。一个数据页有很多data tuple, 因此一个data page可能在SQL query执行中被多次访问。但因为顺序访问，多次访问一个page之间时间间隔也不会超过1s。所以在这个短时间的访问内的page，仍留在old区。可以理解为这些page是fake hot，只在过去1s内因为顺序扫描而多次访问而已，后面就用不到了。继续扫描，之间的page也不会访问了，因此不会被移动到new区，最终在old区中被淘汰。

B+tree暂且告一段落，把目光转向LSM tree log-structured merge tree。

B+tree中的数据查询，修改，增加绝大部分情况触发random IO。磁盘对于random IO的处理是比较慢的，传统的hard disk drive HDD就是一盘磁带，和我们小时候听的步步高磁带是一个东西。我们需要定位一个page时，HDD需要物理转动磁头去寻址到对应的柱面，再到对应的扇区。random IO就这样来回来去，非常耗时。现在的SSD因为不需要物理刺头寻道时间，所以会相对较快一些。但sequential IO好于random IO的条件依然成立。我对SSD的知识有限，大家有兴趣去了解下。LSM的出现就是了尽量避免随机写操作，采用append-only来实现顺序追加写。LSM中所有的insert, update操作都是不需要定位到原来的位置，而是追加在文件后面。当然，这样会导致，一份数据有多个历史版本存在，数据不断膨胀。这时就需要定期进行合并compaction操作。把对应冗余的数据清除合并。B+tree的形式是一个tree, 数据存在leaf node。LSM tree的形式是sorted string table SSTable, 其中包括index table和data table。LSM tree一般一key-value pair的形式存储数据。Index table存放的就是index key和其在data table中的偏移量。Data table就是保存这些key-value pair。

LSM tree的结构

LSM tree的结构从存储架构来看，其在内存和disk都有对应的table。内存中一般称为memtable, disk中的称为SSTable。数据的update insert会先放到memtable中，当到了一定的阈值比如100MB，就在后台刷到磁盘成为SSTable。Memtable一般采用skip list结构存储数据，整体保持有序性。当memtable刚刚刷到SSTable时，称为这个SSTable所在的层级为Level 0。 Level 0的SSTable到了一定的数据规模（比如1GB），会合并compaction操作到Level 1的SSTable。Level 1的SSTable到了一定的数据规模（比如10GB），会合并compaction操作到Level 2的SSTable。.....

LSM的数据操作

Insert和update操作都不能直接修改原来的数据。这些操作也被看为一个新的数据，附上一个timestamp。这样对于相同key值的数据，LSM tree里可能记录着时间顺序上增长的数据版本。删除就直接标记一个bit作为tombstone即可，表示这个key值的数据在时间t被删除了。LSM的search操作，从内存的memtable中查找，如果有直接返回。内存没有就去找Level 0的SSTable, 找到了返回即可。Level 0的SSTable没有转而去找Level 1的SSTable, 找到了返回即可....当在更低层的level的SSTable找到就可返回的原因是，约低层的数据是当前这key值对应的最新的数据。要在一个很大的SSTable中判断是否有一个key存在，常用的优化是bloom filter。它的底层是一个bit map。给定一个key值，bloom filter一般采用多个hash function去映射这个key值，然后把对应的hash结果的bit置为1。比如key=12, bloom filter有三个hash function, hash_1(12) = 2, hash_2(12) = 6, hash_3(12) = 18。那么就把bit map上的第2,6,18位置为1。这样回答达到的效果是：1）当bloom filter说一个key值不存在是，那么它一定不存在。2）当bloom filter说一个key值存在时，那么它只是可能存在。为什么，因为hash function毕竟会有冲突，可能别的key值把bit 2,6,8位置都给占了。

LSM的合并策略

LSM tree的艺术还是在于lazy IO。把当前的操作全用append的sequential IO来解决，但该付出的最终逃不过。Append的数据后期还是需要compaction层层融合到SSTable。Compaction一直是LSM tree的优化主题，很多大文件SSTable之间进行合并，而且层层都要，还是很大的性能考验。LSM tree因为层层compaction，也导致了写放大的问题。一个update操作，在于B-tree找到对应位置修改即可，但是在LSM tree上，level 0到level N基本每层都要应为这个update操作而进行merge触发IO。过去2个decades，每年SIGMOD, VLDB, CIDR都会有paper讨论LSM compaction，很多优秀的paper，大家可以多多阅读。这里推荐几篇比较喜欢的C. Luo and M. J. Carey. LSM-based Storage Techniques: A Survey. The VLDB Journal, 29(1):393–418, 2020Niv Dayan and Stratos Idreos. Dostoevsky: Better spacetime trade-offs for lsm-tree based key-value stores via adaptive removal of superfluous merging. In SIGMOD, 2018. S. Dong, M. Callaghan, L. Galanis, D. Borthakur, T. Savor, and M. Strum. Optimizing Space Amplification in RocksDB. In CIDR, 2017S. Sarkar, D. Staratzis, Z. Zhu, and M. Athanassoulis. Constructing and Analyzing the LSM Compaction Design Space. In VLDB , 2021.

下一篇开始介绍存储引擎-并发控制