狠狠撸

Copyright?2017 NTT corp. All Rights Reserved.
并行実行制御の最适化手法
NTT ソフトウェアイノベーションセンタ
中園翔
nakazono.sho@lab.ntt.co.jp

2Copyright?2017 NTT corp. All Rights Reserved.
トランザクション:
? 不可分な一連の操作 == n回のread/write操作(0<n)
トランザクション処理の目標:
? Atomicity: n回のread/write操作を1回のレジスタ操作と同様に扱えること
? Consistency: 一貫性を守ること. A,I,Dに加えてDBの制約条件を常に満たすこと
? Isolation: トランザクションが他の並行するTxの影響を受けないこと
? Durability: コミット済みのトランザクションは必ず永続化されていること
トランザクション処理の構成要素:
? ログ管理機構(Log manager)
? 並行実行制御(Concurrency Control)
? データ構造, インデックス(Data Structure)
トランザクションと並行実行制御

並行実行制御の目的
T1: Read(x) Write(x) T2: Read(y) Write(y)Read(x)
Read(x) Write(x)History: Read(x)Read(y) AbortWrite(y) Commit
T1: Read(x) Write(x) T2: Read(x) Write(x)Read(x)
Read(x) Write(x)History: Read(x)Read(x) CommitWrite(x) Commit

各トランザクションを直列に実行した際と等価なスケジュール空間が得られることを
直列化可能(Serializable)と呼ぶ.
といったトランザクションが並行実行されている時、
直列化して実行した際と等価なスケジュールを得られれば良い.
例は以下.(全てcommitされるものとする)
History2,3がSerializableであることの証明/詳細は
http://qiita.com/kumagi/items/695f1641407fd726d180参照.
直列化可能(Serializable)
T1: Read(x) Write(x) T2: Read(y) Write(x)Read(x) T3: Write(x)
Read(x) Write(x)History1: Read(y) Read(x) Write(x) Write(x)
Read(x) Write(x)History2: Read(x)Read(y) Write(x)Write(x)
History3: Write(x)Abort Abort

直列実行との等価性にはいくつか細分類がある.
最終状態の直列等価性(FSR)のみを前提とすると、探索空間が非常に膨大となり、
実用的でないため、CSRやMVSRが一般的に扱われている.
CSRやMVSR等のスケジュール生成を保証するリソースの操作手法のことを、
Serializableな並行実行制御手法(Concurrency control)と呼ぶ.
? Two Phase Lock
? Timestamp Ordering
? Multiversion Concurrency Control
? 個々の手法については今回は取り扱わない.
? 前回のBDIでの星野さんのスライド等参照のこと.
並行実行制御とスケジュール空間
最終状態が等価なスケジュール(FSR)
ビュー等価なスケジュール(FSR)
競合等価なスケジュール(CSR)
マルチバージョン等価なスケジュール(MVSR)

例えば、2PLのプロトコルに従う実装を考える.
2PLのプロトコルは、要旨としては以下.
? 「ロックの獲得と解放を二相に分割する」
? 「コミットのタイミングで細分類があり、得られるスケジュールが異なる」
? ナイーブに実装すれば「ロック獲得->ロジック->コミット->ロック解放?」
何を「ロック」と見なすか、何を「コミット」と見なすか等、実装上の最適化
の幅がある.
今回は、エンジニアリング的な最適化手法と理論的な最適化手法を紹介する.
并行実行制御の最适化手法

2PLは、トランザクション全体を「成長相(promotion phase)」と「縮退相
(shrink phase)」で構成する手法.
ロックの獲得を成長相で、解放を縮退相でのみ行う.
競合等価のスケジュール(CSR)が得られる.
(一般的に用いられる)Strict 2PL(S2PL)では、Commit Pointの後に縮退相を持つ.
2PLのセマンティクス
成長相縮退相
Lock(x)
Lock(y)
処理ステップ
Lock(z) Release(y)
Release(z)
Release(x)
Commit Point

2PLをナイーブに実装すると以下のようになる.
プロトコル上言及されていない、トランザクションロジックの実行と、
DurabilityのためのWAL書き込み等の後処理等が必要となる.
ここでは2PLの分類としてはStrict 2PL(S2PL)を想定する.
ロック獲得はロジックを実行しながら動的に行うものが一般的であるが,ここでは便宜上分ける.
2PLのセマンティクスと実装(1)
成長相縮退相
成長相ロジック縮退相
ロック獲得
デッドロック回避
ロジックの実行ロックの解放
Commit Point
WALの書き出し
Recordの書き出し
Commitの返却
後処理
プロトコル
実装
処理ステップ

