動機

不完全的理由是1~3只有跑local simple test，因為我的重點是第4個lab 想要了解不同的isolation level的效果

gradescope

  • 優點
    • 可以print測資
  • 缺點
    • 有神秘的語法限制，但是不會報錯，只有下面的訊息
      • The autograder failed to execute correctly. Please ensure that your submission is valid. Contact your course staff for help in debugging this issue. Make sure to include a link to this page so that they can help you most effectively.
    • 超慢，每次上傳至少超過一分鐘才會看到結果，也沒有做到哪個階段的過程
    • 在project4，明明local的所有測資都過了，但就是有一個test不知道為什麼跑不了
      • output沒有任何東西，直接timeout，但測資有挖出來測過有pass…
      • 同時後面直接在method的第一行放一個cout，之後看timeout的output也沒有噴出來…
        • 答案是rehash，這個很可怕，見下面
    • 一開始還有整個平台不能用的問題 (為期大概一個禮拜)

project1

提幾個重點

  • lru不是一般認知的lru，unpin之後就不用管了
  • page分成readable與occupied
    • 有allocate就是occupied，之後就不用動了
    • readable就是delete時要改的
  • dirty由invoker管，有直到下面的case才會真的寫回去disk
    • flush
    • 被選成victim

project2

bucket就是一個page，直接從頭做search，剩下的struct不用動(也不能動，因為page剩下的空間都是array_的)

剩下就是看這個

project3

其實邏輯都很簡單，但是難在怎麼使用你要的功能要反覆

  1. 透過trace
  2. 看別人的example

總的來說，只要懂得怎麼

  1. 從catalog拿table
  2. 從table的table_iterator拿tuple與rid(當成tuple的address)
  3. 怎麼根據output scheme來產生tuple (轉成vector<value>之後變成tuple)
  4. 怎麼做expression的evalute (要去各自的plan看)

project3就做得出來，其實這就是interpreter pattern

project4

這是重點所以慢慢講，還有下面是gradescope上的屍體(差valgrind)，local上的成體。

ISOLATION LEVELS

  • SERIALIZABLE
    • 上
      • index lock (條件)
        • Why write skew can happen in Repeatable reads?
        • 假設兩個thread都看到還有一個蘋果 (Read lock)
        • 之後兩個跑increase，就變成-1 (upgrade lock)
        • 這裡的重點是在改的當下無法保證條件是成立的
          • 解法是
            • 鎖整個表
            • 為條件(不一定存在的欄位)生出一個鎖
      • column的read lock
      • column的write lock
    • 直到(strict)commit才把所有lock放掉 (strict 2 phase lock)
  • REPEATABLE READS (SNAPSHOT ISOLATION)
    • 上
      • column的read lock
      • column的write lock
    • 直到commit才把所有lock放掉 (strict 2 phase lock)
  • READ COMMITTED
    • 上
      • column的read lock
      • column的write lock
    • 直到commit才把所有lock放掉
      • 除了read lock，他可以馬上放掉 (2 phase lock)
  • READ UNCOMMITTED
    • 不能上lock

在bustub的流程

begin會拿到transaction的id，每個transation會記錄拿了什麼lock(shared或exclusive)

commit與abort時會一次unlock所有lock

abort還會從log中undo之前的操作，commit比較特別的是會一次把delete做完

lock manager

有3個部分

  1. 根據ISOLATION LEVELS決定鎖怎麼給
  2. 怎麼abort與wait (deadlock prevention)
  3. 指令(project3)怎麼用lock manager上lock

指令上lock不難，注意

  1. READ UNCOMMITTED不用上鎖
  2. READ COMMITTED的read lock要放掉

怎麼abort與wait可以看這個

同個網站的extendsible hash也很清楚明瞭，我自己的project2的local test就是看他才做出來的

這裡是做wound-wait，就是

  1. 遇到老事務，等
  2. 遇到新事物，abort他
bool LockManager::LockRequestQueue::WaitWound(Transaction *txn, const RID &rid, LockRequestQueue::WaitPred wait_pred,
                                              LockRequestQueue::WoundPred wound_pred) {
  std::unique_lock<std::mutex> ul(lk_);
  auto &q = request_queue_;
  auto ptr = q.begin();
  while (ptr != q.end()) {
    if (ptr->txn_id_ < txn->GetTransactionId() && wait_pred(ptr)) {
      // old txn
      cv_.wait(ul);
      if (txn->GetState() == TransactionState::ABORTED) {
        return false;
      }
      ptr = q.begin();  // restart check
    } else if (ptr->txn_id_ > txn->GetTransactionId() && wound_pred(ptr, rid)) {
      // young txn
      assert(ptr->txn_id_ != txn->GetTransactionId());
      Transaction *trans = TransactionManager::GetTransaction(ptr->txn_id_);
      ptr = q.erase(ptr);
      trans->SetState(TransactionState::ABORTED);
      cv_.notify_all();
    } else {
      ptr++;
    }
  }

  return true;
}

