【研究レポート抜粋】P2P Replicated File Store の実装

※これはをアプリケーションエンジニアのWatanabe氏が受賞した第3回研究課題レポート(2009年9月提出)からの抜粋です。

開発背景

主な分散ファイルシステムの特徴

Hadoop DFS

GlusterFS

MogileFS

特殊カーネル不要
プロトコルはHTTPを利用
RAID、SAN、NFS一切不要
ファイルシステム依存なし
自動レプリケーション
簡単にディスク追加が可能
自動フェイルオーバー

Apache + WebDAV

新サーバへのデータ割り振り分のデータ以降が難しい
アプリケーション側での分散ルール追加が必要

Isilon

KVSと分散について

MySQLで負荷分散する場合はマスタースレーブ構成にする方式が一般的に多く採用されているが、この方式ではマスターへの書き込みの分散は難しい。

マスターを分散する場合は、

テーブルを物理的に分散させ、アプリケーション側に分散ルールを実装する
レコードをレンジブロックに分割し、アプリケーション側に分散ルールを実装する

が考えられるが、いずれにしてもサーバ追加時のデータ移行作業は高コストである。

さらに、レンジブロック分割をBtoCサービスで利用する場合、古いデータほどアクセスが少なくなる性質があるため、データ量の分散は行えるが、厳密な負荷分散はされない。

アメーバピグで必要とされている分散ファイルシステム

以上のことから、アメーバピグで求められているファイルストアの要件として、

大量の
細かい(小サイズの)ファイルを
大量のI/Oリクエストでも捌けて
サーバ追加時でもデータ平均化が可能で
冗長性(耐障害性)がとれていて
導入が容易

が挙げられる。

P2P Replicated File Storeの特徴

P2P方式について
オーバーレイネットワーク
物理的に接続された端末で構成されたIPネットワーク上で、特定のアプリケーション同士で接続を行い、論理的に構築するネットワーク。
例)　電話網の上に構築されたパソコン通信ネットワークなど。

非構造化オーバーレイ

構造化オーバーレイ

P2P Replicated File Store では、ファイルストアという目的を踏まえ、構造化オーバーレイとしてコンシステントハッシングを使ったDHTを採用する。

コンシステントハッシングと仮想ノード
P2P Replicated File Storeでは分散ルールとしてコンシステントハッシングを行っているが、単純に物理ノードからキーを計算して配置しただけでは、キーの計算結果によってはデータ担当範囲が偏る問題がある。

上図のようにハッシュ計算によりランダムに作成されるキーによってはNodeAのように担当範囲が大きくなり、ノードによって処理するデータの量に偏りが出てしまう。

対策として、物理ノードの1台に対して100台分の仮想ノードを作成し配置する。
仮想ノードキーの計算は、

仮想ノードキー　=　Host名　+　port + i

とした。

1000ファイルをsaveした際のテスト結果が以下である。

【仮想ノードなし】
ノード	担当ファイル数
Node1	163
Node2	76
Node3	92
Node4	669

【仮想ノードキー100個作成】
ノード	担当ファイル数
Node1	251
Node2	231
Node3	243
Node4	275

上記表の通り、仮想ノードにより偏りは少なくなったが、仮想ノードの導入により以下の問題が発生する。

ノード追加時のデータコピーの局所性物理ノードだけでコンシステントハッシングを行う場合、ノードを追加した際は新ノードが配置される場所の次に位置するノードからデータをコピーするだけでよいという特徴がある。

しかし仮想ノードを導入すると仮想的なノードが入り混じる形で配置されるので、結果的に全ての物理ノードにデータコピーが発生する。

そのため、P2P Replicated File Storeではオンラインでのノード追加機能を諦め、ノード追加時には再起動による再配置に絞ることにした。

耐障害性
レプリケーション
P2P Replicated File Store では、ファイルの格納時にノード側でレプリケーションを自動的に行う。

上図のようにシーケンシャルにファイルレプリケーションを行う。
非同期でのレプリケーションも検討したが、レプリケーション遅延発生時にそのノードがクラッシュするとデータ欠損が発生することを考え、シーケンシャル処理とした。

レプリケーション数は現在固定で2としている。（レプリケーション数が増えるとスループットに大きく影響するため）

障害発生時の流れ
ノードがダウンした際は以下の流れでDEADノードとして検出し、ノードサークルから排除される。

クライアントがsaveなどのI/Oリクエストを担当ノード(ノード1)に送る。
ノード1がダウンしているためタイムアウト、もしくはHTTPステータスコード500系エラーが返却される。
クライアントは一定数リトライを繰り返す(回数は設定変更可能)
リトライ閾値を越えた場合、クライアントはマスターにノード1がDEADであることを通知する。
マスターは全ノードにノード1がDEADであることを通知し、各ノードは保持しているノードリストからノード1をDEADステータスに変更する。
クライアントはノード1がDEADステータスに変更されたノードリストをマスターから通知される
クライアントは新しいノードリストを元に担当ノードを計算し、ノード2のレプリケーションノードにリクエストを投げなおす。

