不用数据库实现数据库功能
简略版本
阶段1: 无事务, 单线程, 仅存在于内存的数据库.
该状态下的数据库, 其实就是一个”索引结构”+”语法分析器”.
语法分析器分析SQL语句, 然后根据逻辑, 去执行相应的操作.
索引结构则是用来快速查询.
由于该版本仅存在于内存, 所以只要你会一些常见的索引算法, 即可完成, 可以称之为”简易内存数据库”.
数据结构
如你会B+树算法, 就可以实现一个B+树, Bt.
它实现了两个接口, Bt.Insert(key, value) -> void, Bt.Search(key) -> value.
语法分析器
再实现一个”语法分析器”.
1 如来了一条语句”Insert into student value (tony, 22, 123)”.
2 ”语法分析器”分析该语句, 将value包裹一下, 选取一个该value的键值key.
然后调用 Bt.Insert(key, value).
3 之后执行”Read from student …” 其实也就是分析一下, 然后执行Bt.Search(key).
该版本数据库完成.
阶段2: 无事务, 单线程, 不可靠的磁盘数据库
“磁盘”表示该版本将信息存放在磁盘上.
“不可靠”表示, 当数据库被非正常结束时, 不保证重启后, 数据库内容还会正确.
思路描述
该版本也非常简单, 直接在版本1上修改.
可以这样, 如你索引结构的最小单位为Unit, (如B+树的每个节点就是一个Unit).
你将Unit编码成二进制数据, 然后为每个Unit, 在某个文件中, 分配一段固定的空间, 用来存放它.
于是, 当你需要Unit的信息是, 你从该文件的固定位置读入.
当修改Unit的信息后, 你再将它写到那个固定位置.
如此一来, 数据就被存放于磁盘上了.
实现
这里为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中的位移.
优化
上述实现会频繁的读写磁盘文件, 效率影响甚大.
为了解决这个问题, 可以加入一个模块, 这个模块分页管理IndexFile文件, 并对其进行必要的缓存, 以加快访问效率.
关于分页管理细节, 缓存算法, 不展开说了.
单事务, 单线程, 可靠的磁盘数据库
首先需要了解事务的基本概念, 参考<<数据库系统概念>>.
事务有ACID的性质, 由于现在是单线程版本, 所以不考虑其隔离性(I).
对于ACD这几个性质, 通常配合一定的”日志机制”完成.
于是需要去了解常见的”日志机制”.
这里推荐<<数据库系统概念>>日志恢复的那几章节.
实现
有了”日志机制”, 具体实现的时候还要考虑一些更加细节的东西.
这里是Sqlite的一篇官文, 描述了一些错误会怎么发生, 应该对操作系统做什么样的假设.
不必了解该文档每个细节, 但是可以扩展下思路: How To Corrupt An SQLite Database File
这里是Sqlite官方介绍怎么实现原子性的文档: Atomic Commit In SQLite
同样不需要了解每个细节, 可以扩展下思路.
个人总结
通常, 利用设计好的日志机制来保证事务的ACD性质.
然后利用对操作系统的一些假设, 来保证关键信息的原子性修改, 如数据库的”Boot”信息等.
如在我自己的实现中, 我就假设了操作系统的”rename”是原子性的.
多事务, 多线程, 可靠的数据库
串行化调度
首先需要了解操作冲突的概念, 可串行化调度, 以及解决该问题的”两段锁协议”等, 推荐<<数据库系统概念>>.
两段锁协议会带来一个新的问题, 死锁.
于是, 你还需要去了解解决死锁的一些办法.
我使用的是有向图判环. <<数据库系统概念>>中有一定的介绍.
解决读写冲突
使用”两段锁”能够完成可串行化调度, 但是它会造成”读写阻塞”, 很影响数据库的效率.
当然, 你也可以不解决该问题.
不过我借鉴了Postgresql, 引用了MVCC(多版本并发控制)来解决该问题.
MVCC的资料就大家自行搜索.
总体思路大致是: 为每条数据维护多个版本, 如果事务1锁定了该条数据, 而事务2准备读取的话, 就返回给事务2更老的版本.
事务隔离度
还是得先了解隔离度的基本概念: 事务隔离
然后在MVCC的基础上, Postgresql通过维护各个版本对事务的可见性, 来实现了多种隔离度.
关于Postgresql怎么实现MVCC, 也请大家自行搜索, 或者直接看我的模型中的VM模块, 我借鉴了此方法.
并发的索引
除了事务本身需要进行并发控制, 之前那些没考虑并发的模块, 也要加上并发支持.
其中最重要的一个就是并发的索引结构.
B+树本身是不支持并发访问的, 为了让他支持并发, 需要设计一些协议, 或者更改B+树算法来保证其支持并发.
我借鉴了一份文档的办法, 引入了这份B+树并发访问协议: Sixth Chapter
解决了该问题.
总结
4.1到4.4大致说明了并发的情况下, 数据库会遇到哪些新的问题, 以及解决它们的办法.
虽然每个小节都只有几句话, 但是坑挺深, 每个问题都有各种各样的解决办法, 我只说了我使用到的.
但是, 比起单个解决这些问题, 最重要的, 是考虑怎么让它们组合起来使用也不会出错.
在组合这些方法的过程中, 你需要对这些方法做调整, 其实也就是设计并组合你自己的模块, 这非常重要, 也非常有趣.
如果想明白了上面各种方法怎么协同工作, 且发现不会引入新的问题, 那么可以把上面所有方法的总结抽象为一个完整”模型”了.
准备
首先需要肯定的是将会在编程中用到并发, 需要去了解一些常见的并发概念, 问题, 以及解决方法.
如临界区, 信号量, 锁, 读者写者问题, 哲学家就餐问题等概念.
接着你需要选择一门并发支持较好的语言(我选的是Go).
然后去学习该语言的一些并发编程技巧.
各模块测试
这里的测试包括分模块测试和整体测试.
你设计的各个模块之间, 应该是可以通过指定一些"协议"来解耦的.
于是模拟这些协议, 你的模块应该是可以单独被独立测试的.
如模块A对模块B的访问遵循了协议C.
现在你想单独测试模块B, 那么可以编写一个MockA, 模拟A的操作, 并且遵守协议C.
这样讲B和MockA一起测试.
整体测试
其实我自己的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.最后, 最重要的还是自己思考. 遇到一个问题, 解决一个问题.
参考大牛文章
https://www.zhihu.com/question/35382593
https://web.stanford.edu/class/cs346/2015/
其它文章
我从开始设计的时候，就没有打算做一个严格意义上的数据库，只是打算做一个数据存储工具。
我在公司负责是车联网数据的聚集，我工作的公司目前使用三套数据存储工具。前两套是公司其他程序员开发的。
第一套是单机版本的快速文件存储，不支持事务，使用小文件存储数据；采取二级索引。每个终端每天生成一个数据文件，文件内数据通过B+树检索；每个终端所有日期的数据生成一个索引文件，文件内日期数据通过B+树检索。
第二套是分布式云存储，在第一套单机版本的快速文件存储基础上，增加分布式功能。由路由服务器和存储服务器集群两部分组成，典型的路由-存储的星状拓扑结构；
第三套是基于hbase，spark和kafka的云存储，datanode和namenode结构，选举机制。
我任职的公司的存储服务主要存储依据时间顺序上报的行车记录数据（GPS数据附加脉冲车速、脉冲里程、燃油累计使用量、AD油位、驾驶员卡号、锁车状态和开关量等行车记录数据）。
而我在公司的主要职责是开发维护聚集车辆行车记录数据的定时服务和实施服务。
1：定时服务的主要功能：
处理存储在数据存储的行车记录数据，清洗数据，分析每辆车和每个驾驶员的车辆驾驶行为和统计油气耗数据，将聚集的结果数据保存到数据库。
2：实时服务的主要功能：
基于数据库中历史结果数据和数据存储中的行车记录数据，提供精确到秒的每辆车和每个驾驶员的油气耗统计结果和驾驶行为分析结果。
所以我针对我的业务场景，在设计阶段就对tennbase存储服务做了一些特色设计。
tennbase数据存储是单机版的快速文件存储，支持简单事务，支持快速插入和查询，线程安全，不支持SQL查询。
功能接口
tennbase提供支持事务和无事务两类接口：
1：提供无事务的增删改查接口。
public boolean insert(int key, Colunm colunm);
public boolean update(int key, Colunm colunm);
public boolean delete(int key);
public Colunm search(int key);
2：提供支持事务的增删改查接口
public Trans beginTrans()public boolean commit(Trans tid)
public boolean rollback(Trans tid)
public byte state(Trans tid)
public boolean insert(int key, Colunm colunm, Trans tid) throws AbortTransException;
public boolean update(int key, Colunm colunm, Trans tid) throws AbortTransException;
public boolean delete(int key, Trans tid) throws AbortTransException;public boolean rollback(int key, Trans tid);
public boolean commit(int key, Trans tid);
public Colunm search(int key, Trans tid);作者：tenn
链接：https://www.zhihu.com/question/35382593/answer/110796963
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
模块设计
tennbase 由数据管理、文件管理、索引管理、日志管理、事务管理、目录管理和任务管理七部分组成。
数据管理主要功能有：
1：存储数据
a：采用只追加方式管理数据文件，不支持对数据文件内存储数据的修改和删除；
b：支持按照分页和偏移量随机读取。
2：管理数据缓存，管理page和block。
a：在内存中缓存新增的数据文件分页；
b：在内存中缓存新增的和修改的索引文件分页（节点）。
文件管理，使用Java的RandomAccessFile和FileChannel实现，和主要功能有：
1：管理数据文件：
a：通过页码和索引访问数据文件；
b：数据内容保存在格式化的数据块（block）中；
c：添加数据时，先创建分页，然后在分页中依据数据长度申请数据块，数据块的最大长度
为65535个字节。
2：管理索引文件；
a：通过固定分页管理索引文件。每个节点对应一个分页；
分页的长度是固定的，每个分页最多存储512个单位（B*tree索引树的平衡阀值设为256）；
b：支节点和叶节点分裂出的新节点以新增分页的方式追加在索引文件尾部；
c：以分页在索引文件中的偏移量作为分页和节点的编号；
3：管理日志文件。
a：记录事务文件，记录内容包括事务ID、事务状态、索引关键字（key），原始数据页码
和偏移量、变更后的数据页码和偏移量；
b：服务初始化阶段，执行undo日志和redo日志。
索引管理
使用b*tree实现，在线程安全方面，参考了@张原嘉的 B+树并发控制协议 Sixth Chapter 。
主要功能有：
1：查询数据：
a：服务初始化阶段，在b*tree中加载索引文件中的数据关键字结点。
叶节点中存储索引int类型的关键字（key）、数据内容（value）在数据文件中的
页码（pageid）和偏移量（offset）、数据状态（是否可见）和相邻左右节点的信息；
b：通过b*tree快速检索单条数据。范围查询时，通过叶节点左右结点以链表方式
快速遍节点。
c：根据叶节点中数据文件中的页码和偏移量，加载数据文件中的分页。解析格式化的数据
2：添加数据：
a：先在数据文件中追加数据内容后返回页码和偏移量；
b：在索引中检索数据，如果数据已经存在，直接覆盖结点的页码和偏移量；
如果数据不存在则直接插入。
c：异步刷新缓存到缓存快照文件。
3：修改数据：
a：先在数据文件中追加数据内容后返回页码和偏移量；
b：在索引中检索数据，如果数据已经存在，直接覆盖结点的页码和偏移量；
如果数据不存在则不会插入。
4：删除数据：
a：逻辑删除。在索引中检索数据，如果数据已经存在且数据状态为可见，
则将数据状态置为不可见。
事务管理
仅仅实现了非常简单的事务管理策略
1：只记录写操作，新增、修改和删除数据时会把数据标记为脏数据，
并记录旧的数据状态，分别对应不可见状态、旧的数据文件分页和偏移量及可见状态；
2：如果其他事务或者非事务操作读取未提交的数据，会返回旧数据的快照或者状态。
3：执行写操作前检查互斥，如果其他事务或者非事务操作修改未提交的数据会抛出中断异常。
4：发现互斥之后抛出中断异常，进行事务回滚。
5：事务未终结阶段，索引数据可能会更新到文件中，查询时候以缓存中的数据为准。
该状态下，如果服务重启，会在服务初始化阶段，执行undo日志，回滚未提交的操作。
目录管理
类似于数据表的元数据管理，管理多个索引树和对应的数据文件和索引文件。
任务管理
1：服务非正常终结时，刷新变更的索引分页内容到索引快照文件。
2：后台每隔3秒钟刷新变更的索引分页内容到索引文件。
功能改进
1：早期版本执行插入、修改和删除操作后，会检查索引缓存中是否有脏页，如果有脏页则
立即同步到磁盘上的索引文件。
改进点：
采用异步更新模式；每个数据库表启动一个后台线程，每隔3秒同步脏页到磁盘上的索引
文件。当处理连续批量多次插入的时候，相当于把多次操作合并，然后一次同步到索引文件，
减少了磁盘IO读写的次数。写入数据速度从每秒钟2000次提高到50000次。
2：早期版本使用节点中key集合的平均值作为索引文件的分页ID。这样容易造成索引树中
节点（分页）的ID频繁抖动，每次执行增加和删除操作都要同步整个索引文件。
改进点：
采用分页在索引文件中的偏移量作为分页和节点的编号，这样分页ID与数据内容无关，
只需要修改相关特定分页就可以了。而且当索引树的节点分页时候，新增节点以新分页追加
在索引文件的尾部，对索引文件的操作也简化为更新单个分页和追加单个分页。
3：早期版本是直接对索引文件进行修改，这样如果数据不同步就会破坏索引文件中索引树的
结构，导致索引失效和数据丢失。
改进点：
服务启动时候，将索引文件复制一份快照文件。后台线程会把索引缓存同步到快照文件中。
而当服务中止时候，有一个响应程序退出事件的钩子进程会把整个索引树输出到一个临时索
引文件中，然后把正式索引文件重命名，再把临时索引文件重命名为正式索引文件。
这样就有了三个索引文件的副本。后续我考虑如何利用这三个索引文件和日志来恢复数据，
不过我还没有想清楚具体的恢复策略，可能需要先增加版本号和设置还原点的功能。
索引索引恢复这部分的功能还没有实现。
4：因为系统设计时候，考虑主要用于存储依据时间顺序上报的行车记录数据。而b*tree索引中
节点存储数据的利用率比较低，导致索引文件中有差不多一半的空间是空白。
改进点：
参考 何登成 从MySQL Bug#67718浅谈B+树索引的分裂优化 何登成的技术博客。
在保留随机插入B*tree索引树的同时，实现顺序插入b*tree索引树，不过这部分代码暂时还未
实现。
后续工作
1：增加多版本并发控制；
2：完善索引恢复功能；
3：增加元数据管理模块；
4：增加数据文件瘦身清理功能
（因为目前数据文件采用追加模式，数据即使没有插入或者修改成功，
也会追加到数据文件中，因此数据文件中有很多废弃的碎片）；
5：优化B*tree随机索引树的分裂方式，提高容载率。
6：实现二级索引，增加根据数据保存日期的B*索引树。
7：完备测试。
8：设计目标达到可以在32位操作系统下处理单个容量达到500M的索引文件。
我如果再往下做，有如下几个思路：
如果横向去做，就要做负载均衡，查询引擎和冗余备份。
如果纵向去做，就做列式数据库。
如果向底层做, 优化存储格式和文件资源回收，用一个大文件来存多个不同table的数据。
参考资料
数据库系统实现(第2版)
OceanBase内存事务引擎.pdf
OceanBase-破解数据库高可用难题.ppt
Inside+SQLite.pdf
京公网安备 11010502036488号