写自己的SQL执行引擎前言看了很多数据库的资料，笔者忍不住萌生了造一个数据库轮子的想法。验证自己对数据库底层原理的掌握是否扎实。在作者的github中将此数据库命名为Freedom。既然整体结构是用轮子做的，那么从前端的网络协议交互到后端的文件存储当然要搞定。下面是Freedom实现的整体结构，里面包含了实现的大致模块：最后的存储结构当然是经典的B+树结构。当然，B+树和文件系统块之间的转换是通过Buffer(Page)Manager进行的。当然，为了完成事务，必须使用WAL协议，它通过日志管理器进行操作。Freedom使用索引组织表，使用DruidSQLParse将sql翻译成相应的索引运算符，然后进行相应的语义操作。MySQLProtocol结构client/server之间的交互使用MySQL协议，这样可以很方便的与mysqlclient和jdbc进行交互。querypacketmysql使用3byte定长包头分包，然后解决读取tcp流的问题。然后在应用层用一个sequenceId判断数据包是否连续。结果集包mysql协议最复杂的部分是它对结果集的读取，增加了NIO方式的复杂度。Freedom在Netty框架下通过设置一系列读状态可以更好的解决这个问题。行包读取行格式也比较简单。如上图所示，只需要一步步解析即可。由于协议解析部分比较简单，这里不再赘述。SQLParseFreedom使用成熟易用的DruidSQLParse作为解析器。解析sql其实就是将文本表达的sql的语义表达为一系列的操作符（这里限于篇幅，只给出select中where过滤的原理）。where的处理，比如where后面的谓词，可以表示为一系列树状结构组织的SQL表达式，如下图所示：当访问层通过游标提供一系列行时，可以通过这个树表达式来过滤出符合where要求的数据。Druid使用Parse中常用的visitor来方便的处理上面的表达式计算操作。join的处理join最简单的处理方案就是对两个表进行笛卡尔积，然后通过上面的where条件进行过滤，如下图：Freedom对笛卡尔积进行归约的处理是因为Freedom使用B+树作为底层存储结构，所以B+树扫描（搜索）的范围可以通过where谓词来定义（即最大搜索键和最小搜索键在B+树种中的位置）。考虑sqlselecta.*,b.*fromt_archerasajoint_riderasbwherea.id>=3anda.id<=11b.idandb.id>=19b.id<=31，那么可以定义在id的索引上，a的扫描范围为[3,11]，如下图：b的扫描范围为[19,31]，如下图（假设两个表数据相同，方便作图）：scan从原来的15*15（共15个元素）减少到第2个循环减少到4*4个循环，也就是循环次数减少到7.1%。当然，如果有连接条件，那么Freedom会在底层游标递归处理的时候，对部分数据进行预过滤，进一步减少上层的过滤。B+Tree磁盘结构叶子磁盘结构Freedom的B+Tree存储在磁盘中。考虑到存储限制和键值变长，会变得很复杂。Freedom以页面为单位与磁盘交互。叶子节点和非叶子节点都由页面携带并刷新到磁盘。结构如下：一个元组（tuple/item）在一个页面中分为定长ItemPointer和变长Item。其中，ItemPointer存储的是对应item的起始偏移量和长度。同时，ItemPointer和Item向中心拉伸，如图所示。这种结构有效地组织了非固定长度的项目。Page中leaf和node节点的区别虽然leaf和node在page中的组织结构是一样的，但是它们的item所包含的item确实是不一样的。由于Freedom使用的是索引组织表，因此leaf在聚簇索引（clusterIndex）和二级索引（secondaryIndex）中的表示也存在差异，如下图所示：通过二级索引查找时，通过索引-key找到对应的clusterId，然后用clusterId在clusterIndex中找到对应的行记录。因为需要落盘，所以Freedom将item中index-key对应的pageno写入到node节点中，这样就可以方便的从磁盘中恢复出所有的索引结构。B+Tree在文件中的组织是有页结构的，我们可以把每个页大小的数据放在内存中，同时刷新页到对应的文件中。通过node.item中的pageno，我们可以很方便的将文件和内存结构相互映射。B+树在磁盘文件中的组织结构如下图：B+树在内存中对应的映射结构如下图：文件页和内存页的内容基本相同，除了内存页中的一些特殊字段，例如dirty等。每个索引都有一个B+树。在Freedom中，每个索引都是一个B+树。记录的插入和修改必须对所有B+树进行操作。B+Tree测试作者通过了一系列测试用例，比如向B+树中插入随机变长记录并放入磁盘，修复了几个非常奇葩的cornercase。B+Tree的todo作者这里只是完成了一个最简单的B+树结构，没有给它加并发修改的锁机制，也没有记录B+树运行时的日志，保证B+树在灾难性的情况下这样由于宕机的一致性，所以即使已经完成了这么多的工作量，距离高并发高可用的bptree还有非常大的距离。MetaDatatable的元信息是通过createtable创建的。创建完成后，元信息会放在磁盘上，以便Freedom在重启时加载表信息。每个表的元信息只占一页，依然复用页结构，主要存储聚簇索引和二级索引的信息。meta信息对应的item如下图所示：如果想让mybatis自动生成关于Freedom的代码，需要实现一些特定的SQL来显示Freedom的meta信息。这是在笔者的另一个项目骑手中实现的。原理如下图所示：mybatis-generator在实现以上四种SQL后，可以通过jdbc从Freedom获取meta信息，然后自动生成代码。事务支持由于Freedom目前不保证并发，所以只使用最简单的WAL协议进行事务支持。原子性是通过记录redo/undolog来实现的。Redo/undo日志协议格式Freedom每次进行修改操作都会生成一个日志，记录修改前（undo）和修改后（redo）的行信息。Redo用于回滚，redo用于宕机恢复。结构如下图所示：WAL协议WAL协议很好理解，就是在事务提交前，将当前事务产生的所有日志记录刷到磁盘。Freedom自然也做了这个操作，让宕机后可以通过日志恢复所有数据。回滚的实现由于undo是记录在日志中的，一个事务的回滚可以直接通过日志来undo。如下图：宕机恢复如果在刷完所有页面后关闭Freedom，可以通过加载页面获取原始数据。但是如果突然宕机，比如kill-9之后，可以通过WAL协议中记录的redo/undolog来恢复所有数据。由于时间和精力所限，作者没有实现基于LSN的checkpoint机制。Freedom运行gitclonehttps://github.com/alchemystar/Freedom.git//并没有做打包和部署的工作，所以最简单的方法是在java编辑器中运行alchemystar.freedom.engine.server.main。下面是笔者对Freedom的实际操作实例：joinquerydeleterollbackFreedomtodoFreedom还有很多工作要做，比如层次锁机制和MVCC等，由于工作忙而耽误了。于是笔者看了MySQL源码的实现了解锁的原理和MVCC的实现，写了两篇博客。比自己做容易多了^_^。MVCChttps://my.oschina.net/alchemystar/blog/1927425两级锁https://my.oschina.net/alchemystar/blog/1438839结语刚开始制作的过程很热情很开心车轮。但是，随着系统越来越大，越来越复杂，进度会越来越慢。时不时地，你要推翻你原来的假设重新设计，然后协同修改所有关联的代码，就像泥潭一样。越陷越深。至此，笔者体会到软件工程最重要的就是控制复杂性！保持简洁的界面和优雅的设计是实现大型系统的必要条件。本文转载自微信公众号《Bug解决之路》，可通过以下二维码关注。转载本文请联系BUG解决公众号。