流程是

  1. enqueue，去排隊
  2. 做WaitWound，等與清其他事務
  3. 拿鎖
auto me = q.Enqueue(txn, rid, LockMode::EXCLUSIVE);
if (!q.WaitWound(txn, rid, pred1, pred2)) {
  return false;
}

txn->SetState(TransactionState::GROWING);

最後是根據ISOLATION LEVELS決定鎖怎麼給

exclusive

bool not_appliable = txn->GetState() == TransactionState::ABORTED;
bool need_abort =
  txn->GetState() == TransactionState::SHRINKING && txn->GetIsolationLevel() == IsolationLevel::REPEATABLE_READ;
if (not_appliable || need_abort) {
    if (need_abort) {
      txn->SetState(TransactionState::ABORTED);
    }
    return false;
}

if (!txn->IsExclusiveLocked(rid)) {
    LockRequestQueue::WaitPred pred1 = [](LockRequestQueue::QIter &ptr) { return true; };
    LockRequestQueue::WoundPred pred2 = [](LockRequestQueue::QIter &ptr, const RID &rid) {
      Transaction *trans = TransactionManager::GetTransaction(ptr->txn_id_);
      trans->GetExclusiveLockSet()->erase(rid);
      trans->GetSharedLockSet()->erase(rid);
      return true;
    };
    auto me = q.Enqueue(txn, rid, LockMode::EXCLUSIVE);
    if (!q.WaitWound(txn, rid, pred1, pred2)) {
      return false;
    }

    txn->SetState(TransactionState::GROWING);
    me->lock_mode_ = LockMode::EXCLUSIVE;
    me->granted_ = true;
    txn->GetExclusiveLockSet()->emplace(rid);
}
return true;

shared

bool not_appliable = txn->GetState() == TransactionState::ABORTED;
bool need_abort =
  txn->GetIsolationLevel() == IsolationLevel::READ_UNCOMMITTED || txn->GetState() == TransactionState::SHRINKING;
if (not_appliable || need_abort) {
    if (need_abort) {
      txn->SetState(TransactionState::ABORTED);
    }
    return false;
}

if (!txn->IsSharedLocked(rid)) {
    LockRequestQueue::WaitPred pred1 = [](LockRequestQueue::QIter &ptr) {
          return ptr->lock_mode_ == LockMode::EXCLUSIVE;
    };
    LockRequestQueue::WoundPred pred2 = [](LockRequestQueue::QIter &ptr, const RID &rid) {
          if (ptr->lock_mode_ == LockMode::EXCLUSIVE) {
            Transaction *trans = TransactionManager::GetTransaction(ptr->txn_id_);
            trans->GetExclusiveLockSet()->erase(rid);
            trans->GetSharedLockSet()->erase(rid);
            return true;
          }
          return false;
    };
    auto me = q.Enqueue(txn, rid, LockMode::SHARED);
    if (!q.WaitWound(txn, rid, pred1, pred2)) {
      return false;
    }

    txn->SetState(TransactionState::GROWING);
    me->granted_ = true;
    txn->GetSharedLockSet()->emplace(rid);
}
return true;

upgrade其實與exclusive差不多 就是最後要把shared拔掉與exclusive塞進去

auto &q = GetQ(rid);
bool not_appliable = txn->GetState() == TransactionState::ABORTED;
bool need_abort =
  txn->GetState() == TransactionState::SHRINKING && txn->GetIsolationLevel() == IsolationLevel::REPEATABLE_READ;
if (not_appliable || need_abort) {
    if (need_abort) {
      txn->SetState(TransactionState::ABORTED);
    }
    return false;
}

