###### tags: `database` # Assignment 5 report 2 組員: 109062274, 109062314, 109062315 ## 助教實作 ### Tx with lower txNums lock first 為了確保較小的 Tx 能優先取得 lock，助教的方法為在 `StoredProcedure::prepare` 先透過函式 `MicroTxnProc::prepareKeys` 取得 read/write sets，方法為透過 `MicroTxnProcParamHelper` 獲取相關資訊，接著再呼叫 `StoredProcedure::scheduleTransactionSerially`，此函式保證一次只有一個 RTE 能夠新增 Tx (給予 Tx number)，並同時將所需的 lock 做預約，而預約指的是呼叫 `ConservativeConcurrencyMgr` 定義的函式 `bookReadKeys` 與 `bookWriteKeys`，對 read/write sets 裡的物件不重複地呼叫 `ConservativeLockTable::requestLock`，將當前的 Tx number 放入此物件對應 `ConservativeLockTable::Lockers` 之 `requestQueue`，而這個 Queue 會依序紀錄前來預約之 Tx，方便之後判斷拿該物件 lock 之 Tx 是不是之中最小的。 ### Tx get lock all at once 接著為了一次取得所需的 lock，作法為在呼叫 `MicroTxnProc::executeSql` 之前，先呼叫 `ConservativeConcurrencyMgr::acquireBookedLocks`，這個函式會先取得 write set 的 `xlock`，再獲取 read set 與之不重複部分的 `slock`，方法為呼叫 `ConservativeLockTable` 的 `xLock` 與 `sLock`，而這些函式會先取得 `anchor` 做 `synchronized`，確保一次僅有一個 Tx 能對該物件操作，然後再取得該物件的 `lockers` 進行以下的流程: * 判斷 Tx 是否已取得 lock，若已取得則從 `requestQueue` 移出 Tx 並 return， * 判斷物件是否能上 s/xlock 以及 Tx 是否為 `requestQueue` 的第一個元素，若任一不成立則對 `anchor` 呼叫 `wait`，直到被 notified 再繼續判斷 * 將 `requestQueue` 中第一個元素移除，接著將 Tx 放入 `lockers` 中的 `sLockers/xLocker`，代表真正取得 lock * 最後對 anchor 呼叫 `notifyAll` ### Why works 主要歸功於: 1. Tx 創立的同時將先將所需的 lock 進行註冊 2. `requestQueue` 能確保先來預約的 Tx 先獲取 lock ## 與我們的做法比較 ### Tx with lower txNums lock first 因為創建一個新的 transaction txNum 是累加的數字，我們的做法是用一個 shared variable `monitoredTxSerialNumber` 來監測目前的 txNum 是否是所有未完成的 transaction 中最小的一個。如果是，則可以嘗試鎖住 lockTable 一氣呵成取得所有 lock。也就是說我們把 Tx 要依序執行的邏輯和取得所有 lock 的邏輯寫在一起。 然而我們的做法會產生一個嚴重的效能 bottleneck。如果當前的 txNum 是所有未完成的 transaction 中最小的一個，但是卻無法一氣呵成取得所有 lock，其他未完成的 transaction 便要等 txNum 中最小的一個取得所有 lock 才有機會取得自己要的 lock。 因此我們認為助教的寫法比較好，助教的寫法先利用是 java 的 ReentrantLock，保證一次只有一個 RTE 能夠新增 Tx (給予 Tx number)。並且利用 queue 這個資料結構，讓 locker 能夠知道哪些 transaction 將依序取得此 lock。 ### Tx get lock all at once 我們的做法是直接鎖住 lockTable ，讓 txNum 中最小的一個取得所有 lock。 然而這個做法讓其他 txNum 較大的 transaction 即使想要 lock 的 object 沒有 conflict，還是必須等待比他小的 transaction 取完所有 lock ，才能取得自己想要的 lock。 我們認為助教的方法比較好，第一個於原因是因為取得 lock 不是鎖住 lockTable 一氣呵成取得所有 lock，而是一個個取得所需要的 lock。並且因為在 `Lockers::requestQueue` 中有存取那些 transaction 要依序取得此 object 的 lock 的順序，所以可以達到即使不鎖住 lockTable ，還是可以依 txNum 的順序執行，以達到 deterministic 的效果。 第二個原因是因為助教的寫法可以讓 txNum 較大的 transaction 沒有 conflict 的 object 先鎖起來，不用等輪到時才取得 lock，讓 conservative locking 有更高的 throughput。 ### Implement MGL 我們有實作 MGL，基於 MGL 我們需一同對更高層的 Block 上鎖，`BlockId` 的方法為計算目標 record 位於第幾個 block。Block ID 的公式如下。 $$ blockId = {\rm{integer\_division}}(recordId \times slotSize, blockSize) $$ 但助教寫法是沒有實作 MGL 的。因此我們的實作是更貼近真實的情況。