Speedy Transactions in Multicore In-Memory Databases 読んだ

Speedy Transactions in Multicore In-Memory Databases読んだ。

2013年にSOSPで発表された論文。
↓論文リンク
Speedy transactions in multicore in-memory databases

下手をするとただの論文の和訳になりかねないので、できるだけ要点に絞って書くようにする。
一方で、提案手法のアーキテクチャ・動作原理に関しては僕の理解も含めて詳細に書く。
(と言いつつ、結局全訳感が拭えないものになってしまった)

※ この記事内の[n]は論文中のrefer番号をそのまま使ってその論文へのリンクとしています。

概要

Siloは近年のマルチコア化した環境でscalabilityを持つ、非常にパフォーマンスの高いインメモリDB
Siloはメモリを有効活用するために、トランザクションIDを含む競合となりえるポイントを全て回避して設計されている
Siloの主要な貢献は楽観的並行制御(optimistic concurrency control, 以降OCC)を元にしたコミットプロトコルにより、serializabilityを提供しつつ、共有メモリに対する書き込みの全てを回避していること
定期的に更新される"epochs"とコミットプロトコルにより、serializableなdbと同じトランザクションの保証をし、さらにそれによるスケーリング上のボトルネックや追加的なレイテンシはない
Siloは32コア環境で、標準のTPC-Cベンチマークの結果70万トランザクション/秒を達成した
- ほぼ線形のスケーラビリティ--
- 過去の研究より数段高い性能

Introduction

メインメモリのサイズとプロセッサコアの急激な上昇によって、最近のハイエンドサーバはテラバイトクラスのメモリを積み、80コア以上のCPUで動作している。これを効果的に使うのはややトリッキーで、ちょっとした競合があるとすぐにスケーラビリティを制限してしまう。

この論文ではSiloという、マルチコア環境における高パフォーマンスなDBを紹介している。これは全ての競合ポイントを回避し、データによって同期をすることで、巨大なデータベースにおける高い並行性を実現している。

SiloはインデックスにMasstree[23]に着想を得た木構造を用いている。 Masstreeはマルチプロセッサに最適化された高速なBツリーライクな構造である。しかし、Masstreeはnon-serializableでsingle keyトランザクションしかサポートしていない。一方で、著者らの中心的な成果であるSiloコミットプロトコルではそれらの属性もカバーしている。

Siloではある種のOCC[18]を使っている。OCCはローカルな（スレッドごとの)ストレージにreadとwriteの処理を記録しておき、コミットのタイミングで重複するレコードに処理をしていないか確認し、重複している場合はabortする手法である。これにより、書き込みによる読み出しのロックが不要になるため、競合を減らすことができる[11]。一方で、過去のOCCではスケールする上でのボトルネックをなくせていない。その中心的な理由は"anti-dependencies"(write-after-read conflicts)を記録することである。ある同じレコードに対する、読み出しトランザクションt1, 書き込みトランザクションt2を考えた時にserializableなシステムではこれをt1, t2と正しい順番に実行する必要があり、このためにはt1, t2間で通信を行う必要がある。この通信に用いるトランザクションIDはトランザクションが増えることで単調に増加する問題がある。いくつかのnon-serializableシステムでは、この問題を解決できるが、それらは例外的なsnapshot isolationの"write skew"[2]に悩まされることになる。

Siloは全ての読み込みトランザクションに対して、共有メモリへの書き込みを回避しつつ、serializabilityを提供している。コミットプロトコルには十分に注意されて設計されたメモリフェンスを利用して、scalabilityを実現している。この方法には、正しくリカバリできない問題があるが、これは"epoch-based group commit"の形式を使うことで解決した。

Siloのデザインとして重要な点に、共有のメモリストアを選択したことがある。これはどのデータベースのワーカーも潜在的にはデータベースの全てのデータにアクセスできるということである。いくつかの最近のメインメモリデータベースのデザインは"data partitioning"を利用している。これはワーカーがデータのサブセットに対するアクセスをするというもので、これにより、粒度の適切なロックを取得したり、テーブルサイズを縮小したりできるが、これがうまく動作するのは問い合わせの負荷がパーティショニングにマッチしている時である。この実験として、パーティションを行うSiloの亜種を作って実験すると、いくつかの負荷ではパーティションを行うほうが性能が良いが、パーティショニングをまたがるクエリがあるときや、パーティショニング自体が負荷となる時は共有のメモリストアを使うほうが良い結果となった。

