自己动手写SQL执行引擎
自己动手写SQL执行引擎
前言
在阅读了大量关于数据库的资料后,笔者情不自禁产生了一个造数据库轮子的想法。来验证一下自己对于数据库底层原理的掌握是否牢靠。在笔者的github中给这个database起名为Freedom。
整体结构
既然造轮子,那当然得从前端的网络协议交互到后端的文件存储全部给撸一遍。下面是Freedom实现的整体结构,里面包含了实现的大致模块:
最终存储结构当然是使用经典的B+树结构。当然在B+树和文件系统block块之间的转换则通过Buffer(Page) Manager来进行。当然了,为了完成事务,还必须要用WAL协议,其通过Log Manager来操作。
Freedom采用的是索引组织表,通过DruidSQL Parse来将sql翻译为对应的索引操作符进而进行对应的语义操作。
MySQL Protocol结构
client/server之间的交互采用的是MySQL协议,这样很容易就可以和mysql client以及jdbc进行交互了。
query packet
mysql通过3byte的定长包头去进行分包,进而解决tcp流的读取问题。再通过一个sequenceId来再应用层判断packet是否连续。
result set packet
mysql协议部分最复杂的内容是其对于result set的读取,在NIO的方式下加重了复杂性。 Freedom通过设置一系列的读取状态可以比较好的在Netty框架下解决这一问题。
row packet
还有一个较简单的是对row格式进行读取,如上图所示,只需要按部就班的解析即可。
由于协议解析部分较为简单,在这里就不再赘述。
SQL Parse
Freedom采用成熟好用的Druid SQL Parse作为解析器。事实上,解析sql就是将用文本表示 的sql语义表示为一系列操作符(这里限于篇幅原因,仅仅给出select中where过滤的原理)。
对where的处理
例如where后面的谓词就可以表示为一系列的以树状结构组织的SQL表达式,如下图所示:
当access层通过游标提供一系列row后,就可以通过这个树状表达式来过滤出符合where要求的数据。Druid采用了Parse中常用的visitor很方便的处理上面的表达式计算操作。
对join的处理
对join最简单处理方案就是对两张表进行笛卡尔积,然后通过上面的where condition进行过滤,如下图所示:
Freedom对于缩小笛卡尔积的处理
由于Freedom采用的是B+树作为底层存储结构,所以可以通过where谓词来界定B+树scan(搜索)的范围(也即最大搜索key和最小搜索key在B+树种中的位置)。考虑sql
select a.*,b.* from t_archer as a join t_rider as b where a.id>=3 and a.id<=11 b.id and b.id>=19 b.id<=31
那么就可以界定出在id这个索引上,a的scan范围为[3,11],如下图所示:
b的scan范围为[19,31],如下图所示(假设两张表数据一样,便于绘图):
scan少了从原来的15*15(一共15个元素)次循环减少到4*4次循环,即循环次数减少到7.1%
当然如果存在join condition的话,那么Freedom在底层cursor递归处理的过程中会预先过滤掉一部分数据,进一步减少上层的过滤。
B+Tree的磁盘结构
leaf磁盘结构
Freedom的B+Tree是存储到磁盘里的。考虑到存储的限制以及不定长的key值,所以会变得非常复杂。Freedom以page为单位来和磁盘进行交互。叶子节点和非叶子节点都由page承载并刷入磁盘。结构如下所示:
一个元组(tuple/item)在一个page中分为定长的ItemPointer和不定长的Item两部分。 其中ItemPointer里面存储了对应item的起始偏移和长度。同时ItemPointer和Item如图所示是向着中心方向进行伸张,这种结构很有效的组织了非定长Item。
leaf和node节点在Page中的不同
虽然leaf和node在page中组织结构一致,但其item包含的项确有区别。由于Freedom采用的是索引组织表,所以对于leaf在聚簇索引(clusterIndex)和二级索引(secondaryIndex)中对item的表示也有区别,如下图所示:
其中在二级索引搜索时通过secondaryIndex通过index-key找到对应的clusterId,再通过 clusterId在clusterIndex中找到对应的row记录。
由于要落盘,所以Freedom在node节点中的item里面写入了index-key对应的pageno, 这样就可以容易的从磁盘恢复所有的索引结构了。
B+Tree在文件中的组织
有了Page结构,我们就可以将数据承载在一个个page大小的内存里面,同时还可以将page刷新到对应的文件里。有了node.item中的pageno,我们就可以较容易的进行文件和内存结构之间的互相映射了。 B+树在磁盘文件中的组织如下图所示:
B+树在内存中相对应的映射结构如下图所示:
文件page和内存page中的内容基本是一致的,除了一些内存page中特有的字段,例如dirty等。
每个索引一个B+树
在Freedom中,每个索引都是一颗B+树,对记录的插入和修改都要对所有的B+树进行操作。
B+Tree的测试
笔者通过一系列测试case,例如随机变长记录对B+树进行插入并落盘,修复了其中若干个非常诡异的corner case。
B+Tree的todo
笔者这里只是完成了最简单的B+树结构,没有给其添加并发修改的锁机制,也没有在B+树做操作的时候记录log来保证B+树在宕机等灾难性情况下的一致性,所以就算完成了这么多的工作量,距离一个高并发高可用的bptree还有非常大的距离。
Meta Data
table的元信息由create table所创建。创建之后会将元信息落盘,以便Freedom在重启的时候加载表信息。每张表的元信息只占用一页的空间,依旧复用page结构,主要保存的是聚簇索引和二级索引的信息。元信息对应的Item如下图所示:
如果想让mybatis可以自动生成关于Freedom的代码,还需实现一些特定的sql来展现Freedom的元信息。这个在笔者另一个项目rider中有这样的实现。原理如下图所示:
实现了上述4类SQL之后,mybatis-generator就可以通过jdbc从Freedom获取元信息进而自动生成代码了。
事务支持
由于当前Freedom并没有保证并发,所以对于事务的支持只做了最简单的WAL协议。通过记录redo/undolog从而实现原子性。
redo/undo log协议格式
Freedom在每做一个修改操作时,都会生成一条日志,其中记录了修改前(undo)和修改后(redo)的行信息,redo用来回滚,redo用来宕机recover。结构如下图所示:
WAL协议
WAL协议很好理解,就是在事务commit前将当前事务中所产生的的所有log记录刷入磁盘。 Freedom自然也做了这个操作,使得可以在宕机后通过log恢复出所有的数据。
回滚的实现
由于日志中记录了undo,所以对于一个事务的回滚直接通过日志进行undo即可。如下图所示:
宕机恢复
Freedom如果在page全部刷盘之后关机,则可以由通过加载page的方式获取原来的数据。 但如果突然宕机,例如kill -9之后,则可以通过WAL协议中记录的redo/undo log来重新 恢复所有的数据。由于时间和精力所限,笔者并没有实现基于LSN的检查点机制。
Freedom运行
git clone https://github.com/alchemystar/Freedom.git // 并没有做打包部署的工作,所以最简单的方法是在java编辑器里面 run alchemystar.freedom.engine.server.main
以下是笔者实际运行Freedom的例子:
join查询
delete回滚
Freedom todo
Freedom还有很多工作没有完成,例如有层次的锁机制和MVCC等,由于工作忙起来就耽搁了。 于是笔者就看了看MySQL源码的实现理解了一下锁和MVCC实现原理,并写了两篇博客。比起 自己动手撸实在是轻松太多了^_^。
MVCC
https://my.oschina.net/alchemystar/blog/1927425
二阶段锁
https://my.oschina.net/alchemystar/blog/1438839
尾声
在造轮子的过程中一开始是非常有激情非常快乐的。但随着系统越来越庞大,复杂性越来越高,进度就会越来越慢,还时不时要推翻自己原来的设想并重新设计,然后再协同修改关联的所有代码,就如同泥沼,越陷越深。至此,笔者才领悟了软件工程最重要的其实是控制复杂度!始终保持简洁的接口和优雅的设计是实现一个大型系统的必要条件。
收获与遗憾
这次造轮子的过程基本满足了笔者的初衷,通过写一个数据库来学习数据库。不仅仅是加深了理解,最重要的是笔者在写的过程中终于明白了数据库为什么要这么设计,为什么不那样设计,仅仅对书本的阅读可能并不会有这些思考与领悟。
当然,还是有很多遗憾的,Freedom并没有实现锁机制和MVCC。由于只能在工作闲暇时间写,所以断断续续写了一两个月,工作一忙就将这个项目闲置了。现在将Freedom的设计写出来,希望大家能有所收获。
学习MySQL视频课程
github链接
https://github.com/alchemystar/Freedom
码云链接
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
浅谈产品模型(Profile)在程序设计中的作用
引言 :物联网平台的一个重要功能就是资产管理,产品或者设备都可以看成是资产中组成部分,所以有时候说物联网平台可以进行产品管理和设备管理。通常应用物联网平台开发一套具有产品或者设备管理功能的系统的时候,必须定义产品模型(Profile)。很多物联网平台的使用文档中大都会介绍了如何建立满足平台要求的产品模型,但是很少说明为什么要建立产品模型,建立的产品模型跟程序设计有啥关系。因此很多开发者都会按照介绍完成产品模型的定义,但是不太理解为什么要建这个模型,时不时会想想,为啥要这个Profile。本文从产品模型(Profile)的定义的理解,Profile文件内容的分析,Profile文件与程序设计的联系三个部分的描述,力图能让开发者对Profile在程序设计中的作用有更深入的理解。个人经验有限,理解不正确的地方,希望大家多多包涵,一起讨论。 1.什么是Profile 在华为云的开发文档中能看到,Profile(即产品模型)是用来描述一款产品中的设备“是什么”、“能做什么”以及“如何控制该设备”的文件。如何理解这句话? 通常一款产品或者设备本身具有很多的物理属性或者功能,人们在这个产品的说明书中...
- 下一篇
微软开源 Windows 软件包管理器 winget,一行命令安装软件
除了正式发布Windows Terminal 1.0,微软在此次 Build 2020 大会上还宣布开源一个新工具:Windows Package Manager(winget),Windows 软件包管理器。 winget 由一个命令行工具和一组用于在 Windows 10 上安装应用的服务组成,可以帮助使用者快速轻松地发现地安装不同的工具,只需要使用一个命令即可: winget install <tool> winget 目前有搜索、显示和安装软件包等功能,与 apt-get、pip 等软件包管理器类似,微软介绍接下来还将提供卸载、软件包 list 与更新等功能。 对于开发者来说,可以使用 winget 命令行工具发现、安装、升级、删除和配置选定应用集。安装后,可以通过 Windows 终端、PowerShell 或 cmd 访问 winget。 而独立软件供应商(ISV)可以将 winget 用作集成工具和应用软件包分发渠道,通过使用开源仓库,ISV 可以将软件包(包括 .msix、.msi 与.exe 安装程序)提交到 winget,用户再通过 winget 命...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- MySQL8.0.19开启GTID主从同步CentOS8
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- Docker安装Oracle12C,快速搭建Oracle学习环境
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS7设置SWAP分区,小内存服务器的救世主