狠狠撸

論文紹介: An Empirical Evaluation of
In-Memory Multi-Version Concurrency Control
@nikezono

2Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10, 7 (March 2017), 781-792.
トランザクション:
? 不可分な一連の操作 == n回のread/write操作(0<n)
トランザクション処理の目標:
? Atomicity: n回のread/write操作を1回のレジスタ操作と同様に扱えること
? Consistency: 一貫性を守ること. A,I,Dに加えてDBの制約条件を常に満たすこと
? Isolation: トランザクションが他の並行するTxの影響を受けないこと
? Durability: コミット済みのトランザクションは必ず永続化されていること
トランザクション処理の構成要素:
? ログ管理機構(Log manager)
? 並行実行制御(Concurrency Control)
? データ構造, インデックス(Data Structure)
トランザクションと並行実行制御

MVCC(Multiversion Concurrency Control)
? データベースが複数のバージョンを管理すること
? 論理的なObject(x)が物理的にMVで表現されているということ
? Not-In-place update.
? 対義語は1VCC.
? In-place update.
? 1VCCはアカデミアでは優勢だが、industrialではMVCCだらけ…なぜか?
MVCC 101

MVCC Advantage

直列実行との等価性にはいくつか細分類がある.
「Serializable」という場合，このどれかのクラスに当てはまる処理結果であること(または，そのような
処理結果を生成するアルゴリズムであること)を指す
並行実行制御とスケジュール空間
最終状態が等価なスケジュール(FSR)
マルチバージョン等価なスケジュール(MVSR)
ビュー等価なスケジュール(VSR)
競合等価なスケジュール(CSR)
1V系(2PL/OCC/TO)アルゴリズム
理論的に広くかつ計算量も現実的. MVCCを(まともにやれば)実装できる
直列実行
NP完全(提案なし)
現在有用だと考えられていないclass

There is no standard implementation
? 同じMVCCでも、実装のDesign Decisionによって性能が変わる
? Versionは線形リストで持つか?
? 線形リストはASC/DESCどちらにするか?
? 無限のストレージは無いので，線形リストにはGC(Compaction)が要る.
? いつ/誰がやるか?
? Indexのleafには何を書くか?
? TupleのPhysical Pointerにするか、間接参照するか?
? このようなDesign Decisionは今までアカデミアで議論されてこなかった
? MVCC?はいはい，MVCCね．という感じで，細かい実装の違いは無視されてきた
MVCC Design Choices