また、Siloはワンショットのリクエストモデルを想定している。ワンショットとはクエリの全てのパラメータが実行時に決まっていて、実行中にユーザとのインタラクションが発生しないということである。

これらによって、32コアのマシーンでは、Siloは標準的なTPC-Cベンチマークでおおよそ700,000トランザクション/秒を達成した。コアあたりのトランザクションスループットは8コアの場合の91%で、僅かにしか減少していないことからスケールに成功していることがわかる。この結果は最近のin-memory OLTPシステムのコアあたりのスループットの数倍良い結果である[16, 25, 27, 28]。

Related work

関連研究の章では、過去の研究成果と比べてSiloはスケーリングのボトルネックとなる部分がない、ということが書かれている。

章番号2.1~2.3で、Non-transacrtional systems, Transactional systems, Transactional memoryの過去の研究とsiloとの関係について説明されているが、ここではSiloに関係が強いMasstree[23]とOCC[10, 18]、Siloのゴールに近いとしているトランザクショナルメモリの部分を簡単にまとめておく。

Masstree

Masstree[23]は非常にスケーラブルで高スループットなメインメモリ上のB+treeで、リードロックの代わりにバージョン管理によるバリデーションをする技術を使っている。 Masstreeはtransactionalではないが、Siloの並行なB+tree構造はこのMasstreeに着想を得ている。

OCC(Optimistic concurrency control)

optimistic concurrency control[10, 18]はマルチコア環境に置いていくつかの利点がある。しかしながら、OCCとその亜種[1, 12, 34]はコミットフェーズにおける競合を引き起こす。例えばトランザクションIDの割当や、並行に実行しているトランザクション間のコミュニケーションなどがある。 SiloではOCCの改良したものを実装している。

Transactional memory

Siloのゴールはsoftware transactional memory(STM)システムと似ている。最近のSTMシステムの実装であるTL2[9]はOCCに基づいた実装で、read, writeセットを管理していて、こうした点はOCCデータベースと似ている。いくつかのSTMの実装のテクニック(read validationやロックビットとバリデーションの配置など)はSiloのものと似ているが、他の者は全く違う。

(SiloはSTMにていると言った上で、異なる点も述べている様子だけど、STMがわかっていないせいかこのあたりは理解できなかった)

Architecture

Siloは型付けされたテーブルと名前のあるレコードを提供するRDBである。クライアントはワンショットリクエストのリクエストを発行し、この処理部分はSiloデータベースに直接C++で実装されている。 SiloのテーブルはFig1に示すようにindex treeの集まりで実装されていて、それぞれのテーブルは1つのprimary treeと0個以上のsecondary treeからなる。

Fig 1
f:id:tom__bo:20170916141536p:plain

それぞれのレコードはprimary treeからポイントされる形でメモリ上に保存されている。 secondary treeのキーは、primary keyに関連するレコードに紐付いている。そのため、secondary treeへのルックアップをするときは2つの木を走査することになる。

それぞれのインデックス木は、Masstree[23]ベースのkey-value構造をとっており、他の並行なB-treeに比べるとtrie木のようになっているので、keyの比較に最適化されている。 Masstreeの葉ノードは対応するキーへのrangeを持っている一方で、そのrange内のレコードや、下層の木構造への直接のリンクを持っている。こうした実装は木構造をとっているが、著者らのコミットプロトコル自体は他の木構造(例えばHash-tree)などにも簡単に適用できるようになっている。

それぞれのワンショットリクエストはマルチコア環境でボトルネックにならないように、ワーカースレッド上でブロックをせずに一貫性を保つように(commitかabortのいずれか)実行される。前出の木構造はメインメモリ上に保存されているので、どのワーカーも全てのデータにアクセスすることが出来る。トランザクションの結果は不揮発性のストレージ(stable storage)に保存されることで永続化されるので、それまでユーザに結果を返さない。また、read onlyなトランザクションは現在の状態ではなく、一貫性のあるスナップショットを参照して結果を返す。この"snapshot transaction"の結果は僅かに古い結果を返すことになるが、実行中のトランザクションによってabortされることはない。

Design

