CMU資料庫（15-445) Lab4-CONCURRENCY CONTROL

Lab4- CONCURRENCY CONTROL

拖了很久終於開始做實驗4了。lab4有三個大任務1. Lock Manager、2. DEADLOCK DETECTION 、3. CONCURRENT QUERY EXECUTION。這裡20年的lab好像和之前的不太一樣記得之前有日誌和錯誤恢復lab的。不過就做這個最新的了。

Task1 LOCK MANAGER

1.1 任務描述

這個任務只需要修改兩個文件concurrency/lock_manager.cpp和concurrency/lock_manager.h。這裡cmu已經給我們提供了和事物相關的一些函數。在include/concurrency/transaction.h。這裡的==鎖管理==(下用LM表示)針對於tuple級別。我們需要對lock/unlock請求作出正確的行為。如果出現錯誤應該拋出異常。

1.2 一些小tips

1. 請仔細閱讀位於lock_manager.h內的LockRequestQueue類這會幫助你確定哪些事物在等待一個鎖🔒

2. 建議使用std::condition_variable來通知那些等待鎖的事物

3. 使用shared_lock_set_和exclusive_lock_set_來區別共享鎖和排他鎖。這樣當TransactionManager想要提交和abort事物的時候。LM就可以合理的釋放鎖

4. 你應該通讀TransactionManager::Abort來了解對於Abort狀態的事物。LM是如何釋放鎖的

==一些參考閱讀資料==

  1. 關於多執行緒

  2. 關於鎖

  3. 關於c++11 條件變數

  4. C++互斥對象與互斥鎖

1、兩個常用的互斥對象：std::mutex（互斥對象），std::shared_mutex（讀寫互斥對象）
2、三個用於代替互斥對象的成員函數，管理互斥對象的鎖（都是構造加鎖，析構解鎖）：std::lock_guard用於管理std::mutex，std::unique_lock與std::shared_lock管理std::shared_mutex。

1.3 具體實現細節

