15445第一階段筆記+Buffer Pool（2019）

概念

page與frame

​ 塊，頁，是對同一概念的不同叫法，取決於場景不同。其表述的都是磁碟上某一柱面上的連續扇區（固定數目）。數據在磁碟和緩衝區（記憶體）之間傳輸，傳輸的單位就是塊（頁）。

​ 記憶體區是以定長的頁數組的形式組織的，其中每一個數組條目，被稱為一個幀（frame）。當DBMS請求一個頁時，被請求頁的一份拷貝就被讀取進其中一個幀中。

​ 所以，page和frame實際是指的是同一個概念，buffer pool中的叫做幀，磁碟與記憶體之間的傳輸單位的叫做page或者block。

page table

​ 是一個Page ID到Frame ID的映射。Page ID是磁碟頁的屬性，不同的磁碟頁的Page ID不同，當磁碟頁被讀取進緩衝區時，該磁碟頁會在緩衝區中有一個位置，即Frame ID。緩衝區是Frame的定長數組，一共只有buffer_pool_size大小的frame，所以，當磁碟頁讀進寫出，會存在不同的磁碟頁先後出現在同一個幀位置的情況，那麼這個Page Table，就是保存當前頁ID到幀ID的映射。

page directory

​ Page Directory中的每⼀個小格中包含有對應page所在位置，也包含它剩餘空間信息。通過Page Directory可以將page映射到記憶體或者磁碟上的某個位置

存儲結構

​ 總的來說，資料庫內部的存儲結構可以總結為，Page Directory負責映射記憶體或者磁碟中的page，Page Table負責將page映射到buffer pool中的frame中。

​ 而page內部的header和slot array來組織tuple存放。以下是page中的結構

​ tuple內部的結構也是header+data。

項目

一些註意的地方

clock_replacer

• replacer是一個定長數組，但是clock_size不是定長，而是可以被victim的frame的總數，所以replacer實際上存放的是可以被替換的幀。clock_size初始為0。

• clock_hand是遍歷replacer的指針，只有Victim()函數可以修改clock_hand指針。

buffer_pool_manager

• pages_是buffer pool的幀數組。

函數

clock_replacer

bool Victim(frame_id_t *frame_id)

1.進行迴圈遍歷，掃描所有實際存在replacer中的幀，如果沒有可替換幀，則返回false。

2.只查看實際在replacer中的幀，如果ref為1，則將ref修改為0，clock_hand++。如果ref為0，則將其標記為不在replacer中，clock_size--，並令*frame_id = clock_hand++，將該幀的frame_id傳出去，返回true。

void Pin(frame_id_t frame_id)

將目標幀標記為不在replacer中，clock_size--。

void Unpin(frame_id_t frame_id)

將目標幀標記為在replacer中，clock_size++，同時將ref標記為true（clock_replacer中新添加幀的ref需標記為true）。

buffer_pool_manager

FetchPageImpl(page_id_t page_id)

0.首先用latch上鎖

1.page_table_中是否存在page_id所對應的幀。如果存在，則直接返回所對應的幀，並需要進行pin操作；若沒有則需要將磁碟中的page讀取到buffer pool中，即讀取到pages_中的一個幀的位置。

2.首先從free_list中尋找空閑幀，如果可以找到空閑幀，則go to 4；如果free_list為空，則調用replacer.Victim()獲得可替換幀的victim_frame_id。若沒有可替換幀，則返回nullptr。

3.檢查victim_frame的臟讀位，如果臟讀位有效，則需要調用disk_manager_->WritePage()寫回到磁碟中。

4.進行victim_frame數據的讀取以及元數據的更新操作：

（1）清除victim_frame的頁表中的記錄。

（2）添加victim_frame的page_id到victim_frame_id的新映射。

（3）更新victim_frame（在pages_數組中）的page_id。

（4）進行victim_frame的pin操作，pin_count++，調用者加1，並調用replacer_->pin()方法。

（5）victim_frame的臟讀位記為false。

（6）調用disk_manager_->ReadPage(page_id, pages_[victim_frame_id].data_)，將page的數據讀取到victim_frame中。

5.返回pages_中victim_frame的地址。

Page* NewPageImpl(page_id_t *page_id)

0.首先用latch上鎖

1.首先從free_list中尋找空閑幀，如果可以找到空閑幀，則go to 3；如果free_list為空，則調用replacer.Victim()獲得可用幀的victim_frame_id。若沒有可用幀，則返回nullptr。

2.檢查victim_frame的臟讀位，如果臟讀位有效，則需要調用disk_manager_->WritePage()寫回到磁碟中。

3.調用disk_manager_->AllocatePage()分配一個新的頁，記頁ID為page_id，然後進行victim_frame數據的清除以及元數據的更新操作：

（1）清除victim_frame的頁表中的記錄。

（2）添加victim_frame的page_id到victim_frame_id的新映射。

（3）更新pages_數組中的victim_frame的page_id.

（4）記victim_frame的臟讀位為false

（5）清空victim_frame中的數據

（6）設置victim_frame的pin_count=1

4.返回pages_中victim_frame的地址

bool DeletePageImpl(page_id_t page_id)

0.首先用latch上鎖

1.在page_table_中查找page_id是否存在對應的frame_id，如果不存在，則直接go to 4。

2.若page_table_[frame_id].pin_count不為0，則返回false。

3.若目標幀的臟讀位為true，則調用disk_manager_->WritePage()將其寫回磁碟。

4.進行目標幀的重置操作：

（1）該目標幀不再進行replacer_->Victim()操作，所以調用replacer_->Pin(frame_id)。

（2）從page_table_中刪除page_id的映射

（3）設置目標幀的pin_count=0，is_dirty_=false，data_清空，page_id=INVALID_PAGE_ID。

（4）加入free_list_中。

4.調用disk_manager_->DeallocatePage(page_id)，返回true。