2PLのセマンティクスと実装(2)
成長相縮退相
Commit Point
2PLの性能を向上させる最大の方法は、ロックの保持時間を短くする事.
しかし、実際にナイーブな実装をしてみると、縮退相より前にボトルネックが
集中していることがわかる.
後処理
プロトコル
実装
処理ステップ
ロック獲得
ロジックの実行ロックの解放WALの書き出し
Recordの書き出し
Commitの返却
最も避けたい,
ディスクI/Oが
集中している.

A: I/O Related Delays
レコードを書き終わるまでのI/O wait.
B: Log-induced lock contention
Aに起因するロック保持時間の増加.
それに伴うロックの競合.
C: Excessive context switching
Aを待つ間、スピンする訳にもいかないので、
waitする必要がある. このスケジューラ負荷.
D: Log buffer contention
例えば、WALログとレコードの書き込みを単一
のmutexで管理している場合、WALもwaitする
ことになる. このログバッファで競合が起きる.
Aether [Johnson et al, VLDB 2010]
Ryan Johnson, Ippokratis Pandis, Radu Stoica, Manos Athanassoulis, and Anastasia Ailamaki. 2010. Aether: a
scalable approach to logging. Proc. VLDB Endow. 3, 1-2 (September 2010), 681-692.
DOI=http://dx.doi.org/10.14778/1920841.1920928
Aetherでは、従来のトランザクションのセマンティクスを、2PLやOCCのセマンテ
ィクスに違反しないままうまく変更し、実装上のボトルネックを解決している.
具体的には、以下のボトルネックを問題として挙げている.

ログが直列化されている限り、クライアントにCommitを返却さえしなければ、ログ
が永続化される前にロックを解放しても2PL/OCCの性質は変わらないという提案.
ログの書き出し順序が決定した瞬間（バッファにenqueueした瞬間)をpre-commit
と呼び、この瞬間を2PL/OCCにおけるCommit Pointと見なす.
仮に、あるTxが未commitの永続化されていない値を読んだとしても、読めた(ロック
が解放されている)以上、必ずpre-commit済みの値であることになる.
ログバッファが順序付けされている以上、このTxの永続化が先行することはない.
AetherのEarly Lock Release
precommit point
後処理
ロック獲得
ロジックの実行ロックの解放ログバッファ
へのenqueue
Recordの
書き出し
Commitの
返却
コミット返却

Early Lock Releaseを用いると、トランザクションがロックを保持している期間中
、遅延の大きいディスクI/Oを無くすことができる.
Early Lock Releaseは1985年にIMS Fastpathで既に実装,発表されていたが、
詳細な評価を行ったのはAetherが初出.
世間的には、ELRではなくAsynchronous Commitが実装されることが多い?
Early Lock Releaseの性能
縦軸: 性能向上率.
横軸: データ競合率.
I/Oの遅延が大きければ大きいほど、
ロック保持時間が伸びる.
ロック競合するWorkloadほど差が顕
著で、Slow diskでは35x, Flash
driveでも2xの性能向上.

ELRを適用しても、トランザクションがコミットを返却するまでの間には必ずログを
永続化(flush)しなければならない. ディスクI/Oを避けられるわけではない.
特にGroup Commitなどを用いると、まとめて書き出す分I/O待ち時間が延びる.
この場合条件変数などでwaitすることになるが、このコンテクストスイッチが重い.
これを削減したのがFlush Pipeliningという手法.
ナイーブに実装すると、以下のように、無駄なコンテクストスイッチが発生する.
AetherのFlush Pipelining(1)
…
sleep
sleep
Enq
DeqDeq Flush Notify
sleep
!
!
!
sleep !
Enq
Enq
Commit
Commit
sleep
sleepEnq
Deq Deq
exec next tx
exec next tx

不必要なコンテクストスイッチを減らすために、Flush Pipeliningでは、
各ワーカスレッドがロガースレッドにログに加えてトランザクション情報を送付する.
ロガースレッドは、ログ書き出しが完了したトランザクションに通知を行う.
ワーカスレッドは、通知されたトランザクションをCommitしていく.
(ロガースレッドにCommitの処理をさせるというアプローチもありうる. 下図はそのパターン.)
AetherのFlush Pipelining(2)
Enq
DeqDeq Flush
Enq
Enq
Enq
DeqCommitCommit …
exec next tx..
exec next tx..
exec next tx..
exec next tx..

