ぱと隊長日誌

ブログ運用もエンジニアとしての生き方も模索中

DBTS2017「次世代DB / 分散OLTP(MVCC系)を可能な限り全力で解説」聴講メモ

前書き

db tech showcase Tokyo 2017 (db tech showcase Tokyo 2017 | db tech showcase)
C31:次世代分散OLTP
次世代DB / 分散OLTP(MVCC系)を可能な限り全力で解説
の聴講メモです。

スピーカーはノーチラステクノロジーズの神林さん(@)です。

原則として自分のメモをベースに、Twitterのつぶやきを参考にしながら見直しを行いました。メモしきれなかった内容がTwitterに記録されている場合もありましたので、併せてご参照ください。
#dbts2017 since:2017-09-07 until:2017-09-08 - Twitter Search
9:18~10:27あたり。並行したセッションがあるため、つぶやきは混在しています。

メモは口頭説明を中心にまとめています。私の理解不足でメモの内容に間違いが混入しないよう確認を行いましたが、おかしな箇所がありましたらご指摘ください。

今回の発表を理解するためには、トランザクション技術をある程度理解している必要があります。@さんがとてもわかりやすい記事を公開されていますので、ご参照ください。
一人トランザクション技術 Advent Calendar 2016 - Qiita

【参考】としている個所は私が挿入しています(補足や参考資料など)。登壇者の講演内容ではありませんので、その旨ご了承ください。

聴講メモ

講演資料(スライド)

背景:ムーアの法則の終焉とメニーコア化の進展

CPUは6コアがデフォルトになっている。今後、CPUソケット数も増えるだろう。100コア搭載のマシンも見えてきている。

背景:メモリーバイスの進化

メモリが安くなった。
インメモリデータベースが特別ではなくなった。データがメモリに全部乗る。

メモリデバイスの進化でデータベースのアーキテクチャが大きく変わる。WriteBehindLogging(WBL)。リカバリータイムが従来の1000倍ぐらい変わる。後で解説する。

背景:OLAPとOLTPの統合

OLAPとOLTPの統合では、データを持ってくることはできるが、戻すときにインデックスの更新がきつい。

DBの現状課題

従来のDBではメニーコアの対応ができていない。

メモリの取り扱いが多層的になる。CPUのコアレベルでまず違うし、CPUソケットのまたぎでも速度が違う。

NUMAでのデータのConsistencyの管理について論文は出ているが、結論としては最適解が出ていない。何がよいかは測定するしかない。ただ明確になっているのはハードではダメということ。

ARIESはログをだらだらと書いて、だめならそれを元に戻す。ARIESは実装が難しい。
不揮発性メモリーによって、このリカバリ処理が劇的に簡単になる。後で(WriteBehindLogging)解説する。

【参考】
ARIESについての@さんの解説です。
ARIES - Qiita

大規模OLTP

大規模OLTPの開発競争で一番進んでいるのはOracleで、SAP、MSと続いていると思う。

OSSは関係者が多すぎて進歩のスピードが遅い。

今年(2017年)の春先に Multi version が Single version の性能を抜いた。

RDBMSアーキテクチャの制約により、スケールアウトもスケールアップもできない。

1ノードで Billion TPS のような大きいトランザクションだと、GCが問題になる。トランザクションがabortすると、ゴミが大量に発生することになる。

SQL Server はエンジンにHekatonを採用している。

【参考】
ここでのGCとは、例えばJVMが行っているメモリ上の不要なオブジェクトに対するGCではなく、データベースが不要なデータを対象に行うGCを指しています。
データベースのGCについて適当な資料を見つけることができませんでしたが、例えばPostgreSQLのVACUUMコマンドの説明に"garbage-collect"との表現が出てくることから、その意図するところが想像できるのではないかと思います。

VACUUM -- garbage-collect and optionally analyze a database

PostgreSQL: Documentation: 9.6: VACUUM

【参考】
神林さんのブログでHekatonについての解説記事です。
セッションでお話しされていて、この聴講メモでは含めきれなかった内容も解説記事には書かれています。ぜひご一読ください。
SQLServer 2014 “Hekaton”再考 - 急がば回れ、選ぶなら近道

【参考】
神林さんのブログでSILOについての解説記事です。
SILO再考〜次世代DBのアーキテクチャとして - 急がば回れ、選ぶなら近道

OCC vs MVCC

OCC (Optimistic Concurrency Control)

OCCは楽観(optimistic)。
トランザクションの競合が性能のネックとなる。
これまでのノウハウがある分、今のところ早い。

MVCC (Multi-Version Concurrency Control)

タイムスタンプで管理する。OCCに比べて理論が難しい。

SSN (Serial Safty Net)

中国の方が考えた方式。これから台頭するかも。

【参考】
OCC/MVCCについての@さんの解説です。
Optimistic Concurrency Controlについて - Qiita
Multiversion Concurrency Control(MVCC) その1 - Qiita

【参考】
SSNの発案者の方の名前をメモできませんでしたが、
The Serial Safety Net
おそらくこの論文の Tianzheng Wang と思われます。

OCC

OCCはread-lockをとらない。更新の競合がないことを前提としている。Validation Phase で Consistency Check を行い、serializableでなければabortする。

Serialization空間(理論)

Serializableの種類はIsolationの種類よりもたくさんある。

OCCはCSRだ。

Serializableの枠の外にあるものはabortと判断する。つまり、このSerializable空間の枠を広げることができれば、abortを減らすことができる。

【参考】
神林さんのブログでの解説記事です。
Multi-version Conflict Serializability - 急がば回れ、選ぶなら近道
multi-versionの基礎 - 急がば回れ、選ぶなら近道

