简略版本阶段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./howtocorrupt.html, http://www3./atomiccommit.html: 这两篇Sqlite官方文档, 当做开阔思路. 6.<<SQLite Database System: Design and Implementation>>, 也是介绍Sqlite实现的书, 和<<inside sqlite>>有部分重复, 可以选看. 7.MVCC的相关文档以及Postgresql的可见性逻辑, 请自行谷歌. 8.然后, 就是我自己实现的数据库模型文档了: https://www./book/qw4990/nyadb/details 9.最后, 最重要的还是自己思考. 遇到一个问题, 解决一个问题. 参考大牛文章https://www.zhihu.com/question/35382593 https://web./class/cs346/2015/ 其它文章我从开始设计的时候,就没有打算做一个严格意义上的数据库,只是打算做一个数据存储工具。 我在公司负责是车联网数据的聚集,我工作的公司目前使用三套数据存储工具。前两套是公司其他程序员开发的。 第一套是单机版本的快速文件存储,不支持事务,使用小文件存储数据;采取二级索引。每个终端每天生成一个数据文件,文件内数据通过B+树检索;每个终端所有日期的数据生成一个索引文件,文件内日期数据通过B+树检索。 我任职的公司的存储服务主要存储依据时间顺序上报的行车记录数据(GPS数据附加脉冲车速、脉冲里程、燃油累计使用量、AD油位、驾驶员卡号、锁车状态和开关量等行车记录数据)。 而我在公司的主要职责是开发维护聚集车辆行车记录数据的定时服务和实施服务。 1:定时服务的主要功能: 所以我针对我的业务场景,在设计阶段就对tennbase存储服务做了一些特色设计。 功能接口
作者:tenn 模块设计 文件管理,使用Java的RandomAccessFile和FileChannel实现,和主要功能有: 2:管理索引文件; 3:管理日志文件。 索引管理 2:添加数据: 3:修改数据: 4:删除数据: 事务管理 目录管理 任务管理 功能改进 2:早期版本使用节点中key集合的平均值作为索引文件的分页ID。这样容易造成索引树中 3:早期版本是直接对索引文件进行修改,这样如果数据不同步就会破坏索引文件中索引树的 4:因为系统设计时候,考虑主要用于存储依据时间顺序上报的行车记录数据。而b*tree索引中 后续工作 我如果再往下做,有如下几个思路: 如果横向去做,就要做负载均衡,查询引擎和冗余备份。 如果纵向去做,就做列式数据库。 如果向底层做, 优化存储格式和文件资源回收,用一个大文件来存多个不同table的数据。 参考资料 数据库系统实现(第2版) OceanBase内存事务引擎.pdf OceanBase-破解数据库高可用难题.ppt Inside+SQLite.pdf
|
|