SILO再考〜次世代DBのアーキテクチャとして

大分たってしまったけど、ようやく時間が空いたので、db tech showcase Tokyo 2016 http://enterprisezine.jp/dbonline/detail/8466 で話した内容を記録的に書いておく。あとはSILOの解説を特に自分用に論文の4章を中心に整理しておく。あとはついでに自分の思うところも記す。

SILO
元論文はこちら、執筆陣はMITのLiskov一派とEddie Kohler 現在のDB研究の第一線のメンバー。
http://people.csail.mit.edu/stephentu/papers/silo.pdf

SILO以降、大きくDBベースのアーキテクチャの考え方は変わりました。ほとんど全ての分散系OLTPはSILOを程度の大小はあるとはいえ、意識していると言っても過言ではないでしょう。前世代ではほぼ「空想か?」ぐらいの扱いだった分散transactionはほぼ現実のソリューションになっています。個人的には、ここ数年の既存RDBMSとNoSQL系のどっちが上か論争にほぼ決着がついたと思っています。というよりも論争自体が無効になったのが現在でしょう。今後10年で既存DBのアーキテクチャはほぼ全てSILOの「考え方」を採用したアーキテクチャに席巻されると思います。それは現在のRDBMSの延長でもないし、NoSQLに青息吐息でACIDを後付けで放り込んだNewSQLでもありません。

商用のメジャーなDB,例えば、Oracle SAP(HANA) SQLServer と言ったDBも大きくそのアーキテクチャ変えると思いますというか、現実にその辺を大きく変更する趣旨の論文が多数出そろいつつあるので、もう既定路線でしょう。SAPあたりについては、(DB屋から見ると)ほぼそこまで言うかレベルでの声明まで出しています。また、既存OSS系のRDBMSもNOSQL系も、流れとしてはSILO的な考え方に追随しなければ、パフォーマンスで文字通り圧倒的に遅れをとるし、そもそもメンテナビリティでも差がつきます。対応は不可避でしょう。

DBの製品群でも、入れ替わりが起きるでしょう。どのDBにとっても、ほぼアーキテクチャの完全な変更になるので、資金のないOSS系は対応できずに、むしろ新しくスクラッチで作られたOSSの分散OLTPにその座を明け渡すでしょう。既存プロプラ系DBはもうこれはどれだけ優秀な人材と金を突っ込めるかの勝負になります。

なぜか。非常に理由は簡単です。

理論的にSILO系の「やり方」は、今後のハードウェアのアーキテクチャの進化の流れと軌を同一にしており、そのパフォーマンスを最大限に引き出すことができるからです。言うまでもなく、ソフトウェアとハードウェアは車輪の両輪です。片方が釣り合わない場合は、前には進まず、そのまま同じ場所をぐるぐる回りつづけます。

コンピュータ業界における今世紀の最大のトピックは、クラウドでもAIでもIoTでもありません。ムーアの法則が限界に、それこそ物理限界につき当たったことであり、その代替手段の「発見」が文字通り時間切れになったことです。

結果として、コア出力は上がらないため、メニーコア化に拍車がかかっています。ごく普通に1サーバあたりの物理コア数が100近いマシーンが、秋葉原で簡単に買える時代に入りつつあります。HTであれば普通に200threadで、5台もスタックすれば、1000threadでの同時処理が可能です。これに加えてメモリーの高密度化が進んでいます。普通に数Tのメモリーも手に入る時代になりつつあります。メニーコア化とメモリーの大容量化は、当然ながらバスの高速化を要求します。コア間・メモリー・disk・NWのほぼ全てのバスで高速化が進みつつ有ります。

今までのコア数は4コアや2コアが標準でしたが、一気に桁があがります、サーバ単位で見たときには、場合によっては2桁変わる。一般にITは「桁が変われば、アーキテクチャを根本的に見直した方がよい」といわれますが、SILOはその典型でしょう。OracleでもSQLserverでもMySQLでもPostgresでもDB2なんでもいいのですが,今までの既存のDBでは、100コアどころか20コア行かないぐらいでパフォーマンスが、特にwriteの競合がある場合は飽和します。これは、既存のDBの作りがまずい、ということではなく、単純に環境の前提がそもそも違うからです。大量の分散並列処理+大容量のメモリーは前提にしてないどころか、そもそも想定外です。