そんなにserializationは大事か?

移植を例に挙げる。
スライドの例で、患者Aと患者Bのどちらが選ばれてもserializableといえる。どちらが優先されるかは実装に依存する。例えば、2PLなら患者Aが選ばれる。これをアプリがコントロールするにはロックを取得するしかない。
この例を見てもわかるように、データベースエンジンを変えるだけで挙動が変わってしまうかもしれない。

【参考】
2PL(Two Phase Lock, 2相ロック)についての@さんの解説です。
Two Phase Lock - Qiita

OCCの弱点

MVCCなら追記だけなので、abortしたときの対応が楽だ。

abortしなけばOCCが速い。MV (Multi-Version) は勝てない。

Multi-Versionはversionのおかげでreadもwriteもlockが必要ない。

MVCC

分散処理は時間同期をとれない前提で設計する。これは処理効率が悪い。

時間同期をとれない例としては、ある国がビットコインで分断と再開をしたと仮定したケースが挙げられる。

【参考】
ビットコインの例は、以前に神林さんが自身のブログで挙げていた例を念頭に置いたものと思われます。
ビットコインとブロックチェーンと分散合意 - 急がば回れ、選ぶなら近道

MVCC(Cicada)の圧倒的なパフォーマンス

TPC-Cのスループットのグラフを見ての通り、Cicada(赤のグラフ)が圧倒的なパフォーマンスを出している。

TPC-Cのグラフはトランザクションの最も厳しいケースでの測定結果だが、もっと軽いYCSBでもパフォーマンスが出ている。

【参考】
グラフは以下の論文から引用しています。スライドでは見辛いと思いますので、こちらを参照ください。
https://www.cs.cmu.edu/~hl/papers/cicada-sigmod2017.pdf
なお、神林さんのブログでは、この論文についてのまとめを行っています。
Cicada:Dependably Fast Multi-Core In-Memory Transactions - 急がば回れ、選ぶなら近道

MVCCのserialization空間というか MVTOについて

MVTO (multiversion time ordering) でserialization空間はCSRより広くなる。パフォーマンスもでる。
実装も理屈も簡単。「readするときは必ず最新のversionを読んでいる」ということ「だけ」が保証されていればよい。でも、理論は難しい。証明が大変。

【参考】
神林さんのブログでのMVTOの解説。serializabilityの証明もまとめています。
MVTO (multi-version timestamp ordering) - 急がば回れ、選ぶなら近道

Cicada

※関連スライドの話をまとめてメモしています

Cicadaの全体処理はパフォーマンスのためによく考えられている。

論文はあるのに実装が出ていないところから見て、今後製品化するつもりではないか?

writeとreadのそれぞれでタイムスタンプを管理している。

One-sided synchronization で早いやつにあわせる。これによりバリアが不要となり、ロックフリーとなる。

Validation phase の上2つのブロック (Sort write set by contention, Pre-check version consistency) は早くするための仕組みで、validationの本体は下3つのブロック (Install pending versions, Update read timestamp, Check version consistency) となる。

WBL (WriteBehindLogging)

※関連スライドの話をまとめてメモしています

WBL (WriteBehindLogging) は Durable Storage に対し、Table Heap を書き込んでから Log を書き込む。

WBLは Volatile Storage が NVM (Non-volatile memory、不揮発性メモリ) という前提がある。キャッシュを横取りして Durable Storage の Table Heap に書き込む。Logにはコミットのタイミングで書き込む。

Logの対比の例において、WBLは右側に示すタイミング及びデータのみデータを書き込む。

WALとパフォーマンス(レイテンシースループット)を比較すると、WBLでもログを書いている以上、それほど改善しない。
でも、リカバリータイムは1,000倍以上速い。リカバリーはコミットログからどこまで戻せばよいかを判断するだけでよいからだ。これに対し、WALの場合はREDOも処理せねばならず、処理がややこしくなる。

【参考】
Write-Behind Logging の論文は以下にあるようです。
http://www.vldb.org/pvldb/vol10/p337-arulraj.pdf

【参考】
WBLはリカバリーでロールバックのみすればよい(REDOフェーズ不要)ことについて、論文では以下の説明をしています。

In a single-versioned DBMS with WBL, the system makes a copy of a tuple's before-image prior to updating it and propagating the new version to the database. This is necessary to support transaction rollbacks and to avoid torn writes. The DBMS stores the before-images in the table heap on durable storage. The DBMS's recovery process then only consists of an analysis phase; a redo phase is not needed because the modifications for all committed transactions are already present in the database. The DBMS, however, must roll back the changes made by uncommitted transactions using the before-images. As this undo process is done on demand, the DBMS starts handling transactions immediately after the analysis phase. Similar to the multi-versioned case, the DBMS uses the commit timestamps to determine the visibility of tuples and identify the effects of uncommitted transactions.

http://www.vldb.org/pvldb/vol10/p337-arulraj.pdf

参考

今回、まとめる際に参考にした資料のリンクです。

リレーショナルデータベースの仕組み (3/3) | コンピュータサイエンス | POSTD
リレーショナルデータベースのSQLクエリの処理について、基本の概念を解説しています。リンク先のページ(3/3)では今回のスライドで取り上げられている2フェーズロック(2PL)やARIESに関する説明もあります。ただし、テーマが幅広い分、個々の解説は浅めです。

@さんによる発表資料です。冒頭のQitta記事に全て目を通してから読むと理解しやすいです。

更新情報

2017/09/23

  • Hekatonの解説記事へのリンクを追加しました。