CMU資料庫（15-445）Lab1-BufferPoolManager

0. 關於環境搭建請看

//www.cnblogs.com/JayL-zxl/p/14307260.html

1. Task1 LRU REPLACEMENT POLICY

0. 任務描述

這個任務要求我們實現在課堂上所描述的LRU演算法最近最少使用演算法。

你需要實現下面這些函數。請確保他們都是執行緒安全的。

Victim(T*) : Remove the object that was accessed the least recently compared to all the elements being tracked by the Replacer, store its contents in the output parameter and return True. If the Replacer is empty return False.
Pin(T) : This method should be called after a page is pinned to a frame in the BufferPoolManager. It should remove the frame containing the pinned page from the LRUReplacer.
Unpin(T) : This method should be called when the pin_count of a page becomes 0. This method should add the frame containing the unpinned page to the LRUReplacer.
Size() : This method returns the number of frames that are currently in the LRUReplacer.

關於Lock和Lathes的區別請看下文。

//stackoverflow.com/questions/3111403/what-is-the-difference-between-a-lock-and-a-latch-in-the-context-of-concurrent-a/42464336#42464336

1. 實現

其實這個任務還是蠻簡單的。你只需要清楚什麼是最近最少使用演算法即可。

LRU 演算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。

這個題我熟啊。leetcode上有原題。而且要求在o(1)的時間複雜度實現這一任務。

//leetcode-cn.com/problems/lru-cache/

為了實現在O(1)時間內進行查找。因此我們可以用一個hash表。而且我們要記錄一個時間戳來完成記錄最近最少使用的塊是誰。這裡我們可以用list來實現。

如果我們訪問了鏈表中的一個元素。就把這個元素放在鏈表頭部。這樣放在鏈表尾部的元素一定就是最近最少使用的元素。

為了讓插入和刪除均為O(1)我們可以用雙向鏈表來實現。

這裡對於pin和unpin操作實際上對於了task2。我們為什麼需要pin。書上給了我們答案。下面我們也進行了分析

1.1 數據結構設計

struct Node{
  Node(frame_id_t v) :value(v) {}
  frame_id_t value;
  std::shared_ptr<Node> left;
  std::shared_ptr<Node> right;
};

這裡我們用了雙向鏈表。主要是為了刪除和插入均為0(1)的時間複雜度

1.2 輔助函數設置

這裡我們需要兩個輔助函數remove和insert

這裡的head和tail為頭節點和尾節點。這樣寫能夠減少對於邊界條件判斷。在構造函數內我們進行初始化

LRUReplacer::LRUReplacer(size_t num_pages) {
  head.reset(new Node(-1));
  tail.reset(new Node(-1));
  capacity=num_pages;
  head->right=tail;
  tail->left=head;
}

關於頭節點和尾節點的作用可以參考下文。

//blog.csdn.net/qq_41809589/article/details/86550994

insert函數負責把一個節點插入到鏈表頭部。

void LRUReplacer::insert(std::shared_ptr<Node> node) {
  if (node == nullptr) {
    return;
  }
  node->right = head->right;
  node->left = head;
  head->right->left=node;
  head->right=node;
  hash[node->value] = node;
  size++;
}

remove函數負責把一個節點從鏈表中移除

bool LRUReplacer::remove(const frame_id_t &value) {
  auto iter=hash.find(value);
  if(iter==hash.end())return false;
  auto  node=iter->second;
  node->right->left=node->left;
  node->left->right=node->right;
  hash.erase(value);
  size--;
  return true;
}

1.3 Victim 函數實現

注意這裡必須要加鎖，以防止並發錯誤。

如果沒有可以犧牲的頁直接返回false
如果有的話選擇在鏈表尾部的頁。remove它即可

bool LRUReplacer::Victim(frame_id_t *frame_id) {
  std::scoped_lock lru_clk{lru_mutex};
  if (hash.empty()) {
    return false;
  }
  auto id = tail->left;
  remove(id->value);
  *frame_id = id->value;
  return true;
}

1.4 pin 函數實現

注意這裡必須要加鎖，以防止並發錯誤。

如果這個頁存在則直接remove（因為這個時候它的pin_couter=0

void LRUReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock lru_clk{lru_mutex};
  if(hash.count(frame_id))remove(frame_id);
}

1.5 unpin 函數實現

注意這裡必須要加鎖，以防止並發錯誤。

先看一下這個頁是否在可替換鏈表中
如果它不存在的話。則需要看一下當前鏈表是否還有空閑位置。如果有的話則直接加入
如果沒有則需要移除鏈表尾部的節點知道有空餘位置

void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock lru_clk{lru_mutex};
  auto iter=hash.find(frame_id);
  if(iter==hash.end()){
    if (hash.size() >= capacity) {
      // need to remove item
      while (hash.size() >= capacity) {
       auto p=tail->left;
       remove(p->value);
      }
    }
    auto newNode = std::make_shared<Node>(frame_id);
    insert(newNode);

  }
}

