Concurrent Prefix Recovery: Performing CPR on a Database

TL;DR

• 可以做到紀錄每個session的最後一個commit紀錄
• 用epoch的方式來做，直接做snapshot寫進storage，避免WAL需要大量append的overhead
• 呈上，因為每個session各自完成自己的部分，不需要lock來synchronization

CPR

Transactionally Consistent

如果一個snapshot包含所有被committed的資料，但沒有任何沒被committed的資料，那就可以被稱為Transactionally Consistent。

Prefix Recovery

Prefix recovery比transactionally consistent更嚴格。一個snapshot必須要能recover system-wide、所有transaction的行為，也就是說，所有issued的操作。

一個簡單的方式是在確保consistent之前，停止accept新的transactions，這種作法稱作commit-consistent checkpointing。

另外一種asynchronous的做法是將database分成兩個版本: stable和live。屬於prefix的Transactions會同時更新stable和live，不屬於prefix的transaction只更新live。Stable的版本會asynchronous的被做成snapshot。

Concurrent Prefix Recovery

定義: 對每個client $C$，database state包含了所有的某個時間點$T_C$之前commited的紀錄，但不包含此$T_C$之後的紀錄。

State Machine

Algorithm

Rest Phase

在rest phase的時候才transaction可以commit，在commit的時候，就是執行$Commit$ function，把global phase改成PREPARE，然後在epoch註冊PrepareToInProg，在bump的時候執行。

Prepare Phase

在這個phase會改變database version。任何一個transaction只有在它所有的read write instrcution set都屬於當前的verstion $v$才會被執行。如果transaction含有對大於$v$的資料做讀寫，就abort。

In-Progress Phase

如果所有的threads都進入PREPARE phase，$PrepareToInProg$就會被執行。這時候如果refresh自身的狀態，就會進入IN-PROGRESS，並且在$v+1$的時候執行transaction，並且把records的version都更新成$v+1$。

Wait-Flush Phase

當所有的thread都進入IN-PROGRESS，epoch framework會執行$InProgToWaitFlush$。首先，global phase設定成WAIT-FLUSH。然後，database的版本$v$被capture，如果一個record的version是$v+1$，stable version會被用來commit，不然就用live version。

當這些處理完，global phase被更新成REST，然後版本被更新成$v+1$。

Per Thread Algorithm

Run

Thread 每loop k次，就refresh local的phase和version，如果這時候state machine進到in_progress，就記住time $t_T$

Execute

CPR in FASTER

CPR在FASTER上的實作多了一個state (如下圖)。

States

PREPARE

在PREPARE phase，thread會嘗試替local的pending list裡的request獲取lock (latch)，並且在完成以後才釋放。處理的邏輯如下：

• acquire latch
• 如果record在mutable region，in-place update
• 如果record在fuzzy region，放進pending-list之後處理
• 如果record在read-only region，做copy-on-write
• 如果record不在記憶體，把從storage撈進記憶體的請求放進pending-list
• 如果無法acquire latch或是發現record version > local version，就refresh epoch並且進入IN-PROGRESS

IN-PROGRESS

當所有的thread都進入PREPARE，而且完成acquring latch for pending requests，global state就transition到IN-PROGRESS，而thread在之後也會靠著refresh來進入IN-PROGRESS。

設計上，在$v$之前的操作都會被commit，而之後的record不會，因此版本是$v$的record，如果在記憶體的話，就會嘗試獲取exclusive lock來做copy-on-write，並且把此record append在最後面，設定version為$v+1$。如果record的版本 > $v$，就做in-place update。

WAIT-PENDING

當所有thread都進入IN-PROGRESS，則global state進入WAIT-PENDING。在此phase，所有的thread不是在IN-PROGRESS，就是在WAIT-PENDING，因此做的事跟IN-PROGRESS差不多。

WAIT-FLUSH

當所有request都完成以後，我們紀錄HybridLog的tail offset，並且把read-only的offset移至此offset。

Recovery

在recover的時候，我們scan HybridLog index from $S = min(L^i_s, L^h_s)$ to $E = max(L^i_e, L^h_e)$，然後把每個slot 指向record version $\le v$的record index。

References

• Concurrent Prefix Recovery: Performing CPR on a Database