数据库内核开发-存储模块

相关目录结构

disk_manager： 主要用于数据库和磁盘文件之间交流，操作存储在磁盘中的数据

buffer_pool_manager: 主要用于操作数据库缓冲池

rm_file_handle：主要用于对记录的增删改查

他们中封装了很多对数据进行基本操作的方法

数据的存储原理

一张最基本的数据库表，它包含两部分，第一部分是表头(元数据)，它存储字段信息，第二部分是数据

id	name
1	xiaoming
2	xiaohong

(第一行为表头，2，3行为数据)

像这样的，数据库中的每一行，在数据库系统中是以二进制形式作为一条记录进行存储的，而数据库对磁盘进行操作时并不是以记录为单位，如果每操作一次数据就要回磁盘中操作记录，这样做的效率是极低的，所以数据库中引入了另一种关系模型页，以页为单位管理记录。

因为任何涉及到磁盘的读写的操作，其效率是远不如直接在内存中进行运算的，所以我们要想提高效率，就必须要减少磁盘读写的次数，除了上述说的以页为单位操作数据，在数据库中一般还存在缓冲池（bufferpool）,他可以将一次磁盘读取的多个页暂时存储在内存中，每个页占据缓冲池的一块空间，这块空间称为帧，这样便能大大减少磁盘操作的次数，将大量内存与磁盘之间的数据操作转为内存与内存之间进行操作，在内存中被修改的数据所在的页将被标识为脏页，之后只要对脏页统一写回磁盘，数据就能实现更新。

相关数据结构

记录：

数据结构：

记录⽂件相关的数据结构，每⼀个数据库中的表可以分为表的元数据和表的记录数据，表的元数据统⼀存 储在.meta文件中，表的记录数据单独存储在同名⽂件中，我们称该⽂件为记录⽂件，在RMDB中， 我们⽤RmFileHandle类来对⼀个记录⽂件进⾏管理，RmFileHandle类中记录了⽂件描述符和⽂件头信息，数据结构如下：

/* 每个RmFileHandle对应一个表的数据文件，里面有多个page，每个page的数据封装在RmPageHandle中 */
class RmFileHandle {      
    friend class RmScan;    
    friend class RmManager;

   private:
    DiskManager *disk_manager_; 
    BufferPoolManager *buffer_pool_manager_;
    int fd_;        // 打开文件后产生的文件句柄
    RmFileHdr file_hdr_;    // 文件头，维护当前表文件的元数据
    ...
}

RmFileHdr的数据结构：

struct RmFileHdr {
 int record_size; // 元组⼤⼩（⻓度不固定，由上层进⾏初始化）
 int num_pages; // ⽂件中当前分配的page个数（初始化为1）
 int num_records_per_page; // 每个page最多能存储的元组个数
 int first_free_page_no; // ⽂件中当前第⼀个可⽤的page no（初始化为-1）
 int bitmap_size; // bitmap⼤⼩
};

file_hdr中的num_pages记录此⽂件分配的page个数，page_no范围为[0,file_hdr.num_pages)，page_no从0开始 增加，其中第0⻚存file_hdr，从第1页开始存放真正的记录数据。

RmPageHandle的数据结构如下：

struct RmPageHandle {
 const RmFileHdr *file_hdr; // ⽤到了file_hdr的bitmap_size, record_size
 Page *page; // 指向单个page
 RmPageHdr *page_hdr; // page->data的第⼀部分，指针指向⾸地址，⻓度为sizeof(RmPageHdr)
 char *bitmap; // page->data的第⼆部分，指针指向⾸地址，⻓度为file_hdr->bitmap_size
 char *slots; // page->data的第三部分，指针指向⾸地址，每个slot的⻓度为file_hdr->record_size
};

对于具体的每⼀个记录，使⽤RmRecord来进⾏管理，数据结构如下：

struct RmRecord {
 char *data; // 保存记录的二进制数据，data初始化分配size个字节的空间
 int size; // size = RmFileHdr的record_size
};