1. 我們需要弄清楚各種鎖

  1. X鎖(排他鎖，Exclusive Locks)

    當加X鎖的時候，表示我們要寫這個tuple。當一個事物擁有排他鎖時，其他任何事務必須等到X鎖被釋放才能對該頁進行訪問；X鎖一直到事務結束才能被釋放。下面來看一個例子

    T1:    update table set column1='hello' where id<1000
    T2:    update table set column1='world' where id>1000

    對於這個sql語句而言。加入事物T1先到達。這個過程T1會對id < 1000的記錄施加排他鎖，但是由於T2的更新和T1並無關係，所以它不會阻塞T2的更新

    同樣看下面的例子。

    T1:    update table set column1='hello' where id<1000
    T2:    update table set column1='world' where id>900

    如同上例，如果T1先達，T2立刻也到，T1加的排他鎖會阻塞T2的update.

    對於本實驗的實現。我們需要記住。

    1. 如果有事物對當前rid加了共享鎖。則必須等共享鎖釋放之後才能再加X鎖
    2. 如果有事物對當前rid加了X鎖之後，則在該X鎖釋放之前，不會有任何的鎖被施加

  2. S鎖(共享鎖，Shared Locks)

    多個事務可封鎖一個共享頁；任何事務都不能修改該頁； 通常是該頁被讀取完畢，S鎖立即被釋放。

    本實驗對於S鎖的實現要和U鎖結合起來。因此會在下面說明。

  3. U鎖(更新鎖，Updated Locks)

    為了解決死鎖。引入了更新鎖，看下面的例子

    ----------------------------------------
    T1:
    begin tran
    select * from table(updlock) (加更新鎖)
    update table set column1='hello'
    T2:
    begin tran
    select * from table(updlock)
    update table set column1='world'
    ----------------------------------------

    事物T1加更新鎖的意思就是。我現在雖然只想讀。但是我要預留一個寫的名額，因此當有事物施加U鎖之後，其他事物便不能加U鎖。比如本例，T1執行select，加更新鎖。T2運行，準備加更新鎖，但發現已經有一個更新鎖在那兒了，只好等。

    除此之外，更新鎖可以和讀操作共存這也是我們這個實驗實現時需要重點考慮的

    ----------------------------------------
    T1:    select * from table(updlock)    (加更新鎖）
    T2:    select * from table(updlock)    (等待，直到T1釋放更新鎖，因為同一時間不能在同一資源上有兩個更新鎖）
    T3:    select * from table (加共享鎖，但不用等updlock釋放，就可以讀）
    ----------------------------------------                            

    因此在我們這個實驗實現的時候我們需要注意

    1. 如果有事物對當前rid加了更新鎖。則不允許加X和S鎖
    2. 當被讀取的頁將要被更新時，則升級為X鎖；U鎖要一直到事務結束時才能被釋放。

2. 任務一實現上的一些說明

注:不會附上很多程式碼。(聽Andy教授的話)

1. 對於S鎖

只需要考慮下面這些情況

  • 如果當前Lock_queue中有X鎖則需要wait
  • 如果有其他事物對當前rid加了U鎖則需要wait
  • 否則可以加S鎖

簡單附上一些程式碼

 if (mode == LockMode::SHARED) {
    auto shared_wait_for = [&]() { return !lock_queue.upgrading_ && !lock_queue.hasExclusiveLock(txn); };
    while (!shared_wait_for()) {
      lock_queue.cv_.wait(_lock);
    }
    txn->GetSharedLockSet()->emplace(rid);
  }

lock_queue.hasExclusiveLock(txn)函數

就是用來判斷是否有排他鎖

    inline bool hasExclusiveLock(Transaction *txn) {
      std::list<LockRequest>::iterator curr = request_queue_.begin();
      for (; curr != request_queue_.end(); curr++) {
        if (curr->lock_mode_ == LockMode::EXCLUSIVE) {
          return true;
        }
      }
      return false;
    }

2. 對於X鎖

  • 如果有其他事物加了X鎖則wait
  • 如果有其他事物對當前rid加了U鎖則需要wait
  • 否則可以加X鎖

同樣附上一些簡單的程式碼

 if (mode == LockMode::EXCLUSIVE) {
      auto exclusive_wait_for = [&]() { return !lock_queue.upgrading_ && lock_queue.request_queue_.size() == 1; };
    while (!exclusive_wait_for()) {
      lock_queue.cv_.wait(_lock);
    }
  txn->GetExclusiveLockSet()->emplace(rid);
  }

和共享鎖的實現基本類似

3. 對於U鎖

附上帶注釋的核心邏輯程式碼。基本可以說明白這個地方

// 標記位更新。表明現在正處於等待update鎖階段
queue.upgrading_ = true;
// 假如說當前的request_queue中只有當前update lock這一個請求。則可以加U鎖，否則應該wait
while (lock_table_[rid].request_queue_.size() != 1) {
  queue.cv_.wait(unique_lock);
}
// 加X鎖。並把標記位重製
queue.request_queue_.back() = LockRequest(txn->GetTransactionId(), LockMode::EXCLUSIVE);
queue.upgrading_ = false;

Task2 DEADLOCK DETECTION

這個任務要求你的LM能夠進行死鎖檢測。死鎖檢測演算法就是最常見的資源分配圖演算法

下面用cmu課上ppt的例子來看一下這個演算法。

核心就是如果事物Ti在等待事物Tj釋放鎖。則畫一條從i–>j的邊。如果檢測完所有的衝突事務。如果出現環則表示出現了死鎖。如果沒有環則表示沒有死鎖。

  1. 我們可以發現事務T1正在等待事物T2釋放鎖
  1. 事物T2中對於C的X鎖正在等待事物T3的S鎖釋放
  1. 事物T3對於A的X鎖在等待事物T1對於A的S鎖的釋放

這樣形成了一個環就發生了死鎖，這個時候就需要abort

2.1 一些來自TA和官網的建議

  1. 等待圖是一個有向圖
  2. 你必須有一種方法來通知被abort的等待執行緒
  3. 當你發現一個環的時候，你應該終止yongest的事物來打破死鎖。

2.2 具體實現

1. remove和add的操作比較簡單

就直接附上程式碼不說廢話

void LockManager::AddEdge(txn_id_t t1, txn_id_t t2) {
  for (const auto &txn_id : waits_for_[t1]) {
    if (txn_id == t2) {
      return;
    }
  }
  waits_for_[t1].push_back(t2);
}

void LockManager::RemoveEdge(txn_id_t t1, txn_id_t t2) {
  LOG_DEBUG("we can remove edge");
  auto &vec = waits_for_[t1];
  for (auto iter = vec.begin(); iter != vec.end(); ++iter) {
    if (*iter == t2) {
      vec.erase(iter);
      return;
    }
  }
}

2. hasCycle函數

這個函數的實現。就是對於我們上面演算法的實現。由於依賴圖是一個有向圖。因此我們需要知道如何判斷一個有向圖是否有環。

幫助鏈接

用簡單的dfs就可以實現這一功能。當然除了一個visited數組來判斷這個元素是否被遍歷過之外。我們還需要另外一個數組recStack用來 keep track of vertices in the recursion stack.

具體的過程就和下圖一樣

Lightbox

下面附上上面那個演算法的程式碼實習。但是關於本任務需要的程式碼沒有給出

// This function is a variation of DFSUtil() in //www.geeksforgeeks.org/archives/18212
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
  if (visited[v] == false)
  {
    // Mark the current node as visited and part of recursion stack
    visited[v] = true;
    recStack[v] = true;
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); ++i)
    {
      if( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
        return true;
      else if (recStack[*i])
        return true;
    }
 
  }
  recStack[v] = false; // remove the vertex from recursion stack
  return false;
}

3. 對於構建圖的補充

因為構建圖之前我們要獲取所有已經加鎖和等待鎖的事物id。

這裡用兩個函數來實現這兩個步驟

這裡附上找到所有等待鎖事物的函數。另一個不再給出。

    std::unordered_set<txn_id_t> getWaitingSet() {
      std::list<LockRequest>::iterator wait_start;
      std::unordered_set<txn_id_t> blocking;
      // 遍歷找到wait_start的位置
      std::list<LockRequest>::iterator curr = request_queue_.begin();
      for (; curr != request_queue_.end() && (curr->lock_mode_ == LockMode::SHARED || curr ->lock_mode_ == LockMode::EXCLUSIVE); curr++) {

      }
      wait_start = curr;
      for (; wait_start != request_queue_.end(); wait_start++) {
        if (GetTransaction(wait_start->txn_id_)->GetState() != TransactionState::ABORTED) {
          blocking.insert(wait_start->txn_id_);
        }
      }
      return blocking;
    }
  };