if (!txn->IsExclusiveLocked(rid)) {
    LockRequestQueue::WaitPred pred1 = [](LockRequestQueue::QIter &ptr) { return true; };
    LockRequestQueue::WoundPred pred2 = [](LockRequestQueue::QIter &ptr, const RID &rid) {
      Transaction *trans = TransactionManager::GetTransaction(ptr->txn_id_);
      trans->GetExclusiveLockSet()->erase(rid);
      trans->GetSharedLockSet()->erase(rid);
      return true;
    };
    auto me = q.Enqueue(txn, rid, LockMode::EXCLUSIVE);
    if (!q.WaitWound(txn, rid, pred1, pred2)) {
      return false;
    }

    txn->SetState(TransactionState::GROWING);
    me->lock_mode_ = LockMode::EXCLUSIVE;
    me->granted_ = true;
    txn->GetSharedLockSet()->erase(rid);
    txn->GetExclusiveLockSet()->emplace(rid);
}
return true;

要記得的是在abort與unlock之後馬上notify_all

bool Unlock(Transaction *txn, const RID &rid, LockMode txn_lockmode) {
  std::unique_lock<std::mutex> ul(lk_);
  auto ptr = request_queue_.find(LockRequest{txn->GetTransactionId(), txn_lockmode});
  if (ptr != request_queue_.end()) {
    request_queue_.erase(ptr);
    if (txn_lockmode == LockMode::SHARED) {
      txn->GetSharedLockSet()->erase(rid);
    } else {
      txn->GetExclusiveLockSet()->erase(rid);
    }
    cv_.notify_all();
    return true;
  }
  return false;
}

剩下是因為懶，就用unordered_set管理queue

class LockRequest {
   public:
    LockRequest(txn_id_t txn_id, LockMode lock_mode) : txn_id_(txn_id), lock_mode_(lock_mode), granted_(false) {}

    txn_id_t txn_id_;
    mutable LockMode lock_mode_;
    mutable bool granted_;
  };

  struct LockRequestHash {
    std::size_t operator()(const LockRequest &a) const { return a.txn_id_; }
  };

  struct LockRequestEq {
    bool operator()(const LockRequest &a, const LockRequest &b) const { return a.txn_id_ == b.txn_id_; }
  };

  class LockRequestQueue {
   public:
    using QIter = std::unordered_set<LockRequest, LockRequestHash, LockRequestEq>::iterator;
    using LocalLock = std::unique_lock<std::mutex>;
    using WaitPred = bool (*)(QIter &);
    using WoundPred = bool (*)(QIter &, const RID &);
    std::mutex lk_;
    std::unordered_set<LockRequest, LockRequestHash, LockRequestEq> request_queue_;
    // for notifying blocked transactions on this rid
    std::condition_variable cv_;
    // txn_id of an upgrading transaction (if any)
    // txn_id_t upgrading_ = INVALID_TXN_ID;
    //bool upgrading_ = false;
    LockRequestQueue() { request_queue_.reserve(50); } // avoid rehash

    QIter Enqueue(Transaction *txn, const RID &rid, LockMode mode) {
      std::unique_lock<std::mutex> ul(lk_);
      auto &q = request_queue_;
      return q.insert(LockRequest{txn->GetTransactionId(), mode}).first;
    }

    bool WaitWound(Transaction *txn, const RID &rid, WaitPred wait_pred, WoundPred wound_pred);

    bool Unlock(Transaction *txn, const RID &rid, LockMode txn_lockmode) {
      std::unique_lock<std::mutex> ul(lk_);
      auto ptr = request_queue_.find(LockRequest{txn->GetTransactionId(), txn_lockmode});
      if (ptr != request_queue_.end()) {
        request_queue_.erase(ptr);
        if (txn_lockmode == LockMode::SHARED) {
          txn->GetSharedLockSet()->erase(rid);
        } else {
          txn->GetExclusiveLockSet()->erase(rid);
        }
        cv_.notify_all();
        return true;
      }
      return false;
    }
  };

rehash的bug

全力感謝 记一个关于std::unordered_map并发下rehash引起的的BUG

但gradescope還是很爛

這個bug可怕在哪裡? 只在gradescope上發生，gradescope跑得很慢，gradescope限制output的總量(還有build的output已經先佔了一定容量)，也很難猜(我當初沒想到阿，明明都用id做hash key了)

root cause是unordered_map會rehash，所以可能同個key寫到同一個值，讓之前寫的不見 所以讓有用到hash的container都reserve，減少rehash的可能

但是在我的code上這樣會過不了valgrind，但我懶了，反正目的是認識concurency control，目的已經達到了

這次的反省是使用別人的東西之前，要好好看文件(這個我好像之前在別的文章打過一樣的結論…) 特別注意有沒有做一些user不知道的事(像rehash)，這種transparent的行為都是悲劇與痛苦的來源

最後，附上修法，除了LockQueue以外，還有LockManager的lock_table要做reserve


class LockManager {
  enum class LockMode { SHARED, EXCLUSIVE };

