高い可用性と性能を低コストで確保―分散技術の先端を知る—Part4

クラウドを支える要素技術

数万から数10万台のCPUやHDDを使い、大規模なデータを分散管理・処理する。そのうちいくつかが故障しても処理を継続できる─。
クラウドを支える、このような分散処理はどんな仕組みなのか。そこにはMapReduce、キーバリューストア、P2P通信といった技術要素がある。

分散システムは、複数台のコンピュータノード（以下、ノード）を用いることにより、システム全体としての処理能力を向上させたり、可用性を増大させることを目的にしたシステム形態である。処理するデータ量の増大に対してこれまでは、サーバーのCPUを増設する、リレーショナルデータベース（RDB）を増強する、といった対策で乗り切るケースが多かった。しかし、そうした対策はパフォーマンスとコストの両面から見て限界を迎えつつある。信頼性の高いサービスを低コストで提供するクラウドコンピューティングにとって、大規模な分散システムを実現することは極めて重要である。

ただし、分散システムには複数のコンピュータを単純に並べるだけは不十分で、それらを協調動作させる技術が不可欠だ。その上で大量のデータを高速に処理する性能と高い可用性を実現しなければならない。

本パートでは、インターネットイニシアティブ（IIJ）が独自に開発した「ddd（distributed database daemon）」を例に、低コストのPCを利用しながら信頼性の高い分散システムを実現する技術について解説する。

dddは、IIJのバックボーン回線を流れるトラフィックを解析することを目的に開発した分散システムである。現在では、セキュリティサービスやアプリケーションサービスのログ解析など、より広範なデータの処理に活用している。

ここで、分散システムを定義しておきたい。分散システムとは、多数のノードで構成されているが、それを利用するユーザーからは単一のものとして見えるシステムのことである。分散システムの例としては、巨大なデータを保持する分散ストレージや、分散データ処理などが挙げられる（図4-1、4-2）。近年、この分野では技術開発が活発に進められている。そのなかでも代表的な技術を、表4-1に挙げる。「Google File System」や「Amazon Dynamo」は分散ストレージ、「MapReduce」は分散データ処理技術に分類される（表4-1）。

図4-1　分散ストレージ
データを複数ノードで分散保持する。ユーザーからは1つのストレージに見える

図4-2 分散データ処理
データ処理対象をたくさんのタスクに分割し、複数ノードで並列に処理する

図4-3　dddの3層構造

IIJが開発したdddは、その両方の機能を併せ持つ。dddの各ノードは、図4-3のような3層構造になっている。すべてのノードは同一の構造である。以下で、分散システムを実現するための各層の働きや特徴を見ていきたい。

データの抽出／加工をMapReduce技術で高速化

dddは、「フロー情報」と呼ぶ膨大なトラフィック情報を処理するため、MapReduce機能を搭載している（注：フロー情報については34ページの囲みを参照）。これにより、IIJでは数百億レコードを超える大量のトラフィック情報を対象に様々な条件で、かつ実用的な応答速度で解析できるようになった。

MapReduceは、Googleで考案された大規模データ処理のためのプログラミングモデルである。その名の通り、データを「map」と「reduce」の2段階に分けて処理するモデルで、多数のノードで効率よく分散並列処理を実行するために使われる（図4-4）。

図4-4　「MapReduce」と呼ぶプログラミングモデル。データ効率よく分散並列処理できる

GoogleはMapReduceのソースコードは公開していないものの、仕組みに関する論文を発表している。今では、それを基に類似の機能を持った実装がいくつか出てきており、検索エンジンのインデックスの作成やログファイルの解析などに使われている。

mapとreduceは、分かりやすく言い換えると「抽出」と「集約」である。map（抽出）のフェーズではデータの中から必要な情報を抽出し、必要に応じて後の処理がしやすい形に変換する。reduce（集約）のフェーズでは、mapされた情報を集約する。処理内容それぞれに依存関係がないならば、その処理は複数のノードに分担させて並列実行できる。

