(57)【要約】【課題】  集中管理型分散ファイルシステムで起きていたデータ位置情報管理サーバのボトルネックを解消し、また、自律型分散ファイルシステムで使用用途に特化した効率化を図る。【解決手段】  本発明は、クライアント端末から分散ストレージシステム上のいずれかのデータ位置情報管理サーバＡにファイルのパス名とデータの書き込み、または、読み出しのリクエストを送信し、リクエストを受信したサーバＡは、パス名に基づいて、データ位置情報探索のための分散ハッシュテーブルを参照して、該パス名に対応する他のデータ位置情報管理サーバＢを検索し、該サーバＢにリクエストを転送し、サーバＢは、実データを保存するサーバＣの位置情報を特定し、該サーバＣの位置情報を該クライアント端末に送信し、クライアント端末は、サーバＣにアクセスし、実データの書き込みまたは読み出しを行う。【選択図】  図１
2010271797.tif 000002
【特許請求の範囲】
【請求項１】
分散ストレージシステムにおけるデータ位置管理方法であって、
クライアント端末は、前記分散ストレージシステム上のいずれかのデータ位置情報管理サーバに、ファイルのパス名とデータの書き込み、または、読み出しのリクエストを送信し、
前記クライアント端末から前記リクエストを受信したデータ位置情報管理サーバＡは、前記パス名に基づいて、データ位置情報探索のための構造化オーバレイネットワークの情報である分散ハッシュテーブルを参照して、該パス名に対応する他のデータ位置情報管理サーバＢを検索し、該サーバに前記リクエストを送信し、
前記データ位置情報管理サーバＢは、ランダムに実データを保存するサーバを決定し、該サーバの位置情報を該クライアント端末に送信し、
前記クライアント端末は、前記実データを保存するサーバの位置情報に対応するサーバにアクセスし、実データの書き込みまたは読み出しを行う
ことを特徴とする分散ストレージシステムにおけるデータ位置管理方法。
【請求項２】
前記実データを保存するサーバの位置情報を特定したデータ位置情報管理サーバＢは、該実データを保存するサーバの位置情報を、自装置及び、前記分散ハッシュテーブルのChordリングの両端のサーバの記憶手段に格納する
請求項１記載の分散ストレージシステムにおけるデータ位置管理方法。
【請求項３】
前記クライアント端末から前記実データを受信したサーバは、前記実データを適切なブロックサイズのブロックに分割し、個々のブロックに対して排他的論理和を計算して得られたパリティデータを、他のサーバに転送し、保存させる
請求項１または２に記載の分散ストレージシステムにおけるデータ位置管理方法。
【請求項４】
分散ストレージシステムにおけるサーバ装置であって、
実データを保存するサーバの位置情報を特定するための分散ハッシュテーブルと、
クライアント端末から、保存する実データのパス名、及び、データの書き込み、または、読み出しのリクエストを受信し、該パス名に基づいて、前記分散ハッシュテーブルを参照して、該パス名に対応する他のデータ位置情報管理サーバを検索し、該リクエストを転送するサーバ探索手段と、
自装置が前記パス名に対応するサーバである場合は、実データを保持するサーバをランダムに選択し、選択したサーバの位置情報を前記クライアント端末に送信する位置情報通知手段と、
を有することを特徴とする分散ストレージシステムにおけるサーバ装置。
【請求項５】
前記実データを保存するサーバの位置情報を特定した場合に、該実データを保存するサーバの位置情報を、自装置及び、前記分散ハッシュテーブルのChordリングの両端のサーバの記憶手段に格納する手段を含む
請求項４記載の分散ストレージシステムにおけるサーバ装置。
【請求項６】
前記クライアント端末から実データを取得すると、該実データを適切なサイズのブロックに分割し、個々のブロックに対して排他的論理和を計算して得られたパリティデータを、他のサーバに保存する手段を含む
請求項４または、５記載の分散ストレージシステムにおけるデータ位置情報管理サーバ装置。
【請求項７】
請求項４乃至６のいずれか１項に記載のサーバを構成する各手段としてコンピュータを機能させるための分散ストレージシステムにおけるデータ位置管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ストレージにおけるデータ位置管理方法及び装置及びプログラムに係り、特に、複数のディスクを用いて仮想的なひとつのストレージを提供する分散ストレージシステムにおいて、負荷分散や高性能化を実現するための分散ストレージにおけるデータ位置管理方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
分散ストレージシステムとして、データ位置情報管理サーバが実データ管理サーバから切り分けて構成された分散ストレージシステムの実装方法がある。例えば、分散ファイルシステムLustreでは、図７に示すように、データの位置情報を特定のサーバで管理する構成をとっている。以下、このような構成のシステムを「集中管理型分散ストレージシステム」と呼ぶ。同図に示すシステムでは、ユーザ端末からデータ位置情報管理サーバに対してデータの位置情報を問い合わせ（１）、データ保存サーバの位置情報を取得すると、ユーザ端末とデータ保存サーバ間でデータの読み書きを行う（２）（例えば、非特許文献１参照）。
【０００３】
また、構造化オーバレイネットワークの一種である分散ハッシュテーブルを実現するアルゴリズムを用いることにより、専用のサーバを用いることなく、高速にコンテンツの検索、ルーティングを行う技術がある。データの位置情報を特定のサーバで管理せずに、多数のサーバ間で自律的に管理する方法として、Chordやスキップネットなどの構造化オーバレイネットワークを用いる方法がある。構造化オーバレイネットワークを用いたアプリケーションの例として、図８に示すGnutellaなどのアプリケーションがある。以下このような構成のシステムを「自律型分散ストレージシステム」と呼ぶ。同図に示す自律型分散ストレージシステムでは、ユーザ端末からクラスタ中の任意のデータ保存サーバにアクセスすると（１）、データ保存サーバは、データの保存先を探索し（２）、保存先のデータ保存サーバとユーザ端末の間でデータの読み書きを行う（３）（例えば、非特許文献２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】P. Schwan. Lustre:  Building a file system for 1000-node clusters.  In Proceedings of the 2003 Linux symposium, 2003.
【非特許文献２】I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord:A Scalable peer-to-peer lookup service for internet applications.  SIGCOMM Computer Communication Review, 31(4): 149-160, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の集中管理型分散ストレージシステムでは、大量のファイルにアクセスする時に、データ位置を管理しているサーバに負荷が集中してしまうため、データ位置情報管理サーバがシステム全体の性能のボトルネックになってしまう。そのため、例えば、データの位置情報を頻繁に問い合わせることが起こりうる用途ではシステムの大きさがある程度以上にスケールしないという問題がある。
【０００６】
また、データ位置情報管理サーバが、障害が発生すると、システム全体が停止してしまう単一障害点になっているという問題がある。
【０００７】
一方、自律型分散ストレージシステムは、構造化オーバレイネットワークの特徴によりシステム台数のスケーラビリティには非常に優れる。しかし、データの保存位置を自由に決めることができないという理由から、使用用途に特化した効率化が困難である。
【０００８】
本発明は、上記の点に鑑みなされたもので、集中管理型分散ファイルシステムで起きていたデータ位置情報管理サーバのボトルネックを解消し、また、自律型分散ファイルシステムで使用用途に特化した効率化を図ることが可能な分散ストレージにおけるデータ位置管理方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
図１は、本発明の原理を説明するための図である。
【００１０】
本発明（請求項１）は、分散ストレージシステムにおけるデータ位置管理方法であって、
クライアント端末は、分散ストレージシステム上のいずれかのデータ位置情報管理サーバに、ファイルのパス名とデータの書き込み、または、読み出しのリクエストを送信し（ステップ１）、
クライアント端末から前記リクエストを受信したデータ位置情報管理サーバＡは、前記パス名に基づいて、データ位置情報探索のための構造化オーバレイネットワークの情報である分散ハッシュテーブルを参照して、該パス名に対応する他のデータ位置情報管理サーバＢを検索し（ステップ２）、該サーバに前記リクエストを送信し（ステップ３）、
データ位置情報管理サーバＢは、実データを保存するサーバを選択し、該サーバの位置情報を特定し（ステップ４）、該サーバの位置情報を該クライアント端末に送信し（ステップ５）、
クライアント端末は、実データ保存するサーバの位置情報に対応するサーバにアクセスし、実データの書き込みまたは読み出しを行う（ステップ６）。
【００１１】
また、本発明（請求項２）は、実データを保存するサーバの位置情報を特定したデータ位置情報管理サーバＢは、該実データを保存するサーバの位置情報を、自装置及び、前記分散ハッシュテーブルのChordリングの両端のサーバの記憶手段に格納する。
【００１２】
また、本発明（請求項３）は、クライアント端末から実データを受信したサーバは、実データを適切なブロックサイズのブロックに分割し、個々のブロックに対して排他的論理和を計算して得られたパリティデータを、他のサーバに転送し、保存させる。
【００１３】
図２は、本発明の原理構成図である。
【００１４】
本発明（請求項４）は、分散ストレージシステムにおけるサーバ装置であって、
実データを保存するサーバの位置情報を特定するための分散ハッシュテーブル２３と、
クライアント端末１０から、保存する実データのパス名、及び、データの書き込み、または、読み出しのリクエストを受信し、該パス名に基づいて、分散ハッシュテーブル２３を参照して、該パス名に対応する他のデータ位置情報管理サーバを検索し、該リクエストを転送するサーバ探索手段２２と、
自装置がパス名に対応するサーバである場合は、実データを保持するサーバを選択し、該サーバの位置情報を前記クライアント端末に送信する位置情報通知手段２４と、を有する。
【００１５】
また、本発明（請求項５）は、実データを保存するサーバの位置情報を特定した場合に、該実データを保存するサーバの位置情報を、自装置及び、分散ハッシュテーブル２３のChordリングの両端のサーバの記憶手段に格納する手段を含む。
【００１６】
また、本発明（請求項６）は、クライアント端末１０から実データを取得すると、該実データを適切なサイズのブロックに分割し、個々のブロックに対して排他的論理和を計算して得られたパリティデータを、他のサーバに保存する手段を含む。
【００１７】
本発明（請求項７）は、請求項４乃至６のいずれか１項に記載のサーバを構成する各手段としてコンピュータを機能させるための分散ストレージシステムにおけるデータ位置管理プログラムである。
【発明の効果】
【００１８】
上記のように本発明によれば、構造化オーバレイネットワークを用いて、データ位置情報管理サーバを分散化することで、集中管理方分散ファイルシステムで起きていたデータ位置情報管理サーバのボトルネックが解消される。そのため、大量のファイルへアクセスする場合においても性能が落ちることがなく、大量のファイルを同時に処理することができるようになるため、特にクライアント台数に対するスケーラビリティに関して優れる。
【００１９】
また、データ位置情報管理サーバの耐障害性が、構造化オーバレイネットワーク技術によって確保されているため、既存の集中管理型分散ストレージシステムにあった単一障害点が解消される。
【００２０】
また、実データは任意の場所に保存することができるため、自律型分散ファイルシステムで問題となっていた使用用途に特化した効率化が困難である問題が解消される。そのため、システム台数のスケーラビリティを保持したままデータ配置のコントロールが可能となる。
【図面の簡単な説明】
【００２１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態における動作の概要を示す図である。
【図４】本発明の一実施の形態におけるノードの構成図である。
【図５】本発明の一実施の形態における動作のシーケンスチャートである。
【図６】本発明の一実施例の実装例である。
【図７】集中管理型分散ファイルシステムの例である。
【図８】自律型分散ファイルシステムの例である。
【発明を実施するための形態】
【００２２】
以下、図面と共に本発明の実施の形態を説明する。
【００２３】
本発明では、システムを拡張するにつれてボトルネックとなり、単一障害点でもあるデータ位置情報管理サーバを分散化するために、スケーラビリティと耐障害性に優れる技術である構造化オーバレイネットワークの技術を取り入れる。一方、スループットやレイテシンが重要である実データに関しては、遅延が大きくなり得る構造化オーバレイネットワークによる管理ではなく、集中管理型の構成をとる。
【００２４】
図３は、本発明の一実施の形態における動作の概要を示す図である。同図に示すシステムは、クライアント端末１０と複数のデータ位置情報管理サーバ２０、複数のデータ保存サーバ３０から構成されている。なお、説明の便宜上、データ位置情報管理サーバ２０とデータ保存サーバ３０を区別して記載しているが、これらのサーバは、同じコンポーネントを有するものである。
【００２５】
クライアント端末１０は、ファイルのパス名から構造化オーバレイネットワークを用いて、対応するデータ位置情報管理サーバ２０を探し、そのサーバ２０に実データの保存場所を問い合わせる。その後得られた結果を元に実データを保存するデータ保存サーバ３０にアクセスし、実データを得る（または、実データを書き込む）。
【００２６】
本発明において、データ位置情報管理サーバ２０は保存するファイル毎に異なり、データ位置情報管理サーバを見つけさえすれば、集中管理型分散ストレージシステムの構成とその後の処理は同一である。また、データ位置管理情報を見つけるという点では、処理の流れは自律型分散ストレージシステムと同一である。このように本発明は両手法の良いところを組み合わせて実現している。
【００２７】
図４は、本発明の一実施の形態におけるノードの構成を示す。
【００２８】
クライアント端末１０は、データ位置情報管理サーバ２０及びデータ保存サーバ３０との間でデータの送受信を行う送受信部１１、ユーザとの間でデータの入出力を行うユーザインタフェース部１２、及び、データ位置情報管理サーバ２０の位置情報（アドレス）をファイルのパス名に対応付けて管理するデータ位置情報管理サーバ情報記憶部１３を有する。
【００２９】
データ位置情報管理サーバ２０は、クライアント端末１０及び他のデータ位置情報管理サーバ２０との間でデータの送受信を行う送受信部２１、クライアント端末１０からのリクエスト情報（ファイルのパス名）に基づいて、構造化オーバレイネットワークの分散マップ構造をなす分散ハッシュテーブルを保持するＤＨＴ(Distributed Hash Table)記憶部２３、ＤＨＴ記憶部２３を参照してデータ位置情報管理サーバを探索するサーバ探索部２２、他のデータ位置情報管理サーバから送信されたクライアント端末１０からリクエストに基づいてデータ保存サーバを決定し、送受信部２１を介してクライアント端末１０に決定したデータ保存サーバの位置情報を保存場所リストとして通知するノード決定部２４を有する。
【００３０】
データ保存サーバ３０は、データ位置情報管理サーバ２０と同様の構成であるが、図４では、クライアント端末１０からデータを受信する送受信部３１と当該データを格納するディスク３２のみを示す。
【００３１】
次に、上記の構成における動作を説明する。
【００３２】
図５は、本発明の一実施の形態における動作のシーケンスチャートである。以下では、クライアント端末１０は書き込みを行うものとして説明する。
【００３３】
ステップ１０１）  クライアント端末１０は、データ位置情報管理サーバ情報記憶部１３からデータ位置情報管理サーバ（サーバＩＤ）を選択して、ユーザインタフェース１２を介してデータとファイルのパス名を入力し、これをリクエストとして送受信部１１から当該データ位置情報管理サーバ２０（ここでは、データ位置情報管理サーバ２０Aとする）に送信する。
【００３４】
ステップ１０２）  データ位置情報管理サーバ２０Aは、送受信部２１を介してリクエストを受信し、サーバ探索部２２がパス名に基づいてDHT記憶部２３から対応するデータ位置情報管理サーバ（サーバＩＤ）を検索し、当該データ位置情報管理サーバ２０（ここでは、データ位置情報管理サーバ２０Bとする）に、クライアント端末１０からのリクエストを転送する。
【００３５】
ステップ１０３）  データ位置情報管理サーバ２０Bのノード決定部２４は、ランダムにデータ保存サーバ３０を決定し、当該データ保存サーバ３０の位置情報をデータ位置情報管理サーバ２０Aに送信する。なお、データ保存サーバ３０の選択方法には種々の既存の方法があるが、どのような選択方法を用いてもよい。本実施の形態では、ファイルのパス名を有するデータ保存サーバの中からランダムに選択するものとする。
【００３６】
ステップ１０４）  データ位置情報管理サーバ２０Ａの送受信部２１は、データ位置情報管理サーバ２０Ｂから取得したデータ保存サーバ３０の位置情報をクライアント端末１０に転送する。
【００３７】
ステップ１０５）  クライアント端末１０は、データ保存サーバ３０の位置情報を取得すると、当該データ保存サーバ３０にデータを送信し、これを取得したデータ保存サーバ３０は、ディスク３２に書き込む。
【００３８】
なお、クライアント端末１０のリクエストが読み出し要求である場合は、ステップ１０５において、データ保存サーバ３０はディスク３２から該当するデータを読み出して、受信部３１を介してクライアント端末１０に送信する。
【実施例】
【００３９】
以下に、上記の実装について説明する。
【００４０】
図６は、本発明の一実施例の実装例である。
【００４１】
クライアント端末１０は、通信プロセス１１、Erlang runtime１２、Linuxカーネル１５を有する。
【００４２】
データ位置情報管理サーバ２０A、２０Bは、制御部２０１、raidパリティ計算部２０２、ブロック送受信部２０３、データ位置情報探索に使用するための分散ハッシュ表を管理するＤＨＴ管理部２０４、ノード割当部２０５、メタデータ変換部２０６、隣接ノードの参加・離脱を監視するノードモニタを有するErlang runtime２０７、Linuxカーネル２０９、EXT3（ファイルシステム）２１０を有する。このうち、以下の説明では、ＤＨＴ管理部２０４、ノード割当部２０５、メタデータ変換部２０６のみを用いるものとする。
【００４３】
データ保存サーバ３０は、データ位置情報管理サーバ２０と同様の構成を有しているが、図６では、受信したデータを適切なブロックサイズに分割するブロック分割部３０１、分割されたブロックからパリティを計算し、他のデータ保存サーバのディスクに保存するraidパリティ計算部３０２、ディスク（ストレージ）３２のみを示す。なお、図６において、ディスク（EXT3(ファイルシステム)）３２Ｂ，３２Ｃ，３２Ｄは、それぞれデータ保存サーバ３０に具備されているものとする。
【００４４】
本実施例は、構造化オーバレイネットワークの実装や対障害機構のためのデータの冗長性確保に次のような特徴を持つ実装である。
【００４５】
・構造化オーバレイネットワークの実装として、分散ハッシュ表のChordアルゴリズムを用いた（ＤＨＴ管理部２０４）。
【００４６】
・データ位置管理情報は、Chordリングの両端のノードに複製を保存することで冗長性を確保した（ノード割当部２０５）。
【００４７】
・実データは４つの異なるデータ保存サーバに保存されるブロックに対して排他的論理和を計算して得られたパリティデータを、更に別のサーバに保存することで冗長性を確保した（raidパリティ計算部３０２）。
【００４８】
・開発言語に関数型言語Erlangを用い、Erlangが提供する機能によってサーバ障害の検出を実現した（Erlang runtime２０７）。
【００４９】
・クライアント端末１０は、ファイル毎にデータ位置情報管理サーバ２０の情報をキャッシュし、LRU(Least Recently Used)でキャッシュを管理する。
【００５０】
・FUSEをクライアント端末１０に実装したことで、Linuxのファイルシステムとして扱うことができる。
【００５１】
図６におけるデータ書き込み処理の流れを説明する。同図内の吹き出し表記の番号は処理順序を示す。
【００５２】
１．クライアント端末１０は、通信プロセス１１を介して保存するデータのパス名をキャッシュされている分散ストレージシステムの１台のデータ位置情報管理サーバ２０Ａに送信する。この時、送信先はどのデータ位置情報管理サーバでも構わない。
【００５３】
２．クライアント端末１０からパス名を受信したデータ位置情報管理サーバ２０Ａは、ＤＨＴ管理部２０４の分散ハッシュ表に基づいてパス名に該当するデータ位置情報管理サーバ２０Ｂを探索し、クライアント端末１０からの書き込み（または、読み出し）要求を転送する。
【００５４】
３．リクエスト情報を受信したデータ位置情報管理サーバ２０Ｂは、ノード割当部２０５において全データ保存サーバからランダムにサーバを特定する。
【００５５】
４．データ位置情報管理サーバ２０Ｂのノード割当部２０５は、選択したデータ保存サーバ３０のデータ位置情報をデータ位置情報管理サーバ２０Ａに通知する。
【００５６】
５．データ位置情報管理サーバ２０Ｂのノード割当部２０５は、データ位置情報を当該サーバ自身と、Chordリングの両端のサーバの３台のディスクに保存する。
【００５７】
６．データ位置情報管理サーバ２０Ａのノード割当部２０５は、クライアント端末１０にデータの保存場所（データ保存サーバ３０Ａ）の保存場所のリストを送信する。
【００５８】
７．クライアント端末１０は、通知された保存場所リスト中の１つのデータ保存サーバ３０Ａに対して実データを送信する。実データを受信したデータ保存サーバ３０Ａは、ブロック分割部３０１で当該データを適切なブロックサイズに分割し、それぞれを各データ保存サーバへ転送し、各サーバのディスク３２Ｂ，３２Ｃ、３２Ｄに保存する。また、データ保存サーバ３０Ａのraidパリティ計算部３０２は、分割された個々のブロックに対して排他的論理和を計算して得られたパリティデータも別のデータ保存サーバのディスク３２Ｂ，３２Ｃ、３２Ｄへ保存する。
【００５９】
８．データ保存サーバ３０Ａは、全データの保存が終了したらクライアント端末１０へ書き込み終了の通知を送る。
【００６０】
なお、上記の図４、図６に示すサーバの構成要素の動作をプログラムとして構築し、分散ストレージシステムにおけるサーバとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６１】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００６２】
なお、本発明は、上記の実施の形態及び実施例に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００６３】
本発明は、分散ストレージシステムのサーバに適用可能である。
【符号の説明】
【００６４】
１０  クライアント端末
１１  送受信部、通信プロセス
１２  ユーザインタフェース部
１３  データ位置情報管理サーバ情報記憶部
１４  Erlang runtime
１５  Linuxカーネル
２０  サーバ装置、データ位置情報管理サーバ
２２  サーバ探索手段、サーバ探索部
２３  分散ハッシュテーブル、ＤＨＴ記憶部
２４  位置情報通知手段、ノード決定部
３０  データ保存サーバ
３１  送受信部
３２  ディスク
２０１  制御部
２０２  raidパリティ計算部
２０３  ブロック送受信部
２０４  ＤＨＴ管理部
２０５  ノード割当部
２０６  メタデータ変換部
２０７  Erlang runtime
２０８  復旧部
２０９  Linuxカーネル
２１０  EXT3（ファイルシステム）
３０１  ブロック分割部
３０２  raidパリティ計算部
【図１】
2010271797.tif 000003
【図２】
2010271797.tif 000004
【図３】
2010271797.tif 000005
【図４】
2010271797.tif 000006
【図５】
2010271797.tif 000007
【図６】
2010271797.tif 000008
【図７】
2010271797.tif 000009
【図８】
2010271797.tif 000010