Try   HackMD
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 定義的函式 bookReadKeysbookWriteKeys,對 read/write sets 裡的物件不重複地呼叫 ConservativeLockTable::requestLock,將當前的 Tx number 放入此物件對應 ConservativeLockTable::LockersrequestQueue,而這個 Queue 會依序紀錄前來預約之 Tx,方便之後判斷拿該物件 lock 之 Tx 是不是之中最小的。

Tx get lock all at once

接著為了一次取得所需的 lock,作法為在呼叫 MicroTxnProc::executeSql 之前,先呼叫 ConservativeConcurrencyMgr::acquireBookedLocks,這個函式會先取得 write set 的 xlock,再獲取 read set 與之不重複部分的 slock,方法為呼叫 ConservativeLockTablexLocksLock,而這些函式會先取得 anchorsynchronized,確保一次僅有一個 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=integer_division(recordId×slotSize,blockSize)
但助教寫法是沒有實作 MGL 的。因此我們的實作是更貼近真實的情況。