CMU15-445-Spring-2023-Project #1 - Buffer Pool

前置知识,参考上一篇博客:CMU15-445-Spring-2023-Project #1 - 前置知识(lec01-06)

在存储管理器中实现缓冲池。缓冲池负责将物理页从主内存来回移动到磁盘。它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如,系统使用page唯一标识符(page_id_t)向缓冲池请求一个页面,但系统并不知道该页面是否已在内存中,也不知道系统是否需要从磁盘中获取该页面。
实现必须是线程安全的。

Task #1 - LRU-K Replacement Policy

这部分负责追踪缓冲池中的页面使用。
Impl
src/include/buffer/lru_k_replacer.h
src/buffer/lru_k_replacer.cpp

LRU-K算法的基本思想是维护一个大小为K的历史记录,记录最近K次访问的信息。当需要替换缓存中的数据时,LRU-K会根据这个历史记录来判断哪些数据是最近最少使用的,然后将其替换出去。

与LRU相比,LRU-K增加了对历史访问的考量,因此更加灵活,能够更好地适应不同访问模式下的缓存需求。
LRU-K 算法驱逐的帧的后向 k 距离是替换器中所有帧的最大值。后向 k 距离计算为**当前时间戳(指当前时间而不是history中最近时间戳)**与前第 k 次访问时间戳之间的时间差。历史访问次数少于 k 次的帧的后向 k 距离为 +inf。当多个帧的后向 k 距离为 +inf 时,替换者会驱逐history中最末时间戳最小的帧。

  • Evict(frame_id_t* frame_id):驱逐与所有其他可驱逐帧相比后向 k-distance 最大的帧。在输出参数中存储帧 ID 并返回 True。如果没有可驱逐帧,则返回 False。驱逐不同于remove,区别在于只需要将is_evictable_置为false即可。
  • RecordAccess(frame_id_t frame_id):记录给定帧 ID 在当前时间戳被访问,没有存储该帧则新建一个node,此方法应在页面被固定在 BufferPoolManager 中后调用。
  • Remove(frame_id_t frame_id):清除指定帧的所有访问历史记录,并从node_store_中删除。只有在 BufferPoolManager 中删除页面时才调用此方法。
  • SetEvictable(frame_id_t frame_id, bool set_evictable):该方法控制帧是否可驱逐。它还控制 LRUKReplacer 的大小。具体来说,当某个页面的引用计数达到 0 时(pageGuard进行drop->bpm进行unpin),其对应的帧就会被标记为可驱逐,替换器的大小也会随之增加。
  • Size():该方法返回当前 LRUKReplacer 中可驱逐帧的数量。

Task #2 - Buffer Pool Manager

实现缓冲池管理器(BufferPoolManager)。BufferPoolManager 负责从 DiskManager 抓取数据库页面并将其存储到内存中。BufferPoolManager 还可以在收到明确指示或需要删除页面以便为新页面腾出空间时,将脏页面写出到磁盘。

系统中的所有内存页面都由 Page 对象表示。缓冲池管理器无需了解这些页面的内容。Page 对象只是缓冲池中内存的容器,也就是说,每个页面对象都包含一个内存块,DiskManager 将把它用作从磁盘读取物理页面内容的复制位置。缓冲池管理器(BufferPoolManager)会重复使用同一个页面对象来存储数据,因为数据会在磁盘上来回移动。这意味着,在系统的整个生命周期中,同一个页面对象可能包含不同的物理页面。页面对象的标识符(page_id)可追踪其包含的物理页面;如果页面对象不包含物理页面,则其 page_id 必须设置为 INVALID_PAGE_ID。

每个页面对象还维护一个计数器(pincount),用于记录 “固定” 该页面的线程数。缓冲池管理器不允许释放被钉住的页面。每个页面对象也会记录它是否变脏(write过)。需要记录页面在解除固定前是否被修改过。BufferPoolManager 必须先将脏页面的内容写回磁盘,然后才能重新使用该对象。

BufferPoolManager 实现将使用 LRUKReplacer 类。LRUKReplacer 将跟踪页面对象被访问的时间,以便在必须释放帧以腾出空间从磁盘复制新的物理页面时,决定驱逐哪个页面对象。在 BufferPoolManager 中将 page_id 映射到 frame_id 时,请再次注意 STL 容器不是线程安全的。
Impl
src/include/buffer/buffer_pool_manager.h
src/buffer/buffer_pool_manager.cpp

  • FetchPage(page_id_t page_id):从缓冲池中获取指定page,此时增加pincount,且无法被驱逐;如果page不在缓冲池中,从空闲列表或替换器中选择一个frame(总是先从空闲列表中查找),通过调用 disk_manager_->ReadPage() 从磁盘读取页面,然后替换frame中的旧页面。如果空闲列表中没有可用页面,且所有其他页面当前都被固定(evictable),则应返回 nullptr。如果旧页面is dirty,需要先写入磁盘。
  • UnpinPage(page_id_t page_id, bool is_dirty):is_dirty 参数会跟踪页面在固定期间是否被修改,如果页面之前is_dirty就为true,但是还没有写入磁盘,也就是脏页面会被缓冲,不会立即写回,避免下次fetch又要从磁盘读出。这时就不能置为false。如果pincount减为0了,需要将驱逐标记设为true。
  • FlushPage(page_id_t page_id):刷新页面,将页面写入磁盘,而不管其固定状态如何。
  • NewPage(page_id_t* page_id):在缓冲池中创建一个新的page,AllocatePage() 私有方法会为 BufferPoolManager 提供一个唯一的新页面 ID。
  • DeletePage(page_id_t page_id):删除缓冲池中的指定page,DeallocatePage() 方法是一个无操作的方法,它模仿释放磁盘上的页面。
  • FlushAllPages()