2. 測試

執行下面的語句即可

 cd build
 make lru_replacer_test
 ./test/lru_replacer_test

可以發現成功通過

Task2 BUFFER POOL MANAGER

0. 任務描述

接下來，您需要在系統中實現緩衝池管理器(BufferPoolManager)。BufferPoolManager負責從DiskManager獲取資料庫頁面並將它們存儲在記憶體中。BufferPoolManage還可以在有要求它這樣做時，或者當它需要驅逐一個頁以便為新頁騰出空間時，將臟頁寫入磁碟。為了確保您的實現能夠正確地與系統的其餘部分一起工作，我們將為您提供一些已經填寫好的功能。您也不需要實現實際讀寫數據到磁碟的程式碼(在我們的實現中稱為DiskManager)。我們將為您提供這一功能。

系統中的所有記憶體頁面均由Page對象表示。 BufferPoolManager不需要了解這些頁面的內容。但是，作為系統開發人員，重要的是要了解Page對象只是緩衝池中用於存儲記憶體的容器，因此並不特定於唯一頁面。也就是說，每個Page對象都包含一塊記憶體，DiskManager會將其用作複製從磁碟讀取的物理頁面內容的位置。 BufferPoolManager將在將其來回移動到磁碟時重用相同的Page對象來存儲數據。這意味著在系統的整個生命周期中，相同的Page對象可能包含不同的物理頁面。Page對象的標識符（page_id）跟蹤其包含的物理頁面。如果Page對象不包含物理頁面，則必須將其page_id設置為INVALID_PAGE_ID。

每個Page對象還維護一個計數器，以顯示「固定」該頁面的執行緒數。BufferPoolManager不允許釋放固定的頁面。每個Page對象還跟蹤它的臟標記。您的工作是判斷頁面在解綁定之前是否已經被修改（修改則把臟標記置為1）。BufferPoolManager必須將臟頁的內容寫回磁碟，然後才能重用該對象。

BufferPoolManager實現將使用在此分配的前面步驟中創建的LRUReplacer類。它將使用LRUReplacer來跟蹤何時訪問頁對象，以便在必須釋放一個幀以為從磁碟複製新的物理頁騰出空間時，它可以決定取消哪個頁對象

你需要實現在(src/buffer/buffer_pool_manager.cpp):的以下函數

FetchPageImpl(page_id)
NewPageImpl(page_id)
UnpinPageImpl(page_id, is_dirty)
FlushPageImpl(page_id)
DeletePageImpl(page_id)
FlushAllPagesImpl()

1. 分析

**1.1 為什麼需要pin **

其實大抵可以如下圖。

考慮這樣一種情況。一個塊被放入緩衝區，進程從緩衝區記憶體中讀取塊的內容。但是，當這個塊被讀取的時候，如果一個並發進程將這個塊驅逐出來，並用一個不同的塊替換它，讀取舊塊內容的進程(reader)將看到不正確的數據;如果塊被驅逐時正在寫入它，那麼寫入者最終會破壞替換塊的內容。

因此，在進程從緩衝區塊讀取數據之前，確保該塊不會被逐出是很重要的。為此，進程在塊上執行一個pin操作;緩衝區管理器從不清除固定的塊（pin值不為0的塊）。當進程完成讀取數據時，它應該執行一個unpin操作，允許在需要時將塊取出。

因此我們需要一個pin_couter來記錄pin的數量。其實也就是引用計數的思想。

1.2 如何管理頁和訪問頁

一句話基地址+偏移量

page(基地值)+frame_id(偏移量) 實際上就是數組定址

這裡用了hash表來實現page_table來映射page_id和frame_id

2. 實現

2.1 FetchPageImpl 實現

Page *BufferPoolManager::FetchPageImpl(page_id_t page_id)

這個函數的作用就是我們要訪問一個page。這個函數可以分為三種情況分析

如果該頁在緩衝池中直接訪問
如果該頁不在緩衝池但是緩衝池中有空閑。從disk中取出page然後放入緩衝池之後在訪問
如果該頁不在緩衝池並且緩衝池也非空閑
- 需要找到一個犧牲頁。把它移出（判斷臟位來決定是否要寫會磁碟）
- 然後和情況2一樣。

2.2 UnpinPageImpl 實現

bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty)

函數定義如上。這裡的is_dirty主要是對於兩種情況

情況一。對於讀操作而言is_dirty=false
情況二。對於寫操作而言is_dirty=true

這個函數就是如果我們這個執行緒已經完成了對這個頁的操作。我們需要unpin以下

如果這個頁的pin_couter>0我們直接--
如果這個頁的pin _couter==0我們需要給它加到Lru_replacer中。因為沒有人引用它。所以它可以成為被替換的候選人