くまぎー先輩(そういうば最近無駄にロックフリーって言わなくなりましたな。)のスライドがよく出ていると思うので張っておきます。
http://www.slideshare.net/kumagi/ss-64459138

要するに今までのDBは「コア数は少なめで、というか基本一つで、メモリーは高価でサイズが小さく、できるだけ効率的に使いましょう」という、ハードウェアに対するスタンスが前提になっています。(なので、例えばundo logもdiskに書くという結果になりますね。この一点をとってしてもSILOの方がパフォーマンスもメンテも全然優れていると思います。)

SILO以降の分散DBは、理論的な裏付けとして、今までのRDBMの良質な蓄積を完全に養分としており、別に奇をてらった戦術を駆使しているわけではありません。今までの理論を踏襲すれば、「そりゃそうだわね」という感じで腑に落ちる考え方です。仮に、DBに「進化」という表現を当てはめるのであれば、まさに「環境変化に対する適者生存」という言い方がフィットすると思います。

ということで Section 4 の design から説明しますよ的な。

前書きはともかくここで分かっておけば、なんとかなる(とはいえ、いろいろ論文を通すために端折った部分が有り過ぎなので、その辺は実装みるなり、他の論文(例 Masstreeの詳細)を読んでください的なアレになっている。なんかたくさん書きすぎると査読が通りにくいそうで。大丈夫かアカデミア。)はず。たぶん。

SS4は以下の順序
4.1 Epoch
4.2 Transaction IDs
4.3 Data layout
4.4 Commit protocol
4.5 Database operations
4.6 Range queries and phantoms
4.7 Secondary indexes
4.8 Garbage collection
4.9 Snapshot transactions
4.10 Durability

SS4の前にSILOの前提を書いておく
1.型付きの命名されたレコードを管理。
要するにちゃんとしたDB。

2.one-shot requests
処理のwindowがあるということを意味する。すなわち、clientまで「常に状態を返し続ける」ということではない。serialization pointが存在できる可能性の一つの前提を提供している(overlapが永遠に続くわけではない)

3.MassTreeを利用
PKのindex treeで基本はB+。ただし、secondary keyは別treeになっている。したがって、secondary keyを利用する場合はtree traverseが二回になる。
「Each Masstree leaf contains information about a range of keys, but for keys in that range, the leaf may point either directly to a record or to a lower-level tree where the search can be continued. 」

4.requestの処理は各コアが担当
indexは共有メモリーを利用。

以下、解説的なメモ

4.1 Epoch
ほぼ動作単位のすべての基本になる。
・Global Epoch
全体の進行統括するepoch。Global Epoch Number(E)が設定される。管理threadがある。一種のバリアと機能する。SILOでは単位は40msec。

・各worker threadがlocal epoch(ew)をもっている
基本的にEを取得してセットするので、当然、Global Eよりは遅れる(ことがある)。GCのタイミングの判断として利用している。invariant: E-ew<=1であり、すなわちepochで1単位以上遅れることはない。ローカルが進まないとEが進まない。なので、なのでロングtxの処理中はewをリフレッシュする必要がある。一種のグループコミットの「単位」として機能させる。コミットプロトコルのところで再解説する。

4.2 Transaction IDs
tx-IDはとにかくいろいろkeyになる。version check, lock制御, conflict検知とか。基本的にユニーク保証が必須なので、発行がボトルネックになる。のでいろいろ工夫する。

・分散処理でのtx-IDの割り当て
各workerでtxのcommit可能確定「後」に
 a.発行されたtx-IDよりも大きな値
 b.自身が選択したtx-IDよりも大きな値
 c.単一GlobalEpoch内部に閉じていること
以上の条件を満たすIDが選択される。

tx-IDの発行は単調増加「だけ」でよい。(分散処理可能)。たとえばr-wの検出だけなら、t1:read(x)→t2:write(x)のanti-dependencyの場合、t1<t2 t2<t1 の両方のID順序が発生する。なので、別にserial orderとtx-IDのorderが常に一致する必要はない。ただしepochまたぎは順序保証(serial orderと一致する必要がある)(尚、普通にt1:write(x)→t2:read(x)でserial orderが t1→t2ならTx-IDも t1→t2が必要)が必須。

