刷题刷得头疼，水篇blog。这个BUG是我大约一个月前，在做15445实现lock_manager的时候遇到的一个很恶劣但很愚蠢的BUG，排查 + 摸鱼大概花了我三天的时间，根本原因是我在使用std::unordered_map做并发的时候考虑不周。但由于这个BUG无法在我的本地复现，只能提交代码后再gradescope上看到执行日志，而且打印的日志还不能太多，因为gradescope的执行比较慢，打印日志如果稍微多加一点就会报TIMEOUT，所以着实让我抓狂了一段时间。最后的解决也很突然，非常有戏剧性，可以考虑拿来水点东西。感觉自己写blog很拖刷leetcode和背八股的节奏，所以找到实习前可能写不了太多了。
功能描述15445 Project4要求我们为bustub添加并发访问控制，实现tuple粒度的strict 2PL。简单来说，一个RID表示着一个tuple在磁盘上的位置，因此可以唯一标识tuple；一个事务就是一个线程。事务会并发的对这些tuple进行读写访问，因此必须要引入lock来对访问进行同步，而这个Project要求我们将lock的粒度设定为tuple。为了实现这一点，bustub设定了一个单例的LockManager（但其实现方法并不是单例的），要求任何事务在访问某个RID之前，都要向这个事务申请锁。如果事务进行的是读访问操作，要调用LockManager的lock_shared()方法申请S-LOCK(共享锁，或者说读锁)，否则操作就是写操作，要调用lock_exclusive()方法申请X-LOCK(独占锁，或者说是写锁)；如果事务已经获取了S-LOCK，希望在不释放S-LOCK的情况下将锁升级为X-LOCK，则要调用lock_upgrade方法。此外，由于strict 2PL只能保证serializable Schedule，但无法保证不存在死锁，因此LockManager还需要实现死锁检测功能（但这不是本篇blog的重点）。LockManager的声明如下：
class LockManager { enum class LockMode { SHARED, EXCLUSIVE, UPGRADE }; enum class RIDLockState { UNLOCKED, S_LOCKED, X_LOCKED }; class LockRequest { public: LockRequest(txn_id_t txn_id, LockMode lock_mode) : txn_id_(txn_id), lock_mode_(lock_mode), granted_(false), aborted_(false) {} txn_id_t txn_id_; LockMode lock_mode_; bool granted_; bool aborted_; }; class LockRequestQueue { public: LockRequestQueue() = default; LockRequestQueue(const LockRequestQueue &rhs) = delete; LockRequestQueue operator=(const LockRequestQueue &rhs) = delete; // DISALLOW_COPY(LockRequestQueue); RIDLockState state_; std::mutex queue_latch_; std::list<LockRequest> request_queue_; std::condition_variable cv_; // for notifying blocked transactions on this rid bool upgrading_ = false; }; public: /** * Creates a new lock manager configured for the deadlock detection policy. */ LockManager() { enable_cycle_detection_ = true; cycle_detection_thread_ = new std::thread(&LockManager::RunCycleDetection, this); LOG_INFO("Cycle detection thread launched"); } ~LockManager() { enable_cycle_detection_ = false; cycle_detection_thread_->join(); delete cycle_detection_thread_; LOG_INFO("Cycle detection thread stopped"); } /* * [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); /** * Checks if the graph has a cycle, returning the newest transaction ID in the cycle if so. * @param[out] txn_id if the graph has a cycle, will contain the newest transaction ID * @return false if the graph has no cycle, otherwise stores the newest transaction ID in the cycle to txn_id */ bool HasCycle(txn_id_t *txn_id); /** @return the set of all edges in the graph, used for testing only! */ std::vector<std::pair<txn_id_t, txn_id_t>> GetEdgeList(); /** Runs cycle detection in the background. */ void RunCycleDetection(); private: std::unordered_map<txn_id_t, std::vector<txn_id_t>> BuildTxnRequestGraph(); std::mutex latch_; std::atomic<bool> enable_cycle_detection_; std::thread *cycle_detection_thread_; /** Lock table for lock requests. */ std::unordered_map<RID, LockRequestQueue> lock_table_; /** Waits-for graph representation. */ std::unordered_map<txn_id_t, std::vector<txn_id_t>> waits_for_; };