2.3 FlushPageImpl 實現

bool BufferPoolManager::FlushPageImpl(page_id_t page_id)

這個函數是要把一個page寫入磁碟。

首先找到這一個頁在緩衝池之中的位置
寫入磁碟

2.4 NewPageImpl 實現

Page *BufferPoolManager::NewPageImpl(page_id_t *page_id)

分配一個新的page。

如果緩衝池有空閑位置。則直接放進緩衝池
否則的話。如果有頁可以被犧牲掉。則犧牲它，把我們的新頁放進去
否則失敗

2.5 DeletePageImpl 實現

bool BufferPoolManager::DeletePageImpl(page_id_t page_id)

這裡是要我們把緩衝池中的page移出

如果這個page根本就不在緩衝池則直接返回
如果這個page 的引用計數大於0(pin_counter>0)表示我們不能返回
如果這個page被修改過則要寫會磁碟
否則正常移除就好了。（在hash表中erase）

3. 源碼解析

3.1 ResetMemory()

這個非常簡單就是一個簡單的記憶體分配。給我們的frame分配記憶體區域

3.2 ReadPage

void DiskManager::ReadPage(page_id_t page_id, char *page_data)

void DiskManager::ReadPage(page_id_t page_id, char *page_data) {
  int offset = page_id * PAGE_SIZE; //PAGE_SIZE=4kb 先計算偏移。判斷是否越界（因為文件大小有限制）
  // check if read beyond file length
  if (offset > GetFileSize(file_name_)) {
    LOG_DEBUG("I/O error reading past end of file");
    // std::cerr << "I/O error while reading" << std::endl;
  } else {
    // set read cursor to offset
    db_io_.seekp(offset); //把讀寫位置移動到偏移位置處
    db_io_.read(page_data, PAGE_SIZE); //把數據讀到page_data中
    if (db_io_.bad()) {
      LOG_DEBUG("I/O error while reading");
      return;
    }
    // if file ends before reading PAGE_SIZE
    int read_count = db_io_.gcount();
    if (read_count < PAGE_SIZE) {
      LOG_DEBUG("Read less than a page");
      db_io_.clear();
      // std::cerr << "Read less than a page" << std::endl;
      memset(page_data + read_count, 0, PAGE_SIZE - read_count); //如果讀取的數據小於4kb剩下的補0
    }
  }
}

3.3 WritePage

void DiskManager::WritePage(page_id_t page_id, const char *page_data) {
  size_t offset = static_cast<size_t>(page_id) * PAGE_SIZE; //先計算偏移
  // set write cursor to offset
  num_writes_ += 1; //記錄寫的次數
  db_io_.seekp(offset);
  db_io_.write(page_data, PAGE_SIZE); //向offset處寫data
  // check for I/O error
  if (db_io_.bad()) {
    LOG_DEBUG("I/O error while writing");
    return;
  }
  // needs to flush to keep disk file in sync
  db_io_.flush(); //刷新緩衝區
}

3.4 DiskManager 構造函數

就是獲取文件指針

DiskManager::DiskManager(const std::string &db_file)
    : file_name_(db_file), next_page_id_(0), num_flushes_(0), num_writes_(0), flush_log_(false), flush_log_f_(nullptr) {
  std::string::size_type n = file_name_.rfind('.');
  if (n == std::string::npos) {
    LOG_DEBUG("wrong file format");
    return;
  }
  log_name_ = file_name_.substr(0, n) + ".log";

  log_io_.open(log_name_, std::ios::binary | std::ios::in | std::ios::app | std::ios::out);
  // directory or file does not exist
  if (!log_io_.is_open()) {
    log_io_.clear();
    // create a new file
    log_io_.open(log_name_, std::ios::binary | std::ios::trunc | std::ios::app | std::ios::out);
    log_io_.close();
    // reopen with original mode
    log_io_.open(log_name_, std::ios::binary | std::ios::in | std::ios::app | std::ios::out);
    if (!log_io_.is_open()) {
      throw Exception("can't open dblog file");
    }
  }

  db_io_.open(db_file, std::ios::binary | std::ios::in | std::ios::out); //獲取文件指針。並且打開輸入輸出流
  // directory or file does not exist
  if (!db_io_.is_open()) {
    db_io_.clear();
    // create a new file
    db_io_.open(db_file, std::ios::binary | std::ios::trunc | std::ios::out);
    db_io_.close();
    // reopen with original mode
    db_io_.open(db_file, std::ios::binary | std::ios::in | std::ios::out);
    if (!db_io_.is_open()) {
      throw Exception("can't open db file");
    }
  }
  buffer_used = nullptr;
}

4. 測試

 cd build
 make buffer_pool_manager_test
 ./test/buffer_pool_manager_test

Tags: C++ 資料庫 CMU15-445（cmu資料庫課程）Lab cmu