Task3

3.1 隔離級別

Read Uncommitted（讀取未提交內容）

在該隔離級別，所有事務都可以看到其他未提交事務的執行結果。本隔離級別很少用於實際應用，因為它的性能也不比其他級別好多少。讀取未提交的數據，也被稱之為臟讀（Dirty Read）。

就好比還沒確定的消息，你卻先知道了發布出去，最後又變更了，這樣就發生了錯誤

Read Committed（讀取提交內容）

這是大多數資料庫系統的默認隔離級別（但不是MySQL默認的）。它滿足了隔離的簡單定義：一個事務只能看見已經提交事務所做的改變。這種隔離級別 也支援所謂的不可重複讀（Nonrepeatable Read），因為同一事務的其他實例在該實例處理其間可能會有新的commit，所以同一select可能返回不同結果。

Repeatable Read（可重讀）

這是MySQL的默認事務隔離級別，它確保同一事務的多個實例在並發讀取數據時，會看到同樣的數據行。不過理論上，這會導致另一個棘手的問題：幻讀 （Phantom Read）。簡單的說，幻讀指當用戶讀取某一範圍的數據行時，另一個事務又在該範圍內插入了新行，當用戶再讀取該範圍的數據行時，會發現有新的「幻影」 行。

3.2 對於seqScan的並發控制

由於對於整個表的遍歷。也就是讀操作，在並發的情況下可能發生錯誤。所以必須加以控制

這裡附上一些加鎖的程式碼進行解釋

首先是對於隔離級別的區分

  1. 如果隔離級別為READ_UNCOMMITTED則不需要加鎖
  2. 如果隔離級別為READ_COMMITTED或者REPEATABLE_READ則需要判斷。如果當前rid沒有被加鎖。則加上共享鎖
  Transaction *txn = exec_ctx_->GetTransaction();
  LockManager *lock_mgr = exec_ctx_->GetLockManager();
  if (lock_mgr != nullptr) {
    switch (txn->GetIsolationLevel()) {
      case IsolationLevel::READ_UNCOMMITTED:
        break;
      case IsolationLevel::READ_COMMITTED:
      case IsolationLevel::REPEATABLE_READ:
        RID r = iter->GetRid();
        if (txn->GetSharedLockSet()->empty() && txn->GetExclusiveLockSet()->empty()) {
          lock_mgr->LockShared(txn, r);
          txn->GetSharedLockSet()->insert(r);
        }
        break;
    }
  }

3.3 對於update的並發控制

這個更新比較簡單。

主要有下面兩個原則

  1. 如果當前rid擁有共享鎖。當我想要update的時候需要把它更新成update Lock
  2. 否則定話如果沒有排他鎖我們需要加上排他鎖
if (lock_mgr != nullptr) {
      if (txn->IsSharedLocked(*rid)) {
        lock_mgr->LockUpgrade(txn, *rid);
        txn->GetSharedLockSet()->erase(*rid);
        txn->GetExclusiveLockSet()->insert(*rid);
      } else if (txn->GetExclusiveLockSet()->empty()) {
        lock_mgr->LockExclusive(txn, *rid);
      }
    }

對於delete的並發控制和update的完全一樣。只需要加入上面的原則即可

總結

總算磕磕絆絆把四個lab都寫完了。感謝在知乎和github以及qq群裡面得到的各種幫助。後面準備配合這門課的要求把對應章節的書的內容讀一下。同時把之前沒有寫完的上課筆記寫完。順帶有時間把前面lab的部落格改一下。因為實現方面有了變化。後面就準備開搞下一個lab了。不知道大家是推薦824分散式還是推薦os那。

Tags:

VirMach 便宜 VPS

QNews

QNews