この章ではSiloがどのようにトランザクションを実行するかを説明する。
著者らによるOCCの変形は、定期的に更新されるepochsを使うことによって、リカバリの後に置いても有効なserializabilityを達成している。このepochsによって、ガーベッジコレクション(GC)を効率化し、スナップショットトランザクションも可能にしている。

この章ではepochsに続いて、transaction ID, レコードのレイアウト、そして、コミットプロトコルとdatabaseがどのようにこれらを処理するかを説明し、その後、gc, snapshot transactionの実行、durability suppoortについて説明している。

Epochs

Siloは定期的な時刻を示すepochsに基づいて動作している。 epochsによって、seriaizableなリカバリを可能にし、gcとread-onlyなスナップショットを提供している。これらはepoch numberによって識別される。

global epoch
- globalなepoch numberであるEは全てのスレッドから見える
- 専用のスレッドがEを定期的に進める
- 他のスレッドはトランザクションをコミットする際にこのEにアクセスする
- この値はトランザクションのレイテンシに影響するため、頻繁に更新されなければならない一方で、トランザクションの長さより短い必要がある
- 著者らの実装ではEは40msごとに更新される
local epoch
- それぞれのworkerスレッド(w)はlocalなepoch numberであるe_wを保持している
- これはworkerが計算中にEより遅れる
- この遅れを安全にgarbageを回収するために利用する
- Eとe_wが1秒以上離れないようにする必要がある。そのため、実行時間の長いトランザクションは定期的にe_wを更新する

Snapshot transactionsは次で説明する追加のepoch変数を利用する。

Transaction IDs

transaction IDs(以降TIDs)はトランザクションとレコードのバージョンを特定する。またこれによって、のSiloのconcurrency control centerは、ロックの提供とコンフリクトの検出を行う。それぞれのレコードは最新の変更を加えたトランザクションのTIDを持っている。

TIDの構造

TIDは64ビットのIntegerで、その高位ビットはepoch number, 中間ビットは同じepochを持つレコードとの識別子, 最下位の3ビットは以降で説明する"status bits"となっている。

TIDの決定方法

多くのシステムとは違って、SiloはTIDsを中央集権でない方法で決定している。ワーカーはトランザクションのTIDをトランザクションがコミット出来ると確認できた後にだけ決定する。この時、以下の条件を満たす最小の番号に決定する。

(a) トランザクションによって読み書きしたどのレコードのTIDよりも大きい
(b) ワーカーが最新で選択したTIDよりも大きい
(c ) 現在のglobal epoch内における番号のもの

この結果はトランザクションによって更新されたそれぞれのレコードに書き込まれる。

TIDの順序はたいていserial orderになるが、必ずしもserial order担っているわけではない。これはTIDsがanti-dependencies(write-after-read conflicts)を反映していないからである。 (例は省略)

TID word

著者らはTIDは単純なtransaction IDを示し、TID wordをTID+最下位の3ビットとする、と言っている(最初の説明は何だったのか？) statusビットは論理的にTIDとは分離されているが、これらは一緒にすることによって、レコードのバージョンやアンロック操作を1度のアトミックな操作で出来るようにしている。

ステータスビットはそれぞれ、lock bit, latest-version bit, absent bitである

lock bit
- いわゆるlatch
- レコードが現在実行中の更新以外から操作されないようにする
latest-version bit
- 対応するkeyの最新版のレコードであるとき1にセットされる
- 例えばsnapshot transactionのために一時的に古いレコードが保存されるなどして、レコードが置き換えられるときは0にされる
absent bit
- 存在しないkeyと同じものとしてレコードをみなすときに1になる
- insertやremoveによってこういったレコードが作られる

Data layout

Siloのレコードは以下の情報を含んでいる

TID word
previous-version pointer
- previous-versionがない場合はnull
- snapshot transaction(ss 4.9)をサポート
record data
- 可能であればrecord headerと同じcache lineに保存される
- (おそらく上記の2つがredcord header)

コミットトランザクションは高速化のためにレコードデータを入れ替える。しかし、読み取りはそれぞれのレコードで一貫したバージョンを読んでいるかの確認をするために、バリデーションプロトコルが必要になる(ss 4.5) データ部分を除いたレコードは32byteである。

Commit protocol

ここでは存在するキーにたいしてread, updateをするトランザクションについて説明する. insert, delete, range queryについては次の節で説明する

