database
組員: 109062274, 109062314, 109062315
為了確保較小的 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 是不是之中最小的。
接著為了一次取得所需的 lock,作法為在呼叫 MicroTxnProc::executeSql
之前,先呼叫 ConservativeConcurrencyMgr::acquireBookedLocks
,這個函式會先取得 write set 的 xlock
,再獲取 read set 與之不重複部分的 slock
,方法為呼叫 ConservativeLockTable
的 xLock
與 sLock
,而這些函式會先取得 anchor
做 synchronized
,確保一次僅有一個 Tx 能對該物件操作,然後再取得該物件的 lockers
進行以下的流程:
requestQueue
移出 Tx 並 return,requestQueue
的第一個元素,若任一不成立則對 anchor
呼叫 wait
,直到被 notified 再繼續判斷requestQueue
中第一個元素移除,接著將 Tx 放入 lockers
中的 sLockers/xLocker
,代表真正取得 locknotifyAll
主要歸功於:
requestQueue
能確保先來預約的 Tx 先獲取 lock因為創建一個新的 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。
我們的做法是直接鎖住 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。
我們有實作 MGL,基於 MGL 我們需一同對更高層的 Block 上鎖,BlockId
的方法為計算目標 record 位於第幾個 block。Block ID 的公式如下。
但助教寫法是沒有實作 MGL 的。因此我們的實作是更貼近真實的情況。