Java手写简易数据库--持续更新中

MYDB

  • 0. 项目结构
    • 0.1 引用计数缓存框架
      • 为什么不使用LRU
      • 引用计数缓存
      • 缓存框架实现
    • 0.2 共享内存数组
  • 1. 事务管理器--TM
    • 1.1 XID 文件
      • XID 规则
      • XID 文件结构
      • 读取方式
      • 事务状态
    • 1.2 代码实现
  • 2. 数据管理器--DM
    • 2.1 页面缓存
      • 页面结构
      • 页面缓存
      • 数据页管理
        • 第一页
        • 普通页
    • 2.2 日志文件
  • 3. 版本管理器--VM
  • 4. 索引管理器--IM
  • 5. 表管理器--TBM

0. 项目结构

  • 原项目博客地址
  • MYDB 分为后端和前端，前后端通过 socket 进行交互。
  • 前端（客户端）读取用户输入，并发送到后端执行，输出返回结果，并等待下一次输入。
  • 后端需要解析 SQL，如果是合法的 SQL，就尝试执行并返回结果。
  • 后端划分为五个模块，每个模块都又一定的职责，通过接口向其依赖的模块提供方法。

五个模块如下：

  1. Transaction Manager（TM，事务管理器）
  2. Data Manager（DM，数据管理器）
  3. Version Manager（VM，版本管理器）
  4. Index Manager（IM，索引管理器）
  5. Table Manager（TBM，表管理器）

在这里插入图片描述
实现顺序：TM–>DM–>VM–>IM–>TBM

0.1 引用计数缓存框架

  • 数据项管理、分页管理涉及缓存，设计实现更通用的缓存框架

在这里插入图片描述

为什么不使用LRU

  • LRU 策略中，资源驱逐不可控，上层模块无法感知
  • 引用计数缓存只有上层模块主动释放引用，缓存在确保没有模块在使用这个资源的时候，才会驱逐资源

引用计数缓存

  • 只有在上层模块主动释放引用，缓存确保没有模块在使用这个资源，才会去驱逐资源。
  • 新增release(key)方法，用于释放资源的引用
  • 缓存满了之后，引用计数法无法自动释放缓存，直接报错OOM

缓存框架实现

  • 定义抽象类AbstractCache< T >，包含两个抽象方法：
    • getForCache()：资源不在缓存时的获取缓存
    • releaseForCache()：当资源被驱逐时的写回行为
  • 维护一个计数
  • 针对多线程场景，记录哪些资源正在从数据源获取中：
    • private HashMap<Long, T> cache; // 实际缓存的数据
    • private HashMap<Long, Integer> references; // 资源的引用个数
    • private HashMap<Long, Boolean> getting; // 正在被获取的资源
  • get()方法，用于获取资源，首先要检查getting，死循环获取
    • 资源在缓存中，直接返回，引用数 +1
    • 资源不在缓存中，如果缓存没满，getting中注册，从数据源中获取资源，使用getForCache()获取，获取完成后删除getting
  • release()方法，用于释放缓存，直接references - 1
    • 如果已经减到 0，执行回源操作，并删除缓存中所有相关的结构
  • close()方法，安全关闭方法，关闭时需要缓存中所有资源强制回源

0.2 共享内存数组

Java中，数组作为对象，以对象形式存储在内存中

  • 在 Java 中，当你执行类似 subArray 的操作时，只会在底层进行一个复制，无法同一片内存。
  • 因此，Java无法实现共享内存数组，这里单纯松散的规定数组的可使用范围，实现“共享”
  • “共享” 是指多个对象引用同一个数组对象，并不是多个对象共享同一片内存
public class SubArray {public byte[] raw;public int start;public int end;public SubArray(byte[] raw, int start, int end) {this.raw = raw;this.start = start;this.end = end;}
}

1. 事务管理器–TM

TM 通过 XID 文件维护事务的状态，并提供接口供其他模块查询某个事务的状态

1.1 XID 文件