トランザクションが実行されるとき、ワーカーは読みだすレコードを特定する"read-set"を保持する。これはアクセスした時点のTIDである。 updateされるレコードについては、新しいレコードの状態をもった(read-setと異なるTID)"write-set"を保持する。たいてい、write-setに存在するレコードはread-setにも存在する。

トランザクションが完了したら、ワーカーは図2のプロトコルに従って、コミットを実行しようとする。

Fig2
f:id:tom__bo:20170915231650p:plain

Phase 1
- 全てのwrite-setのレコードを調べ、ロックをかける
- ↑のあとにGlobal epochから取得する
- Global epoch取得の部分はコンパイラフェンスによって、コンパイル時の最適化による実行順序の変更を避ける
Phase 2
- 全てのread-setに含まれるレコードを調べる
- Abort if...
  - 読みだしたTIDがレコードのものと異なる
  - TIDが最新でない
  - 他のトランザクションにロックされている、
- 上記の場合以外はPhase 1で取得したepochを利用してTIDをセットする
- (図2ではnode-setのバージョンを確認しているが本文中にはない)
Phase 3
- TIDを利用してレコードの書き込み(update)を行う
- ロックを開放する(TID wordの構造を利用することで簡単に出来る)

Serializability

このプロトコルは以下の理由でserializableである。

読みだすレコードのTIDを検証(validation)する前に書き込みを行うレコードをロックしている
ロックされたレコードをダーティなものと判断し、それがあった場合はabortしている
Phase 1の(コンパイラ)フェンスによって、TIDの検証が全ての現在のアップデート結果を見ていることを保証している

次にこのserializabilityをstrict two-phase locking(S2PL)と比較することで議論する。著者らのOCCがコミットするということはS2PLであるということである。 S2PLでは読みだすレコードの全てにread-lockをかけ、コミット時にしかリリースしない必要がある。SILOではPhase2で最初のアクセスからTIDが変更されていないことと、他のトランザクションからロックが取得されていないことを確認しているので、これを満たしていると考えられる。また、S2PLはupdateされるレコードに対してはread-lockをコミット時に排他(exclusive write lock)ロックにアップグレードするものと扱うことも出来る。SiloではPhase1で書き込みの発生するロックに排他ロックをかけ、Phase2で最初にアクセスしたread-lockと同じものか検証し、アップグレードしている(と考えることが出来る)。

Database operations

ここでは他のデータベースの操作をどのようにサポートしているかの詳細を説明している。

Reads and writes

トランザクションをコミットするときに、変更するレコードを可能であれば上書きするが、変更内容がもとの領域より大きい場合は新しい領域を確保して、そちらにポインタを切り替える。この変更は並列に動作している他の読み出しからは一貫性のあるデータが見えなくなるということである。これを以下で述べる"version validation"プロトコルによって解決している。

commitプロトコルにおけるPhase3でレコードのデータを書き換えるために、ロックを保持しているワーカは、

(a) レコードをアップデートする
(b) メモリフェンスを実行する
(c) TIDを格納し、ロックをリリースする

一貫性のために要求されることは、並行して実行している読み出しがロックの開放されたレコードを見るときに、新しいデータと新しいTIDが見えなければならない、ということである。ステップ(b)で新しいデータが見えることが保証され、ステップ( c)で新しいTIDの格納とロックの解法が同時に行われる(TID wordとして一箇所にあるため、これが可能)。

トランザクションの実行中に(このコミットプロトコルとは別に)データレコードにアクセスするには、

(a) TID wordを読む(lockがクリアになるまでspinする)
(b) レコードが最新か確認する
(c ) データを読む
(d) メモリフェンスを実行する
(e) TIDワードを再度確認する

もし、ステップ(b)でレコードが最新のも音出なかったり、TID wordがステップ(a)と(e)で異なっていたら、ワーカーはretryかabortする。

Deletes

Snapshotトランザクションでは削除されたレコードが木構造に残る必要がある(スナップショットに関連するバージョンはアクセス可能な状態であることが必要)。そのため、Siloではabsent bitを利用して、レコードを残したまま、検索ではmissing keyと判定できるようにしている。このレコードはいずれgarbage collectionによって回収されるが、上書きされることはない。

Inserts