同时，使⽤Rid来对每⼀个记录进⾏唯⼀的标识，数据结构如下：

struct Rid {
 int page_no; // 该记录所在的数据⻚的page_no
 int slot_no; // 该记录所在数据⻚中的具体slot_no
};

关系解读：

- RmFileHandle：这是一个文件句柄类，它维护了一个打开的表文件的信息。它包含一个DiskManager对象和一个BufferPoolManager对象，这两个对象分别用于管理磁盘和缓冲池。它还包含一个文件描述符fd_，用于标识打开的文件。此外，它还包含一个RmFileHdr对象，用于存储文件头信息。

- RmFileHdr：这是一个文件头结构，它存储了表文件的元数据，如记录大小、页面数量、每页的记录数量、第一个包含空闲空间的页面号和每页的bitmap大小。

- RmPageHandle：这是一个页面句柄结构，它包含了一个页面的所有信息。它包含一个RmFileHdr对象的指针，指向当前页面所在文件的文件头。它还包含一个Page对象的指针，指向页面的实际数据。此外，它还包含一个RmPageHdr对象的指针，指向页面的页头信息。最后，它还包含两个字符指针，分别指向页面的bitmap和记录槽。

- RmPageHdr：这是一个页面头结构，它存储了每个页面的元数据，如下一个包含空闲空间的页面号和当前页面中的记录数量。

- RmRecord：这是一个记录结构，它包含了一条记录的数据和大小。

- PageId：这是一个页面ID结构，它包含了一个文件描述符和一个页面号，用于唯一标识一个页面。

表的元数据存储

数据结构：

表的元数据主要通过TabMeta数据结构来进⾏管理：

struct TabMeta {
 std::string name; // 表名称
 std::vector<ColMeta> cols; // 表包含的字段
 std::vector<IndexMeta> indexes; // 表上建⽴的索引
};

对于每个字段，运用ColMeta数据结构进行管理：

struct ColMeta {
 std::string tab_name; // 表名称
 std::string name; // 字段名称
 ColType type; // 字段类型
 int len; // 字段⻓度
 int offset; // 字段所在记录中的偏移量，⽤于查询字段的具体存储位置
};

对于索引结构，通过IndexMeta数据结构来进⾏管理：

struct IndexMeta {
 std::string tab_name; // 索引所属表名称
 int col_tot_len; // 索引字段⻓度总和
 int col_num; // 索引字段数量
 std::vector<ColMeta> cols; // 索引包含的字段
};

关系解读：

TabMeta是表的封装，包括表名，字段名，表上的索引。

ColMeta是字段的封装，包括字段所在的表名，字段名，字段类型，字段长度，字段所在记录中的偏移量。关于偏移量（offset），根据之前说的记录的定义，每一条记录即是表的一行，一行可能存在多个字段，所以要依靠偏移量来定位字段在记录中的位置。

IndexMeta是对索引的封装，包括索引的基本信息。

操作方法和部分实现思路

磁盘管理器（diskmanager）:

主要是对磁盘文件开启关闭，写入读入。

//页操作
/**
 * @description: 将数据写入文件的指定磁盘页面中
 * @param {int} fd 磁盘文件的文件句柄
 * @param {page_id_t} page_no 写入目标页面的page_id
 * @param {char} *offset 要写入磁盘的数据
 * @param {int} num_bytes 要写入磁盘的数据大小
 */
    void write_page(int fd, page_id_t page_no, const char *offset, int num_bytes);
/**
 * @description: 读取文件中指定编号的页面中的部分数据到内存中
 * @param {int} fd 磁盘文件的文件句柄
 * @param {page_id_t} page_no 指定的页面编号
 * @param {char} *offset 读取的内容写入到offset中
 * @param {int} num_bytes 读取的数据量大小
 */
    void read_page(int fd, page_id_t page_no, char *offset, int num_bytes);

    /*目录操作*/
    bool is_dir(const std::string &path);

    void create_dir(const std::string &path);

    void destroy_dir(const std::string &path);

    /*文件操作*/
    bool is_file(const std::string &path);

    void create_file(const std::string &path);

    void destroy_file(const std::string &path);

    int open_file(const std::string &path);

    void close_file(int fd);

    int get_file_size(const std::string &file_name);

    std::string get_file_name(int fd);

    int get_file_fd(const std::string &file_name);
