大学生如何实现一个数据库？
工作两年回看，当时自豪的作品已变成了玩具; 不变的是对技术的好奇和热情; 18年底加入PingCAP，真正迈入了DB领域; 有兴趣的同学可看看TiDB系列文章，并贡献PR成为contributor，满足自己好奇心并为开源社区创造价值; 对PingCAP有兴趣的同学也可内推实习或者工作;  ===================== 更新了一篇boltDB的模型和分析文档， 感兴趣的同学可以看看 https://github.com/qw4990/blog/tree/master/database/boltDB ===================== 大概半年前, 我收到了这个问题的邀请. 现在我数据库完成, 我觉得我有底气回答这个问题了. 算是对我这将近一年工作的总结, 也当做是一些分享(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: 开始编程 这个过程就没什么可以多说的了, 就是考验编程功底. 将模型抽象清楚, 然后开始写:) 我前后的尝试过程大致为: 整个过程是痛苦并快乐的, 毫无疑问非常锻炼编程和抽象能力. ======================================================================================================================================== 阶段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.最后, 最重要的还是自己思考. 遇到一个问题, 解决一个问题.   ========================================================================================================================================  本人很少上知乎, 虽然在知乎发了这篇文, 但还是鼓励大家多动手, 少上知乎. (会被和谐么? 最后, 感谢一直给予我帮助的左老师:)