[n] は論文中のreferの番号をそのまま使っています。
Abstract
この論文では2013年から存在したVoltDB DBMSの設計上の決断について説明している。 特に"concurrency control"と高可用性について議論している。
Introduction
VoltDBの目的は伝統的なRDBMS(MySQL,DB2,SQL Server)より高速に動作することである。
これらのRDBMSは伝統的なトランザクション処理(TP)を行う一方で、最近のTPアプリケーションでは従来とは違ったユースケースが必要となっている。
例えばインターネットゲームの状態管理や、リアルタイム広告配信などで、これらでは大量のメッセージによる更新の繰り返しに、信頼性のあるTPを高速に行わなければならない。
この論文ではこういったTPをModernTPと呼んでいる。
VoltDBと研究面でのプロトタイプであるH-Storeの開発モチベーションは、メインメモリの価格が急落したことにある。 1TBのメインメモリが$30,000で買えるようになり、128GB*8ノードのコンピュータネットワークを構築できるようになった。 時間とともに、10~100TBのデータベースがメインメモリ上に展開されるようになるだろう。 この時代(decade)の終わりには、"Phase Change Memory(PCM)“か"Memristors"のような新しいメモリ技術が利用可能になっているだろう。
もしデータがメインメモリに収まる程度であるなら、[3]がdiskベースのDBMSアプリケーションのパフォーマンスに重要な評価をしている([3]を読んだ以前の記事)。 TPC-Cのベンチマークに置いて、従来のDBMSアーキテクチャでは10%程度しか本来の処理(usefle work)を行っていないというものだ。 残りの90%は大きく4つのオーバヘッドに割かれていて、それはバッファプール、マルチスレッド化、レコードレベルのロック、ARIESスタイルのwrite-ahead log(WAL)である。 この論文の惹きつけられる結論はこの4つのオーバヘッド全てを取り除かないと大きな改善が出来ないというところである。このこのモチベーションによってVoltDBは設計されている。
Assumption
Workload
まず、高可用性(HA)とはアプリケーションの最下層に求められるもので、ノードが落ちたときにシステムはシームレスにバックアップレプリカにフェイルオーバし、稼働し続けことである。シングルノードのシステムではこれは不可能であり、VoltDBではマルチノードのクラスタアーキテクチャを想定している。 この環境であれば、テーブルを"シャード(shards)“として分割してシャードをクラスタ内のノードに配置することも理解できるだろう。 VoltDBではハッシュ(以降、レンジ:range)分割をサポートし、それぞれのシャードはK+1回レプリケートすることで"K-safety"の概念をサポートしている。
次にVoltDBでは現在のトランザクションとレプリケーションに対してもACID特性を提供することに注力している。 これは多くのDBMSが弱い保証をしていることとは対象的である。 もっと言うなら、結果整合性"eventual consistency"は全く保証していない。 VoltDBはレプリケートされ、シャード化された純粋なACID SQLシステムである。
著者らはアプリケーションはいくつかのトランザクションからなっているとし、small/midium readとsmall writeに分類した上でさらにwriteについて以下のように分類した。
- Single-node transactions(最多数派)
- One-shot transactions(少ない)
- 並行にさまざまなノードで実行されるトランザクション
- General transactions(さらに少ない)
- 複数のフェーズからなり、前のフェーズが完了してから次のフェーズに進む
- 複数のノードで実行される
Large readはデータウェアハウスが最適化されているので、そっちを使えとのこと(ModernTPの範疇ではないということか?)
VoltDBではトランザクションは決定的であると想定している。
そのため、読み出しの途中で分岐が発生せず(?)、さらにトランザクションの途中でVoltDBの外部との通信によってブロックされない。
VoltDBではトランザクションはストアドプロシージャであり、コンパル時に解析され、上記のwriteパターンに分類されruntimeシステムに組み込まれる。
ユーザはトランザクションを実行する際にストアドプロシージャをその引数とともに指定する。
アドホックなクエリや更新は一時的なストアドプロシージャを作成することで対応する。
LAN and WAN Behavior
大抵のVoltDBアプリケーションはLAN内で1つのクラスタを構築する。 その場合、LANが原因で分断が発生することは極端に稀である。分断が起こるのは、node failures, application errors, DBA errorsなどで、後半の2つはVoltDBクラスタを停止させるが、ネットワークの分断はそれほどボトルネックではなく(“the high pole in the tent”)、全体の可用性を極度に改善するわけではない。 そのため、VoltDBでは可用性と一貫性を選択した(“chooses consistency over availability”,おそらくCAP定理のCAを選択という意味)。
ネットワークの遅延が課題となるがWAN越しのクラスタ構築も可能。
Multi-Threaded Operation
VoltDBは共有メモリを静的に"チャンク(chunks)“という単位に区切り、それを個々のCPUコアに割り当てて1つのノードとしている。CPUコア内ではマルチスレッド可はされていないため、ラッチやクリティカルセクションがない。 そのため、VoltDBはマルチスレッドシステムで蔓延しているレースコンディションを気にしない。 著者らの意見では、マルチスレッドシステムのせいで、多くのコンカレンシコントロールとリカバリエラーが引き起こされている。 VoltDBには並行処理のコードがないので、比較的デバッグがしやすい。
Main Memory Operation
すべてのデータはメインメモリ上に保存される。 もちろん物理メモリを使い切り、仮想メモリがスワップし始めるとパフォーマンスが落ちるので、十分な物理メモリがあることは必須である。 この構造のため、バッファプールやそのためのコードはない。
Concurrency control
VoltDBは全てのオペレーションを決まった順序で実行する。 この分野の過去の成果は時間を実行順序として利用しているものが多いが、VoltDBは時間ベースのスキームではない。 VoltDBのクライアントライブラリはシャーディングの情報を持っているので、シングルノードトランザクションは正しい"ノードコントローラ"に転送され、シリアライズされて実行される。
その他のトランザクションは特別な"グローバルコントローラ"に転送され、順序が決定される。
Crash Recovery and High Availability(HA)
レプリケーション、フェイルオーバ、フェイルバックと停電のような"global cluster failure"について議論する。
Replication
高可用性はレプリケーションを通して達成される。 VoltDBであｈトランザクションが実行されると、最初に安全に全てのレプリカに並列に送信される。言い換えるとこれはactive-activeシステムである。コンカレンシコントロールが決定的なので、それぞれのトランザクションは全てのノードにおいて成功するか、失敗するかであり、他の同期処理を必要としない。 対象的に他の一般的なコンカレンシコントロールスキームは、例えばMVCC、この決定的な性質を持っていないので、ログを送信しあうなどして同じ結果がえられるかを確認している。このactive-passiveスキームはログの通信を必要とするので、期待できるパフォーマンスはずっと悪くなる。
ノードは"I am alive"メッセージを交換し合い、死んでいると判断されたノードはクラスタから外され、残りのクラスタで処理が続けられる。このように、K台まではノードフェイラーを収容していき、K+1のエラーとなるとクラスタが停止する。
ノードがオペレーションに復帰すると、次の節で述べる方法で、現状のクラスタと近い状態になるような処理が実行される。新しいノードが追加された状態にシステムカタログが更新され、直近のトランザクションログが実行されて(次の節で述べる)、元の通常の状態に戻る。
Global Errors
著者らはいくつものVoltDBカスタマーを抱えている。大抵はオフプレミス(クラウド)で運用しているため、UPSのおかげで停電とは無縁である。 一方で、オンプレミスのサーバはUPSを持っていないことがあり、この場合は停電が発生した場合に全てのデータを失うことになる。
このエラー状態を解決するために、VoltDBであｈ非同期のトランザクションからなるチェックポイントを設けている。 特に"checkpoint-begin"が発生すると、ローカルエクゼキュータはcopy-on-writeモードで動作し、チェックポイントまでの結果をディスクに書き込む。 インデックスの情報はこれに含まれないが、リカバリ時に再構築を行う。
加えて、VoltDBはトランザクションログを保持している。これはトランザクションの指定しと、そのパラメータである。 トランザクションログはユーザに結果を応答する前にグループコミットによってディスクに書き込む。
グローバルエラーが発生した場合は、最後のチェックポイントまでのトランザクションを各ノードで復元し、それ以降のデータのために、ノード間でトランザクションログの最後を送信し合い、最後のトランザクションログまでを各ノードで通常通り実行することでコミットされたトランザクションを実行した状態まで復元ができる。
著者らの実装ではチェックポイント作成とトランザクションログの生成による低減は5%程度であり、一方で、ディスクへのトランザクションの効果を押し上げる手法を開発した。これは[5]で解説されていて、ARIESの単純化され、合理化されたバリエーションである。 テストとして、トランザクションのロギングと、データをロギングする手法を比較すると、トランザクションのロギングが3倍高速だった。 これによって、リカバリの時間も増加するが、グローバルフェイラーは極めて稀なため、リカバリの時間よりもランタイムの時間に最適化することは適切なように思える。
Current Development Focus
SQL
VoltDBのエンジニアはサポートするSQLのサブセットを拡大することに集中している。 結局SQLの仕様は1500ページにもなるので、現在進行中である。そのため、カスタマーのリクエストのあるものをベースにしている。
On-Line Reprovisioning
著者らのカスタマー、特にウェブサービスを提供している、はしばしば激的な負荷の上昇に遭遇する。 いわゆる"hockey stick of success"である。 明らかにこうした場合にK個のサーバーで処理をしたいので、ノードを追加したり削減したりするために再配置(re-sharding)が発生しうる。 この論文が公開されることには無停止再配置(On-line re sharding)が完全に利用可能になっているだろう。
Integration with Downstream Repositories
2章で述べたようにVoltDBは保存することに重点を置いて、長期でデータを運用するようなデータウェアハウススタイルのクエリを想定していない。 カスタマーの要望に答えるために、データをストレージにエクスポートするつもりである。
Application Areas and Benchmarks
Early Application Areas
省略
VoltDB Performance
電話投票を模したベンチマークを行って性能を評価した。 テーブル構造は以下の表1で、投票に、3select, 1insert, 2updateが走る。 この他、立候補者のヒートマップの作成、リーダーボードの作成のための集計が1秒に1回行われる。
表1
5ノードの"dual quad-core SGI)システム(全40コア)のシステムでは、640,000 投票トランザクション/秒となり、これはコアあたりの1SQLコマンドに10μsしかかかっていない結果である。 更にノード数に対して線形に性能が上がり、30ノードでは3.4 million トランザクション/秒で、線形のスケーラビリティの傾きは0.88となった。 この結果は、www.sgi.com/pdfs/4238.pdfにとあるが、リンク切れだった。
Summary
VoltDBはクラスタノード上でModernTPのために設計されたメインメモリDBMSである。 これは決定的なスケジューリングをすることで、active-activeレプリケーション戦略をとっている。 こうした"NewSQL" DBMSが、パフォマーンスにおける圧倒的な優位性によって、ModernTPのマーケットを台頭していくと予測している。
感想
“Rethinking Main Memory OLTP Recovery"を読もうとしてVoltDBの話が分からなかったので、この論文を読んでみた。 VoltDBのwebサイト見ればDBの仕組みはわかるけど、論文としてミドルウェアの紹介があるんだなーということで読んでみた。 結局システムそのものの理解をするなら公式サイトを見に行ったほうが良くて、これが開発された背景、理論的な立ち位置を理解するには論文を見てみても良いかなといったところ。
理論よりなものでなくても、未だに論文(英語)を読んでいて理解に時間がかかるものが10文くらい出てきて、そのうち2つくらいは結局理解できないという感じ。 今回だと6章で出てくるThe net result is …の２文が理解できなかった。。。
こういう応用より？な論文だと、"high pole in the tent"ととか、セクハラまがいな(?)説明とか"hockey stick of success"みたいな表現がでてきて結構面白い。 アカデミックでないわけではないけど、他分野の論文で、こういう表現見たことない。(←サンプル数100程度…)
ということで次は"Rethinking…“を読んでみる