private:
    // 文件打开列表，用于记录文件是否被打开

    //path2fd_:通过文件路径查找其文件句柄。用于检查文件是否已打开,并获取其句柄。
    //fd2path_:通过文件描述符查找其文件路径。用于通过文件句柄获取对应的文件路径。

    std::unordered_map<std::string, int> path2fd_;  //<Page文件磁盘路径,Page fd>哈希表
    std::unordered_map<int, std::string> fd2path_;  //<Page fd,Page文件磁盘路径>哈希表

write_page & read_page分别为读页和写页，这两个函数的实现思路是一样的，因为涉及到在文件的某一位置读或者写，所以要先定位，可以直接使用c++自带的io库中的lseek方法

lseek(fd,page_no * PAGE_SIZE,SEEK_SET); //定位到第page_no个文件的文件头，SEEK_SET = 0

读写同样调用自带write，read方法

ssize_t bw = write(fd,offset,num_bytes);
ssize_t br = read(fd,offset,num_bytes);

目录操作和文件操作都是基本的io操作，不做详解了。

// 文件打开列表，用于记录文件是否被打开

std::unordered_map<std::string, int> path2fd_; //<Page文件磁盘路径,Page fd>哈希表
std::unordered_map<int, std::string> fd2path_; //<Page fd,Page文件磁盘路径>哈希表

文件打开列表是两个map类型，记录了当前系统下被打开的文件，即使用中的文件，可以利用它防止重复打开，关闭或删除正在使用中的文件，同时我们在打开和关闭文件时都要注意更新文件打开列表。

缓冲池管理器（buffer_pool_manager）：

缓冲池管理器主要是对系统的缓冲池进行管理，包括给页分配空闲帧，对缓冲池更新，将缓冲池中的脏页写回，其中缓冲池的更新需要实现专门的更新算法，比较重要。

 /**
  * @description: 将目标页面标记为脏页
  * @param {Page*} page 脏页
  */
 static void mark_dirty(Page* page) { page->is_dirty_ = true; }

public: 
 Page* fetch_page(PageId page_id);

 bool unpin_page(PageId page_id, bool is_dirty);

 bool flush_page(PageId page_id);

 Page* new_page(PageId* page_id);

 bool delete_page(PageId page_id);

 void flush_all_pages(int fd);

 void delete_pages_index(int fd);

private:
 bool find_victim_page(frame_id_t* frame_id);

 void update_page(Page* page, PageId new_page_id, frame_id_t new_frame_id);

find_victim_page:

* @description: 从free_list或replacer中得到可淘汰帧页的 *frame_id

* @return {bool} true: 可替换帧查找成功 , false: 可替换帧查找失败

* @param {frame_id_t*} frame_id 帧页id指针,返回成功找到的可替换帧id

从空闲帧链表中获取帧id，并return true，同时如果没有空闲帧则需要调用淘汰算法进行淘汰

update_page:

* @description: 更新页面数据, 如果为脏页则需写入磁盘，再更新为新页面，更新page元数据(data, is_dirty, page_id)和page table

* @param {Page*} page 写回页指针

* @param {PageId} new_page_id 新的page_id

* @param {frame_id_t} new_frame_id 新的帧frame_id

更新缓冲池中的页到磁盘，如果页面未被修改（非脏页），则直接更新该页的数据给新页，删除旧帧号和页面号之间的映射，将新页号和帧号映射，如果是脏页，还需要提前写回磁盘：