次回再起動時には、DEADノードのデータ復旧が実施される。
※　ノードのハードディスクがクラッシュした場合でも、レプリケーションから復旧される。

データ復旧は全ノードからのデータ復旧リクエストが発生するためある程度の時間を要する。
※　ノードを増やして1ノードあたりの担当ファイル数を減らせば、時間を短くすることは可能。

ディレクトリ情報(Meta データ)の扱い

P2P Replicated File Store では、ディレクトリ情報(Meta 情報)をメモリ上に保持している。
ディレクトリパスをキーにして、ファイルと同じくコンシステントハッシュで分散保持している。

オンメモリに保持しているため、P2P Replicated File Store の再起動時には、各ノードは自信が保持しているファイルのディレクトリパスをキーにして担当ノードを決定し、その担当ノードに対してディレクトリ情報を報告する。

ディレクトリ情報の更新処理は、ファイルMeta 情報、ディレクトリMeta 情報それぞれにチェーン方式による非同期レプリケーションが行われる。

node0は、受け取ったファイルの保存処理の前に、ディレクトリパスからキーの計算を行い、担当ノード(node1)にディレクトリ情報を保存する。
node1は、非同期にmetadataをレプリケーションノード(node2)にレプリケーションを行う。
同じくnode2も、レプリケーションノード(node3)にレプリケーションを行う。

尚、障害発生時はファイルと同じくレプリケーションノードからディレクトリ情報を取得することが可能になっている。

データの平均化機能

P2P Replicated File Store では、再起動を行うと全ノードが自身のファイルを全走査し、キーの再計算を行い、自分が担当ノードかどうかをチェックする。
このとき、ノードの追加や減少により、自分が担当ファイルではないファイルがあった場合は、担当ノードにファイルを送信し、自身のファイルは削除される。

データ復旧機能

P2P Replicated File Store運用時にDEADノードが発生すると、マスターはDEADノードをログに記載する。

P2P Replicated File Storeではオンラインでの復帰（DEADからの復帰）ができないので、次回再起動に復帰することになる。

この再起動の際にマスターはDEADログをチェックし、DEADログがあるノードに関してはレプリケーションノードから復帰ノードへデータの復旧を行う。
この時、復帰ノードに既に同じファイルがあった場合はタイムスタンプが古い場合のみ上書き復旧を行う。

容易な導入

P2P Replicated File StoreはJ2EEアプリケーションとなっているため、TomcatなどのJ2EEコンテナにデプロイすればすぐに利用可能となる。
特別なライブラリやOSレベルでの設定変更などは必要ないため、導入も容易に行える。

パフォーマンス
パフォーマンステスト
約12kbのswfファイルを100万ファイルsaveしたロードテストのパフォーマンス結果を以下に示す。

環境

ロードテスト方法

パフォーマンステスト考察
ロードアベレージ、CPU使用率ともに安定している。
JVMに関してはディレクトリ情報をメモリ上に保持しているため、Old領域の増加が見られる。
これは必要に応じてノードの追加をすることによって回避する必要がある。

GCについてもScavenge GCが安定して実施されており、問題はないと思われる
尚、ロードテスト実施中にはFullGCは起きていない。

クライアント側で計測した1ファイルあたりのスループットもおおよそ0.5秒から0.6秒とファイルストアとしては速くはないが、ファイル数が増えても性能劣化（スローダウン）しないことがわかる。

クライアントが増えてI/Oリクエストの頻度が上がった場合でもスケールアウトさせて（ノードを増やして）対応することで、これ以上遅くはならない。

課題

安定運用ができるようにしていく。

再起動時のデータ復旧機能やリバランシング、キー計算をマルチスレッドで行い、高速化を図りたい。
レプリケーション処理に関して、スレッドプールによる非同期処理を行い、高速化を図りたい。
レプリケーションチェックツール(レプリケーション数の確認)がほしい。

参考

Wikipedia GlusterFShttp://ja.wikipedia.org/wiki/GlusterFS
MogileFSで構築する高速スケーラブルな分散ファイルシステムhttp://builder.japan.zdnet.com/sp/open-source-software-moonlinx-2009/story/0,3800096543,20391825,00.htm
坂本佳久　GlusterFSの性能に関するレポート
Winnyの技術http://www.amazon.co.jp/Winny%E3%81%AE%E6%8A%80%E8%A1%93-%E9%87%91%E5%AD%90-%E5%8B%87/dp/4756145485/ref=sr_1_2?ie=UTF8&s=books&qid=1254044344&sr=8-2
P2P 教科書http://www.amazon.co.jp/P2P%E6%95%99%E7%A7%91%E6%9B%B8-%E3%82%A4%E3%83%B3%E3%83%97%E3%83%AC%E3%82%B9%E6%A8%99%E6%BA%96%E6%95%99%E7%A7%91%E6%9B%B8%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E6%B1%9F%E5%B4%8E-%E6%B5%A9/dp/4844325043/ref=sr_1_4?ie=UTF8&s=books&qid=1254044344&sr=8-4

サイバーエージェント公式エンジニアブログ

CyberAgent Engineer Blog.

【研究レポート抜粋】P2P Replicated File Store の実装