CMU数据库系统实验一之缓冲池管理器
CMU-15-445 数据库系统实验一缓冲池管理器
前言
之前选课的时候没抢到数据库系统(非科班)，没关系，在网上找到了这个CMU的数据库系统的课程，还有教学视频在｀YouTube`上，很良心，虽然感觉讲的一般般，但我主要是做其中的项目，所以也就没什么影响。
实验使用C++，很对我胃口(不会Java= =)，这门课的实验有一个特点，就是实验是层层递进的，要做实验二就必须完成实验一，因为要用到实验一的代码
话不多说，开始实验一吧
实验一：缓冲池
在存储管理器中实现缓冲池。缓冲池负责将物理页面从主存储器来回移动到磁盘。
它允许DBMS支持大于系统可用内存量的数据库。它的操作对系统中的其他部分是透明的。
例如，系统使用其唯一标识符（page_id）向缓冲池请求页面，并且它不知道该页面是否已经在内存中，或者系统是否必须从磁盘检索它。
你的实现需要是线程安全的。多个线程将同时访问内部数据结构，因此您需要确保其关键部分受锁存器保护（这些在操作系统中称为“锁”）。
需要在存储管理器中实现以下三个组件： 1. 可扩展的哈希表 2. LRU页面替换政策 3. 缓冲池管理器
可扩展的哈希表
简介
可扩展哈希表是一种动态哈希表，也就是说，它的桶的个数是可以增加的
要求
你将构建一个通用哈希表，该表使用无序桶来存储唯一的键/值对。你的哈希表必须支持插入/删除键/值条目而不指定表的最大大小的功能。你的表需要根据需要自动增大，但不需要缩小它。也就是说，不需要实现对缩小或压缩哈希表的支持。还需要支持检查哈希表中是否存在密钥并返回其对应的值。
特性
- 相比较静态哈希表，桶不再是数据块本身，而是用一个指向块的指针数组来表示桶
- 指针数组能增长，它的长度总是2的幂，因此数组每增长一次，桶的数目就翻倍
- 不过并非每个桶都有一个数据块，如果某些桶中的所有记录可以放在一个块中，那么这些桶可以共享一个块
- 哈希函数h为每个键计算出一个K位二进制序列，该K足够大，比如32。但是桶的数目总是使用从序列第一位或者最后一位算起的若干位，此位数小于K，比如说i位。也就是说，当i是使用的位数时，桶数组将有2的i次方个项
实验中的难点
- 要理解全局的
depth和局部(桶)的depth的作用，用HashKey找位置时要仔细 - 实验中最难的操作就是插入了，因为要考虑到当某个桶里的数据满的时候，就要分裂，即增加局部的
depth，然后重新分配桶的map，分裂后桶的数目要加倍，全局的depth要一直大于等于局部的depth
LRU页面替换政策
简介
内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。
LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。
要求
该组件负责跟踪缓冲池中页面的使用情况。你将LRUReplacer在src/include/buffer/lru_replacer.h中实现一个新的子类，并在src/buffer/lru_replacer.cpp中实现相应的实现文件。这是一个通用类，用于跟踪何时使用它跟踪的元素。
实验中的难点
- 要选好数据结构，我选择的数据结构是哈希表，即STL中的
unordered_map，键是页面，值是一个节点，节点我用一个双向链表连接起来 - 剩下的工作就很简单了
Q&A
为什么要用哈希表？
虽然说实现LRU算法虽简单的数据结构是队列，但当你插入一个页面时，如果该页面是之前就已经在队列中的，那么就要找出之前已经存在队列中的那个页面，然后删除，在重新插入在队列尾部，找到并删除这个操作对于队列来说明显不合适，哈希表能快速查找并删除
为什么节点要用双向链表连接？
既然已经决定了要用双向链表，那么怎么知道那个页面是最近未使用呢？那必定要用一个类似队列的东西，选择链表最为合适，然后为什么要用双向呢？是由于实验要求要支持Erase操作，即指定某个页面并删除，虽然用单向链表能找到要删除的页面，但是要删除一条链表中的某个节点，必须要知道前后的节点才能删除，因此要保存指向前一个节点的指针
缓冲池管理器
要求
缓冲池管理器负责从中获取数据库页面DiskManager并将其存储在内存中。该BufferPoolManager也可以写脏页到磁盘时，它明确地指示这样做或何时需要移除一个页面，或产生新的一页。
系统中的所有内存页面都由Page对象表示。在BufferPoolManager并不需要了解这些网页的内容。但是，你必须了解Page对象只是缓冲池中内存的容器，因此并不特定于唯一页面。也就是说，每个Page对象都包含一块内存，DiskManager用作复制从磁盘读取的物理页面内容的位置。当它来回移动到磁盘时，BufferPoolManager它将重用相同的Page对象来存储数据。这意味着同一Page对象在整个系统生命周期中可能包含不同的物理页面。该Page对象的IDENTIFER（page_id）跟踪它包含的物理页面; 如果Page对象不包含物理页面，则page_id必须将其设置为INVALID_PAGE_ID。
每个Page对象还维护一个计数器，用于“固定”该页面的线程数。BufferPoolManager不能释放Page被钉住的东西。每个Page对象还会跟踪它是否脏。在取消固定页面时，记录页面是否被修改是您的工作。BufferPoolManager必须写一个肮脏的内容Page背到磁盘之前，该对象可重复使用。
BufferPoolManager实现将使用在先前步骤中创建的ExtendibleHashTable和LRUReplacer。它将使用ExtendibleHashTable映射page_id到Page对象的表。它还将使用它LRUReplacer来跟踪何时Page访问对象，以便它可以决定在必须释放帧以从磁盘复制新物理页面时腾出哪一个。
实验中的难点
- 需要了解
DiskManager和Page - 剩下的实现只要按照注释中的解释就很简单了
实验一总结
总的来说三个子项目的难度排序大概是哈希表>管理器>LRU，第一个我认为是最难的，我花的时间也最长
虽然过程磕磕绊绊，但也总算是完成了第一个实验，准备着手第二个实验了
