大学生如何实现一个数据库？ 第1页

工作两年回看，当时自豪的作品已变成了玩具;

不变的是对技术的好奇和热情;

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: 开始编程

这个过程就没什么可以多说的了, 就是考验编程功底.

将模型抽象清楚, 然后开始写:)

我前后的尝试过程大致为:

1. 一开始尝试用c++写个单线程版本, 后面放弃了.
2. 用java实现了一个单线程版本, 总共大概约1200行.
3. 尝试用java实现多线程版本, 最后放弃了.
4. 用Go实现了一个多线程版本, 最后代码加注释大致10000行.
5. 重构了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.最后, 最重要的还是自己思考. 遇到一个问题, 解决一个问题.

========================================================================================================================================

本人很少上知乎, 虽然在知乎发了这篇文, 但还是鼓励大家多动手, 少上知乎. (会被和谐么?

最后, 感谢一直给予我帮助的左老师:)