« My weblog URL changed (ブログ移転のおしらせ) | Main | Pacific のクライアントAPI (仮) について »

June 10, 2009

Pacific という名前の分散ストレージを作り始めた件

 大規模なウェブアプリケーションのボトルネックがデータベースであるという点については、多くの同意が得られるところだと思います。解決策としては、同じ種類のデータを複数の RDBMS に保存する「sharding」 (別名:アプリケーションレベルパーティショニング/レベル2分散注1) が一般的ですが、最近では、分散キーバリューストア (分散 KVS) を使おうとする試みもみられるようになってきています。

 分散 KVS が RDBMS sharding に対して優れている要素としては、事前の分割設計が不要で、動的なノード追加(とそれにともなう負荷の再分散)が容易、といった点が挙げられると思います。一方で、KaiKumofs のような最近の実装では eventually consistent でこそ無くなってきているものの、ハッシュベースの分散 KVS は、レンジクエリができなかったり (例: 最新5件の日記を表示)、トランザクションがないためアプリケーションプログラムが複雑になったりするという問題を抱えています。

 では、どうすればいいのか? MySQL や PostgreSQL を使った RDBMS sharding でも、動的なノード追加(と無停止での負荷の再分散)を実現したい。というのが、今回コードを書き始めた動機でした。それが Pacific です。

 技術的には、大して複雑ではありません。Pacific は、パーティショニング情報とロックを管理する中央サーバ(リゾルバと呼んでいます)と、実際のデータを保存する RDBMS のノード群によって構成されます。

 Pacific では、レンジクエリを実行するために、ユニークキーを利用したレンジパーティショニングを行います。レンジパーティショニングは、ハッシュベースのパーティショニングよりもデータの局所性が向上するので、パフォーマンスや障害の局所性が高まるという効果も期待できます。

 また、トランザクションを可能にするためには、関連するデータが常に同一のノード上に配置される必要があるため注2、全てのデータがパーティショニング用のキーに関連づけられるようなテーブル設計を強制することになります。このデータモデルは、(Pacific が RDBMS 上の分散ストレージであるという点を除けば) Google App Engine の Data Store注3 と同様です。Pacific では、パーティショニング用のキーを含むテーブルをプライマリテーブル、プライマリテーブルと 1:1 または 1:n のリレーションをもつテーブルをセカンダリテーブルと呼んでいます。

 データの再配置は、単一の (あるいは数個の) ユニークキー単位で、1) そのキーに属する全データに排他的書き込みロックをかけ、2) データを別ノードにコピー、3) パーティショニング情報を更新して書き込みロック解除、 4) 旧ノードから読んでいるクライアントがいなくなった時点で旧ノード上のデータ削除、という操作を繰り返すことで行います。再配置中に読み込みがブロックされることはありませんし、書き込みがブロックされる時間も、エンドユーザーが意識しなくていい程度に抑えることができる、と考えています注4

 一番アクセスが集中するのはリゾルバということになりますが、パーティショニング情報の変更は少ないことが予測できますから、ストレージへのアクセス数が 10万 QPS 程度になるまでは問題は発生しないと思います注5。また、パーティショニング情報は RDBMS に保存されるため、リゾルバが不正終了しても、データの不整合が発生することはありません。

 Pacific については、コードは公開の svn レポジトリ注6上においてありますが、現状、テストコードとラフなサンプルが動いている程度で、ドキュメントが全く未整備です。進捗や具体的な使い方等については、今後このブログで書いて行きたいと思います。

17:12追記: 高可用性については、ウェブアプリケーションが使う分散ストレージの場合、ネットワーク分断が発生しない(冗長化によって防止できる)ので、ノードをまたがるような冗長化は必要なく、各ノード毎にクラスタを組めばいいという考えです。

注1. ミクシィのCTOが語る「mixiはいかにして増え続けるトラフィックに対処してきたか」:ITpro
注2. 多くのトランザクションは、関連する数個のテーブルに対する局所的な操作であるという仮定の下、同一のキーに属するデータ内でのみトランザクショナルな操作を可能としています
注3. The Python Datastore API - Google App Engine - Google Code
注4. 書き込みがブロックされる時間は、特定のキーに属するデータサイズ (Google App Engine で言うところのエンティティグループの大きさ) をコピーする時間に依存しますが、一番遅いのはHDDにシーケンシャル書き込みになるでしょうから、数MB/s 程度は目指したいところです
注5. より高いパフォーマンスが必要なら、リゾルバをレプリケーション対応化すればいいという話です。同時に、各ノードへの直接接続をやめて、中継サーバを用意するといった作業も必要になるでしょう
注6. http://kazuho.31tools.com/svn/pacific/

TrackBack

TrackBack URL for this entry:
http://bb.lekumo.jp/t/trackback/404050/20122637

Listed below are links to weblogs that reference Pacific という名前の分散ストレージを作り始めた件:

Comments

Post a comment