4.3 Data layout
・以下の三つから構成されている
抽象化されたtxの各レコードは以下通り
TID : Transaction ID
Previous-version pointer : snapshot transactionで利用(後述)
Record data : 本体

本体については割と普通だと思う。普通にtupleを格納するpageモデルで、普通にin-placeなんで、RDBと同じスタイル

4.4 Commit protocol
外観:
Data: read set R, write set W, node set N, global epoch number E

// Phase 1
for record, new-value in sorted(W) do
lock(record);
compiler-fence();
e ←E; // serialization point
compiler-fence();

// Phase 2
for record, read-tid in R do
if record.tid != read-tid or not record.latest
or (record.locked and record !∈W)
then abort();
for node, version in N do
if node.version != version then abort();

commit-tid ← generate-tid(R,W,e);

// Phase 3
for record, new-value in W do
write(record, new-value, commit-tid);
unlock(record);

・個人的な解説:
4 phase approachで、これはほぼ業界デファクトっぽい。論文はcommitだけなら3 phaseに見えるが、実際はglobal epochでのphaseがあるので、4 phaseと見た方がよいと思う。今のところコレ以外のアプローチは、この手法のバリエーションしかない(気がする)。以下、順番に解説

Phase 1
[Write lock]
for record, new-value in sorted(W) do
lock(record);
compiler-fence();
e ←E; // serialization point
compiler-fence()

write setのロック処理
基本的にserializationは、2PL方式で処理する。ただしreadロックは取らず、2PLのread lockに相当する処理はversion checkで代替する。read lockを取らないので、OCCになりreadはブロックしない。fencingしてちゃんと同期する(epochの取得)。one-shot requestなので、epoch確定処理でserialization pointを決定する。同じくfencingしてちゃんと同期する・・論文では二回やってるがなんかこの辺fencingは一発でいんじゃないか?説あり

Phase 2
[Validation]
validationはread setのロック処理と同等の処理を行う。
for record, read-tid in R do
if record.tid != read-tid or not record.latest or (record.locked and record !∈W)
then abort();
自分の持っているread setのtx-IDが既に最新ではない(どこかで更新が入っている)か、または、そもそも自分のwrite setにはかぶっていないけどロックが取られている場合(他でロック)は abort。

for node, version in N do
if node.version != version
then abort();
treeのノードからphantomのチェックを行う(後述)

commit-tid ← generate-tid(R,W, e);
コミット用のTx-IDの発行

Phase 3
[Pre-commit]
for record, new-value inW do
write(record, new-value, commit-tid);
writeの書き出し

unlock(record);
lockのリリース。phase4が存在するので、いわゆるearly lock release。この辺がいろいろスタイルが存在する。最終的にcommitの永続化や、H/Wの想定性能も考慮して決まっているように見える。

Phase 4
[Durable commit]
■明示的には論文には書いていないが、・・・PersistentのPhase Durableのセクションより

・When a worker commits a transaction, it creates a log record consisting of the transaction’s TID and the table/ key/value information for all modified records.
とりあえずcommit時の全部ログは持つ

・This log record is stored in a local memory buffer in disk format.
ただし、それはメモリー上(なんで消える可能性あり)

・When the buffer fills or a new epoch begins, the worker publishes its buffer to its corresponding logger using a per-worker queue,
bufferがヤバイか、epochを進めるときに書き出す

・and then publishes its last committed TID by writing to a global variable ctidw.
んで、自分の担当分の最終commit tx-IDを発行(ここで完了)

■基本的にepochベースのグループcommit(に近い)
one-shot requestが前提。validationでcommit可能であっても(というかcommitなんだけど)durable(すなわちlogが終了するまでは)になるまではclientにはcommitは返さない、加えて、loggingが終わるまではsnapshotのinstallは行われない。なので、実際はcommitableなんだけど、読ませないので、SIとしてはちょっとだけstaleになる可能性がある。というか、これgroup commit系には必ず発生する問題にはなると思う。
client(というかapplication)的には、そもそもcommitが見えてないので、group commitでこけた場合は、handlerとしてはabortとして処理できる。この時、残っているのはredo logなので復旧が超っぱや。これはすごく重要。尚、個人的にはこれは事実上のstaleとのtrade-offになっていると思う。・・逆に言うとこれは、アプリサイドにはあんまり選択の余地はない。
あとは、結果、基本snapshotについてはreplicaになるので、どーやってlog shipするかは結構マニアな課題になると思う。

