(57)【要約】【課題】KVペアのデータサイズに偏りがあっても、パーティションの再配置を行なうことなく、データ量の偏りの抑制と負荷の分散化とを図る。【解決手段】データノード管理装置１０は、データノード２０に対する命令を受け付ける指示受付部１１と、命令が書き込み命令である場合に、対象となるペアデータのキー値に添え字を付与するペアデータ変換処理部１２と、ペアデータを親ペアデータとして、それに含まれるデータを設定数に分割し、分割後の各データと親ペアデータのキー値とで子ペアデータを生成し、各子ペアデータのキー値の添え字を識別番号に書き換えるペアデータ分割部１３と、子ペアデータを識別番号の順にデータノード２０に格納するデータノードアクセス部１４と、読み込み命令である場合にリストに基づいて子ペアノードを取得して結合するデータ結合部１５とを備えている。【選択図】図１
2018159987.tif 000002
【特許請求の範囲】
【請求項１】
データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えている、ことを特徴とするデータノード管理装置。
【請求項２】
前記ペアデータ変換処理部が、前記書き込み命令が受け付けられると前記書き込み対象となるペアデータにおいて、データに、分割の有無及び状態を示すフラグを付与し、そして、前記子ペアデータの前記データノードへの格納が終了すると、前記親ペアデータの前記フラグを分割ありに設定し、
前記ペアデータ分割部が、前記書き込み対象となるペアデータにおいて、設定された分割数に応じて子ペアデータヘの分割を行なう、
請求項１に記載のデータノード管理装置。
【請求項３】
前記書き込み命令が受け付けられた場合に、前記書き込み対象となるペアデータのデータに、当該データノード管理装置の識別子とタイムスタンプとを付与し、
更に、前記子ペアノードの前記データノードへの格納が終了した場合に、前記親ペアデータのデータに付与されている、前記識別子と前記タイムスタンプとを取得し、取得した前記識別子と前記タイムスタンプとが、当該データノード管理装置によって付与されたものかどうかを判定し、付与されたものでない場合は、前記書き込み命令はタイムアウトしているとする、タイムスタンプ判定部を備えている、
請求項２に記載のデータノード管理装置。
【請求項４】
データとそれに対応するキー値とをペアデータとして格納するデータノードと、データノード管理装置とを備え、
前記データノード管理装置は、
前記データノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えている、ことを特徴とするストレージシステム。
【請求項５】
前記データノードが、
前記データノードが格納する前記ペアデータの中から前記子ペアデータを特定し、特定した前記子ペアデータのうち、設定条件を満たす子ペアデータを削除する、ペアデータ削除部を更に備えている、
請求項４に記載のストレージシステム。
【請求項６】
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とするデータノード管理方法。
【請求項７】
コンピュータに、
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データノードで構成されたストレージシステム、データノードの管理を行なう、データノード管理装置、及びデータノード管理方法に関し、更には、これらを実現するためのプログラムに関する。
【背景技術】
【０００２】
KVSは、保存対象となるデータ（Value）に対して、対応する一意の標識（Key）を設定し、これらをペア（ＫＶペア）で保存するデータストアである。また、KVSのうち、特に、複数のサーバ装置又は記憶装置に分散してデータを保存できる機能をもったものは、「分散KVS」と呼ばれている。
【０００３】
分散KVSは、近年、極めて大量のデータを保管する分野において注目されている。例えば、Voldemort（非特許文献１参照）は、分散ＫＶＳが実装されたシステムのひとつである。一般に、分散KVSは、スケーラビリティに優れており、ノードの数だけ膨大なデータを格納することが可能となる。
【０００４】
また、分散KVSでは、キー値を基にハッシュ関数によって算出されたハッシュ値によって、格納先のノードが決定される。特に、Consistent Hashing（例えば、特許文献１参照）は、分散KVSシステムにおいて、データの格納先を決めるための手法として、利用されている。Consistent Hashingでは、ハッシュ空間は、均等なQ個のパーティションに分割される。また、Q／N個のパーティションが、各ノードに割り当てられる。Nは全体ノードの数である。
【０００５】
但し、Valueのデータサイズに偏りがある論理データ構造の場合、ノード毎に格納しているデータ量が異なり、ノード間に偏りが生じてしまう。この結果、データサイズの大きなValueを持つキー値の格納先となっている特定のノードに、大きな負荷がかかってしまう。また、このようなノードにおいては、KVペアの取得時のTAT（Turn Around Time）が増加してしまう。
【０００６】
特に、分散KVSをRDB（Relational Database）に適用する場合は、検索性を高めるために、特定の値及び属性によってレコードがまとめられるので、１つのKeyに複数のデータが格納される。このため、Valueが大きくなってしまうケースが多くなってしまう。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１１−９５９７６号公報
【非特許文献】
【０００８】
【非特許文献１】“Project Voldemort”，［online］，［平成29年3月1日検索］，インターネット＜URL：http://www.project-voldemort.com/＞
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述のノード間におけるデータ量の偏りを解消するための手法として、割り当てたパーティションを再配置して、各ノードのデータ量を均一にする手法が提案されている。しかしながら、パーティションの再配置に伴って、データの再配置も発生するため、既存ノード間のデータ移動が大量に起こる可能性がある。この結果、上記手法を実行する場合には、大きなコストがかかってしまう。
【００１０】
本発明の目的の一例は、KVペアのデータサイズに偏りがあっても、パーティションの再配置を行なうことなく、データ量の偏りの抑制と負荷の分散化とを図り得る、ストレージシステム、データノード管理装置、データノード管理方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１１】
上記目的を達成するため、本発明の一側面におけるデータノード管理装置は、
データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えている、ことを特徴とする。
【００１２】
上記目的を達成するため、本発明の一側面におけるストレージシステムは、データとそれに対応するキー値とをペアデータとして格納するデータノードと、データノード管理装置とを備え、
前記データノード管理装置は、
前記データノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えていることを特徴とする。
【００１３】
また、上記目的を達成するため、本発明の一側面におけるデータノード管理方法は、
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とする。
【００１４】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、
コンピュータに、
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とする。
【発明の効果】
【００１５】
以上のように、本発明によれば、KVペアのデータサイズに偏りがあっても、パーティションの再配置を行なうことなく、データ量の偏りの抑制と負荷の分散化とを図ることができる。
【図面の簡単な説明】
【００１６】
【図１】図１は、本発明の実施の形態におけるデータノード管理装置の概略構成を示すブロック図である。
【図２】図２は、本発明の実施の形態におけるデータノード管理装置の具体的構成を示すブロック図である。
【図３】図３（ａ）〜（ｃ）は、それぞれ、本実施の形態におけるペアデータに付加される添え字とフラグとの具体例を示す図である。
【図４】図４は、ペアデータの分割を模式的に示す図である。
【図５】図５は、本発明の実施の形態におけるデータノード管理装置の書き込み命令発行時の動作を示すフロー図である。
【図６】図６は、本発明の実施の形態における子KVペアの格納先の決定手法の一例を説明する説明図である。
【図７】図７は、本発明の実施の形態における子KVペアの格納先の決定手法の他の例を説明する説明図である。
【図８】図８は、本発明の実施の形態におけるデータノード管理装置の読み込み命令発行時の動作を示すフロー図である。
【図９】図９は、本発明の実施の形態におけるデータノードの他の例を示すブロック図である。
【図１０】図１０は、本発明の実施の形態におけるデータノード管理装置１０を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１７】
（本発明の概要）
本発明では、Valueサイズの大きなKVペアは、格納先となるKVSデータノードの数に応じて、自動的に複数のKVペアに分割されてから格納される。また、読み出し時においては、分割されたKVペアがすべて読み出され、読み出されたKVペアが結合された後、結合後のKVペアが返却される。
【００１８】
更に、本発明では、分割後のKVペアは、格納される段階で、格納対象となるKVSデータノードの数に応じて、最大数で分割されるので、ノード間でのデータの偏りを未然に防ぐことが可能となる。また、分割後のKVペアに対して、並列に読み込み及び書き込みを実行することで、サイズの大きなKVペアの操作に伴うレイテンシも改善することができる。
【００１９】
（実施の形態）
以下、本実施の形態における、データノード管理装置、ストレージシステム、データノード管理方法、及びプログラムについて、図１〜図１０を参照しながら説明する。
【００２０】
［装置構成］
最初に、図１を用いて、本実施の形態におけるデータノード管理装置の構成について説明する。図１は、本発明の実施の形態におけるデータノード管理装置の概略構成を示すブロック図である。
【００２１】
図１に示す本実施の形態におけるデータノード管理装置１０は、データとそれに対応するキー値とをペアデータとして格納するデータノード２０を管理するための装置である。データノード管理装置１０は、各データノード２０に、ネットワーク３０を介して接続されており、データノード２０と共に、ストレージシステム１００を構築している。
【００２２】
図１に示すように、データノード管理装置１０は、指示受付部１１と、ペアデータ変換処理部１２と、ペアデータ分割部１３と、データノードアクセス部１４と、データ統合部１５とを備えている。
【００２３】
指示受付部１１は、外部から、データノード２０に対する命令、即ち、書き込み命令（put）又は読み込み命令（get）を受け付ける。
【００２４】
ペアデータ変換処理部１２は、受け付けられた命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する。
【００２５】
ペアデータ分割部１３は、まず、書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成する。また、ペアデータ分割部１３は、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換える。更に、ペアデータ分割部１３は、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する。
【００２６】
データノードアクセス部１４は、分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている識別番号の順に、いずれかのデータノード２０に格納する。
【００２７】
データ結合部１５は、受け付けられた命令が読み込み命令である場合に、親ペアデータが格納しているリストに基づいて、読み込み対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する。
【００２８】
このように、本実施の形態では、書き込み対象となるデータは、設定数、例えば、データノード２０の数に応じて分割され、分割された子ノードは、キー値に付与された識別番号によって管理される。また、読み込みの際には、キー値に付与された識別番号を元に、各データノード２０から子ペアデータが取得され、これらが結合される。このため、本実施の形態によれば、KVペアのデータサイズに偏りがあっても、パーティションの再配置を行なうことなくノード間のデータの偏りが抑制され、負荷が分散される。
【００２９】
続いて、図２を用いて、本実施の形態におけるデータノード管理装置１０の構成についてより具体的に説明する。図２は、本発明の実施の形態におけるデータノード管理装置の具体的構成を示すブロック図である。
【００３０】
図２に示すように、本実施の形態では、複数のデータノード２０は、分散KVSシステムを構築している。本実施の形態におけるペアデータは、KVペアである。よって、以降の説明においては、ペアデータはKVペアとも表記する。また、これに合わせて、親ペアデータは、親KVペア、子ペアデータは子KVペアとも表記する。また、データノード２０は、計算機であり、それが備えるストレージに、KVペアを格納している。
【００３１】
また、図２に示すように、本実施の形態では、データノード管理装置１０には、クライアント端末４０が接続されている。クライアント端末４０は、ユーザの操作に応じて、データノード２０に対して、書き込み命令（put）及び読み込み命令（get）を発行し、これをデータノード管理装置１０に入力する。
【００３２】
また、本実施の形態において、データノード２０の数は特に限定されるものではない。更に、図２の例では、図示されているクライアント端末４０は１つであるが、実際には、クライアント端末４０の数も複数である。そして、一般的な分散KVSシステムでは、複数のデータノード２０は、不特定多数のクライアント端末４０と通信し、その要求に応じて処理を実行する。本実施の形態では、クライアント端末４０とデータノード２０との間に、データノード管理装置１０が配置される。
【００３３】
更に、本実施の形態においては、１つの分散KVSシステムにおいて、データノード管理装置１０は、複数存在していても良い。加えて、一つのデータノード管理装置１０が、複数のクライアント端末４０からの命令を並列に受け付けることもできる。
【００３４】
また、図２に示すように、本実施の形態では、データノード管理装置１０は、上述した指示受付部１１、ペアデータ変換処理部１２、ペアデータ分割部１３、データノードアクセス部１４、及びデータ統合部１５に加えて、タイムスタンプ判定部１６も備えている。
【００３５】
指示受付部１１は、本実施の形態では、クライアント端末４０から、データノード２０に対する、書き込み命令（put）及び読み込み命令（get）を受け付ける。また、指示受付部１１は、受け付けた命令に対する結果を、クライアント端末４０に返却する。
【００３６】
ペアデータ変換処理部１２は、本実施の形態では、指示受付部１１で書き込み命令が受け付けられると書き込み対象となるKVペアにおいて、そのデータに、分割の有無及び状態を示すフラグを付与する。また、ペアデータ変換処理部１２は、分割後の子KVペアのデータノード２０への格納が終了すると、親KVペアのフラグを「分割あり」に設定する。
【００３７】
データノードアクセス部１４は、本実施の形態では、各子KVペアをデータノード２０に格納する場合は、各データノードに対して、書き込み命令（put）を発行する。また、データノードアクセス部１４は、各データノード２０から、各子KVペアを取得する場合は、各データノード２０に対して、読み込み命令（get）を発行する。
【００３８】
タイムスタンプ判定部１６は、まず、指示受付部１１で書き込み命令が受け付けられると、書き込み対象となるKVペアのデータに、データノード管理装置１０の識別子とタイムスタンプとを付与する。具体的には、タイムスタンプ判定部１６は、図３に示した分割フラグ：L（ロック中）のKVペアが生成される際に、識別子とタイムスタンプとを付与する。
【００３９】
また、タイムスタンプ判定部１６は、子KVペアのデータノード２０への格納が終了した場合は、親KVペアのデータに付与されている、識別子とタイムスタンプとを取得する。そして、タイムスタンプ判定部１６は、取得した識別子とタイムスタンプとが、自身を備えているデータノード管理装置１０によって付与されたものかどうかを判定する。判定の結果、付与されたものでない場合は、タイムスタンプ判定部１６は、書き込み命令はタイムアウトしているとする。
【００４０】
ここで、図３及び図４を用いて、ペアデータ変換処理部１２、ペアデータ分割部１３、及びデータ結合部１５の処理について具体的に説明する。図３（ａ）〜（ｃ）は、それぞれ、本実施の形態におけるペアデータに付加される添え字とフラグとの具体例を示す図である。図４は、ペアデータの分割を模式的に示す図である。
【００４１】
本実施の形態では、ペアデータ変換処理部１２は、KVペアにおけるキー値とValue部のデータとを、図３（ａ）〜（ｃ）のいずれかに示す形式に書き換える。
【００４２】
具体的には、ペアデータ変換処理部１２は、キー値に、添え字として、「−００００」〜「−９９９９」の形式の４ケタの数字（識別番号）を付与する。また、本実施の形態では、添え字が「−００００」であるものは「親KVペア」とされる。更に、添え字が「−０００１」以降のものは「子KVペア」とされ、分割されたKVペアであることが表される。また、ペアデータ変換処理部１２は、データが格納されているValue部の先頭に、「flag:N」、「flag:D」、「flag:L」といった形式で分割フラグを付与する。
【００４３】
また、ペアデータ変換処理部１２は、読み込み命令（get）の結果を、クライアント端末４０に返却する時は、キー値の4ケタの添え字「−００００」と、Value部の分割フラグとを取り除いた元の形式で、KVペアを返却する。
【００４４】
また、本実施の形態では、ペアデータ分割部１３は、図４に示すように、元のKVペアを複数の子KVペアに分割し、更に、親KVペアを生成する。また、このとき、ペアデータ分割部１３は、元のKVペアのValue部のデータを設定された分割数に応じて分割し、子KVペアに格納する。
【００４５】
更に、本実施の形態では、データ結合部１５は、親KVペアのValue部に格納されているキー値のリスト（図４参照）に基づいて、図４に示す形式に分割されたKVペアを取得し、これらのデータを結合する。
【００４６】
［装置動作］
次に、本発明の実施の形態におけるデータノード管理装置１０の動作について図５〜図８を用いて説明する。以下の説明においては、適宜図１〜図４を参酌する。また、本実施の形態では、データノード管理装置１０を動作させることによって、データノード管理方法が実施される。よって、本実施の形態におけるデータノード管理方法の説明は、以下のデータノード管理装置の動作説明に代える。
【００４７】
最初に、図５〜図７を用いて、クライアント端末４０から書き込み命令が発行されて、データ格納処理が指示された場合について説明する。図５は、本発明の実施の形態におけるデータノード管理装置の書き込み命令発行時の動作を示すフロー図である。
【００４８】
まず、前提として、クライアント端末４０がデータ格納処理を実施する場合、クライアント端末４０は、put要求とputするKVペアとを、データノード管理装置１０に発行する。これにより、図５に示す処理が実行される。
【００４９】
図５に示すように、最初に、指示受付部１１は、クライアント端末４０から、データノード２０に対する、データ格納処理を受け付ける（ステップＡ１）。
【００５０】
次に、ペアデータ変換処理部１２は、「元のキー値-0000」を用いて、データノード１０に対して、読み込み処理（get処理）を行い（ステップＡ２）、「親KVペア」の存在有無を確認する（ステップＡ３）。
【００５１】
ステップＡ３の判定の結果、既に親KVペアが存在している場合は、ペアデータ変換処理部１２は、図３に示した分割フラグを確認し、取得した親KVペアの分割フラグが「L」であるかどうかを判定する（ステップＡ１３）。
【００５２】
ステップＡ１３の判定の結果、分割フラグが「flag:L」でない場合は、ペアデータ変換処理部１２は、書き込み処理を継続し、ステップＡ４を実行する。
【００５３】
一方、ステップＡ１３の判定の結果、分割フラグが「flag:L」である場合は、ロック中であり、他のデータノード管理装置が該当するキー値のKVペアを分割して書き込み中であることを表す。その場合は、ペアデータ変換処理部１２は、Value部にタイムスタンプが格納されているので、タイムスタンプと現在の時刻との差分が予め設定されているタイムアウト値を超えているかどうかを判定する（ステップＡ１４）。
【００５４】
ステップＡ１４の判定の結果、タイムスタンプと現在時刻との差分値が予め設定されているタイムアウト値を超えていない場合は、ペアデータ変換処理部１２は、該当するキー値のデータは『書き込み中』であると判断し、書き込み処理は失敗であることを、クライアント端末４０に返却し、一連のデータ格納処理を終了とする（ステップＡ１５）。
【００５５】
一方、ステップＡ１４の判定の結果、タイムスタンプと現在時刻との差分値が予め設定されているタイムアウト値を超えている場合は、他のデータノード管理装置が実施していた書き込みは失敗したものとして、ペアデータ変換処理部１２は、書き込み処理を継続し、後述するステップＡ４を実行する。
【００５６】
ステップＡ３の判定の結果、既に親KVペアが存在していない場合は、ペアデータ変換処理部１２は、クライアント端末４０から受けとったKVペアのデータサイズが閾値を超えていないかどうかを判定する（ステップＡ４）。ステップＡ４の判定の結果、閾値を超えていればステップＡ５以降の分割処理が実行される。
【００５７】
一方、ステップＡ４の判定の結果、閾値を超えていなければ分割処理が実行されずに、ペアデータ変換処理部１２は、格納先となるデータノード２０に、KVペアを格納する（ステップＡ１２）。
【００５８】
具体的には、ステップＡ１２では、ペアデータ変換処理部１２は、図３に示した分割フラグの形式に沿って、キー値に「−００００」を付与し、Value部の先頭には分割フラグを「flag:N」を付与して、KVペアを書換え、データノード２０に格納（put）処理を実施させる。データノード２０による格納処理の完了後、ペアデータ変換処理部１２は、クライアント端末４０にデータ格納処理の完了を返却し、一連のデータ格納処理を終了とする。
【００５９】
ステップＡ５では、分割処理が実行されるので、ペアデータ変換処理部１２は、格納先となるデータノード２０の総数を最大分割数として、格納されるデータ量が閾値を超えないサイズになるように、分割数を決定する。
【００６０】
次に、ペアデータ変換処理部１２は、データノードアクセス部１４を介して、キー値に「−００００」を付与した親KVペアの書き込みを実施する（ステップＡ６）。
【００６１】
具体的には、ペアデータ変換処理部１２は、図３に示した分割フラグの形式に沿って、親KVペアにおいて、キー値に「−００００」を付与し、Value部には、分割フラグ「flag:Ｌ」と、データノード管理装置１０の識別子（装置ID）とを付与する。また、ペアデータ変換処理部１２は、親KVペアのValue部には、実行時のタイムスタンプも付与する。その後、ペアデータ変換処理部１２は、形式を変更した親KVペアのデータ格納処理をデータノード２０に行なわせる。なお、ここで付与される識別子としては、ホスト名とプロセスIDとを合わせたもの等、データノード管理装置１０を一位に特定できるものが挙げられる。
【００６２】
ステップＡ６で、親KVペアが「ロック中」で書き込まれると、ペアデータ分割部１３は、分割数に応じて元のKVペアを、図４に示した子KVペアに分割し、データノードアクセス部１４を介して、各データノード２０に対して分割後の子KVペアの書き込みを指示する（ステップＡ７）。
【００６３】
具体的には、ステップＡ７では、ペアデータ分割部１３は、各子KVペアの分割フラグを「flag:N」とし、キー値の添え字として、分割した順番に「−０００１」から分割数までの識別番号を付与する。
【００６４】
また、ステップＡ７では、ペアデータ分割部１３は、子KVペアの格納先を、図６に示すようにConsistent Hashingの手法を用いて決定することができる。図６は、本発明の実施の形態における子KVペアの格納先の決定手法の一例を説明する説明図である。図６の例では、キー値の添え字が「−００００」である親KVペアのキー値でハッシュされた数字を起点として、子KVペアは順に格納され、分散されていく。
【００６５】
更に、ステップＡ７では、ペアデータ分割部１３は、図７に示すように、子KVペアの書込み時に分散KVSのQuarum判定の仕様に沿ってレプリケーションすることもできる。図７は、本発明の実施の形態における子KVペアの格納先の決定手法の他の例を説明する説明図である。図７の例では、子KVペアは、レプリケーションされるものも含めて、「親KVペア」のキー値でハッシュされた数字を起点として、順番に格納される。
【００６６】
次に、ステップＡ７の終了後、タイプスタンプ判定部１６は、データノード２０に対して読み込みを指示して、親KVペアを再度取得し、更に、親KVペアのデータに付与されている、識別子とタイムスタンプとを取得する。そして、タイムスタンプ判定部１６は、取得した識別子とタイムスタンプとが、自身を備えているデータノード管理装置１０によって付与したものと一致するかどうかを判定する（ステップＡ９）。
【００６７】
ステップＡ９の判定の結果、一致していない場合は、ステップＡ１で受け付けたデータ格納処理はタイムアウトしており、別のデータノード管理装置１０によって書き換えられてしまっている。分割フラグがL以外になっていた場合も同様である。従って、この場合は、
ペアデータ変換処理部１２は、ステップＡ１５を実行し、書き込み処理は失敗であることを、クライアント端末４０に返却し、一連のデータ格納処理を終了とする。
【００６８】
一方、ステップＡ９の判定の結果、一致している場合は、ペアデータ変換処理部１２は、図２に示した分割フラグの形式に沿って、親KVペアのValue部において、分割フラグを「flag:D」とし、子KVペアのキー値のリストを更新する（ステップＡ１０）。また、ペアデータ変換処理部１２は、データノードアクセス部１４を介して、親KVペアへの更新処理としてデータノード２０に対して親KVペアの書き込みを実施する。
【００６９】
その後、ペアデータ変換処理部１２は、クライアント端末４０に対して、データ格納処理の完了を返却し、一連のデータ格納処理を終了とする（ステップＡ１１）。
【００７０】
続いて、図８を用いて、クライアント端末４０から読み込み命令が発行されて、データ取得処理が指示された場合について説明する。図８は、本発明の実施の形態におけるデータノード管理装置の読み込み命令発行時の動作を示すフロー図である。
【００７１】
まず、前提として、クライアント端末４０がデータ取得処理を実施する場合、クライアント端末４０は、get要求とgetするKVペアとを、データノード管理装置１０に発行する。これにより、図８に示す処理が実行される。
【００７２】
図８に示すように、最初に、指示受付部１１は、クライアント端末４０から、データノード２０に対する、データ取得処理を受け付ける（ステップＢ１）。
【００７３】
次に、ペアデータ変換処理部１２は、「元のキー値-0000」を用いて、データノード２０に対して、読み込み処理（get処理）を行い（ステップＢ２）、「親KVペア」の存在有無を確認する（ステップＢ３）。
【００７４】
ステップＢ３の判定の結果、既に親KVペアが存在していない場合は、ペアデータ変換処理部１２は、該当するキー値のKVペアは存在しなかったという結果を、クライアント端末４０に返却し、一連のデータ取得処理を終了とする（ステップＢ８）。
【００７５】
一方、ステップＢ３の判定の結果、既に親KVペアが存在している場合は、ペアデータ変換処理部１２は、このKVペアを取得し、図３に示した分割フラグを確認する。そして、ペアデータ変換処理部１２は、取得したKVペアの分割フラグが「flag:L」であるかどうかを判定する（ステップＢ４）。
【００７６】
ステップＢ４の判定の結果、分割フラグが「flag:L」（ロック中）である場合は、ペアデータ変換処理部１２は、該当するキー値のKVペアは「書き込み中」であることを、クライアント端末４０に返却し、一連のデータ取得処理を終了とする（ステップＢ９）。また、「書き込み中」の情報を受け取ったクライアント端末４０は、データ取得処理を失敗としてもよいし、一定時間待機してリトライしてもよい。
【００７７】
一方、ステップＢ４の判定の結果、分割フラグが「flag:L」でない場合は、ペアデータ変換処理部１２は、更に、取得したKVペアの分割フラグが「flag:N」（分割なし）であるかどうかを判定する（ステップＢ５）。
【００７８】
ステップＢ５の判定の結果、分割フラグが「flag:N」（分割なし）である場合は、ペアデータ変換処理部１２は、取得したKVペアのValue部から分割フラグの情報を除いたものをValue値とし、このValue値をクライアント端末４０に返却し、一連のデータ取得処理を終了とする（ステップＢ９）。
【００７９】
一方、ステップＢ５の判定の結果、分割フラグが「flag:N」（分割なし）でない場合、即ち、分割フラグが「flag:D」（分割あり）である場合は、ペアデータ変換処理部１２は、Value部にある子KVペアのキー値リストを元に、データノード２０に対して読み込み処理を実施し、リストにある子KVペアのデータを全て取得する（ステップＢ６）。
【００８０】
次に、ステップＢ６の実行後、ペアデータ変換処理部１２は、取得した子KVペアのValue部のデータを、キー値の添え字の識別番号の順に沿って結合し、結合できたデータをValue値としてクライアント端末４０に返却し、一連のデータ取得処理を終了とする（ステップＢ７）。
【００８１】
［実施の形態における効果］
以上のように、本実施の形態では、データサイズの大きなKVペアは、格納先のデータノードの数に応じて分割され、分散されて格納されるので、特定のノードにデータが偏ることが、格納の段階で回避される。
【００８２】
また、本実施の形態では、分割されたKVペアは、各ノードに分散されているため、データノードの数だけ並列して読み込み処理又は書き込み処理を実施することが可能となるので、レイテンシの改善が期待できる。
【００８３】
KVペアの分割及び結合は、データノード管理装置１０を経由して、システム内部で自動的に実行されるので、ユーザは、分割及び結合の処理を意識せずに、分散KVSシステムを運用できる。更に、ユーザは、データモデル設計時において、データサイズの大きなKVペアが生成されることを考慮しなくても良く、自由に設計を行なうことができる。
【００８４】
［変形例］
ここで、本実施の形態における変形例について図９を用いて説明する。図９は、本発明の実施の形態におけるデータノードの他の例を示すブロック図である。図９に示すように、本変形例では、データノード２０は、通信部２１と、ストレージ２２と、ペアデータ削除部２３とを備えている。
【００８５】
このうち、通信部２１は、データノード管理装置１０からの命令の受信、KVペアの送受信を行なっている。ストレージ２２は、KVペア（親KVペア、子KVペア）を格納する。ペアデータ削除部２３は、データノード２０が格納するKVペアの中から子KVペアを特定し、特定した子KVペアのうち、設定条件を満たす子ペアデータを削除する。
【００８６】
図５に示した処理が実行され、何らかの原因で一連の書き込み処理が中断されてしまった場合に、途中まで書き込まれた子KVペアが、その後どのデータノード管理装置からも参照されず、不要なデータとしてデータノード２０に残り続けてしまう可能性がある。このような中断が生じる場合としては、分割及び書き込みが決定され、先に親KVペアがロック中で書き込まれた後、分割後の子KVペアが書き込まれている途中で、データノード管理装置１０がダウンしたり、タイムアウトと判定され、他のデータノード管理装置に親KVペアが書き換えられたりした場合である。このような場合、親KVペアのロックはタイムアウトにより解除されるが、途中まで書き込まれた子KVペアは、データノード２０に残り続けてしまう。
【００８７】
これに対して、本変形例では、ペアデータ削除部２３は、このような不要な子KVペアを削除する。具体的には、ペアデータ削除部２３は、定期的に（ユーザが予め設定したタイミングで）、ストレージ２２内の子KVペア（添え字が-0000ではないもの）を全件走査する。そして、ペアデータ削除部２３は、走査において、例えば、親KVペア（添え字が-0000のもの）をgetできない子KVペア、親KVペアのValue部内のキー値リストに含まれていない子KVペアを見つけると、これらを削除する。この結果、障害又はタイムアウトによって書き込み処理が中断され、不要な子KVペアがストレージ２２内に溜まってしまうことが回避される。
【００８８】
［プログラム］
本発明の実施の形態におけるプログラムは、コンピュータに、図５に示すステップＡ１〜Ａ１５、図８に示すＢ１〜Ｂ１０を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態におけるデータノード管理装置１０とデータノード管理方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、指示受付部１１、ペアデータ変換処理部１２、ペアデータ分割部１３、データノードアクセス部１４、データ統合部１５、及びタイムスタンプ判定部１６として機能し、処理を行なう。
【００８９】
また、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、指示受付部１１、ペアデータ変換処理部１２、ペアデータ分割部１３、データノードアクセス部１４、データ統合部１５、及びタイムスタンプ判定部１６のいずれかとして機能しても良い。
【００９０】
ここで、本実施の形態におけるプログラムを実行することによって、データノード管理装置１０を実現するコンピュータについて図１０を用いて説明する。図１０は、本発明の実施の形態におけるデータノード管理装置１０を実現するコンピュータの一例を示すブロック図である。
【００９１】
図１０に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。
【００９２】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００９３】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００９４】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００９５】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体が挙げられる。
【００９６】
なお、本実施の形態におけるデータノード管理装置１０は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、データノード管理装置１０は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００９７】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記１１）によって表現することができるが、以下の記載に限定されるものではない。
【００９８】
（付記１）
データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えている、ことを特徴とするデータノード管理装置。
【００９９】
（付記２）
前記ペアデータ変換処理部が、前記書き込み命令が受け付けられると前記書き込み対象となるペアデータにおいて、データに、分割の有無及び状態を示すフラグを付与し、そして、前記子ペアデータの前記データノードへの格納が終了すると、前記親ペアデータの前記フラグを分割ありに設定し、
前記ペアデータ分割部が、前記書き込み対象となるペアデータにおいて、設定された分割数に応じて子ペアデータヘの分割を行なう、
付記１に記載のデータノード管理装置。
【０１００】
（付記３）
前記書き込み命令が受け付けられた場合に、前記書き込み対象となるペアデータのデータに、当該データノード管理装置の識別子とタイムスタンプとを付与し、
更に、前記子ペアノードの前記データノードへの格納が終了した場合に、前記親ペアデータのデータに付与されている、前記識別子と前記タイムスタンプとを取得し、取得した前記識別子と前記タイムスタンプとが、当該データノード管理装置によって付与されたものかどうかを判定し、付与されたものでない場合は、前記書き込み命令はタイムアウトしているとする、タイムスタンプ判定部を備えている、
付記２に記載のデータノード管理装置。
【０１０１】
（付記４）
データとそれに対応するキー値とをペアデータとして格納するデータノードと、データノード管理装置とを備え、
前記データノード管理装置は、
前記データノードに対する命令を受け付ける、指示受付部と、
受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ペアデータ変換処理部と、
書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ペアデータ分割部と、
分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかの前記データノードに格納する、データノードアクセス部と、
受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、データ結合部と、
を備えている、ことを特徴とするストレージシステム。
【０１０２】
（付記５）
前記データノードが、
前記データノードが格納する前記ペアデータの中から前記子ペアデータを特定し、特定した前記子ペアデータのうち、設定条件を満たす子ペアデータを削除する、ペアデータ削除部を更に備えている、
付記４に記載のストレージシステム。
【０１０３】
（付記６）
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とするデータノード管理方法。
【０１０４】
（付記７）
前記（ｂ）のステップにおいて、前記書き込み命令が受け付けられると前記書き込み対象となるペアデータにおいて、データに、分割の有無及び状態を示すフラグを付与し、そして、前記子ペアデータの前記データノードへの格納が終了すると、前記親ペアデータの前記フラグを分割ありに設定し、
前記（ｃ）のステップにおいて、前記書き込み対象となるペアデータで、設定された分割数に応じて子ペアデータヘの分割を行なう、
付記６に記載のデータノード管理方法。
【０１０５】
（付記８）
（ｆ）前記書き込み命令が受け付けられた場合に、前記書き込み対象となるペアデータのデータに、当該データノード管理装置の識別子とタイムスタンプとを付与する、ステップと、
（ｇ）前記子ペアノードの前記データノードへの格納が終了した場合に、前記親ペアデータのデータに付与されている、前記識別子と前記タイムスタンプとを取得し、取得した前記識別子と前記タイムスタンプとが、当該データノード管理装置によって付与されたものかどうかを判定し、付与されたものでない場合は、前記書き込み命令はタイムアウトしているとする、ステップと、
を更に有する、付記７に記載のデータノード管理方法。
【０１０６】
（付記９）
コンピュータに、
（ａ）データとそれに対応するキー値とをペアデータとして格納するデータノードに対する命令を受け付ける、ステップと、
（ｂ）受け付けられた前記命令が書き込み命令である場合に、書き込み対象となるペアデータにおいて、キー値に、予め設定された添え字を付与する、ステップと、
（ｃ）書き込み対象となるペアデータを親ペアデータとして、親ペアデータに含まれるデータを設定数に分割し、分割された各データと親ペアデータのキー値とを合わせて、子ペアデータを生成し、その際、各子ペアデータのキー値に付与されている添え字を、子ペアデータ毎に異なる連続した識別番号に書き換え、更に、親ペアデータのデータに、各子ペアデータのキー値のリストを格納する、ステップと、
（ｄ）分割によって生成した子ペアデータを、各子ペアデータのキー値に付与されている前記識別番号の順に、いずれかのデータノードに格納する、ステップと、
（ｅ）受け付けられた命令が読み込み命令である場合に、前記リストに基づいて、読込対象となるペアデータの子ペアノードを取得し、取得した子ペアノードを結合する、ステップと、
を有する、ことを特徴とするプログラム。
【０１０７】
（付記１０）
前記（ｂ）のステップにおいて、前記書き込み命令が受け付けられると前記書き込み対象となるペアデータにおいて、データに、分割の有無及び状態を示すフラグを付与し、そして、前記子ペアデータの前記データノードへの格納が終了すると、前記親ペアデータの前記フラグを分割ありに設定し、
前記（ｃ）のステップにおいて、前記書き込み対象となるペアデータで、設定された分割数に応じて子ペアデータヘの分割を行なう、
付記９に記載のプログラム。
【０１０８】
（付記１１）
前記コンピュータに、
（ｆ）前記書き込み命令が受け付けられた場合に、前記書き込み対象となるペアデータのデータに、当該データノード管理装置の識別子とタイムスタンプとを付与する、ステップと、
（ｇ）前記子ペアノードの前記データノードへの格納が終了した場合に、前記親ペアデータのデータに付与されている、前記識別子と前記タイムスタンプとを取得し、取得した前記識別子と前記タイムスタンプとが、当該データノード管理装置によって付与されたものかどうかを判定し、付与されたものでない場合は、前記書き込み命令はタイムアウトしているとする、ステップと、
を更に実行させる、付記１０に記載のプログラム。
【産業上の利用可能性】
【０１０９】
以上のように、本発明によれば、KVペアのデータサイズに偏りがあっても、パーティションの再配置を行なうことなく、データ量の偏りの抑制と負荷の分散化とを図ることができる。本発明は、ストレージシステム、特に分散KVSシステムに有用である。
【符号の説明】
【０１１０】
１０  データノード管理装置
１１  指示受付部
１２  ペアデータ変換処理部
１３  ペアデータ分割部
１４  データノードアクセス部
１５  データ統合部
１６  タイムスタンプ判定部
２０  データノード
２１  通信部
２２  ストレージ
２３  ペアデータ削除部
３０  ネットワーク
４０  クライアント端末
１００  ストレージシステム
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2018159987.tif 000003
【図２】
2018159987.tif 000004
【図３】
2018159987.tif 000005
【図４】
2018159987.tif 000006
【図５】
2018159987.tif 000007
【図６】
2018159987.tif 000008
【図７】
2018159987.tif 000009
【図８】
2018159987.tif 000010
【図９】
2018159987.tif 000011
【図１０】
2018159987.tif 000012