java学习基地

微信扫一扫 分享朋友圈

已有 1827 人浏览分享

自己动手写SQL执行引擎

[复制链接]
1827 2
本帖最初由 进修派 于 2020-12-7 19:20 编纂

本人入手写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的设想写出去,期望各人能有所播种。



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

举报 使用道具

回复

评论 2

酷到无边  vip年度会员  发表于 2020-12-22 19:07:45 | 显示全部楼层
站位支持

举报 使用道具

回复
今世伴明月  vip终身会员  发表于 2020-12-22 22:08:08 | 显示全部楼层
嘘,低调。

举报 使用道具

回复
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

0

关注

0

粉丝

138

主题
精彩推荐
热门资讯
网友晒图
图文推荐

Archiver|手机版|java学习基地 |网站地图

GMT+8, 2021-7-31 08:11 , Processed in 0.518575 second(s), 28 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.