Index Concurrency Control

在之前討論的資料結構中，為了討論方便，所以只考慮了 single-threaded 的情況，但在實際情況中，除了一些特別的資料庫 (如 VoltDB、Redis) 之外，大部分的 DBMS 都需要透過 multi-threaded 來利用多核心的優勢。

本節要討論的 concurrency control 就是討論在 multi-threaded 的情況下，要如何確保結果是正確的。

我們通常會從兩個層面來討論 concurrency control 的正確性 :

• Physical Correctness : 內部的資料是否正確 (本篇重點)
• Logical Correctness : 我們是否能看到應該看到的資料 (後面會討論)

Locks and Latches

這裡我們會重點討論 latch，在 latch 中有兩種 mode :

• read mode
  • 多個 thread 同時讀取
  • 當別的 thread 已經有 latch 時，可以再取得 read latch
• write mode
  • 只能有一個 thread 取得 write latch
  • 當別的 thread 已經有任一種模式的 latch 時，就無法獲得 write latch

Latch Implementations

在實現上，latch 不應該佔據太多的記憶體，且在沒有競爭的情況下，要有快速獲取的方法。

在 DBMS 中，主要有以下幾種實現方式 :

• Test-and-Set Spin Latch (TAS)
• Blocking OS Mutex
• Reader-Writer Latches

Test-and-Set Spin Latch (TAS)

這種方式的原理是 thread 不斷的執行 CAS (Compare-And-Swap) 來更新一個記憶體中的位置，並由 DBMS 來控制成功或失敗後的行為，可以給予比 mutex 更多的彈性及效能。

• 優點
  • 效能佳
• 缺點
  • 無法擴展以及 cache coherence 的問題
• 範例
  • std::atomic<T>

CAS 是一種原子操作，它比較一個內存位置的值與給定的預期值，如果它們相同，則將該內存位置的值更新為新值，由於是原子操作，所以不會被其他 thread 中斷。

Blocking OS Mutex

這種方式是直接使用由 OS 所提供的互斥鎖，在 Linux 的 futex 中 DBMS 會先嘗試獲得 user-space mutex，如果獲取成功則代表 latch 被成功設定，如果失敗的話就會去嘗試獲取 kernel-space mutex，如果依然無法獲得就會被放進 block scheduler，而 block scheduler 會決定下一個要被執行的 thread。

• 優點
  • 使用簡單
• 缺點
  • 效能較差 (每次鎖定和解鎖需要 25ns)
• 範例
  • std::mutex

Reader-Writer Latches

這種方式是建立在 spinlock 之上，但與前面兩種方式不同，這種方式可以允許 latch 以 read mode 或 write mode 來被取得。我們會追蹤有多少 thread 取得了 latch 以及有多少 thread 在等待 latch，並依據不同的 policy (如 reader-preferred、writer-preferred、fair reader-writer locks) 來維護 priority queue 來決定下一個要被執行的 thread。

• 優點
  • 允許併發的讀取，在讀多寫少的情況下效能較佳
• 缺點
  • 實作較為複雜
  • 有可能會有 starvation 的問題
  • 需要額外的儲存空間來儲存需要用來排序的 metadata
• 範例
  • std::shared_mutex

Hash Table Latching

對於 hash table 來說併發控制是相對簡單的，這是因為在 hash table 中所有的 thread 的訪問方向都相同，且一次只會訪問一個 page / slot，因此不會有 deadlocks 的問題。

如果 hash table 需要 resize 的時候，我們只需要對整個 hash table 加鎖即可，動態的 hash table 也是透過類似的方式實現。

主要有兩種方式來實現 hash table 的 latch (依據粒度) :

• Page Latches
• Slot Latches

Page Latches

每個 page 都有自己的 latch 來保護整個頁面的資料，thread 在訪問 page 的時候需要先獲得 read / write 的 latch。

• 優點
  • 單個 thread 訪問同一 page 的多個 slot 時速度快
• 缺點
  • 併發度低，因為只有一個 thread 可以訪問 page

Slot Latches

每個 slot 都有自己的 latch 來保護 slot 的資料。

• 優點
  • 併發度高，因為不同的 thread 可以訪問不同的 slot
• 缺點
  • 增加了 latch 的數量，可能會增加儲存和計算的 overhead

除了上述的兩種方式，也可以使用 latch-free 的方式來實現 hash table，直接使用 CAS 來探測是否可以進行操作，在某些情況下可以提高效率。

B+Tree Latching

在 B+Tree 中，我們需要考慮以下兩個情況 :

• 多個 thread 同時修改同一個 node
• 一個 node 在遍歷的時候另一個 thread 在 merge / split

Latch Crabbing / Coupling

Latch Crabbing 是一種可以允許多個 thread 同時訪問 (修改) 一個 node 的協定，基本思路如下 :

1. 獲取 parent 的 latch
2. 獲取 child 的 latch
3. 如果 child 是 safe 的話，就釋放 parent 的 latch

safe 的定義是發生操作時，該節點不會被 merge / split :

• insert : 該節點未滿
• delete : 該節點超過半滿

Search

從 root 開始往下遍歷，不斷的獲取 child 的 read latch 並釋放 parent 的 latch 直到 leaf node。

Insert / Delete

從 root 開始往下遍歷， 並獲取 child 的 write latch， 如果獲取就檢查 child 是否 safe， 如果是的話就釋放之前獲取的所有 latch。

Better Latching Algorithm

在實際的應用中，每次都要在路徑中獲取 write latch 很容易成為瓶頸 (特別是 root node)，並且大部分的操作並不會造成 merge / split，因此我們可以採用一種較為樂觀的方式。 在遍歷的時候使用 read latch，到達 leaf node 的時候再獲取 write latch 來更新或刪除值，如果在過程中發現有 merge / split 的情況，就重新從 root 開始直接原始的 latch crabbing。

Leaf Node Scans

前面只有討論 top-down 的 latch crabbing，但在 range query 中，我們會需要進行橫向的訪問。

在 top-down 的訪問中， thread 只能從下層節點來獲取 latch，如果 latch 無法被獲取， thread 就需要等待，因此避免了 deadlock 的問題。但在 leaf node scans 中，如果 thread 1 嘗試進行 scan，而 thread 2 則在刪除節點，就會導致 deadlock 的問題。

當獲取 latch 失敗時，thread 應該快速停止所有動作並且釋放所有 latch，最後再重新開始，這是因為我們需要盡量避免長時間的等待以及不需要的計算。

References

• Spinlock