epoch 式回收(epoch-based reclamation, EBR)
/ EP-uhk /
危害指標保護一個執行緒所碰的每個個別節點——精確,但每次存取都要付出一次發布。epoch 式回收採取較粗、較便宜的視角:它不追蹤確切哪些節點正在使用,而是追蹤一個執行緒正運作於哪個寬廣的時間窗,唯有當它確知每個執行緒都已越過某塊記憶體被移除時所在的那個窗,才釋放該記憶體。它以精確度換取極低的每次存取負擔。
機制如下。有一個全域 epoch 計數器,偶爾向前跳動。每個執行緒進入一段會碰共享結構的區間(讀者端臨界區間)時,宣告當前的全域 epoch 並把自己標為活躍;結束時把自己標為非活躍(靜止 quiescent)。一個節點被移除時,會退役到一個以當前 epoch 標記的桶裡。唯有當每個執行緒都已靜止、或已前進到更新的 epoch 時,該節點才安全可釋放——到那時你確信沒有執行緒還能身處該節點存活時所在的 epoch,因此沒人持有指向它的指標。當所有活躍執行緒都同意已看過當前 epoch 時,全域 epoch 就能前進。靜止狀態回收(QSBR)是密切相關的變體,執行緒只是通過已知的靜止點(如事件迴圈的頂端),而不必為每個臨界區間加上括號。
吸引力在於速度:進入與離開一個 epoch 臨界區間只是幾個便宜的原子操作,遠少於危害指標的逐指標發布,所以讀取幾乎免費。誠實的代價是同一枚硬幣的另一面——單一執行緒若在臨界區間內停擺,或乾脆永遠不到達靜止狀態,就會阻止 epoch 前進,退役的記憶體便無上界地堆積,直到那個執行緒配合為止。因此 EBR 假設執行緒會及時通過靜止狀態,若某執行緒可能在結構內任意長時間阻塞,它就不適合。Crossbeam(Rust)與許多資料庫引擎正是看中它讀者端的便宜而採用 EBR。
/* 讀者端:以進入/離開 epoch 為臨界區間加上括號。 */ epoch_enter(); /* 宣告當前全域 epoch,標為活躍 */ Node *p = lookup(key); use(p->data); epoch_leave(); /* 標為靜止 */ /* 移除端:retire(node) 用當前 epoch 標記它;唯有所有執行緒都已 離開那個 epoch(或已靜止)後,該節點才被釋放。 */
讀取由便宜的 enter/leave 呼叫加上括號;退役節點要等到每個執行緒都越過它被移除時的那個 epoch 才釋放。
EBR 的讀取幾乎免費,但只要一個執行緒在臨界區間內停擺(或永不靜止),就會卡住 epoch 前進,讓退役記憶體無上界成長。它假設執行緒會及時靜止。