MapReduceの最も単純で分かりやすい応用分野は、分散grepだろう。grepはUNIX系のOSに付属しているコマンドで、テキストファイル中から指定した文字列パターンにマッチする行を検索して出力するものである。grepは事前に検索のためのインデックスを作らず、その都度総当たりで調べるため、ファイルが巨大であったり大量にある場合は時間がかかる。このgrepコマンドにMapReduceを使えば、対象ファイルのgrep処理を複数ノードで分担できるため、全体の処理時間を短縮できる。

IIJは、このMapReduseの考え方に基づくデータ処理プログラムを独自開発した。このプログラムにおける処理の流れを説明しよう。

ユーザーはまず、解析対象や対象期間、データ抽出条件、グルーピングの軸といったパラメータを含む「MapReduceジョブリクエスト」を準備する。次に、dddのノードのどれかに対してそのリクエストを送信する。リクエストを受けたノードは、対象期間を一定間隔で分割する形で、MapReduceジョブを複数のmapタスクとreduceタスクに分解する。mapタスクは各ノードに割り振られ、各ノードはパラメータに従って抽出やグルーピングといった処理を実行する。

各ノードでのmapタスクの実行が終わったら、reduceタスクを起動して結果を集約する。集約された結果は、分散ストレージに書き出される。または、ユーザーのマシンに直接返すこともできる。

キーバリューストア方式で分散ストレージを構築

dddのストレージは、「分散キーバリューストア」と呼ぶ構造を持つ。キーバリューストア（key-value store）とは、データを「キー」と「バリュー」の組み合わせで格納するシンプルなデータベースの一種である。それを、複数のノードで分担して管理するのが分散キーバリューストアだ。

キーバリューストアは、従来のRDBに比べて機能が限られる。データの結合機能（JOIN）や、トランザクションの一貫性を保持する機構を持たず、基本的にはキーを指定して対応するバリューを読み書きすることだけが可能だ。

しかし、キーバリューストアは機能が少ない代わりに、スケーラビリティを高めやすいという利点がある。キーの値によってデータを複数のノードに振り分けるという考え方が、分散管理に適しているのである。キーバリューストアが「クラウド時代のデータストア」と言われるのは、このためだ。

dddは、このキーバリューストアを実装。IIJのバックボーン回線を流れる詳細なトラフィック情報や各種サーバーのログなどを、機器IDと時刻をキーにして分散ストレージに格納している。

一方、分散システム環境では日常的なノードの増減を前提として考えなければならない。そこで、キーに応じて担当ノードを振り分ける際のアルゴリズムには、ノードの増減に強い「コンシステントハッシュ法」を採用した。

コンシステントハッシュ法は、ノードやキーをリング上に配置されるものとして考える（図4-5）。ノードのIPアドレスと、キーの値をハッシュ関数に通し、0から2の160乗-1までの数値に変換。それぞれを、リング上の該当する位置に配置する。リングには0から2の160乗-1までの整数の目盛りが振られており、最初と最後はつながっている。各キーの位置から反時計回りに回って最初に遭遇するノードが、そのキーの格納ノードとして処理を担当する。

図4-5　コンシステントハッシュ法と呼ぶアルゴリズムに基づくノードとキーの配置の概念図。ノードが増減した際の影響範囲が限られるという利点がある

このコンシステントハッシュ法に基づくキーの振り分けにより、ノードが増減した場合に影響を受けるキーの範囲を限定できる。例えば、図の中でノードBがダウンした場合、薄い緑色で示す範囲のキーのみが影響を受け、それ以外のキーは影響を受けない。

RAIDを使わぬ冗長化でコストを低減

dddでは、ハードウェアのコストを低く抑えるために、RAIDなどのディスク冗長化技術は採用していない。その代わり、より上位のレベルでデータを冗長化し、どのノードがいつ故障してリング上から脱退しても支障のない仕組みを実現している。

