Open guevara opened 2 weeks ago
数据库存储引擎的实现 https://ift.tt/KMm4fFi
简单记录一下这个拖了许久的小轮子
目前实现了一个简单的数据库存储引擎，具有的功能
实现的细节大部分是自己推敲，整体思路是参考书籍，整个过程写起来还是挺愉悦的
要实现持久化，就是要定制从内存到外存之间的转换协议，我的做法是针对一个表（内存）对应一个文件（外存）
文件是单一的，但内部需要分页，正常人的做法是分页大小为 4K 字节的倍数，比如 InnoDB 采用 16K，我选择 8192 字节，实测相对快一点
InnoDB
每个页都需要分配一个 page id，由于页是固定大小的，很容易在文件中定位，比如 page_id*8192
page id
page_id*8192
既然分页了，那就需要确定需要怎样、多少的页类型来足以描述整个表，现在只谈表头页（head page）和记录页（record page）
head page
record page
表头页用于描述一个表的信息（其实也没啥信息）
在目前没怎么开始具体设计的时候，很容易构造出一个草稿
---------------------------------- | MAGIC | FIRST_FREE | TABLE_INFO | ---------------------------------- |← 8192 Bytes →|
这是一个像样的表头页，简单描述以下信息
magic
first free
table info
column
key attribute
设定每个表对应的表头页的 page id 为 0，可以很方便的在首次访问就能得到表的描述信息以构造内存中所需描述的对象
0
细节：表头页加载后就单独常驻内存，这样可不拖慢整个系统的性能
记录页（数据页）则用于描述行记录，单个记录页可描述多个行数据，能描述多少个取决于不同行记录的大小
那么该怎么描述，才能得知这个页能否存入这条记录，这个页怎样才能\(O(1)\)获取数据？
这里采用分槽页（slotted page）来解决这两个问题
slotted page
→------------------------------------- ↑ ↓ ----------------------------------------------------·---------------------------------- | MAGIC | END_FREE | PTR_CNT | PTR[0] | PTR[1] | .. | REC[N-1] | REC[N-2] | .. | REC[0] | -------------------------------------------------------------------------------·------- = N ↓ ↑ |← FIXED →| →---------------------------------------------
这里显得稍微复杂，逐一解释
end free
free space
ptr
rec
ptr_cnt
ptr[i]
rec[i]
可以看出，前三个域的大小是已知固定的，而指针个数等于记录个数，是动态变化的
一开始 end free 肯定是偏移量为 8192，表示 \([ptr[ptr \ cnt],end \ free)\) 是一段唯一、连续可用的区域，很简单就能算出一条记录能否插入，无需逐一尝试各种碎片段
每次插入记录，就分配出一个新的指针，由于有 ptr cnt，可以很容易的知道新的指针 ptr 开始分配的地方，而记录 rec 则从当前的 end free 往前移需要的字节数再填充，完成后 end free 和 ptr 都指向该记录的首字节（其实 end free是 可以省略的，但是方便）
ptr cnt
end free是
而删除记录则相对麻烦点，比如记录在各个 rec 域的中间，删除等价于把（位置在左边的）前面的记录都后移覆盖到当前记录的最后一个字节，修改 end free 和改动位置的记录对应的 ptr，维持 free space 总是中间一段连续区域的性质，以提高空间利用率。虽然逐个偏移记录看着有点慢，但是利用 memmove 性能也不差，ptr 的修改也不涉及到很多字节数目，整体不亏（虽然还残留有问题，但后面我会指出）
memmove
现在到了设计记录页中 rec 内部的阶段，他们有可能是整型，整型可能 4 字节、8 字节，甚至可能是字符串，多长也不知道，因此需要记入足够的信息
简化问题，假定单一的记录不会特别大，8K 足以满足所有单一记录的要求，可以这样来设计
------------------------------------------------------------ | (998244) | (28,7) | (10^12+7) | (35,5) | "kiseki" | "jojo" | ·----------·--------·-----------·--------·----------·------- 0 4 12 20 28 35 |← FIXED →|
第一个为 4 字节整型，我们直接记入其数值，第三个长整型同理
而第二、第四个列为可变长的字符串，可以记入 (offset,length) 以避免接下来的逐个偏移（PS.这里的 length 是算入结束符的）
(offset,length)
length
这样的好处是左半边的大小是固定的，这在 column 的信息中已经决定好了，这样可方便记录任意变长类型
至于不同列的类型判断的问题，还是要看表头信息
数据页已经设计好了，那就要设计怎样找到数据页的索引协议，
这里使用了常规的 B+ 树索引，我的实现是非聚簇的，因为实在是太方便了
（聚簇索引想了下也不需要太大改动，就是我认为可能需要两套不同的平衡因子还有数据和键值杂糅在一起的设计容易出🐞）
这个没啥好说的，就是查询、增加、删除的操作实现，给个图方便琢磨
至于外存上的页面设计，bplus page 大概如下所示
bplus page
---------------------------------------------------------------- | MAGIC | PARENT | KEY_CNT | CHILD_CNT | --KEYS-- | --CHILDREN-- | ---------------------------------------------------------------- |← FIXED →|
由于前面各段都是固定的，平衡因子 b 很容易通过简单的式子在编译时求出最优解
b
而对于表头页，我们需要加一个小的段来表示它的 root 的 page id
root
我在实现上妥协的一点是，对于内部节点，由于采用和叶子节点相同的结构，children 中的儿子指针是 8 字节的 offset<<32 | page_id 的形式实现，offset 是用于给叶子节点定位到记录页的第 offset 个指针，这会带来一定的浪费，因为内部节点只需要 pageid 即可，但它实在是太方便了
children
offset<<32 | page_id
offset
pageid
另外，删除操作真正的实现我觉得很复杂，虽然写了一套，但后来还是改成了 LAZY 操作，直接把叶的儿子节点置 0，这样不仅方便而且还减少调整树的形态的开销，并且避免了前面记录页的删除操作带来的管理混乱）
LAZY
其实挺简单的，就是个 LRU 的淘汰置换，不考虑全表扫描等致命操作，效率还是可以的，有一个小的优化是可以用数组映射数值较小的 page_id，而少部分交给 map 进行额外映射
LRU
page_id
map
在具体的实现上，可能比较麻烦的地方标记脏的操作，我的做法是额外分一个类，用 read_op 和 write_op 来对 page_id 寻址（从缓存中获得）和分配页面类，每一次写操作的寻址都标记脏，而读操作则直接分配一个 const 限定的页强制限制写操作，bplus_tree 不得持有任何一个 page_id 而必须通过该类来访问节点，当然还有一些读缓存和写缓存之类的小优化，不细说了
read_op
write_op
const
bplus_tree
如果一个页是确实要删除，那么与其让它变成空洞文件，不如回收利用，这里需要表头页来进行配合
一个 free page 是极其简单的结构，只有 magic 和 next_page
free page
next_page
我们通过表头的 first free，可以直接拿到要复用的页，并把 first free 置为当前复用页的 next_page
看到这应该能想出完整方案了，就是一个插头的过程，不细说
另外再聊一个没啥用处的优化，就是对于大部分的页，可以只初始化（覆盖）几个或十几个字节就能完成复用，而不用强行 8K 都要初始化，看看前面的固定区域都是非常小的，道理挺简单
最后，我在实际过程中还是把这个复用给砍了，因为既然采用 LAZY 的策略，那还需要什么回收，可以等到重建过程直接整理碎片即可（然而没写）
毕竟我说的是存储引擎，不是完整的 DBMS
这个交给 SQLite 完成，它提供了 Virtual Table 机制，可以翻一下官方文档
Virtual Table
剩下需要实现的就是面向接口编程，提供迭代器给 SQLite 即可（谁愿意写 parser 啊）
当然还是要考虑如何断定能否使用索引、常规数据类型的转换、隐式 rowid 的创建等琐碎问题，这里是我写的最磨蹭的地方
原来的设想：简单的溢出页，在记录页中再加一个 next 段来维护一个页链表
next
后来的设想：既然是大型的记录，直接另开一个文件单独存储这个行记录，而在原来的页中只保留一个可寻址到该文件的句柄，然后解析工作丢给应用层
最后的设想：大型记录为啥不用纯粹的文件系统？不写了
目前的事务使用的是简单的一次封锁，虽然比较简单，但我觉得并不比两阶段封锁（2PL）要差
原因：
至于为啥不写更好的 MVCC 那肯定是太难实现了。。。
该模型下不需处理事务冲突级别的回滚（写互斥了，也不存在死锁冲突，因此不用 abort），只针对崩溃恢复（突然掉电，不正常结束直接 kill，其实点个叉干掉 shell 也算的）进行处理
用到的日志分为三种：undo / redo / commit，为了方便连 start 标记都省了，并且粒度是页
undo
redo
commit
start
日志的记录方式都是统一的：三种日志不管任何事务全部放在同一个 [表文件名]log 文件中，每次添加都用 append 方式追加到文件末尾，每次追加都是 [日志页][内容页] 的形式，通过日志页中记录的事务信息来决定内容页该怎么用
[表文件名]log
append
[日志页][内容页]
在追加的过程中，如果用 u/r/c 来简写前面三种日志，可以确定事务肯定是这种形式 xxxxxcxxxxxcxxxxc，x 表示任意的 u 或 r，描述同一个页的 u 肯定在 r 之前，而 c 与 c 之间肯定是描述同一事务的日志
什么时候添加 undo：第一次写操作前，并强制刷新磁盘
什么时候添加 redo：最后一次写操作后，commit 前
什么时候添加 commit：事务结束时
commit 后：把事务带来的修改更新到全局的已提交缓冲，新的事务从该缓冲中访问并拷贝为私有的页
如果是只读操作（不存在事务状态），对页的访问则直接访问已提交缓冲，否则访问事务私有页
（这部分显得有点多此一举，因为我本来是想写多版本控制的。。）
恢复过程：
log
xxxxxc
一些细节：
fsync
FILE*
fd
fflush
（其实实现上的琐碎事比上面的多得多）
实现 MVCC+ 并发 B-link 协议！
更新时间是贾老板回国的同一天
让我们一起，为梦想窒息 (ノﾟ∀ﾟ) ノ
《数据库系统实现》（大部分看不下去）
《数据库系统概念》（通俗易懂，但是中文版的伪代码描述有误，谨慎）
last update: 20/4/20
数据库存储引擎的实现
https://ift.tt/KMm4fFi
简单记录一下这个拖了许久的小轮子
Overview
目前实现了一个简单的数据库存储引擎，具有的功能
（即将完成）大型记录存储实现的细节大部分是自己推敲，整体思路是参考书籍，整个过程写起来还是挺愉悦的
持久化的实现
要实现持久化，就是要定制从内存到外存之间的转换协议，我的做法是针对一个表（内存）对应一个文件（外存）
文件是单一的，但内部需要分页，正常人的做法是分页大小为 4K 字节的倍数，比如
InnoDB采用 16K，我选择 8192 字节，实测相对快一点每个页都需要分配一个
page id，由于页是固定大小的，很容易在文件中定位，比如page_id*8192既然分页了，那就需要确定需要怎样、多少的页类型来足以描述整个表，现在只谈表头页（
head page）和记录页（record page）表头页
表头页用于描述一个表的信息（其实也没啥信息）
在目前没怎么开始具体设计的时候，很容易构造出一个草稿
这是一个像样的表头页，简单描述以下信息
magic：用于校验它是否为head pagefirst free：第一个空闲的page id，这涉及到页的复用和分配table info：文本形式的表信息，记录各个column、key attribute的细节设定每个表对应的表头页的
page id为0，可以很方便的在首次访问就能得到表的描述信息以构造内存中所需描述的对象细节：表头页加载后就单独常驻内存，这样可不拖慢整个系统的性能
记录页
记录页（数据页）则用于描述行记录，单个记录页可描述多个行数据，能描述多少个取决于不同行记录的大小
那么该怎么描述，才能得知这个页能否存入这条记录，这个页怎样才能\(O(1)\)获取数据？
这里采用分槽页（
slotted page）来解决这两个问题这里显得稍微复杂，逐一解释
magic：校验它是record page的魔数end free：空闲区域（free space）的结尾偏移量，总是指向最后的ptr指向的记录rec的第一个字节ptr_cnt：ptr的个数，使得实际存在的ptr范围为 \([0,ptr \ cnt)\)ptr[i]：记录指针，指向某个记录的第一个字节rec[i]：真正的行记录可以看出，前三个域的大小是已知固定的，而指针个数等于记录个数，是动态变化的
一开始
end free肯定是偏移量为 8192，表示 \([ptr[ptr \ cnt],end \ free)\) 是一段唯一、连续可用的区域，很简单就能算出一条记录能否插入，无需逐一尝试各种碎片段每次插入记录，就分配出一个新的指针，由于有
ptr cnt，可以很容易的知道新的指针ptr开始分配的地方，而记录rec则从当前的end free往前移需要的字节数再填充，完成后end free和ptr都指向该记录的首字节（其实end free是可以省略的，但是方便）而删除记录则相对麻烦点，比如记录在各个
rec域的中间，删除等价于把（位置在左边的）前面的记录都后移覆盖到当前记录的最后一个字节，修改end free和改动位置的记录对应的ptr，维持free space总是中间一段连续区域的性质，以提高空间利用率。虽然逐个偏移记录看着有点慢，但是利用memmove性能也不差，ptr的修改也不涉及到很多字节数目，整体不亏（虽然还残留有问题，但后面我会指出）行记录
现在到了设计记录页中
rec内部的阶段，他们有可能是整型，整型可能 4 字节、8 字节，甚至可能是字符串，多长也不知道，因此需要记入足够的信息简化问题，假定单一的记录不会特别大，8K 足以满足所有单一记录的要求，可以这样来设计
第一个为 4 字节整型，我们直接记入其数值，第三个长整型同理
而第二、第四个列为可变长的字符串，可以记入
(offset,length)以避免接下来的逐个偏移（PS.这里的length是算入结束符的）这样的好处是左半边的大小是固定的，这在
column的信息中已经决定好了，这样可方便记录任意变长类型至于不同列的类型判断的问题，还是要看表头信息
B+ 树索引
数据页已经设计好了，那就要设计怎样找到数据页的索引协议，
这里使用了常规的 B+ 树索引，我的实现是非聚簇的，因为实在是太方便了
（聚簇索引想了下也不需要太大改动，就是我认为可能需要两套不同的平衡因子还有数据和键值杂糅在一起的设计容易出🐞）
这个没啥好说的，就是查询、增加、删除的操作实现，给个图方便琢磨
至于外存上的页面设计，
bplus page大概如下所示由于前面各段都是固定的，平衡因子
b很容易通过简单的式子在编译时求出最优解而对于表头页，我们需要加一个小的段来表示它的
root的page id我在实现上妥协的一点是，对于内部节点，由于采用和叶子节点相同的结构，
children中的儿子指针是 8 字节的offset<<32 | page_id的形式实现，offset是用于给叶子节点定位到记录页的第offset个指针，这会带来一定的浪费，因为内部节点只需要pageid即可，但它实在是太方便了另外，删除操作真正的实现我觉得很复杂，虽然写了一套，但后来还是改成了
LAZY操作，直接把叶的儿子节点置 0，这样不仅方便而且还减少调整树的形态的开销，并且避免了前面记录页的删除操作带来的管理混乱）页级缓存
其实挺简单的，就是个
LRU的淘汰置换，不考虑全表扫描等致命操作，效率还是可以的，有一个小的优化是可以用数组映射数值较小的page_id，而少部分交给map进行额外映射在具体的实现上，可能比较麻烦的地方标记脏的操作，我的做法是额外分一个类，用
read_op和write_op来对page_id寻址（从缓存中获得）和分配页面类，每一次写操作的寻址都标记脏，而读操作则直接分配一个const限定的页强制限制写操作，bplus_tree不得持有任何一个page_id而必须通过该类来访问节点，当然还有一些读缓存和写缓存之类的小优化，不细说了页的回收复用
如果一个页是确实要删除，那么与其让它变成空洞文件，不如回收利用，这里需要表头页来进行配合
一个
free page是极其简单的结构，只有magic和next_page我们通过表头的
first free，可以直接拿到要复用的页，并把first free置为当前复用页的next_page看到这应该能想出完整方案了，就是一个插头的过程，不细说
另外再聊一个没啥用处的优化，就是对于大部分的页，可以只初始化（覆盖）几个或十几个字节就能完成复用，而不用强行 8K 都要初始化，看看前面的固定区域都是非常小的，道理挺简单
最后，我在实际过程中还是把这个复用给砍了，因为既然采用
LAZY的策略，那还需要什么回收，可以等到重建过程直接整理碎片即可（然而没写）SQL 解析
毕竟我说的是存储引擎，不是完整的 DBMS
这个交给 SQLite 完成，它提供了
Virtual Table机制，可以翻一下官方文档剩下需要实现的就是面向接口编程，提供迭代器给 SQLite 即可（谁愿意写 parser 啊）
当然还是要考虑如何断定能否使用索引、常规数据类型的转换、隐式 rowid 的创建等琐碎问题，这里是我写的最磨蹭的地方
大型记录存储
原来的设想：简单的溢出页，在记录页中再加一个
next段来维护一个页链表后来的设想：既然是大型的记录，直接另开一个文件单独存储这个行记录，而在原来的页中只保留一个可寻址到该文件的句柄，然后解析工作丢给应用层
最后的设想：大型记录为啥不用纯粹的文件系统？不写了
事务
目前的事务使用的是简单的一次封锁，虽然比较简单，但我觉得并不比两阶段封锁（2PL）要差
原因：
至于为啥不写更好的 MVCC 那肯定是太难实现了。。。
该模型下不需处理事务冲突级别的回滚（写互斥了，也不存在死锁冲突，因此不用 abort），只针对崩溃恢复（突然掉电，不正常结束直接 kill，其实点个叉干掉 shell 也算的）进行处理
用到的日志分为三种：
undo/redo/commit，为了方便连start标记都省了，并且粒度是页undo：负责记录撤回用的日志，保证可回滚到该事务任意写操作前的状态redo：负责重演，保证commit后确实执行commit：表示一个事务正常的结束日志的记录方式都是统一的：三种日志不管任何事务全部放在同一个
[表文件名]log文件中，每次添加都用append方式追加到文件末尾，每次追加都是[日志页][内容页]的形式，通过日志页中记录的事务信息来决定内容页该怎么用在追加的过程中，如果用 u/r/c 来简写前面三种日志，可以确定事务肯定是这种形式 xxxxxcxxxxxcxxxxc，x 表示任意的 u 或 r，描述同一个页的 u 肯定在 r 之前，而 c 与 c 之间肯定是描述同一事务的日志
什么时候添加
undo：第一次写操作前，并强制刷新磁盘什么时候添加
redo：最后一次写操作后，commit 前什么时候添加
commit：事务结束时commit后：把事务带来的修改更新到全局的已提交缓冲，新的事务从该缓冲中访问并拷贝为私有的页如果是只读操作（不存在事务状态），对页的访问则直接访问已提交缓冲，否则访问事务私有页
（这部分显得有点多此一举，因为我本来是想写多版本控制的。。）
恢复过程：
log文件，找出所有 commit 标记，依顺序处理xxxxxc过程中无论是undo还是redo都可任意顺序执行，因为日志记录的单位是页，也就是同一事务中的日志其实是相互独立的，又因为内容页直接记录的就是页，直接刷新覆盖到原来的表文件对应的位置就可以了一些细节：
fsync，但这个只有 unix api 才支持，没有一个好的跨平台方法（我的设计用的FILE*而不是fd），暂时只用了不太严格的fflush，起码用户态的崩溃是没问题的undo必不可缺，但commit时直接把要更新的redo页写到磁盘的表文件也不是不行，但这会牺牲磁盘的顺序读，这也是为什么把日志全部放在一个文件并用追加形式的原因（其实实现上的琐碎事比上面的多得多）
下一步
实现 MVCC+ 并发 B-link 协议！
更新时间是贾老板回国的同一天
参考
《数据库系统实现》（大部分看不下去）
《数据库系统概念》（通俗易懂，但是中文版的伪代码描述有误，谨慎）
last update: 20/4/20
via Caturra’s Blog
September 10, 2024 at 11:04AM