void BufferPoolManager::update_page(Page *page, PageId new_page_id, frame_id_t new_frame_id) {
    // 1 如果是脏页，写回磁盘，并且把dirty置为false
    if (page->is_dirty()) {
        disk_manager_->write_page(page->get_page_id().fd, page->get_page_id().page_no, page->get_data(), PAGE_SIZE);
        page->is_dirty_ = false;
    }
    // 2 更新page table
    page_table_.erase(page->get_page_id());
    page_table_[new_page_id] = new_frame_id;
    // 3 重置page的data，更新page id
    page->reset_memory();
    page->id_ = new_page_id;
}

fetch_page:

• @description: 从buffer pool获取需要的页。

•          如果页表中存在page_id（说明该page在缓冲池中），并且pin_count++。
  

•          如果页表不存在page_id（说明该page在磁盘中），则找缓冲池victim page，将其替换为磁盘中读取的page，pin_count置1。
  

• @return {Page*} 若获得了需要的页则将其返回，否则返回nullptr
• @param {PageId} page_id 需要获取的页的PageId

Page* BufferPoolManager::fetch_page(PageId page_id) {
    latch_.lock();
    frame_id_t frame_id;
    // 1.     从page_table_中搜寻目标页
    // 1.1    若目标页有被page_table_记录，则将其所在frame固定(pin)，并返回目标页。
    if (page_table_.find(page_id) != page_table_.end()) {
        frame_id = page_table_.at(page_id);
        Page* page = &pages_[frame_id];
        if (++page->pin_count_ == 1) {
            replacer_->pin(frame_id);
        }
        latch_.unlock();
        return page;
    } 
    // 1.2    否则，尝试调用find_victim_page获得一个可用的frame，若失败则返回nullptr
    if (!find_victim_page(&frame_id)) {
        latch_.unlock();
        return nullptr;
    }
    Page* page = &pages_[frame_id];
    // 2.     若获得的可用frame存储的为dirty page，则须调用updata_page将page写回到磁盘
    update_page(page, page_id, frame_id);
    // 3.     调用disk_manager_的read_page读取目标页到frame
    disk_manager_->read_page(page_id.fd, page_id.page_no, page->get_data(), PAGE_SIZE);
    // 4.     固定目标页，更新pin_count_
    if (++page->pin_count_ == 1) {
        replacer_->pin(frame_id);
    }
    // 5.     返回目标页
    latch_.unlock();
    return page;
}

flush_page：

* @description: 将目标页写回磁盘，不考虑当前页面是否正在被使用

* @return {bool} 成功则返回true，否则返回false(只有page_table_中没有目标页时)

* @param {PageId} page_id 目标页的page_id，不能为INVALID_PAGE_ID

delete_page：

* @description: 从buffer_pool删除目标页

* @return {bool} 如果目标页不存在于buffer_pool或者成功被删除则返回true，若其存在于buffer_pool但无法删除则返回false

* @param {PageId} page_id 目标页

flush_all_pages：

* @description: 将buffer_pool中的所有页写回到磁盘

* @param {int} fd 文件句柄

记录操作(rm_file_handle):

/* 判断指定位置上是否已经存在一条记录，通过Bitmap来判断 */
bool is_record(const Rid &rid) const {
    RmPageHandle page_handle = fetch_page_handle(rid.page_no);
    return Bitmap::is_set(page_handle.bitmap, rid.slot_no);  // page的slot_no位置上是否有record
}

std::unique_ptr<RmRecord> get_record(const Rid &rid, Context *context) const;

Rid insert_record(char *buf, Context *context);

void insert_record(const Rid &rid, char *buf);

void delete_record(const Rid &rid, Context *context);

void update_record(const Rid &rid, char *buf, Context *context);

get_record:

• @description: 获取当前表中记录号为rid的记录
• @param {Rid&} rid 记录号，指定记录的位置
• @param {Context*} context
• @return {unique_ptr} rid对应的记录对象指针