コミットプロトコルのPhase2は最初にロックを獲得することでwrite-write conflictを扱っているが、レコードがない場合(insertされる前の状態ではレコードがない)、ロックすることが出来ない。そのため、Siloではコミットプロトコルが始まる前にデータをinsertする。その後は通常通りコミットプロトコルを実行し、コミットする場合は通常のput(書き込み)と同様に処理し、abortした場合はabsent bitを立てて、gcされるようにする。

Range queries and phantoms

Siloはトランザクション中にRange queryを使える。一方で、Range queryは複雑で、"phantom problem"[10]という範囲検索をしている最中に本プロトコルで感知出来ないところで、範囲中のレコードが消えたり変化したりすることで、serializabilityを壊す問題がある。この問題を解決する典型的な方法は"next-key locking"[24]であるが、読み出しのためにロックが必要になることからSiloの設計思想(design philosophy)と逆行する。

そのため、SiloではB+treeのバージョンナンバーを活用することでこの問題に対処している。 B+treeでは構造の変化が起こるときにノードのバージョンナンバーが変化することが保証されている。そこで、read-setを管理するときにバージョンナンバーを含んだnode-setも管理し、このnode-setに変化がなく、phantomも発生していないときにコミットするようにしている。さらに、insertでは構造変化が起きるが、現在のトランザクションによって、構造変化がおきているのか(abortするべき)、値の変化がおきてノードのバージョンが変わったのか(abortする必要はない)を区別する必要がある。これにはinsertはコミットプロトコルを開始する前にinsertを実行していることを利用し、node-setに入れたバージョンが変化するかを見ることで、insertが成功したか失敗したかを判断し、有効な構造変化が実際におきているかを区別している。

Secondary indexes

Siloのコミットプロトコルにとって、セカンダリインデックスは単純にsecondary keyからprimary keyへのマッピングをしている追加の表と考えられる。あるトランザクションが、セカンダリインデックスの構造を変化させるような変更を行うと、通常その影響を受けるセカンダリインデックスを使う他のトランザクションはabortすることになる。

Garbage collection

SiloのトランザクションはB+treeのノードとDatabaseのレコードの2つのgarbageを発生させる。これらの解放には参照カウンタを利用するのではなく、read-copy update(RCU)[11,13]を利用している。少し詳細に説明すると、ワーカーがgarbageを発生させたときにはそのオブジェクトと"reclamation epoch"をCPUコアごとのリストに追加する。 reclamation epochとはそのエポック移行はそのデータに触れなくなることを示すためのエポック時間である。この時間を過ぎたものを解放していく。

Snapshot transactions

Siloでは実行中のread-onlyな直近のsnapshotsを、レコードの余分なバージョンを保持することで実現している。これらのバージョンは一定の期間の全ての変更をserial orderで保持した、一貫したスナップショットを構成している。

スナップショットを管理することはチェックポイントにも有効だが、スナップショットが一貫して完全なものであることを保証すること、メモリが徐々にGCされることを保証することの2点でトリッキーである。

Evaluation

Siloのパフォーマンスに関する以下の仮説を検証していく。

単純なkey-valueベースの負荷に対してread/writeのコストが低い
さらなるcore数のスケールが可能なこと
partition data storeなものより、cross-partitionの負荷に対して頑健
snapshotトランザクションによって、read-onlyのトランザクションの効率が向上する

Experimental setup

全ての実験は1台の端末で行っている

8コア, Intel Xeon E7-4830, 2.1GHz(最大で32物理コア)
1コアあたり32KBのL1キャッシュ, 256KBのL2キャッシュ
1CPU(8コア)ごとに24MBのL3キャッシュと65GBのDRAM
64bit Linux 3.2.0
カスタムのメモリアロケータ
4スレッドのロガーを起動
- 3つはそれぞれ異なるFusion IO ioDrive2デバイスに接続
- 残りの1つはRAID-5で設定された6つの7200RPM SATAドライブに接続
- (目的不明)

ネットワーク接続したクライアントは使用しなかった。ネットワーク接続することでMasstreeは23%のスループット向上が見込める[23]ため、ネットワーク接続すればさらに性能向上する見込みだそう。

Durabilityを考慮しなくて良い場合を想定して、ロギングを行わない設定の場合"MemSilo"と示す。

Overhead of small transactions

Fig4
f:id:tom__bo:20170915231720p:plain

Fig4はMemSiloとKey-Valueストアのスループットの比較を示している