DiskManager::WritePage() 函数需要在获取的页面为脏时,或者刷新页面时调用。不要忘记unset页面的is dirty标记。

Task #3 - Read/Write Page Guards

在缓冲池管理器中,FetchPage 和 NewPage 函数返回的指针指向已被钉住的页面。钉住机制确保在页面上没有更多读写之前,页面不会被驱逐。要表明内存中不再需要该页面,必须手动调用 UnpinPage。

实现用于存储 BufferPoolManager 和 Page 对象指针的 BasicPageGuard。页面防护确保一旦相应的页面对象退出作用域(析构),就会调用 UnpinPage。

由于 BasicPageGuard 隐藏了底层的页面指针,因此它还可以提供 read-only/write API,这些 API 可提供编译时检查,以确保为每个用例正确设置 is_dirty 标志。

在未来的项目中,多个线程将读写同一页面,因此需要读写器锁存来确保数据的正确性。请注意,在页面类中,有相关的锁定方法用于此目的。与取消页面锁定类似,在使用页面后可能会忘记取消锁定。为了缓解这一问题,将实现 ReadPageGuard 和 WritePageGuard,一旦页面超出范围,它们就会自动解除锁定。

Impl
src/storage/page/page_guard.cpp
src/buffer/buffer_pool_manager.cpp

实验结果

优化方面,减少stl的使用会明显增加qps。
image.png

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

spring boot 集成邮件发送功能

一、首先到QQ邮箱申请开启POP3、SMTP协议 二、安装依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency><dependency><groupId>org.springframew…

【漏洞挖掘】挖掘CNVD证书

文章目录 一、CNVD介绍事件型漏洞通用型漏洞 二、挖掘思路1. 黑盒测试资产搜集fofa API筛选脚本 2. 白盒测试代码审计 3. google hack注意事项 一、CNVD介绍 国家信息安全漏洞共享平台&#xff08;简称CNVD&#xff09;&#xff0c;对于白帽子来说&#xff0c;挖掘的漏洞提交后…

关于谷歌Gemini大模型

2023年12月7日&#xff0c;谷歌AI宣布发布新一代基于Transformer架构的大模型Gemini。 Gemini的名字来源于双子座&#xff0c;象征着模型的双重性质&#xff1a; 一方面&#xff0c;它是一个强大的训练模型&#xff0c;可以在各种下游任务上进行微调&#xff0c;如文本摘要、机…

MiniTab的宏基础知识

什么是宏&#xff1f; 宏是包含一系列 Minitab 会话命令的文本文件。可以使用宏自动执行重复性任务&#xff08;例如&#xff0c;生成月度报表&#xff09;或扩展 Minitab 的功能&#xff08;例如&#xff0c;计算特殊检验统计量&#xff09;。 Minitab 提供以下类型的宏&…

计算机毕业设计选题分享-SSM律师事务所业务管理系统01664(赠送源码数据库)JAVA、PHP,node.js,C++、python,大屏数据可视化等

SSM律师事务所业务管理系统 摘 要 随着科学技术的飞速发展&#xff0c;社会的方方面面、各行各业都在努力与现代的先进技术接轨&#xff0c;通过科技手段来提高自身的优势&#xff0c;律师事务所业务管理系统当然也不能排除在外。律师事务所业务管理系统是以实际运用为开发背景…

CodeWave智能开发平台--03--目标:应用创建--04自定义主题样式5子页面页面跳转逻辑

摘要 本文是网易数帆CodeWave智能开发平台系列的第07篇&#xff0c;主要介绍了基于CodeWave平台文档的新手入门进行学习&#xff0c;实现一个完整的应用&#xff0c;本文主要完成04自定义主题样式5子页面页面跳转逻辑 参考:新手训练营-PC端应用 CodeWave智能开发平台的07次接…

NVIDIA Jetpack6.0DP使用过程中的问题

Jetpack6.0DP是2023年12月才发布&#xff0c; 操作系统使用了ubuntu 22.04&#xff0c; gcc是11.4&#xff0c;版本都很高&#xff0c; 用起来还存在一些问题 无法使用jtop https://forums.developer.nvidia.com/t/jtop-no-longer-works-on-jp-6-0-dp/275215 使用$ sudo -H p…