XID 规则

  • 在 MYDB 中，每个事务都有一个XID，这个 ID 唯一标识了这个事务。
  • 事务的 XID 从 1 开始标号，自增不可重复。
  • 特殊规定 XID 0 是一个超级事务（Super Transaction）。
  • 当一些操作想在没有申请事务的情况进行，那么可以将操作的 XID 设置为 0。
  • XID 为 0 的事务的状态永远是committed。

XID 文件结构

  • XID 文件头部，保存一个 8 字节的数字，记录这个 XID 文件管理的事务的个数。
  • XID 文件给每个事务分配了一个字节的空间，用来保存其状态。
  • 某个事务 xid 在文件中的状态就存储在 (xid-1)+8 字节处，Super XID 的状态不记录。

读取方式

  • 采用 NIO 方式 的 FileChannel

事务状态

  • activate，正在进行，尚未结束
  • committed，已提交
  • absorted，已撤销（回滚）

1.2 代码实现

  • 在构造函数创建了一个 TransactionManager 之后，首先要对 XID 文件进行校验，以保证这是一个合法的 XID 文件。
  • 校验方式：通过文件头的 8 字节数字反推文件的理论长度，与文件的实际长度做对比。如果不同则认为 XID 文件不合法。
  • 对于校验没有通过的，会直接通过 panic 方法，强制停机。
  • 在一些基础模块中出现错误都会如此处理，无法恢复的错误只能直接停机。

create方法：创建事务管理器