Flush Pipeliningの性能
Flush Pipeliningを用いることでコンテクストスイッチの回数が大幅に削減される.
論文中では、この手法はストレージの遅延が少ないほど有効で、またメニーコアにな
ればなるほど扱うスレッド数が増えるため効果が高いと主張している.
左図: Shore-MT
右図: Shore-MT+Flush Pipelining
左縦軸: CPU使用率
右縦軸: コンテクストスイッチ数
横軸: スレッド数
縦軸: スループット
横軸: スレッド数
Flush Pipelining + ELRで、Asynchronous Commit(ログをロガーに送付
して即時コミットを返却)と同等のスループットが出ている.
加えて、Asynchronous Commitでは対処できない,
“ログをロガーが書き出す前に障害が発生”したケースでもDurabilityを
守ることができている.

2PLやOCCといった手法は、任意のトランザクションがabortしうる(non-
deterministic)プロトコル.
言い換えると、”CSRやMVSRのスケジュールに違反するread/writeを動的に検出
してabortさせる”手法.
そもそものスケジュール空間が広くなれば、abort回数は減る.
Abortが減る -> 無駄なクロックやリカバリプロセスの削減 -> 性能向上
理論的な最適化手法
最終状態が等価なスケジュール(FSR)
マルチバージョン等価なスケジュール(MVSR)
2PLが作るスケジュール
直列実行

スケジュール空間と性能差の例
T1: Read(x) Write(y) T2: Read(x) Read(z)Read(y)
Read(x) Write(y)History: Read(y) Read(z)Read(x)
Read(x1) Write(x2)History: Read(y1) Read(z1)Read(x1)
[1] H. T. Kung and John T. Robinson. 1981. On optimistic methods for concurrency control. ACM
Trans. Database Syst. 6, 2 (June 1981)

