近期開啟的新系列,以分享資料庫系統相關的論文並簡介內容為主,不會講得太深入,但是會需要些對資料庫系統內部運作原理的基本概念。
這篇論文 [1] 主要是把近期常被拿來討論幾個主要的 Concurrency Control 的分支,放在具備 1000 個 Core 的環境下進行測試。 目的是為了瞭解這些做法在 Core 數量極多的機器上的 Scalability 如何。 在研究過程中,他們也嘗試去優化這些方法,盡可能地避免實作上可能會造成的瓶頸。 所以這篇論文的研究也可以當作在 multi-thread 環境下,實作這些 CC 作法的參考。
基本資料
- 論文作者群:Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, Michael Stonebraker
- 研究機構:MIT, CMU
- 發表會議/期刊:Very Large Database (VLDB) 2014 年期刊
需要具備的知識
- 知道 Transaciton 是甚麼
- 了解 Concurrency Control 的目的
- 對 multi-threads programming 有基本認識
做為測試目標的 Concurrency Control 作法
簡單介紹一下這篇論文所探討的主流 Concurrency Control 作法。
Two Phase Locking (2PL)
最傳統且常見的 Concurrency Control 作法。 基本概念是在 Transaction (以下簡稱 Tx) 取得資料之前先把資料鎖住,防止其他 Tx 存取。 一般又會依照讀寫的狀況分成 shared lock (slock) 跟 exclusive lock (xlock)。 一旦 Tx 開始放棄 lock 就不能再 lock 資料,以確保資料能夠正確的 recovery。
其中這篇論文又依照處理 deadlock 的方式分成以下三種作法:
DL_DETECT
不會預先防範 deadlock 的發生,但是發生的話可以藉由建立一個 wait-for graph 來找出發生的地方,並且會把其中一個卡住的 Tx abort 來解除 deadlock。
NO_WAIT
只要 Tx 存取資料的時候,發現可能需要等待其他 Tx 釋放 lock,就會自動 abort。
WIAT_DIE
Tx A 存取資料時,如果發現資料被鎖住的話,依照下列情況做處理:
- 如果 Tx A 比鎖住資料的 Tx B 年輕 => abort Tx A
- 如果 Tx A 比鎖住資料的 Tx B 老 => 等待 Tx B 釋放 lock
這個方法確保不會有 deadlock 發生,因為一個 deadlock 互相等待的關係之中,一定有一個 Tx 比較年輕,因此只要讓其中一邊沒機會等待就可以避免 deadlock。
這個方法成本比 DL_DETECT 低很多,又不會亂 abort Tx,所以是最常見的作法。
Timestamp Ordering (T/O)
Timestamp ordering 的基本概念是 DBMS 會為每個 Tx 配發一個 timestamp (以下簡稱 ts),這個 ts 會作為判斷 Tx 順序的標準。 除此之外,Tx 一般會將自己的 ts 寫在自己寫入過的資料上面,用來給後面存取的 Tx 辨識。
Basic T/O
Tx 會檢查資料上的 ts,若上面的 ts 比自己的 ts 還要年輕,就會 abort。 反之,照常寫入資料。
Multi-version Concurrency Control (MVCC)
每次 Tx 寫入資料的時候,直接創造一個新的版本另外儲存,原本的版本就保留不動。 好處是如果有其他人正在讀同樣的資料,就不會被寫入影響到 (reads do not block writes)。
Optimistic Concurrency Control (OCC)
Tx 在執行期間不做任何檢查,讀取任何想讀的資料,寫的時候先寫在一個獨立的空間。 最後 Tx 要 commit 時檢查之前的讀寫是否會跟人家衝突 (conflict)。 沒問題的話就把先前寫入的東西寫到共用的空間。 有問題就 abort Tx。 一種先斬後奏的作法。
H-STORE
H-Store [2] 這種系統專用的作法。 先將資料切割成多個分區 (partition),然後每個分區交給一個 core 處理,並且每個分區一次只允許一個 thread 執行。 因此在一個分區內不需要處理 Concurrency Control。 若有 Tx 想要跨分區存取,就必須要先把這些分區全部鎖住。
Challenges
- 需要實作各種 CC 方法
- 需要盡可能地避免實作上的瓶頸
有用的發現
主要的瓶頸來源
- Memory Allocation:很多時間會浪費在等 malloc 分配記憶體。解決方法是使用 previous work (TCMalloc [3], jemalloc [4]) 來為每個 thread 建立 memory pool,減少分配的 cost。
- Lock Table: 避免使用 centrolized lock table,而是將 lock 儲存在各個 tuple 中,但是可能需要耗費額外記憶體。
- Mutex: Mutex 是一個很昂貴的動作,造成 CPU 需要做多次 message passing。2PL 主要出現在 Deadlock detection,Timestamp-based 出現在 centrolized timestamp allocator。
實作 Scalable 2PL 的技巧
- 實作 lock-free deadlock detection 方法: 每個 Tx 只將等待的目標存在自己的 queue 中,detector 會看過所有 queue 來尋找 partial wait-for graph。
- 讓等太久的 Tx abort: 原本 Tx 等待 lock 時,會等到 lock 被釋放才回復執行。 根據實驗結果顯示,若能適度讓等太久的 Tx abort,可以減少 wait chaining 的狀況,因此反而可以增加 throughput。 實驗結果顯示等待上限設為 100us 差不多。
實作 Scalable Timestamp-based CC 的技巧
分配 Timestamp
分配 timestamp 必須是一個 centralized 的架構,以確保 timestamp 的順序性,但是也造成了效能瓶頸。這邊有四種解法:
- 使用 Atomic Addition 指令。
- 使用 Atomic Addition 指令,一次取得大量 timestamps (batching)。
- 讓 timestamp 使用 core 的 local clock 加上 thread id 組成。這個方法需要 core 之間 synchronize clocks,用軟體實作會非常昂貴。目前只有 Intel 提供硬體支援。
- 用 hardware counter 來產生 timestamp,目前尚未有 CPU 提供支援。
Clock 的作法在所有實驗上取得最佳效果,但是在 high-contention 的實驗中,單純使用無 batch 的 atomic addition 效果就跟 clock 一樣好。有鑑於簡單性與支援性,之後都採用 atomic addition 這個做法。
分散式 Validation
類似 Microsoft Hakaton [5] ,在每個 tuple 上 validate tx,而不是用 centralized 的 critical section。
實作 H-Store 的技巧
讓 thread 直接 access 其他 thread 的 memory,而不是還要另外送 query 過去讓其他 core 處理。
實驗
實驗的部分就不細談,基本上就是使用 YCSB Benchmark 去模擬各種 workloads,並且研究每種作法在不同環境的優缺點,以幫助使用者選擇自己適合用甚麼 Concurrency Control 方法。 實驗的數量很多,因此有興趣的人可以自己細看。
另外提一下,1000 Cores 的機器目前還不存在,所以論文中是使用將多台機器連接在一起,並使用模擬器的方式去模擬的。
參考資料
[1] Yu, Xiangyao, et al. “Staring into the abyss: An evaluation of concurrency control with one thousand cores.” Proceedings of the VLDB Endowment 8.3 (2014): 209-220.
[2] Kallman, Robert, et al. “H-store: a high-performance, distributed main memory transaction processing system.” Proceedings of the VLDB Endowment 1.2 (2008): 1496-1499.
[3] Ghemawat, Sanjay, and Paul Menage. “Tcmalloc: Thread-caching malloc.” (2009).
[4] J. Evans. jemalloc.http://canonware.com/jemalloc
[5] Neumann, Thomas, Tobias Mühlbauer, and Alfons Kemper. “Fast serializable multi-version concurrency control for main-memory database systems.” Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. ACM, 2015.