■このcommit protocolはserializableなのか?
普通に2PL。
We verify in Phase 2 that the record’s TID has not changed since its original access,and that the record is not locked by any other transaction.This means that S2PL would have been able to obtain a read lock on that record and hold it up to the commit point.
よって、普通にS2PL(と理論的に同等)

■分散処理だが、barrierはどうするのか?
epochで処理するという理解でいいと思う。phase1でepochの状態をfensingする

4.5 Database operations
Read/Write
省略〜前述のcommit protocolでほぼ説明可能

Delete
Snapshot txでtreeをたどるときに必要なので、論理削除は可能だが、物理削除はできない。absentフラグを設定する。ただしGCの当然、問題になる。

Insert
commit protocolの「前に」先にinsert処理をしておく(treeに追加)。その直後のcommit protocol のread setとwrite setに加える。この辺が特にphantomの除去について妙技になっている。(後述)

4.6 Range queries and phantoms
Siloではrange queryもサポートしている。ということで当然phantomもクリアしている。基本的にはNext-key lockingで対応しており、割と古典的な手法を使っている。最初になかったヤツが現れる場合は、確かにNext-key lockingは割と行ける。が。最初に有ったヤツが消える場合、すなわち、readでヒットしているケースだが、ここでlockはreadロックになるので無理・・・なのでNext-key lockingはそのままではまずいわけですね。SILOでは、treeのnode自体にversionを持たせて対処する。read setに対応する node setを持たせる。これでversionを確認するわけよ。

これはinsertでの structural modificationにも対応できる。insertはcommitの前に行われる・・ので、node setにcommit protocolに加える処理をする。すなわち、node setのversionが更新して、abortさせる(phantom)

■Node-setでの制御
「これは割とイマイチな気がするのは多分俺だけじゃない」ということでいろいろ議論になっている気がする。treeの制御がやっぱり面倒な感じがするので、パフォーマンスが結構アレな感じになる(と思う)。特にDelete系は鬼門に見える。

結構、tree制御とcommit protocolが割と密接に絡んでいるのは、ひとつの特徴とも言える。個人的にはあんまり美しくないと思うけど・・・とはいえ、現実解としては優秀とは言える

4.7 Secondary indexes
普通に対応している。省略
まぁ実装は面倒だと思う。論文はあんまりまじめに書いてないけど、実際は結構大変だと思われる。「Secondary key は別treeになっている。したがって、それを利用する場合はtree traverseが二回になる」(再掲)この辺はもういいのではないでしょうか的な展開になっている。まじめに書いてない。(多分書けるけど書くと査読がうるさいという理由だと思われる)

4.8 Garbage collection
発生するgarbageは以下。
・tree node(B+)
・record
GCについては、RCUで、epochベースでのreclamation スキームを導入している。参照カウントだと全writeが共有メモリーにアクセスして厳しいので使わない

たとえば・・・
削除(別にrecordでnodeでもよい)実行する場合
・対象とreclamation epochをコア毎に登録
・reclamation epochを経過したらごっそり消す
例としては、各ローカルのepoch numberで考える。epochの進み方から e<=min ew-1なるeをtree reclamation epochと想定してGCする。

4.9 Snapshot transactions
Read-only snapshot transactionを想定。
とりあえずconsistent snapshotを取る必要があって、この時の考慮点はconsistencyとreclamationになる。(consistent snapshotはいわゆる分散環境下のconsistencyのこと)両者に対してはSnapshot Epochというものを考える。要するboundaryをepochで管理する。そもそもepochがserial orderの管理なので、これは正しい。あとはalignの方法の問題。snap(e) = k・floor(e/k)で、k=25 で eのインターバルが40mなんで snapshotは1sec

まず、Global Snapshot Epochを導入(SE) SE←snap(E-k)んで各ローカルのsewを設定sew←SE 最新のsnapshotのversionは epoch <= sew

