文档章节

自己动手写SQL执行引擎

无毁的湖光-Al
 无毁的湖光-Al
发布于 05/20 13:57
字数 2672
阅读 3.6W
收藏 152

阿里云携手百名商业领袖、技术大咖,带您一探行进中的数字新基建!>>>

自己动手写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)的行信息,undo用来回滚,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的设计写出来,希望大家能有所收获。
image

学习MySQL视频课程

github链接

https://github.com/alchemystar/Freedom

码云链接

https://gitee.com/alchemystar/Freedom

© 著作权归作者所有

无毁的湖光-Al

无毁的湖光-Al

粉丝 531
博文 37
码字总数 70616
作品 0
浦东
后端工程师
私信 提问
加载中

评论(42)

s
spleepycat
佩服佩服
无毁的湖光-Al
无毁的湖光-Al 博主
:)
yong230
yong230
博主你好,可否讲讲如何实现模板引擎原理,抽象语法树解析等
无毁的湖光-Al
无毁的湖光-Al 博主
粗略搞过但没深入钻研
木九天
木九天
6
无毁的湖光-Al
无毁的湖光-Al 博主
多谢 :)
SvenAugustus
SvenAugustus
这个厉害了
无毁的湖光-Al
无毁的湖光-Al 博主
:)
牛逼的小菜鸟
牛逼的小菜鸟
厉害厉害,佩服,我每次想造轮子的时候,也是一样,越想越复杂,最终都没下手……
无毁的湖光-Al
无毁的湖光-Al 博主
但你写下第一行代码的时候 你就成功了一半
kppom
kppom
膜拜大佬,我当初花了将近一年的时间才完成技术积累到勉强可用的SQL模拟器,ACID只实现了一个持久性。大佬是一个人写的吗?
无毁的湖光-Al
无毁的湖光-Al 博主
是呀 不过是看了一堆书才下笔的
t
teleport
无毁的湖光-Al
无毁的湖光-Al 博主
:)
yong9981
yong9981
一个月做成这样很不错了,但是把时间花在前人已走过的路上有点不值,数据库已经有太多版本了。建议找一个有实用价值的目标。
无毁的湖光-Al
无毁的湖光-Al 博主
纯粹为了造轮子开心:)
Y
Y292450104
启动完以后如何 进入命令行哈。
无毁的湖光-Al
无毁的湖光-Al 博主
用mysql客户端连 用户名 密码 代码里面有
Y
Y292450104
很赞
Iridium
Iridium
不錯不錯
无毁的湖光-Al
无毁的湖光-Al 博主
多谢多谢
Iridium
Iridium
這篇文檔的圖是用什麽軟件生成的?很漂亮。
无毁的湖光-Al
无毁的湖光-Al 博主
mac下的omni graffle
Iridium
Iridium
thanks
For update带来的思考

For update or not 起源 之所以想写这个专题,是因为最近在做一个抢占任务的实现。假设数据库很多个任务,在抢占发生之前任务的状态都是FREE。现在假设同时有一堆抢占线程开始工作,抢占线程...

osc_o1mwzw8v
2018/06/28
17
0
Django(app的概念、ORM介绍及编码错误问题)

day61 Django中的APP: 什么是APP?以及为什么要用APP? project --> 项目 (老男孩教育大学校) APP --> 应用 (Linux学院/Python学院/大数据学院/Java学院) 方便我们在一个大的Django项目中,管理...

osc_0n1rfouw
2019/01/19
14
0
springboot p6spy 打印完整sql

调试时打印出sql的需求,太正常不过了,mybatis也提供了这样的功能: mybatis:configuration: 但它打印的sql里,含有占位符? ==> Preparing: select id, name WHERE id in (?,?,?,?,?,?)==...

osc_57loaj8m
2018/12/20
15
0
你知道select count(*)底层究竟干了啥么?

作者:贾春生 https://blog.didiyun.com/index.php/2019/01/08/mysql-count/ “SELECT COUNT( ) FROM T” 是个再常见不过的 SQL 需求了。在 MySQL 的使用规范中,我们一般使用事务引擎 Inno...

Java进阶架构师
2019/04/27
0
0
Python爬虫进阶——爬虫框架概述 - 知乎

综述 爬虫入门之后,我们有两条路可以走。 一个是继续深入学习,以及关于设计模式的一些知识,强化Python相关知识,自己动手造轮子,继续为自己的爬虫增加分布式,多线程等功能扩展。另一条路...

Python爬虫教程
2019/10/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Java Spring Boot VS .NetCore (九) Spring Security vs .NetCore Security

谈到安全,如现在市面上有的 OAuth2 \ OIDC -OpenId Connect ,身份认证、授权等,下面先来说下Java Security 这一块的东西非常多复杂,不能是Spring Security 还是 .NetCore Security,一点一...

战略板儿砖
23分钟前
9
0
一行Python代码就可以下载任意网站视频,零基础小白也能轻松学会

对于Python爬虫很多人都不陌生,可以用它来批量下载文字、图片、视频等,其中涉及的知识点也是比较多的,但是Python中有一个方法,一行代码就能爬取任意网站上面的视频,只要你安装了Python环...

Python教授
25分钟前
10
0
技术分享 | InnoDB 的索引高度

作者:洪斌 爱可生南区负责人兼技术服务总监,MySQL ACE,擅长数据库架构规划、故障诊断、性能优化分析,实践经验丰富,帮助各行业客户解决 MySQL 技术问题,为金融、运营商、互联网等行业客...

爱可生
28分钟前
14
0
RabbitMq在低并发下处理失效订单的应用

RabbitMQ 基本概念 Message 消息,消息是不具名的,它由消息头和消息体组成。消息体是不透明的,而消息头则由一系列的可选属性组成,这些属性包括routing-key(路由键)、priority(相对于其...

JLLang
30分钟前
13
0
[分享]ApiPost-预(后)执行脚本常用方法集合

本文主要讲解接口管理工具ApiPost的预执行脚本和后执行脚本里,常见的响应参数变量和常用方法集合。 ApiPost简介: ApiPost是一个支持团队协作,并可直接生成文档的API调试、管理工具。它支持...

小台6
30分钟前
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部