【JAVA】OPENGL+TIFF格式图片,不同阈值旋转效果

有些科学研究领域会用到一些TIFF格式图片&#xff0c;由于是多张图片相互渐变&#xff0c;看起来比较有意思&#xff1a; import java.io.IOException; import java.text.SimpleDateFormat; import java.util.Date; import java.util.logging.*;/*** 可以自已定义日志打印格式…

Oracle数据库新手零基础入门,Oracle安装配置和操作使用详解

一、教程描述 本套教程是专门为初学者量身定制的&#xff0c;无需任何Oracle数据库基础&#xff0c;课程采用循序渐进的教学方式&#xff0c;从Oracle数据库的基础知识开始讲起&#xff0c;并不会直接涉及到一项具体的技术&#xff0c;而是随着课程的不断深入&#xff0c;一些…

基于python的leetcode算法介绍之动态规划

文章目录 零 算法介绍一 例题介绍 使用最小花费爬楼梯问题分析 Leetcode例题与思路[118. 杨辉三角](https://leetcode.cn/problems/pascals-triangle/)解题思路题解 [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/)解题思路题解 [96. 不同的二叉搜索树](h…

自动驾驶预测-决策-规划-控制学习(4):预测分析文献阅读

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、摘要分析1.Transformer模型是什么&#xff1f;什么是自注意力机制&#xff1f; 2.数据集是什么&#xff1f;3.预测车辆行驶轨迹和车辆换道意图4. LSTM 网络…

Pytest成魔之路 —— fixture 之大解剖!

1. 简介 fixture是pytest的一个闪光点&#xff0c;pytest要精通怎么能不学习fixture呢&#xff1f;跟着我一起深入学习fixture吧。其实unittest和nose都支持fixture&#xff0c;但是pytest做得更炫。 fixture是pytest特有的功能&#xff0c;它用pytest.fixture标识&#xff0c…

MybatisPlus—快速入门

目录 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 1.2 定义Mapper 2.MybatisPlus常用注解 2.1 TableName 2.2 TableId 2.3 TableField 2.4 小结 3. 常用配置 4. 总结 1.使用MybatisPlus的基本步骤 1.1引入MybatisPlus的起步依赖 MyBatisPlus官方提…

如何使用 NFTScan NFT API 在 PlatON 网络上开发 Web3 应用

PlatON 是由万向区块链和矩阵元主导开发的面向下一代的全球计算架构&#xff0c;创新性的采用元计算框架 Monad 和基于 Reload 覆盖网络的同构多链架构&#xff0c;其愿景是成为全球首个提供完备隐私保护能力的运营服务网络。它提供计算、存储、通讯服务&#xff0c;并提供算力…

软件测试|什么是Python构造方法,构造方法如何使用?

构造方法&#xff08;Constructor&#xff09;是面向对象编程中的重要概念&#xff0c;它在创建对象时用于初始化对象的实例变量。在Python中&#xff0c;构造方法是通过特殊的名称__init__()来定义的。本文将介绍Python构造方法的基本概念、语法和用法。 什么是构造方法&…

React使用动态标签名称

最近在一项目里&#xff08;React antd&#xff09;遇到一个需求&#xff0c;某项基础信息里有个图标配置&#xff08;图标用的是antd的Icon组件&#xff09;&#xff0c;该项基础信息的图标信息修改后&#xff0c;存于后台数据库&#xff0c;后台数据库里存的是antd Icon组件…

ArkTS - 网络请求

一、Axios请求 应用通过HTTP发起一个数据请求&#xff0c;支持常见的GET、POST、OPTIONS、HEAD、PUT、DELETE、TRACE、CONNECT方法。 前端开发肯定都使用过一个叫axios的第三方库&#xff0c;它是是一个基于 promise 的网络请求库&#xff0c;可以用于浏览器和 node.js&…

Rust 字符串 初步了解

rust 的字符串 。字符串不是复合类型&#xff0c; String 和 &str &#xff1a; String 具有所有权&#xff0c;是存储在堆上的。&str 没有所有权&#xff0c;是对 String 的引用。字符串字面量也是 &str 类型&#xff0c;存储在栈上。 切片&#xff08;slice&a…

Nacos与Eureka

一、前言 在构建和管理微服务架构时&#xff0c;选择适当的服务注册中心至关重要。Nacos和Eureka都是微服务体系结构中常用的服务注册和发现工具。本文将探讨它们之间的区别&#xff0c;帮助开发者在选择适合其项目需求的注册中心时做出明智的决策。 二、架构和适用场景 Nacos …

TSConfig 配置(tsconfig.json)

详细总结一下TSConfig 的相关配置项。个人笔记&#xff0c;仅供参考&#xff0c;欢迎批评指正&#xff01; 另外&#xff0c;如果想了解更多ts相关知识&#xff0c;可以参考我的其他笔记&#xff1a; vue3ts开发干货笔记ts相关笔记&#xff08;基础必看&#xff09;ts相关笔记…