参考: ERMIAとSilo
Kangnyeon Kim, Tianzheng Wang, Ryan Johnson, and Ippokratis Pandis. 2016. ERMIA: Fast
Memory-Optimized Database System for Heterogeneous Workloads. In Proceedings of the 2016
International Conference on Management of Data (SIGMOD '16)
参考: ERMIA(SIGMOD ’16)
ERMIAでは、TPC-Cの5ワークロードに、read-intensiveなQ2というワークロードを追加して実験を
している.
結果,Silo(単一バージョン, S2PL相当)の並行実行制御ではほぼQ2が完走しないことが報告された.
ERMIAは、「実世界のワークロードにはRead-intensiveなLong Txは混ざってくる」と主張している.

並行するトランザクションが書いた値をすぐに読めるようにすると、リカバリにお
いて不都合がある.
以下のスケジュールを考える.
この場合、Serializableであるためには、本来存在しないはずの値であるx1を読ん
だT2はabortされるべきである. が、T2は既にcommitを返した.
T1のabortが確定した時点で、Serializableが達成不可能になっている.
これを回復不可能という.
トランザクションの回復可能性
T1: Write(x) T2: Read(x) Write(y)
AbortHistory: Read(x1) Write(y2)Write(x1) Commit

回復可能なスケジュール空間にも細分類がある.
直列化可能性に関するスケジュール空間とは直交している.
ここでは、「回復可能」と「連鎖的アボートの回避」について説明する.
回復可能性の細分類
回復可能スケジュール(Recoverable)
連鎖的アボートの回避スケジュール(Avoids cascading abort)
厳格スケジュール(Rigorous)

回復可能
AbortHistory: Read(x1) Write(y2)Write(x1)
[2] G. Weikum and G. Vossen. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann
Publishers Inc.,San Francisco, CA, USA, 2001. ISBN 1-55860-508-8.
[3] 北川博之, データベースシステム, オーム社, 2014, ISBN 4274216055

連鎖的アボートの回避
AbortHistory: Read(x1) Write(y2)Write(x1)
[2] G. Weikum and G. Vossen. Transactional information systems: theory, algorithms, and the practice of concurrency control and recovery. Morgan Kaufmann
Publishers Inc.,San Francisco, CA, USA, 2001. ISBN 1-55860-508-8.
[3] 北川博之, データベースシステム, オーム社, 2014, ISBN 4274216055
AbortHistory: Read(x1) Write(y2)Write(x1) Read(x1) Read(x1) ......Read(x1)

「回復可能」スケジュールと「連鎖的アボートの回避」の差は、
“Commitするまで他のTxには値が読めない” という制約の有無のみ.
これは以下のように実装する.
? Commit後にWrite-Lockを手放す
? Commitするまで他のReaderをwaitさせるか、即abortさせる
VLDB ‘17の論文では、この性能特性の違いをマイクロベンチマークしている.
回復可能と連鎖的アボートの回避
Jose M. Faleiro, Daniel J. Abadi, and Joseph M. Hellerstein. 2017. High performance
transactions via early write visibility. Proc. VLDB Endow. 10, 5 (January 2017), 613-624. DOI:
https://doi.org/10.14778/3055540.3055553
横軸: Hot Recordに触るタイミング
Read-modify-writeを10 recordに行
うマイクロベンチマーク.
10’000’000 recordsからランダムに選
択する, low contended workload.
ただし、全てのTxがひとつだけ、同じ
hot recordに触る.
早期にhot recordに触るほど(右),
ロック保持期間が延び、性能が落ちる.

回復可能スケジュールの適用
「連鎖的アボートの回避」を実装すると、全てのロックを同じタイミング(コミット
時)まで手放すことができない.
これを改善し、かつ「連鎖的アボート」の性能ペナルティは最小限にしたい.
そこで”部分的に” 回復可能スケジュールを適用することで性能を向上させる、以下
の手法が提案されている.
? Group Commit [Gawlick et al. DE Bull 1985]
? Early Lock Release [Johnson et al. VLDB 2010]
? Speculative Read/Speculative Ignore [Larson et al. VLDB 2011]
? Piece-Wise Visibility(PWV)[Faleiro et al. VLDB 2017]
前述したGroup Commit/ELRも「回復可能と連鎖的アボートの回避」の観点で説
明できる. というのが面白い.

Group Commitは、「複数のTxをバッファし、まとめてログ書き出しすることに
よってI/O回数を減らす」アプローチ.
Early Lock Releaseは、「ログの書き出しをCommit pointと見なすことによっ
て、早期にロックを解放する」アプローチ.
Group Commit + Early Lock Releaseのシステム(e.g. Silo)では、同じグル
ープ内のトランザクションのコミットは同じI/Oで確定され返却される.
すなわち、グループ内では早期にロックを解放することで「回復可能」スケジュー
ルを適用し、複数グループを全体としては「連鎖的アボートの回避」スケジュール
として扱っている、とみなせる.
Group Commit & Early Lock Release
Enq
Enq
DeqDeq Flush
Enq
Enq
…Deq Deq Flush
Commit
Group
Commit
Group
各Commit Group内では早期にロ
ックを解放している分、連鎖アボ
ートが発生しうる.
Commit Groupをまたいだ連鎖ア
ボートは発生しない.
??????

Hekatonの前身となるMVCC論文では以下の構造体でMVCCを実装している.
HekatonのSpeculative Read(1)
Begin: このレコードを書いたTxのId
End: 次のレコードのTxのId or INFINITY
Name: Key
Amount: Value
Hash ptr: 次のレコードへのポインタ
Per-?ke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M. Patel, and Mike Zwilling. 2011. High-performance concurrency control
mechanisms for main-memory databases. Proc. VLDB Endow. 5, 4 (December 2011), 298-309. DOI=http://dx.doi.org/10.14778/2095686.2095689

HekatonのSpeculative Read(2)
[1] Xiangyao Yu, George Bezerra, Andrew Pavlo, Srinivas Devadas, and Michael Stonebraker. 2014. Staring into the abyss:
an evaluation of concurrency control with one thousand cores. Proc. VLDB Endow. 8, 3 (November 2014), 209-220.
Per-?ke Larson, Spyros Blanas, Cristian Diaconu, Craig Freedman, Jignesh M. Patel, and Mike
Zwilling. 2011. High-performance concurrency control mechanisms for main-memory databases.
Proc. VLDB Endow. 5, 4 (December 2011), 298-309.

Transaction Choppingと静的解析により、”Early Write Visibility”を実現する手
法. 連鎖的アボートのリスクなしに回復可能スケジュールを部分的に適用できている.
Piece-Wise Visibility [Faleiro et al, VLDB 2017]
PWV: 提案手法
RC: (Silo-OCC - Read validation). Read commited相当
Locking: 2PL(MCS-Lock)
OCC: Siloベースの実装
Low-Contention(上図)では、CPUコア数に対して最も
性能が出ているのはSiloだが、同様にスケールしている.
High-Contention(中図)では、Silo-OCCが殆ど通らない
ため性能が落ち込む. 提案手法は変わらずスケールする.
Varying Contention(下図)ではContention Rateを変化
させたときの性能の落ち込み方を計測している.
Contentionが高くなっても、提案手法は高速.

回復可能スケジュールを部分的に適用するに
あたり、各トランザクションのstatements
は全て宣言済み(静的解析可能)であり、決定
的動作をするものと限定される.
(全てのabortが明示的に宣言されている)
これを静的解析することにより、各
statementの依存関係グラフを描く.
このとき,他のstatementに依存されていな
いstatementのwriteは、早期にvisibleに出
来るはず, というアプローチ.
(abortするstatementの後なら、例えば’S’のインクリメン
トは早期にvisibleにしても連鎖アボートせずリカバリ可能.)
このとき、トランザクションのPieceが以下
の条件に反しない限り、早期にVisibleにして
も並列実行してもSerializableである:
1. Abortしうるpieceは全てVisible pointに先行する.
2. AbortしうるPieceとW-R,W-Wの依存があるpieceは、
その実行を待つ.
3. AbortしないPieceは、Visible point以後に実行できる.
4. R-Wの依存は、常に待つ.
Jose M. Faleiro, Daniel J. Abadi, and Joseph M. Hellerstein. 2017. High performance
transactions via early write visibility. Proc. VLDB Endow. 10, 5 (January 2017), 613-624. DOI:
https://doi.org/10.14778/3055540.3055553
Piece-Wise Visibility [Faleiro et al, VLDB 2017]

? 並行実行制御に関して、性能向上手法について紹介した.
? エンジニアリング的手法
? Group Commit
? Early Lock Release
? Flush Pipelining
? 理論的手法
? Early Write Visibilityの概説
? Speculative Read
? Piece-wise Visibility
? 発表の便宜上、区分をしたが、両者に差分がないこともある.
? Group Commit & Early Lock Releaseはどちらとも言える.
? 釈迦に説法だったかもしれませんが、以後お見知りおきを.
まとめ

? Early Lock Release, Flush Pipelining:
? Aether: A Scalable Approarch to Logging [Johnson, et
al. VLDB 2010]
? Hekaton MVCC:
? High Performance Concurrency Control Mechanisms for
Main-Memory Databases [Larson et al. VLDB 2011]
? Piece-wise Visibility(Early Write Visibility):
? High Performance transactions via early write visibility
[Faleiro et al. VLDB 2017]
References

Aetherのアプローチはロガースレッドが単一のキューとして動くことが前提.
これに対して、ロガースレッドを複数持つDistributed Loggingという手法があ
る. ログバッファの競合がボトルネックになることを想定している.
が,Aetherでは, Distributed Loggingは性能が出ないと主張している.
補足: Aether vs Distributed Logging(1)
Distributed Loggingの依存関係のサンプリ
ング. 8のロガースレッド(横線)を用意し並列
書き込みを行っている.
縦の線は物理論理ログの依存関係.
暗い線はR-Wの依存関係.
あるログが他のロガースレッドのログに依存
する場合、適切な順番で永続化しなければな
らない. この待ちが頻繁に発生する.
Workloadから分割して、H-Storeのように
Partitioned Transactionを行うほうが、ロガ
ーのみを分散させるよりも現実的.

Aetherは”Slow I/O & Heavy Dependency Tracking”をもってDistributed
Loggingを諦めていた.
これに対して、VLDB ’14では、NVRAMをLog Bufferに用い、Epoch based
Group Commitを用いることでDistributed Loggingを実現するアプローチが提案
されている[1].
ベンチマークではAetherを大幅に上回っている.
補足: Aether vs Distributed Logging(2)
Write-intensive Workloadでの比較.
横軸: スレッド数(物理24コア)
メインメモリ上にキューを用意するAetherと異
なり、ログバッファとしてNVRAMを用いる.
また、SiloのようなGroup Commitを行うこと
によって、”同一epochの全Txが永続化されたら
Commitを返却”とする.
依存関係解決に使うCPUリソースを削減できる.
Tianzheng Wang and Ryan Johnson. 2014. Scalable logging through emerging non-volatile
memory. Proc. VLDB Endow. 7, 10 (June 2014), 865-876.

狠狠撸

并行実行制御の最适化手法

More Related Content

并行実行制御の最适化手法