# JyDB **Repository Path**: he-junyang/jy-db ## Basic Information - **Project Name**: JyDB - **Description**: 使用java完成的简单数据库系统 - **Primary Language**: Unknown - **License**: MulanPSL-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 1 - **Forks**: 0 - **Created**: 2023-06-05 - **Last Updated**: 2023-06-06 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 1. JyDB 数据库 个人学习, 模仿声哥的 MY_DB, [教程地址](https://blog.csdn.net/qq_40856284/category_11504274.html) JyDB 是一个 Java 实现的简单的数据库，部分原理参照自 MySQL、PostgreSQL 和 SQLite。实现了以下功能： - 数据的可靠性和数据恢复 - 两段锁协议（2PL）实现可串行化调度 - MVCC 多版本并发控制 - 两种事务隔离级别（读提交和可重复读） - 死锁处理 - 简单的表和字段管理 - 简陋的 SQL 解析（因为懒得写词法分析和自动机，就弄得比较简陋） - 基于 socket 的 server 和 client ## 示例 ![](./media/示例.png) ## 项目启动: 个人 首先, 我们需要创建一个数据库, 通过IDEA, 我们设置如下并且启动 ![](./media/创建数据库.png) 启动后, 我们需要加载这个数据库, 并且打开服务, 设置如下并且启动 ![](./media/打开数据库.png) 最后, 我们启动客户端 com.hjy.frontend.Launcher : [Launcher.java](src%2Fmain%2Fjava%2Fcom%2Fhjy%2Ffrontend%2FLauncher.java) ## 项目启动: 官方 注意首先需要在 pom.xml 中调整编译版本，如果导入 IDE，请更改项目的编译版本以适应你的 JDK 首先执行以下命令编译源码： ```shell mvn compile ``` 接着执行以下命令以 C:\my\E\Java_document\JyDB\JyDB\tmp\db 作为路径创建数据库： ```shell mvn exec:java -Dexec.mainClass="com.hjy.backend.Launcher" -Dexec.args="-create C:\my\E\Java_document\JyDB\JyDB\tmp\db" ``` 随后通过以下命令以默认参数启动数据库服务： ```shell mvn exec:java -Dexec.mainClass="com.hjy.backend.Launcher" -Dexec.args="-open C:\my\E\Java_document\JyDB\JyDB\tmp\db" ``` 这时数据库服务就已经启动在本机的 9999 端口。重新启动一个终端，执行以下命令启动客户端连接数据库： ```shell mvn exec:java -Dexec.mainClass="com.hjy.frontend.Launcher" ``` ## 数据库结构以及文件存储结构概述 首先, 我们看数据库目录结构 ![](./media/数据库目录结构.png) db.bt : 用于存储第一张表的 uid db.db : 存储所有的数据, 例如行数据, 字段数据, 表数据, 等等 ![](./media/xxx.db.png) ![](./media/Page.png) ![](./media/DataItem.png) ![](./media/Entry.png) ![](./media/Node.png) ![](./media/string.png) ![](./media/Field.png) ![](./media/table.png) db.log : 存放日志内容, 便于恢复 ![](./media/Log.png) db.xid : 事务文件, 存储事务号 ![](./media/xid文件存储.png) ## 语句执行流程 见 [Table.java](src%2Fmain%2Fjava%2Fcom%2Fhjy%2Fbackend%2FtableManager%2FTable.java) insert语句 => 开始事务, 获得事务号 => 获取对应的表Table => 将插入的记录按照表字段名的顺序封装成byte[], 通过VersionManager封装成Entry, 用DataItem插入 => 提交事务 select语句 => 开始事务, 获得事务号 => 获取对应的表Table => 解析where语句, 获得其所有有可能的记录的uid => VersionManager 通过其事务号, 根据记录Entry可见性, 过滤uid, 查询出剩下的uid对应的记录, 返回结果 => 提交事务 update语句 => 开始事务, 获得事务号 => 获取对应的表Table => 解析where语句, 获得其所有有可能的记录的uid => VersionManager 通过其事务号, 根据记录Entry可见性, 过滤uid => 对可行的记录, VersionManager删除删除 => 然后 VersionManager新增一个新的修改后的记录 => 提交事务 delete语句 => 开始事务, 获得事务号 => 获取对应的表Table => 解析where语句, 获得其所有有可能的记录的uid => VersionManager 通过其事务号, 根据记录Entry可见性, 过滤uid => 对可行的记录, VersionManager删除 => 提交事务 其他语句类似... # 2. TransactionManager 事务管理器, 通过 XID 文件来维护事务的状态，并提供接口供其他模块来查询某个事务的状态 XID 文件的开头保存一个 8 字节的数字，记录 XID 文件中事务的个数，然后给每个事务分配 1 字节, 用来保存事务的状态 举个例子：第 1 个事务(xid, id =1)在文件中的状态就存储在 (xid - 1) + 8 字节处，因为 第 1 个事务是超级事务 ，永远是已提交状态(committed),不需要记录, 超级事务 xid = 0 ![img.png](./media/xid文件存储.png) TransactionManager 维护了一个 XID 格式的文件，用来记录各个事务的状态。JyDB 中，每个事务都有下面的三种状态： - active，正在进行，尚未结束, 标识为 0 - committed，已提交 , 标识为 1 - aborted，已撤销（回滚）, 标识为 2 通过类[TransactionManagerImpl.java](src%2Fmain%2Fjava%2Fcom%2Fhjy%2Fbackend%2FtransactionManager%2FTransactionManagerImpl.java) , 我们可以 1. 开启一个事务 2. 提交一个事务 3. 撤销一个事务 说到底, 其实就是对 xx.xid 文件的底层操作 # 3. DataManager 数据管理器, 也是最重要的模块 这个模块是比较底层的一个模块, 因为直接和二进制文件打交道(xxx.db文件), 向下直接读写文件，向上提供数据的包装 ## 计数缓存框架 在 com.hjy.backend.commons, 我们设置了一个缓存框架, 其算法为计数缓存 ![](./media/计数缓存.png) 继承了这个类的方法, 需要实现两个方法: - getForCache : 当资源不在缓存时的获取行为, 也就是如何创建一个资源 - releaseForCache : 当资源被驱逐时的释放行为 这里不在细说 ## 数据页 Page DataManager 向下对文件进行操作时, 也绝不是直接操作, 而是使用了一个数据页Page的对象进行抽象 一个数据页, 默认大小为 8K, 为了管理 Page, 我们创建了 PageCache 缓存对应管理 Page 页, 相对于的, PageCache 对应直接操作 xx.db 数据文件, 其能力如下: 1. 通过页面号, 直接从 xxx.db 中加载出 Page 对象 2. 对于脏页面(即在内存中修改但是在磁盘中未修改), 可以刷新进磁盘 3. 截断, 将多少页后数据全部清除(逻辑清除) 数据页也分为两种类型 ### 首页 也就是第一页, 这一页没有别的事情, 就是判断上一次数据库是否正常关闭 db启动时给100~107字节处填入一个随机字节，db关闭时将其拷贝到 108~115 字节 用于判断上一次数据库是否正常关闭, 如果是异常关闭，就需要执行数据的恢复流程。 ### 普通页 除了首页外, 其他都是普通页, 普通页二进制格式如下: [pageOffset][data] - pageOffset: 2 字节无符号数, 表示这一页的空闲位置的偏移量。剩下的部分都是实际存储的数据 - data: 实际存储的数据 普通页提供的能力是在 pageOffset 的地方插入数据, 或者在任何 pageOffset 地方插入数据 ## 数据项 DataItem 如果说Page是 DataManager 对二进制文件的抽象, 那么 DataItem 就是 DataManager对于上层模块的抽象, 在DataItem 中, 我们不需要再去思考数据的大小, 数据如何插入等底层的事情, 其二进制形容帮助我们完成了这一切 二进制格式如下: ```java // 其中 ValidFlag 占用 1 字节，标识了该 DataItem 是否有效。删除一个 DataItem，只需要简单地将其有效位设置为 0。 // DataSize 占用 2 字节，标识了后面 Data 的长度。 [ValidFlag] [DataSize] [Data] ``` 但是, 这样的二进制格式似乎不太顶用, 我们需要指定其放在哪个 Page 中, 以及这个Page的哪个位置, 于是 uid 横空出世 uid 可以位置标识一个 DataItem , 拥有 8 位, 前四位是PageId , 后四位是 PageOffset, 这个Uid 存储在 [Data] 的前8位 ## 页面索引 PageIndex 页面索引，缓存了每一页的空闲空间。用于在上层模块进行插入操作时, 能够快速找到一个合适空间的页面，而无需从磁盘或者缓存中检查每一个页面的信息。 JyDB 用一个比较粗略的算法实现了页面索引，一个页有 8K, 我们划分为不同的等级, 如 0.2K级, 0.4K级 ... 根据实验这需要的剩余空间大小, 我们给其对应的页面号PageId ## 日志 JyDB 提供了崩溃后的数据恢复功能。DM 层在每次对底层数据操作时，都会记录一条日志到磁盘上。 在数据库崩溃之后，再次启动时，可以根据日志的内容，恢复数据文件，保证其一致性。 日志的二进制文件，按照如下的格式进行排布： ```text [XChecksum][Log1][Log2][Log3]...[LogN][BadTail] ``` 其中 XChecksum 是一个四字节的整数，是对后续所有日志计算的校验和。Log1 ~ LogN 是常规的日志数据，BadTail 是在数据库崩溃时，没有来得及写完的日志数据，这个 BadTail 不一定存在。 每条日志的格式如下: ```text [Size][Checksum][Data] ``` 其中，Size 是一个四字节整数，标识了 Data 段的字节数。Checksum 则是该条日志的校验和 4位。 最核心的部分, 在于日志的**恢复** 日志分为修改型日志和新增型日志, 日志的类型不同, 恢复方式也不同, 每条日志 [Data]部分的格式也不同 - 新增型日志 [Data] 部分格式 : `[LogType] [XID] [PageID] [Offset] [Raw]` - LogType: 日志类型, 新增型日志是 0, 占一位 - XID : 事务号, 8位 - PageID : 页面号, 4位 - Offset : 页内偏移, 2位 - 修改型日志 [Data] 部分格式 : `[LogType] [XID] [UID] [OldRaw] [NewRaw]` - LogType: 日志类型, 新增型日志是 0, 占一位 - XID : 事务号, 8位 - UID : DataItem 唯一表示, 由PageId和Offset组成, 8位 恢复策略redo: 1. 正序扫描事务 T 的所有日志 2. 如果日志是插入操作 (Ti, I, A, x)，就将 x 重新插入 A 位置 3. 如果日志是更新操作 (Ti, U, A, oldx, newx)，就将 A 位置的值设置为 newx 撤销策略undo: 1. 倒序扫描事务 T 的所有日志 2. 如果日志是插入操作 (Ti, I, A, x)，就将 A 位置的数据删除 3. 如果日志是更新操作 (Ti, U, A, oldx, newx)，就将 A 位置的值设置为 oldx ## DataManager 对外暴露的模块, 用于操作数据 read方法可以通过一个 uid , 读取出一个 DataItem insert 方法可以进行插入数据 # 4. VersionManager 版本管理模块, 主打的就是一个保卫数据库的安全性(事务安全), 也就最难的一部分, 是 JyDB 的事务和数据版本的管理核心。 这个模块主要解决的问题是多个事务在执行时, 其操作之间的可见性, 以及事务的开始, 提交, 与回滚, 提交的数据将会被封装成一个Entry对象, 方便回滚和查看可见性 ## 2PL 与 MVCC 2PL : 两段锁协议 MVCC : Multi version Concurrency Control 多版本并发控制 VM 基于两段锁协议实现了调度序列的可串行化，并实现了 MVCC 以消除读写阻塞。同时实现了两种隔离级别。 首先来定义数据库的冲突，暂时不考虑插入操作，只看更新操作（U）和读操作（R），两个操作只要满足下面三个条件，就可以说这两个操作相互冲突： 1. 这两个操作是由不同的事务执行的 2. 这两个操作操作的是同一个数据项 3. 这两个操作至少有一个是更新操作 那么这样，对同一个数据操作的冲突，其实就只有下面这两种情况： 1. 两个不同事务的 U 操作冲突 2. 两个不同事务的 U、R 操作冲突 3. 那么冲突或者不冲突，意义何在？作用在于，交换两个互不冲突的操作的顺序，不会对最终的结果造成影响，而交换两个冲突操作的顺序，则是会有影响的。 现在我们先抛开冲突不谈，记得在第四章举的例子吗，在并发情况下，两个事务同时操作 x。假设 x 的初值是 0: ```text T1 begin T2 begin R1(x) // T1读到0 R2(x) // T2读到0 U1(0+1) // T1尝试把x+1 U2(0+1) // T2尝试把x+1 T1 commit T2 commit ``` 最后 x 的结果是 1，这个结果显然与期望的不符。 VM 的一个很重要的职责，就是实现了调度序列的可串行化。JyDB 采用两段锁协议（2PL）来实现。当采用 2PL 时，如果某个事务 i 已经对 x 加锁，且另一个事务 j 也想操作 x，但是这个操作与事务 i 之前的操作相互冲突的话，事务 j 就会被阻塞。譬如，T1 已经因为 U1(x) 锁定了 x，那么 T2 对 x 的读或者写操作都会被阻塞，T2 必须等待 T1 释放掉对 x 的锁。 由此来看，2PL 确实保证了调度序列的可串行话，但是不可避免地导致了事务间的相互阻塞，甚至可能导致死锁。JyDB 为了提高事务处理的效率，降低阻塞概率，实现了 MVCC。 在介绍 MVCC 之前，首先明确记录和版本的概念。 DM 层向上层提供了数据项（Data Item）的概念，VM 通过管理所有的数据项，向上层提供了记录（Entry）的概念。上层模块通过 VM 操作数据的最小单位，就是记录。VM 则在其内部，为每个记录，维护了多个版本（Version）。每当上层模块对某个记录进行修改时，VM 就会为这个记录创建一个新的版本。 JyDB 通过 MVCC，降低了事务的阻塞概率。譬如，T1 想要更新记录 X 的值，于是 T1 需要首先获取 X 的锁，接着更新，也就是创建了一个新的 X 的版本，假设为 x3。假设 T1 还没有释放 X 的锁时，T2 想要读取 X 的值，这时候就不会阻塞，JyDB 会返回一个较老版本的 X，例如 x2。这样最后执行的结果，就等价于，T2 先执行，T1 后执行，调度序列依然是可串行化的。如果 X 没有一个更老的版本，那只能等待 T1 释放锁了。所以只是降低了概率。 还记得我们在第四章中，为了保证数据的可恢复，VM 层传递到 DM 的操作序列需要满足以下两个规则： > 规定1：正在进行的事务，不会读取其他任何未提交的事务产生的数据。 > > 规定2：正在进行的事务，不会修改其他任何未提交的事务修改或产生的数据。 由于 2PL 和 MVCC，我们可以看到，这两个条件都被很轻易地满足了。 ## Entry 记录 对于一条记录来说，JyDB 使用 Entry 类维护了其结构。 虽然理论上，MVCC 实现了多版本，但是在实现中，VM 并没有提供 Update 操作， 对于字段的更新操作由后面的表和字段管理（TBM）实现。所以在 VM 的实现中，一条记录只有一个版本。 我们可以通过 DataItem 存储 Entry, 所以 Entry 中携带对应的 uid Entry二进制格式如下: ```text [XMIN] [XMAX] [DATA] ``` XMIN 是创建该条记录（版本）的事务编号，而 XMAX 则是删除该条记录（版本）的事务编号, 每个都是 8 位 ## 事务的隔离级别 ### 读提交 上面提到，如果一个记录的最新版本被加锁，当另一个事务想要修改或读取这条记录时，JyDB 就会返回一个较旧的版本的数据。这时就可以认为，最新的被加锁的版本，对于另一个事务来说，是不可见的。于是版本可见性的概念就诞生了。 版本的可见性与事务的隔离度是相关的。JyDB 支持的最低的事务隔离程度，是“读提交”（Read Committed），即事务在读取数据时, 只能读取已经提交事务产生的数据。保证最低的读提交的好处，第四章中已经说明（防止级联回滚与 commit 语义冲突）。 JyDB 实现读提交，为每个版本维护了两个变量，就是上面提到的 XMIN 和 XMAX： - XMIN：创建该版本的事务编号 - XMAX：删除该版本的事务编号 XMIN 应当在版本创建时填写，而 XMAX 则在版本被删除，或者有新版本出现时填写。 XMAX 这个变量，也就解释了为什么 DM 层不提供删除操作，当想删除一个版本时，只需要设置其 XMAX，这样，这个版本对每一个 XMAX 之后的事务都是不可见的，也就等价于删除了。 如此，在读提交下，版本对事务的可见性逻辑如下： ```text (XMIN == Ti and // 由Ti创建且 XMAX == NULL // 还未被删除 ) or // 或 (XMIN is commited and // 由一个已提交的事务创建且 (XMAX == NULL or // 尚未删除或 (XMAX != Ti and XMAX is not commited) // 由一个未提交的事务删除 )) ``` ### 可重复读 读提交会导致的问题大家也都很清楚，八股也背了不少。那就是不可重复读和幻读。这里我们来解决不可重复读的问题。 不可重复度，会导致一个事务在执行期间对同一个数据项的读取得到不同结果。如下面的结果，加入 X 初始值为 0： ```text T1 begin R1(X) // T1 读得 0 T2 begin U2(X) // 将 X 修改为 1 T2 commit R1(X) // T1 读的 1 ``` 可以看到，T1 两次读 X，读到的结果不一样。如果想要避免这个情况，就需要引入更严格的隔离级别，即可重复读（repeatable read）。 T1 在第二次读取的时候，读到了已经提交的 T2 修改的值，导致了这个问题。于是我们可以规定： **事务只能读取它开始时, 就已经结束的那些事务产生的数据版本** 这条规定，增加于，事务需要忽略： - 在本事务后开始的事务的数据; - 本事务开始时还是 active 状态的事务的数据 对于第一条，只需要比较事务 ID，即可确定。而对于第二条，则需要在事务 Ti 开始时，记录下当前活跃的所有事务 SP(Ti)，如果记录的某个版本，XMIN 在 SP(Ti) 中，也应当对 Ti 不可见。 于是，可重复读的判断逻辑如下： ```text (XMIN == Ti and // 由Ti创建且 (XMAX == NULL or // 尚未被删除 )) or // 或 (XMIN is commited and // 由一个已提交的事务创建且 XMIN < XID and // 这个事务小于Ti且 XMIN is not in SP(Ti) and // 这个事务在Ti开始前提交且 (XMAX == NULL or // 尚未被删除或 (XMAX != Ti and // 由其他事务删除但是 (XMAX is not commited or // 这个事务尚未提交或 XMAX > Ti or // 这个事务在Ti开始之后才开始或 XMAX is in SP(Ti) // 这个事务在Ti开始前还未提交 )))) ``` ## 死锁检测 查找图中是否有环的算法也非常简单，就是一个深搜，只是需要注意这个图不一定是连通图。思路就是为每个节点设置一个访问戳，都初始化为 -1，随后遍历所有节点，以每个非 -1 的节点作为根进行深搜，并将深搜该连通图中遇到的所有节点都设置为同一个数字，不同的连通图数字不同。这样，如果在遍历某个图时，遇到了之前遍历过的节点，说明出现了环。 # 5. IndexManager 索引管理, 用于快速找到记录, 一般来说, 我们用B+tree维护索引, [B+tree视频教程](https://www.bilibili.com/video/BV1HX4y1N7v6/) ![](./media/B+树.png) 对于每个节点, 都对应着一个 DataItem 进行存储, 每个节点可以存储多个数据项([Son][Key]) IndexManager 中, 对应B+树, 我们直接使用 DataManager 进行存储, 不需要 VersionManager 进行版本管理 只有叶子节点里面的数据项真正记录了该B+树索引对应的表的记录的uid > 注意, 每个表的每个索引字段都会对应一颗 B+ tree B+ 树创建的流程如下: ![](./media/im-1.png) ![](./media/im-2.png) ![](./media/im-3.png) ![](./media/im-4.png) # 6. TableManager 表管理, 直接参与数据存储 ## sql语句 JyDB 实现的 SQL 语句语法如下： ```text begin [isolation level (read committed|repeatable read)] begin isolation level read committed commit abort create table ... [(index )] create table students id int32, name string, age int32, (index id name) drop table
drop table students
[] select * from student where id = 1 select name from student where id > 1 and id < 4 select name, age, id from student where id = 12 insert into
values insert into student values 5 "Zhang Yuanjia" 22 delete from
delete from student where name = "Zhang Yuanjia" update
set = [] update student set name = "ZYJ" where id = 5 where (>|<|=) [(and|or) (>|<|=) ] where age > 10 or age < 3
[a-zA-Z][a-zA-Z0-9_]* int32 int64 string .* ``` 示例 ```text 1. begin 2. commit 3. abort 4. create table test_table id int32, name string, age int32, (index id) 5. drop table test_table 6. select name, age, id from test_table where id = 12 7. select * from test_table 8. insert into test_table values 5 "Zhang Yuanjia" 22 9. update test_table set name = "ZYJ" where id = 5 10. update test_table set name = "ZYJ" where id = 5 and name = "Zhang Yuanjia" ``` ## 字段 字段的二进制格式: `[FieldName][TypeName][IndexUid]` - FileName 与 TypeName 都是以String类型进行的存储, String类型存储结构如下: [StringLength][StringData], 前4位是string的长度, 后面是str字符串 - IndexUid 占 8 位, 指向了索引二叉树的根 - 如果field无索引，IndexUid为0 如果这个字段是索引的话, 那么这个表的这个字段将对应一颗索引B+树, **注意, JyDB 只支持索引检索** ## 表 表的二进制格式: `[TableName][NextTable][Field1Uid][Field2Uid]...[FieldNUid]` - TableName 是string类型: [StringLength][StringData], 前4位是string的长度, 后面是str字符串 - NextTable, Field1Uid 等等都是 8 位 - 这个类集成了语句的具体执行流程