public static TransactionManagerImpl create(String path) {File f = new File(path + TransactionManagerImpl.XID_SUFFIX);try {if (!f.createNewFile()) {// 文件已存在Panic.panic(Error.FileExistsException);}} catch (IOException e) {Panic.panic(e);}if (!f.canRead() || !f.canWrite()) {// 文件不可读或不可写Panic.panic(Error.FileCannotRWException);}FileChannel fc = null;RandomAccessFile raf = null;try {raf = new RandomAccessFile(f, "rw");fc = raf.getChannel();} catch (IOException e) {Panic.panic(e);}// 写空XID文件头ByteBuffer buf = ByteBuffer.wrap(new byte[TransactionManagerImpl.LEN_XID_HEADER_LENGTH]);try {fc.position(0);fc.write(buf);} catch (IOException e) {Panic.panic(e);}return new TransactionManagerImpl(raf, fc);
}

在这里插入图片描述

open方法：开启事务管理器

public static TransactionManagerImpl open(String path) {File f = new File(path + TransactionManagerImpl.XID_SUFFIX);if (!f.exists()) {Panic.panic(Error.FileNotExistsException);}if (!f.canRead() || !f.canWrite()) {Panic.panic(Error.FileCannotRWException);}FileChannel fc = null;RandomAccessFile raf = null;try {raf = new RandomAccessFile(f, "rw");fc = raf.getChannel();} catch (FileNotFoundException e) {Panic.panic(e);}return new TransactionManagerImpl(raf, fc);}

在这里插入图片描述

begin方法：开启事务

// 开启一个事务 并返回xid
public long begin() {counterLock.lock();try {long xid = xidCounter + 1;updateXID(xid, FIELD_TRAN_ACTIVE);incrXIDCounter();return xid;} finally {counterLock.unlock();}
}

在这里插入图片描述

commit方法：提交事务

// 提交事务
@Override
public void commit(long xid) {updateXID(xid, FIELD_TRAN_COMMITTED);
}

在这里插入图片描述

abort方法：回滚事务

// 回滚事务
@Override
public void abort(long xid) {updateXID(xid, FIELD_TRAN_ABORTED);
}

在这里插入图片描述

2. 数据管理器–DM

DM 直接管理数据库 DB 文件和日志文件

  1. 上层模块和文件系统之间的一个抽象层，向下直接读写文件，向上提供数据包装
  2. 日志功能

主要职责：

  1. 分页管理 DB 文件，并进行缓存
  2. 管理日志文件，保证在发生错误时，可以根据日志进行恢复
  3. 抽象 DB 文件为 DataItem 供上层模块使用，并提供缓存

2.1 页面缓存

页面结构

  • 存储在内存中的页面，与已经持久化到磁盘的抽象页面有区别
  • 设置默认数据页大小定位8K
  • 脏页面是指已经被修改但尚未写回磁盘的数据库页
public class PageImpl implements Page{private int pageNumber; // 页面页号，页号从1开始private byte[] data; 	// 实际包含的字节数据private boolean dirty; 	// 是否是脏页面，脏页面需要被写回磁盘private Lock lock;// 用来方便在拿到 Page 的引用时可以快速对这个页面的缓存进行释放操作private PageCache pc;
}

页面缓存

  • 页面缓存接口
public interface PageCache {int newPage(byte[] initData); // 新增页面Page getPage(int pgno) throws Exception; // 获取页数// 抽象缓存框架中定义的方法void close(); // 关闭缓存，写回所有资源void release(Page page); // 释放缓存void truncateByPgno(int maxPgno); // 根据页号截断缓存int getPageNumber(); // 获取当前打开的数据库文件页数void flushPage(Page pg); // 刷回数据源
}
  • 页面缓存实现类，需要继承抽象缓存框架，实现getForCache() 和 releaseForCache() 抽象方法
  • 由于数据源就是文件系统，getForCache() 直接从文件中读取，并包裹成 Page 即可
  • releaseForCache() 驱逐页面时，也只需要根据页面是否是脏页面，来决定是否需要写回文件系统
@Override
protected Page getForCache(long key) throws Exception {// 数据源就是文件系统 直接从文件中读取，并包裹成 Pageint pgno = (int) key;long offset = PageCacheImpl.pageOffset(pgno);ByteBuffer buf = ByteBuffer.allocate(PAGE_SIZE);fileLock.lock();try {fc.position(offset);fc.read(buf);} catch (IOException e) {Panic.panic(e);}fileLock.unlock();return new PageImpl(pgno, buf.array(), this);
}
private static long pageOffset(int pgno) {// 页号从 1 开始return (pgno-1) * PAGE_SIZE;
}// ===========================================@Override
protected void releaseForCache(Page pg) {if (pg.isDirty()) {flush(pg);pg.setDirty(false);}
}
  • PageCache 还使用了一个 AtomicInteger，来记录了当前打开的数据库文件有多少页。
  • 这个数字在数据库文件被打开时就会被计算，并在新建页面时自增。
@Override
public int newPage(byte[] initData) {// 打开时计算，新增页面时自增int pgno = pageNumbers.incrementAndGet();Page pg = new PageImpl(pgno, initData, null);flush(pg); // 新建的页面需要立刻写回文件系统return pgno;
}

数据页管理

数据库文件的第一页通常用作一些特殊用途，比如存储一些元数据，启动检查等

第一页
  • MYDB第一页只用来做启动检查
    • 每次数据库启动时，会生成一串随机字节，存储在 100 ~ 107 字节。在数据库正常关闭时，会将这串字节，拷贝到第一页的 108 ~ 115 字节。
    • 这样数据库在每次启动时，就会检查第一页两处的字节是否相同，以此来判断上一次是否正常关闭。如果是异常关闭，就需要执行数据的恢复流程。
// 启动时设置初始字节
public static void setVcOpen(Page pg) {pg.setDirty(true);setVcOpen(pg.getData());
}
private static void setVcOpen(byte[] raw) {System.arraycopy(RandomUtil.randomBytes(LEN_VC), 0, raw, OF_VC, LEN_VC);
}// 关闭时拷贝字节
public static void setVcClose(Page pg) {pg.setDirty(true);setVcClose(pg.getData());
}
private static void setVcClose(byte[] raw) {System.arraycopy(raw, OF_VC, raw, OF_VC + LEN_VC, LEN_VC);
}// 校验字节
public static boolean checkVc(Page pg) {return checkVc(pg.getData());
}
private static boolean checkVc(byte[] raw) {return Arrays.equals(Arrays.copyOfRange(raw, OF_VC, OF_VC + LEN_VC), Arrays.copyOfRange(raw, OF_VC + LEN_VC, OF_VC + 2 * LEN_VC));
}
普通页

  Free Space Offset（自由空间偏移量）通常用于数据库管理系统中的页分配和管理。在数据库中，数据通常存储在页（Page）中，每个页都有固定大小的存储空间。自由空间偏移量表示了一个页中空闲空间开始的位置，即从该偏移量开始的位置可以用来存储新的数据。当向页中插入新的数据时，数据库系统会根据当前的自由空间偏移量来确定新数据的存储位置，并更新自由空间偏移量以反映已使用的空间。
  对普通页的管理，基本都是围绕着对 FSO 进行的

  • 开头 2 字节无符号数，表示这一页的空闲位置的偏移 FSO
  • 剩下的部分都是实际存储的数据
// 向页面插入数据
// 将raw插入pg中，返回插入位置
public static short insert(Page pg, byte[] raw) {pg.setDirty(true);short offset = getFSO(pg.getData()); // 获取到FSO// 将 raw 中的内容复制到 pg.getData() 中 offset 开始的地方System.arraycopy(raw, 0, pg.getData(), offset, raw.length);setFSO(pg.getData(), (short)(offset + raw.length));return offset;
}/*recoverInsert()和recoverUpdate()用于在数据库崩溃后重新打开时，恢复例程直接插入数据以及修改数据使用*/// 将raw插入pg中的offset位置，并将pg的offset设置为较大的offset
public static void recoverInsert(Page pg, byte[] raw, short offset) {pg.setDirty(true);System.arraycopy(raw, 0, pg.getData(), offset, raw.length);short rawFSO = getFSO(pg.getData());if(rawFSO < offset + raw.length) {setFSO(pg.getData(), (short)(offset + raw.length));}
}// 将raw插入pg中的offset位置，不更新update
public static void recoverUpdate(Page pg, byte[] raw, short offset) {pg.setDirty(true);System.arraycopy(raw, 0, pg.getData(), offset, raw.length);
}

2.2 日志文件

  • MYDB 提供了崩溃后的数据恢复功能。
  • DM 层在每次对底层数据操作时，都会记录一条日志到磁盘上。
  • 在数据库奔溃之后，再次启动时，可以根据日志的内容，恢复数据文件，保证其一致性。

3. 版本管理器–VM

VM 基于两段锁协议实现调度序列的可串行化，并实现 MVCC ，实现两种隔离级别

4. 索引管理器–IM

IM 实现了基于 B+ 树的索引，BTW，目前只支持已索引字段

5. 表管理器–TBM

TBM 实现对字段和表的管理。同时，解析 SQL 语句，并根据语句操作表

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2868762.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

一文搞懂PCL中自定义点云类型的构建与函数使用

一文搞懂PCL中自定义点云类型的构建与函数使用

上周猛男快乐开发时遇到个bug&#xff0c;要用pcl的函数对自定义的点云进行处理。一起解决问题时遇到了很多问题&#xff0c;解决后整理出来分享给各位参考&#xff0c;以免踩一样的坑&#x1f60a;。文章中自定义的点我用PointT来表示&#xff0c;自定义点云一般指的是pcl::Po…
阅读更多...
西门子TIA中配置Anybus PROFINET IO Slave 模块

西门子TIA中配置Anybus PROFINET IO Slave 模块

1、所需产品 Siemens S7 PLC CPU 315-2 PN/DP 6ES7 315-2EH-0AB0 Siemens PLC 编程电缆 n.a. n.a. PC ，并安装Siemens PLC编程软件 TIA Portal V11 X-gateway Slave 接口的GSDML文件 根据网关的软件版本而定 Anybus Communicator GSD文件 GSDML-V1.0-HMS-ABCPRT-20050317.xl…
阅读更多...
算法耗时通用优化技巧 总结

算法耗时通用优化技巧 总结

最近在部署AI相关的算法&#xff0c;并要求减少总耗时&#xff0c;从中总结出的一些比较通用的优化技巧。精髓总结一句话就是&#xff1a;在同一时间尽可能充分利用硬件资源。而怎么尽可能充分利用呢&#xff0c;方式就是多线程并行处理。 1、单线程串行处理数据 假设算法需要…
阅读更多...
Python中字符串知识点汇总，以及map（）函数的使用

Python中字符串知识点汇总，以及map（）函数的使用

1.字符串的定义 字符串&#xff1a;字符串就是一系列字符。在python中&#xff0c;用引号括起来的都是字符串&#xff0c;其中的引号可以是单引号&#xff0c;也可以是双引号。 2.使用方法修改字符串的大小写 ①将字符串的字母全部改为大写&#xff1a;upper()函数 实例&…
阅读更多...
kkview远程控制: 内网远程桌面控制软件

kkview远程控制: 内网远程桌面控制软件

内网远程桌面控制软件&#xff1a;高效、安全的远程管理方案 在信息技术日新月异的今天&#xff0c;内网远程桌面控制软件已成为许多企业和个人用户不可或缺的工具。这类软件允许用户通过内部网络&#xff0c;实现对其他计算机的远程访问和控制&#xff0c;从而大大提高工作效…
阅读更多...
蓝桥杯Java准备

蓝桥杯Java准备

蓝桥杯马上就要开始了&#xff0c;话说干什么都先准备准备&#xff0c;临阵磨枪不快也光。 首先蓝桥杯java语言中使用的是eclipse的2020.06的版本&#xff0c;使用jdk1.8的版本&#xff0c;大家可以先下载下来然后体验一下。 然后就是熟悉的Helloworld环节 eclipse设置 打开几…
阅读更多...
Linux第79步_使用自旋锁保护某个全局变量来实现“互斥访问”共享资源

Linux第79步_使用自旋锁保护某个全局变量来实现“互斥访问”共享资源

自旋锁使用注意事项:自旋锁保护的“临界区”要尽可能的短。 因此&#xff0c;在open()函数中申请“spinlock_t自旋锁结构变量”&#xff0c;然后在release()函数中释放“spinlock_t自旋锁结构变量”&#xff0c;这种方法就行不通了。如果使用一个变量“dev_stats”来表示“共享…
阅读更多...
解锁区块链游戏数据解决方案

解锁区块链游戏数据解决方案

作者&#xff1a;stellafootprint.network 随着区块链技术的日新月异&#xff0c;游戏行业正迎来一场革命&#xff0c;催生了区块链游戏的崛起。这一变革不仅为用户带来了全新的互动体验&#xff0c;也开辟了全新的盈利渠道。然而&#xff0c;在这一新兴领域&#xff0c;数据的…
阅读更多...
多站合一的音乐搜索下载助手PHP源码l亲测

多站合一的音乐搜索下载助手PHP源码l亲测

源码获取方式 回复&#xff1a;031601 搭建教程&#xff1a; 将源码下载上传至宝塔面板&#xff0c;直接运行即可~ 说明&#xff1a; 该源码进行测试&#xff0c;测试成功源码无加密优化相关其他采集问题。
阅读更多...
html--花瓣

html--花瓣

代码 <!DOCTYPE html> <html lang"en" ><head> <meta charset"UTF-8"> <title>Petals</title><link rel"stylesheet" href"css/style.css"></head><body><div class"…
阅读更多...
JAVA---学生管理系统

JAVA---学生管理系统

遍历字符串 ArrayList学习&#xff1a;
阅读更多...
Postman接口测试之断言，全网最细教程没有之一！

Postman接口测试之断言，全网最细教程没有之一！

一、断言 在 postman 中我们是在Tests标签中编写断言&#xff0c;同时右侧封装了常用的断言&#xff0c;当然 Tests 除了可以作为断言&#xff0c;还可以当做后置处理器来编写一些后置处理代码&#xff0c;经常应用于&#xff1a; 【1】获取当前接口的响应&#xff0c;传递给…
阅读更多...
二分/二分查找(整数二分详解+拓展浮点二分）

二分/二分查找(整数二分详解+拓展浮点二分）

先上题目 在一个有序数组中&#xff0c;查找x所在的下标。 输入 第一行两个整数n和m。 第二行n个数&#xff0c;表示有序的数列。 接下来m行&#xff0c;每行一个整数x&#xff0c;表示一个询问的数。 输出 对于每个询问如果x在数列中&#xff0c;输出下标。否则输出-1 样…
阅读更多...
Linux网络编程: IP协议详解

Linux网络编程: IP协议详解

一、TCP/IP五层模型 物理层&#xff08;Physical Layer&#xff09;&#xff1a;物理层是最底层&#xff0c;负责传输比特流&#xff08;bitstream&#xff09;以及物理介质的传输方式。它定义了如何在物理媒介上传输原始的比特流&#xff0c;例如通过电缆、光纤或无线传输等。…
阅读更多...
2024年腾讯云2核4G服务器够用吗？性能测评

2024年腾讯云2核4G服务器够用吗？性能测评

腾讯云轻量2核4G5M带宽服务器支持多少人在线访问&#xff1f;5M带宽下载速度峰值可达640KB/秒&#xff0c;阿腾云以搭建网站为例&#xff0c;假设优化后平均大小为60KB&#xff0c;则5M带宽可支撑10个用户同时在1秒内打开网站&#xff0c;并发数为10&#xff0c;经阿腾云测试&a…
阅读更多...
第三门课：结构化机器学习项目-机器学习策略

第三门课：结构化机器学习项目-机器学习策略

文章目录 1 机器学习策略一1.1 为什么是ML策略&#xff1f;1.2 正交化1.3 单一数字评估指标1.4 满足和优化指标1.5 训练、开发及测试集划分1.6 开发集和测试集的大小1.7 什么时候改变开发、测试集和指标&#xff1f;1.8 为什么是人的表现&#xff1f;1.9 可避免偏差1.10 理解人…
阅读更多...
【编程项目开源】微信飞机大战（鸿蒙版）

【编程项目开源】微信飞机大战（鸿蒙版）

目标 仿微信飞机大战 效果 开发工具 下载DevEco Studio 工程截图 开源地址 https://gitee.com/lblbc/plane_game/tree/master/PlaneGame_hongmeng_ArkTS 关于 厦门大学计算机专业|华为八年高级工程师 专注《零基础学编程系列》 http://lblbc.cn/blog 包含&#xff1a;Ja…
阅读更多...
前端Prettier 插件的使用配置(详细)

前端Prettier 插件的使用配置(详细)

各个参数代表的意思:printWidth&#xff1a;每行代码的最大长度限制。 tabWidth&#xff1a;选项用于控制制表符的宽度。 useTabs&#xff1a;指定是否使用制表符代替空格。 semi&#xff1a;指定是否在语句的末尾添加分号。 singleQuote&#xff1a;指定是否使用单引号或双引号…
阅读更多...
操作系统系列学习——一个实际的schedule函数

操作系统系列学习——一个实际的schedule函数

文章目录 前言一个实际的schedule函数 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招&#xff0c;计划学习操作系统并完成6.0S81&#xff0c;加油&#xff01; 本文总结自B站【哈工大】操作系统 李治军&#xff08;全32讲&#xff09; 老师课程讲的非常好&#xff0c;感…
阅读更多...
Java后端面试经验分享，~纯分享

Java后端面试经验分享，~纯分享

本文将从面试、工作、学习三个方面分享最近面试的一些心得以及以后发展的一些规划&#xff0c;仅供参考&#xff0c;哈哈&#xff0c;毕竟本人也很菜&#xff0c;因为菜才要多学习。一会儿也会分享两本Java面试题库&#xff08;题库是b站大学找的&#xff0c;一会儿我也会分享出…
阅读更多...
最新文章

Copyright @ 2022~2023