std::unique_ptr<RmRecord> RmFileHandle::get_record(const Rid& rid, Context* context) const {
    // 1. 获取指定记录所在的page handle
    // 2. 初始化一个指向RmRecord的指针（赋值其内部的data和size）
    
    // 加锁
    if(context!=nullptr){
        context->lock_mgr_->lock_shared_on_record(context->txn_,rid,fd_);
    }
    // 6/29 补充可能出现的异常抛出
    if(rid.page_no > handle.file_hdr->num_pages || rid.slot_no > handle.file_hdr->num_records_per_page){
        throw RecordNotFoundError(rid.page_no,rid.slot_no);
    }

     if (!Bitmap::is_set(handle.bitmap, rid.slot_no)) {
        throw RecordNotFoundError(rid.page_no, rid.slot_no);
    }
    //以上
    RmPageHandle  handle = fetch_page_handle(rid.page_no);
    std::unique_ptr<RmRecord> record(new RmRecord());
    record->size = file_hdr_.record_size;
    record->data = handle.get_slot(rid.slot_no);

    buffer_pool_manager_->unpin_page(handle.page->get_page_id(),false);
    
    return record;
}

LRU替换器(lru_replacer):

因为缓冲中只是在内存开辟出的一小块空间，用于快速访问，它本身大小肯定要远小于磁盘储存大小，所以缓冲池中不可能永远存在你想要的页面，如果出现要用的页面在缓冲池中不存在的情况，那就需要缓冲池替换策略来替换掉近期用的最少的页面，这样整个缓冲池就动态起来了。

class LRUReplacer : public Replacer {
   public:
    /**
     * @description: 创建一个新的LRUReplacer
     * @param {size_t} num_pages LRUReplacer最多需要存储的page数量
     */
    explicit LRUReplacer(size_t num_pages);

    ~LRUReplacer();

    bool victim(frame_id_t *frame_id);

    void pin(frame_id_t frame_id);

    void unpin(frame_id_t frame_id);

    size_t Size();

   private:
   // LRUhash_ :页面id和页面在LRUlist_中的位置 LRUlist_：头最近访问，尾长时间未访问
    std::mutex latch_;                  // 互斥锁
    std::list<frame_id_t> LRUlist_;     // 按加入的时间顺序存放unpinned pages的frame id，首部表示最近被访问
    std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> LRUhash_;   // frame_id_t ->unpinned pages的frame id
    size_t max_size_;   // 最大容量（与缓冲池的容量相同）
};

victim:

* @description: 使用LRU策略删除一个victim frame，并返回该frame的id

* @param {frame_id_t*} frame_id 被移除的frame的id，如果没有frame被移除返回nullptr

* @return {bool} 如果成功淘汰了一个页面则返回true，否则返回false

对于pin和unpin，他们的主要作用是固定住某一页面，这些页面往往是正在使用的，如果该页面处于pin状态，则不会被淘汰，unpin就是解除该状态。

总结

DiskManager，BufferPoolManager和RMFileHandle是实现存储管理的关键组件，他们之间的关系和调用流程如下：

1. DiskManager：负责管理磁盘存储，包括读写磁盘上的页面，创建和删除磁盘文件等。

2. BufferPoolManager：负责管理内存中的缓冲池，包括从磁盘中读取页面到缓冲池，将缓冲池中的页面写回磁盘，页面的替换策略等。

3. RMFileHandle：负责管理一个特定的关系，包括读写该关系的记录，插入和删除记录等。

一个页面从磁盘中取出到使用的流程如下：

1. 当需要访问一个页面时，首先在BufferPoolManager的缓冲池中查找该页面。

2. 如果在缓冲池中找到了该页面，就直接使用该页面。

3. 如果在缓冲池中没有找到该页面，就需要从磁盘中读取该页面。BufferPoolManager会调用DiskManager的read_page方法，将该页面从磁盘读取到缓冲池中。

4. 如果缓冲池已满，需要选择一个页面进行替换。BufferPoolManager会根据其页面替换策略，选择一个页面，如果该页面被修改过，就调用DiskManager的write_page方法，将该页面写回磁盘，然后将新的页面读取到这个位置。

5. RMFileHandle通过BufferPoolManager获取到页面后，就可以对该页面进行操作，例如读取记录，修改记录等。