(57)【要約】【課題】ネットワークで接続された複数のコンピュータを用いて情報を分散管理する分散型データストアシステムにおいて、コンピューティングリソースの無駄を回避するとともにレスポンス性能を向上させる。【解決手段】ネットワークで接続された複数のノード２−１〜２−３にて、Ｋｅｙによって特定されるレコードを分散管理する分散型データストアシステムにおいて、複数のノード２−１〜２−３は、そのノードが管理する複数のレコードをＫｅｙの任意の範囲毎に集合体として記憶する記憶部５０と、集合体に対して、その集合体の範囲に含まれるＫｅｙを用いたインデクスを付与するインデクス付与部１０と、レコード取得要求に対して、インデクスを参照することにより、レコード取得要求にて要求されたレコードを記憶部５０から取得するレコード取得部４０とを有する。【選択図】図１
2012168781.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークで接続された複数のノードにて、識別子によって特定されるレコードを分散管理する分散型データストアシステムにおいて、
前記複数のノードは、
当該ノードが管理する複数のレコードを前記識別子の任意の範囲毎に集合体として記憶するレコード記憶手段と、
前記集合体に対して、当該集合体の範囲に含まれる識別子を用いたインデクスを付与するインデクス付与手段と、
レコード取得要求に対して、前記インデクスを参照することにより、前記レコード取得要求にて要求されたレコードを前記レコード記憶手段から取得するレコード取得手段とを有することを特徴とする分散型データストアシステム。
【請求項２】
請求項１に記載の分散型データストアシステムにおいて、
前記レコード記憶手段は、
キャッシュ機能を具備するメモリ領域と、
レコードが永続的に記憶されるディスク領域とを具備し、
レコードを前記識別子の昇順または降順で前記メモリ領域に蓄積し、前記メモリ領域に蓄積されたレコードのサイズが所定の閾値を超えた場合に、当該レコードを１つのファイル単位として前記ディスク領域に記憶する記憶制御手段を有する分散型データストアシステム。
【請求項３】
請求項２に記載の分散型データストアシステムにおいて、
前記ディスク領域に記憶された複数のレコードの中から所定の条件に従う複数のレコードを抽出し、当該複数のレコードを前記識別子の昇順または降順で並び替えて新たなファイルを生成するファイル分割手段を有する分散型データストアシステム。
【請求項４】
請求項３に記載の分散型データストアシステムにおいて、
前記識別子は、タイムスタンプを構成要素として具備し、
前記ファイル分割手段は、前記識別子の構成要素のうちタイムスタンプのみが異なるレコードを世代が異なる同一レコードとして認識し、世代が同一となるレコードを１つのファイルとして生成する分散型データストアシステム。
【請求項５】
請求項４に記載の分散型データストアシステムにおいて、
前記レコード取得手段は、レコード取得要求に対して、レコード取得条件に世代の指定がない場合は、前記インデクスを参照して前記レコード取得要求に基づきレコードを前記レコード記憶手段から取得し、前記レコード取得条件に世代の指定がある場合は、指定された世代のファイルから前記レコード取得要求に基づきレコードを前記レコード記憶手段から取得する分散型データストアシステム。
【請求項６】
請求項５に記載の分散型データストアシステムにおいて、
前記インデクス付与手段は、前記メモリ領域に蓄積されたレコードが前記ディスク領域に記憶された契機、または前記新たなファイルが生成された契機で、前記集合体に対して前記インデクスを再付与する分散型データストアシステム。
【請求項７】
ネットワークで接続された複数のノードにて、識別子によって特定されるレコードを分散管理する分散型データストアシステムにおけるレコード管理方法であって、
前記複数のノードが、当該ノードが管理する複数のレコードを前記識別子の任意の範囲毎に集合体として記憶する際に、前記集合体に対して当該集合体の範囲に含まれる識別子を用いたインデクスを付与しておき、レコード取得要求に対して、前記インデクスを参照することにより、前記レコード取得要求にて要求されたレコードを取得する、分散型データストアシステムにおけるレコード管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで接続された複数のコンピュータを用いて情報を分散管理することでスケールアウトを実現する分散型データストアシステムに関し、特に、コンピューティングリソースの無駄を回避し、レスポンス性能を向上させる技術に関する。
【背景技術】
【０００２】
一般的なデータベースにおけるデータの格納は、テーブルスキーマで定義される一定のサイズに従って領域を確保するため、格納したデータのオフセット位置が容易にわかり、任意のレコードやカラムへのアクセスを効率的に行うことができる。
【０００３】
一方、レコード追記型の分散型データストアシステムでは、複数の可変長レコードをまとめてファイルに書き込み、また更新時においても既存のファイルを上書きするのではなく、ファイルの末尾や別ファイルに追記を行うため、所望のレコードを取得するには、これらのファイルを逐一メモリ領域上に読み込んだ上で、そのレコードの有無を確認する処理が必要となり、それにより、１レコードの取得や特定カラムのみを抽出したい場合にも、本来読み込む必要のないファイルへのアクセスが発生し、無駄なコンピューティングリソースの消費や、レスポンスの低下につながる等の非効率な処理が行われることになる。
【０００４】
このような分散型データストアシステムでは、特にＫｅｙとＶａｌｕｅとの組み合わせをレコードとするものがあり、それにおいては、格納するデータであるＶａｌｕｅに、任意のＫｅｙを付与し、連続するＫｅｙとそれに対応するＶａｌｕｅとの組を最小単位として任意のサイズで分割し、ファイルシステムとなるディスク領域に保存することで自動的にＫｅｙ空間を任意の範囲で分割し、分割したＫｅｙ範囲をそれぞれ異なるノードに担当させることによってスケールアウトを実現している。あるＫｅｙに対応するレコードを読み込む際は、そのＫｅｙを含むＫｅｙ範囲を担当しているノードのロケーションをインデクスノードに問い合わせ、そのＫｅｙ範囲を担当しているノードのＩＰアドレス等のロケーション情報を取得した後、それに基づいて、担当ノードに対してＫｅｙに対応するレコードを読み取る要求を行うことで、Ｋｅｙに対応するレコードを読み込む。
【０００５】
また、ノード内では、最近アクセスのあったＫｅｙとＶａｌｕｅとの組はメモリ領域上においておき、それ以外のデータはディスク領域から読み込む。また、更新や挿入等の処理もメモリ領域上でのみ行い、メモリ領域上のＫｅｙとＶａｌｕｅのサイズや、コミットログのサイズが閾値を超えた場合は、マイナーコンパクションと呼ばれる処理が発生し、メモリ領域上の複数のＫｅｙとＶａｌｕｅとの組からなるレコード群をディスク領域上にファイルとして書き出して永続的に記憶している（例えば、非特許文献１参照。）。
【先行技術文献】
【特許文献】
【０００６】
【非特許文献１】OSDI'06:Seventh Symposium on Operating System Design and Implementation, Seattle, WA, November, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述したように分散型データストアシステムにおいては、メジャーコンパクションが実行されない限り、特定のＫｅｙ範囲に対応するディスク領域上のファイルを全て読み込み、どのファイルに目的のデータが含まれるのか確認する必要が生じることとなり、分散ファイルシステムにおいては、ディスク領域に対するディスクＩ／Ｏの負荷や、分散ファイルシステムを構成するノード間のネットワークＩ／Ｏの負荷が高いという問題点がある。
【０００８】
本発明は、上述したような従来の技術が有する問題点に鑑みてなされたものであって、ネットワークで接続された複数のコンピュータを用いて情報を分散管理する分散型データストアシステムにおいて、コンピューティングリソースの無駄を回避するとともにレスポンス性能を向上させることができる分散型データストアシステム及び分散型データストアシステムにおけるレコード管理方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために本発明は、
ネットワークで接続された複数のノードにて、識別子によって特定されるレコードを分散管理する分散型データストアシステムにおいて、
前記複数のノードは、
当該ノードが管理する複数のレコードを前記識別子の任意の範囲毎に集合体として記憶するレコード記憶手段と、
前記集合体に対して、当該集合体の範囲に含まれる識別子を用いたインデクスを付与するインデクス付与手段と、
レコード取得要求に対して、前記インデクスを参照することにより、前記レコード取得要求にて要求されたレコードを前記レコード記憶手段から取得するレコード取得手段とを有することを特徴とする。
【００１０】
また、ネットワークで接続された複数のノードにて、識別子によって特定されるレコードを分散管理する分散型データストアシステムにおけるレコード管理方法であって、
前記複数のノードが、当該ノードが管理する複数のレコードを前記識別子の任意の範囲毎に集合体として記憶する際に、前記集合体に対して当該集合体の範囲に含まれる識別子を用いたインデクスを付与しておき、レコード取得要求に対して、前記インデクスを参照することにより、前記レコード取得要求にて要求されたレコードを取得する。
【発明の効果】
【００１１】
以上説明したように本発明においては、ネットワークで接続された複数のノードにて、識別子によって特定されるレコードを分散管理する場合に、複数のノードのそれぞれにおいて、そのノードが管理する複数のレコードを識別子の任意の範囲毎に集合体として記憶する際に、集合体に対してその集合体の範囲に含まれる識別子を用いたインデクスを付与しておき、レコード取得要求に対して、インデクスを参照することにより、レコード取得要求にて要求されたレコードを取得する構成としたため、識別子の所定の範囲に対応するファイルが複数ある状況においても、目的の識別子が含まれるファイルへアクセスすることができ、それにより、複数のファイルへアクセスする必要が無く、読込み時の応答時間が短縮されるとともに、ファイルシステムやネットワークへの負荷を軽減することができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の分散型データストアシステムの実施の一形態を示す図である。
【図２】図１に示した分散型データストアシステムにおいて記憶部にレコードを書き込む際の処理を説明するための図である。
【図３】図１に示したインデクス付与部にて作成されるインデクスの構成を示す図である。
【図４】図１に示した分散型データストアシステムにおいて記憶部に記憶されたレコードを読み込む際の処理を説明するための図である。
【図５】図１に示した分散型データストアシステムにおいて世代単位でファイルを管理する方法を説明するための図である。
【図６】世代単位で作成されるファイルの構成を示す図であり、（ａ）は全体の構成を示す図、（ｂ）はＫｅｙの構成を示す図、（ｃ）は具体的な構成例を示す図である。
【図７】図１に示した分散型データストアシステムにおけるレコードの読み込み処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１３】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１４】
図１は、本発明の分散型データストアシステムの実施の一形態を示す図である。
【００１５】
本形態は図１に示すように、インデクスノード１と、３つのノード２−１〜２−３とがネットワークで接続されて構成されている。ノード２−１〜２−３にて分散管理されるレコードは、各レコードを一意に識別するための識別子となるＫｅｙとＶａｌｕｅとの組から構成されるＫｅｙ−Ｖａｌｕｅ  Ｓｔｏｒｅ形式（ＫＶＳ形式）のデータ構造である。そして、Ｋｅｙの構成要素は、ＲｏｗＫｅｙ、カラム名及びタイムスタンプとなっており、タイムスタンプの概念を持つテーブル構造を表すことができるモデルとなっている。また、一台または階層構造を持つインデクスノード１によって、任意のＫｅｙの範囲を担当するノードが定められており、あるＫｅｙに対応するレコードへの読み込み／書き込み要求に対する処理は全てそのＫｅｙを担当するノードが行う。本形態においては、図１に示すように、ノード２−１が２つのＫｅｙ範囲Ｒａｎｇｅ１，Ｒａｎｇｅ２を担当し、ノード２−２が１つのＫｅｙ範囲Ｒａｎｇｅ３を担当し、ノード２−３が１つのＫｅｙ範囲Ｒａｎｇｅ４を担当している。
【００１６】
ノード２−１〜２−３のそれぞれは、担当するＫｅｙ範囲のレコードを記憶するレコード記憶手段である記憶部５０を有しているとともに、インデクス付与部１０と、記憶制御部２０と、ファイル分割部３０と、レコード取得部４０とを有している。
【００１７】
記憶部５０は、キャッシュ機能を具備するメモリ領域５１と、メモリ領域５１に蓄積されたレコードについてマイナーコンパクションが実行されることによって作成されたファイルが永続的に記憶されるディスク領域５２とを有し、ノード２−１〜２−３が管理する複数のレコードを任意のＫｅｙ範囲毎に集合体として記憶する。
【００１８】
インデクス付与部１０は、ノード２−１〜２−３が管理する任意のＫｅｙ範囲毎に、そのＫｅｙ範囲に対応するレコードにアクセスするためのインデクスを作成して付与する。
【００１９】
記憶制御部２０は、ノード２−１〜２−３が管理する任意のＫｅｙ範囲のレコードをＫｅｙの昇順または降順でメモリ領域５１に蓄積し、メモリ領域５１に蓄積されたレコードのサイズが所定の閾値を超えた場合に、マイナーコンパクションを実行することにより、そのレコードを１つのファイル単位としてディスク領域５２に記憶する。
【００２０】
ファイル分割部３０は、ディスク領域５２に記憶された複数のレコードの中から所定の条件に従う複数のレコードを抽出し、その複数のレコードをＫｅｙの昇順または降順で並び替えて新たなファイルを生成する。
【００２１】
レコード取得部４０は、レコード取得要求に対して、インデクスを参照することにより、レコード取得要求にて要求されたレコードを記憶部５０から取得し、レコード取得要求元に返す。
【００２２】
以下に、上記のように構成された分散型データストアシステムにおけるレコード管理方法について説明する。
【００２３】
まず、記憶部５０にレコードを書き込む際の処理について説明する。なお、以下においては、ノード２−１に対する処理を例に挙げて説明するが、ノード２−２，２−３に対する場合も同様の処理となる。
【００２４】
図２は、図１に示した分散型データストアシステムにおいて記憶部５０にレコードを書き込む際の処理を説明するための図である。
【００２５】
クライアントからの任意のＫｅｙに対するレコードの書き込み要求は図２のように、そのＫｅｙ範囲のレコードを管理するノード２−１に送信される。
【００２６】
すると、レコードの書き込み要求を受け取ったノード２−１においては、記憶制御部２０の制御によって、まず、レコードがメモリ領域５１に蓄積される（図２中ア）。この際、メモリ領域５１へは、Ｋｅｙの昇順または降順でレコードが蓄積されることになる。
【００２７】
そして、メモリ領域５１に蓄積された全レコードサイズが所定の閾値を超えた場合、マイナーコンパクションが実行され（図２中イ）、レコードが１つのファイル単位として作成されてディスク領域５２に永続的に記憶される（図２中ウ）。なお、上記閾値としては、一般的には搭載物理メモリサイズを基準に指定されることになる。
【００２８】
また、それと同時に、インデクス付与部１０において、全レコードに対応するインデクスが作成され、ディスク領域５２に記憶されたレコードに付与される。これにより、Ｋｅｙ範囲に対応するインデクス情報（図２中ｉｎｄｅｘ１）が更新される。
【００２９】
図３は、図１に示したインデクス付与部１０にて作成されるインデクスの構成を示す図である。
【００３０】
インデクス付与部１０にて作成されるインデクスは図３に示すように、Ｋｅｙが含まれるファイル名、ファイル内のオフセット、レコードサイズが格納され、ノード２−１にて担当するＫｅｙが任意の範囲毎に集合体とされたそれぞれに付与されている。
【００３１】
これにより、ノード２−１〜２−３のそれぞれにおいて、担当するＫｅｙ範囲（Ｒａｎｇｅ）毎に、その範囲に属するレコードが論理的な集合体として管理され、その際、その集合体に対し、Ｋｅｙに対応するＶａｌｕｅにアクセスするためのインデクスが付与される。
【００３２】
次に、記憶部５０に記憶されたレコードを読み込む際の処理について説明する。
【００３３】
図４は、図１に示した分散型データストアシステムにおいて記憶部５０に記憶されたレコードを読み込む際の処理を説明するための図である。
【００３４】
図４に示すように、ディスク領域５２には、上述したようにファイルが記憶されており（図４中ア）、これらのファイルは、上述したようにして作成されたインデクスによってアクセス可能となっている（図４中イ）。
【００３５】
任意のＫｅｙに対応するレコードを読み込むためのレコード取得要求がクライアントから送信されると、ノード２−１においてはまず、目的のＫｅｙが含まれるＫｅｙ範囲に対応するインデクスが参照され、どのファイルに目的のＫｅｙが含まれているのかが調べられる（図４中ウ）。インデクスにおいては、上述したように、Ｋｅｙが含まれるファイル名、ファイル内のオフセット、レコードサイズが格納されているため、Ｋｅｙを指定することにより、そのＫｅｙが含まれるファイルを調べることができる。
【００３６】
次に、レコード取得部４０において、目的のＫｅｙが含まれるファイルにアクセスが行われてレコードが読み込まれ（図４中エ）、それにより取得されたレコードがクライアントに返却される。
【００３７】
ここで、タイムスタンプが最も新しい最新世代のみ取得するクエリを実行する場合において、分散型データストアシステムのＫｅｙはＲｏｗＫｅｙ、カラム名、タイムスタンプといった優先度でソートされているため、最新のタイムスタンプを持つレコードは、ファイル上にまばらに存在する。そのため、シーケンシャルアクセスであっても、本来ならば読み込む必要のない古いタイムスタンプのレコードも含めて、ファイル内容全てをファイルシステムより読み込む必要が生じ、ファイルシステムから読み取るレコード数が多くなってしまう。
【００３８】
そこで、タイムスタンプのみが異なるレコードを世代が異なる同一レコードとして認識し、世代が同一となるレコードを１つのファイルとして生成することが考えられる。
【００３９】
図５は、図１に示した分散型データストアシステムにおいて世代単位でファイルを管理する方法を説明するための図である。
【００４０】
図１に示した分散型データストアシステムにおいて世代単位でファイルを管理する場合は、まず、ファイル分割部３０において、メジャーコンパクションが実行され、世代（Ｇ３：第３世代、Ｇ２：第２世代、Ｇ１：第１世代）単位でファイルが作成される（図５中カ）。
【００４１】
図６は、世代単位で作成されるファイルの構成を示す図であり、（ａ）は全体の構成を示す図、（ｂ）はＫｅｙの構成を示す図、（ｃ）は具体的な構成例を示す図である。
【００４２】
世代単位で作成されるファイルは図６に示すように、ＫｅｙとＶａｌｕｅとから構成されており、Ｋｅｙにおいては、ＲｏｗＫｅｙ、カラム名及びタイムスタンプがコロン（:）によって連結されている。
【００４３】
ファイル分割部３０においては、Ｋｅｙの構成要素のうちタイムスタンプのみが異なるレコードが、世代が異なる同一レコードとして認識され、世代が同一となるレコードが１つのファイルとして生成される。具体的には、メジャーコンパクション実行時において、Ｋｅｙ要素依存ファイル分割機能が用られ、当該機能において所定の条件（抽出条件）として、“世代”が指定されることで、ＲｏｗＫｅｙ、カラム名が共に同じレコードが全て集められ、タイムスタンプが調べられることで各レコードの世代が識別され、世代単位のファイルが作成される。この際、世代単位のファイルは、一般的なマイナーコンパクションやメジャーコンパクションで作成されるファイルと同様にＫｅｙによってソートされている。
【００４４】
これにより、最新世代である第３世代へのアクセスは、１つのファイル（ＦＩＬＥ（Ｇ３））を読み込むだけで完了する（図５中キ）。その際、最新世代の必要なカラムだけ読み込む必要がある場合は、一度インデクスに問い合わせる方法（図５中ク）と組み合わせることで、目的のＫｅｙに対応するレコードが第３世代ファイルのどの位置にあるのかを調べることにより、ファイルシステムのディスクＩ／Ｏや、分散ファイルシステムの場合はネットワークＩ／Ｏを削減することができる。また、メジャーコンパクションによって世代単位のファイルを作成した後に、マイナーコンパクションが発生し、世代単位のファイルの他にも、ファイルが作成された場合において、最新世代のレコードのみを読み込む場合は、最新世代のファイルを読み込みつつ、マイナーコンパクションによって作成されたファイルにさらに新しいレコードが含まれていないか、インデクスを検索し、新しい方のレコードを結果として返す。
【００４５】
このように、タイムスタンプのみが異なるレコードを世代が異なる同一レコードとして認識し、世代が同一となるレコードを１つのファイルとして生成しておくことにより、１つのファイルに特定の世代が連続して記録されていることになり、特定世代のファイルに対してアクセスを行うことにより、従来ではランダムアクセスとなってしまったアクセスパターンも、シーケンシャルアクセスにすることができ、応答時間やスループットを向上させ、また、不要な情報を読み込む必要が無くなるため、ファイルシステムやネットワークへの負荷を軽減することができる。
【００４６】
なお、本形態においては、ファイル分割部３０において、Ｋｅｙの構成要素のうちタイムスタンプのみが異なるレコードを世代が異なる同一レコードとして認識し、世代が同一となるレコードを１つのファイルとして生成しているが、ディスク領域５２に記憶された複数のレコードの中から所定の条件に従う複数のレコードを抽出し、その複数のレコードをＫｅｙの昇順または降順で並び替えて新たなファイルを生成するものであれば、上記のように世代管理に限らない。
【００４７】
以下に、上述した分散型データストアシステムにおけるレコードの読み込み処理について説明する。
【００４８】
図７は、図１に示した分散型データストアシステムにおけるレコードの読み込み処理を説明するためのフローチャートである。
【００４９】
まず、レコード取得部４０において、クライアントからのレコード取得要求となるクエリに含まれるレコード取得の条件式によって、特定世代へのアクセスであるか、特定カラム（複数選択可能）へのアクセスであるかが判別され、それに応じて、特定世代のファイルを全て読み込むか、インデクスを用いて読み込むかが選択される（ステップ１）。
【００５０】
世代が指定されておらず、特定世代へのアクセスではない場合は、インデクスが参照され、レコード取得要求に基づいてレコードがディスク領域５２から読み込まれて取得される（ステップ２）。
【００５１】
一方、世代が指定され、特定世代へのアクセスである場合は、レコード取得要求に特定カラムへのアクセスが指定されているかどうかが判別され（ステップ３）、特定カラムへのアクセスが指定されている場合は、特定世代のファイルに対し、上述したインデクスを用いたレコード取得機能によって、レコード取得要求に基づいてレコードが取得される（ステップ４）。
【００５２】
また、特定カラムへのアクセスが指定されていない場合は、レコード取得要求に基づいて、要求されたレコードが特定世代のファイルから直接取得される（ステップ５）。
【００５３】
次に、マイナーコンパクション機能で作成された新たなファイルが存在する場合は（ステップ６）、マイナーコンパクション機能で作成された新たなファイルについては、インデクスが参照され、レコード取得要求に基づいてレコードがディスク領域５２から読み込まれて取得される（ステップ７）。
【００５４】
このようにしてディスク領域５２から取得されたレコードは、レコード取得要求の要求元に返却される。
【００５５】
なお、インデクス付与部１０においては、マイナーコンパクションやメジャーコンパクションの実行時、もしくは、新たな特定世代のファイルが生成された契機のいずれかにおいて、インデクスが更新され、再付与されることになる。すなわち、各ノード２−１〜２−３にて管理されるＫｅｙ範囲に含まれるＫｅｙの読み込みを行う際に、インデクスに該当するＫｅｙが無く、かつインデクスを構築していない１つ以上のファイルがあれば、クライアントからのレコード取得要求に基づき、従来の方法で目的のレコードを検索すると同時に、インデクスが更新されることになる。具体的には、マイナーコンパクション機能で新たなファイルが生成された契機、または、世代単位の新たなファイルが生成された契機のいずれかにおいて、インデクスが更新されることになる。
【符号の説明】
【００５６】
１    インデクスノード
２−１〜２−３    ノード
１０    インデクス付与部
２０    記憶制御部
３０    ファイル分割部
４０    レコード取得部
５０    記憶部
５１    メモリ領域
５２    ディスク領域
【図１】
2012168781.tif 000003
【図２】
2012168781.tif 000004
【図３】
2012168781.tif 000005
【図４】
2012168781.tif 000006
【図５】
2012168781.tif 000007
【図６】
2012168781.tif 000008
【図７】
2012168781.tif 000009