Key-ValueストアにはSiloで使っている並列B+treeを用いている。ベンチマークはYCSB[6]ベンチマークをの修正版を使っている。この修正は適切にMemSiloの特性を調べるためにしたもので、詳細は省略。大まかな修正内容は、

read/writeの比率を50/50から80/20に変更
write操作をread結果を変更するwriteに変更
レコードサイズを1000バイトから100バイトに変更

この結果Key-ValueはMemSiloと比較して最大1.07倍の性能向上を示した。

また、TIDの割当をする部分を1つのglobalなカウンターで行った場合の結果が"MemSilo+GlobalTID"であり、この性能が32ワーカースレッドで大きく悪化していることから、TIDの割当部分のボトルネックを解消する必要があったことがわかる。

Scalability and persistence

次に一般的なTPC-C[33]でのベンチマークの結果を示す。 TPC-Cでは倉庫に対する操作をシミュレートしているが、ほとんどはローカルの倉庫にリクエストを飛ばすのに対して、少数のリクエストはリモートの倉庫に対して行うことになる。 SiloでTPC-Cを実行するために、同じ倉庫に属する全てのクライアントは同じスレッドに割当てた。これによって、トランザクションによってアクセスされるメモリは大抵同じNUMAノード内になる。また、倉庫の数をワーカーの数と同じにすることで、ワーカーが増えることでデータベースも大きくなる用にした。

Durabilityの影響を比較するためにMemSiloとロギングを行うSiloで実験を行った結果がFig5,6である。

Fig5 (Fig6は省略)
f:id:tom__bo:20170915231744p:plain

MemSiloでは32ワーカーまで、スケーリングが線形に近く達成されている。32ワーカーでのコアあたりのスループットは1ワーカの場合の81%で、8ワーカーの場合1ワーカの98%だった。 1~8コアでのパフォーマンスの低下はL3キャッシュのサイズが要因(と言っているが、8~32コアでの原因は触れられていない) 28ワーカー以上ではロガースレッドのコンテンションが発生している。

更に、著者らはロギングのシステムとハードディスク(durable storage devices)の影響を分離するために、tmpfsをロギング先にして実験を行った。この時のレイテンシの変化をFig7に示す。

Fig7
f:id:tom__bo:20170915231800p:plain

Silo+tmpfsのときのスループットは最大で1.03倍の向上しかなく、このことからハードディスクへの書き込みによる遅延よりも、ワーカースレッドからロギング用のスレッドへのデータ転送でスループットが低下していることがわかる。 Fig7を見ると、ワーカースレッドとロギングスレッドでの競合が発生することで28コアあたりで、スパイクが発生していることがわかる(← 図からでスレッド同士のコンテンションといえるのか??)。ロギングの影響はスループットよりもレイテンシに大きく関わるが、レイテンシが僅かに(modest)上昇するだけで、32コア環境ではMemSiloはSiloの1.16倍しか変わらない。(←図では省略したMemSiloが出てくる。。。)

Comparison with Partitioned-Store

ここではSiloと静的にパーティショニングされたデータストア("Partitioned-Store") [25, 30, 32]との比較評価を行う。以前に述べた理由から、TPC-Cのテーブルはwarehouse-idによってパーティションする。

[Cross-partition transactions]

Partitioned-StoreはH-Store,VoltDB[32]を土台として著者らが設計した様子。これらの詳細は省略するが、B+treeのテーブルからパーティションごとに分離し、グローバルなパーティションロックを用いて、全てのトランザクションは一度パーティションロックをスピンロックで取得して、パーティション毎の処理を実行する用になっている。
また、Siloに対しても同様にテーブルを静的に分割したものを用意し、これをMemSilo+Splitとする。

TCP-Cには倉庫をまたいで新たしい注文を作成するトランザクションが僅かに含まれているが、このパーティションをまたいだ(cross-partition)トランザクションの割合を変化させたときのスループットをFig8に示す。

Fig8
f:id:tom__bo:20170915231833p:plain

この図を見るとわかるようにパーティションのロックが必要となるPartitioned-Store方式では、パーティションをまたぐクエリがないときや10%程度のときはスループットが高いが、約20%程度でMemSiloとの逆転が起きる。 (Partitioned-Store方式には永続化デバイスへの書き込みがないので、Silo側もMemSiloとの比較となっている)
また、MemSiloにパーティションを取り込んだMemSilo+Splitはそれぞれのノードでのキャッシュローカリティが向上することで、約13%の改善ができた。MemSiko+Splitの違いはコンカレンシーコントロールの部分だけである。

