(57)【特許請求の範囲】
【請求項１】
入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える分散処理システムであって、
前記ディスパッチャは、
コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、
前記入力装置から前記入力情報を受信し、前記入力情報に対して、順序性を保持したハッシュ関数を用いてハッシュ値を計算し、前記計算したハッシュ値が、前記コンシステントハッシュ環上に配置された前記複数のサーバのいずれの仮想ノードの担当領域に含まれるかを、前記仮想ノード割当情報に基づき判定し、前記計算したハッシュ値を担当領域に含むと判定された仮想ノードの基となるサーバを、振り分け先となる前記サーバとして決定し、前記決定したサーバに前記入力情報を送信する振り分け処理部と、
前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントするアクセス情報管理部と、
前記分散処理システムに、新たなサーバが追加される場合に、自身以外のディスパッチャから、前記仮想ノード毎のアクセス数を取得して、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記自身以外のディスパッチャに送信する仮想ノード割当部と、
を備えることを特徴とする分散処理システム。
【請求項２】
前記仮想ノード割当部は、
前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成すること
を特徴とする請求項１に記載の分散処理システム。
【請求項３】
入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える分散処理システムの前記ディスパッチャであって、
コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、
前記入力装置から前記入力情報を受信し、前記入力情報に対して、順序性を保持したハッシュ関数を用いてハッシュ値を計算し、前記計算したハッシュ値が、前記コンシステントハッシュ環上に配置された前記複数のサーバのいずれの仮想ノードの担当領域に含まれるかを、前記仮想ノード割当情報に基づき判定し、前記計算したハッシュ値を担当領域に含むと判定された仮想ノードの基となるサーバを、振り分け先となる前記サーバとして決定し、前記決定したサーバに前記入力情報を送信する振り分け処理部と、
前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントするアクセス情報管理部と、
前記分散処理システムに、新たなサーバが追加される場合に、自身以外のディスパッチャから、前記仮想ノード毎のアクセス数を取得して、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記自身以外のディスパッチャに送信する仮想ノード割当部と、
を備えることを特徴とするディスパッチャ。
【請求項４】
前記仮想ノード割当部は、
前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成すること
を特徴とする請求項３に記載のディスパッチャ。
【請求項５】
入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバと、前記複数のディスパッチャに接続され、前記ディスパッチャが受信した入力情報の振り分け先となる前記サーバを管理する分散処理管理装置と、を備える分散処理システムの前記分散処理管理装置であって、
コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、
前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントしたアクセス情報を、前記複数のディスパッチャそれぞれから収集するアクセス情報収集部と、
前記分散処理システムに新たなサーバが追加される場合、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記複数のディスパッチャに配信する仮想ノード割当情報生成部と、
を備えることを特徴とする分散処理管理装置。
【請求項６】
前記仮想ノード割当情報生成部は、
前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成すること
を特徴とする請求項５に記載の分散処理管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散配置されるサーバをクラスタ化してデータを格納する分散データベースの技術分野、および、大規模なデータ集合から、所定の条件で所望のデータを取得する検索技術の分野に属する。
【背景技術】
【０００２】
近年、クラウド化に伴いＷｅｂ側でのサービス提供が多くなってきている。ユーザも非常に膨大となることから、単位時間当たりのクエリ処理量に着目し、分散システムを導入する場合が増えつつある。特にボトルネックとなり易いＤＢ（DataBase）の分野では、旧来のＲＤＢ（Relational DataBase）からＮｏＳＱＬ型のシステムに移行しつつある。
【０００３】
ＮｏＳＱＬ型では、スケーラビリティを享受することを最大目標としており、ハッシュ関数を利用するＫＶＳ（Key Value Store）形式のものが多い。ＫＶＳでは、ＲＤＢのようにテーブル構造のデータを持つことはせず、検索対象としてkeyを予め設定し、そのkeyに対してハッシュ関数を適用することでＯ(1)若しくはＯ（log(N)）の計算量によるvalue検索を可能とし、上記の特性を得ている。但し、その代償としてＳＱＬレベルの検索や、トランザクション処理の一貫性等が不得意であることが知られている。
【０００４】
代表的なＫＶＳ形式のＤＢとしては、コンシステントハッシュ（Consistent Hashing）アルゴリズムを利用したシステムがある（非特許文献１参照）。
【０００５】
非特許文献１に記載されたようなコンシステントハッシュを利用したＤＢでは、動的にサーバを、追加、削除したとしても、既存のクラスタに対する影響が小さいという特徴がある。また、コンシステントハッシュにおいては、１つの物理ノードに対して、仮想的に複数のノードを割り当てる仮想ノードという概念を導入し、コンシステントハッシュ環の領域を仮想ノードに割り当てることにより、更に既存のクラスタへの影響を低減することも可能である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Giuseppe DeCandia，et al.，“Dynamo: Amazon’s Highly Available Key-value Store,” SOSP’07, October 14-17, 2007, Stevenson, Washington, USA，［online］、［平成24年2月13日検索］、インターネット<http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明で解決しようとする課題は、以下の点である。
ＮｏＳＱＬ型のＤＢシステム、特に、コンシステントハッシュに基づくものは、データ集合を得る手段として用いられる範囲検索を効率化（高速化）するため、通常一致検索で用いる不連続なハッシュ関数（図１０（ａ）参照）ではなく、順序性を保持したハッシュ関数（連続関数）を用いる（図１０（ｂ）参照）。しかし、順序性を保持したハッシュ関数では、入力分布に偏りが発生した際に、クラスタ内のいずれかのサーバに負荷が集中してしまうことが発生し易くなる。
【０００８】
順序性を保持したハッシュ関数だけでは、基本的にはあらゆる入力分布に対して負荷を均等化することはできないため、コンシステントハッシュの仮想ノードの割り当てを用いて、負荷を均等化することが考えられる。但し、順序性を保持するハッシュ関数では、コンシステントハッシュ環においてデータの配置が非常に偏ることになった場合に、単純にランダムで仮想ノードを割り当ててしまうと、密にデータが配置された領域にはほとんど仮想ノードが割り当てられないケースが発生し、結果として負荷が均等にならないという問題がある。
【０００９】
このような背景に鑑みて本発明がなされたのであり、本発明は、コンシステントハッシュを適用したＫＶＳ形式のデータベースにおいて、範囲検索を高速化し、かつ、サーバ負荷を均等にすることができる、分散処理システム、ディスパッチャおよび分散処理管理装置を提供することを課題とする。
【課題を解決するための手段】
【００１０】
前記した課題を解決するため、請求項１に記載の発明は、入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える分散処理システムであって、前記ディスパッチャが、コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、前記入力装置から前記入力情報を受信し、前記入力情報に対して、順序性を保持したハッシュ関数を用いてハッシュ値を計算し、前記計算したハッシュ値が、前記コンシステントハッシュ環上に配置された前記複数のサーバのいずれの仮想ノードの担当領域に含まれるかを、前記仮想ノード割当情報に基づき判定し、前記計算したハッシュ値を担当領域に含むと判定された仮想ノードの基となるサーバを、振り分け先となる前記サーバとして決定し、前記決定したサーバに前記入力情報を送信する振り分け処理部と、前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントするアクセス情報管理部と、前記分散処理システムに、新たなサーバが追加される場合に、自身以外のディスパッチャから、前記仮想ノード毎のアクセス数を取得して、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記自身以外のディスパッチャに送信する仮想ノード割当部と、を備えることを特徴とする分散処理システムとした。
【００１１】
また、請求項３に記載の発明は、入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバとを備える分散処理システムの前記ディスパッチャであって、コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、前記入力装置から前記入力情報を受信し、前記入力情報に対して、順序性を保持したハッシュ関数を用いてハッシュ値を計算し、前記計算したハッシュ値が、前記コンシステントハッシュ環上に配置された前記複数のサーバのいずれの仮想ノードの担当領域に含まれるかを、前記仮想ノード割当情報に基づき判定し、前記計算したハッシュ値を担当領域に含むと判定された仮想ノードの基となるサーバを、振り分け先となる前記サーバとして決定し、前記決定したサーバに前記入力情報を送信する振り分け処理部と、前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントするアクセス情報管理部と、前記分散処理システムに、新たなサーバが追加される場合に、自身以外のディスパッチャから、前記仮想ノード毎のアクセス数を取得して、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記自身以外のディスパッチャに送信する仮想ノード割当部と、を備えることを特徴とするディスパッチャとした。
【００１２】
このようにすることで、本発明に係る分散処理システムのディスパッチャは、順序性を保持したハッシュ関数を用いて、振り分け先となるサーバを決定することができる。よって、範囲検索を行う際に、すべてのサーバを検索する必要をなくし、所定の範囲のデータを検索すればよくなるため、応答速度を高速化することができる。
さらに、分散処理システムにおいて、新たなサーバが追加される場合に、各ディスパッチャが、コンシステントハッシュ環上に配置された仮想ノードに対するアクセス数をカウントし、各ディスパッチャの仮想ノード毎のアクセス数の合計値を算出し、その合計値が最も大きい仮想ノードのコンシステントハッシュ環上の担当領域に、新たなサーバの仮想ノードを配置する。よって、アクセス数が多い領域に優先的に仮想ノードを配置するため、サーバ負荷を均等にすることができる。
【００１３】
請求項２に記載の発明は、前記仮想ノード割当部が、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成することを特徴とする請求項１に記載の分散処理システムとした。
【００１４】
また、請求項４に記載の発明は、前記仮想ノード割当部が、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成することを特徴とする請求項３に記載のディスパッチャとした。
【００１５】
このようにすることで、分散処理システムにおいて、新たなサーバが追加される場合に、仮想ノードのアクセス数が最も大きい仮想ノードの担当領域に対する、新たなサーバの仮想ノードの配置を繰り返し実行することができる。よって、サーバ負荷を均等にする効果をさらに高めることができる。
【００１６】
請求項５に記載の発明は、入力装置から受信した入力情報を、サーバに振り分ける複数のディスパッチャと、前記ディスパッチャから受信した入力情報に基づき、データの保存、検索を含む処理を実行する複数の前記サーバと、前記複数のディスパッチャに接続され、前記ディスパッチャが受信した入力情報の振り分け先となる前記サーバを管理する分散処理管理装置と、を備える分散処理システムの前記分散処理管理装置であって、コンシステントハッシュ環上における、前記複数のサーバの仮想ノードの担当領域を示す仮想ノード割当情報を記憶する記憶部と、前記コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、前記入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すアクセス数を、前記仮想ノード毎にカウントしたアクセス情報を、前記複数のディスパッチャそれぞれから収集するアクセス情報収集部と、前記分散処理システムに新たなサーバが追加される場合、前記仮想ノード毎のアクセス数の合計値を計算し、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置し、新たな前記仮想ノード割当情報を生成して、前記複数のディスパッチャに配信する仮想ノード割当情報生成部と、を備えることを特徴とする分散処理管理装置とした。
【００１７】
このようにすることで、本発明に係る分散処理管理装置は、各ディスパッチャから、コンシステントハッシュ環上に配置された仮想ノードに対するアクセス数をカウントしたアクセス情報を収集する。そして、分散処理管理装置は、新たなサーバを追加する場合に、各ディスパッチャの仮想ノード毎のアクセス数の合計値を算出し、その合計値が最も大きい仮想ノードのコンシステントハッシュ環上の担当領域に、新たなサーバの仮想ノードを配置して、新たな仮想ノード割当情報を生成し、各ディスパッチャに配信する。よって、アクセス数が多い領域に優先的に仮想ノードを配置するため、各サーバの負荷を均等にすることができる。
【００１８】
請求項６に記載の発明は、前記仮想ノード割当情報生成部が、前記計算したアクセス数の合計値が最も大きい仮想ノードの前記コンシステントハッシュ環上の担当領域に、前記新たなサーバの仮想ノードを配置した場合に、当該アクセス数の合計値を、前記仮想ノードを配置したことにより分割された領域の領域比に応じて分配し、新たな仮想ノードのアクセス数の合計値として設定し、前記設定後のコンシステントハッシュ環上の仮想ノードにおいて、前記アクセス数の合計値が最も大きい仮想ノードの担当領域に、前記新たなサーバの仮想ノードを配置する仮想ノード割当処理を、前記新たなサーバに設定される所定数の仮想ノードが前記コンシステントハッシュ環上に配置し終えるまで実行し、前記新たな仮想ノード割当情報を生成することを特徴とする請求項５に記載の分散処理管理装置とした。
【００１９】
このようにすることで、分散処理管理装置は、分散処理システムにおいて、新たなサーバが追加される場合に、仮想ノードのアクセス数が最も大きい仮想ノードの担当領域に対する、新たなサーバの仮想ノードの配置を繰り返し実行することができる。よって、サーバ負荷を均等にする効果をさらに高めることができる。
【発明の効果】
【００２０】
本発明によれば、コンシステントハッシュを適用したＫＶＳ形式のデータベースにおいて、範囲検索を高速化し、かつ、サーバ負荷を均等にする、分散処理システム、ディスパッチャおよび分散処理管理装置を提供することができる。
【図面の簡単な説明】
【００２１】
【図１】本実施形態に係る分散処理システムを含む全体構成を示す図である。
【図２】本実施形態に係る分散処理システムの内部構成を示す図である。
【図３】本実施形態に係る分散処理システムの処理の概要を説明するための図である。
【図４】本実施形態に係るディスパッチャの構成例を示す機能ブロック図である。
【図５】本実施形態に係る仮想ノード割当情報のデータ構成の一例を示す図である。
【図６】本実施形態に係る各ディスパッチャによる、仮想ノードの担当領域のアクセス数のカウント処理を説明するためのフローチャートである。
【図７】本実施形態に係る各ディスパッチャによる、仮想ノードの担当領域のアクセス数のカウント処理を説明するための図である。
【図８】本実施形態に係る分散処理システムにおいて、新たなサーバが追加される場合の仮想ノード割当処理を説明するためのシーケンス図である。
【図９】本実施形態に係る分散処理システムにおいて、既存のサーバを削除する場合の仮想ノード割当処理を説明するためのシーケンス図である。
【図１０】コンシステントハッシュにおける不連続関数と連続関数を説明するための図である。
【発明を実施するための形態】
【００２２】
次に、本発明を実施するための形態（以下、「本実施形態」という）における分散処理システム１について説明する。
【００２３】
＜システム構成＞
図１は、本実施形態に係る分散処理システム１を含む全体構成を示す図である。
図１に示すように、分散処理システム１は、ネットワークを介して、外部システム２であるオペレータシステムや、端末３等と接続される。そして、外部システム２や端末３からの入力データ（クエリ）を受け取り、分散処理システム１内でデータの保存、更新、検索等を行い、その結果を出力データとして、外部システム２や端末３に送信する。
【００２４】
＜分散処理システムの構成＞
図２は、本実施形態に係る分散処理システム１の内部構成を示す図である。
図２に示すように、本分散処理システム１は、ロードバランサＢ（Balancer：各図において「Ｂ」と表記）と、複数のディスパッチャＤ（Dispatcher：各図において「Ｄ」と表記）と、複数のプロセッサＰ（Processor：各図において「Ｐ」と表記）と、複数のストレージＳ(Storage：各図において「Ｓ」と表記）とを含んで構成される。
【００２５】
ロードバランサＢは、入力装置４から入力データを取得し、出力データを出力装置５に送信する。また、ロードバランサＢは、ラウンドロビン等により、入力データを複数のディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）のいずれかに振り分ける。ここで、入力装置４および出力装置５は、図１に示した外部システム２や端末３である。また、本分散処理システム１に対する入力データは、例えば、ＳＱＬのクエリやＸＣＡＰ（XML Configuration Access Protocol）のような、データベースからデータを取得するための要求のことである。
【００２６】
各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）は、複数のプロセッサＰ（Ｐ１，Ｐ２，Ｐ３）と接続されており、ロードバランサＢから取得した入力データ（クエリ）を、プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）のいずれかに振り分ける。このディスパッチャＤは、入力データを解析し、コンシステントハッシュを適用してハッシュ関数により、データの格納先であるサーバ（プロセッサＰとストレージＳとの組）を決定し、その入力データ（クエリ）を送信する。なお、ディスパッチャＤの詳細な構成と処理については、後記する。
【００２７】
プロセッサＰは、複数のディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）と自身が制御するストレージＳとに接続されており、いずれかのディスパッチャＤから入力データを受信し、その入力データに従い、ストレージＳに新規データを保存したり、既存データを更新したり、データの検索処理をしたりする制御を実行する。また、ストレージＳは、実際にデータを保存する記憶手段であり、例えば、各データがＸＭＬ（Extensible Markup Language）ファイルで保存される。なお、本実施形態においては、このプロセッサＰとストレージＳとの組を、１つのサーバとして説明する。また、後記において説明するように、本実施形態において、サーバ（プロセッサＰとストレージＳとの組）が本分散処理システム１に追加、削除される際には、その該当サーバ（例えば、プロセッサＰ１およびストレージＳ１）の分散処理システム１への登録等を管理するディスパッチャＤ１も併せて、追加、削除されるものとする。さらに、ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）、プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）、ストレージＳ（Ｓ１，Ｓ２，Ｓ３）それぞれは、図２に図示した３つの装置に限定されず、複数の装置であればよい。
【００２８】
＜概要＞
まず、本実施形態に係る分散処理システム１が行う処理の概要について説明する。
図３は、本実施形態に係る分散処理システム１の処理の概要を説明するための図である。
図３（ａ）は、コンシステントハッシュに基づき、仮想ノードを設定し、範囲検索を高速化するためにハッシュ関数を連続かつ単調増加関数とした場合の従来のシステムにおける例を示している。この場合、各サーバに格納されたデータを、ハッシュ値順にソートしておくことで、任意の範囲を取得すること（例えば、keyを文字列とする前方一致）に対して、常にＯ（log(N)）の計算量でデータを取得できる。しかしながら、図３（ａ）に示すように、コンシステントハッシュ環の一部の領域に出現頻度が偏る可能性が高くなる。この問題を、仮想ノードを増やすことで解決しようとする場合、従来の仮想ノード割当方法では、例えば、ランダムに仮想ノードが配置されてしまうため、仮想ノードを増加させても、偏った領域に充分に仮想ノードが配置されず、その結果サーバ負荷のばらつきが解消されない可能性がある。
この問題を解決するため、本実施形態に係る分散処理システム１では、各ディスパッチャＤが、コンシステントハッシュ環の担当領域において、仮想ノードがそのデータ処理を担当したアクセス数をカウントし、アクセス数が多い領域に集中的に新たな仮想ノードを配置することで、サーバ負荷を均等にするものである（図３（ｂ）参照）。
【００２９】
以下、まず、本実施形態に係る分散処理システム１において、仮想ノードのアクセス数のカウント処理と、コンシステントハッシュ環への仮想ノードの配置処理とを行う、ディスパッチャＤの詳細について説明する。その後に、本分散処理システム１が実行する処理の流れについて説明する。
【００３０】
≪ディスパッチャＤ≫
図４は、本実施形態に係るディスパッチャＤの構成例を示す機能ブロック図である。
ディスパッチャＤは、ロードバランサＢおよび複数のプロセッサＰ（Ｐ１，Ｐ２，Ｐ３）と通信可能に接続され、ロードバランサＢから取得した入力データ（クエリ）を、プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）に振り分ける装置であり、図４に示すように、制御部１０と、入出力部２０と、メモリ部３０と、記憶部４０とを含んで構成される。
【００３１】
入出力部２０は、ロードバランサＢや、各プロセッサＰ（Ｐ１，Ｐ２，Ｐ３）との間の情報の入出力を行う。例えば、入出力部２０は、ロードバランサＢが送信した入力データ（クエリ）を受信し、各プロセッサＰに対し、その入力データ（クエリ）の送信を行う。また、入出力部２０は、ストレージＳに保存されるデータ等の検索結果をプロセッサＰから受信し、ロードバランサＢに対して送信する等の処理を行う。
また、この入出力部２０は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００３２】
制御部１０は、ディスパッチャＤ全体の制御を司り、情報受信部１１と、構文解析部１２と、振り分け処理部１３と、保存情報管理部１４と、アクセス情報管理部１５と、仮想ノード割当部１６と、情報送信部１７とを含んで構成される。なお、この制御部１０は、例えば、ディスパッチャＤの記憶部４０に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部３０であるＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００３３】
情報受信部１１は、入出力部２０を介して、ロードバランサＢからの入力データ（クエリ）や、プロセッサＰからの出力データを取得する。
【００３４】
構文解析部１２は、情報受信部１１から入力データ（クエリ）を受け取り、そのクエリの内容を構文解析する。例えば、構文解析部１２は、その入力データ（クエリ）が、ストレージＳに格納されたデータに対する検索要求（GET）であり、「keyの完全一致検索」や、「keyの範囲検索」等であるかを解析したり、新規のデータの登録要求（PUT）や、既存データの更新要求（UPDATE）等のクエリの内容を解析したりする。
そして、構文解析部１２は、その解析結果を振り分け処理部１３に引き渡す。
【００３５】
振り分け処理部１３は、ハッシュ値計算部１３１を備え、ハッシュ値計算部１３１が、構文解析部１２から取得した解析結果に基づき、予め設定された順序性を保持したハッシュ関数、つまり、連続かつ単調増加するハッシュ関数を用いて、コンシステントハッシュを適用し、入力データのハッシュ値を計算する。
また、振り分け処理部１３は、ハッシュ値計算部１３１が計算したハッシュ値に基づき、記憶部４０に記憶された仮想ノード割当情報１００を参照し、振り分け先となるコンシステントハッシュ環上の仮想ノードを決定する。そして、振り分け処理部１３は、この決定された仮想ノードの基となるサーバ（プロセッサＰとストレージＳとの組）を、振り分け先のサーバとして選択する。なお、仮想ノード割当情報１００については、後記して説明する。
【００３６】
保存情報管理部１４は、構文解析部１２が入力データ（クエリ）を構文解析した結果に応じて、各サーバに保存される情報を管理する全体的な制御を行う。
具体的には、保存情報管理部１４は、振り分け処理部１３が、データの取得要求（検索）、保存、変更等を実行するサーバを決定すると、その決定した振り分け先となるサーバに、入力データ（クエリ）を、情報送信部１７を介して送信する。
また、保存情報管理部１４は、データの取得要求を示す入力データ（クエリ）の場合に、各サーバから取得したデータを、出力データとしてロードバランサＢに送信する制御を行う。
【００３７】
アクセス情報管理部１５は、振り分け処理部１３が、入力データ（クエリ）を処理する仮想ノードを決定し、保存情報管理部１４が、その仮想ノードの基となるサーバ（プロセッサＰとストレージＳとの組）に入力データを送信し、その応答情報を当該サーバから受信したことを契機として、その仮想ノードが処理した回数である、アクセス数１０４を１つカウントアップする。具体的には、アクセス情報管理部１５は、記憶部４０に記憶された仮想ノード割当情報１００に設けられたコンシステントハッシュ環における仮想ノードの担当領域に対応づけて、入力データのアクセス数１０４をカウントアップする。
なお、このアクセス数１０４は、コンシステントハッシュ環上に配置された仮想ノードの担当領域に対し、入力情報のハッシュ値が当該仮想ノードの担当領域に含まれることを示すものである。
【００３８】
図５は、本実施形態に係る仮想ノード割当情報１００のデータ構成の一例を示す図である。
図５に示すように、仮想ノード割当情報１００は、仮想ノードＩＤ（Identification）１０１、物理ノードＩＤ１０２、ハッシュ値１０３、アクセス数１０４のデータ項目を含んで構成される。
【００３９】
ここで、仮想ノードＩＤ１０１は、本分散処理システム１内において仮想ノードを特定するための固有な番号である。例えば、図５に示す、仮想ノードＩＤ１０１の「１３−１８１」は、仮想ノードの基となる物理ノードのＩＤ（物理ノードＩＤ１０２）と、当該物理ノードにおける固有な番号のうちの１つ（ここでは、「１８１」番）との組により構成される。
物理ノードＩＤ１０２は、入力データの振り分け先となるサーバ（プロセッサＰとストレージＳとの組）を、本分散処理システム１内において特定するための固有な番号である。例えば、図５に示すように、物理ノードＩＤ１０２として「１３」が設定される。
なお、この仮想ノードＩＤ１０１および物理ノードＩＤ１０２は、本分散処理システム１内において、一意に特定されるＩＤであればよく、図５に示した表記方法に限定されるものではない。
【００４０】
ハッシュ値１０３は、コンシステントハッシュ環において、仮想ノードが担当する領域を特定するためのものであり、例えば、「０」から順に「１００００」までのいずれかの値が格納される。
例えば、図５に示す、第１行目のハッシュ値１０３が「５６」の場合は、仮想ノードＩＤ１０１が「１３−１８１」の仮想ノードのコンシステントハッシュ環における入力データの担当領域が、「０」〜「５６」であることを示す。また、第２行目のハッシュ値１０３が「１７２」の場合は、仮想ノードＩＤ１０１が「５−９６」の仮想ノードのコンシステントハッシュ環における入力データの担当領域が、１つ前の行のハッシュ値１０３の値に「１」をプラスした「５７」〜「１７２」であることを示す。
【００４１】
アクセス数１０４には、仮想ノードが担当する入力データが処理される毎に、その仮想ノードの担当領域に配置された入力データの数（アクセス数）がアクセス情報管理部１５によりカウントアップされ格納される。
例えば、図５に示す、第１行目のアクセス数１０４が「１０９８」の場合は、仮想ノードＩＤ１０１が「１３−１８１」の仮想ノードの担当であるハッシュ値１０３が「０」〜「５６」の領域に、「１０９８」回のアクセス数があったことを示す。
【００４２】
この仮想ノード割当情報１００のうち、仮想ノードＩＤ１０１、物理ノードＩＤ１０２およびハッシュ値１０３は、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）において、すべて共通の値を備えている。これに対し、アクセス数１０４は、ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）それぞれが受信した入力データに対し、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）の振り分け処理部１３が振り分けた仮想ノード毎に、各アクセス情報管理部１５により独自にカウントされる。なお、このアクセス情報管理部１５による、仮想ノードの担当領域のアクセス数１０４のカウント処理については、後記する図６および図７において詳細に説明する。
【００４３】
また、アクセス情報管理部１５は、コーディネータとなるディスパッチャＤ（詳細は後記）から、アクセス情報集計通知を受信すると、自身のディスパッチャＤが備える仮想ノード割当情報１００を参照し、アクセス情報を返信する。ここで、アクセス情報とは、仮想ノード割当情報１００のデータ項目のうち、仮想ノードＩＤ１０１とそれに対応付けられたアクセス数１０４の情報を意味する。
さらに、アクセス情報管理部１５は、コーディネータとなるディスパッチャＤから、新たな仮想ノード割当情報１００を受信すると、記憶部４０に記憶された仮想ノード割当情報１００を、受信した新たな仮想ノード割当情報１００で更新する。その際、アクセス数１０４は「０」に初期化される。
【００４４】
図４に戻り、仮想ノード割当部１６は、分散処理システム１内において、各サーバ（プロセッサＰとストレージＳとの組）の負荷にばらつきが生じる等したことより、サーバを追加したり削除したりする場合に、当該サーバの追加や削除に対応した、新たな仮想ノードのコンシステントハッシュ環上の配置を決定する。
なお、以下に説明する仮想ノード割当部１６の処理は、自身のディスパッチャＤが、仮想ノードの新たな配置を決定する各ディスパッチャＤのコーディネータとして機能する場合に実行されるものである。このコーディネータは、各ディスパッチャＤのうちの１つが管理者等により、または、任意に設定され、コーディネータとして機能するディスパッチャＤが故障等した場合には、他のディスパッチャＤのうちの１つが、代わりにコーディネータの役割を果たすものである。
【００４５】
仮想ノード割当部１６は、サーバ（プロセッサＰとストレージＳとの組）を追加する場合に、例えば、追加するサーバを管理するディスパッチャＤから、サーバが新たに追加されたことを示す参加通知を受け取ると、既存の各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）に対して、アクセス情報集計通知を送信する。このアクセス情報集計通知は、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）が備える仮想ノード割当情報１００に記憶されたアクセス情報（仮想ノードＩＤ１０１とそれに対応付けられたアクセス数１０４の情報）の返信を求めるメッセージである。
仮想ノード割当部１６は、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）から送信されたアクセス情報を集計し、アクセス数１０４の合計値が最も大きい仮想ノードを選択する。そして、仮想ノード割当部１６は、新たに追加するサーバの仮想ノードを、アクセス数１０４の合計値が最も大きい仮想ノードの担当領域に配置する。
【００４６】
なお、このときの当該領域への仮想ノードの配置は、１つの仮想ノードに限定されず、予め設定した所定数の仮想ノードを当該領域に配置するようにしてもよい。また、仮想ノードを配置する位置（ハッシュ値）も、例えば、当該領域に１つの仮想ノードを配置する場合に、その領域を２等分する位置に配置してもよいし、領域の長さを例えば、１対２のように分割する位置に配置してもよい。また、当該領域に２つの仮想ノードを配置する場合に、その領域を３等分する位置に配置してもよいし、その領域の長さを任意の割合で分割する位置に配置するようにしてもよい。
【００４７】
仮想ノード割当部１６は、当該領域に仮想ノードを配置すると、その領域のアクセス数１０４をそれぞれの領域比に応じて分配し、その分割された領域のアクセス数１０４の合計値とする。そして、仮想ノード割当部１６は、新たに配置された仮想ノードを含めて、再度、アクセス数１０４の合計値が最も大きい仮想ノードの領域を選択し、所定数の仮想ノードをその領域に配置する処理を繰り返す。なお、１つの物理ノードに対応する仮想ノードの数は予め決められており、仮想ノード割当部１６は、新たに配置するすべての仮想ノードの配置が終了するまで、この仮想ノード割当処理を繰り返す。
【００４８】
仮想ノード割当部１６は、すべての仮想ノードのコンシステントハッシュ環の領域への配置が終了することにより、新たな仮想ノード割当情報１００（図５に示す、仮想ノードＩＤ１０１、物理ノードＩＤ１０２およびハッシュ値１０３の情報）を生成し、その生成した新たな仮想ノード割当情報１００を、追加するサーバを管理するディスパッチャＤを含めた各ディスパッチャＤに送信する。
【００４９】
また、仮想ノード割当部１６は、分散処理システム１の管理者等により、既存のサーバのうちの一つの削除指示を受けた場合に、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）に対して、アクセス情報集計通知を送信する。仮想ノード割当部１６は、各ディスパッチャＤ（Ｄ１，Ｄ２，Ｄ３）から送信されたアクセス情報を集計し、物理ノード（サーバ）毎に、各物理ノード（サーバ）に設定されたすべての仮想ノードのアクセス数１０４を合計する。そして、そのアクセス数１０４の合計値が最も少ない物理ノード（サーバ）を削除する物理ノード（サーバ）に決定する。
【００５０】
続いて、仮想ノード割当部１６は、削除する物理ノード（サーバ）に設定された仮想ノードを、コンシステントハッシュ環上から取り除いた新たな仮想ノード割当情報１００（図５に示す、仮想ノードＩＤ１０１、物理ノードＩＤ１０２およびハッシュ値１０３の情報）を生成し、その生成した新たな仮想ノード割当情報１００を、削除するサーバを管理するディスパッチャＤを除いた、各ディスパッチャＤに送信する。また、仮想ノード割当部１６は、削除するサーバを管理するディスパッチャＤに対して、削除通知を送信する。
【００５１】
情報送信部１７は、振り分け処理部１３が決定した振り分け先となるプロセッサＰに対して、入力データ等を送信したり、入力データ（クエリ）の内容に応じた各サーバへの制御情報等を送信したりする。また、プロセッサＰから受信したデータ等を、ロードバランサＢへ送信する等の制御を行う。
【００５２】
次に、記憶部４０は、ハードディスクやフラッシュメモリ等の記憶装置からなり、前記した仮想ノード割当情報１００（図５）を記憶する。また、記憶部４０は、ロードバランサＢや、自身以外の各ディスパッチャＤ、各プロセッサＰのアドレス（ＩＰアドレス）等を記憶する。
【００５３】
メモリ部３０は、ＲＡＭ等の一次記憶装置からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶している。
【００５４】
＜分散処理システムの処理の流れ＞
次に、本実施形態に係る分散処理システム１の処理の流れについて説明する。
【００５５】
≪アクセス数のカウント処理≫
まず、図６および図７を参照して、本実施形態に係るディスパッチャＤによるアクセス数１０４のカウント処理について説明する。
図６は、本実施形態に係る各ディスパッチャＤ（アクセス情報管理部１５）による、仮想ノードの担当領域のアクセス数１０４のカウント処理を説明するためのフローチャートである。なお、図６においては、入力装置４と出力装置５が同一の装置である例を示すが、入力装置４と出力装置５が別の装置であっても構わない。
【００５６】
まず、入力装置４は、入力データ（クエリ）として、例えば、検索要求「GET Key=a0123」をロードバランサＢに送信する（ステップＳ１０）。ロードバランサＢは、例えば、ランダムに入力データをディスパッチャＤに振り分ける。ここでは、ロードバランサＢは、ディスパッチャＤ１に振り分けて、入力データを送信する（ステップＳ１１）。
【００５７】
ディスパッチャＤ１の振り分け処理部１３は、入力データ（例えば、「Key=a0123」）のハッシュ値を計算し、仮想ノード割当情報１００を参照して、振り分け先となる仮想ノードを決定し、その決定した仮想ノードの基となる物理ノード（サーバ）に、入力データを送信する（ステップＳ１２）。ここで、ディスパッチャＤ１は、複数のサーバのうち、例えば、プロセッサＰｋとストレージＳｋとの組のサーバに、入力データを送信する（ステップＳ１２）。
【００５８】
次に、プロセッサＰｋは、入力データ（クエリ）として「GET Key=a0123」を受け取り、ストレージＳｋを検索し、検索結果として、例えば、「a0123.xml」のデータを得る（ステップＳ１３）。そして、プロセッサＰｋは、検索結果「a0123.xml」を、ディスパッチャＤ１に送信する（ステップＳ１４）。
【００５９】
続いて、ディスパッチャＤ１のアクセス情報管理部１５は、受信した応答情報（ここでは、検索結果）の基となる入力データ（クエリ）について、コンシステントハッシュ環で担当した仮想ノードを特定し、自身が記憶する仮想ノード割当情報１００（図５）のアクセス数１０４を１つカウントアップする（ステップＳ１５）。
【００６０】
続いて、ディスパッチャＤ１は、検索結果「a0123.xml」を、ロードバランサＢを介して、出力装置５に送信する（ステップＳ１６，Ｓ１７）。
【００６１】
次に、入力装置４から、別の入力データ（クエリ）として検索要求「GET Key=b9876」がロードバランサＢに送信されたものとする（ステップＳ２０）。ロードバランサＢは、例えば、ランダムに入力データをディスパッチャＤに振り分ける。ロードバランサＢは、ここでは、例えば、ディスパッチャＤ２に振り分け先を決定して、入力データを送信する（ステップＳ２１）。
【００６２】
ディスパッチャＤ２の振り分け処理部１３は、入力データ（例えば、「Key=b9876」）のハッシュ値を計算し、仮想ノード割当情報１００を参照して、振り分け先となる仮想ノードを決定し、その決定した仮想ノードの基となる物理ノード（サーバ）に、入力データを送信する。ここで、ディスパッチャＤ２は、複数のサーバのうち、例えば、プロセッサＰｍとストレージＳｍとの組のサーバに、入力データを送信する（ステップＳ２２）。
【００６３】
次に、プロセッサＰｍは、入力データ（クエリ）として「GET Key=b9876」を受け取り、ストレージＳｍを検索し、検索結果として、例えば、「b9876.xml」のデータを得る（ステップＳ２３）。そして、プロセッサＰｍは、検索結果「b9876.xml」を、ディスパッチャＤ２に送信する（ステップＳ２４）。
【００６４】
続いて、ディスパッチャＤ２のアクセス情報管理部１５は、受信した応答情報（ここでは、検索結果）の基となる入力データ（クエリ）について、コンシステントハッシュ環で担当した仮想ノードを特定し、自身が記憶する仮想ノード割当情報１００（図５）のアクセス数１０４を１つカウントアップする（ステップＳ２５）。
【００６５】
続いて、ディスパッチャＤ２は、検索結果「b9876.xml」を、ロードバランサＢを介して、出力装置５に送信する（ステップＳ２６，Ｓ２７）。
【００６６】
図７は、図６のステップＳ１５およびステップＳ２５における、各ディスパッチャＤのアクセス情報管理部１５による、仮想ノード割当情報１００（図５）のアクセス数１０４のカウント処理を説明するための図である。
各ディスパッチャＤには、同じ位置に仮想ノードが配置された同一のコンシステントハッシュ環が設定される。各ディスパッチャＤによるアクセス数１０４のカウントは、図７に示すように、例えば、ディスパッチャＤ１やディスパッチャＤ２それぞれにおいて、コンシステントハッシュ環上に配置された仮想ノードが担当する領域に、振り分け処理部１３が、入力データ（クエリ）を何回振り分けて処理したかを、アクセス情報管理部１５がカウントする。
【００６７】
なお、アクセス情報管理部１５は、図８において説明するように、コーディネータとなるディスパッチャＤから、アクセス情報集計通知を受け取ると、自身の仮想ノード割当情報１００（図５）を参照して、仮想ノードＩＤ１０１とそれに対応付けられたアクセス数１０４との情報を、アクセス情報として、コーディネータとなるディスパッチャＤに返信する。コーディネータとなるディスパッチャＤ（仮想ノード割当部１６）は、仮想ノードＩＤ１０１毎に、アクセス数１０４を集計し、アクセス数１０４の合計値が最も大きい仮想ノードの領域に、新たな仮想ノードを配置する。
以下、サーバを追加する場合と、削除する場合とについての、本実施形態に係るディスパッチャＤの仮想ノード割当処理について具体的に説明する。
【００６８】
≪仮想ノード割当処理（サーバを追加する場合）≫
図８は、本実施形態に係る分散処理システム１において、新たなサーバが追加される場合の仮想ノード割当処理を説明するためのシーケンス図である。
サーバの追加は、例えば、既存のサーバだけでは充分な性能を得られない（例えば、スループットが足りない）場合や、サーバ負荷にばらつきが生じている場合等に、サーバを追加することでサーバ負荷の均等化を図るために実行される。
なお、図８では、サーバ「＃４」としてのプロセッサＰ４とストレージＳ４との組と共に、このサーバ「＃４」を管理するディスパッチャＤ４も一緒に追加されるものとして説明する。なお、この追加される、プロセッサＰ４とストレージＳ４とディスパッチャＤ４とをまとめて追加される物理ノードと記載することがある。
【００６９】
図８に示すように、まず、追加されるサーバ＃４（プロセッサＰ４とストレージＳ４との組）を管理するディスパッチャＤ４から、各ディスパッチャＤのうち、コーディネータとして機能するディスパッチャＤ（ここでは、ディスパッチャＤ１とする）に向けて、参加通知が送信される（ステップＳ３０）。この参加通知には、追加されるディスパッチャＤ４およびプロセッサＰ４のアドレス情報等が含まれる。
【００７０】
参加通知を受信したディスパッチャＤ１の仮想ノード割当部１６は、参加通知を送信してきたディスパッチャＤ４以外の既存の各ディスパッチャＤ（Ｄ２，Ｄ３）に対し、アクセス情報集計通知を送信する（ステップＳ３１）。
【００７１】
アクセス集計通知を受信したディスパッチャＤ（Ｄ２，Ｄ３）のアクセス情報管理部１５それぞれは、自身のディスパッチャＤが記憶する仮想ノード割当情報１００に基づき、アクセス情報（仮想ノードＩＤ１０１とそれに対応付けられたアクセス数１０４との情報）を生成し、ディスパッチャＤ１に送信する（ステップＳ３２）。
【００７２】
ディスパッチャＤ１の仮想ノード割当部１６は、各ディスパッチャＤ（Ｄ２，Ｄ３）から送信されたアクセス情報のアクセス数１０４を仮想ノード毎に集計し、アクセス数１０４の合計値の最も大きい仮想ノードの領域を選択する。そして、仮想ノード割当部１６は、新たに追加するサーバの所定数の仮想ノードを、アクセス数１０４の合計値の最も大きい仮想ノードが担当しているコンシステントハッシュ環上の領域（最頻領域）に配置する（ステップＳ３３）。そして、ディスパッチャＤ１の仮想ノード割当部１６は、最頻領域に仮想ノードを配置すると、その最頻領域のアクセス数１０４の合計値をそれぞれの領域比に応じて分配し、その分割された領域のアクセス数１０４の合計値とする。そして、仮想ノード割当部１６は、新たに配置された仮想ノードを含めて、再度、アクセス数１０４の合計値の最も大きい仮想ノードの領域（最頻領域）を選択し、仮想ノードをその領域（最頻領域）に配置する処理を繰り返す。
【００７３】
ディスパッチャＤ１の仮想ノード割当部１６は、すべての仮想ノードの割り当てが終了すると、仮想ノード（仮想ノードＩＤ１０１）と、コンシステントハッシュ環上のその仮想ノードの担当領域（ハッシュ値１０３）とを示した新たな仮想ノード割当情報１００（図５）を生成し、自身の仮想ノード割当情報１００を更新した上で、各ディスパッチャＤ（Ｄ２，Ｄ３，Ｄ４）に通知する（ステップＳ３４）。そして、各ディスパッチャＤ（Ｄ２，Ｄ３，Ｄ４）のアクセス情報管理部１５は、受信した新たな仮想ノード割当情報１００を用いて、記憶部４０に記憶された仮想ノード割当情報１００を更新する。
【００７４】
≪仮想ノード割当処理（サーバを削除する場合）≫
図９は、本実施形態に係る分散処理システム１において、既存のサーバを削除する場合の仮想ノード割当処理を説明するためのシーケンス図である。なお、ここでは、最も負荷が少ないサーバを、仮想ノード割当情報１００のアクセス数１０４に基づき決定し、削除する例を説明する。
なお、このサーバの削除は、例えば、分散処理システム１内において、サーバ数を一定に保ちたいときであり、かつ、サーバ負荷にばらつきが生じているときに、既存のサーバを一旦削除し、その削除したサーバを再度追加することで、サーバ負荷の均等化を図る場合等に実行される。
また、ここでの削除は、サーバ（プロセッサＰとストレージＳとの組）と共にそのサーバを管理するディスパッチャＤも含めた１つの物理ノードが削除されるものとして説明する。
【００７５】
まず、コーディネータとして機能するディスパッチャＤ（ここでは、ディスパッチャＤ１とする）の仮想ノード割当部１６は、各ディスパッチャＤ（図９では、ディスパッチャＤ２，Ｄ３，Ｄ４）に対して、アクセス情報集計通知を送信する（ステップＳ４０）。なお、コーディネータとして機能するディスパッチャＤは、例えば、分散処理システム１の管理者等から、サーバ（１つの物理ノード）の削除指示を受信したこと等を契機として、各ディスパッチャＤに対し、アクセス情報集計通知を送信する。
【００７６】
アクセス集計通知を受信したディスパッチャＤ（Ｄ２，Ｄ３，Ｄ４）のアクセス情報管理部１５それぞれは、自身のディスパッチャＤが記憶する仮想ノード割当情報１００に基づき、アクセス情報（仮想ノードＩＤ１０１とそれに対応付けられたアクセス数１０４との情報）を生成し、ディスパッチャＤ１に送信する（ステップＳ４１）。
【００７７】
ディスパッチャＤ１の仮想ノード割当部１６は、各ディスパッチャＤ（Ｄ２，Ｄ３，Ｄ４）から送信されたアクセス情報のアクセス数１０４を仮想ノード毎に集計し、さらに、仮想ノードのアクセス数１０４の集計を、その仮想ノードの基となる物理ノード（サーバ）毎に合計し、アクセス数１０４の合計値が最も少ない物理ノード（サーバ）を削除する物理ノード（サーバ）に決定する（ステップＳ４２）。ここでは、サーバ「＃２」およびそれを管理するディスパッチャＤ２の物理ノードが削除されるものとする。
【００７８】
ディスパッチャＤ１の仮想ノード割当部１６は、削除する物理ノード（サーバ）を決定すると、コンシステントハッシュ環上から、その物理ノードに対応して配置された仮想ノードを取り除き、仮想ノードの新たな担当領域（ハッシュ値１０３）を決定して、新たな仮想ノード割当情報１００（図５）を生成する。そして、ディスパッチャＤ１の仮想ノード割当部１６は、自身の仮想ノード割当情報１００を、生成した新たな仮想ノード割当情報１００で更新した上で、削除するサーバを管理するディスパッチャＤ２を除いた、各ディスパッチャＤ（Ｄ３，Ｄ４）に、新たな仮想ノード割当情報１００を送信する（ステップＳ４３）。そして、各ディスパッチャＤ（Ｄ３，Ｄ４）のアクセス情報管理部１５は、受信した新たな仮想ノード割当情報１００を用いて、記憶部４０に記憶された仮想ノード割当情報１００を更新する。また、仮想ノード割当部１６は、削除するサーバを管理するディスパッチャＤ（ここでは、ディスパッチャＤ２）に対して、削除通知を送信する（ステップＳ４４）。
【００７９】
以上説明したように、本実施形態に係る、分散処理システム１およびディスパッチャＤによれば、コンシステントハッシュを適用したＫＶＳ形式のデータベースにおいて、順序性のあるハッシュ関数を用いることで、範囲検索を行う際の応答速度を高速化できる。さらに、コンシステントハッシュ環上において、仮想サーバのアクセス数１０４をカウントすることにより、アクセスの頻度が偏った箇所に優先的に仮想ノードを割り当て、サーバ負荷を均等にすることができる。
【００８０】
（変形例１）
本実施形態においては、図８および図９に示したように、複数のディスパッチャＤのうちの１つがコーディネータとして機能することにより、サーバの追加や削除に伴う仮想ノード割当処理を行った。しかし、本発明は、これに限定されず、サーバの追加や削除の情報を、ゴシッププロトコル（Gossip protocol）により、配信負荷を抑制しながら、複数のディスパッチャＤ全体に配信し、各ディスパッチャＤの仮想ノード割当部１６それぞれが仮想ノード割当処理を実行するようにしてもよい。
【００８１】
（変形例２）
また、本実施形態のように、複数のディスパッチャＤのうちの１つがコーディネータとして機能する構成に替えて、各ディスパッチャＤと接続される管理装置（分散処理管理装置）を設ける構成にしてもよい。
この場合、管理装置（分散処理管理装置）は、仮想ノード割当情報１００を記憶する記憶部と、アクセス情報収集部と、仮想ノード割当情報生成部を備える。
そして、管理装置のアクセス情報収集部が、各ディスパッチャＤに対し、図８に示したアクセス情報集計通知を送信し、各ディスパッチャＤがカウントしたアクセス情報を、ディスパッチャＤそれぞれから受信する。
【００８２】
管理装置の仮想ノード割当情報生成部は、分散管理システム１に新たなサーバが追加される場合、アクセス情報収集部が収集したアクセス情報に基づき、仮想ノード毎のアクセス数の合計値を計算し、計算したアクセス数の合計値が最も大きい仮想ノードのコンシステントハッシュ環上の担当領域に、新たなサーバの仮想ノードを配置し、新たな仮想ノード割当情報１００を生成する。そして、生成した新たな仮想ノード割当情報１００を、管理装置から各ディスパッチャＤに配信する。
【００８３】
なお、仮想ノード割当情報生成部は、新たな仮想ノード割当情報１００を生成する際に、計算したアクセス数の合計値が最も大きい仮想ノードのコンシステントハッシュ環上の担当領域に、新たなサーバの仮想ノードを配置し、そのアクセス数の合計値を、仮想ノードを配置したことにより分割された領域の領域比に応じて分配して、新たな仮想ノードのアクセス数の合計値として設定し、設定後のコンシステントハッシュ環上の仮想ノードにおいて、アクセス数の合計値が最も大きい仮想ノードの担当領域に、新たなサーバの仮想ノードを配置する仮想ノード割当処理を、新たなサーバに設定される所定数の仮想ノードがコンシステントハッシュ環上に配置し終えるまで実行して、新たな仮想ノード割当情報１００を生成してもよい。
【００８４】
（変形例３）
また、本実施形態に係るディスパッチャＤのアクセス情報管理部１５は、自身のディスパッチャＤが入力データ（クエリ）を処理する度に、すべての入力データについて、仮想ノードのアクセス数１０４のカウント処理を行うものとして説明した（図６参照）。しかしながら、アクセス情報管理部１５は、サーバへアクセスするすべての入力データについてカウント処理を行うのではなく、例えば、所定期間のサンプリングによりカウント処理を行うようにしてもよい。この場合、例えば、時間平均や波形推測等の一般的に用いられる手法により補正を行うことにより、サーバ負荷の均等化を実現する。
【符号の説明】
【００８５】
１      分散処理システム
２      外部システム
３      端末
４      入力装置
５      出力装置
１０    制御部
１１    情報受信部
１２    構文解析部
１３    振り分け処理部
１４    保存情報管理部
１５    アクセス情報管理部
１６    仮想ノード割当部
１７    情報送信部
２０    入出力部
３０    メモリ部
４０    記憶部
１００  仮想ノード割当情報
１３１  ハッシュ値計算部
Ｂ      ロードバランサ
Ｄ      ディスパッチャ
Ｐ      プロセッサ
Ｓ      ストレージ
【図１】
0005719323.tif 000002
【図２】
0005719323.tif 000003
【図３】
0005719323.tif 000004
【図４】
0005719323.tif 000005
【図５】
0005719323.tif 000006
【図６】
0005719323.tif 000007
【図７】
0005719323.tif 000008
【図８】
0005719323.tif 000009
【図９】
0005719323.tif 000010
【図１０】
0005719323.tif 000011