read/write処理では基本的に直接versionは触らない。ただし、phase3で snap(epoch(r.tid)) = snap(E)ならば、そのまま上書き。そうでなければ新しいverisonをinstallして、前のものへのポインタをprevious-versionにセット。このあたりを見ても4phaseアプローチに見える

reclamationについてはSnapshot reclamation epoch(min sew-1)が進めば破棄できる。このときは別にprevious-versionは気にしなくてもよい。dangling pointerは参照されない(epochが進んでいる)から。

Deleteは簡単ではない。absentのフラグが立っている状態で管理。Snapshot reclamation epochで「消してもいいよ状態にまずセット」次にtree reclamation epochで処理する。むーん。

4.10 Durability
recoveryの単位の問題になる。epochベース(durable epoch D)で処理をする。serial orderを維持。いろいろ書いてあるけど、要するにLSNの管理の代わりにepoch使うということ。・・・だから4 phaseぢゃないですか・・・あとは読めばわかるので省略

総括

・MVCCが基本になる
Snapshot Isolationが基本になるけど、SSIではなくてS2PLで処理。その上でそもそもsnapshotをどう作るのか?というところも解決している。

・Epochベース
barrierの一つで同期処理のラウンドに似ている。時差(ローカルとグローバル)を入れるのは良いアイデアに見える。割といろんなところでepochを利用する。

・RDBMよろしくtree構造でいろいろ
実装ベースのノウハウはうまく使うのはあり。B+というかMassTreeが基本。要勉強。

・PreCommitのコンセプト
返答してなければ「なかったこと」にできる。結果、リカバリーが劇的に楽+速い。パフォーマンスに大きな影響があって、今後の分散DBの肝になる。どの単位で書き込むかも含めて、実際はハードウェアにも依存すると思う。NVM:高速→reclamationが重要 / SSD:低速→あんまりreclamationは考えなくてもよいかも

・感想
DB屋的には、アーキテクチャを理解する必要があると思う。運用、特に対障害設計を考えるときに諸処わからないと厳しい。実際にこの手のモノが出てきたら、チューニングが大変になると思う。

アプリケーション屋的には、「できること」と「できないこと」をどう理解するか?がポイントになる。トランザクション・セマンティクスの理解は必須だと思うし、最低でも少なくともログの話は抑えないと厳しい。

その他関連する情報
FaRM:
MS:マルチノードでの本気の分散OLTP
アプローチはSILOに近いが、かなり違う。
https://www.usenix.org/system/files/conference/nsdi14/nsdi14-paper-dragojevic.pdf

Foedus
HP Labの木村さん
SILOの進化版(って言ったら怒られる気がするけど、本人もSILOぐらい知っとけ的な感じなのでいいかなと)
http://www.hpl.hp.com/techreports/2015/HPL-2015-37.pdf

ERMIA
Sigmod2016
http://www.cs.toronto.edu/~tzwang/ermia.pdf
SSIからの挑戦→SILO的なものと融合?(まだまじめに読んでない)

MOCC
ERMIA遅いよね的な反撃
http://www.labs.hpe.com/techreports/2016/HPE-2016-58.pdf

以上すべて、SILO的な展開のうえでの発展

大体以上がまとめ、んで、その上で、ですが・・・・

そうそう単純にSILOクラスのDBが商用に出てくるということではありません。DBが「使い物になる」というのは、過去の実績からみても5年単位の時間がかかります。さらに、特に日本企業のように、新しい技術の採用に比較的慎重な風土病があるところでは、新しいアーキテクチャのDBの採用は時間がさらにかかります。内製化が企業の急務とはいえ実態のSI依存体質が強いのであればなおさらでしょう。

経験的には、ここでのSILO的なDBが実際の企業の基幹バックエンドに使われるのは2030年以降だと個人的に思う一方で、(欧米では5年待たずに導入されるとは思いますが。)Oracle・MS・SAPもこちらのアーキテクチャに変更してくるのは必然なのでOracle頼みの日本企業のバックエンドも強制的に移行せざる得ないかもしれません。今も昔も外圧頼みのところは変わらないので、そういうオチかもしれませんね。はてさて。

そんな感じ。次はFoedusとかの解説とか書く予定。その前にFaRM書くかも。いやまて。