[Skewed workloads]

次の実験では負荷(workloads)に偏り(skew)をもたせる、つまり局所的なデータにアクセスさせる(hot-spotを作る)複数のワーカーを1つのパーティションのデータに対してのみアクセスさせ、かつ、競合を起こしやすいように全てのトランザクションが新規の注文を行うものとする。こうした負荷は現実では発生しないが、パーティションのデータへのアクセスに対するスケーラビリティを調査するものである。

この結果を示しているのがFig9で、Partitioned-Storeの方式ではパーティションごとに1スレッドしかないため、スケールしないが、Siloではこの場合でもスケールしていることがわかる。また、このベンチマークのリクエストでは注文のIDを生成する最初のトランザクションと、それを利用する次のトランザクションによって構成されている。そのため、OCCの方式によって、2つ目がabortすると、1つめも含めてabortすることになる(このあたりのtransactionは「処理」という広義の意味で使っているのか不明)。そこで、IDを生成する部分を外部に出したMemSilo+FastIdsの結果も示してある。これを見るとわかるように、MemSilo+FastIdsではほぼ線形にスケールしていることがわかる。

Effectiveness of snapshot

5.5, 5.6節ではSnapshotの機構によって大量のデータをreadするトランザクションに対しての処理能力向上や、メモリの効率的管理、それによるGCの効率化について述べているが省略。

Factor analysis

Siloのオーバーヘッドをより明確に調べるために、2つのグループに分けて、オーバーヘッドを調査した。 1つ目はRegularと示すもので、永続化部分に関係ない処理を変更したもの、2つめはPersistenceと示す、永続化部分に変更を加えたものである。

この結果をFig11に示す。

Fig11
f:id:tom__bo:20170915231922p:plain

（僕としてはどちらも累積値を示しているので、本当にそうか疑問だと思うが、)
Regularの方ではOverwrites:値の上書きができる場合は追記ではなく上書きする、処理による効率化が最も有効。 Persistenceの方はMemSiloから、

+SmallRecs: 書き込み処理だけロギング
+FullRecs: 全てロギング、Fig5と同じSilo
+Compress: ログをLZ4で圧縮

それぞれの処理を加えていった結果を示している。 (ここから、圧縮処理によって、ワーカーからロガーバッファーへ渡すデータ量が減っているみたいなことが書かれているが、英語力がなくて理解できず、そもそも説明不足だと思う)

Conclusions

この論文では、大量のマルチコアマシーン上でもスケールするOCCベースでシリアライザブルなストレージエンジン、Siloを提案した。Siloのコンカレンシーコントロールプロトコルでは、マルチコアのパフォーマンスのために、グローバルなクリティカルセクションを回避するとともに、read処理のためにローカルなメモリに書き込みを行わないものになっている。また、シリアライザブルなリカバリ、GC、read-onlyなスナップショットトランザクションのために、epochという仕組みを導入している。この結果、SiloはYCSB-AとTPC-Cのベンチマークにおいてほとんど線形なスケーラビリティを達成し、トランザクションの一貫性(consistency)とスケーラビリティはhigh performanceレベルで共存できることを示した。

感想・メモ

Global Tidがボトルネックになっているから、epoch使ってTidの割当を分散しようというのが言葉としてはわかるんだけれど、Fig2と合わせても、なるほどーくらいしか分からなくて、周辺のコードをさっと確認できるとC++力が欲しい。
phantom readの対策としてB+treeのバージョン構造(今回だとMasstree?)を使っているらしい、インデックスでのバージョン管理、排他制御の仕組みを見てみる
- 適当にggってみたら日本語でも最近の関連論文あった(http://db-event.jpn.org/deim2017/papers/387.pdf)
登壇時動画(Youtube)
- www.youtube.com
この論文に関して書いているブログをggって見たらid:okachimachiorz さんの解説があった
- d.hatena.ne.jp
- DB研究の第一線メンバー/チームとか、実際のDBプロダクトの流れは論文をいくつか読むだけではわからないので、とても参考になります。

tom__bo’s Blog

MySQL!! MySQL!! @tom__bo