Empirical Evaluation for Design Decision
1. Concurrency control
2. Version storage
3. Garbage Collection
4. Index Management
Peloton(https://github.com/cmu-db/peloton)上に実装
? CMU Andy Pavloらが主導するOSS RDBMS
? このリポジトリから論文が多く出ている
? Tile-based Architecture(ICMD’16)
? Self-Driving Database(CIDR’17)
? Relaxed Operator Fusion(VLDB’17)
? Write-Behind Logging(VLDB’16)
学生の授業課題がこのリポジトリへのcontribution.
Contribution

? Evaluationの前に，Tuple Format(線形リストのノード構造体)を紹介する．
? これ以後の全ての実験でこのFormatを用いる．
? Txn-idは書いたトランザクションのid.
? Idはunique and monotonically increasing.
? begin-tsとend-tsはuint64_t.
? Begin-ts < 自分のTS < end_ts なら読める,という風に使う
? これをCASすることでロックに使う
? 例:
1. begin-tsをINFにして自分のwriteを反映させた新しいversion tupleを作る.
2. リスト末尾のTupleのend-tsを0にCASする(と，誰も読めなくなるので，lockに等しい)
3. pointerを自分が作ったタプルにつなぐ
4. End-tsを自分のTidにする(unlockに等しい)
Tuple Format

MVTO(Multiversion Timestamp Ordering)
? 商用ＤＢに実装無し
? 通称Tx本(weikum)/CC本(bernstein)という本では紹介されている
? まずTimestampをallocateし、それに従ってRead/Write
? 例:自分がT2だとする
? Ti(i<2)のwriteを読む
? Tj(2<j)が既にreadしている場合は自分のwriteが遅すぎた。アボート
? MVSRになる(うまく実装すれば)
? MVSRにしようとすると，線形リストが V1 -> V5 -> V3…と順不同になるので，実装するのにやや工夫がいる
? そのへんの理由で実装が無いのだと思われる(私の主観)
Concurrency Control: MVTO
T1
T2
TS Alloc
TS Alloc
Write(x1)Read(x0)
Linearization Point
Write(y2)
Linearization Point
Read(y0) Read(x1)
Commit
Commit

Concurrency Control: MVOCC
T1
T2
TS Alloc
TS Alloc
Write(x1)Read(x0)
Linearization Point
Write(y2)Read(x0)
Validation(x) Commit
Validation(x) Abort

?MV2PL(Multiversion Two Phase Locking)
? よく知られている2PLをMVCCに拡張したもの
? read the most recent version(∈uncommitted)
? write after all concurrent writer has committed
? commit after all concurrent reader/writer has committed
? readがblockしないだけで、事実上ほぼ2PL?
? 1Vで使っていた2PLのアルゴリズムをそのままMVに引っ張ってきただけに読める
Concurrency Control: MV2PL
T1
T2
TS Alloc
TS Alloc
Write(x1)Read(x0)
Read(x1)
Commit
Commit
rlock
commit wait

Comparison(SSI,SSNは省略…)

YCSB Benchmark: ReadOnly

YCSB Benchmark: ReadWrite Mixed

YCSB Benchmark: Contention

Oldest-to-Newest(O2N)
? 線形リストの末尾にデータを追加していく
? ReadでもWriteでも，たいていの場合リスト末尾までのVersion traverseが必要になる
? GCが遅れるとリストが伸びて不要なランダムI/Oが……
Newest-to-Oldest(N2)
? 線形リストの先頭(HEAD)にデータを追加していく
? O(1)で(latest)read/writeできる
? HEADを更新する == インデックスも更新する
? Secondary indexがある場合，その更新も同時，というかatomicである必要がある
? 間接参照を挟めばatomicに出来るが、これは不要なランダムアクセスか?
Version Storage: Append-only

Time-travel
? SAP HANAの実装.
? Main TableにはLatest Versionのみ置く.
? 古いVersionはTime-travel Storageという別の領域に置く．この領域はN2O
? Write時に毎回Main to Timetravelのcopyが発生する
? 歴史的経緯で複数のストレージが合体して生まれたSAP HANAならではのデザインか?
Delta
? MySQL and Oracle uses this
? タプルの全内容ではなく更新の差分をN2Oでリストにする
? Partial updateに強い．リストの各ノードにコピーするデータ量が大幅に減る
? ただしSELECT * FROM…とかされると，リストを辿ってレコードの欠片を拾い集めないといけないので辛い
Version Storage: Timetravel & Delta

YCSB Benchmark: Footprint

YCSB Benchmark: Memory Allocation
Memory spaces: mallocできるareaの数.(多分)
Deltaはfootprintが?さくなるのであまり影響を受けない.

YCSB Benchmark: Contention

Garbage Collection: Tuple-Level
? 前提: RCU-based memory reclamation(QSBR)
? 各TxnにはTxn-idがある．これは単調増加する
? m = min({Tid | all runnning transactions}) を計算する
? end_ts < m のタプルはもう誰も読めるものが居ない．
? すなわちGCできる

? Background Vacuuming(VACUUM)
? PostgreSQL,Oracle, MySQL
? ワーカスレッドとは別にGC専用スレッドを立て，定期的に各テーブル/レコードをGCしていく

? Cooperative Cleaning(COOP)
? Microsoft SQL Server(Hekaton)
? トランザクションを実行するワーカスレッドがGCする
? 開始時にmを計算して，m以下のノードをGCしながら走っていく
? 古いデータを見つけ次第即時GCされていくので，無駄なリストのtraverseを最小化できる
? が，誰にも読まれず書き込みだけが連続する場合，リストが伸び続ける問題がある

Garbage Collection: Transaction-Level

YCSB Benchmark: Tuple-Level

YCSB Benchmark: Tuple vs Transaction

?Logical Pointer
? 間接参照を用いて，各Indexは間接参照を指すようにする
? セカンダリインデックスがあるN2Oでも，Atomicに更新できる
? 間接参照先を何にするかで流派がある
? Primary Key: セカンダリインデックスに触った場合，Primary Indexを再Traverseさせることになる
? Tuple ID: 線形リストのheadに直接つなぐ．
?Physical Pointer
? Indexに(B-treeならLeafに)Version Chainをそのまま置く
? セカンダリインデックスをアトミックに更新したいならLockする
Index Management

YCSB Benchmark: Tuple-Level

これまで「MVCC」と言われてきたDBMSを同じワークロードで評価．
これだけ性能が変わる理由はこれまで述べてきたDesign Decisionで説明できる……
(と論文では言っている)
おまけ: Configuration Comparison

? https://twitter.com/andy_pavlo/status/902863242774634496
? 論文タイトルで三回rejectされている
? タイトルが全部強気で面白い
余談

狠狠撸

論文紹介: An empirical evaluation of in-memory multi-version concurrency control

More Related Content

論文紹介: An empirical evaluation of in-memory multi-version concurrency control