(57)【要約】【課題】断片化が不可能なファイルに更新が集中する時の性能を向上させることにある。【解決手段】意味的に分割可能なデータを論理分割装置２４により分割し、分割ユニットを別のノード２に格納させる。これにより、クライアント３からの更新要求がそのユニットに集中した場合でもその更新要求を分割ユニットを格納した各ノード２に分散させることができるので、分散ファイルシステム１の性能の低下を抑制することができる。【選択図】図１
2009259007.tif 000002
【特許請求の範囲】
【請求項１】
それぞれがデータを格納するストレージを備えた複数のノードにデータを分散して格納する分散格納方法であって、
前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割するステップと、
分割された分割データのそれぞれを別々のノードに格納させるステップと、
を有することを特徴とする分散格納方法。
【請求項２】
前記分割するステップは前記データを格納したノードの負荷が高い場合に当該データを分割するものであって、
前記格納させるステップは前記ノードそれぞれの負荷に基づいて前記分割データの格納先ノードを決定することを特徴とする請求項１記載の分散格納方法。
【請求項３】
前記分割データのそれぞれについて、各前記分割データの格納された前記ノードを示す位置情報と各前記分割データのメタ情報とを保持する分割情報蓄積手段から前記メタ情報を読み出し、当該メタ情報を用いてデータに対するアクセスの振り分け先ノードを決定するステップを有することを特徴とする請求項１又は２記載の分散格納方法。
【請求項４】
複数のノードにデータを分散して格納する分散格納システムであって、
前記ノードは、
データを格納するストレージと、
前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割し、分割された分割データのそれぞれを別々のノードに格納させる分割手段と、を有すること
を特徴とする分散格納システム。
【請求項５】
前記ノードそれぞれの負荷情報を管理する負荷分散装置を有し、
前記分割手段は、当該分割手段を有する前記ノードの負荷が高い場合に前記データを分割し、前記負荷分散装置の管理する前記負荷情報に基づいて前記分割データの格納先ノードを決定することを特徴とする請求項４記載の分散格納システム。
【請求項６】
前記分割データのそれぞれについて各分割データの格納された前記ノードを示す位置情報とメタ情報とを保持する分割情報蓄積手段と、
データに対するアクセスを前記分割情報蓄積手段から読み出した前記メタ情報を用いてそのアクセスの振り分け先ノードを決定する分散手段と、
を備えた分割情報管理装置を有することを特徴とする請求項４又は５記載の分散格納システム。
【請求項７】
データを格納するストレージと、
前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割し、分割された分割データを送信する分割手段と、
を有することを特徴とする分散格納装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを複数の計算機に分散して格納する技術に関する。
【背景技術】
【０００２】
分散データ管理機構は、ローカルストレージを持つネットワークに接続された計算機のクラスタの各計算機にデータを分散して格納し、データにアクセスするクライアントには、一つの巨大なストレージを持つデータ管理機構として見せるデータ管理手法である。分散データ管理機構は、データが物理的に異なる複数の計算機に分散配置されているので、複数のクライアントによるＩ／Ｏ要求を複数の計算機で並列に処理することができ、システム全体の応答速度やスループットなどの性能を向上することができる。しかし、多数のクライアントのＩ／Ｏ要求がシステム内の１つの計算機に格納されているデータ群に集中すると、その計算機の性能にシステム全体の性能が制限されてしまう。
【０００３】
この問題を解決すべく、非特許文献１，２では、分散データ管理機構を構成する計算機の負荷を把握し、負荷が高い計算機に格納されているデータ群の一部を負荷が少ない計算機に移動することにより、１つの計算機に集中するＩ／Ｏ要求を分散させる技術が提案されている。これにより１つの計算機に対するＩ／Ｏ要求が複数の計算機に分散されるため、上記問題を解決することができる。
【０００４】
また、非特許文献３には、参照要求が１つの計算機のあるデータに集中する場合は、その負荷を分散させるために、そのデータの複製を他の計算機に生成し、クライアントからの参照要求を分散させてシステム全体の性能を向上させるキャッシュ方式の技術が開示されている。
【０００５】
特許文献１には、１つのファイルを複数の断片に分割し、それぞれを別々の計算機に格納し、Ｉ／Ｏを個別に管理することにより、１つのファイルに対する更新要求による負荷を分散させる技術が開示されている。この技術では、１つのファイルが複数の計算機に分散して格納されているので、１つのファイルに更新が集中しても更新部分が異なる場合、システム全体の性能が低下することがない。
【特許文献１】特許第３４８１３９１号
【非特許文献１】Brighten Godfrey, Karthik Lakshminarayanan, Sonesh Surana, Richard Karp and Ion stoica, "Load Balancing in Dynamic Structured P2P Systems", INFOCOM 2004. Twenty-third AnnalJoint Conference of the IEEE Computer and Communications Societies, 2004, Vol.4, p2253-2262
【非特許文献２】Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels, "Dynamo:Amazon's Highly Available Key-value Store", SOSP'07, 2007, p.205-220
【非特許文献３】Sanjay Ghemawat, Howard Gobioff and Shun-Tak Leung, "The Google File System", SOSP'03, 2003, Vol.37, p.29-43
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献１に記載の技術では、１つのファイルに更新要求が集中し、しかも更新部分が同じ断片の場合、その断片を格納する計算機の性能にシステム全体の性能が制限されてしまうという問題がある。主に数量に関するデータで発生する。以下、２つの例を考える。
【０００７】
クォータは、ユーザ毎に設けられているファイルシステムで利用可能なディスク容量の総量を示す。例えば、１００Ｇバイトのクォータを持つユーザは、全体で１００Ｇバイトまでの情報をファイルシステムに記録可能である。ファイルシステムは、ユーザがファイルを更新する度にクォータに反映させ、クォータが０以下であるかチェックする。クォータが０以下の場合、新たなファイルの作成やデータ書き込みを不可能とする。ユーザは、多数のプロセスを立ち上げることが可能であるので、各プロセスが頻繁にファイルを作成／更新する場合、ユーザのクォータに多数の更新要求が集中する。その為、分散データ管理機構の計算機数に関係なく、更新性能が１つの計算機の性能に制限される。クォータの性質上、記録可能量の制限のチェックが完了しないとファイルの更新ができないため、クォータチェックの性能低下は、ユーザプロセスの更新性能低下に直結する。
【０００８】
別の例としては、人気商品あるいは人気公演のチケットの販売のときの在庫数が考えられる。人気のある商品、チケットをインターネットで販売するとき、一時的に購入が集中する。購入は、在庫数に対する更新であり、その更新が在庫数を格納する計算機に集中するため、システム全体の性能が低下してしまう。在庫数が確認できない状態では販売が行えないので、購入手続の遅れがサービスの質に影響する。
【０００９】
このようなクォータや在庫数などのデータは、非特許文献１，２および特許文献１に記載の技術では複数の断片に分割できないため、そのデータを格納する計算機の性能にシステム全体の性能が制限されてしまう。
【００１０】
非特許文献３に記載のキャッシュ方式では、データを更新する場合、１つしか存在しない元のデータに対して更新を行うので、更新要求は、その元のデータに集中し、キャッシュによる負荷の分散効果を期待できない。また、元のデータと複数の計算機に複製されているキャッシュとを一致させるための同期化が必要であるため、キャッシュ方式における更新は、キャッシュを用いない場合にくらべて性能が低下する。
【００１１】
本発明は、上記に鑑みてなされたものであり、その課題とするところは、分散ファイルシステムにおいて、断片化が不可能なファイルに更新が集中する時の性能を向上させることにある。
【課題を解決するための手段】
【００１２】
第１の本発明に係る分散格納方法は、それぞれがデータを格納するストレージを備えた複数のノードにデータを分散して格納する分散格納方法であって、前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割するステップと、分割された分割データのそれぞれを別々のノードに格納させるステップと、を有することを特徴とする。
【００１３】
本発明にあっては、意味的に分割可能なデータを分割して別々のノードに格納させることにより、断片化が不可能な１つのデータに対して更新要求が集中した場合でも、データそのものを分割して分散配置することで、更新要求を別々のノードに分散させることが可能となり、性能の低下を抑制することができる。ここで意味的に分割可能なデータとは、例えば、人気商品の在庫数など何かの総量を表すものであり、そのデータを分割、融合しても意味が損なわれないデータである。意味が損なわれないとは、例えば、在庫数１００００個を５０００個、５０００個に分割しても、システム全体としての在庫数は変わらず、データにアクセスするクライアント側からみた場合でも意味が変化しないことを言う。
【００１４】
上記分散格納方法において、前記分割するステップは前記データを格納したノードの負荷が高い場合に当該データを分割するものであって、前記格納させるステップは前記ノードそれぞれの負荷に基づいて前記分割データの格納先ノードを決定することを特徴とする。
【００１５】
本発明にあっては、負荷が高いノードのデータを分割し、より負荷の低いノードに分割データを格納することで性能の低下を抑制することが可能となる。
【００１６】
上記分散格納方法において、前記分割データのそれぞれについて、各前記分割データの格納された前記ノードを示す位置情報と各前記分割データのメタ情報とを保持する分割情報蓄積手段から前記メタ情報を読み出し、当該メタ情報を用いてデータに対するアクセスの振り分け先ノードを決定するステップを有することを特徴とする。
【００１７】
本発明にあっては、分割データの位置情報およびその分割データのメタ情報を保持し、そのメタ情報を用いてアクセスを振り分けることにより、分割データの更新をそれぞれの分割データの保持する値に応じて分散させることができる。メタ情報とは、例えば、データを分割したときの分割比率である。
【００１８】
第２の本発明に係る分散格納システムは、複数のノードにデータを分散して格納する分散格納システムであって、前記ノードは、データを格納するストレージと、前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割し、分割された分割データのそれぞれを別々のノードに格納させる分割手段と、を有することを特徴とする。
【００１９】
上記分散格納システムにおいて、前記ノードそれぞれの負荷情報を管理する負荷分散装置を有し、前記分割手段は、当該分割手段を有する前記ノードの負荷が高い場合に前記データを分割し、前記負荷分散装置の管理する前記負荷情報に基づいて前記分割データの格納先ノードを決定することを特徴とする。
【００２０】
上記分散格納システムにおいて、前記分割データのそれぞれについて各分割データの格納された前記ノードを示す位置情報とメタ情報とを保持する分割情報蓄積手段と、データに対するアクセスを前記分割情報蓄積手段から読み出した前記メタ情報を用いてそのアクセスの振り分け先ノードを決定する分散手段と、を備えた分割情報管理装置を有することを特徴とする。
【００２１】
第３の本発明に係る分散格納装置は、データを格納するストレージと、前記データのうち分割しても意味が損なわれない意味的に分割可能なデータを前記ストレージから読み出して分割し、分割された分割データを送信する分割手段と、を有することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、分散ファイルシステムにおいて、断片化が不可能なファイルに更新が集中する時の性能を向上させることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態について図面を用いて説明する。
【００２４】
図１は、本実施の形態における分散ファイルシステムの構成を示すブロック図である。同図に示す分散ファイルシステム１は、ローカルストレージ２６をそれぞれに接続した複数のノード２を備えた分散ファイルシステムであり、従来の分散ファイルシステムでは分割することができなかった意味的に分割可能なデータを格納するファイルを分割して各ノード２に分散配置するものである。意味的に分割可能なデータとは、例えば、利用可能なディスク容量の総量を示すクォータや在庫商品の総数あるいは人気公演のチケットの残りの総数など、分割しても意味が損なわれないデータである。
【００２５】
ノード２は、負荷分散装置２１、位置管理装置２２、Ｉ／Ｏ管理装置２３、論理分割装置２４、分割情報管理装置２５およびローカルストレージ２６を備える。なお、ノード２は、演算処理装置、記憶装置、メモリ等を備えたコンピュータにより構成して、各装置の処理がプログラムによって実行されるものとしてもよい。このプログラムはノード２が備える記憶装置に記憶されており、磁気ディスク、光ディスク、半導体メモリ等の記録媒体に記録することも、ネットワークを通して提供することも可能である。このプログラムは、Ｕｎｉｘ（登録商標）、Ｓｏｌａｒｉｓ（登録商標）、Ｌｉｎｕｘ（登録商標）およびＷｉｎｄｏｗｓ（登録商標）などのオペレーティングシステム上で実行することができる。ローカルストレージ２６を持ち、このプログラムを実行可能な計算機であれば、ＰＣ（パーソナルコンピュータ）、サーバコンピュータに限らず携帯電話などの携帯端末もノード２とすることができる。以下、各装置について説明する。
【００２６】
位置管理装置２２は、ファイルが分散ファイルシステム１のどのノード２に格納されているかを示す位置情報を管理し、クライアント３から問い合わせがあったときに、その位置情報を返す。位置情報は複数のノード２が分散管理しており、専用のルーティングアルゴリズムを用いてファイルの位置情報を持つノード２を検索する。
【００２７】
負荷分散装置２１は、分散ファイルシステム１のノード２の負荷情報、性能情報を管理し、ノード２間の負荷が一定でない場合、負荷分散政策に基づいて負荷が多いノード２のファイルを負荷の少ないノード２へ分散配置させる。
【００２８】
Ｉ／Ｏ管理装置２３は、ローカルストレージ２６を接続し、ファイルの読み書きを行う。
【００２９】
論理分割装置２４は、ノード２の負荷が高いときに、意味的に分割可能なデータの分割を行う。この論理分割装置２４の詳細については後述する。
【００３０】
分割情報管理装置２５は、分割されたデータの位置を管理する。この分割情報管理装置２５の詳細については後述する。
【００３１】
一方、クライアント３は、ネットワーク１０を介して分散ファイルシステム１に対してアクセスする計算機である。分散ファイルシステム１とクライアント３とは、相互通信可能なＴＣＰなどの通信プロトコルを用いて通信を行う。クライアント３は、ＰＣ、サーバコンピュータおよび携帯端末など様々な機器を用いることができる。クライアント３は、いずれかのノード２の位置管理装置２２に対して所望のファイルの位置情報を問い合わせて位置情報を求め、その位置情報を基に所望のファイルが格納されているノード２に接続し、Ｉ／Ｏ管理装置２３を介してファイルにアクセスする。
【００３２】
次に、論理分割装置２４について詳細に説明する。既存の分散ファイルシステムでは、意味的に分割が可能なデータとその他のデータの区別がなく、すべてファイルに記録され、ファイル単位で管理される。ここでは、他のデータを格納したファイルと区別するため、意味的に分割可能なデータを格納したファイルを「ユニット」と称する。また、ユニットを分割して生成された分割ファイルを「分割ユニット」と称する。
【００３３】
図２は、論理分割装置２４の構成を示すブロック図である。論理分割装置２４は、トラフィック解析部２４１と分割部２４２を備える。
【００３４】
トラフィック解析部２４１は、分割に必要な情報と、ユニットへの更新要求の頻度を表すトラフィック情報を管理する。トラフィック解析部２４１は、管理しているユニットのトラフィック情報を基にユニットを分割するか否かの判断をし、分割が必要と判断したとき、分割部２４２にユニットの分割を依頼する。トラフィック情報およびユニットの分割の詳細については後述する。
【００３５】
分割部２４２は、負荷分散装置２１からのノード２の負荷情報と、トラフィック解析部２４１からのトラフィック情報を利用してユニットを分割し、ユニットの分割情報を分割情報管理装置２５に伝える。分割情報管理装置２５に伝えられた分割情報は、クライアント３が分割ユニットにアクセスするために用いられる。
【００３６】
＜ユニットの生成＞
ここで、ユニットの生成について説明する。クライアント３は、格納するデータが分割可能なものであることを知らせるために、ユニット名、フラグ、値、最大分割数、最低要求値、許容応答時間、分割ヒントを含むユニット情報をそのユニットを格納するノード２に伝送する。図３に、クライアント３が伝送するユニット情報を示す。
【００３７】
ユニット名は、ユニットを格納するファイルを論理的に識別するための文字列である。ユニットが分割され複数の分割ユニットになってもユニット名は変更されない。
【００３８】
フラグは、ユニットか一般のファイルかを示す数値である。０は一般のファイルを意味し、１以上はユニットを意味する。論理分割装置２４は、このフラグが１以上の場合にのみ分割を行う。本実施の形態では、フラグが１のときには数値データを表し、フラグが２以上のときにはその他の意味的に分割可能なデータを表す。
【００３９】
値は、ユニットに格納される意味的に分割可能なデータの値である。
【００４０】
最大分割数は、ユニットが分割される最大数を示す。本実施の形態では、２分木の深さの値である。
【００４１】
最低要求値は、分割ユニットが持つ最低限の値である。分割の結果、分割ユニットの値が最低要求値より小さくなるときに分割は実施されない。
【００４２】
許容応答時間は、ユニットに対するＩ／Ｏ要求に期待する最低限の応答時間である。本実施の形態では、許容応答時間よりも平均応答時間が長いときにユニットを分割する。
【００４３】
分割ヒントは、ユニットを分割するための分割方法を示す。本実施の形態では、ｘｍｌのタグを使い分割方法を示す。例えば、数量データの分割ヒントは、〈flag〉１〈/flag〉〈Method〉divide〈/Method〉となる。〈flag〉１〈/flag〉は、このデータが数量ユニットであることを示す。〈Method〉divide〈/Method〉は、分割方法を定義しており、divide は分割したデータの値の合計が元のデータと等しくなることを意味する。
【００４４】
なお、最大分割数、最低要求値および許容応答時間は、クライアント３から受信せず、分散ファイルシステム１内で予め設定しておき、データの種類に応じて選択することも可能である。
【００４５】
図４に示すように、上記のユニット情報を受け取ったノード２は、Ｉ／Ｏ管理装置２３により、論理分割装置２４のトラフィック解析部２４１およびローカルストレージ２６にユニット情報を記録する。
【００４６】
トラフィック解析部２４１は、ユニット毎の分割に必要な情報をユニット表で管理する。ユニット表は、ユニット情報をメモリ上で管理する為の機構であり、ユニット名により各ユニットを識別する。ユニット表は、さまざまな構造で実装可能であるが、本実施の形態においては、ユニット名をキーとする二分探索木により実装した。
【００４７】
トラフィック解析部２４１が保持するユニット情報は、ユニット名、現在分割数、分割構造、最大分割数、最低要求値、許容応答時間、分割ヒントおよびトラフィック情報である。現在分割数は、現在の分割ユニットの数を示す。本実施の形態では、２分木の深さで表すので、ユニット生成時は０である。分割構造は、分割ユニット間の関係を表す２分木の構造である。ユニット生成時は何も記録されない。分割構造の詳細については後述する。トラフィック情報は、ユニットへの更新要求の頻度を表す。トラフィック情報の詳細については後述する。
【００４８】
論理分割装置２４がトラフィック解析部２４１のユニット表にユニット情報を記録した後に、ローカルストレージ２６にもユニット情報が記録される。ローカルストレージ２６には、クライアント３から受信したユニット情報に加えて現在分割数および分割構造が記憶される。
【００４９】
＜トラフィック情報＞
次に、トラフィック情報について説明する。
【００５０】
トラフィック情報は、ユニットへの更新要求の頻度を表すものであり、ユニットを分割または融合するか否かの判断に用いられる。ユニットが生成された後、クライアント３はそのユニットへのアクセスが可能である。ユニット生成直後は、そのユニットは物理的に１つのファイルに格納されている。ユニットへの更新要求が集中して許容応答時間を保証できないときにユニットは分割される。また、分割ユニットへの更新要求が少ない場合、分割ユニットは１つのユニットに融合される。このように、ユニットは更新要求の頻度に応じて分割／融合される。
【００５１】
図５にトラフィック情報の構成を示す。トラフィック情報は、過負荷度、要求数、累積応答時間、累積変化量、前期平均応答時間、前期平均変化量、大量変化要求数および累積大量変化量で構成される。トラフィック情報は、トラフィック解析部２４１のユニット表においてユニット毎に管理される。
【００５２】
過負荷度は、ユニットに対する更新要求の過負荷の程度を示す値である。整数値で−１０から＋１０までの値をとる。
【００５３】
要求数は、ユニットに対する更新要求の数である。更新要求のたびに１加算される。
【００５４】
累積応答時間は、ユニットに対する全ての更新要求の応答時間を足した値である。
【００５５】
累積変化量は、ユニットに対する全ての更新要求の変化量を足した値である。
【００５６】
前期平均応答時間は、以前のトラフィック解析により算出した応答時間の平均である。
【００５７】
前期平均変化量は、以前のトラフィック解析により算出した変化量の平均である。
【００５８】
大量変化要求数は、ある条件下で前期平均変化量に比べて変化量が３倍以上多い更新要求数である。ユニット作成時で前期平均変化量がない場合０となる。
【００５９】
累積大量変化量は、大量変化要求時の変化量の累積値である。
【００６０】
図６は、トラフィック解析部２４１がトラフィック情報を更新する処理の流れを示すフローチャートである。トラフィック情報は、クライアント３がユニットへの更新要求を出したときに更新される。クライアント３がＩ／Ｏ管理装置２３に対してユニットの更新要求を出すと、Ｉ／Ｏ管理装置２３は、ローカルストレージ２６に格納されたユニットの値を更新する。
【００６１】
そして、トラフィック解析部２４１は、ユニット名、要求到達時刻、応答時刻および変化量を含む更新情報をＩ／Ｏ管理装置２３から受信する（ステップＳ６０１）。要求到達時刻は、クライアント３からの更新要求がＩ／Ｏ管理装置２３に到着した時刻である。応答時刻は、クライアント３からの更新要求をＩ／Ｏ管理装置２３が処理してクライアント３に応答した時刻である。これらの時刻は、ノード２のシステム時間を利用する。変化量は、一回の更新要求でユニットの値が変化した量である。例えば、数量データの場合、ユニットの値が５から２に変化したときの変化量は３である。数量データ以外のその他のデータの場合では更新されたバイト数である。
【００６２】
トラフィック解析部２４１は、受信したユニット名と同じユニット名を持つユニット情報をユニット表から検索する（ステップＳ６０２）。該当するユニット名がない場合は処理を終了する。
【００６３】
トラフィック解析部２４１は、ユニット情報を検索した後、そのユニット情報のトラフィック情報を更新する（ステップＳ６０３）。具体的には、トラフィック情報の要求数を１増加させる。応答時刻から要求到達時刻を引いた応答時間をトラフィック情報の累積応答時間に加算する。トラフィック情報の累積変化量に変化量を加算する。このようにトラフィック情報の更新を行う。この後、応答時間が許容範囲を超えるか否か判断し、その可能性がある場合は、トラフィック情報の中の別の項目も更新する。
【００６４】
まず、応答時間が許容応答時間のＡ％（例えば、Ａ＝９０、この値は変更可能である）以上であるか否か調べる（ステップＳ６０４）。応答時間が許容応答時間のＡ％より短い場合は、トラフィックが許容範囲内であると判断して処理を終了する。
【００６５】
変化量が前期平均変化量のＢ倍（例えば、Ｂ＝３、Ｂは任意に設定する）以上であるか調べる（ステップＳ６０５）。変化量がＢ倍内であれば処理を終了する。変化量がＢ倍以上の場合、大量トラフィック情報の更新を行う（ステップＳ６０６）。具体的には、大量変化要求数を１増加させ、要求数を１減少させる。累積大量変化数に変化量を加算し、累積変化数から変化量を減算する。このようにトラフィック情報は更新される。
【００６６】
＜ユニット分割／融合の判断＞
次に、ユニット分割／融合の判断処理について説明する。
【００６７】
トラフィック解析部２４１は、一定時間毎にユニットの分割／融合の判断を行う。図７は、トラフィック解析部２４１によるユニット分割／融合の判断過程を示すフローチャートである。以下、図７を用いてユニットの分割／融合の処理の流れについて説明する。
【００６８】
まず、トラフィック解析部２４１は、トラフィック情報の初期化を行う（ステップＳ７０１）。具体的には、累積応答時間を要求数で割り、前期平均応答時間に記録する。累積変化量を要求数で割り、前期平均変化量に記録する。要求数、累積応答時間、累積変化量を０にする。過負荷度、大量変化要求数および大量要求数はそのままの値にしておく。
【００６９】
続いて、一定時間（例えば、１秒間）待機する（ステップＳ７０２）。待機中に上記で述べたトラフィック情報の更新が行われる。
【００７０】
そして、待機中に蓄積されたトラフィック情報に基づいてユニットの分割判断を行う。まず、累積応答時間を要求数で割り、平均応答時間を算出し（ステップＳ７０３）、平均応答時間が許容応答時間以上か否かを調べる（ステップＳ７０４）。
【００７１】
平均応答時間が許容応答時間以上の場合、過負荷度に過負荷度変化量を加算する（ステップＳ７０５）。過負荷度変化量は、過負荷度変化量＝（（（（平均応答時間−許容応答時間）／許容応答時間）×１０）＋ａ）、ａ＝（（要求数−Ｆ）／Ｆ）により計算する。本実施の形態では、Ｆ＝５０×待機時間（１秒）を用いる。
【００７２】
過負荷度変化量を加えた過負荷度が１０以上となった場合（ステップＳ７０６）、ユニット分割を行う（ステップＳ７２０）。過負荷度が１０より小さい場合は、待機状態（ステップＳ７０２）に戻る。
【００７３】
平均応答時間が許容応答時間内の場合は（ステップＳ７０４）、ユニットを融合するか否かの判断を行う。まず、ユニットの値がすぐに０になるか否か調べる（ステップＳ７０７）。値が０になったユニットに対する更新要求は失敗する確率が高いので、０になる前にユニットを融合しておく。本実施の形態では、（ユニットの値−（累積変化量×Ｃ））、（Ｃ＝３）の結果で判断する。この値が０以下ならばユニットを融合させる（ステップＳ７３０）。
【００７４】
まだユニットの値に余裕がある場合、平均応答時間が許容応答時間のＤ％（Ｄは任意）以上であるか否か調べる（ステップＳ７０８）。平均応答時間が許容応答時間のＤ％以上の場合は、待機状態（ステップＳ７０２）に戻る。
【００７５】
平均応答時間が許容応答時間のＤ％より小さい場合、つまり処理に余裕がある場合は、過負荷度を１減少させ（ステップＳ７０９）、過負荷度が−１０以下となった場合（ステップＳ７１０）、ユニットを融合する（ステップＳ７３０）。
【００７６】
このように、トラフィック解析部２４１は、トラフィック情報に基づいてユニットの分割／融合の判断を行う。
【００７７】
＜ユニット分割＞
次に、ユニット分割について説明する。ユニット分割は、論理分割装置２４の分割部２４２がトラフィック解析部２４１からの要請により行う。
【００７８】
図８は、ユニット分割を説明するための説明図である。分割部２４２は、ローカルストレージ２６およびトラフィック解析部２４１のユニット表から、値、分割構造、分割ヒントなどを読み込み、値を分割する。図８では、値を値１と値２に分割している。このとき、現在分割数を１増加させ、分割構造を更新する。図８では、分割構造が新たに分割構造２となっている。その他のユニット情報は、分割前と分割後に変化はない。また、分割した２つの分割ユニットの内容は値を除いて同じである。
【００７９】
一方の分割ユニット（図８では値１のもの）は、トラフィック解析部２４１のユニット表及びＩ／Ｏ管理装置２３を介してローカルストレージ２６に書き込まれる。他方の分割ユニット（図８では値２のもの）は、２相コミットなどのトランザクション管理方式を用いて、負荷分散装置２１により負荷の低い別のノード２に安全に伝送される。
【００８０】
また、ユニット名、分割識別および分割差分などの情報は、分割したユニットを生成した元のノード２に伝送される。分割識別は、分割あるいは融合を示す値であり、０は融合を示し、１は分割を示す。分割差分は、分割により変更した分割構造である。元のノード２の分割情報管理装置２５は、これらの情報を受信し、分割情報管理装置２５が管理するユニットの分割表を更新する。分割情報管理装置２５の詳細については後述する。
【００８１】
続いて、ユニットの値の分割比率の決定方法について説明する。分割部２４２は、ローカルストレージ２６から値を、トラフィック解析部２４１のユニット表からユニット情報を読み込んだ後、分割比率を決定する。
【００８２】
図９は、分割部２４２が分割比率を決定する過程を示すフローチャートである。
【００８３】
現在分割数が最大分割数以上の場合（ステップＳ９０１）、これ以上分割はしない（ステップＳ９２０）。
【００８４】
現在分割数が最大分割数より小さいときは、分割比率を計算する（ステップＳ９０２）。分割比率をＰ１，Ｐ２とすると、Ｐ１，Ｐ２の最小値が０、最大値が１００であり、Ｐ１＋Ｐ２＝１００となるように、分割比率Ｐ１，Ｐ２を決定する。多数の分割比率の決定方法が考えられるが、本実施の形態では、負荷分散装置２１から取得した性能情報を利用する。
【００８５】
性能情報は０から１００の値をとるものとする。負荷分散装置２１から性能情報に基づいて、分割するユニットのユニット名と同一のユニットを持たないノード２のうち、負荷が一番小さいノード２を分割ユニットの配置先とする。配置先が決定したら、Ｐ２＝（配置先ノードの性能情報／（現在ノードの性能情報＋配置先ノードの性能情報））×１００により配置先の分割比率Ｐ２を決定する。分割比率Ｐ１＝１００−Ｐ２となる。
【００８６】
ユニットの値を分割比率Ｐ１，Ｐ２に基づいて計算する。現在ノード２のユニットの値１は、値１＝値×（Ｐ１／（Ｐ１＋Ｐ２））で、配置先ノード２のユニットの値２は、値２＝値×（Ｐ２／（Ｐ１＋Ｐ２））により計算する。計算した値１，値２のどちらかが最低要求値よりも小さい場合（ステップＳ９０３）、分割はおこなわない（ステップＳ９２０）。値１，値２のいずれも最低要求値より大きい場合は（ステップＳ９０３）、分割を行う（ステップＳ９１０）。
【００８７】
＜分割構造＞
次に、分割構造について説明する。図１０に示すように、分割構造は、分割情報の集合で表現される。分割が行われる度に、分割構造に分割情報が追加される。分割した分割ユニットそれぞれは同じ分割構造を持つ。
【００８８】
分割情報は、ユニットがどのように分割されて分割ユニットになったのかを示す木構造である。分割情報は、分割前のユニットの位置情報、参照度と、分割後の２つの分割ユニットの位置情報、参照度とを木構造で表したものである。位置情報は、そのユニットが格納されているノード２を示す。参照度は、生成時のユニットの参照度を１００として、分割の度に、分割割合に応じて分割前のユニットの参照度を分けたものである。参照度は、クライアント３がアクセスするノード２を決定する際に用いられる。クライアント３からのアクセスの詳細については後述する。
【００８９】
図１１は、file0 のユニットを分割して file0_01 と file0_02 の２つの分割ユニットに分割したときの分割情報を表している。file0, file0_01, file0_02 それぞれの参照度をＲ，Ｒ１，Ｒ２とし、file0_01, file0_02 の分割比率をＰ１，Ｐ２とした場合、参照度Ｒ１，Ｒ２は、Ｒ１＝Ｒ×（Ｐ１／（Ｐ１＋Ｐ２））、Ｒ２＝Ｒ×（Ｐ２／（Ｐ１＋Ｐ２））で計算される。
【００９０】
続いて、図１２乃至１４を用いて、分割構造の変化の過程について説明する。
【００９１】
まず、file0 のユニットを分割して file0_01 と file0_02 の２つに分割した場合、図１２（ａ）に示すように、file0 を file0_01 と file0_02 に分割した分割情報１が分割構造０に追加される。図１２（ｂ）のリーフは、格納された分割ユニットを示している。また、その上方にその分割ユニットの持つ分割構造を示している。分割ユニット file0_01, file0_02 はそれぞれノード１，３に格納された。それぞれの分割ユニットは同じ分割構造０を保持している。
【００９２】
続いて、file0_01 が file0_01_01, file0_01_02 の２つにさらに分割された場合、file0_01 の保持する分割構造０に分割情報２が追加され、図１３（ａ）に示す分割構造１となる。図１３（ｂ）に示すように、分割後の file0_01_01, file0_01_02 はそれぞれノード１，２に格納された。この分割に関係のない file0_02 の分割構造は、図１２（ａ）で示した分割構造０のままである。
【００９３】
また、file0_02 が file0_02_01, file0_02_02 の２つに分割された場合、file0_02 の保持する分割構造０に分割情報３が追加され、図１４（ａ）に示す分割構造２となる。図１４（ｂ）に示すように、分割後の file0_02_01, file0_02_02 はそれぞれノード３，４に格納された。
【００９４】
このように、ユニットを分割する毎に、分割前のユニットの保持する分割構造に分割情報を追加していく。それぞれの分割ユニットは、元のユニットから自らを作成するための分割情報を保有している。自分と関係ない分割情報は保有していない。例えば、分割構造１を持つ file0_01_01 は、分割情報３を保有していない。
【００９５】
すべての分割ユニットの位置情報と参照度は、ユニットを生成したノード２の分割情報管理装置２５が保有する。この情報を保持する分割情報管理装置２５により、クライアント３からのアクセスをすべての分割ユニットに分散させる。
【００９６】
＜分割情報管理装置＞
次に、分割情報管理装置の詳細について説明する。図１５は、分割情報管理装置２５の構成を示すブロック図である。図１５に示すように、分割情報管理装置２５は、位置管理部２５１とアクセス管理部２５２とを備える。
【００９７】
位置管理部２５１は、ユニットの全ての分割履歴を含む分割構造を管理する分割表を保持する。分割表は、そのノード２に生成されたユニットの分割履歴をメモリ、ローカルストレージ２６で管理するための機構であり、ユニット名を用いて分割履歴を識別する。さまざまな構造で分割表を実装可能であるが、本実施の形態では、ユニット名をキーとする二分探索木で実装した。分割表の保持する分割構造は、トラフィック解析部２４１のユニット表の保持する分割構造と同じであるが、ユニット全ての分割情報が記録される。
【００９８】
ユニットが分割される度に、ユニットを分割したノード２からユニット名、分割識別および分割差分がそのユニットの分割表を管理するノード２に伝送される。位置管理部２５１は、その分割差分を分割構造に追加して分割履歴を更新する。
【００９９】
図１６（ａ）に、分割構造を更新する様子を示す。分割構造が分割情報１，２を保持するときに、分割情報３を保持する分割差分が伝送された場合、分割構造と分割差分とを結合することで分割情報１，２，３を保持する分割構造となる。図１６（ｂ）に、上記分割構造の結合の様子を木構造で示した。
【０１００】
一方、ユニットが融合された場合は、分割構造から分割差分を引くことで分割構造を更新する。図１７（ａ）に、ユニットが融合されたときの分割構造の更新の様子を示す。分割構造が分割情報１，２，３を保持するときに、分割情報３を保持する分割差分が伝送された場合、分割構造から分割差分を引くことで、分割構造１，２を保持する分割構造となる。図１７（ｂ）に、上記分割構造を更新する様子を木構造で示した。
【０１０１】
ユニットが分割されたのか、あるいは、融合されたのかは、分割識別の値により判別する。分割のときは分割識別の値が０であり、融合のときは分割識別の値が１である。
【０１０２】
＜ユニット融合＞
ここまでユニットの分割に関して説明した。次は、ユニットの融合について説明する。分割部２４２がユニットの融合を行う。
【０１０３】
図１８は、ユニット融合の要請を受けた後の分割部２４２の融合可能であるか否かを判断する処理の流れである。
【０１０４】
トラフィック解析部２４１からユニット融合の要請を受けた分割部２４２は、融合対象の分割ユニットと同じ分割で生成された分割ユニットの位置情報を分割構造から探し出し、それら融合対象の分割ユニットがさらに分割されていないか調べる（ステップＳ１８０１）。
【０１０５】
融合対象の分割ユニットか分割されていない場合は、ユニットの融合を開始する（ステップＳ１８１０）。融合対象の分割ユニットが分割されていた場合は、融合しない（ステップＳ１８２０）。
【０１０６】
ユニットの融合は、融合対象の分割ユニットを、分割前のユニットがあったノード２に２相コミットのような既存の分散トランザクション機構を利用して安全に伝送する。伝送が成功したらユニット表およびローカルストレージ２６からその分割ユニットを削除する。
【０１０７】
分割ユニットを受け取ったノード２は、いずれかの分割ユニットから分割情報を複製し、分割ユニットそれぞれの値を加算したものを新たな値とし、現在分割数を１減少させ、分割構造を更新する。分割構造の更新は、分割構造から融合対象の分割ユニットを生成した分割情報を削除することにより行う。そして、融合したユニットの情報をユニット表およびローカルストレージ２６に書き込む。さらに、ユニットの位置情報を管理するノード２にユニット名、分割識別、分割差分を伝える。分割識別の値は１であり、分割差分は削除した分割情報である。このように分割ユニットを融合する。
【０１０８】
＜アクセス要求＞
次に、クライアントからのアクセスを各分割ユニットに分散させる仕組みについて説明する。本分散ファイルシステム１は、クライアント３からのアクセスとして、分割された分割ユニットの１つの対する参照／更新、および、全体への参照／更新を提供する。ユニットが数値データの場合、更新は、値の加算／減算のみとする。１つの分割ユニットに対する参照／更新の成功判断は、既存の分散ファイルシステムの参照／更新の成功判断と同じである。
【０１０９】
まず、１つの分割ユニットに対する参照／更新について説明する。クライアント３は、任意のノード２の位置管理装置２２に対して、アクセスしようとするユニットの位置を管理しているノード２の位置情報を問い合わせる。位置管理装置２２は、ルーティングアルゴリズムを用いて該当ユニットの位置を管理するノード２を探し出す。
【０１１０】
続いて、検索されたノード２の分割情報管理装置２５のアクセス管理部２５２は、位置管理部２５１の分割表からユニット名を用いて分割情報を検索する。分割情報が無い場合は、そのユニットは分割されていないので、ノード２自身が管理するユニットの位置をクライアント３に返す。アクセス管理部２５２は、分割情報のそれぞれから分割ユニット毎の参照度を読み出し、その参照度を利用してクライアント３がアクセスする分割ユニットを決定する。
【０１１１】
図１９は、アクセス管理部２５２が参照度を利用してアクセスされる分割ユニットを決定する様子を説明するための図である。図１９にはユニットが分割された様子を示す分割構造が示されている。ユニット file0 は、４つの分割ユニット file0_01_01, file0_01_02, file0_02_01, file0_02_02 に分割されている。分割ユニットそれぞれの参照度は、２０，３０，４０，１０である。アクセス管理部２５２は、０から１００までの論理的空間を分割ユニットの参照度に応じて割り当てる。割り当てが終了したら、アクセス管理部２５２は、０から９９の値の数字の中で１つをランダムに選び、そのランダム値を内包する論理的空間に対応する分割ユニットを選択する。選択された分割ユニットをクライアント３がアクセスする分割ユニットとし、クライアント３に分割ユニットの位置を伝える。参照度は、分割ユニットが持つ値のユニット生成時の値に対する比率であり、このように参照度に応じて分割ユニットを選択することにより各分割ユニットの値が０に近づく時期が近くすることができる。
【０１１２】
図２０は、クライアント３がノード２にアクセスする処理の流れを示すフローチャートである。クライアント３は、伝えられた分割ユニットの位置情報を利用してノード２に参照／更新の要求を出す（ステップＳ２００１）。参照／更新が成功した場合（ステップＳ２００２）、成功として処理を終了する。参照／更新が失敗した場合で（ステップＳ２００２）、分割ユニットを持つすべてのノード２に要求を出していたときは（ステップＳ２００３）、失敗として処理を終了する。まだ要求を出していないノード２があるときは（ステップＳ２００３）、再度、そのノード２に対して参照／更新の要求を出す（ステップＳ２００１）。
【０１１３】
続いて、分割ユニット全体に対する参照要求について説明する。図２１は、クライアント３が分割ユニット全体に対する参照を要求したときの処理の流れを示すフローチャートである。
【０１１４】
まず、まだ参照していないノード２を決定し、データの参照要求を出す（ステップＳ２１０１）。
【０１１５】
そのノード２に対して参照要求が失敗した場合は（ステップＳ２１０２）、失敗として処理を終了する。参照要求が成功した場合は（ステップＳ２１０２）、読み込んだデータの値を加算する（ステップＳ２１０３）。
【０１１６】
分割ユニットを持つすべてのノード２に対して参照要求を出し終えたときは（ステップＳ２１０４）、加算して得られた値を返す。まだノード２が残っている場合は、そのノード２に対して参照要求を出す（ステップＳ２１０１）。
【０１１７】
続いて、分割ユニット全体に対する更新要求について説明する。図２２は、クライアント３が分割ユニット全体に対する更新を要求したときの処理の流れを示すフローチャートである。
【０１１８】
まず、まだ更新していないノード２を決定し、データの更新要求を出す（ステップＳ２２０１）。ここで、分割ユニット毎に更新要求する値は、（クライアントが更新を要求した値）×（分割ユニットの参照度／１００）とする。
【０１１９】
そのノード２に対して更新要求が失敗した場合は（ステップＳ２２０２）、失敗した量とノード２を記録し（ステップＳ２２０４）、次のノード２を決定する（ステップＳ２２０１）。
【０１２０】
更新要求が成功した場合であって（ステップＳ２２０２）、分割ユニットを持つすべてのノード２に対して更新要求を出し終えたときは（ステップＳ２２０３）、成功した量と失敗したノード２を返して処理を終了する（ステップＳ２２１０）。まだ、分割ユニットを持つすべてのノード２に対して更新要求を出していないときは（ステップＳ２２０３）、次のノード２を選択して更新要求を出す（ステップＳ２２０１）。
【０１２１】
＜別の形態の分散ファイルシステム＞
図２３は、本実施の形態における別の分散ファイルシステムの構成を示すブロック図である。図２３に示す分散ファイルシステムは、各ノード２が負荷分散装置２１、位置管理装置２２を備えず、ネームサーバ４が負荷分散装置２１、位置管理装置２２を備えた点で図１に示した分散ファイルシステムと異なる。このような形態の分散ファイルシステムにおいても上記で説明したように意味的に分割可能なデータを格納するファイルを分割して各ノード２に分散配置することが可能である。なお、分割情報管理装置２５を各ノード２ではなく、ネームサーバ４に備えてもよい。
【０１２２】
以上説明したように、本実施の形態によれば、ユニットを論理分割装置２４により分割し、分割ユニットを別のノード２に格納させることにより、クライアント３からの更新要求がそのユニットに集中した場合でもその更新要求を分割ユニットを格納した各ノード２に分散させることができるので、分散ファイルシステム１の性能の低下を抑制することができる。
【０１２３】
本実施の形態によれば、すべての分割ユニットの位置情報、参照値を分割情報管理装置２５が保持することにより、クライアント３からの更新要求をその参照値に応じて分散させることができる。
【図面の簡単な説明】
【０１２４】
【図１】一実施の形態における分散ファイルシステムの構成を示すブロック図である。
【図２】上記分散ファイルシステムにおける論理分割装置の構成を示すブロック図である。
【図３】ユニット情報を示す図である。
【図４】ユニットを生成する様子を示す説明図である。
【図５】トラフィック情報を示す図である。
【図６】トラフィック情報を更新する処理の流れを示すフローチャートである。
【図７】ユニット分割／融合を判断する処理の流れを示すフローチャートである。
【図８】ユニットを分割する様子を示す説明図である。
【図９】分割比率を決定する処理の流れを示すフローチャートである。
【図１０】分割構造を示す図である。
【図１１】分割情報を示す図である。
【図１２】ユニットを分割したときの分割情報、分割構造を示す図である。
【図１３】上記ユニットの分割ユニットを分割したときの分割情報、分割構造を示す図である。
【図１４】上記ユニットの別の分割ユニットを分割したときの分割情報、分割構造を示す図である。
【図１５】分割情報管理装置の構成を示すブロック図である。
【図１６】上記分割情報管理装置が分割構造を更新する様子を示す説明図である。
【図１７】上記分割情報管理装置が分割構造を更新する別の様子を示す説明図である。
【図１８】ユニットが融合可能であるか否かを判断する処理の流れを示すフローチャートである。
【図１９】分割情報管理装置のアクセス管理部が参照度を用いて更新要求を分散させる様子を示す説明図である。
【図２０】クライアントがノードにアクセスする処理の流れを示すフローチャートである。
【図２１】クライアントが分散ユニット全体に対する参照要求を出したときの処理の流れを示すフローチャートである。
【図２２】クライアントが分散ユニット全体に対する更新要求を出したときの処理の流れを示すフローチャートである。
【図２３】一実施の形態における別の分散ファイルシステムの構成を示すブロック図である。
【符号の説明】
【０１２５】
１…分散ファイルシステム
２…ノード
３…クライアント
４…ネームサーバ
１０…ネットワーク
２１…負荷分散装置
２２…位置管理装置
２３…管理装置
２４…論理分割装置
２５…分割情報管理装置
２６…ローカルストレージ
２４１…トラフィック解析部
２４２…分割部
２５１…位置管理部
２５２…アクセス管理部
【図１】
2009259007.tif 000003
【図２】
2009259007.tif 000004
【図３】
2009259007.tif 000005
【図４】
2009259007.tif 000006
【図５】
2009259007.tif 000007
【図６】
2009259007.tif 000008
【図７】
2009259007.tif 000009
【図８】
2009259007.tif 000010
【図９】
2009259007.tif 000011
【図１０】
2009259007.tif 000012
【図１１】
2009259007.tif 000013
【図１２】
2009259007.tif 000014
【図１３】
2009259007.tif 000015
【図１４】
2009259007.tif 000016
【図１５】
2009259007.tif 000017
【図１６】
2009259007.tif 000018
【図１７】
2009259007.tif 000019
【図１８】
2009259007.tif 000020
【図１９】
2009259007.tif 000021
【図２０】
2009259007.tif 000022
【図２１】
2009259007.tif 000023
【図２２】
2009259007.tif 000024
【図２３】
2009259007.tif 000025