  class LockRequest {
   public:
    LockRequest(txn_id_t txn_id, LockMode lock_mode) : txn_id_(txn_id), lock_mode_(lock_mode), granted_(false) {}

    txn_id_t txn_id_;
    mutable LockMode lock_mode_;
    mutable bool granted_;
  };

  struct LockRequestHash {
    std::size_t operator()(const LockRequest &a) const { return a.txn_id_; }
  };

  struct LockRequestEq {
    bool operator()(const LockRequest &a, const LockRequest &b) const { return a.txn_id_ == b.txn_id_; }
  };

  class LockRequestQueue {
   public:
    using QIter = std::unordered_set<LockRequest, LockRequestHash, LockRequestEq>::iterator;
    using LocalLock = std::unique_lock<std::mutex>;
    using WaitPred = bool (*)(QIter &);
    using WoundPred = bool (*)(QIter &, const RID &);
    std::mutex lk_;
    std::unordered_set<LockRequest, LockRequestHash, LockRequestEq> request_queue_;
    // for notifying blocked transactions on this rid
    std::condition_variable cv_;
    // txn_id of an upgrading transaction (if any)
    // txn_id_t upgrading_ = INVALID_TXN_ID;
    LockRequestQueue() { request_queue_.reserve(50); } // avoid rehash

    QIter Enqueue(Transaction *txn, const RID &rid, LockMode mode) {
      std::unique_lock<std::mutex> ul(lk_);
      auto &q = request_queue_;
      return q.insert(LockRequest{txn->GetTransactionId(), mode}).first;
    }

    bool WaitWound(Transaction *txn, const RID &rid, WaitPred wait_pred, WoundPred wound_pred);

    bool Unlock(Transaction *txn, const RID &rid, LockMode txn_lockmode) {
      std::unique_lock<std::mutex> ul(lk_);
      auto ptr = request_queue_.find(LockRequest{txn->GetTransactionId(), txn_lockmode});
      if (ptr != request_queue_.end()) {
        request_queue_.erase(ptr);
        if (txn_lockmode == LockMode::SHARED) {
          txn->GetSharedLockSet()->erase(rid);
        } else {
          txn->GetExclusiveLockSet()->erase(rid);
        }
        cv_.notify_all();
        return true;
      }
      return false;
    }
  };

 public:
  /**
   * Creates a new lock manager configured for the deadlock prevention policy.
   */
  LockManager() { lock_table_.reserve(50); } // avoid rehash

  ~LockManager() = default;

  /*
   * [LOCK_NOTE]: For all locking functions, we:
   * 1. return false if the transaction is aborted; and
   * 2. block on wait, return true when the lock request is granted; and
   * 3. it is undefined behavior to try locking an already locked RID in the
   * same transaction, i.e. the transaction is responsible for keeping track of
   * its current locks.
   */

  /**
   * Acquire a lock on RID in shared mode. See [LOCK_NOTE] in header file.
   * @param txn the transaction requesting the shared lock
   * @param rid the RID to be locked in shared mode
   * @return true if the lock is granted, false otherwise
   */
  bool LockShared(Transaction *txn, const RID &rid);

  /**
   * Acquire a lock on RID in exclusive mode. See [LOCK_NOTE] in header file.
   * @param txn the transaction requesting the exclusive lock
   * @param rid the RID to be locked in exclusive mode
   * @return true if the lock is granted, false otherwise
   */
  bool LockExclusive(Transaction *txn, const RID &rid);

  /**
   * Upgrade a lock from a shared lock to an exclusive lock.
   * @param txn the transaction requesting the lock upgrade
   * @param rid the RID that should already be locked in shared mode by the
   * requesting transaction
   * @return true if the upgrade is successful, false otherwise
   */
  bool LockUpgrade(Transaction *txn, const RID &rid);

  /**
   * Release the lock held by the transaction.
   * @param txn the transaction releasing the lock, it should actually hold the
   * lock
   * @param rid the RID that is locked by the transaction
   * @return true if the unlock is successful, false otherwise
   */
  bool Unlock(Transaction *txn, const RID &rid);

  LockRequestQueue &GetQ(const RID &rid) {
    std::unique_lock<std::mutex> ul(latch_);
    return lock_table_[rid];
  }

 private:
  std::mutex latch_;
  std::unordered_map<RID, LockRequestQueue> lock_table_;
};

Ref

大老的實現筆記與code 大老的code 有人把recovery的test挖出來 2021 CMU-15445/645 Project #4 : Concurrency Control 【完】