(57)【特許請求の範囲】
【請求項１】
クライアントが、元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバーに分散配布するデータ処理システムにおいて
各サーバー毎にＮ個のブロックファイルに関連づけられた異なるＮ個の係数を１セットとして決定する係数決定手段と、
前記元のファイルのデータを同一サイズ間隔で多数に区切り、各区切られたデータを前記サイズより更に小さい同一サイズでＮ個に再区切りし、該再区切りされてＮ個のブロックファイルを構成するＮ個のデータに、それぞれ関連づけられた前記１セットの係数をそれぞれ乗算してＮ個の積を求め、該Ｎ個の積を合算して１個のデータに圧縮する処理を繰り返して、元のファイルを１／Ｎのサイズのファイルにエンコードして前記サーバー配布用のファイルとするエンコード手段と、
コンピュータが、Ｎ台のサーバーに配布されたＮ個のファイルと、前記Ｎ台のサーバー毎に定められた前記係数とを用いて、Ｎ個の未知数を用いたＮ個の一次方程式の組からなる連立一次方程式を生成し、該連立一次方程式を解いてＮ個のブロックファイルを復元するデコード手段と、
該復元されたＮ個のブロックファイルを連結して元のファイルを再生するファイル連結手段とを有しており、
前記エンコード手段は、サーバー群を階層化して接続しており、最上層のＮ台のサーバーはクライアントからエンコードされたデータを直接に分散配布され、上記最上層以外のサーバー群は、相対的に上層のＮ台のサーバーから相対的に下層のサーバーにエンコードされたデータを配信し、最上層と最下層のサーバーを除く全てのサーバーが順次にエンコード処理を一斉に行うことを特徴とするデータ処理システム。
【請求項２】
Ｎが３であって、元のファイルがＸ１、Ｘ２、Ｘ３のブロックファイルからなっており、
再区切りされた３個のデータがｘ１、ｘ２、ｘ３からなり、
ｘ１の係数をａｋ．１、ｘ２の係数をａｋ．２、ｘ３の係数をａｋ．３（ここでｋはサーバーを指定する数）として、
ａｋ．１ｘ１＋ａｋ．２ｘ２＋ａｋ．３ｘ３、∀ｋ∈｛１．２．３．４．・・・｝
を求めて１つのデータに圧縮してなることを特徴とする請求項１に記載のデータ処理システム。
【請求項３】
エンコードおよびデコードの演算がガロア体（有限体」を用いて演算されてなることを特徴とする請求項１または２に記載のデータ処理システム。
【請求項４】
クライアントが元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバーに前記ファイルを分散配布する分散データシステムにおいて、
各サーバー毎にＮ個のブロックファイルに関連づけられた異なるＮ個の係数を１セットとして決定し、該係数を保存する係数決定手段と、
前記元のファイルのデータを同一サイズ間隔で多数に区切り、各区切られたデータを前記サイズより更に小さい同一サイズでＮ個に再区切りし、該再区切りされてＮ個のブロックファイルを構成するＮ個のデータに、それぞれ関連づけられた前記１セットの係数をそれぞれ乗算してＮ個の積を求め、該Ｎ個の積を合算して１個のデータに圧縮する処理を繰り返して、元のファイルを１／Ｎのサイズのファイルにエンコードして前記サーバー配布用のファイルとするエンコード手段と、
該エンコードされたデータを前記配布予定のサーバーに配布して保存する分散保存手段と、
多数のサーバーの中から任意のＮ台のサーバーを選択するサーバー選択手段と、
選択されたＮ台のサーバーに配布されたＮ個のファイルと、前記Ｎ台のサーバー毎に定められた前記係数とを用いて、Ｎ個の未知数を用いたＮ個の一次方程式の組からなる連立一次方程式を生成し、該連立一次方程式を解いてＮ個のブロックファイルを復元するデコード手段と、
該復元されたＮ個のブロックファイルを連結して元のファイルを再製するファイル連結手段とを有し、
前記エンコード手段は、サーバー群を階層化して接続しており、最上層のＮ台のサーバーはクライアントからエンコードされたデータを直接に分散配布され、上記最上層以外のサーバー群は、相対的に上層のＮ台のサーバーから相対的に下層のサーバーにエンコードされたデータを配信し、最上層と最下層のサーバーを除く全てのサーバーが順次にエンコード処理を一斉に行っており、
前記エンコード手段およびデコード手段での演算は、ガロア体（有限体）を用いて演算されていることを特徴とする分散データシステム。
【請求項５】
Ｎが２または３からなることを特徴とする。請求項４に記載の分散データシステム。
【請求項６】
Ｎが３であって、元のファイルがＸ１、Ｘ２、Ｘ３のブロックファイルからなっており、
再区切りされた３個のデータがｘ１、ｘ２、ｘ３からなり、
ｘ１の係数をａｋ．１、ｘ２の係数をａｋ．２、ｘ３の係数をａｋ．３（ここでｋはサーバーを指定する数）として、
ａｋ．１ｘ１＋ａｋ．２ｘ２＋ａｋ．３ｘ３、∀ｋ∈｛１．２．３．４．・・・｝を求めて１つのデータに圧縮してなることを特徴とする請求項４に記載の分散データシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数あるデータ管理サーバーのいずれかが故障しても、任意の所定数のサーバーを用いることで元のファイルを再生することができるエンコード・デコード構造およびこれを用いた分散データシステムに関するものである。
【背景技術】
【０００２】
従来、データ保護における堅牢性とデータ保存容量における高効率性をもつランダムネットワークコーディングを用いたデータシステムはエンコードされたデータへのアクセスの難しさのために、実用化が難しい技術であった。
例えば、特開２０１５−３５１８２の分散データシステムでは、クラスタを構成するデータ管理サーバーが故障等した場合に、データ欠損を検出し、その欠損したデータのキーのハッシュ値の範囲を特定するための発明であり、分散データシステムが備える欠損データ特定装置は、データを保存するデータ管理サーバーそれぞれと対になるダミーデータを生成し、振り分けサーバーを介して各データ管理サーバーに記憶しておく。欠損データ特定装置は、データ管理装置の増減を管理する分散ハッシュ情報の変更通知を受信すると、変更前後の分散ハッシュ情報を比較し、データ管理サーバーの増減を判定する。そして、欠損データ特定装置は、データ管理サーバーが削除された場合は、そのデータ管理サーバーに向けてダミーデータの削除要求を、振り分けサーバーを介して送信し、登録したダミーデータを削除できないことにより、データの欠損を検出し、変更前の分散ハッシュ情報に基づき、欠損データのキーの範囲を特定する構成からなっている。
このようにすることで、クラスタを構成する複数のデータ管理サーバーが故障等した場合に、原本データと所定の複製数の複製データが失われたことによる、データの欠損を検出することができる。また、損失データ特定装置が、旧世代の分散ハッシュ情報を記憶しておくことにより、減少したデータ管理装置の担当範囲に基づき、欠損したデータのキーのハッシュ値の範囲を特定することができる。
上記構成ではデータ管理サーバーが故障した場合に、データの欠損を復元させるために、多くの時間を費やす必要があり、復元したデータを用いてデコードするためには、従来同様に、一定条件を有する所定の原本データまたは複製データを有する複数の管理サーバーを用いてデータ全体のデコードを行う必要があった。
大規模データの分散データ処理システムとして、例えば、従来のＨａｄｏｏｐでは、一つの元のファイルＸ０を複数（Ｎ）個（図示例ではＸ１、Ｘ２、Ｘ３の３つ）のブロックに区切り、各ブロックの複製を複数のサーバーＳ１、Ｓ２、Ｓ３、・・に分配する（図９参照）構成が知られている。
そして、一クラスターにおいて、Ｒ台のサーバーがアクセス不能の状況下にあるとすると、１＋Ｒ倍のデータ保存容量を必要とする。
このことは、元のファイルの複製をそのまま前記サーバーに分配する従来のＧｌｕｓｔｅｒＦＳの場合も同様で、１＋Ｒ倍の保存容量が必要とされていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１２−２２１４１９２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
この発明が解決しようとする問題点は、分散データシステムにおいて、多数のデータサーバーに配布されるファイルを元のファイル容量の１／Ｎでエンコードして保存すると共に、前記多数のサーバーの中から任意のＮ台のサーバーを選択して元のファイルを再製することができるデータ処理システムおよびこれを用いたデータ分散システムを提供することにある。
【課題を解決するための手段】
【０００５】
本発明は、上記課題を達成するために、請求項１のデータ処理システムでは、
クライアントが、元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバーに分散配布するデータ処理システムにおいて
各サーバー毎にＮ個のブロックファイルに関連づけられた異なるＮ個の係数を１セットとして決定する係数決定手段と、
前記元のファイルのデータを同一サイズ間隔で多数に区切り、各区切られたデータを前記サイズより更に小さい同一サイズでＮ個に再区切りし、該再区切りされてＮ個のブロックファイルを構成するＮ個のデータに、それぞれ関連づけられた前記１セットの係数をそれぞれ乗算してＮ個の積を求め、該Ｎ個の積を合算して１個のデータに圧縮する処理を繰り返して、元のファイルを１／Ｎのサイズのファイルにエンコードして前記サーバー配布用のファイルとするエンコード手段と、
コンピュータが、Ｎ台のサーバーに配布されたＮ個のファイルと、前記Ｎ台のサーバー毎に定められた前記係数とを用いて、Ｎ個の未知数を用いたＮ個の一次方程式の組からなる連立一次方程式を生成し、該連立一次方程式を解いてＮ個のブロックファイルを復元するデコード手段と、
該復元されたＮ個のブロックファイルを連結して元のファイルを再生するファイル連結手段とを有しており、
前記エンコード手段は、サーバー群を階層化して接続しており、最上層のＮ台のサーバーはクライアントからエンコードされたデータを直接に分散配布され、上記最上層以外のサーバー群は、相対的に上層のＮ台のサーバーから相対的に下層のサーバーにエンコードされたデータを配信し、最上層と最下層のサーバーを除く全てのサーバーが順次にエンコード処理を一斉に行うことを特徴とする。
また、請求項４のデータ分散システムでは、
クライアントが元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバーに前記ファイルを分散配布する分散データシステムにおいて、
各サーバー毎にＮ個のブロックファイルに関連づけられた異なるＮ個の係数を１セットとして決定し、該係数を保存する係数決定手段と、
前記元のファイルのデータを同一サイズ間隔で多数に区切り、各区切られたデータを前記サイズより更に小さい同一サイズでＮ個に再区切りし、該再区切りされてＮ個のブロックファイルを構成するＮ個のデータに、それぞれ関連づけられた前記１セットの係数をそれぞれ乗算してＮ個の積を求め、該Ｎ個の積を合算して１個のデータに圧縮する処理を繰り返して、元のファイルを１／Ｎのサイズのファイルにエンコードして前記サーバー配布用のファイルとするエンコード手段と、
該エンコードされたデータを前記配布予定のサーバーに配布して保存する分散保存手段と、
多数のサーバーの中から任意のＮ台のサーバーを選択するサーバー選択手段と、
選択されたＮ台のサーバーに配布されたＮ個のファイルと、前記Ｎ台のサーバー毎に定められた前記係数とを用いて、Ｎ個の未知数を用いたＮ個の一次方程式の組からなる連立一次方程式を生成し、該連立一次方程式を解いてＮ個のブロックファイルを復元するデコード手段と、
該復元されたＮ個のブロックファイルを連結して元のファイルを再製するファイル連結手段とを有し、
前記エンコード手段は、サーバー群を階層化して接続しており、最上層のＮ台のサーバーはクライアントからエンコードされたデータを直接に分散配布され、上記最上層以外のサーバー群は、相対的に上層のＮ台のサーバーから相対的に下層のサーバーにエンコードされたデータを配信し、最上層と最下層のサーバーを除く全てのサーバーが順次にエンコード処理を一斉に行っており、
前記エンコード手段およびデコード手段での演算は、ガロア体（有限体）を用いて演算されていることを特徴とする。
前記Ｎは２または３であることが望ましい。
【発明の効果】
【０００６】
この発明によれば、元のファイルをＮ個のブロックのファイルに分け、各サーバー毎に異なる一次方程式を作成することができるようにエンコードされる。
エンコード、デコードの演算はガロア体演算ライブラリーを用いるので、短時間で処理することができる。
エンコードに際しては、元のファイルに対して１／Ｎのサイズに圧縮することができる。
そして、デコードに際しては、任意のＮ台のサーバーを選択し、Ｎ個の一次方程式を連立して解くことで元のファイルを再製することができ、デコードするサーバーの台数以外を特定する必要がない。
【図面の簡単な説明】
【０００７】
【図１】分散データシステムの概略を示す機能ブロック図である。
【図２】エンコードされたデータの分散を示す概略図である。
【図３】任意のサーバーを選択してデコードする場合の概略図である。
【図４】エンコード時のファイルの区切を説明するブロック図である。
【図５】エンコード時の圧縮状態を説明するブロック図である。
【図６】ハッシュリングの初期状態を示す模式図である。
【図７】同サーバー追加前を示す模式図である。
【図８】サーバー追加後の模式図である。
【図９】従来のＨａｄｏｏｐによるデータ分散を示す説明図である。
【発明を実施するための形態】
【実施例１】
【０００８】
この発明の分散データシステムは、元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバー（データ管理サーバー）に前記ファイルを分散配布する分散データシステムであって、クライアントサーバーシステムで用いることができる分散データシステムである。
また上記分散システムに用いるデータ処理装置は、エンコード、デコードにおいて同一である。【０００９】
ここで、分散データシステム１の概略は、図１のブロック図に示すように、クライアントコンピュータＣにより決定された各サーバー毎にＮ個のブロックファイルに関連づけられた異なるＮ個の係数を１セットとして決定し、該係数を保存する係数決定手段２と、クライアントにより前記元のファイルＸ０のデータを同一サイズ間隔で多数に区切り、各区切られたデータを前記サイズより更に小さい同一サイズでＮ個に再区切りし、該再区切りされてＮ個のブロックファイルを構成するＮ個のデータに、それぞれ関連づけられた前記１セットの係数をそれぞれ乗算してＮ個の積を求め、該Ｎ個の積を合算して１個のデータに圧縮する処理を繰り返して、元のファイルを１／Ｎのサイズのファイルにエンコードして前記サーバー配布用のファイルとするエンコード手段３と、該エンコードされたデータを前記配布予定のサーバーに配布して保存する分散保存手段４と、多数のサーバーの中から任意のＮ台のサーバーを選択するサーバー選択手段５と、選択されたＮ台のサーバーに配布されたＮ個のファイルと、前記Ｎ台のサーバー毎に定められた前記係数とを用いて、Ｎ個の未知数を用いたＮ個の一次方程式の組からなる連立一次方程式を生成し、該連立一次方程式を解いてＮ個のブロックファイルを復元するデコード手段６と、該復元されたＮ個のブロックファイルを連結して元のファイルＸ０を再製するファイル連結手段７とを有している。
前記エンコード手段３およびデコード手段６での演算は、ガロア体（有限体）を用いて演算されている。
なお、データ処理システムでは、図１の係数決定手段２と、エンコード手段３と、デコード手段６と、ファイル連結手段７とからなっているのでその説明を省略する。【００１０】
［ランダムネットワークコーディング］
ここで、説明の便宜上、Ｎを３として具体的に説明するが、この発明ではＮは３に限定されることなく２でもよいし、他の自然数であってもよい。
ランダムネットワークコーディングでは、連立一次方程式の特性を生かし、データシステムにおける高堅牢性とデータ容量の節約を両立させている。
そこで、元のファイルＸ０を３つのブロック（Ｘ１、Ｘ２、Ｘ３）に区切り、Ｘ１を構成するデータをｘ１、Ｘ２を構成するデータをｘ２、Ｘ３を構成するデータをｘ３とする。【００１１】
例えば、ｘ１＝３、ｘ２＝１、ｘ３＝１２として、以下のように異なった係数の組み合わせで多数の一次方程式を作るとする。
２ｘ１＋５ｘ２＋ｘ３＝１３
７ｘ１＋３ｘ２＋８ｘ３＝４２
４ｘ１＋ｘ２＋２ｘ３＝１９
５ｘ１＋４ｘ２＋９ｘ３＝３３
・・・・・・・・（省略）
ここで元のファイルＸ０を構成するＸ１，Ｘ２，Ｘ３を得るには、前記多数の一次方程式のうち３つの方程式があれば十分である。
従って、ランダムネットワークコーディングでは、１つの元のファイルＸ０をＮ個、実施例ではＸ１、Ｘ２、Ｘ３の３個に分けて、サーバー毎の異なった組合せの係数ａで、３つ以上の一次方程式を作ってエンコードが行われる。
係数は、サーバー単位で、且つ３つに区切られたファイル（ｘ１、ｘ２、ｘ３）毎に設定される。【００１２】
この場合、クライアントＣは、まず３つのブロックに区切られたデータＸ１、Ｘ２、Ｘ３に対して関連づけられるサーバー毎の３つの係数ａを決める。
ここで１つのサーバーに用いる１セットとなる３つの係数は、３つのうち全てが異なる係数でも、２つ以上の係数が同一の係数であってもよい。
しかし、異なるサーバー間において、同一の係数の組合せが用いられることはなく、各サーバーごとに違う組み合わせの係数が割り当てられる。
そこで、ａｋ．１、ａｋ．２、ａｋ．３、∀ｋ∈｛１，２，３，４，・・・・｝を決め、ａｋ．１ｘ１＋ａｋ．２ｘ２＋ａｋ．３ｘ３、∀ｋ∈｛１，２，３，４，・・・・｝の式に基づいて各サーバーに分散配布されるデータｂ１、ｂ２、ｂ３、ｂ４、・・・を演算する。
ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３＝ｂ１
ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３＝ｂ２
ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３＝ｂ３
ａ４．１ｘ１＋ａ４．２ｘ２＋ａ４．３ｘ３＝ｂ４
・・・・・・・・（省略）【００１３】
ここで、ａに続く数字「１」はサーバーＳ１を指定する数字、「．１」はサーバーに保存されるｘ１を指定する数字であり、「ａ１．１」はサーバーＳ１のｘ１のデータに用いる係数を示す。
同様に「．２」はｘ２を指定し、「．３」はｘ３を指定している。
ａに続く数字「２」はサーバーＳ２を指定する数字、「３」はサーバーＳ３指定する数字であり、その他は同様である。
そして、ｂ１は、前記サーバーＳ１に保存するファイルを構成する数値、ｂ２はサーバーＳ２に保存する同様の数値、ｂ３はサーバーＳ３で保存する同様の数値である。
このように各サーバー毎で、区切られるファイル毎に異なる係数が予め設定される。
ここで、前記各サーバーに送られる係数ａのサイズはそれぞれ２ｂｙｔｅｓであり、サーバーに配布されるファイルのヘッダーに記録される。【００１４】
［エンコード］
クライアントＣは前記サーバー毎の係数をファイルサイズ，ファイルの更新された時間といった情報と共に、対応するサーバーに配布し，その後にファイルのエンコードを開始する。
エンコードは、例えば、ファイルを６ｂｙｔｅｓ毎に区切り，その６ｂｙｔｅｓのデータを更に２ｂｙｔｅｓ毎に区切って、前記Ｘ１，Ｘ２，Ｘ３に対応したｘ１、ｘ２、ｘ３に割り当てる（図４参照）。
そして、前記ａｋ．１ｘ１＋ａｋ．２ｘ２＋ａｋ．３ｘ３、∀ｋ∈｛１，２，３，４，・・・・｝の式をガロア体を用いて算出し、新たに求められて２ｂｙｔｅｓのデータｂｘ（図５参照）が、前記係数に対応したサーバーに送られる。
上記一連の作業は前記ファイルの末尾に到達するまで行われる。
本実施例では、第１次の区切りのサイズを６ｂｙｔｅｓとし、第２次の再区切りのサイズを２ｂｙｔｅｓとしたが、上記数値は特に限定されるものではない。【００１５】
このようにエンコードされたファイルのサイズは、元のファイルＸ０容量の１／３となる。
先に述べたように前記サーバーに保存されるファイルには係数や，必要に応じて元のファイルの情報などがヘッダー情報として付加されるので、最終的にサーバーに保存されるファイル容量のサイズは元のファイルＸ０の１／３よりも若干大きくなる。
一方、エンコードで得られたｂ１、ｂ２、ｂ３、・・は、繰り返し計算され、その都度、前記各サーバーに送信される。【００１６】
エンコードで得られるデータが、前記クライアントＣのみで行う場合、多数の全てのサーバーＳ１、Ｓ２、・・・・毎に配布するには、演算に多くの処理時間がかかる。
そこで、この発明では、エンコードの処理を階層的に接続したサーバーで階層毎に行う。
即ち、クライアントＣが演算処理するエンコードのデータは、最上層となるＮ台（本実施例ではＳ１、Ｓ２、Ｓ３の３台）のサーバー向けに演算処理し配信する。
この最上層のサーバーＳ１にはエンコードされた順に少しずつデータｄｂ１が配布され、サーバーＳ２にはデータｄｂ２が配布され、サーバーＳ３にはデータｄｂ３が順次配布されそれぞれ保存される。【００１７】
ここで配布されるエンコードのデータｄｂ１、ｄｂ２、ｄｂ３は、演算処理された順番に一部の小容量毎のデータ（例えば、全体が１０Ｇｂのデータの場合に７Ｍｂなど）であり、これらが順次追加されて完成されたデータｂ１、ｂ２、ｂ３となるが、演算された順番毎の一部のデータの配信により短時間で各サーバーＳ１、Ｓ２、Ｓ３に配信できる。【００１８】
そこで、クライアントＣからサーバーＳ１に配信された前記データｄｂ１は、サーバーＳ１に保存されると同時に、サーバーＳ１から２層目のすべてのサーバーＳ４、Ｓ５、Ｓ６に配信され、それぞれのサーバーに保存される。
同様に、クライアントＣからサーバーＳ２に配信された前記データｄｂ２は、サーバーＳ２に保存されると同時に、サーバーＳ２から２層目のすべてのサーバーＳ４、Ｓ５、Ｓ６に配信され、それぞれのサーバーに保存される。【００１９】
同じく、クライアントＣからサーバーＳ３に配信された前記データｄｂ３は、サーバーＳ３に保存されると同時に、サーバーＳ３から２層目のすべてのサーバーＳ４、Ｓ５、Ｓ６に配信され、それぞれのサーバーに保存される。
これにより、２層目のサーバーＳ４、Ｓ５、Ｓ６には、１層目のサーバーＳ１、Ｓ２、Ｓ３からデータｄｂ１，ｄｂ２，ｄｂ３が配信される。【００２０】
一方、２層目のサーバーＳ４、Ｓ５、Ｓ６には、それぞれのサーバー毎に予め設定されている係数を用いて、ｄｂ１、ｄｂ２、ｄｂ３のデータを前記エンコーダと同様の手順で１／３に圧縮して、サーバーＳ４はデータｄｂ４をエンコードされたデータとして保存し全体としてデータｂ４を作成し、サーバーＳ５はデータｄｂ５をエンコードされたデータとして保存し全体としてデータｂ５を作成し、サーバーＳ６はデータｄｂ６をエンコードされたデータとして保存して全体としてデータＳ６を作成する。【００２１】
次に、３層目のサーバーＳ７、Ｓ８にはそれぞれ２層目のサーバーＳ４、Ｓ５、Ｓ６に保存されたデータｄｂ４、ｄｂ５、ｄｂ６が順次配信され、前記エンコーダと同様の手順で１／３に圧縮して、サーバーＳ７はデータｄｂ７をエンコードされたデータとして保存し全体としてデータｂ７が作成され、サーバーＳ８はデータｄｂ８をエンコードされたデータとして保存し全体としてデータｂ８が作成される。【００２２】
このようにしてクライアントＣから最上層のサーバーＳ１、Ｓ２、Ｓ３に配信されたデータｄｂ１、ｄｂ２、ｄｂ３はほぼ同時ないし僅かに遅れて２層目のサーバーＳ４、Ｓ５、Ｓ６に配信され、２層目のサーバーで再度エンコードされて保存されると共に、３層目のサーバーＳ７、Ｓ８に配信され、最下層の直前の階層のサーバーまで再度エンコードが行われてデータが保存される。
なお最下層のサーバーの台数は最上層のサーバーの台数以下であればよい。【００２３】
このようにクライアントＣのみで全てのサーバー（図示例ではＳ１からＳ８）用にエンコードデータを演算する必要がなく、クライアントＣはＮ個のサーバーにだけエンコードデータを演算すればよい。【００２４】
サーバー群は、最上層のＮ台のサーバー（Ｓ１〜Ｓ３）はクライアントＣからエンコードされたデータを直接に分散配布され、上記最上層のサーバー（Ｓ１、Ｓ２、Ｓ３）と最下層のサーバー（Ｓ７、Ｓ８）以外のサーバー群（Ｓ４〜Ｓ６）は、相対的に上層のＮ台のサーバーがそれぞれエンコードしたデータを相対的に下層のサーバーに配信するので、前記サーバー群が順次にエンコード処理を一斉に行うことになり、エンコードにかかる演算処理の時間を大幅に短縮することができる。【００２５】
図２を例に、前記エンコーディング（リレーエンコーディング）について更に詳細に説明する。
クライアントＣが、前述のように２Ｂｙｔｅｓのｘ１，ｘ２，ｘ３に対してエンコードを行いｄｂ１（ｂ１），ｄｂ２（ｂ２），ｄｂ３（ｂ３）を算出する。ちなみにｄｂ１，ｄｂ２，ｄｂ３もそれぞれ２Ｂｙｔｅｓである。
＜式（１）＞（ここで、式（ｎ）はまとまった複数の式を示す）
ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３＝ｂ１
ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３＝ｂ２
ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３＝ｂ３【００２６】
次にクライアントＣは最上層のサーバーＳ１．Ｓ２．Ｓ３にそれぞれｂ１．ｂ２．ｂ３を送信する（ｄｂ１の積み重ねからなるｂ１はＳ１に、ｄｂ２の積み重ねからなるｂ２はＳ２に、ｄｂ３の積み重ねからなるｂ３はＳ３に送信される）。  サーバーＳ１．Ｓ２．Ｓ３はそれらｂ１．ｂ２．ｂ３をそれぞれ保存しながら、次の層（２層目）のサーバーＳ４，Ｓ５，Ｓ６の三台に送信する。
次に、サーバーＳ４，Ｓ５，Ｓ６は、それぞれ受け取ったｂ１．ｂ２．ｂ３を元に新たに＜式（２）＞のようにエンコーディングを行い、
＜式（２）＞
ａ４．１ｂ１＋ａ４．２ｂ２＋ａ４．３ｂ３＝ｂ４
ａ５．１ｂ１＋ａ５．２ｂ２＋ａ５．３ｂ３＝ｂ５
ａ６．１ｂ１＋ａ６．２ｂ２＋ａ６．３ｂ３＝ｂ６【００２７】
新しく算出されたｂ４．ｂ５．ｂ６を各々保存しながら次の層のサーバーＳ７，Ｓ８に送信する。Ｓ７，Ｓ８は送られてきたｂ４．ｂ５．ｂ６をもとに以下の＜式３＞のようにエンコードしｂ７，ｂ８を求めそれらを保存する。
＜式３＞
ａ７．１ｂ４＋ａ７．２ｂ５＋ａ７．３ｂ６＝ｂ７
ａ８．１ｂ４＋ａ８．２ｂ５＋ａ８．３ｂ６＝ｂ８【００２８】
以上が、本実施例のリレーエンコーディングの概要であり、最上層の各サーバー（Ｓ１、Ｓ２、Ｓ３）はクライアントＣから一つだけデータを受け取り、そのサーバーではエンコードを行わずにデータを保存しながら次の層（２層目）のサーバー（Ｓ４．Ｓ５．Ｓ６）にデータを送信する。
次の層はその上の層の各サーバーから１つずつ（図示例では三つのデータ）を受け取り、それらをエンコードし新たに演算処理したデータを保存しながら次の下の層の各サーバーにそれを送信する。【００２９】
なお元のｘ１．ｘ２．ｘ３を基にｂ４．ｂ５．．．．．を見てみると、＜式（２）＞に＜式（１）＞を代入すると、
＜式（４）＞
ａ４．１（ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３）＋
ａ４．２（ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３）＋
ａ４．３（ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３）＝ｂ４
ａ５．１（ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３）＋
ａ５．２（ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３）＋
ａ５．３（ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３）＝ｂ５
ａ６．１（ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３）＋
ａ６．２（ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３）＋
ａ６．３（ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３）＝ｂ６
となる。【００３０】
これを変更すると以下の＜式（５）＞となる。
（ａ４．１ａ１．１＋ａ４．２ａ２．１＋ａ４．３ａ３．１）ｘ１＋
（ａ４．１ａ１．２＋ａ４．２ａ２．２＋ａ４．３ａ３．２）ｘ２＋
（ａ４．１ａ１．３＋ａ４．２ａ２．３＋ａ４．３ａ３．３）ｘ３＝ｂ４
（ａ５．１ａ１．１＋ａ５．２ａ２．１＋ａ５．３ａ３．１）ｘ１＋
（ａ５．１ａ１．２＋ａ５．２ａ２．２＋ａ５．３ａ３．２）ｘ２＋
（ａ５．１ａ１．３＋ａ５．２ａ２．３＋ａ５．３ａ３．３）ｘ３＝ｂ５
（ａ６．１ａ１．１＋ａ６．２ａ２．１＋ａ６．３ａ３．１）ｘ１＋
（ａ６．１ａ１．２＋ａ６．２ａ２．２＋ａ６．３ａ３．２）ｘ２＋
（ａ６．１ａ１．３＋ａ６．２ａ２．３＋ａ６．３ａ３．３）ｘ３＝ｂ６【００３１】
＜式（５）＞を以下の＜式（６）＞とすると
ａ４．１ａ１．１＋ａ４．２ａ２．１＋ａ４．３ａ３．１＝α４．１
ａ４．１ａ１．２＋ａ４．２ａ２．２＋ａ４．３ａ３．２＝α４．２
ａ４．１ａ１．３＋ａ４．２ａ２．３＋ａ４．３ａ３．３＝α４．３
ａ５．１ａ１．１＋ａ５．２ａ２．１＋ａ５．３ａ３．１＝α５．１
ａ５．１ａ１．２＋ａ５．２ａ２．２＋ａ５．３ａ３．２＝α５．２
ａ５．１ａ１．３＋ａ５．２ａ２．３＋ａ５．３ａ３．３＝α５．３
ａ６．１ａ１．１＋ａ６．２ａ２．１＋ａ６．３ａ３．１＝α６．１
ａ６．１ａ１．２＋ａ６．２ａ２．２＋ａ６．３ａ３．２＝α６．２
ａ６．１ａ１．３＋ａ６．２ａ２．３＋ａ６．３ａ３．３＝α６．３【００３２】
従って、前記＜式（５）＞は、以下の＜式（７）＞で表わすことができる。
α４．１ｘ１＋α４．２ｘ２＋α４．３ｘ３＝ｂ４
α５．１ｘ１＋α５．２ｘ２＋α５．３ｘ３＝ｂ５
α６．１ｘ１＋α６．２ｘ２＋α６．３ｘ３＝ｂ６【００３３】
また、エンコード時に同じ方程式が存在しないようにするには、まず＜式１＞において各方程式が独立し、なおかつ三元連立方程式において解が求まるようにａ１．１．ａ１．２．．．．．ａ３．３を＜式（８）＞のようにランダムに選択する。
例えば、＜式（８）＞
（ａ１．１、ａ１．２、ａ１．３）＝（８、３、４）
（ａ２．１、ａ２．２、ａ２．３）＝（９、１５、２）
（ａ３．１、ａ３．２、ａ３．３）＝（１３、６、５）
が選択されたとする。
次に、第２層におけるエンコーディング、＜式（２）＞における方程式も＜式（１）＞を含めて独立したものであるようにするために、＜式（７）＞に着目し、互いに独立になるようなα４．１．．．．．，α６．３を任意に選択する。【００３４】
例えば、＜式（９）＞
（α４．１、α４．２、α４．３）＝（１９、２３、５）
（α５．１、α５．２、α５．３）＝（８、４１、６）
（α６．１、α６．２、α６．３）＝（７、２、３３）
が選択されたとする。これら（＜式（８）＞と＜式９＞）を＜式６＞に代入すると、
例えば、＜式（１０）＞
８ａ４．１＋９ａ４．２＋１３ａ４．３＝１９
３ａ４．１＋１５ａ４．２＋６ａ４．３＝２３
４ａ４．１＋２ａ４．２＋５ａ４．３＝５
となり、別途ａ４．１．．．．．，ａ４．３を求めるための三元連立方程式が作られ、これを解くことによって＜式（２）＞におけるａ４．１．．．．．，ａ４．３が求められる。  同様にａ５．１．．．．．，ａ５．３．ａ６．１．．．．．，ａ６．３．．．．．に対して行えばリレーエンコーディングにおける係数を求めることができる。【００３５】
［デコード］
デコードは、まず目的のファイルを所有しているサーバーを探索する。
ファイルの探索において、もしファイルを所有しているサーバーの台数が３台未満であればデコードは失敗となる。
もし３台以上であればクライアントＣは、そのうち任意の３台のサーバーを選択し、まず３台のサーバーから全部の係数ａを記録した係数リストを含むヘッダー情報を取得し、次いで、エンコードされたデータをダウンロードする。
そして、２ｂｙｔｅｓに圧縮されたデータ前記ｂｘ毎に、以下の連立一次方程式からガウスの消去法を用いてｘ１、ｘ２、ｘ３を求め、これらを連結して６ｂｙｔｅｓ毎の元のデータｘ１、ｘ２、ｘ３に復元する（図４参照）。
ａ１．１ｘ１＋ａ１．２ｘ２＋ａ１．３ｘ３＝ｂ１
ａ２．１ｘ１＋ａ２．２ｘ２＋ａ２．３ｘ３＝ｂ２
ａ３．１ｘ１＋ａ３．２ｘ２＋ａ３．３ｘ３＝ｂ３【００３６】
この作業はファイルの末尾まで行われ，復元されたｘ１、ｘ２、ｘ３のデータをＸ１、Ｘ２、Ｘ３の３つのデータに復元し、このデータを組み合わせて元のファイルＸ０とすることでデコードが完了する。
このデコードの演算についても、エンコードと同様にガロア体（有限体）演算ライブラリを用いて演算される。【００３７】
［コンシステントハッシュ法によるファイル管理］
本実施例では、メタデータサーバーのような情報を管理する特別なサーバーを使用せず，コンシステントハッシュ法を用いて、どのサーバーが目的のファイルを持っているかなどの情報をクライアントが直接割り出すことができる。
例として４台のサーバーと、「ｔｅｓｔ．ｃ」、「Ｍａｋｅｆｉｌｅ」、「Ｒｅａｄｍｅ．ｔｘｔ」、「ＴＯＤＯ」の４つのファイルが存在するとする。
本実施例では、まず図６に見られるように、ハッシュ値を用いてリング上にサーバーを割り当てる。【００３８】
次いで同様に図７のようにリング上に前記ファイルを割り当てるが、各ファイルの所有者はそのファイルの位置から時計回りに最も近いサーバーとなる。
図７ではサーバーＳ３が、ファイルＴＯＤＯを所有することになる。
本実施例では、例えば図８のように、サーバーＳ５が追加されたとすると、ここでファイルの所有者が変更されるのは「ＴＯＤＯ」ファイルのみで、「ＴＯＤＯ」の新たな所有者はサーバーＳ５となるが、他のファイルは影響を受けないので、それらの際にファイルを所有するサーバーの変更が最低限で収まるようになっている。【００３９】
本実施例では、各サーバーＳ１、Ｓ２、３・・・Ｓｎが、それぞれクラスター内の全てのサーバーのホスト名のサーバーリストを保持している。
そして、クライアントが任意の１台のサーバーに接続した際に、前記サーバーリストを受け取る。
クライアントＣは、上記そのリストを元に、図６のようなハッシュリングを作り、図７〜図８のようにどのサーバーが目的のファイルを持っているかを割り出す。
本実施例では、最低３台のサーバーが目的のファイルを所有していなければならないが、割り出されたサーバーをＳ４とすると、他のサーバーに関してはサーバーリスト上にあるＳ４に続くサーバーＳ５．Ｓ６が所有しているものと見なす。【００４０】
サーバープログラムは、クライアントプログラムと通信し、データの送受信、読み込み、保存処理を行うプログラムと、ファイルのエンコード、デコード、サーバーヘのアップロード、サーバーからのダウンロード等を実行するプログラムと、サーバーに保存されたデータをファイルシステムとしてローカルなホストからアクセスできるようにするプログラムとを有している。
更に、ＪａｖａＳｃｒｉｐｔ（登録商標）からなるプログラムとして、エンコードされたデータをサーバーからダウンロードし、デコードを行いながら、データが動画であればウェブブラウザ上で再生を行うプログラムが用いられている。
これにより、エンコードされたデータが動画データの場合、ダウンロードはＸＭＬＨｔｔｐＲｅｑｕｅｓｔ関数を用いてＨＴＴＰで行い、動画再生にはＨＴＭＬ５の機能を使用して再生することができ、クラウドシステムや映像・音楽ストリーミングサービスのネットワークにおけるデータの保存量を減少させることが可能になった。
【符号の説明】
【００４１】
１  分散データシステム
２  係数決定手段
３  エンコード手段
４  分散保存手段
５  サーバー選択手段
６  デコード手段
７  再製手段
Ｓ１、Ｓ２、Ｓ３、・・・サーバー
Ｃ  クライアント
【要約】
元のファイルをＮ個の異なるブロックファイルに分けてＮ台以上の多数のサーバーに前記ファイルを分散配布する分散データシステムに関する。
【課題】元のファイルに対して１／Ｎの容量で多数のサーバーにデータを保存でき、デコードに際してはＮ台のサーバーを選択すればよい。
【解決手段】
元のファイルを同一間隔で区切り、区切られたデータをＮ個に再区切りし、該再区切りされたＮ個のデータにそれぞれ配布予定のサーバーに対応した前記係数を乗算してからその値を合算して１つのデータに圧縮するエンコード手段と、選択されたＮ台のサーバーからエンコードされたデータを集めてデコードし、それぞれのサーバーからＮ個のブロックファイルを求める一次方程式を取得するデコード手段とを有することを特徴とする。
【選択図】図１【図１】
0006300293.tif 000002
【図２】
0006300293.tif 000003
【図３】
0006300293.tif 000004
【図４】
0006300293.tif 000005
【図５】
0006300293.tif 000006
【図６】
0006300293.tif 000007
【図７】
0006300293.tif 000008
【図８】
0006300293.tif 000009
【図９】
0006300293.tif 000010