(57)【要約】【課題】ノードを追加した後に行うデータの再配置に要する時間（性能劣化時間）を短縮する事ができる。【解決手段】配信装置であるノード２００は、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部２０２ａと、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を他の前記配信装置に通知する範囲差分通知部２０２ｂとを備える。【選択図】図２
2016157266.tif 000002
【特許請求の範囲】
【請求項１】
ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する配信装置であって、
新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、
前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を他の前記配信装置に通知する範囲差分通知部とを備える、
ことを特徴とする配信装置。
【請求項２】
前記現行範囲は、前記ハッシュ関数の範囲を各々の前記配信装置で等分割したものである、
ことを特徴とする請求項１に記載の配信装置。
【請求項３】
前記現行範囲に隣接する隣接範囲を担当する前記配信装置から前記範囲差分のデータを取得するデータコピー部をさらに備える、
ことを特徴とする請求項１または請求項２に記載の配信装置。
【請求項４】
前記データコピー部は、リソースに余裕がある場合に前記範囲差分のデータを取得し、リソースに余裕がない場合に前記範囲差分のデータを取得しない
ことを特徴とする請求項３に記載の配信装置。
【請求項５】
ハッシュ関数を用いてデータを複数の配信装置に分散配置することにより、各々の前記配信装置には前記ハッシュ関数の範囲の内で自身が担当する範囲である現行範囲のデータが保有されている分散ファイルシステムに通信可能に接続され、データの再配置を行う再配置装置であって、
新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、
前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知部とを備える、
ことを特徴とする再配置装置。
【請求項６】
ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する各々の配信装置が保有するデータの再配置を行う再配置装置における再配置方法であって、
前記再配置装置は、
新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定ステップと、
前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知ステップと、
を有することを特徴とする再配置方法。
【請求項７】
ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する各々の配信装置が保有するデータの再配置を行うコンピュータを、
新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部、
前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知部、
として機能させるための再配置プログラム。
【請求項８】
ハッシュ関数を用いてデータを複数の配信装置に分散配置することにより、各々の前記配信装置には前記ハッシュ関数の範囲の内で自身が担当する範囲である現行範囲のデータが保有されている分散ファイルシステムであって、
少なくとも何れかの一つの前記配信装置は、
新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、
前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記現行範囲と前記予測範囲との範囲差分を他の前記配信装置に通知する範囲差分通知部とを備え、
各々の前記配信装置は、
前記現行範囲に隣接する隣接範囲を担当する前記配信装置から前記範囲差分のデータを取得するデータコピー部を備える、
ことを特徴とする分散ファイルシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、配信装置、再配置装置、再配置方法、再配置プログラムおよび分散ファイルシステムに関する。
【背景技術】
【０００２】
データを複数のサーバ（ノード）に分散配置する分散ファイルシステムが知られている。この分散ファイルシステムの性能を最大限に発揮させるには、各ノードに配置されているデータ量を均等に保つ必要がある。そこで、新しいノードが追加された場合に、データをノード間で相互にコピーして、各ノードが持つデータ量を均等にする作業（以下、「再配置」と呼ぶ場合がある）を行うのが一般的である。
【０００３】
従来、コンシステント・ハッシュ法を用いた分散ファイルシステムが知られている（非特許文献１参照）。コンシステント・ハッシュ法は、ノードやデータ（キー）をリング上に配置すると考えるものである。例えば、ノードのＩＰアドレスとキーの値をハッシュ関数に通して「０〜２の１６０乗−１」の数値に変換し、「０〜２の１６０乗−１」の整数の目盛りが振られているリング上の該当する位置にそれぞれを配置する。そして、各キーの位置から反時計回りに回って最初に遭遇するノードを、そのキーを格納するノードとして決定するものである。この分散ファイルシステムは、新しいノードが追加された場合に、再配置の影響を受けるデータ（キー）の範囲を限定することができるので、ノードの追加に強い分散ファイルシステムである。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“高い可用性と低コストで確保−分散技術の先端を知る−Ｐａｒｔ４”、[online]、株式会社インプレス、[平成２７年２月１日検索]、インターネット、＜URL:http://it.impressbm.co.jp/articles/-/7037＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１に記載された技術を用いた分散ファイルシステムといえども、再配置は大量のファイルコピーがノード間で発生するため短時間で完了させようとするとファイルシステム全体の性能が著しく劣化する。その為、連続運転が求められるようなシステムでは、ゆっくりと時間をかけて再配置を進める必要があるので、長時間に渡って最大のパフォーマンスを発揮できない状態が続く事になる。
【０００６】
本発明は、前記問題に鑑みてなされたものであり、ノードを追加した後に行うデータの再配置に要する時間（性能劣化時間）を短縮する事ができる、配信装置、再配置装置、再配置方法、再配置プログラムおよび分散ファイルシステムを提供するものである。
【課題を解決するための手段】
【０００７】
前記課題を解決するため、本発明に係る配信装置は、ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する配信装置であって、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を他の前記配信装置に通知する範囲差分通知部とを備える、ことを特徴とする。
前記課題を解決するため、本発明に係る再配置装置は、ハッシュ関数を用いてデータを複数の配信装置に分散配置することにより、各々の前記配信装置には前記ハッシュ関数の範囲の内で自身が担当する範囲である現行範囲のデータが保有されている分散ファイルシステムに通信可能に接続され、データの再配置を行う再配置装置であって、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知部とを備える、ことを特徴とする。
前記課題を解決するため、本発明に係る再配置方法は、ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する各々の配信装置が保有するデータの再配置を行う再配置装置における再配置方法であって、前記再配置装置は、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定ステップと、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知ステップと、を有することを特徴とする。
前記課題を解決するため、本発明に係る再配置プログラムは、ハッシュ関数を用いてデータを分散配置する分散ファイルシステムを構成する各々の配信装置が保有するデータの再配置を行うコンピュータを、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記ハッシュ関数の範囲の内で各々の前記配信装置が担当する範囲である現行範囲と前記予測範囲との範囲差分を各々の前記配信装置に通知する範囲差分通知部、として機能させる、ことを特徴とする。
前記課題を解決するため、本発明に係る分散ファイルシステムは、ハッシュ関数を用いてデータを複数の配信装置に分散配置することにより、各々の前記配信装置には前記ハッシュ関数の範囲の内で自身が担当する範囲である現行範囲のデータが保有されている分散ファイルシステムであって、少なくとも何れかの一つの前記配信装置は、新たな配信装置が追加される前に、当該新たな配信装置の前記ハッシュ関数の範囲上における位置を決定する追加位置決定部と、前記新たな配信装置が追加された場合における前記ハッシュ関数の範囲の内で各々の前記配信装置が担当することになる範囲である予測範囲を算出し、前記現行範囲と前記予測範囲との範囲差分を他の前記配信装置に通知する範囲差分通知部とを備え、各々の前記配信装置は、前記現行範囲に隣接する隣接範囲を担当する前記配信装置から前記範囲差分のデータを取得するデータコピー部を備える、ことを特徴とする。
【発明の効果】
【０００８】
本発明によれば、ノードを追加した後に行うデータの再配置に要する時間（性能劣化時間）を短縮する事ができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態に係る分散ファイルシステムの構成図である。
【図２】実施形態に係る分散ファイルシステムを構成するノードの機能構成図である。
【図３】実施形態に係る分散ファイルシステムで用いるハッシュレンジの例示である。
【図４】各ノードのハッシュレンジ上の初期位置の例示である。
【図５】システム稼働開始処理後の各ノードのハッシュレンジ上の位置の例示である。
【図６】システム稼働処理を説明するための図である。
【図７】実施形態に係る分散ファイルシステムを構成するノードの事前再配置処理の動作を示すフローチャートである。
【図８】事前再配置処理により算出される範囲差分を説明するための図であり、（ａ）はノード追加前のノードＮ1の現行範囲Ｒ1を示し、（ｂ）はノード追加後の予測範囲Ｒ1'を示す。
【図９】事前再配置処理により算出される範囲差分を説明するための図であり、（ａ）はノード追加前のノードＮ2の現行範囲Ｒ2を示し、（ｂ）はノード追加後の予測範囲Ｒ2'を示す。
【図１０】事前再配置処理により算出される範囲差分を説明するための図であり、（ａ）はノード追加前のノードＮ3の現行範囲Ｒ3を示し、（ｂ）はノード追加後の予測範囲Ｒ3'を示す。
【図１１】事前再配置処理により算出される範囲差分を説明するための図であり、（ａ）はノード追加前のノードＮ4の現行範囲Ｒ4を示し、（ｂ）はノード追加後の予測範囲Ｒ4'を示す。
【図１２】変形例に係る分散ファイルシステムの構成図である。
【発明を実施するための形態】
【００１０】
［実施形態の概要］
コンシステント・ハッシュ法を用いた分散ファイルシステムでは、各ノードが担当するハッシュレンジ上の範囲の広さとそのノードに対するアクセス頻度が比例する事になる。よって、分散ファイルシステム全体の性能を最大限に発揮するには、各ノードのハッシュレンジ上の間隔を均等にする必要がある。ここで、システム拡張のため新しいノードを追加しようとするとその均衡が崩れてしまう。よって新しいノードが追加された場合には、各ノードのハッシュレンジ上の間隔が均等になるようにノード位置の調整とそれに伴うデータの再配置が必要となる。
【００１１】
本発明者は、ノードが追加された場合に再配置の影響を受けるデータの範囲を事前に限定できることに着目し、ノードの追加前に追加後の状態を想定してデータの再配置を可能な範囲内で済ませておく分散ファイルシステムを発明するに至った。これにより、ノードを追加した後に行うデータの再配置に要する時間（性能劣化時間）を短縮する事ができる。
【００１２】
以下、本発明の実施するための形態を、適宜図面を参照しながら詳細に説明する。
各図は、本発明を十分に理解できる程度に、概略的に示してあるに過ぎない。よって、本発明は、図示例のみに限定されるものではない。また、本実施形態では、本発明と直接的に関連しない構成や周知な構成については、説明を省略する場合がある。なお、各図において、共通する構成要素や同様な構成要素については、同一の符号を付し、それらの重複する説明を省略する。
【００１３】
≪実施形態に係る分散ファイルシステムの構成≫
図１を参照して、実施形態に係る分散ファイルシステム１の構成について説明する。図１は、実施形態に係る分散ファイルシステム１の構成図である。
分散ファイルシステム１は、データの保存・参照を要求する複数の端末１００と、端末の要求に応えてデータの格納・送信を行う複数のノード２００とからなり、各装置はネットワークＮＷを介して相互に接続されている。端末１００は、例えばＰＣ（Personal Computer）であり、ノード２００は、例えばファイルサーバである。
【００１４】
分散ファイルシステム１は、ここでは、コンシステント・ハッシュ法を用いたものを想定している。その為、全ての端末１００および全てのノード２００は、同一のハッシュ関数Ｈを有している。ハッシュ関数Ｈは、ＭＤ５やＳＨＡアルゴリズムのように決定性と一様性を併せ持つハッシュ関数であればよい。以下では、ハッシュ関数Ｈが出力する値域をハッシュレンジと呼ぶことにする。
【００１５】
各ノード２００は、ハッシュ関数Ｈにより特定されるハッシュレンジ上で担当する範囲が決められており、担当する範囲に含まれるデータの要求に応答する。例えば、端末１００は、データを書き込む際に、ハッシュ関数Ｈを用いて対象データのファイル名のハッシュ値を計算し、計算したハッシュ値をマルチキャストで送信することにより担当するノード２００の問い合わせを行う。それに対して、問い合わせがあったハッシュ値を担当するノード２００は、問い合わせを行った端末１００に対して自身のアドレスを通知する。端末１００は、そのアドレスに対してデータを送信し、担当するノード２００は、データを格納する。
【００１６】
図２にノード２００の構成を示す。ノード２００は、データ送受信部２０１と、事前再配置処理部２０２と、再配置処理部２０３と、データ保持部２０４とを備えて構成されている。データ送受信部２０１、事前再配置処理部２０２および再配置処理部２０３は、例えば、ＣＰＵ（Central Processing Unit）によるプログラム実行処理や、専用回路等により実現される。プログラム実行処理により実現する場合、ノード２００には、データ送受信部２０１、事前再配置処理部２０２および再配置処理部２０３を実現するためのプログラムが格納される。また、データ保持部２０４は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。ここではノード２００の各機能の概要のみ説明し、処理の詳細は後述する。
【００１７】
データ送受信部２０１は、端末１００または自身以外の他のノード２００から自身が担当する範囲のデータの保存要求または参照要求を受け取る。また、データ送受信部２０１は、これらの要求に応じてデータ保存部２０４にデータを保存し、またはデータ保存部２０４から取得したデータの内容を要求元に送信する。
【００１８】
事前再配置処理部２０２は、新たなノード２００が追加された場合を想定して、データの再配置を可能な限りで事前に行う処理部分であり、必要に応じて他のノード２００に対してデータを要求して自身のデータ保持部２０４に保存する。事前再配置処理部２０２は、新たなノード２００のハッシュレンジ上における位置を決定するノード追加位置決定処理部２０２ａを含んでいる。また、事前再配置処理部２０２は、新たなノード２００が追加される前のハッシュレンジ上における担当範囲（現行範囲）と新たなノード２００が追加された後のハッシュレンジ上における担当範囲（予測範囲）との差分（範囲差分）を通知する範囲差分通知部２０２ｂを含んでいる。また、事前再配置処理部２０２は、範囲差分のデータを他のノード２００から取得するデータコピー部２０２ｃを含んでいる。
【００１９】
再配置処理部２０３は、実際に新たなノード２００が追加された場合に、データの再配置を行う処理部分である。事前再配置処理部２０２によって範囲差分のデータを他のノード２００から取得している場合には、再配置処理部２０３によるデータの再配置に要する時間（性能劣化時間）が短縮する。
【００２０】
データ保存部２０４には、ハッシュレンジ上における自身が担当する範囲（現行範囲）のデータが格納されている。この現行範囲のデータは、端末１００からの保存要求をデータ送受信部２０１が処理を行うことによって常時更新される。
また、データ保存部２０４には、範囲差分のデータが格納されている。この範囲差分のデータは、リソースの状態を見計らって事前再配置処理部２０２が処理を行うことによって常時更新される。
【００２１】
≪実施形態に係る分散ファイルシステムの動作≫
以下、実施形態に係る分散ファイルシステム１の動作について説明する。ここで、本実施形態の分散ファイルシステム１で用いるハッシュレンジを図３に示す。図３では、単純化のためハッシュレンジを「０〜３６０」としており、値が小さいものから時計回りに円形に並べている。「３６０」と「０」は同値として扱うものとする。
【００２２】
分散ファイルシステム１の動作は、「システム稼働開始処理」、「システム稼働処理」、「事前再配置処理」および「再配置処理」に大きく分けることができる。
ここで、システム稼働開始処理とは、分散ファイルシステム１が起動してすぐの初期化時の動作である。また、システム稼働処理とは、システム稼働開始処理が完了した後に実行されるものであり、自身が担当する範囲のデータの処理を行う動作である。また、事前再配置処理とは、システム稼働処理と並行して実行されるものであり、新たなノード２００が追加された場合を想定して、データの再配置を可能な限り事前に行う動作である。また、再配置処理とは、実際に新たなノード２００が追加された場合に、データの再配置を行う動作である。
【００２３】
＜システム稼働開始処理（初期化処理）＞
システム稼働開始処理では、ｎ（２以上の整数）台のノード２００に対して個別にハッシュ値（以後「位置」と呼ぶ）を付与し、ハッシュレンジ上の各ノード２００の位置の間隔が均等になるように調整を行う。
【００２４】
最初に、各ノード２００のデータ送受信部２０１は、自身のホスト名をハッシュ関数Ｈでハッシングしたハッシュ値を各ノード２００の位置の初期値として決定する。そして、各ノード２００のデータ送受信部２０１は、自身が決定した各ノード２００の位置の初期値をマルチキャストで他のノード２００に送信し、ノード２００間でこの情報を共有する。なお、同じ値を持つノード２００があった場合は、無作為に選ばれた「０〜３５９」までのランダムな値で決定しても良いものとする。
【００２５】
続いて、位置の初期値の値（ホスト名をハッシュ関数Ｈでハッシングしたハッシュ値）が小さい順に各ノード２００に番号が付与される。ここでは、位置の初期値の値が小さい順に処理上付与された後の各ノード２００を、ノードＮ1，Ｎ2，・・・，Ｎnと表すものとする。例えば、４つのノードＮ1〜Ｎ4の位置の初期値がそれぞれ次に示すものであった場合、各ノードＮ1〜Ｎ4のハッシュレンジ上の位置は図４のように表す事ができる。
Ｎ1の位置（初期値）＝４５
Ｎ2の位置（初期値）＝１００
Ｎ3の位置（初期値）＝２５０
Ｎ4の位置（初期値）＝２８０
【００２６】
次に、ノードＮ1のデータ送受信部２０１は、各ノードＮ1〜Ｎnのハッシュレンジ上の間隔が均等になるように、ノードＮxの位置Ｄxを次の式（１）で決定する。
Ｄx＝Ｄ1＋（ｘ−１）×（３６０／ｎ）  ・・式（１）
【００２７】
これはつまり、ノードＮ1の位置Ｄ1を基準として間隔が均等になるように、他のノードＮ2〜Ｎnの位置Ｄ2〜Ｄnを調整する事を意味している。そして、ノードＮ1のデータ送受信部２０１は、決定した位置Ｄ2〜Ｄnを他のノードＮ2〜Ｎnに通知する。
【００２８】
例えば、図４に示す初期状態に対し、式（１）を適用すると各ノードＮ1〜Ｎnの位置Ｄ1〜Ｄnは次の通りに決定される（図５参照）。
Ｄ1＝４５＋（１−１）×（３６０／４）＝４５
Ｄ2＝４５＋（２−１）×（３６０／４）＝１３５
Ｄ3＝４５＋（３−１）×（３６０／４）＝２２５
Ｄ4＝４５＋（４−１）×（３６０／４）＝３１５
【００２９】
＜システム稼働処理＞
システム稼働処理では、端末１００から自身が担当する範囲のデータの保存要求または参照要求を受け取り、これらの要求に応じてデータ保存部２０４にデータを保存し、またはデータ保存部２０４から取得したデータの内容を要求元に送信する。
ここでは、データのハッシュ値（位置）から反時計回りに回って最初に遭遇するノードＮ1〜Ｎnをそのデータの保存先とする場合を想定する。
【００３０】
例えば、あるデータのハッシュ値が「９０」であった場合、図６に示すように、反時計回りで最初に遭遇するノードＮ1がそのデータの保存先ノードとなる。つまり、特定のノードＮx（ｘ＝１〜ｎ）が保持しなければならないデータは、データのハッシュ値が自身の位置Ｄxから時計回り方向に隣接するノードＮ(x+1)までの間（ただし隣接するノードＮ(x+1)の位置Ｄ(x+1)は含まない）となる。
【００３１】
表記を簡略化するため「位置αから時計回り方向に進んだ位置β未満の間」の範囲を［α，β］と表すものとすると、ノードＮxが保持しなければならないハッシュ値の範囲Ｒxは次の式で表す事ができる。
Ｒx＝［Ｄx，Ｄ(x+1)］  ・・式（２）
【００３２】
ここで、上式（２）に式（１）を適用すると次の式（３）を得る。
Ｒx＝［Ｄ1＋（ｘ−１）×（３６０／ｎ），Ｄ1＋ｘ×（３６０／ｎ）］  ・・式（３）
【００３３】
例えば、図５に示す各ノードが保持しなければならないハッシュ値の範囲Ｒ1〜Ｒ4を式（３）を用いて表すと次のようになる。
Ｒ1＝［４５，１３５］
Ｒ2＝［１３５，２２５］
Ｒ3＝［２２５，３１５］
Ｒ4＝［３１５，４５］
【００３４】
ノードＮ1のデータ送受信部２０１は、以上に説明した各ノードＮ1〜Ｎnの範囲Ｒ1〜Ｒnを計算し、その結果を他のノードＮ2〜Ｎnに通知する。通知を受けた各ノードＮ2〜ＮnとノードＮ1自身は、自ノードが担当する範囲Ｒ1〜Ｒnのデータに対し端末１００からのデータの保存要求と参照要求に応答する。
【００３５】
＜事前再配置処理＞
事前再配置処理では、新しいノードＮ(n+1)が追加された場合を想定して、可能な範囲で再配置を事前に済ませておく処理を行う。
ここで、コンシステント・ハッシュ法を用いた分散ファイルシステム１では、各ノードＮが担当するハッシュレンジ上の範囲の広さとそのノードＮに対するアクセス頻度が比例する事になる。よって、分散ファイルシステム１全体の性能を最大限に発揮するには各ノードＮのハッシュレンジ上の間隔が均等となる必要がある。
【００３６】
前記したシステム稼働処理によりノードＮ1〜Ｎnの間隔を均等にする事はできるが、システム拡張のため新しいノードＮ(n+1)を追加しようとするとその均衡が崩れてしまう。よって新しいノードＮ(n+1)が追加された場合は間隔が均等になるようノードＮ1〜Ｎ(n+1)の位置Ｄ1〜Ｄ(n+1)の調整とそれに伴うデータの再配置が必要となる。従来、データの再配置はノード追加後に実施されるものであるが、本実施形態では追加前に追加後の状態を想定しておき、可能な限り再配置を済ませておく事で追加後の再配置時間を短縮させる。そして、その処理を事前再配置処理で行う。
【００３７】
図７を参照して、事前再配置処理について説明する。図７は、本実施形態におけるノードＮの動作を表すフローチャートである。なお、図７に示す処理は、各ノードＮ1〜Ｎnの事前再配置処理部２０２がそれぞれ行う。
【００３８】
最初に、各ノードＮ1〜Ｎnの事前再配置処理部２０２は、内部変数λを空に初期化する（ステップＳ０１）。なお、この内部変数λは、ノードＮ1から通知されるステップＳ０４で行われる処理（２）の結果（＝範囲差分）を代入する変数である。続いて、各ノードＮ1〜Ｎnの事前再配置処理部２０２は、自身がノードＮ1であるか否かを判定する（ステップＳ０２）。自身がノードＮ1である場合（ステップＳ０２で“Ｙｅｓ”）はステップＳ０３の処理に進み、自身がノードＮ1でない場合（ステップＳ０２で“Ｎｏ”）はステップＳ０５の処理に進む。
【００３９】
ステップＳ０２で自身がノードＮ1である場合（ステップＳ０２で“Ｙｅｓ”）に、ノードＮ1のノード追加位置決定部２０２ａ（図２参照）は、「処理（１）：ノード追加位置決定処理」を実行する（ステップＳ０３）。「処理（１）：ノード追加位置決定処理」は、新しいノードＮ(n+1)が追加された場合を想定して、新しいノードＮ(n+1)の位置を算出する処理である。処理の詳細については後述する。そして、処理をステップＳ０４に進める。
【００４０】
ステップＳ０３に続いて、ノードＮ1の範囲差分通知部２０２ｂ（図２参照）は、「処理（２）：範囲差分通知処理」を実行する（ステップＳ０４）。「処理（２）：範囲差分通知処理」は、新しいノードＮ(n+1)が追加された後に、各ノードＮ1〜Ｎnが新たに範囲としなければならないハッシュ値の範囲Ｒ1'〜Ｒn'を算出し、追加前である現在の範囲Ｒ1〜Ｒnとの差分（範囲差分）を各ノードＮ1〜Ｎnで共有する処理である。処理の詳細については後述する。そして、処理をステップＳ０８に進める。なお、この処理が完了した時点で各ノードＮ1〜Ｎnに範囲差分が通知されるため、ノードＮ1でステップＳ０４の処理（２）が実行された後にノードＮ1以外のノードＮ2〜Ｎnが実行するステップＳ０６の判定結果は「Ｙｅｓ」となる。
【００４１】
ステップＳ０２で自身がノードＮ1でない場合（ステップＳ０２で“Ｎｏ”）に、ノードＮ1以外のノードＮ2〜Ｎnの事前再配置処理部２０２は、内部変数λが空であるか否かを判定する（ステップＳ０５）。この判定は、言い換えると自身が範囲差分のデータを有しておらずに他のノードがそのデータを有している場合のように、事前にコピーしておくべきデータがあるか否かを判定するものである。内部変数λには、ステップＳ０７で値が代入される。内部変数λが空である場合（ステップＳ０５で“Ｙｅｓ”）はステップＳ０６の処理に進み、内部変数λが空でない場合（ステップＳ０５で“Ｎｏ”）はステップＳ０８の処理に進む。
【００４２】
ステップＳ０５で内部変数λが空である場合（ステップＳ０５で“Ｙｅｓ”）に、ノードＮ1以外のノードＮ2〜Ｎnの事前再配置処理部２０２は、ステップＳ０４で算出される処理（２）の結果がノードＮ1から通知されて来ていないかを確認する（ステップＳ０６）。処理（２）の結果が通知されて来ていない場合（ステップＳ０６で“Ｎｏ”）はステップＳ０５の処理に戻り、処理（２）の結果が通知されて来ていた場合（ステップＳ０６で“Ｙｅｓ”）にステップＳ０７の処理に進む。これはつまり、内部変数λが空であるノードＮ2〜Ｎn（ノードＮ1以外）は、処理（２）の結果がノードＮ1から通知されて来ない限りステップＳ０５とステップＳＳ０６との処理を繰り返し実行する事を意味する。
【００４３】
そして、処理（２）の結果が通知されて来ていた場合（ステップＳ０６で“Ｙｅｓ”）に、ノードＮ2〜Ｎnの事前再配置処理部２０２は、ノードＮ1から通知されてきた処理（２）の結果を内部変数λに代入し（ステップＳ０７）、ステップＳ０５の処理に進む。これにより、ステップＳ０５で内部変数λが空でないと判定されて、ノードＮ2〜Ｎn（ノードＮ1以外）についてもステップＳ０８の処理に進むことになる。
【００４４】
ノードＮ1についてはステップＳ０４に続いて、ノードＮ2〜ＮnついてはステップＳ０５で“Ｎｏ”と判定された場合に、システムに新しいノードＮ(n+1)が追加されたか否かを判定する（ステップＳ０８）。新しいノードＮ(n+1)が追加されていた場合（ステップＳ０８で“Ｙｅｓ”）はステップＳ０１の処理に戻り、新しいノードＮ(n+1)が追加されていない場合（ステップＳ０８で“Ｎｏ”）はステップＳ０９の処理に進む。これはつまり、新しいノードＮ(n+1)が追加されると内部変数λが空で初期化され、ステップＳ０３における処理（１）およびステップＳ０４における処理（２）によって再計算される事を意味する。
【００４５】
ステップＳ０８で新しいノードＮ(n+1)が追加されていない場合（ステップＳ０８で“Ｎｏ”）に、各ノードＮ1〜Ｎnのデータコピー部２０２ｃは、自身のリソースに余裕があるか否かを判定する（ステップＳ０９）。この判定は、例えば、直近のディスク容量が閾値以下であるか、単位時間当たりのディスクＩ／Ｏ（Input/Output）の利用状況，ＣＰＵ使用率（負荷），ネットワーク使用率（転送量）が閾値以下であるか等により行ってもよい。リソースに余裕がある場合（ステップＳ０９で“Ｙｅｓ”）はステップＳ１０に処理を進め、リソースに余裕がない場合（ステップＳ０９で“Ｎｏ”）には、例えば一定時間経過後に再度この判定を行う。
【００４６】
ステップＳ０９でリソースに余裕があると判定された場合（ステップＳ０９で“Ｙｅｓ”）に、各ノードＮ1〜Ｎnのデータコピー部２０２ｃは、「処理（３）：データコピー処理」を実行する（ステップＳ１０）。「処理（３）：データコピー処理」は、範囲差分に基づいて、データの事前配置（範囲差分のデータのコピー）を行う処理である。処理の詳細については後述する。そして、ステップＳ０５に処理を進める。これはつまり、ステップＳ０８で新しいノードＮ(n+1)が追加されるまで、ステップＳ１０の「処理（３）：データコピー処理」を繰り返し実行する事を意味する。
【００４７】
＜処理（１）：ノード追加位置決定処理＞
次に、図７のステップＳ０３で実行される「処理（１）：ノード追加位置決定処理」について説明する。ここでは、ノードの数がｎである分散ファイルシステム１において、新たに１つのノードＮ(n+1)を追加する場合を想定して説明する。
ノードＮ1のノード追加位置決定部２０２ａ（図２参照）は、新たなノードＮ(n+1)の追加位置Ｄ(n+1)を以下の式（４）で決定する。これは新たなノードＮ(n+1)を、ノードＮnの位置ＤnとノードＮ1の位置Ｄ1の丁度中間の位置に追加する事を意味する。
【００４８】
Ｄ(n+1)＝Ｄn＋（３６０／ｎ）／２  ・・式（４）
なお、式（４）の計算結果がハッシュレンジの最大値以上になる場合、その値は最大値（ここでは３６０）で割った余りと読み替える。例えば、位置「３６０」は位置「０」であり、また位置「３８０」は位置「２０」である。
【００４９】
＜処理（２）：範囲差分通知処理＞
次に、図７のステップＳ０４で実行される「処理（２）：範囲差分通知処理」について説明する。
ノードＮ1の範囲差分通知部２０２ｂ（図２参照）は、ノードＮ(n+1)が追加された後、各ノードＮx（ｘ＝１〜ｎ）が新たに範囲としなければならないハッシュ値の範囲を以下の手順で判定し、その結果を他のノードＮ2〜Ｎnに通知する。
【００５０】
まず、ノードＮ1の範囲差分通知部２０２ｂ（図２参照）は、各ノードＮx（ｘ＝１〜ｎ）が移動しなければならない位置Ｄx'を次の式（５）で算出する。これは、追加したノードＮ(n+1)の位置Ｄ(n+1)を起点にして、各ノードＮxの間隔が均等になるように移動させた場合の位置を表している。
Ｄx'＝Ｄ(n+1)＋ｘ×（３６０／（ｎ＋１））    ・・式（５）
【００５１】
ここで、式（５）のＤ(n+1)を式（４）で置き換えると、以下の式（６）を得ることができる。
Ｄx'＝Ｄn＋（３６０／ｎ）／２＋ｘ×（３６０／（ｎ＋１））    ・・式（６）
【００５２】
各ノードＮx（ｘ＝１〜ｎ）の位置Ｄxが位置Ｄx'に移動するのに伴い、各ノードＮxが担当するハッシュ値の範囲Ｒxは、以下の式（７）に示す範囲Ｒx'に変化する。
Ｒx'＝［Ｄx'，Ｄ(x+1)'］  ・・式（７）
【００５３】
ここで、上の式（７）に式（６）を代入すると、以下の式（８）を得る。
Ｒx'＝［Ｄn＋（３６０／ｎ）／２＋ｘ×（３６０／（ｎ＋１）），Ｄn＋（３６０／ｎ）／２＋（ｘ＋１）×（３６０／（ｎ＋１））］  ・・式（８）
【００５４】
さらに、式（８）のＤnを式（１）で置き換えると、次の式（９）を得る。
Ｒx'＝［Ｄ1＋（ｎ−１）×（３６０／ｎ）＋（３６０／ｎ）／２＋ｘ×（３６０／（ｎ＋１）），Ｄ1＋（ｎ−１）×（３６０／ｎ）＋（３６０／ｎ）／２＋（ｘ＋１）×（３６０／（ｎ＋１））］  ・・式（９）
【００５５】
式（３）と式（９）からノード追加前の範囲Ｒxの最小値（Ｒx_min）と最大値（Ｒx_max）、ノード追加後の範囲Ｒx'の最小値（Ｒx_min'）と最大値（Ｒx_max'）は、それぞれ以下の通り算出する事ができる。
Ｒx_min  ＝Ｄ1＋（ｘ−１）×（３６０／ｎ）  ・・式（１０−１）
Ｒx_max  ＝Ｄ1＋ｘ×（３６０／ｎ）          ・・式（１０−２）
Ｒx_min'＝Ｄ1＋（ｎ−１）×（３６０／ｎ）＋（３６０／ｎ）／２＋ｘ×（３６０／（ｎ＋１））  ・・式（１０−３）
Ｒx_max'＝Ｄ1＋（ｎ−１）×（３６０／ｎ）＋（３６０／ｎ）／２＋（ｘ＋１）×（３６０／（ｎ＋１））  ・・式（１０−４）
【００５６】
ここで、ノードＮ1の範囲差分通知部２０２ｂは、範囲Ｒxと範囲Ｒx'との差分の内で新たに増加する範囲差分を次の条件式で判定し、その結果を自身を除く全ノードＮ2〜Ｎnに通知する。つまり範囲差分は、ノードが１つ追加された場合に、各ノードＮx（ｘ＝１〜ｎ）が新たに保持しなければならないハッシュ値である。なお、範囲差分は、上述のように内部変数λに代入され、各ノードＮx（ｘ＝１〜ｎ）の範囲差分は、内部変数λxに代入される。
［Ｒx_min'，Ｒx_min］（ただし、Ｒx_min'＜Ｒx_minの場合のみ）  ・・条件式（１１）
［Ｒx_max，Ｒx_max'］（ただし、Ｒx_max≦Ｒx_max'の場合のみ）  ・・条件式（１２）
【００５７】
ここまでの処理を、４台のノードＮ1〜Ｎ4（ｎ＝４）で構成され、ノードＮ1の位置Ｄ1＝４５の場合を想定して説明する。
なお、前記した説明した通り、計算の結果値がハッシュレンジの最大値（ここでは３６０）以上となった場合、その値は最大値で割った余りと読み替える。例えば、位置「４３２」は位置「７２」であり、また位置「５０４」は位置「１４４」である。
【００５８】
（ノードＮ1（ｘ＝１））
式（１０−１）〜式（１０−４）を使うと、移動前と移動後のノードＮ1が担当するハッシュ値の範囲の最大値、最小値は、以下の通り算出される。
Ｒ1_min  ＝４５＋（１−１）×（３６０／４）＝４５
Ｒ1_max  ＝４５＋１×（３６０／４）＝１３５
Ｒ1_min'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋１×（３６０／５）＝４３２＝７２
Ｒ1_max'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋（１＋１）×（３６０／５）＝５０４＝１４４
【００５９】
この場合、Ｒ1_min'＞Ｒ1_minであるため条件式（１１）を満たす範囲はないが、Ｒ1_max＜Ｒ1_max'であるので、次の範囲差分が代入される内部変数λ1は条件式（１２）を満たす範囲と判定され、ノードＮ1自身に通知される。
λ1＝［１３５，１４４］
つまり、ノードＮ1は、ノード追加前に［１３５，１４４］のデータも保持していれば、ノード追加後の再配置は不要となる事を意味している（図８参照）。図８（ａ）はノード追加前のノードＮ1の現行範囲Ｒ1を示し、図８（ｂ）はノード追加後の予測範囲Ｒ1'を示す。
【００６０】
（ノードＮ2（ｘ＝２））
式（１０−１）〜式（１０−４）を使うと、移動前と移動後のノードＮ2が担当するハッシュ値の範囲の最大値、最小値は、以下の通り算出される。
Ｒ2_min  ＝４５＋（２−１）×（３６０／４）＝１３５
Ｒ2_max  ＝４５＋２×（３６０／４）＝２２５
Ｒ2_min'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋２×（３６０／５）＝５０４＝１４４
（Ｒ2_min'の値「５０４」は、ハッシュレンジが「０〜３６０」であるので、「１４４」となる。）
Ｒ2_max'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋（２＋１）×（３６０／５）＝５７６＝２１６
（Ｒ2_max'の値「５７６」は、ハッシュレンジが「０〜３６０」であるので、「２１６」となる。）
【００６１】
この場合、Ｒ2_min'＞Ｒ2_minであるため条件式（１１）を満たす範囲はなく、また、Ｒ2_max＞Ｒ2_max'であるため条件式（１２）を満たす範囲も存在しないと判定され、ノードＮ2には範囲差分が代入される内部変数λ2が存在しない旨（＝空）が通知される。
λ2＝（空）
つまり、ノードＮ2は、ノードが追加されても新たに保持しなければならないデータはない事になるため、ノード追加後に再配置そのものが不要である事を意味している（図９参照）。図９（ａ）はノード追加前のノードＮ2の現行範囲Ｒ2を示し、図９（ｂ）はノード追加後の予測範囲Ｒ2'を示す。
【００６２】
（ノードＮ3（ｘ＝３））
式（１０−１）〜式（１０−４）を使うと、移動前と移動後のノードＮ3が担当するハッシュ値の範囲の最大値、最小値は、以下の通り算出される。
Ｒ3_min  ＝４５＋（３−１）×（３６０／４）＝２２５
Ｒ3_max  ＝４５＋３×（３６０／４）＝３１５
Ｒ3_min'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋３×（３６０／５）＝５７６＝２１６
（Ｒ3_min'の値「５７６」は、ハッシュレンジが「０〜３６０」であるので、「２１６」となる。）
Ｒ3_max'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋（３＋１）×（３６０／５）＝６４８＝２８８
（Ｒ3_max'の値「６４８」は、ハッシュレンジが「０〜３６０」であるので、「２８８」となる。）
【００６３】
この場合、Ｒ3_max＞Ｒ3_max'であるため条件式（１２）を満たす範囲はないが、Ｒ3_min'＜Ｒ3_minであるので、次の範囲差分が代入される内部変数λ3は条件式（１１）を満たす範囲と判定され、ノードＮ3に通知される。
λ3＝［２１６，２２５］
つまり、ノードＮ3は、ノード追加前に［２１６，２２５］のデータも保持していれば、ノード追加後の再配置は不要となる事を意味している（図１０参照）。図１０（ａ）はノード追加前のノードＮ3の現行範囲Ｒ3を示し、図１０（ｂ）はノード追加後の予測範囲Ｒ3'を示す。
【００６４】
（ノードＮ4（ｘ＝４））
式（１０−１）〜式（１０−４）を使うと、移動前と移動後のノードＮ4が担当するハッシュ値の範囲の最大値、最小値は、以下の通り算出される。
Ｒ4_min  ＝４５＋（４−１）×（３６０／４）＝３１５
Ｒ4_max  ＝４５＋４×（３６０／４）＝４０５＝４５
Ｒ4_min'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋４×（３６０／５）＝６４８＝２８８
（Ｒ4_min'の値「６４８」は、ハッシュレンジが「０〜３６０」であるので、「２８８」となる。）
Ｒ4_max'＝４５＋（４−１）×（３６０／４）＋（３６０／４）／２＋（４＋１）×（３６０／５）＝７２０＝０
（Ｒ4_max'の値「７２０」は、ハッシュレンジが「０〜３６０」であるので、「０」となる。）
【００６５】
この場合、Ｒ4_max＞Ｒ4_max'であるため条件式（１２）を満たす範囲はないが、Ｒ4_min'＜Ｒ4_minであるので、次の範囲差分が代入される内部変数λ4は条件式（１１）を満たす範囲と判定され、ノードＮ4に通知される。
λ4＝［２２８，３１５］
つまり、ノードＮ4は、ノード追加前に［２２８，３１５］のデータも保持していれば、ノード追加後の再配置は不要となる事を意味している（図１１参照）。図１１（ａ）はノード追加前のノードＮ4の現行範囲Ｒ4を示し、図１１（ｂ）はノード追加後の予測範囲Ｒ4'を示す。
【００６６】
＜処理（３）：データコピー処理＞
次に、図７のステップＳ１０で実行される「処理（３）：データコピー処理」について説明する。
各ノードＮx（ｘ＝１〜ｎ）のデータコピー部２０２ｃ（図２参照）は、ステップＳ０４の処理（２）で得られた範囲差分が代入される内部変数λのデータを隣接するノードＮ(x-1)，Ｎ(x+1)に対して要求し、自身のデータ保持部２０４にコピー（格納）する。ここで、隣接するノードＮ(x-1)，Ｎ(x+1)とは、ハッシュレンジ上における自身が担当する範囲（現行範囲）に隣接する範囲（隣接範囲）を担当するノードＮのことを意味する。一例として、ｘ＝２であるならば、担当するノードＮ2に隣接するノードはノードＮ1，Ｎ3であり、ｘ＝ｎであるならば、担当するノードＮnに隣接するノードはノードＮ(n-1)，Ｎ1である。この処理は、ステップＳ０９で自身のリソースに余裕がある場合に限り行われる。
【００６７】
＜再配置処理＞
再配置処理では、新しいノードＮ(n+1)が追加された場合に、データの再配置を行う。
各ノードＮx（ｘ＝１〜ｎ）の再配置処理部２０３（図２参照）は、新しいノードＮ(n+1)が追加された後に各ノードＮ1〜Ｎnが新たに範囲としなければならないハッシュ値の範囲Ｒ1'〜Ｒn'のデータについてコピーを行う。ここで、前記説明した事前再配置処理で事前に再配置を済ませている範囲については、処理を省略することが可能である。
なお、新しいノードＮ(n+1)が追加された場合に、図７のステップＳ０８の判定で“Ｙｅｓ”となり、ステップＳ０１で内部変数λが空で初期化され、ステップＳ０３における処理（１）およびステップＳ０４における処理（２）によって再計算される。
【００６８】
以上のように、本実施形態に係る分散ファイルシステム１は、新たなノードＮ(n+1)が追加された場合を想定して、データの再配置を可能な限りで事前に行う。つまり、新たなノードＮ(n+1)が追加される前のハッシュレンジ上における担当範囲（現行範囲）と新たなノードＮ(n+1)が追加された後のハッシュレンジ上における担当範囲（予測範囲）との差分（範囲差分）を各ノードＮ1〜Ｎnに通知する。そして、各ノードＮ1〜Ｎnでは、リソースに余裕がある時間に範囲差分のデータを隣接するノードＮ(x-1)，Ｎ(x+1)から事前に取得する。その為、本実施形態に係る分散ファイルシステム１によれば、新たなノードＮ(n+1)を追加した後に行うデータの再配置に要する時間（性能劣化時間）を短縮する事ができる。
【００６９】
［変形例］
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、特許請求の範囲の趣旨を変えない範囲で実施することができる。実施形態の変形例を以下に示す。
【００７０】
本実施形態では、ノードＮ1が「処理（１）：ノード追加位置決定処理」および「処理（２）：範囲差分通知処理」を行い、ノードＮ1〜Ｎnが「処理（３）：データコピー処理」を行っていた。しかしながら、「処理（１）：ノード追加位置決定処理」および「処理（２）：範囲差分通知処理」を実行するのは、ノードＮ1に限定されるものではなく、例えば、ノードＮ2〜Ｎnの何れかがこれらの処理を実行してもよい。
【００７１】
また、図１２に示すように、分散ファイルシステム１ａは、データの保存・参照を要求する複数の端末１００と、端末の要求に応えてデータの格納・送信を行う複数のノード２００と、ノード２００が保存するデータの再配置を行う再配置装置３００と、から構成されていてもよい。この再配置装置３００は、「処理（１）：ノード追加位置決定処理」および「処理（２）：範囲差分通知処理」を行うようにする。
【符号の説明】
【００７２】
１，１ａ  分散ファイルシステム
１００  端末
２００  ノード（配信装置）
２０１  データ送受信部
２０２  事前再配置処理部
２０２ａ  ノード追加位置決定部（追加位置決定部）
２０２ｂ  範囲差分通知部
２０２ｃ  データコピー部
２０３  再配置処理部
２０４  データ保持部
３００  再配置装置
【図１】
2016157266.tif 000003
【図２】
2016157266.tif 000004
【図３】
2016157266.tif 000005
【図４】
2016157266.tif 000006
【図５】
2016157266.tif 000007
【図６】
2016157266.tif 000008
【図７】
2016157266.tif 000009
【図８】
2016157266.tif 000010
【図９】
2016157266.tif 000011
【図１０】
2016157266.tif 000012
【図１１】
2016157266.tif 000013
【図１２】
2016157266.tif 000014