学生如何实现一个数据库？
现在的问题是我太弱了,对数据库的理解只限于简单概念,有哪些好的书可以看?是实现一个Oracle,还是MYSQL的数据库,或是其它类型?
我打算在两年内完成这个项目.(那个学长也是搞ACM的,水平很高,他大四了,准备用一年时间来实现一个代码量十万行的数据库)
大概半年前, 我收到了这个问题的邀请.
现在我数据库完成, 我觉得我有底气回答这个问题了.
算是对我这将近一年工作的总结, 也当做是一些分享(zhuangX).
我大致说一下我从一开始做, 到完成我的作品, 大致经历了哪些阶段, 以做参考.
这里是我作品的github: GitHub - qw4990/NYADB2: NYADB2
PS:
因为大家对数据库的认知和了解都不同, 所以我的切入点必定无法满足所有人.
不过我想会关注这个问题的人, 大多应该都是用过简单的数据库功能, 感觉非常好奇, 想自己实现一个的人, 就同一年前的我一样.
下面我描述了我实现DB的各个阶段, 你可以在任意一个阶段停下, 然后实现它.
========================================================================================================================================
阶段1: 无事务, 单线程, 仅存在于内存的数据库.
该状态下的数据库, 其实就是一个”索引结构”+”语法分析器”.
语法分析器分析SQL语句, 然后根据逻辑, 去执行相应的操作.
索引结构则是用来快速查询.
由于该版本仅存在于内存, 所以只要你会一些常见的索引算法, 即可完成, 可以称之为”简易内存数据库”.
如你会B+树算法, 就可以实现一个B+树, Bt.
它实现了两个接口, Bt.Insert(key, value) -> void, Bt.Search(key) -> value.
再实现一个”语法分析器”.
如来了一条语句”Insert into student value (tony, 22, 123)”.
”语法分析器”分析该语句, 将value包裹一下, 选取一个该value的键值key.
然后调用 Bt.Insert(key, value).
之后执行”Read from student …” 其实也就是分析一下, 然后执行Bt.Search(key).
该版本数据库完成.
========================================================================================================================================
阶段2: 无事务, 单线程, 不可靠的磁盘数据库
“磁盘”表示该版本将信息存放在磁盘上.
“不可靠”表示, 当数据库被非正常结束时, 不保证重启后, 数据库内容还会正确.
2.1: 思路描述
该版本也非常简单, 直接在版本1上修改.
可以这样, 如你索引结构的最小单位为Unit, (如B+树的每个节点就是一个Unit).
你将Unit编码成二进制数据, 然后为每个Unit, 在某个文件中, 分配一段固定的空间, 用来存放它.
于是, 当你需要Unit的信息是, 你从该文件的固定位置读入.
当修改Unit的信息后, 你再将它写到那个固定位置.
如此一来, 数据就被存放于磁盘上了.
2.2: 实现
这里为B+树提供一种最简单的思路.
首先将索引数据和实际数据分别存放于两份文件, 称之为IndexFile, DB.
B+树有一个BALANCE_NUMBER, 简称BN, 为定值, 那么一个B+树节点最多有2*BN个(key, value)的键值对.
我们将key固定为uint64, value固定为uint64类型.
那么一个B+树节点最多占用(8+8)*2*BN这么多byte, 将其表示为MAX_BYTES.
于是, 就可以这样来编码B+树了.
规定根节点在IndexFile的位移为0.
每当创建新的节点时, 在IndexFile尾部, 追加MAX_BYTES大小的空间.
然后将该空间在IndexFile的位移, 作为这个新节点的”位置”, 用该空间存放新节点.
于是, B+树内部节点的value就用来存放”对应子节点的位置”.
叶节点的value, 也被作为”位置”, 指向了该条记录在DB中的位移.
2.3: 优化
上述实现会频繁的读写磁盘文件, 效率影响甚大.
为了解决这个问题, 可以加入一个模块, 这个模块分页管理IndexFile文件, 并对其进行必要的缓存, 以加快访问效率.
关于分页管理细节, 缓存算法, 不展开说了.
========================================================================================================================================
阶段3: 单事务, 单线程, 可靠的磁盘数据库
版本3在2的基础上, 同时支持了事务和数据库可靠性.
3.1: 关于事务
首先需要了解事务的基本概念, 参考<<数据库系统概念>>.
事务有ACID的性质, 由于现在是单线程版本, 所以不考虑其隔离性(I).
对于ACD这几个性质, 通常配合一定的”日志机制”完成.
于是需要去了解常见的”日志机制”.
这里推荐<<数据库系统概念>>日志恢复的那几章节.
3.2: 实现
有了”日志机制”, 具体实现的时候还要考虑一些更加细节的东西.
这里是Sqlite的一篇官文, 描述了一些错误会怎么发生, 应该对操作系统做什么样的假设.
不必了解该文档每个细节, 但是可以扩展下思路: How To Corrupt An SQLite Database File
这里是Sqlite官方介绍怎么实现原子性的文档: Atomic Commit In SQLite
同样不需要了解每个细节, 可以扩展下思路.
3.3: 个人总结
通常, 利用设计好的日志机制来保证事务的ACD性质.
然后利用对操作系统的一些假设, 来保证关键信息的原子性修改, 如数据库的”Boot”信息等.
如在我自己的实现中, 我就假设了操作系统的”rename”是原子性的.
========================================================================================================================================
阶段4: 多事务, 多线程, 可靠的数据库
前面三个阶段已经有一些内容了, 但是和多线程下的情况相比, 微不足道.
4.1: 可串行化调度
首先需要了解操作冲突的概念, 可串行化调度, 以及解决该问题的”两段锁协议”等, 推荐<<数据库系统概念>>.
两段锁协议会带来一个新的问题, 死锁.
于是, 你还需要去了解解决死锁的一些办法.
我使用的是有向图判环. <<数据库系统概念>>中有一定的介绍.
4.2: 解决读写冲突
使用”两段锁”能够完成可串行化调度, 但是它会造成”读写阻塞”, 很影响数据库的效率.
当然, 你也可以不解决该问题.
不过我借鉴了Postgresql, 引用了MVCC(多版本并发控制)来解决该问题.
MVCC的资料就大家自行搜索.
总体思路大致是: 为每条数据维护多个版本, 如果事务1锁定了该条数据, 而事务2准备读取的话, 就返回给事务2更老的版本.
4.3: 事务隔离度
还是得先了解隔离度的基本概念: 事务隔离
然后在MVCC的基础上, Postgresql通过维护各个版本对事务的可见性, 来实现了多种隔离度.
关于Postgresql怎么实现MVCC, 也请大家自行搜索, 或者直接看我的模型中的VM模块, 我借鉴了此方法.
4.4: 并发的索引
除了事务本身需要进行并发控制, 之前那些没考虑并发的模块, 也要加上并发支持.
其中最重要的一个就是并发的索引结构.
B+树本身是不支持并发访问的, 为了让他支持并发, 需要设计一些协议, 或者更改B+树算法来保证其支持并发.
我借鉴了一份文档的办法, 引入了这份B+树并发访问协议: Sixth Chapter
解决了该问题.
4.5: 总结
4.1到4.4大致说明了并发的情况下, 数据库会遇到哪些新的问题, 以及解决它们的办法.
虽然每个小节都只有几句话, 但是坑挺深, 每个问题都有各种各样的解决办法, 我只说了我使用到的.
但是, 比起单个解决这些问题, 最重要的, 是考虑怎么让它们组合起来使用也不会出错.
在组合这些方法的过程中, 你需要对这些方法做调整, 其实也就是设计并组合你自己的模块, 这非常重要, 也非常有趣.
如果想明白了上面各种方法怎么协同工作, 且发现不会引入新的问题, 那么可以把上面所有方法的总结抽象为一个完整”模型”了.
而下一步就是将这个”模型”实现.
========================================================================================================================================
阶段5: 实现版本4
想清楚了模型, 那么开始实现它.
5.1: 准备
首先需要肯定的是将会在编程中用到并发, 需要去了解一些常见的并发概念, 问题, 以及解决方法.
如临界区, 信号量, 锁, 读者写者问题, 哲学家就餐问题等概念.
接着你需要选择一门并发支持较好的语言(我选的是Go).
然后去学习该语言的一些并发编程技巧.
5.2: 开始编程
这个过程就没什么可以多说的了, 就是考验编程功底.
将模型抽象清楚, 然后开始写:)
我前后的尝试过程大致为:
- 一开始尝试用c++写个单线程版本, 后面放弃了.
- 用java实现了一个单线程版本, 总共大概约1200行.
- 尝试用java实现多线程版本, 最后放弃了.
- 用Go实现了一个多线程版本, 最后代码加注释大致10000行.
- 重构了Go的多线程版本, 得到现在的版本, 注释加代码大概7500行.
整个过程是痛苦并快乐的, 毫无疑问非常锻炼编程和抽象能力.
========================================================================================================================================
阶段6:测试
6.1: 各模块测试
这里的测试包括分模块测试和整体测试.
你设计的各个模块之间, 应该是可以通过指定一些"协议"来解耦的.
于是模拟这些协议, 你的模块应该是可以单独被独立测试的.
如模块A对模块B的访问遵循了协议C.
现在你想单独测试模块B, 那么可以编写一个MockA, 模拟A的操作, 并且遵守协议C.
这样讲B和MockA一起测试.
6.2: 整体测试
其实我自己的DB在整体测试上做的是不够的.
目前我针对一些特定功能, 做了一些手动的测试.
关于更好的测试方法目前我也还在思考中.
========================================================================================================================================
其他问题:
实实在在的实现一个数据库当然还有其他很多问题, 如Server与Client的交互方法, 制定自己的SQL文法, 怎么有效优雅的解析SQL语句, 数据库运行状态的监控, 对日志文件进行自动归档等.
我上面描述的是”数据库引擎”需要解决的重点问题, 这些问题就略过了.
这些问题都是可以被作为"甜点", 在"主菜"完成后慢慢品尝的.
所以分清楚哪些问题是重点, 哪些问题是可以之后慢慢解决的也很重要.
总的来说, 只要你设计好了自己的"模型", "模型"之外的问题, 几乎都可以被作为"甜点"了.
========================================================================================================================================
总结:
数据库的功能点非常多, 选好要解决的问题, 然后去查找对应问题的解决办法.
接着将这些单个问题的解决办法, 组合成一个能正确工作的模型.
每个数据库都有自己的模型, 设计这个模型是数据库最好玩, 也是最难的地方, 这是"主菜".
将模型抽象好, 用合适的方法去将其实现, 这是难点二.
这个难点就没有多说的了, 就考验编程功底.
最后就是对数据库进行测试, 以及不断的完善.
则是"甜点"了.
所以数据库不管在理论, 还是工程上, 还是在考验人的耐心上, 真是都挺难啊哈哈= =.
========================================================================================================================================
一些可能会用到的资料推荐:
1.可以看一下简单的自动机实现, 用于分析语法.
2.B+树算法, 常见的缓存算法等, 推荐看wiki.
3.<<数据库系统概念>>, 这本书可以看看有关事务, 恢复, 锁的那几章, 以做基础概念.
4.<<inside sqlite>>, 这本书介绍了sqlite的后端模型, 原书非常短小, 大概80到100页.
5.http://www.sqlite.org/howtocorrupt.html,http://www3.sqlite.org/atomiccommit.html: 这两篇Sqlite官方文档, 当做开阔思路.
6.<<SQLite Database System: Design and Implementation>>, 也是介绍Sqlite实现的书, 和<<inside sqlite>>有部分重复, 可以选看.
7.MVCC的相关文档以及Postgresql的可见性逻辑, 请自行谷歌.
8.然后, 就是我自己实现的数据库模型文档了: https://www.gitbook.com/book/qw4990/nyadb/details
9.最后, 最重要的还是自己思考. 遇到一个问题, 解决一个问题.
========================================================================================================================================