(57)【要約】      （修正有）【課題】一次データ群からＤＨＴへのデータの書き込みを効率的に行うことの可能なデータ登録装置を提供すること。【解決手段】各ＤＨＴノード３は、キーに対応付けられたデータを該キーのハッシュ値に基づいて分散記憶する。データ登録装置１は、入力部１５を介し一次データテーブル２から前記キーと前記データの元である一次データとを含む登録情報の系列を入力し、ハッシュ・ソート部１２にて、該系列の各登録情報につきキーのハッシュ値を計算し、該ハッシュ値に基づき、該系列における登録情報の順序を、同一のＤＨＴノード３に記憶すべき登録情報が連続する順序となるようにソートし、フィルタ部１３にて該系列の登録情報のうち再登録すべきもの以外を削除し、書込部１４にて該系列の各登録情報の対応するＤＨＴノード３への書き込みを、当該ソート順に従って行う。【選択図】図５
2009020757.tif 000002
【特許請求の範囲】
【請求項１】
キー情報に対応付けられたデータを該キー情報のハッシュ値に基づいて分散記憶する複数の分散ハッシュノード装置からなる分散ハッシュテーブルに該データを登録するデータ登録装置において、
前記キー情報と前記データの元である一次データとを含む登録情報の系列を入力する手段と、
入力された前記系列の各々の登録情報について、当該登録情報に係る前記キー情報のハッシュ値を計算するハッシュ手段と、
入力された前記系列における登録情報の順序が、同一の分散ハッシュノード装置に記憶すべき登録情報が連続する順序となるように、各登録情報に係る前記キー情報のハッシュ値に基づいて該系列における登録情報の順序をソートするソート手段と、
ソートされた前記系列に含まれる登録情報の全部又は一部を対象として、当該登録情報を記憶すべき前記分散ハッシュノード装置への当該登録情報の書き込みを、当該ソート順に従って行う書込手段とを備えたことを特徴とするデータ登録装置。
【請求項２】
前記書込手段は、
予め複数の前記分散ハッシュノード装置のうちから書き込み先として選択した分散ハッシュノード装置を示すノード情報を保持しておき、
前記系列のうちで書き込み対象となった前記登録情報の書き込みを行うにあたっては、まず、当該登録情報について前記ノード情報を書き込み先として前記書き込みを試行し、この結果、当該登録情報の書き込みに成功した場合は、前記系列において次に書き込むべき順位を持つ登録情報の書き込みに移り、一方、当該登録情報を記憶すべき分散ハッシュノード装置が、前記ノード情報の示す分散ハッシュノード装置とは異なるものであったために、当該登録情報の書き込みに失敗した場合は、前記ノード情報を他の分散ハッシュノード装置に変更した上で、当該登録情報について再度前記書き込みを試行することを特徴とする請求項１に記載のデータ登録装置。
【請求項３】
前記書込手段は、対象となった前記登録情報の書き込みに失敗した場合に、前記ノード情報が示す分散ハッシュノード装置又は他の分散ハッシュノード装置から、対象となった前記登録情報を記憶すべき分散ハッシュノード装置により近い分散ハッシュノード装置を示す情報を受信し、前記ノード情報を、受信した該正しい分散ハッシュノード装置を示す情報に変更することを特徴とする請求項２に記載のデータ登録装置。
【請求項４】
前記書込手段は、外部からコピー命令を受信した場合に、ソートされた前記系列に含まれる登録情報の全部を対象として、前記書き込みを行うことを特徴とする請求項１ないし３のいずれか1項に記載のデータ登録装置。
【請求項５】
前記書込手段が前記書き込みを行うのに先立って、ソートされた前記系列に含まれる各々の登録情報について、前記書き込みを行うか否かを選択する選択手段を更に備え、
前記書込手段は、ソートされた前記系列に含まれる登録情報のうち、前記選択手段により前記書き込みを行うことが選択されたものについてのみ、前記書き込みを行うことを特徴とする請求項１ないし３のいずれか1項に記載のデータ登録装置。
【請求項６】
前記分散ハッシュテーブルにおいて欠損されたデータに係るキー情報のハッシュ値のリスト情報を指示するメッセージを受信する手段を更に備え、
前記選択手段は、ソートされた前記系列に含まれる各々の登録情報について、該登録情報に係る前記キー情報のハッシュ値が前記リスト情報に含まれる場合に、前記書き込みを行うことを選択することを特徴とする請求項５に記載のデータ登録装置。
【請求項７】
前記選択手段は、ソートされた前記系列に含まれる各々の登録情報について、該登録情報に係る前記一次データの内容が更新されてから、未だ該登録情報の書き込みが行われていない場合に、前記書き込みを行うことを選択することを特徴とする請求項５に記載のデータ登録装置。
【請求項８】
前記登録情報は、該登録情報に係る前記一次データの最終更新時刻を示す情報をも含むものであり、
前記選択手段は、前記登録情報に含まれる最終更新時刻を示す情報が、前回の書き込みに関する時刻以降の時刻を示すものである場合に、前記書き込みを行うことを選択することを特徴とする請求項７に記載のデータ登録装置。
【請求項９】
前記書込手段は、前記書き込みにおいて、書き込み先となる分散ハッシュノード装置が変更になる際に、ランダムな待ち時間を設けることを特徴とする請求項１ないし８のいずれか1項に記載のデータ登録装置。
【請求項１０】
複数の前記分散ハッシュノード装置は、それぞれ、前記分散ハッシュテーブルにおいて使用されるハッシュ値空間から自装置に割り当てられた連続するハッシュ値の範囲に含まれるハッシュ値を与えるキー情報に係るデータを記憶するものであり、
前記ソート手段は、入力された前記系列における登録情報の順序を、該登録情報に係るキー情報のハッシュ値の昇順又は降順にソートすることを特徴とする請求項１ないし９のいずれか1項に記載のデータ登録装置。
【請求項１１】
前記書込手段は、ソートされた前記系列に含まれる各登録情報の前記書き込みを、ソートされた前記系列からランダムに選択した登録情報から開始することを特徴とする請求項１ないし１０のいずれか1項に記載のデータ登録装置。
【請求項１２】
前記書込手段は、一定期間毎に繰り返し、前記書き込みを行うことを請求項１ないし１１のいずれか1項に記載のデータ登録装置。
【請求項１３】
前記分散ハッシュテーブルのためのハッシュアルゴリズム及びソートアルゴリズムの情報を指示するメッセージを受信する手段を更に備え、
前記ハッシュ手段は、前記ハッシュアルゴリズムに従って、前記キー情報から前記ハッシュ値を計算し、
前記ソート手段は、前記ソートアルゴリズムに従って、前記系列における登録情報の順序をソートすることを特徴とする請求項１ないし１２のいずれか1項に記載のデータ登録装置。
【請求項１４】
キー情報に対応付けられたデータを該キー情報のハッシュ値に基づいて分散記憶する複数の分散ハッシュノード装置からなる分散ハッシュテーブルに該データを登録するデータ登録装置のデータ登録方法において、
前記キー情報と前記データの元である一次データとを含む登録情報の系列を入力するステップと、
入力された前記系列の各々の登録情報について、当該登録情報に係る前記キー情報のハッシュ値を計算するステップと、
入力された前記系列における登録情報の順序が、同一の分散ハッシュノード装置に記憶すべき登録情報が連続する順序となるように、各登録情報に係る前記キー情報のハッシュ値に基づいて該系列における登録情報の順序をソートするステップと、
ソートされた前記系列に含まれる登録情報の全部又は一部を対象として、当該登録情報を記憶すべき前記分散ハッシュノード装置への当該登録情報の書き込みを、当該ソート順に従って行うステップとを有することを特徴とするデータ登録方法。
【請求項１５】
キー情報に対応付けられたデータを該キー情報のハッシュ値に基づいて分散記憶する複数の分散ハッシュノード装置からなる分散ハッシュテーブルに該データを登録するデータ登録装置としてコンピュータを機能させるためのプログラムにおいて、
前記キー情報と前記データの元である一次データとを含む登録情報の系列を入力する手段と、
入力された前記系列の各々の登録情報について、当該登録情報に係る前記キー情報のハッシュ値を計算するハッシュ手段と、
入力された前記系列における登録情報の順序が、同一の分散ハッシュノード装置に記憶すべき登録情報が連続する順序となるように、各登録情報に係る前記キー情報のハッシュ値に基づいて該系列における登録情報の順序をソートするソート手段と、
ソートされた前記系列に含まれる登録情報の全部又は一部を対象として、当該登録情報を記憶すべき前記分散ハッシュノード装置への当該登録情報の書き込みを、当該ソート順に従って行う書込手段とをコンピュータに機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散ハッシュテーブルへのデータの登録を行うデータ登録装置、データ登録方法及びプログラムに関する。
【背景技術】
【０００２】
Ｃｈｏｒｄ方式（非特許文献１）やＴａｐｅｓｔｒｙ方式（非特許文献２）などといった分散ハッシュテーブル（Distributed Hash Table，ＤＨＴ）を代表とする大規模分散ストレージシステムにおいては、ストレージシステム上で取り扱うデータはソフトステート的に保持されることが多い（非特許文献３）。つまり、ストレージシステム上でのデータの保持は一定期間しか保証されず、一次データを所有するデータ源（分散して存在するクライアント）が必要に応じて再び書きこむ必要がある。
【０００３】
一次データを全てソフトステート的にＤＨＴ上で保持する場合、ＤＨＴのシステム規模が大きくなり、データ量が大きくなると、データ量に比例して維持すべきステートおよびリフレッシュのための通信が増加してしまい、スケールしない。他方、ソフトステートを用いずに、ＤＨＴ側にデータの保持を任せると、ＤＨＴノードの故障などでデータが失なわれる可能性がある。さらに、ＤＨＴからのバックアップあるいはマイグレーションを行う際には、ＤＨＴが期待するデータ量を保管しなければならないので、素直にリニアなバックアップを行うと時間がかかりすぎることから、ＤＨＴへのバックアップあるいはマイグレーションを行うことが自然であるが、このとき効率的に一方のＤＨＴの内容を他方のＤＨＴにコピーする方法が存在しなかった。
【非特許文献１】I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of ACM SIGCOMM, August 2001.
【非特許文献２】Ben Y. Zhao, John D. Kubiatowicz, and Anthony D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB//CSD-01-1141, U.C.Berkeley, April 2000.
【非特許文献３】Sean Rhea, Brighten Godfrey, Brad Karp, John Kubiatowicz, Sylvia Ratnasamy, Scott Shenker, Ion Stoica, and Harlan Yu. OpenDHT: A public DHT service and its uses. In Proceedings of ACM SIGCOMM 2005, August 2005.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来、一次データ群からＤＨＴへのデータの書き込み或いは第１のＤＨＴから第２のＤＨＴへのデータの書き込みを行う効果的な方法がなかった。
【０００５】
本発明は、上記事情を考慮してなされたもので、一次データ群からＤＨＴへのデータの書き込み或いは第１のＤＨＴから第２のＤＨＴへのデータの書き込みを効率的に行うことの可能なデータ登録装置、データ登録方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、キー情報に対応付けられたデータを該キー情報のハッシュ値に基づいて分散記憶する複数の分散ハッシュノード装置からなる分散ハッシュテーブルに該データを登録するデータ登録装置において、前記キー情報と前記データの元である一次データとを含む登録情報の系列を入力する手段と、入力された前記系列の各々の登録情報について、当該登録情報に係る前記キー情報のハッシュ値を計算するハッシュ手段と、入力された前記系列における登録情報の順序が、同一の分散ハッシュノード装置に記憶すべき登録情報が連続する順序となるように、各登録情報に係る前記キー情報のハッシュ値に基づいて該系列における登録情報の順序をソートするソート手段と、ソートされた前記系列に含まれる登録情報の全部又は一部を対象として、当該登録情報を記憶すべき前記分散ハッシュノード装置への当該登録情報の書き込みを、当該ソート順に従って行う書込手段とを備えたことを特徴とする。
【発明の効果】
【０００７】
本発明によれば、一次データ群からＤＨＴへのデータの書き込み或いは第１のＤＨＴから第２のＤＨＴへのデータの書き込みを効率的に行うことができる。
【発明を実施するための最良の形態】
【０００８】
以下、図面を参照しながら本発明の実施形態について説明する。
【０００９】
（第１の実施形態）
図１に、本発明の一実施形態に係る分散ハッシュテーブルシステムの構成例を示す。
【００１０】
図１において、１はデータ登録装置、２は一次データテーブル、３はＤＨＴノード、８はネットワークである。
【００１１】
複数台のＤＨＴノード３が連携して、１つの分散ハッシュテーブル３０を構成する。分散ハッシュテーブル３０を構成するＤＨＴノードの台数は任意である。また、この台数は、ＤＨＴノードの参加・離脱によって、動的に変動し得るものである。
【００１２】
各ＤＨＴノード３は、自身が担当するハッシュ値に該当するハッシュ値を与えるキー情報について、図２に例示するようにキー情報（ｋｅｙ）とデータ（ｄａｔａ：１又は複数のｖａｌｕｅ）とを対応付けて保持しており、クライアント装置（図示せず）により送信された、キー情報が指定された問い合せメッセージを受信した場合に、これに応答して、該キー情報のハッシュ値を求め、該ハッシュ値が自身の担当するハッシュ値であれば、該キー情報に対応して記憶しているデータを含む応答メッセージを該クライアント装置へ返送する。自身の担当するハッシュ値でなければ、例えば、その問い合せメッセージを他のＤＨＴノード３へ転送するか、より適切なＤＨＴノード３への参照として、ＩＰアドレスとポート番号の組合せやＵＲＬなどを返送する。
【００１３】
なお、ＤＨＴノード３については、自ノードに関する情報の管理、参加・離脱制御、隣接ノードに関する情報の管理、データベースの管理、自ノードの属するハッシュ空間上の任意のハッシュ値を担当するＤＨＴノードの検索、クライアント装置からの問い合わせメッセージに対する手続などは、基本的には、従来からある方法を用いて構わない。
【００１４】
一次データテーブル群２０の個々の一次データテーブル２は、それぞれ、図３に例示するように、分散ハッシュテーブル３０に登録すべきデータの元（データ源）となる多様な一次データ（ｖａｌｕｅ）を、そのキー情報（ｋｅｙ）に対応付けて保持する。一次データテーブル２の数は任意である。なお、同一のキー情報を持つ一次データが、複数の一次データテーブル２に渡って保持されることもある。
【００１５】
なお、一次データテーブル群２０はどのような構成であってもよく、例えば、一次データテーブル群２０の個々の一次データテーブル２が通常の独立したデータベースであってもよいし、複数の一次データテーブル２がもう１つの分散ハッシュテーブル３０を構成するものであってもよい。
【００１６】
データ登録装置１は、一次データテーブル２の保持する一次データを、当該一次データを担当するＤＨＴノード３に登録する（すなわち、各一次データは、これに対応するキー情報のハッシュ値を担当するＤＨＴノード３に登録される）。なお、ここでは、データ登録装置１は、個々の一次データテーブル２に対応して一つずつ設けられるものとする。一対のデータ登録装置１と一次データテーブル２とは、互いに独立した装置であってもよいし、一体化した装置であってもよい。
【００１７】
１つの分散ハッシュテーブル３０を構成する複数のＤＨＴノード３は、ネットワーク８を介して、相互に通信可能である。また、各データ登録装置１は、ネットワーク８を介して任意のＤＨＴノード３と通信可能である。なお、ネットワーク８は、どのようなネットワークでもよい。ここでは、一例としてネットワーク８がインターネットである場合を例にとって説明する。
【００１８】
さて、図１に例示する分散ハッシュテーブルシステムは、例えばトレーサビリティ応用などに用いるサービス構成（例えば文献「尾崎哲, 土井裕介, 若山史郎. 小規模から円滑に拡張できる商品トレーサビリティシステム. 東芝レビュー, Vol.60, No.8, pp.27-31, 2005.」）に適うものである。以下では、本分散ハッシュテーブルシステムを、個品トレーサビリティシステムの構築に利用する場合を例にとって説明するものとする。
【００１９】
個品トレーサビリティシステムに適用する場合には、例えば、一次データテーブル群２０の各一次データテーブル２は、個品ごとの一次データとしての「その個品に関連する情報（例えば、品質情報等）を提供するサーバ装置の情報（例えば、ＵＲＬ）」を、そのキー情報としての「その個品に固有の識別情報（以下、タグＩＤと呼んで説明するものとする）」に対応付けて保持し、分散ハッシュテーブル３０の各ＤＨＴノード３は、ルックアップ等に用いるインデックス用のテーブルに、二次データとしての（１又は複数の）上記ＵＲＬ等をタグＩＤと対応付けて保持する。なお、この場合、ＵＲＬ等は、図１の一次データテーブル２を持つノードを示すものであってもよいし、他のサーバ装置を示すものであってもよい。
【００２０】
図４に、個品毎に付与されるタグＩＤの一例として、ＥＰＣｇｌｏｂａｌにおけるＧＩＤ−９６（EPCglobal. EPC tag data standards version 1.3. EPCglobal Ratified Specification, March 2006.）を示す。この場合、タグＩＤは、会社ＩＤ・商品種別ＩＤ・個品ＩＤの３階層からなる。なお、この場合、ＤＨＴは、例えば、会社毎あるいは会社及び商品種別毎などに設けられるが、これに限定されるものではない。
【００２１】
このような個品トレーサビリティシステムにおいては、例えば、ある商品（個品）に関する情報を取得・閲覧したいユーザ（例えば消費者）は、クライアント装置（図示せず）から、その個品のタグＩＤを指定した問い合わせメッセージを、分散ハッシュテーブル３０（のいずれかのＤＨＴノード３）に送信し、分散ハッシュテーブル３０からＵＲＬ等のリストを取得した後に、さらに、取得したＵＲＬ等をもとに所定のサーバ装置に問い合わせメッセージを送信することによって、該個品に関する具体的な情報（例えば温度管理履歴等）を取得する、といった動作が行われる。
【００２２】
ここで、分散ハッシュテーブル３０は、ノード故障などにより、インデックス用のテーブル（タグＩＤ：［ＵＲＬ，…］）の一部を失うことがある。その際、特定のＤＨＴノード３の保持するデータの一部が壊れるケースや、特定のＤＨＴノード３が故障して（離脱が生じて）、そのＤＨＴノード３が保持していたデータが全て失われるケースなどがある。
【００２３】
前者の場合には、その壊れたデータをそのＤＨＴノード３に再登録することで復旧できる。
【００２４】
後者の場合には、その故障したＤＨＴノード３が保持していたデータを、他のＤＨＴノード３に再登録することで復旧できる。どのＤＨＴノード３が故障した場合に、どのＤＨＴノード３を用いて復旧させるかは、予め決めておくのが望ましい。一例として、Ｃｈｏｒｄのように、ハッシュ値の集合で構成されるハッシュ空間において、両端が連結された閉じた数直線としてハッシュ空間が形成される場合を考える（例えば、各ＤＨＴノード３にハッシュ値（例えばＤＨＴノードのアドレスのハッシュ値）が割り当てられ、各ＤＨＴノード３の担当するハッシュ値の範囲（上限値及び下限値）は、各ＤＨＴノード３に割り当てられたハッシュ値に基づいて決せられる）と、この場合、例えば、或るＤＨＴノード３が故障した場合に、そのＤＨＴノード３が保持していたデータを、ハッシュ空間上でハッシュ値の増加方向でそのＤＨＴノード３に最も近いノード（サクセッサー）、あるいは、ハッシュ空間上でハッシュ値の減少方向でそのＤＨＴノード３に最も近いノード（プレデセッサー）が、以降、それら欠損したデータをも保持するものと予め決めておくことができる。
【００２５】
なお、ハッシュ値を計算するためのハッシュ関数としては、ビット数が充分長くて一様な割り当てが行なわれる関数として、例えば、ＳＨＡ−１やＭＤ５を採用することができる。ハッシュ空間は、ＳＨＡ−１の場合は、ｍ＝１６０とし、ＭＤ５の場合は、ｍ＝１２８として、０〜２ｍ−１のｍビットの整数で表わされる。
【００２６】
また、各ＤＨＴノード３に対応付けるハッシュ値の決め方としては、例えば、当該ＤＨＴノード３の持つアドレス（例えばＩＰアドレス）に対してハッシュ関数を適用して得られるハッシュ値を用いる方法を採用してもよいし、他の方法を採用してもよい。
【００２７】
本実施形態のデータ登録装置１は、上記のデータが欠損した領域（故障領域）を検出し、これを復元するものである。
【００２８】
以下、本実施形態のデータ登録装置１について詳しく説明する。
【００２９】
図５に、本実施形態に係るデータ登録装置１の構成例を示す。図４に示されるように、データ登録装置１は、指示受信部１１、ハッシュ・ソート部１２、フィルタ部１３、書込部１４、入力部１５を備えている。
【００３０】
指示受信部１１は、ネットワーク８を介して、対象となる分散ハッシュテーブル３０における故障領域を示す情報（故障領域情報）、該分散ハッシュテーブル３０で使用すべきハッシュアルゴリズム、同一のＤＨＴノード３の担当するハッシュ値が連続するようにソートするためのソートアルゴリズムを含む登録指示メッセージを受信し、それらを蓄積するためのものである。
【００３１】
なお、上記ハッシュアルゴリズム及びソートアルゴリズムについては、例えば、事前にパラメータの組み合わせを表記する方法を定義して、登録指示メッセージに該パラメータを記述するようにしてもよいし、Ｊａｖａ（登録商標）等のプラットフォームにある動的なオブジェクト読み込み手段を用いるようにしてもよい。
【００３２】
また、上記ハッシュアルゴリズム及びソートアルゴリズムは、登録指示メッセージに含めず、個々のデータ登録装置１においてそれぞれ設定するようにしてもよい。
【００３３】
故障領域情報は、例えば、故障したデータのキー情報（ｋｅｙ）のハッシュ値（ｈ（ｋｅｙ））のリストである。なお、該リストのフォーマットは、どのようなものでもよく、例えば、全ハッシュ値を列記する方法で記述してもよいし、ハッシュ値の始点と終点との組を列記する方法で記述してもよいし、それらを併用してもよい。
【００３４】
なお、指示受信部１１が登録指示メッセージを受信できるようにする方法には種々のバリエーションが可能である。
【００３５】
例えば、分散ハッシュテーブル３０全体で、故障した領域を記録する故障領域リストというテーブルを共有するものとし（例えば、ＤＨＴノード３以外の管理ノード（図示せず）を１台設け、これに故障領域リストを保持させるものとし）、各ＤＨＴノード３は、定期的に、自装置が故障領域を持つかどうか調べ、故障領域を持つ場合に、故障領域リストに、故障領域のエントリ（故障領域の始点，故障領域の終点）を書き加えるものとする。
【００３６】
なお、例えば、或るＤＨＴノード３が故障して離脱した場合には、該或るＤＨＴノード３は、故障領域のエントリを書き加えることはできないことになるが、該或るＤＨＴノード３の代わりとなるべきＤＨＴノード３（例えば、サクセッサーあるいはプレデセッサー）が、該或るＤＨＴノード３の離脱を検出した以降に、該或るＤＨＴノード３が保持すべきデータが全て欠損したものとして、故障領域のエントリを書き加えることができるようになる。また、主として耐故障性の向上のために、或るＤＨＴノード３の担当するデータと同じ内容(ミラー)を、常時、該或るＤＨＴノード３が故障して離脱した際に該或るＤＨＴノード３の代わりとなるべきＤＨＴノード３（例えば、サクセッサーあるいはプレデセッサー）が保持するようにする場合には、該代わりとなるべきＤＨＴノード３が、該或るＤＨＴノード３の離脱を検出した以降に、該或るＤＨＴノード３の担当するデータのうちに故障領域があれば、これを故障領域のエントリを書き加えることができるようになる。また、後述する時刻によるバックアップ指示と同様に、ミラーの最終更新時刻をもとにしたデータ復元を行うために、故障領域のエントリに時刻情報を追記してもよい。この場合は、該故障領域に含まれるデータのうち、エントリに記録された時刻よりも新しいデータが失われた可能性があることを意味する。
【００３７】
そして、データ登録装置１は、定期的に、上記管理ノードに、故障領域に関する問い合わせメッセージを送信し、これを受信した該管理ノードが、該故障領域リストを登録指示メッセージに含めて、そのデータ登録装置１に返送するようにしてもよい。
【００３８】
あるいは、管理ノードが、定期的に、該故障領域リストを含む登録指示メッセージを全データ登録装置１にブロードキャストするようにしてもよい。
【００３９】
なお、上記では、ＤＨＴノード３以外の管理ノードを１台設けるものとしたが、管理ノードを複数台設けてもよいし、管理ノードの代わりに又はこれに加えて、1又は複数のＤＨＴノード３に、管理ノードの役割を担わせてもよい。また、故障領域リストを保持する管理ノード等が複数設けられる場合には、データ登録装置１は、それらのうちのいずれか一つに故障領域に関する問い合わせメッセージを送信すればよい。また、管理ノードが、定期的に、該故障領域リストを含む登録指示メッセージをデータ登録装置１に送信するようにする場合には、管理ノード等が複数設けられるときは、それらノードが、登録指示メッセージを送信すべきデータ登録装置１を分担してもよい。
【００４０】
また、管理ノード等を複数設ける場合に、各管理ノード等で、故障領域リストの対象とするＤＨＴノード３を分担することも可能である。
【００４１】
ところで、修復されたデータの情報が、故障領域リストいつまでも残るのを避けるために、故障領域リスト内の各エントリは、時間ｔで期限切れとなるようにするのが好ましい。ただし、個々のデータ登録装置１は、自身がデータを持つタグＩＤに対応するデータが欠損になれば、これを復元しなければならないので、復元より先に期限切れが発生して復元し損なうことを回避するために、上記管理ノード等に、時間ｔよりも短かい間隔で故障領域に関する問い合わせを行って、故障領域リストを確実に取得して、故障したデータを更新するようにするのが好ましい。また、管理ノード等が、定期的に、該故障領域リストを含む登録指示メッセージをデータ登録装置１に送信するようにする場合には、時間ｔよりも短かい間隔で登録指示メッセージを送信するのが好ましい。
【００４２】
ハッシュ・ソート部１２は、書き込み対象とする分散ハッシュテーブル３０の持つハッシュ値空間の連続性を考慮して効率的な書き込みを行うために、分散ハッシュテーブル３０のハッシュ値空間の連続性に沿って一次データ源のデータをソートする。
【００４３】
ハッシュ・ソート部１２は、入力部１５を介して、対応する一次データテーブル２から、それが保持する全てのエントリ（ｋｅｙ，ｖａｌｕｅ）を、任意の順序の（ｋｅｙ，ｖａｌｕｅ）の系列として入力し、該（ｋｅｙ，ｖａｌｕｅ）の系列の各々のエントリについて、指示されたハッシュアルゴリズムに従って、キー情報ｋｅｙのハッシュ値ｈ（ｋｅｙ）を計算して、（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）を求め、全（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）を、指示されたソート・アルゴリズムに従ってソートして、ソートされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列を作成する。
【００４４】
例えば、複数のＤＨＴノード３が、それぞれ、分散ハッシュテーブル３０において使用されるハッシュ値空間から自装置に割り当てられた連続するハッシュ値の範囲に含まれるハッシュ値を与えるキー情報に係るデータを記憶するものである場合に、ソート・アルゴリズムは、該分散ハッシュテーブル３０において使用されるハッシュ値空間の順序に従って書き込みが行われるようにソートするものである。
【００４５】
具体例として、例えば、Ｃｈｏｒｄに従う分散ハッシュテーブル３０において、ハッシュアルゴリズムをＭＤ５あるいはＳＨＡ−１とし、ソート・アルゴリズムを昇順若しくは降順又はランダムスタートの昇順若しくはランダムスタートの降順などとすることができる。
【００４６】
なお、ランダムスタートのソート・アルゴリズムは、データの書き込みが特定のＤＨＴノード３に集中しないように、書き込みを開始するＤＨＴノード３がランダムになるようにするために、ランダムに選択したハッシュ値が先頭になるようにソートするものである。例えばＣｈｏｒｄのような分散ハッシュテーブルアルゴリズムでは、ハッシュ値の空間は閉じた数直線で表現され、前後関係のみが定義される。従って、数直線のどこから書き込みを開始してもハッシュ値空間を一周することにより、漏れなく全てのｖａｌｕｅを書き込むことができる。
【００４７】
フィルタ部１３は、ハッシュ・ソート部１２から書込部１４に与えられた、ソートされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列を対象として、指示された「故障領域情報」に基づいて、フィルタリングを行う。すなわち、故障領域情報には、再登録すべきデータのハッシュ値が記述されているので、ソートされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列から、再登録すべきデータ以外のものを削除する（すなわち、ｈ（ｋｅｙ）が故障領域情報に記述されていない（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）を削除すればよい）。
【００４８】
なお、このフィルタ部１３は、ハッシュ・ソート部１２と書込部１４との間に設けてもよい。
【００４９】
書込部１４は、書き込み対象とする分散ハッシュテーブル３０の持つハッシュ値空間の連続性とＤＨＴノード３の担当領域を判断しながら、データをかたまり（バルク）単位で書き込む。
【００５０】
書込部１４は、ネットワーク８を介して、ソート及びフィルタリングされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列の各登録情報（ｋｅｙ，ｖａｌｕｅ）を、先頭から（もしくは、ランダムな位置から）順に、分散ハッシュテーブル３０（の該当するＤＨＴノード３）へ書き込むものである。
【００５１】
なお、ランダムな位置から開始するのは、データの書き込みが特定のＤＨＴノード３に集中しないようにするためである。また、遅いＤＨＴノード近辺で輻輳をおこさないように、書きこみの速度（書き込み先ノードの変更の時間間隔など）に一定の制約をかける（例えば、ランダムな待ち時間を設ける）ようにしてもよい。
【００５２】
図６に、データ登録装置１の処理手順の一例を示す。
【００５３】
データ登録装置１は、一定期間の間に受信された登録指示メッセージに含まれる（対象となる分散ハッシュテーブル３０における）故障領域情報（例えば、故障領域リスト）と、ハッシュアルゴリズムと、ソートアルゴリズムとを抽出し、これらを指示受信部１１に伝えることで、復元動作をトリガする（ステップＳ１)。
【００５４】
なお、ステップＳ２で新たな故障領域情報が検出されなかった場合（一定期間の間に登録指示メッセージが受信されなかった場合を含む）は、以降の処理をスキップしてステップＳ１に戻る。
【００５５】
さて、ステップＳ２で新たな故障領域情報が検出された（例えば、故障領域リストに新規に書き加えられた故障領域情報が存在する）場合は、その領域（故障領域の始点、故障領域の終点）をフィルタ部１３にセットし、上記ハッシュアルゴリズム及びソートアルゴリズムをハッシュ・ソート部１２にセットした後に、データの復元を開始する。
【００５６】
まず、ハッシュ・ソート部１２は、一次データ源である一次データテーブル２から、対象となる分散ハッシュテーブル３０に書き込むべき（ｋｅｙ，ｖａｌｕｅ）形式のデータの（任意の順序の）列を受信し、セットされたハッシュアルゴリズムｈを利用してｈ（ｋｅｙ）を計算して（ステップＳ３）、（ｋｅｙ，ｖａｌｕｅ）の列を（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列に変換した後に、セットされたソートアルゴリズムに従ってソートを行う（ステップＳ４)。ソートされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列は、同一のＤＨＴノード３の担当するハッシュ値が連続するようにソートされるので（例えば、ｃｈｏｒｄの場合は、ｈ（ｋｅｙ）がハッシュ値空間上で連続するようにソートされるので）、書込部１４により効率的に書き込むことができる。
【００５７】
次に、書込部１４は、書き込むべきデータをフィルタ部１３に問合せ、フィルタ部１３は、セットされた故障領域情報に基づいてフィルタリングを行い（すなわち、ソートされた（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列から、故障領域情報にｈ（ｋｅｙ）が含まれないエントリを削除し）、書き込むべきデータ（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列を書込部１４に返し（ステップＳ５）、書込部１４は、フィルタリング及びソートされたデータ（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）の列における各（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）を対象として、書き込みを行う（ステップＳ６）。なお、フィルタ部１３から書込部１４へは、ｈ（ｋｅｙ）でソートされた（ｋｅｙ，ｖａｌｕｅ）を返してもよい。
【００５８】
図７に、ステップＳ６の書き込みの処理手順の一例を示す。
【００５９】
まず、対象となる分散ハッシュテーブル３０のうちから、適当なＤＨＴノード３を一つ選択して設定する（ステップＳ１１）。
【００６０】
次に、フィルタリング及びソートされたデータ（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）（あるいは、（ｋｅｙ，ｖａｌｕｅ））の列を対象として、未だ書き込みが完了していないデータ（ｋｅｙ，ｖａｌｕｅ）のうち、最もソート順の早いものを一つ選択し、（ｋｅｙ，ｖａｌｕｅ）を含む書き込みメッセージを現在設定されているＤＨＴノード３へ送信することによって、当該データ（ｋｅｙ，ｖａｌｕｅ）の書き込みを試行する（ステップＳ１２）。
【００６１】
ここで、データ登録装置１から、書き込むべき（ｋｅｙ，ｖａｌｕｅ）を含む書き込みメッセージを受信したＤＨＴノード３は、そのｋｅｙから計算したハッシュ値ｈ（ｋｅｙ）が自装置の担当するものであれば、該（ｋｅｙ，ｖａｌｕｅ）を自装置に登録する。ｈ（ｋｅｙ）が自装置の担当するものでなければ、該ＤＨＴノード３又は他のＤＨＴノード３等が、該ハッシュ値ｈ（ｋｅｙ）を担当するＤＨＴノード３により近いＤＨＴノード３（担当するＤＨＴノード３を含む）を解決して、該より近いＤＨＴノード３を指示するリダイレクトメッセージを、データ登録装置１へ返すものとする。
【００６２】
なお、例えば、各ＤＨＴノード３が、自装置が担当する一連のハッシュ値の直後に位置するＤＨＴノード（後続ＤＨＴノード）を記憶しておき、ハッシュ値ｈ（ｋｅｙ）が自装置の担当範囲にない（ｋｅｙ，ｖａｌｕｅ）を含む書き込みメッセージを受信したＤＨＴノード３は、この後続ＤＨＴノードの情報をリダイレクトメッセージに含めて返信するようにしてもよい。この場合、後続ＤＨＴノードが正しいものであれば、次の書き込みに成功するが、正しいものでなければ、書き込みに成功するまで、次々とリダイレクトメッセージが返信される。もちろん、ハッシュ値ｈ（ｋｅｙ）が自装置の担当範囲にない（ｋｅｙ，ｖａｌｕｅ）を含む書き込みメッセージを受信したＤＨＴノード３が、当該ハッシュ値を担当する正しいＤＨＴノードを他のＤＨＴノード３に問い合わせメッセージを送信するなどして、該正しいＤＨＴノードを解決した上で、該書き込みメッセージを受信したＤＨＴノード３あるいは該問い合わせメッセージを受信したＤＨＴノード３等が、正しいＤＨＴノードを示す情報をリダイレクトメッセージに含めて返信するようにしてもよいし、他の方法を用いてもよい。
【００６３】
リダイレクションが発生すれば（ステップＳ１３）、上記ＤＨＴノード３から返された上記データを書き込むべき正しいＤＨＴノード３を設定し直し（ステップＳ１１）、あらためて上記データの書き込みを行う（ステップＳ１２）。
【００６４】
リダイレクションが発生せず、書き込みに成功すれば（ステップＳ１３）、ソート順で次のデータの書き込みを試行する（ステップＳ１２）。
【００６５】
なお、上記ソートによって、同一のＤＨＴノード３に書き込むべきデータが複数ある場合には、それらは連続する順番にソートされるので、次に書き込むべきＤＨＴノード３が変わるまで、ステップＳ１２の書き込みは連続して成功することになる。
【００６６】
以上の処理は、ステップＳ１４で次のデータが有る間、繰り返され、すべてのデータが書き込まれると、処理が終了となる。
【００６７】
なお、図６及び図７の例では、ステップＳ５で全データについてフィルタリングを完了した後に、ステップＳ６で書き込みを行うようにしたが、図７のステップＳ１２において、データを一つ選択した際に、このデータにフィルタリングをかけて（すなわち、故障領域情報に基づいて書き込むべきデータか否か調べて）、書き込むべきデータである場合に、書き込むものとし、書き込むべきデータでない場合には、ステップＳ１４に遷移することを、繰り返し行うようにしてもよい。
【００６８】
以下、より具体的な書き込みの手順例について説明する。
【００６９】
例えばＣｈｏｒｄの場合は、ＳＨＡ１により定義される閉じた１６０ビット１次元のハッシュ値空間となり、１次元空間上の一定の領域を一定のＤＨＴノードが管理する。もし、ソートしないデータ列の書き込みを行った場合は、Ｃｈｏｒｄアルゴリズムに基づくＤＨＴノード探索が書き込み毎に実行され、効率が悪くなるが、本実施形態では、ハッシュ・ソート部１２により、書き込み先の分散ハッシュテーブル３０のハッシュ値空間の連続性に沿った順序のデータ列で書き込みを行うことによって、特定のＤＨＴノードが担当する領域への書き込みをまとめられるようになり、探索のコストを削減できる。同様に、当該範囲への書き込みが終了し、次のデータエントリを書き込む先を探索する場合も、ハッシュ値空間の連続性に基づき書き込み先を移動するだけでよい。
【００７０】
なお、上記において、分散ハッシュテーブル３０を構成する各ＤＨＴノード３は、自身が担当するハッシュ値に該当するハッシュ値を与えるキー情報について、キー情報（ｋｅｙ）とデータ（ｄａｔａ：１又は複数のｖａｌｕｅ）とを対応付けて保持し、クライアント装置からのキー情報を指定した問い合せメッセージに応答して、該キー情報に対応して記憶しているデータを含む応答メッセージを返送するものとしたが、その代わりに、各ＤＨＴノード３は、キー情報のハッシュ値（ｈ（ｋｅｙ））とデータ（ｄａｔａ：１又は複数のｖａｌｕｅ）とを対応付けて保持し、クライアント装置からのキー情報のハッシュ値を指定した問い合せメッセージに応答して、該キー情報のハッシュ値に対応して記憶しているデータを含む応答メッセージを返送するものであってもよい。この場合には、各実施形態において、データ登録装置１は、キー情報（ｋｅｙ）からハッシュ値ｈ（ｋｅｙ）を計算した後は、（ｈ（ｋｅｙ），ｖａｌｕｅ）を扱えばよい（キー情報（ｋｅｙ）は扱わなくて構わない）。また、ＤＨＴノード３へ送信する書き込みメッセージには、（ｋｅｙ，ｖａｌｕｅ）の代わりに（ｈ（ｋｅｙ），ｖａｌｕｅ）を付加すればよい。この点は、第２、第３の実施形態についても同様である。
【００７１】
図８に、ｐｓｅｕｄｏｃｏｄｅによる書き込みのアルゴリズム例を示す。なお、このアルゴリズム例は、図６のステップＳ４のフィルタリングとステップＳ５の書き込みを一体化したものである。なお、図６において、／／で始まる文はコメント文である。
【００７２】
このアルゴリズム例において、ＴｕｐｌｅＳｔｒｅａｍはＴｕｐｌｅのイテレータであり、Ｔｕｐｌｅはｈｋｅｙとｖａｌｕｅの組み合わせである。ｈｋｅｙはｈ（ｋｅｙ）に相当する、一次データ側の（ｋｅｙ，ｖａｌｕｅ）に対するｈ（ｋｅｙ）である。ｓｏｒｔｅｄ＿ｓｏｕｒｃｅは、（フィルタリングされる前の）ソートされた（ｈ（ｋｅｙ），ｖａｌｕｅ）である。
【００７３】
ＴｕｐｌｅＦｉｌｔｅｒは、（ｈ（ｋｅｙ），ｖａｌｕｅ）を対象とする、故障領域情報に基づくフィルタである。
【００７４】
ＤＨＴＮｏｄｅは、対象となる分散ハッシュテーブル３０のＤＨＴノード３を代表するクラスである。ｎｐｔｒは、ＤＨＴノード３の１つのノードを示すＤＨＴＮｏｄｅのインスタンスへのポインタであり、ＵＲＬあるいはＩＰアドレス等を含む。
【００７５】
ｎｐｔｒ．ｐｕｔ（ｔ．ｈｋｅｙ，ｔ．ｖａｌｕｅ）は、一つの（ｈ（ｋｅｙ），ｖａｌｕｅ）をｎｐｔｒが示すＤＨＴノード３へ書き込む。なお、ここでは、ｈ（ｋｅｙ）を送信する場合について記述しているが、ｋｅｙを送信する場合には、ｔ．ｈｋｅｙをｔ．ｋｅｙとすればよい。
【００７６】
ＤＨＴノード３は、自装置の担当する範囲外への書き込み要求については、ＲｅｄｉｒｅｃｔＥｘｃｅｐｔｉｏｎとともにより正しいと考えられるＤＨＴＮｏｄｅへの参照を返す。ｃａｔｃｈは、これを受信するものである。ｎｐｔｒ＝ｒｅ．ｒｅｄｉｒｅｃｔｅｄ＿ｔｏは、返されたＤＨＴノード３のＵＲＬあるいはＩＰアドレス等から生成されたＤＨＴＮｏｄｅのインスタンスをｎｐｔｒにセットする。
【００７７】
ここで、対象となる分散ハッシュテーブル３０の故障領域情報（故障領域リスト）の発見と広告は、ＤＨＴのアルゴリズムによって異なる方式が考えられる。例えば、Ｃｈｏｒｄの場合は、ＤＨＴハッシュ値空間上で（前のノードを示す）プレデセッサーの値の変動により、ノードの離脱／故障を発見することができる。離脱したノードが所持していた領域のミラーを当該ＤＨＴノードが持っていない場合は、当該ＤＨＴノードが持つ故障領域リスト情報に離脱したＤＨＴノードの領域情報を時刻と共に追記し、更新した故障領域リストを広告する。故障領域リストの広告は、（後のノードを示す）サクセッサーおよびＣｈｏｒｄ上の短絡経路であるフィンガーの宛先となる各ＤＨＴノードに対して行うことが一例として考えられる。故障領域リストの広告を受信したＤＨＴノードは、その故障領域リストを自身の故障領域リストと比較し、新しいデータが存在する場合のみ自身の故障領域リストに新しいデータをマージし、同様に広告を行う。この比較のために、生成する故障領域リストに疑似乱数や時刻などに基づくＩＤをつけてもよい。
【００７８】
故障領域リストの発見と広告と、データ登録装置の組み合わせにより、一次データテーブル群２０とインデックス用ＤＨＴという構成において、ＤＨＴの故障等に由来するデータの欠損から素早く低コストに復帰できる。
【００７９】
本実施形態によれば、分散ハッシュテーブル上のデータ欠損に対する一次データ源からの復元を効率的に行うことができる。
【００８０】
（第２の実施形態）
以下、第２の実施形態が第１の実施形態と相違する部分を中心に説明する。
【００８１】
図９に、本実施形態に係る分散ハッシュテーブルシステムの構成例を示す。
【００８２】
本実施形態は、第１の実施形態の一次データテーブル群２０を、第１の分散ハッシュテーブル４０とし（一次テーブル２をＤＨＴノード４とし）、第１の実施形態の分散ハッシュテーブル３０を、第２の分散ハッシュテーブル３０として、第２の分散ハッシュテーブル３０を、第１の分散ハッシュテーブル４０のバックアップとして使用するようにしたものである。
【００８３】
なお、バックアップを複数系統備えてもよく（第２の分散ハッシュテーブル３０を複数系統備えてもよく）、この場合には、バックアップは、各系統毎に独立して行えばよい。
【００８４】
図１０に、本実施形態に係るデータ登録装置１の構成例を示す。この構成例は基本的には図５と同様である。
【００８５】
本実施形態では、第２の分散ハッシュテーブル４０に第１の分散ハッシュテーブル３０のバックアップを行うにあたって、データ登録装置１は、継続的に（例えば一定期間が経過する毎に）差分バックアップを行う場合を例にとって説明する。なお、この差分バックアップは、例えば、分散ハッシュテーブルやネットワークの負荷が低い時間帯などに行うと効果的である。
【００８６】
なお、例えば第１の分散ハッシュテーブル４０及び第２の分散ハッシュテーブル３０に対して設けられた制御装置７が、各々のデータ登録装置１（の指示受信部１１）に対して同時或いは順次にバックアップ指示を出す（個々のデータ登録装置１においては適当な間隔でバックアップ指示を受信する）ようにしてもよいし、制御装置７を設けずに、個々のデータ登録装置１の内部において、自発的に且つ継続的に（例えば、一定期間経過毎に）、その指示受信部１１にバックアップ指示を出すようにしてもよい。
【００８７】
また、第２の分散ハッシュテーブル３０のためのハッシュアルゴリズム及びソートアルゴリズムについても基本的には第１の実施形態と同様であり、例えば、制御装置７が上記ハッシュアルゴリズム及びソートアルゴリズムをバックアップ指示メッセージに含めて各データ登録装置１に与えてもよいし、バックアップ指示メッセージに含めず、個々のデータ登録装置１においてそれぞれ設定するようにしてもよい。
【００８８】
さて、本実施形態においては、例えば、制御装置７（又はデータ登録装置１自身）が、データ登録装置１の指示受信部１１に対して、「前回のバックアップ指示時刻」を示すことによって、その時刻以降に更新された（ｋｅｙ，ｖａｌｕｅ）のデータエントリのみを更新する方法が考えられる。このときは、一次データ源であるＤＨＴノード４に、個々の（ｋｅｙ，ｖａｌｕｅ）のデータエントリの登録時刻を記録する機能と、ＮＴＰ等の機能により個々の一次データ源であるＤＨＴノード４の時計を揃えておく機能とを設けるのが望ましい。例えば、データエントリ（ｋｅｙ，ｖａｌｕｅ）に、登録時刻ｒｅｇ＿ｔを加えて、（ｋｅｙ，ｖａｌｕｅ，ｒｅｇ＿ｔ）とし、また、上記「前回のバックアップ指示時刻」以降の時刻に登録されたデータエントリ（すなわち、「前回のバックアップ指示時刻」以降の時刻である登録時刻ｒｅｇ＿ｔを持つデータエントリ）のみを登録するように、フィルタ部１３が登録時刻ｒｅｇ＿ｔを参照してフィルタリングを行うようにすればよい。
【００８９】
なお、バックアップを一系統だけ備える場合には、より簡単にdirty bitなどの管理手法により、バックアップされていないデータのみを選択的に更新することもできる。例えば、指示受信部１１は、dirty bitがセットされているデータエントリのみを登録するようにフィルタ部１３を設定し、また、一次データ源であるＤＨＴノード４は、バックアップが完了したデータエントリからdirty bitを解除するようにすればよい。
【００９０】
図１１に、本実施形態のデータ登録装置１の処理手順の一例を示す。
【００９１】
ステップＳ２１のステップＳ２（図６）との相違は、ステップＳ２１で、指示受信部１１が（例えば「前回のバックアップ指示時刻」を含む）バックアップ指示を受信したことによって、処理が開始する点である。
【００９２】
ステップＳ２２，Ｓ２３（ハッシュ計算及びソート）は、図６のステップＳ３，Ｓ４と同様である。
【００９３】
ステップＳ２４（フィルタリング）のステップＳ５（図６）との相違は、フィルタリングの内容が、前回のバックアップ指示時刻あるいはdirty bitなどに基づく差分バックアップを行うようにフィルタリングするものである点である。
【００９４】
ステップＳ２５（書き込み）は、図６のステップＳ６及び図７と同様である。
【００９５】
また、第１の実施形態で示した図８の手順例も、フィルタリングの内容が異なる以外は、本実施形態でも同様に使用可能である。
【００９６】
なお、本実施形態においても、分散ハッシュテーブル４０側に設けたデータ登録装置１が、第１の実施形態と同様に分散ハッシュテーブル３０における故障領域の復元をも行うようにしてもよい。
【００９７】
また、分散ハッシュテーブル３０側にもデータ登録装置１を設け、第１の実施形態と同様に分散ハッシュテーブル４０における故障領域の復元を行うようにしてもよい。
【００９８】
本実施形態によれば、分散ハッシュテーブル間の差分バックアップを効率的に行うことができる。
【００９９】
（第３の実施形態）
以下、第３の実施形態が第１、第２の実施形態と相違する部分を中心に説明する。
【０１００】
本実施形態に係る分散ハッシュテーブルシステムの構成例は図９と同様である。
【０１０１】
本実施形態に係るデータ登録装置１の構成例は図１０と同様である。
【０１０２】
第２の実施形態では、第１の分散ハッシュテーブル４０から第２の分散ハッシュテーブル３０への差分バックアップを行ったが、本実施形態は、第１の分散ハッシュテーブル４０から第２の分散ハッシュテーブル３０へのコピー（複製）を行うようにしたものである。なお、コピーはどのような目的で行われるものであってもよく、例えばバックアップでも分散ハッシュテーブルシステムのリプレースでも構わない。
【０１０３】
なお、例えば第１の分散ハッシュテーブル４０及び又は第２の分散ハッシュテーブル３０に対して設けられた制御装置７が、第１の分散ハッシュテーブル４０における各々のデータ登録装置１（の指示受信部１１）に対して同時或いは順次に、第２の分散ハッシュテーブル３０へのコピー指示に、第２の分散ハッシュテーブル３０へのエントリポイント（例えばＩＰアドレスとポート番号）を付加して送信する。なお、第２の分散ハッシュテーブル３０のためのハッシュアルゴリズム及びソートアルゴリズムについても基本的には第１、第２の実施形態と同様である。
【０１０４】
第１の分散ハッシュテーブル４０における各データ登録装置１では、ハッシュ・ソート部１２にソートアルゴリズムをセットする点は第１、第２の実施形態と同様であるが、ここでは、対応するＤＨＴノード４が持っている全データをバックアップするため、フィルタ部１３には、空データ（ｎｕｌｌ）を設定することによって、書きこみ領域の制限は行わないようにする。
【０１０５】
ハッシュ・ソート部１２は、データ（ｋｅｙ，ｖａｌｕｅ）の列を入力として、指定された、第２の分散ハッシュテーブル３０のハッシュアルゴリズムとソートアルゴリズムを利用し、ソートされたデータ列（ｈ（ｋｅｙ），ｋｅｙ，ｖａｌｕｅ）を書込部１４へ渡す。
【０１０６】
書込部１４は、与えられたデータを先頭から（もしくは、ランダムな位置から）書きこみを開始する。書込部１４は、第２の分散ハッシュテーブル３０の或るＤＨＴノード３に塊のままのデータを書き込む。書き込むデータがノードの担当領域を外れた時点で、エラー通知等の手段により第２の分散ハッシュテーブル３０により定義される空間内の適切な隣接ノードに書きこみ先を変更する。ランダムな位置から開始するのは、第１の分散ハッシュテーブル４０における各データ登録装置１が第２の分散ハッシュテーブル３０の特定のＤＨＴノード４へ書き込んでしまうような事態を防ぐためである。なお、遅いＤＨＴノード近辺で輻輳をおこさないように、書きこみの速度（書き込み先ノードの変更の時間間隔など）に一定の制約をかける（例えば、ランダムな待ち時間を設ける）ようにしてもよい。
【０１０７】
図１２に、本実施形態のデータ登録装置１の処理手順の一例を示す。
【０１０８】
ステップＳ３１のステップＳ２（図６）との相違は、ステップＳ２１で、指示受信部１１が（例えばＩＰアドレスとポート番号を含む）コピー指示を受信したことによって、処理が開始する点である。
【０１０９】
ステップＳ３２，Ｓ３３（ハッシュ計算及びソート）は、図６のステップＳ３，Ｓ４と同様である。
【０１１０】
ステップＳ３４（フィルタリング）のステップＳ５（図６）との相違は、フィルタリングの内容が、全データをコピー対象とするようにフィルタリングするものである点である。なお、本実施形態においては、フィルタ部１３及びステップＳ３４を省くことも可能である。
【０１１１】
ステップＳ３５（書き込み）は、図６のステップＳ６及び図７と同様である。
【０１１２】
また、第１の実施形態で示した図８の手順例も、フィルタリングの内容が異なる以外は、本実施形態でも同様に使用可能である。
【０１１３】
なお、本実施形態においても、分散ハッシュテーブル４０側に設けたデータ登録装置１が、第１の実施形態と同様に分散ハッシュテーブル３０における故障領域の復元をも行うようにしてもよいし、第２の実施形態と同様に差分バックアップをも行うようにしてもよい。
【０１１４】
また、分散ハッシュテーブル３０側にもデータ登録装置１を設け、第１の実施形態と同様に分散ハッシュテーブル４０における故障領域の復元を行うようにしてもよい。
【０１１５】
本実施形態によれば、第１の分散ハッシュテーブルから第２の分散ハッシュテーブルへデータ移行を効率的に行うことができる。
【０１１６】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手順を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１１７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１１８】
【図１】本発明の一実施形態に係る分散ハッシュテーブルシステムの構成例を示す図
【図２】ＤＨＴノード３が保持するデータの一例を示す図
【図３】一次データテーブルが保持するデータの一例を示す図
【図４】タグＩＤの一例を示す図
【図５】同実施形態に係るデータ登録装置の構成例を示す図
【図６】同実施形態に係るデータ登録装置の処理手順の一例を示すフローチャート
【図７】図６の手順のステップＳ６の書き込みの処理手順の一例を示すフローチャート
【図８】書き込みのアルゴリズム例を示す図
【図９】同実施形態に係る分散ハッシュテーブルシステムの他の構成例を示す図
【図１０】同実施形態に係るデータ登録装置の他の構成例を示す図
【図１１】同実施形態に係るデータ登録装置の処理手順の他の例を示すフローチャート
【図１２】同実施形態に係るデータ登録装置の処理手順の更に他の例を示すフローチャート
【符号の説明】
【０１１９】
１…データ登録装置、２…一次データテーブル、３，４…ＤＨＴノード、７…制御装置、８…ネットワーク、１１…指示受信部、１２…ハッシュ・ソート部、１３…フィルタ部、１４…書込部、１５…入力部、２０…一次データテーブル群、３０，４０…分散ハッシュテーブル
【図１】
2009020757.tif 000003
【図２】
2009020757.tif 000004
【図３】
2009020757.tif 000005
【図４】
2009020757.tif 000006
【図５】
2009020757.tif 000007
【図６】
2009020757.tif 000008
【図７】
2009020757.tif 000009
【図８】
2009020757.tif 000010
【図９】
2009020757.tif 000011
【図１０】
2009020757.tif 000012
【図１１】
2009020757.tif 000013
【図１２】
2009020757.tif 000014