具体的には、冗長化のためにすべてのデータを異なる3つのノードに複製する。先ほど、キーのハッシュ値から反時計回りに回って最初に当たったノードにデータを格納すると述べた。これに加えて、2番めと3番めのノードにも同じデータをコピーするということだ。同時に3台のノードが壊れることはまずないため、データ保全の信頼性は高い。

ノードの1つが壊れるなどして一時的にデータの複製数が2つ以下になることもあり得る。そうした場合は、残ったデータを「ihave／sendme」と呼ぶ仕組みでコピーし、常に複製数を3つに保つようにしている（図4-6）。

図4-6　データを自動的に複製し、冗長化する仕組み

まず、各ノードは自分の持っているキーをリストアップする。次に、そのキーを担当するほかのノードに対してキーのリストを送る。これを、「ihaveメッセージ」と言う。メッセージを送信すべき相手となるノードは、キーの値からハッシュ値を計算するだけで簡単に割り出せる。

ihaveメッセージを受け取ったノードは、リストに含まれているキーと自分の持っているキーを比べ、もし持っていないキーがあればそのデータの送信要求を返す。これを「sendmeメッセージ」と呼ぶ。sendmeメッセージを受け取ったノードは、要求元のノードにデータを送信する。通常、キーの数は大量にあるため、一度に全部のキー情報を交換するのではなく、少しずつ分割してやりとりする。

ノードの数が増減した場合は、その影響を受ける範囲のキーについてのみ、コンシステントハッシュ法で割り出されるihaveメッセージ送信先が変化し、新たに担当となったノードにデータが転送される。例えば、先の図4-5でノードBがなくなった場合、薄い緑色で示される範囲のキーの担当は「ノードB、A、D」から「ノードA、D、C」に変化し、新たに担当となったCにA、Dのいずれかからデータが転送される。dddは延々とこれを繰り返し、結果として若干のリードタイムでデータの複製数を常に3つに保つ。

同じデータをネットワークで接続する複数ノードに分散して保持する分散ストレージ環境においては、データの一貫性にも留意する必要が必要がある。一部のノードが故障したりネットワーク的に分断される可能性があるため、システムの可用性を高めようとすると、そのトレードオフとしてデータの一貫性を保証できなくなる可能性があるからだ。

当社がdddの分散ストレージに格納しているフロー情報やログ情報の内容は不変であり、一度データベースに書き込んだ情報を更新することはない。このため、上記の一貫性が保証されないという特性は、実際にはほとんど問題にならない。

ただし、ノードの増減に伴うデータの複製が発生している瞬間は、「あるはずのノードにデータがない」ということが起こり得る。そうした場合に備えて、アプリケーション側で不整合に対処できる仕組みを用意した。具体的には、あるノードからのデータ取得に失敗した場合、複製データを保持しているはずの2台のノードにリトライする機能を持たせた。

pure P2Pのネットワーク構成で耐障害性を向上

dddの各ノードは、中央管理ホストを持たないpure P2Pのネットワークを構成する。すべてのノードは対等で、それぞれが協調して動作する。中央管理ホストがないので、その部分に障害が起きるとシステム全体が停止してしまう「単一障害点」が存在しない。

各ノードは起動中、ほかのノードと数秒おきにIPアドレスなどの情報を交換している。このため、各ノードはほかのすべてのノードの情報を知っていることになる。新規にノードを追加する場合は、既存のノードの1つに接続して起動する。新規ノードは、接続した既存ノードから他のノードの情報を取得する。同時に、新規ノードの情報はほかの既存のノードに広報されていく。

こうしたpure P2Pのネットワーク構成と、上で述べたストレージ層でのデータ冗長化機能により、ノードが追加や故障で増減してもシステム全体としては問題なく稼働する分散環境を実現した。

以上、dddの概要を述べた。今後は、dddの開発・運用で培った技術を活用し、企業向けのクラウドサービス基盤を提供していく計画である。