(57)【特許請求の範囲】
【請求項１】
ネットワークと、複数の記憶装置とを含む記憶システムにおいて、
前記記憶装置が、
前記複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含み、
さらに、前記記憶装置が、
前記ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、前記ネットワークを介して前記フラグメントデータを他の記憶装置に送信するフラグメント処理手段と、
前記ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定する状態判定手段と、
前記状態判定手段が前記記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成する仮想ノード管理手段と
を含み、
前記仮想ノード管理手段が、
大きさの関係が等比数列となる段階的な大きさの前記仮想ノードを作成し、
前記仮想ノードを識別するための情報のビット数を、前記仮想ノードの大きさに反比例するように割り当てる
記憶システム。
【請求項２】
前記フラグメント処理手段が、
前記ネットワークを介して他の記憶装置からフラグメントデータを読み出し、フラグメントデータを結合したデータを生成する
請求項１に記載の記憶システム。
【請求項３】
前記仮想ノードを識別するための情報が、
前記ネットワークを介して受信したデータに関連する情報に基づいて作成される
請求項１又は２に記載の記憶システム。
【請求項４】
ネットワークと、複数の記憶装置とを含む記憶システムに含まれる記憶装置で、
前記複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含む記憶装置が、
前記ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、前記ネットワークを介して前記フラグメントデータを他の記憶装置に送信し、
前記ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定し、
前記記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成し、
大きさの関係が等比数列となる段階的な大きさの前記仮想ノードを作成し、
前記仮想ノードを識別するための情報のビット数を、前記仮想ノードの大きさに反比例するように割り当てる
記憶方法。
【請求項５】
ネットワークと、複数の記憶装置とを含む記憶システムに含まれる記憶装置で、
前記複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含む記憶装置であるコンピュータに、
前記ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、前記ネットワークを介して前記フラグメントデータを他の記憶装置に送信する処理と、
前記ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定する処理と、
前記記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成する処理と、
大きさの関係が等比数列となる段階的な大きさの前記仮想ノードを作成する処理と、
前記仮想ノードを識別するための情報のビット数を、前記仮想ノードの大きさに反比例するように割り当てる処理と
を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの保存に関し、特に、データを分散して保存する記憶システム、記憶方法、及び、プログラムに関する。
【背景技術】
【０００２】
データ量の増減及び記憶装置の構成変更などに柔軟に対応するため、サーバなどの情報処理装置は、分散して配置されている複数の記憶装置（ストレージノード）を用いて構成されているにストレージシステムを用いている（例えば、特許文献１を参照）。
【０００３】
図面を参照して、特許文献１に記載されているような一般的なストレージノードを分散配置させたストレージシステムについて説明する。
【０００４】
図２は、一般的なストレージシステム１２０の構成の一例を示すブロック図である。ストレージシステム１２０は、サーバ１１０からデータを受信し、サーバ１１０にデータを送信する。そのため、ストレージシステム１２０は、アクセスノード１３０と、ネットワーク１５０と、ストレージノード１４０とを含む。
【０００５】
アクセスノート１３０は、サーバ１１０からデータを受け取ると、ネットワーク１５０を介して、ストレージノード１４０にデータを書き込む。また、アクセスノード１３０は、ネットワーク１５０を介してストレージノード１４０からデータを読み出し、サーバ１１０にデータを送り出す。
【０００６】
ストレージノード１４０は、ネットワーク１５０を介して、アクセスノード１３０からデータを受け取り、図示しない内蔵するディスク装置にデータを格納する。
【０００７】
ネットワーク１５０は、上記のデータの中継を実行する。
【０００８】
次に、図面を参照して、ストレージノード１４０に分散されるデータについて説明する。
【０００９】
なお、ストレージノード１４０は、ネットワーク１５０を介して連携し、データを分散配置及び保持する。そのため、いずれかのストレージノード１４０が、リーダ役として、以下の説明における仮想ノードの設定及びデータのフラグメントを実行する。ただし、各ストレージノード１４０は、いずれも、リーダ役を実行できる。そのため、以下の説明において、特に明示しない限り、ストレージノード１４０は、リーダ役のストレージノード１４０として説明する。また、仮想ノードは、ストレージノード１４０に設定済みとする。
【００１０】
図３は、ストレージノード１４０におけるデータの格納方法の一例を示す図である。図３は、１つのブロックデータ６０２を９つのフラグメントデータ６０３と、３つの冗長パリティ６０４とに分散して配置する場合を示す。
【００１１】
図３において、データを保存する仮想ノード４１０は、複数のストレージノード１４０にまたがって構成されている。仮想ノード４１０は、データを保存するデータ格納用コンテナ４１１を含む。なお、先頭ビット列４１２は、仮想ノード４１０を選択（識別）するときの用いられる情報である。先頭ビット列４１２については、後ほど説明する。
【００１２】
ストレージシステム１２０のアクセスノード１３０は、サーバ１１０から、ストレージノード１４０に保存する保存データ６０１を受信すると、図３に示すように、保存データ６０１を、所定のサイズのブロックデータ６０２に分割する。また、アクセスノード１３０は、データに対応するハッシュ値を計算する。そして、アクセスノード１３０は、ブロックデータ６０２とハッシュ値とを、リーダ役のストレージノード１４０に送信する。
【００１３】
ストレージノード１４０は、ブロックデータ６０２を、所定の数（以下、Ｄ個とする）均等な大きさのフラグメントデータ６０３に分割する。また、ストレージノード１４０は、ブロックデータ６０２に対応する冗長パリティ６０４として、所定の数（以下、Ｐ個とする）の冗長フラグメントデータを算出し、フラグメントデータ６０３に付加する。以下、Ｄ個とＰ個とを合わせた数をＦ個とする（Ｆ＝Ｄ＋Ｐ）。図３は、「Ｄ＝９」、「Ｐ＝３」及び「Ｆ＝１２」の場合を示す。なお、ストレージシステム１２０は、Ｄ及びＰの値を、図３に示す値に限らず、変更可能である。
【００１４】
そして、ストレージノード１４０は、フラグメントデータ６０３と冗長パリティ６０４を合わせたＦ個の均等な大きさのフラグメントデータ６０５を、複数のストレージノード１４０に分散配信する。つまり、ストレージノード１４０は、複数のストレージノード１４０にまたがって構成されている仮想ノード４１０に所属するＦ個のデータ格納用コンテナ４１１に、フラグメントデータ６０５を分散して、格納する。
【００１５】
図４は、データを格納する仮想ノード４１０を説明するための図である。
【００１６】
図４に示すように、複数の仮想ノード４１０が、ストレージシステム１２０内のストレージノード１４０をまたいで構成されている。図４は、一例として、４台の仮想ノード４１０を示している。
【００１７】
そして、ストレージノード１４０は、ブロックデータ６０２のハッシュ値の先頭から所定の数のビット（先頭ビット列４１２）の値を基に、どの仮想ノード４１０に、どのフラグメントデータ６０５を保存するかを決定している。
【００１８】
図４は、仮想ノード４１０が４台の場合を示す。ここで、「４」は、２ビットを用いて分類できる。そのため、ストレージノード１４０は、ブロックデータ６０２のハッシュ値の先頭２ビット（先頭ビット列４１２）を基に、格納場所として用いる仮想ノード４１０を決定する。例えば、ハッシュ値が、「００００１１１１…」の場合、先頭ビット列４１２は、「００」である。そのため、フラグメントデータ６０５は、先頭ビット列４１２の「００」に対応する仮想ノード４１０に格納される。
【００１９】
同じ大きさのブロックデータ６０２から生成されたフラグメントデータ６０５の大きさは、同じ大きさとなる。そのため、同一の仮想ノード４１０に所属するデータ格納用コンテナ４１１は、同じ量のデータが書き込まれる。つまり、同一の仮想ノード４１０に所属するデータ格納用コンテナ４１１に含まれるデータ量は、均一となる。さらに、各仮想ノード４１０は、同じビット数のハッシュ値の先頭ビット列４１２に対応する。そのため、ストレージシステム１２０に書き込まれるデータ量が、十分に多い場合、全ての仮想ノード４１０に書き込まれるデータの総量は、概ね均一となる。したがって、ストレージシステム１２０に含まれるデータ格納用コンテナ４１１は、概ね、均一なデータ量を格納（記憶）する。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特開２０１０−０７９８８６
【発明の概要】
【発明が解決しようとする課題】
【００２１】
ストレージシステム１２０に含まれるストレージノード１４０の数が変更された場合、ストレージノード１４０は、均等な分散状態を維持するため、データ格納用コンテナ４１１を、ストレージノード１４０間で移動しようとする。しかし、データ格納用コンテナ４１１の総数が、ストレージノード１４０の数で割り切れない場合、データ格納用コンテナ４１１の分散配置は、均等とはならない。可能な範囲での最適な分散配置は、一部のストレージノード１４０に含まれるデータ格納用コンテナ４１１の数が、他のストレージノード１４０に含まれるデータ格納用コンテナ４１１の数より１つ少なくなる。このため、少ない数のデータ格納用コンテナ４１１を含むストレージノード１４０には、使用不可能な領域が、生じる。そのため、ストレージシステム１２０の容量効率は、低下する。
【００２２】
使用不可能な領域を小さくするための方法として、仮想ノード４１０の数又は仮想ノード４１０当たりのデータ格納用コンテナ４１１の数を、多くする方法が、想定される。仮想ノード４１０の数を多くすることは、データ格納用コンテナ４１１の総数を増やすことである。つまり、この方法は、データ格納用コンテナ４１１を増やす方法である。
【００２３】
しかし、データ格納用コンテナ４１１は、互いに、通信を介した生存確認を行っている。そのため、データ格納用コンテナ４１１の数が増えると、通信量が増加する。そのため、現実的に作成できるデータ格納用コンテナ４１１の数には、制限がある。つまり、データ格納用コンテナ４１１の数を増やす方法は、増やせる数に制限があるという問題点があった。
【００２４】
あるいは、ストレージノード１４０の数が変更されるたびに、データ格納用コンテナ４１１の総数が、ストレージノード１４０の数で割り切れるように、上記のＦの値及び仮想ノード４１０の数を変更する方法が想定される。
【００２５】
しかし、データ格納用コンテナ４１１の個数が変化すると、ストレージノード１４０には、次に示すフラグメントに関する動作が必要となる。すなわち、ストレージノード１４０は、データ格納用コンテナ４１１に含まれるフラグメントデータ６０５を読み出して、結合する。そして、ストレージノード１４０は、結合したデータを改めてフラグメントデータ６０５に分割して、新しいデータ格納用コンテナ４１１に書き込む。このように、データ格納用コンテナ４１１の個数の変化は、全てのデータの書き直しが必要となる。そのため、データ格納用コンテナ４１１の個数の変化は、ＩＯ（Input and Output）の処理コストが非常に高くなる。つまり、上記のＦの値数を変更する方法も、適用範囲が限られる。
【００２６】
このように、データ格納用コンテナ４１１の数の変更は、ストレージシステム１２０のスケーラビリティを低下させる。そのため、Ｆの値は、ストレージシステム１２０において、基本的に固定である。
【００２７】
また、仮想ノード４１０の数は、ストレージノード１４０数を基に決められている。そして、仮想ノード４１０の数の変更に伴って、データ格納用コンテナ４１１の数が変更される。つまり、仮想ノード４１０の数を変更する方法も、適用範囲が限られる。
【００２８】
このように、特許文献１に記載の技術は、容量効率を向上することができないという問題点があった。
【００２９】
本発明の目的は、上記問題点を解決し、冗長性及びスケーラビリティを低下させずに、容量効率を向上できる記憶システム、記憶方法、及び、プログラムを提供することにある。
【課題を解決するための手段】
【００３０】
本発明の一形態における記憶システムは、ネットワークと、複数の記憶装置とを含み、記憶装置が、複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含み、さらに、記憶装置が、ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、ネットワークを介してフラグメントデータを他の記憶装置に送信するフラグメント処理手段と、ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定する状態判定手段と、状態判定手段が記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成する仮想ノード管理手段とを含む。
【００３１】
本発明の一形態における記憶方法は、ネットワークと複数の記憶装置とを含む記憶システムに含まれる記憶装置で、複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含む記憶装置が、ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、ネットワークを介してフラグメントデータを他の記憶装置に送信し、ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定し、記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成する。
【００３２】
本発明の一形態におけるプログラムは、ネットワークと複数の記憶装置とを含む記憶システムに含まれる記憶装置で、複数の記憶装置にまたがって論理的に構成された仮想ノードの構成として、データを保存する１つ又は複数のコンテナを含むデータ記憶手段を含む記憶装置であるコンピュータに、ネットワークを介して受信したデータを所定の数に分割したフラグメントデータを生成し、ネットワークを介してフラグメントデータを他の記憶装置に送信する処理と、ネットワークにおける他の記憶装置の構成の状態を監視し、構成の変更を判定する処理と、記憶装置の構成の変更を検出した場合に、変更後の記憶装置に構成に合わせて複数の大きさの仮想ノードを作成する処理とを実行させる。
【発明の効果】
【００３３】
本発明に基づけば、冗長性及びスケーラビリティを低下させることなく、容量効率を向上させるとの効果を奏することができる。
【図面の簡単な説明】
【００３４】
【図１】図１は、本発明のおける第１の実施形態に係る記憶システムの構成の一例を示すブロック図である。
【図２】図２は、一般的な分散配置ストレージシステムの構成の一例を示すブロック図である。
【図３】図３は、ストレージノードにおけるデータの格納方法の一例を示す図である。
【図４】図４は、データを格納する仮想ノードを説明するための図である。
【図５】図５は、記憶装置の数と、仮想ノードの数との対応関係の一例を示す図である。
【図６】図６は、分割後のハッシュ値域の一例を示す図である。
【図７】図７は、分割後のハッシュ値域の一例を示す図である。
【図８】図８は、分割後のハッシュ値域の一例を示す図である。
【図９】図９は、第１の実施形態に係る記憶装置におけるデータの書き込み動作の一例を示すフローチャートである。
【図１０】図１０は、第１の実施形態に係る記憶装置におけるデータの読み出し動作の一例を示すフローチャートである。
【図１１】図１１は、第１の実施形態に係る記憶装置における構成変更時の仮想ノードの設定動作の一例を示すフローチャートである。
【図１２】図１２は、第１の実施形態に係る記憶装置の変形例の構成の一例を示すブロック図である。
【発明を実施するための形態】
【００３５】
次に、本発明の実施形態について図面を参照して説明する。
【００３６】
なお、各図面は、本発明の実施形態を説明するためのものである。ただし、本発明は、各図面の記載に限られるわけではない。また、各図面の同様の構成には、同じ番号を付し、その繰り返しの説明を、省略する場合がある。
【００３７】
また、以下の説明に用いる図面において、本発明の説明に関係しない部分の構成については、記載を省略し、図示しない場合もある。
【００３８】
まず、本発明の実施形態の説明に用いる用語について、まとめておく。
【００３９】
「仮想ノード」とは、データを格納するためのコンテナを含む論理的なグループである。つまり、仮想ノードは、仮想的なストレージノード（記憶装置）である。仮想ノードは、複数の物理的に分かれた記憶装置（ストレージノード）をまたいで構成される。また、仮想ノードは、保存するデータに対応する情報を用いて識別（区別）される。この識別用の情報は、特に制限はない。ただし、本発明の実施形態の説明では、一例として、データに所定のハッシュ関数を適用して求めてハッシュ値を用いるとする。より詳細には、後ほど説明する先頭ビット列を用いるとする。
【００４０】
「コンテナ」は、フラグメントデータを保存（格納）するために、仮想ノードの構成として、記憶装置に設けられた論理的な記憶単位である。コンテナは、例えば、ファイルとして作成される。
【００４１】
「先頭ビット列」とは、上記の仮想ノードを識別すためのハッシュ値の先頭から所定数のビット列である。ただし、本発明の実施形態は、仮想ノードを識別するための情報として、ハッシュ値の先頭からビット列に限る必要はない。例えば、本発明の実施形態は、ハッシュ値の所定に位置（例えば、先頭から奇数番目のビット）から抽出したビット列を用いてもよい。以下、先頭以外のビット列を含めて、先頭ビット列と呼ぶ。また、上記のとおり、先頭ビット列は、仮想ノードを識別する情報である。また、仮想ノードは、データをコンテナに格納する。そのため、先頭ビット列は、データを格納するコンテナを識別する情報（インデックス情報）、又は、インデックス情報の一部を構成する情報である。
【００４２】
「ハッシュ値域」とは、同じ先頭ビット列に対応するハッシュ値の範囲である。仮想ノードのコンテナは、コンテナが対応するハッシュ値域に、ハッシュ値が含まれるデータを保存する。
【００４３】
「フラグメントデータ」とは、所定の数に分割（フラグメント化）されたデータである。以下の本発明の実施形態は、受信したデータの信頼性を確保するためデータ（以下、「冗長パリティ」と呼ぶ）を生成し、受信したデータと同様に分割（フラグメント化）して保存する。そのため、以下、フラグメントデータは、冗長パリティを含む。ただし、本発明の実施形態は、冗長パリティを含まないフラグメントデータを保存してもよい。
【００４４】
「仮想ノードの粒度」とは、仮想ノードの設定における細かさの程度を示す値である。例えば、粒度の値又は粒度の値の幅（Ｇ）が大きい場合、仮想ノードは、より詳細に設定される。ただし、粒度の値は、反対としてもよい。つまり、粒度の値が小さい場合に、仮想ノードは、より詳細に設定されてもよい。
【００４５】
なお、本発明の実施形態の記憶装置は、ネットワークを介して接続されているため、ネットワークのノードである。そのため、記憶装置は、ストレージノードとも呼ばれる。
【００４６】
＜第１の実施形態＞
本発明における第１の実施形態について図面を参照して説明する。
【００４７】
［構成の説明］
まず、第１の実施形態に係る記憶システム２０の構成について図面を参照して説明する。
【００４８】
図１は、第１の実施形態に係る記憶システム２０の構成の一例を示すブロック図である。
【００４９】
記憶システム２０は、複数台の記憶装置（ストレージノード）４０と、ネットワーク５０とを含む。
【００５０】
ネットワーク５０は、図示しないアクセスノードと、記憶装置４０とを接続する通信網である。ネットワーク５０は、記憶装置４０間におけるデータの通信についても中継する。ただし、本実施形態のネットワーク５０は、通信方法及び通信形式に、特に制限はない。例えば、ネットワーク５０は、ＬＡＮ（Local Area Network）又はファイバーチャネルなどの、一般的な通信網でもよい。そのため、ネットワーク５０の詳細な説明を省略する。
【００５１】
記憶装置４０は、ネットワーク５０を介して、アクセスノードから受信したデータを、複数の記憶装置４０に分散して記憶する。記憶装置４０は、データを受信する際、データに対応するハッシュ値を受信する。
【００５２】
そのため、記憶装置４０は、フラグメント処理部４０１と、仮想ノード管理部４０２と、状態判定部４０３と、データ記憶部５００とを含む。
【００５３】
なお、リーダ役として動作する記憶装置４０が、以下で説明する主な動作を実行する。そのため、以下の説明において、特に説明しない場合、リーダ役として動作する記憶装置４０についての説明とする。
【００５４】
フラグメント処理部４０１は、アクセスノードから受信したデータを分割（フラグメント化）して、フラグメントデータを生成する。また、フラグメント処理部４０１は、冗長パリティを生成する。また、フラグメント処理部４０１は、先頭ビット列として、ハッシュ値の先頭から所定の長さのビットを抽出する。そして、フラグメント処理部４０１は、ネットワーク５０を介して、他の記憶装置４０にフラグメントデータと先頭ビット列とを配布する。なお、記憶装置４０は、先頭ビット列の代わりに、仮想ノードを指定する別の情報を送信してもよい。
【００５５】
各記憶装置４０のフラグメント処理部４０１は、リーダ役の記憶装置４０から送られてきた先頭ビット列を基に、フラグメントデータを保存する仮想ノードのコンテナ５０１を判定し、フラグメントデータをコンテナ５０１に格納する。なお、リーダ役の記憶装置４０は、自装置に保存するフラグメントデータを、自装置内のコンテナ５０１に格納する。つまり、記憶装置４０は、自装置のコンテナ５０１に保存するフラグメントデータを、配布しない。
【００５６】
また、リーダ役の記憶装置４０のフラグメント処理部４０１は、各記憶装置４０のコンテナ５０１に格納されているフラグメントデータを集め、集めたフラグメントデータを結合して、アクセスノードに返却するデータを生成する。そして、フラグメント処理部４０１は、ネットワーク５０を介して、生成したデータをアクセスノードに送信する。
【００５７】
データ記憶部５００は、フラグメントデータを格納するためのコンテナ５０１を含む。例えば、データ記憶部５００は、磁気ディスク装置、光ディスク装置、又は、ＳＳＤ（Solid State Drive）である。
【００５８】
コンテナ５０１は、フラグメントデータを格納する。コンテナ５０１は、後ほど説明するように、ハッシュ値からフラグメントデータの位置が参照可能なように先頭ビット列、又はインデックス情報を含む。インデックス情報等は、先頭ビット列に加え、フラグメントデータを関するための情報（例えば、コンテナ５０１内のフラグメントデータの位置など）を含む情報である。コンテナ５０１は、例えば、論理的なファイルである。コンテナ５０１は、仮想ノードの設定に基づいて、データ記憶部５００に、１つ又は複数個作成されている。なお、インデックス情報は、各コンテナ５０１ではなく、図示しないデータ記憶部５００の制御部が、図示しない記憶部に保存してもよい。その場合、その制御部が、記憶部に保存したインデックス情報を基に、フラグメントデータをコンテナ５０１に保存する。
【００５９】
仮想ノード管理部４０２は、記憶装置４０（ストレージノード）の数を基に、コンテナ５０１を含む仮想ノードの数、並びに、仮想ノードに対応する先頭ビット列及びハッシュ値域を管理する。具体的には、仮想ノード管理部４０２は、仮想ノードの管理として、仮想ノードの追加及び削除を実行する。
【００６０】
状態判定部４０３は、ネットワーク５０を介して、仮想ノードを構成している記憶装置４０の動作状況を監視（生存確認）する。そして、状態判定部４０３は、正常に動作している（生存している）記憶装置４０の構成に変更が発生したか否かを判定する。より具体的には、状態判定部４０３は、正常に動作している記憶装置４０の数に増加又は減少が発生したか否かを判定する。そして、状態判定部４０３は、記憶装置４０の構成の変更（数の増加又は減少）が発生したと判定した場合、構成の変更を仮想ノード管理部４０２に通知する。
【００６１】
ここで、正常に動作しているとは、記憶装置４０が、記憶システム２０における記憶機能を実現できるように動作していることである。つまり、正常に動作しているとは、リーダ役の記憶装置４０からフラグメントデータを受信でき、リーダ役の記憶装置４０にフラグメントデータに送信できることである。
【００６２】
［動作の説明］
次に、本実施形態の動作について図面を参照して説明する。
【００６３】
より詳細には、記憶システム２０における、データの書き込み、データの読み出し、及び、構成変更に伴う仮想ノードの設定の各動作に説明する。
【００６４】
（データの書き込み）
図９は、第１の実施形態に係る記憶装置４０のデータの書き込み動作の一例を示すフローチャートである。
【００６５】
まず、フラグメント処理部４０１は、アクセスノードから、保存するデータと、データに対応するハッシュ値とを受信する（ステップＳ１０２）。
【００６６】
なお、先頭ビットは、ハッシュ値を基に生成される。また、先頭ビットは、仮想ノードを識別するための情報である。つまり、記憶装置４０は、ネットワーク５０を介して受信したデータに関連する情報を基に、仮想ノードの識別するための情報を作成する。
【００６７】
次に、フラグメント処理部４０１は、データを分割し、冗長パリティを生成して、フラグメントデータを生成する（ステップＳ１０３）。
【００６８】
フラグメント処理部４０１は、ハッシュ値の先頭から所定の長さのビット列である先頭ビット列を基に、フラグメントデータの書き込み先である仮想ノードを決定する（ステップＳ１０４）。
【００６９】
リーダ役の記憶装置４０のフラグメント処理部４０１は、ネットワーク５０を介して、フラグメントデータと先頭ビット列とを、分散配置されている各記憶装置４０に配布する。
【００７０】
各記憶装置４０のフラグメント処理部４０１は、先頭ビット列を基に、受信したフラグメントデータの書き込み先である仮想ノードに含まれるコンテナ５０１を決定し、決定したコンテナ５０１にフラグメントデータを書き込む（ステップＳ１０５）。なお、各記憶装置４０のフラグメント処理部４０１は、先頭ビット列と、コンテナ５０１に書き込んだフラグメントデータとの対応関係（インデックス情報の一部）を保存しておく。
【００７１】
フラグメント処理部４０１は、全てのフラグメントデータがコンテナ５０１に格納された後、アクセスノードに書き込み完了の結果を返却する（ステップＳ１０６）。なお、記憶システム２０が、ライトバックを用いている場合、記憶装置４０は、ステップＳ１０２完了時に、アクセスノードに書き込み完了を返却してもよい。
【００７２】
（データの読み出し）
図１０は、第１の実施形態に係る記憶装置４０におけるデータの読み出し動作の一例を示すフローチャートである。
【００７３】
フラグメント処理部４０１は、アクセスノードから受信したハッシュ値を基に、フラグメントデータが保存されている仮想ノードを決定する（ステップＳ２０２）。より詳細には、フラグメント処理部４０１は、ハッシュ値から先頭ビット列を生成し、先頭ビット列を基に仮想ノードを決定する。
【００７４】
フラグメント処理部４０１は、ネットワーク５０を介して、先頭ビット列を用いて、各記憶装置４０における仮想ノードのコンテナ５０１から、フラグメントデータを読み出す（ステップＳ２０３）。
【００７５】
なお、各記憶装置４０のフラグメント処理部４０１は、先頭ビット列と、書き込み時に保存したインデックス情報と基に、コンテナ５０１に格納されているフラグメントデータを読み出す。
【００７６】
フラグメント処理部４０１は、読み出したフラグメントデータを結合して、アクセスノードに返却するためのデータを生成する（ステップＳ２０４）。
【００７７】
フラグメント処理部４０１は、生成したデータを、アクセスノードに返却する（ステップＳ２０５）。
【００７８】
（構成変更時の仮想ノードの設定）
図１１は、第１の実施形態に係る記憶装置４０における構成変更時の仮想ノードの設定動作の一例を示すフローチャートである。
【００７９】
まず、説明の前提をまとめておく。
【００８０】
仮想ノードの粒度の幅を示す定数（Ｇ）は、予め、記憶装置４０に設定されているとする。なお、以下の説明では、「Ｇ＝１」とする。
【００８１】
また、記憶装置４０の数と、仮想ノードの数との対応は、予め、記憶装置４０に設定されているとする。図５は、以下の説明で用いる、記憶装置４０の数と、仮想ノードの数との対応関係の一例を示す図である。ただし、本実施形態における記憶装置４０の数と、仮想ノードの数との対応は、図５に限られない。
【００８２】
また、以下で説明する動作は、状態判定部４０３が、記憶装置４０の構成の変更を検出して、仮想ノード管理部４０２に、構成の変更を通知した後の動作である。
【００８３】
以下、具体的な動作を説明する。
【００８４】
状態判定部４０３から構成の変更の通知を受信すると、仮想ノード管理部４０２は、記憶装置４０の数と仮想ノードの数との対応関係（図５を参照）を基に、構成変更後の記憶装置４０の数に対応する仮想ノードの数を決定する（ステップＳ３０２）。なお、仮想ノード管理部４０２は、図５に示すような表を用いるのではなく、所定の計算式を用いて仮想ノードの数を決定してもよい。
【００８５】
そして、仮想ノード管理部４０２は、決定した仮想ノードの数と、現在の仮想ノードの数との比較を基に、仮想ノードの数の変更が必要か否かを判定する（ステップＳ３０３）。なお、仮想ノード管理部４０２は、構成変更後の記憶装置４０の数が、現在設定されている仮想ノードの数に対応する記憶装置４０の数の範囲に含まれているか否かを判定してもよい。
【００８６】
仮想ノードの数の変更が必要ない場合（ステップＳ３０３でＮｏ）、仮想ノード管理部４０２は、仮想ノードのコンテナ５０１が保有するデータを変更する必要はない。そこで、仮想ノード管理部４０２は、コンテナ５０１を、構成変更後の記憶装置４０に合わせて、再配置する（ステップＳ３０７）。例えば、仮想ノード管理部４０２は、コンテナ５０１を、記憶装置４０間で移動する。なお、コンテナ５０１の再配置は、必要ない場合もある。そのような場合、仮想ノード管理部４０２は、特に動作せず、動作を終了する。
【００８７】
仮想ノード数の変更が必要な場合（ステップＳ３０３でＹｅｓ）、仮想ノード管理部４０２は、仮想ノードを作成（又は削除）する。この動作については、後ほど詳細に説明する。
【００８８】
そして、仮想ノードの作成（又は削除）が完了すると、仮想ノード管理部４０２は、構成変更後の記憶装置４０に、コンテナ５０１を再配置する（ステップＳ３０５）。
【００８９】
コンテナ５０１の再配置後、フラグメント処理部４０１は、データを新しいコンテナ５０１に移動する。つまり、フラグメント処理部４０１は、構成前のコンテナ５０１に格納されているデータを読み出し、構成後の新しいコンテナ５０１に格納する（書き込む）（ステップＳ３０６）。
【００９０】
次に、ステップＳ３０４における仮想ノードの作成の動作についてさらに説明する。
【００９１】
まず、以下の説明の用いる変数を説明する。
【００９２】
構成変更後の記憶装置４０に対応する仮想ノードの数を、「ｎ」個とする。ここで、ｎは、２のべき乗（累乗）数である（図５を参照）。
【００９３】
また、先頭ビット列の長さ（ビット数）を「Ｌ」とする。ただし、後ほど説明する通り、先頭ビット列の長さは、複数種類となる。そこで、先頭ビット列の長さ（Ｌ）を区別する場合、「Ｌ」に添え字を追加する。つまり、最初に設定する先頭ビット列の長さを「Ｌ１」とし、以下、「Ｌ２」、「Ｌ３」、…とする。
【００９４】
また、分割後のハッシュ値域の数を「ｍ」個とする。ただし、ハッシュ値域の分割は、後ほど説明する通り、変化する。そこで、ハッシュ値域の数（ｍ）を区別する場合、「ｍ」に添え字を追加する。つまり、最初の分割後のハッシュ値域の数を「ｍ１」とし、以下、「ｍ２」、「ｍ３」、…とする。
【００９５】
まず、仮想ノード管理部４０２は、最初の先頭ビット列の長さ（Ｌ１）と、ハッシュ値域の分割数（ｍ１）とを、次のように決める。すなわち、仮想ノード管理部４０２は、最初の先頭ビット列の長さ（Ｌ１）として、次の式を用いる。
【００９６】
［数式１］
Ｌ１＝（ｌｏｇ２ｎ）−Ｇ［単位はビット］
そして、仮想ノード管理部４０２は、上記の長さ（Ｌ１）の先頭ビット列を用いて識別されるハッシュ値域の分割数（ｍ１）を「ｎ／２Ｇ［個］」とする。
【００９７】
例えば、ｎ＝８の場合について説明する。
【００９８】
この場合、仮想ノード管理部４０２は、最初の先頭ビット列の長さ（Ｌ１）として、「Ｌ１＝２（＝（Ｌｏｇ２８）−１＝３−１）［ビット］」を算出する。また、仮想ノード管理部４０２は、ハッシュ値域の数（ｍ１）として、４個（＝８／２１＝８／２）を算出する。つまり、仮想ノード管理部４０２は、ハッシュ値域を４つに分割する。
【００９９】
図６は、この場合の分割（第１の分割）後のハッシュ値域の一例を示す図である。
【０１００】
図６において、先頭ビット列７０１は、２ビット長のビット列（Ｌ１＝２）である。また、全てのハッシュ値を含むハッシュ値域７０は、４つのハッシュ値域７０４に分割されている（ｍ１＝４）。
【０１０１】
そして、仮想ノード管理部４０２は、ハッシュ値域の分割の数（ｍ）が、仮想ノードの数（ｎ＝８）となるまで、次の動作を実行する。
【０１０２】
今の場合、ハッシュ値域の分割数（ｍ１＝４）は、仮想ノードの数（ｎ＝８）より小さい。そのため、仮想ノード管理部４０２は、ハッシュ値域の分割を継続する。
【０１０３】
仮想ノード管理部４０２は、分割されたハッシュ値域の中から、要素数（ハッシュ値域に値の範囲）が最少であるハッシュ値域を選択する。そして、仮想ノード管理部４０２は、選択したハッシュ値域において、先頭ビット列の値が大きい方から半数のハッシュ値域を選択する。
【０１０４】
なお、最初のハッシュ値域の分割後では、全てのハッシュ値域の要素数が、同じである。そのため、仮想ノード管理部４０２は、先頭ビット列の値が大きい方から半数のハッシュ値域を選択すればよい。例えば、図６の場合、仮想ノード管理部４０２は、先頭ビット列７０１の値が「１０」及び「１１」に対応するハッシュ値域７０２を選択する。
【０１０５】
そして、仮想ノード管理部４０２は、選択したハッシュ値域について、ハッシュ値域を示す先頭ビット列の長さ（Ｌ）を１ビット増やす（Ｌ２＝Ｌ１＋１＝３）。つまり、仮想ノード管理部４０２は、選択したハッシュ値域に対応する先頭ビット列の数を２倍にする。そして、仮想ノード管理部４０２は、先頭ビット列に対応するようにハッシュ値域を分割する。
【０１０６】
図７は、この場合の分割（第２の分割）後のハッシュ値域の一例を示す図である。
【０１０７】
仮想ノード管理部４０２は、図６に示されている先頭ビット列７０１の「１０」を基に、図７に示す先頭ビット列８０１の「１００」及び「１０１」を生成する。同様に、仮想ノード管理部４０２は、図６に示されている先頭ビット列７０１の「１１」を基に、図７に示されている先頭ビット列８０１の「１１０」及び「１１１」を生成する。そして、仮想ノード管理部４０２は、図６の下方に示されている２つのハッシュ値域７０２を、先頭ビット列８０１に対応した４つのハッシュ値域８０２に分割する。
【０１０８】
その結果、ハッシュ値域の数（ｍ２）は、「６」となる。しかし、ハッシュ値域の数（ｍ２＝６）は、仮想ノードの数（ｎ＝８）より小さい。そのため、仮想ノード管理部４０２は、さらにハッシュ値域を分割する。
【０１０９】
上記の同様に、仮想ノード管理部４０２は、要素数（ハッシュ値域に値の範囲）が最少であるハッシュ値域の中で、先頭ビット列の値が大きい方から半数のハッシュ値域を選択する。図７の場合、仮想ノード管理部４０２は、先頭ビット列８０１が「１１０」と「１１１」に対応するハッシュ値域８０２を選択する。
【０１１０】
そして、仮想ノード管理部４０２は、選択したハッシュ値域について、ハッシュ値域を示す先頭ビット列の長さ（Ｌ）を１ビット増やす（Ｌ３＝Ｌ２＋１＝４）。つまり、仮想ノード管理部４０２は、選択したハッシュ値域に対応する先頭ビット列の数を２倍にする。そして、仮想ノード管理部４０２は、先頭ビット列に対応するようにハッシュ値域を分割する。
【０１１１】
図８は、この場合の分割（第３の分割）後のハッシュ値域の一例を示す図である。
【０１１２】
仮想ノード管理部４０２は、図７に示されている先頭ビット列８０１の「１１０」を基に、図８に示す先頭ビット列９０１の「１１００」及び「１１０１」を生成する。同様に、仮想ノード管理部４０２は、図７に示されている先頭ビット列８０１の「１１１」を基に、図８に示されている先頭ビット列９０１の「１１１０」及び「１１１１」を生成する。そして、仮想ノード管理部４０２は、図７の下方に示されている２つのハッシュ値域８０２を、先頭ビット列９０１に対応した４つのハッシュ値域９０２に分割する。
【０１１３】
その結果、ハッシュ値域の数（ｍ３）は、「８」となる。つまり、ハッシュ値域の数（ｍ３＝８）は、仮想ノードの数（ｎ＝８）と同じになる。
【０１１４】
そのため、仮想ノード管理部４０２は、ハッシュ値域の分割を終了する。
【０１１５】
その結果、仮想ノード管理部４０２は、ハッシュ値域の分割として、図８に示すように、ハッシュ値域の範囲の幅（広さ）が「４：２：１」となるようにハッシュ値域を分割する。つまり、仮想ノード管理部４０２は、ハッシュ値域を段階的な大きさに分割する。
【０１１６】
また、上記のように、仮想ノード管理部４０２は、ハッシュ値域の大きさと先頭ビット列の長さとを対応を、反比例の関係とする。
【０１１７】
これは、次のような理由のためである。
【０１１８】
大きなハッシュ値域は、選択される回数が多い。ハッシュ値域の判定時間は、先頭ビット列の長さに比例する。そのため、大きなハッシュ値域に短い先頭ビット列を割り当てると、フラグメント処理部４０１における仮想ノードを識別するためのハッシュ値域の判定時間が、短くなる。つまり、記憶装置４０は、フラグメントデータの書き込み及び読み出し時間を削減するとの効果を奏する。
【０１１９】
ハッシュ値域の分割の説明に戻る。
【０１２０】
仮想ノード管理部４０２は、ハッシュ値域の分割後、それぞれのハッシュ値域及び先頭ビット列を、仮想ノードに対応させる。つまり、仮想ノード管理部４０２は、段階的な大きさの仮想ノードを作成できる。
【０１２１】
そして、仮想ノード管理部４０２は、仮想ノードに含まれるコンテナ５０１の作成を、各記憶装置４０に依頼する。
【０１２２】
なお、仮想ノード管理部４０２は、先頭ビット列の大きな方からではなく、小さい方から半数のハッシュ値域を選択するようにしてもよい。あるいは、仮想ノード管理部４０２は、中央など、所定の位置から半数のハッシュ値域を選択してもよい。
【０１２３】
また、仮想ノード管理部４０２は、半数（１／２）ではなく、他の比率（例えば、１／３又は１／４）のハッシュ値域を選択してもよい。例えば、「１、２、４」は、公比「２」の等比数列の一部である。つまり、仮想ノード管理部４０２は、仮想ノードの大きさの比率が、公比が「２」の等比数列の関係となるように、仮想ノードを作成している。
【０１２４】
そこで、仮想ノード管理部４０２は、ハッシュ値域の段階的な大きさを決定する等比数列の公比として「２」以外の値を用いてもよい。つまり、仮想ノード管理部４０２は、仮想ノードの大きさとして、公比が「２」以外の等比数列の関係となる段階的な大きさの仮想ノードを作成してもよい。
【０１２５】
（効果の説明）
次に、本実施形態の効果について説明する。
【０１２６】
第１の実施形態に係る記憶システム２０の記憶装置４０は、冗長性及びスケーラビリティを低下させることなく、容量効率を向上させるとの効果を奏することができる。
【０１２７】
この理由は、次のとおりである。
【０１２８】
本実施形態の記憶システム２０に含まれる記憶装置４０の状態判定部４０３は、記憶装置４０の構成変更を検出する。そして、構成変更が発生した場合、仮想ノード管理部４０２が、変更後の構成に対応した仮想ノードを設定する。仮想ノード管理部４０２は、仮想ノードを割り当てるハッシュ値域の分割を、均等分割ではなく、異なる範囲の分割となるように分割する。例えば、仮想ノード管理部４０２は、ハッシュ値域の範囲として「４：２：１」となるようにハッシュ値域を分割する。そして、仮想ノード管理部４０２は、大きさが異なるハッシュ値域を仮想ノードに割り当てる。
【０１２９】
このように、本実施形態の記憶装置４０は、段階的な大きさの仮想ノードを作成できる。そのため、本実施形態の記憶装置４０は、データを格納することができない領域を削減できる。つまり、本実施形態の記憶装置４０は、容量効率の高い分散配置を実行できるためである
また、本実施形態の記憶装置４０は、仮想ノード当たりのコンテナ５０１の数が、一般的な分散配置ストレージシステムと同程度である。
【０１３０】
そのため、本実施形態に係る記憶システム２０は、冗長性及びスケーラビリティを低下させない。
【０１３１】
例えば、本実施形態の記憶システム２０において、記憶装置４０の数と仮想ノード数との対応関係は、一般的な分散配置ストレージシステムの対応関係と同様である。そのため、本実施形態における仮想ノードの数の変更の発生頻度は、一般的な分散配置ストレージシステムと同程度である。
【０１３２】
また、記憶装置４０は、フラグメントデータの書き込み及び読み出しの時間を削減するとの効果を奏する。
【０１３３】
これは次のような理由のためである。
【０１３４】
仮想ノード管理部４０２は、ハッシュ値域の大きさと先頭ビット列の長さとを反比例させる。そのため、選択される回数が多い大きなハッシュ値域は、判定に用いる先頭ビット列が短い。そのため、フラグメント処理部４０１におけるハッシュ値域の判定時間が、短くなる。このように、本実施形態の記憶装置４０は、フラグメントデータの書き込み及び読み出しの時間を削減する効果を奏する。
【０１３５】
［変形例］
以上の説明した記憶装置４０は、次のように構成される。
【０１３６】
例えば、記憶装置４０の各構成部は、ハードウェア回路で構成されても良い。
【０１３７】
また、記憶装置４０は、各構成部が、ネットワークを介して接続した複数の装置を用いて、構成されても良い。
【０１３８】
また、記憶装置４０は、複数の構成部を１つのハードウェアで構成しても良い。
【０１３９】
また、記憶装置４０は、ＣＰＵ（Central Processing Unit）と、ＲＯＭ（Read Only Memory）と、ＲＡＭ（Random Access Memory）とを含むコンピュータ装置として実現してもよい。記憶装置４０は、上記構成に加え、さらに、入出力接続回路（ＩＯＣ：Input / Output Circuit）と、ネットワークインターフェース回路（ＮＩＣ：Network Interface Circuit）とを含むコンピュータ装置として実現しても良い。
【０１４０】
図１２は、本変形例に係る記憶装置６０の構成の一例を示すブロック図である。
【０１４１】
記憶装置６０は、ＣＰＵ６１と、ＲＯＭ６２と、ＲＡＭ６３と、データ記憶装置６４と、ＩＯＣ６５と、ＮＩＣ６８とを含み、コンピュータ装置を構成している。
【０１４２】
ＣＰＵ６１は、ＲＯＭ６２からプログラムを読み込む。そして、ＣＰＵ６１は、読み込んだプログラムに基づいて、ＲＡＭ６３と、データ記憶装置６４と、ＩＯＣ６５と、ＮＩＣ６８とを制御する。そして、ＣＰＵ６１を含むコンピュータは、これらの構成を制御し、図１に示す、フラグメント処理部４０１と、仮想ノード管理部４０２と、状態判定部４０３としての各機能を実現する。
【０１４３】
ＣＰＵ６１は、各機能を実現する際に、ＲＡＭ６３又はデータ記憶装置６４を、プログラムの一時記憶として使用しても良い。
【０１４４】
また、ＣＰＵ６１は、コンピュータで読み取り可能にプログラムを記憶した記憶媒体８０が含むプログラムを、図示しない記憶媒体読み取り装置を用いて読み込んでも良い。あるいは、ＣＰＵ６１は、ＮＩＣ６８を介して、図示しない外部の装置からプログラムを受け取り、ＲＡＭ６３に保存して、保存したプログラムを基に動作しても良い。
【０１４５】
ＲＯＭ６２は、ＣＰＵ６１が実行するプログラム及び固定的なデータを記憶する。ＲＯＭ６２は、例えば、Ｐ−ＲＯＭ（Programmable-ROM）又はフラッシュＲＯＭである。
【０１４６】
ＲＡＭ６３は、ＣＰＵ６１が実行するプログラム及びデータを一時的に記憶する。ＲＡＭ６３は、例えば、Ｄ−ＲＡＭ（Dynamic-RAM）である。
【０１４７】
データ記憶装置６４は、記憶装置６０が長期的に保存するデータ及びプログラムを記憶する。さらに、データ記憶装置６４は、図１に示すデータ記憶部５００として動作する。また、データ記憶装置６４は、ＣＰＵ６１の一時記憶装置として動作しても良い。データ記憶装置６４は、例えば、ハードディスク装置、光磁気ディスク装置、ＳＳＤ（Solid State Drive）又はディスクアレイ装置である。
【０１４８】
ここで、ＲＯＭ６２とデータ記憶装置６４は、不揮発性（non-transitory）の記憶媒体である。一方、ＲＡＭ６３は、揮発性（transitory）の記憶媒体である。そして、ＣＰＵ６１は、ＲＯＭ６２、データ記憶装置６４、又は、ＲＡＭ６３に記憶されているプログラムを基に動作可能である。つまり、ＣＰＵ６１は、不揮発性記憶媒体又は揮発性記憶媒体を用いて動作可能である。
【０１４９】
ＩＯＣ６５は、ＣＰＵ６１と、入力機器６６及び表示機器６７とのデータを仲介する。ＩＯＣ６５は、例えば、ＩＯインターフェースカード又はＵＳＢ（Universal Serial Bus）カードである。
【０１５０】
入力機器６６は、記憶装置６０の操作者からの入力指示を受け取る機器である。入力機器６６は、例えば、キーボード、マウス又はタッチパネルである。
【０１５１】
表示機器６７は、記憶装置６０の操作者に情報を表示する機器である。表示機器６７０は、例えば、液晶ディスプレイである。
【０１５２】
ＮＩＣ６８は、記憶装置６０とネットワーク５０との通信を中継する。ＮＩＣ６８は、例えば、ＬＡＮ（Local Area Network）カードである。
【０１５３】
このように構成された記憶装置６０は、記憶装置４０と同様の効果を得ることができる。
【０１５４】
その理由は、記憶装置６０のＣＰＵ６１が、プログラムに基づいて記憶装置４０と同様の機能を実現できるためである。
【０１５５】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成及び詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１５６】
本発明は、仮想的なストレージデバイスに対して冗長符号を用いたグリッドストレージに利用可能である。
【符号の説明】
【０１５７】
２０    記憶システム
４０    記憶装置
５０    ネットワーク
６０    記憶装置
６１    ＣＰＵ
６２    ＲＯＭ
６３    ＲＡＭ
６４    データ記憶装置
６５    ＩＯＣ
６６    入力機器
６７    表示機器
６８    ＮＩＣ
７０    ハッシュ値域
８０    記憶媒体
１１０    サーバ
１２０    ストレージシステム
１３０    アクセスノード
１４０    ストレージノード
１５０    ネットワーク
４０１    フラグメント処理部
４０２    仮想ノード管理部
４０３    状態判定部
４１０    仮想ノード
４１１    コンテナ
４１２    先頭ビット列
５００    データ記憶部
５０１    コンテナ
６０１    保存データ
６０２    ブロックデータ
６０３    フラグメントデータ
６０４    冗長パリティ
６０５    フラグメントデータ
７０１    先頭ビット列
７０２    ハッシュ値域
８０１    先頭ビット列
８０２    ハッシュ値域
９０１    先頭ビット列
９０２    ハッシュ値域
【図１】
0006269530.tif 000002
【図２】
0006269530.tif 000003
【図３】
0006269530.tif 000004
【図４】
0006269530.tif 000005
【図５】
0006269530.tif 000006
【図６】
0006269530.tif 000007
【図７】
0006269530.tif 000008
【図８】
0006269530.tif 000009
【図９】
0006269530.tif 000010
【図１０】
0006269530.tif 000011
【図１１】
0006269530.tif 000012
【図１２】
0006269530.tif 000013