JP5880689B2 - 分散ストレージシステム、制御装置、クライアント端末、負荷分散方法及びプログラム - Google Patents

Description

（関連出願についての記載）
本発明は、日本国特許出願：特願２０１２−０７９９５２号（２０１２年３月３０日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。

本発明は、分散ストレージシステム、制御装置、クライアント端末、負荷分散方法及びプログラムに関し、特に、Ｋｅｙ−Ｖａｌｕｅ型のデータを管理する分散ストレージシステム、制御装置、クライアント端末、負荷分散方法及びプログラムに関する。

特許文献１には、サイト内のＷｅｂサーバに対する負荷分散装置への負荷を軽減し、負荷分散装置への経路に障害が発生した場合にも、高速な経路の切り替えができるという、ネットワークシステムが開示されている。同文献によれば、クライアントとサーバの中間に位置するルータが、クライアントからパケットを受信すると、パケットヘッダに含まれる送信元アドレスのハッシュ値と、送信先Ｌ４ポート番号をもとに、転送先サーバを決定している。これにより、Ｌ４で認識できるサービスごとに異なるサーバに処理を割り当てることができる、とされている。

特許文献２には、一意性を保証しつつ、クライアントへの応答性の劣化を防止することができるという負荷分散装置が開示されている。同文献によれば、負荷分散装置とサーバの間に位置する中継装置が、サーバからクライアントへのレスポンスを参照し、経路識別子（中継装置ごとに割り当てられた識別子）をＬ７データ内に追記する。クライアントが再度リクエストを送信する時に、前回受信した経路識別子を埋め込むことで、それを受信した負荷分散装置が適切な中継装置にパケットを転送する。

特許文献３には、転送先決定処理を複数の装置で分割して処理することによって、ＵＲＬ（Ｕｎｉｆｏｒｍ Ｒｅｓｏｕｒｃｅ Ｌｏｃａｔｏｒ）スイッチの計算量及び記憶容量を削減できるというコンピュータシステムが開示されている。

非特許文献１、２には、オープンフローと呼ばれる集中制御型のネットワークが開示されている。オープンフローは、オープンフローコントローラと呼ばれる制御装置が、オープンフロースイッチと呼ばれるスイッチの振る舞いを制御する集中制御型のネットワークアーキテクチャを採用している。オープンフローによれば、ネットワーク全体の状況に合わせ、仮想ネットワークを構成するスイッチの振る舞いを柔軟に変更することができる。このため、オープンフローを用いることで、柔軟性の高い仮想ネットワークを構築することが容易になっている。

特開２００３−１３１９６１号公報 特開２０１１−０４１００６号公報 特開２００６−３０９３８３号公報

Ｎｉｃｋ ＭｃＫｅｏｗｎほか７名、"ＯｐｅｎＦｌｏｗ： Ｅｎａｂｌｉｎｇ Ｉｎｎｏｖａｔｉｏｎ ｉｎ Ｃａｍｐｕｓ Ｎｅｔｗｏｒｋｓ"、［ｏｎｌｉｎｅ］、［平成２４（２０１２）年２月１４日検索］、インターネット〈URL: http://www.openflow.org/documents/openflow-wp-latest.pdf〉 "ＯｐｅｎＦｌｏｗ Ｓｗｉｔｃｈ Ｓｐｅｃｉｆｉｃａｔｉｏｎ" Ｖｅｒｓｉｏｎ １．１．０ Ｉｍｐｌｅｍｅｎｔｅｄ （Ｗｉｒｅ Ｐｒｏｔｏｃｏｌ ０ｘ０２）、［ｏｎｌｉｎｅ］、［平成２４（２０１２）年２月１４日検索］、インターネット〈URL:http://www.openflow.org/documents/openflow-spec-v1.1.0.pdf〉

以下の分析は、本発明によって与えられたものである。Ｋｅｙ−Ｖａｌｕｅ型のデータを管理する分散ストレージシステムにおいては、転送先サーバ選択の一元化と、リクエスト処理の遅延低減を両立することが困難である。転送先サーバ選択の一元化とは、クライアントからの全リクエストをどのサーバに転送するか選択する処理を単一ノードで行うということである。この処理を複数ノードで行う場合、サーバの追加・削除があった時に、ノード間でサーバ情報の一貫性確保のための仕組みが必要となるため、処理が複雑になるという問題点がある。

一方、転送先サーバ選択を一元化すると、選択処理を行うノードで、全てのクライアントからの全てのリクエストを受信し、転送先サーバを選択し、転送処理を行う必要がある。そのため、該ノードの負荷が高くなり、リクエスト処理の遅延が大きくなるという問題点がある。

この点、特許文献１のネットワークシステムでは、特定のクライアントから同一サービスへのリクエスト頻度が高いと、それは同一のサーバに転送されることになり、負荷分散が十分になされないという問題点がある。

また、特許文献２の発明においても、中継装置で、サーバからクライアントへのすべてのレスポンスを参照する必要があるため、処理遅延の増大につながるという問題点がある。

また、特許文献３には、クライアントからの要求コンテンツの識別子から計算した固定長のハッシュ値と、転送先とを対応付けた転送先選択テーブルを用いて転送先を決定するものである。特定のコンテンツに要求が集中すれば、同一のサーバが選択されることになり、負荷の分散は行われない。

本発明は、上述したＫｅｙ−Ｖａｌｕｅ型のデータを管理する分散ストレージシステムにおける転送先サーバの選択ノードの一元化と、リクエスト処理の遅延低減との両立に貢献できる分散ストレージシステム、制御装置、クライアント端末、負荷分散方法及びプログラムを提供することを目的とする。

第１の視点によれば、それぞれキー情報と対応付けられたデータを格納する複数のサーバと、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、前記パケットに含まれるキー情報に基づき前記パケットの転送先を決定する転送先選択部と、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するエントリ設定部と、を備える制御装置と、を含み、前記パケット転送装置は、前記設定されたフローエントリを用いて、前記同一キー情報を含むパケットを前記転送先に転送する分散ストレージシステムが提供される。

第２の視点によれば、それぞれキー情報と対応付けられてデータを格納する複数のサーバと、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、に接続され、前記パケットに含まれるキー情報に基づき前記要求パケットの転送先を決定する転送先選択部と、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するエントリ設定部と、を備える制御装置が提供される。

第３の視点によれば、キー情報のハッシュ値を用いて生成された送信先アドレスを設定した要求パケットを生成するアドレス設定部を備え、前記要求パケットを用いてサーバに対しリクエストを行うクライアント端末が提供される。

第４の視点によれば、パケット転送装置から、値と組になったキー情報を含む新規パケットの転送先の決定要求を受け付けるステップと、前記制御装置が、前記パケットに含まれるキー情報に基づき、複数のサーバの中から前記パケットの転送先を決定し、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するステップと、を含む負荷分散方法が提供される。本方法は、ユーザに対して項目を提示し、ユーザから項目の選択を受け付けるコンピュータという、特定の機械に結びつけられている。

第５の視点によれば、それぞれキー情報と対応付けられてデータを格納する複数のサーバと、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、に接続された制御装置に搭載されたコンピュータに、前記パケットに含まれるキー情報に基づき前記パケットの転送先を決定する処理と、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定する処理とを実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な（非トランジエントな）記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。

本発明によれば、Ｋｅｙ−Ｖａｌｕｅ型のデータを管理する分散ストレージシステムにおいて、転送先サーバの選択ノードの一元化と、リクエスト処理の遅延低減との両立に貢献することが可能となる。

本発明の一実施形態の構成を示す図である。 本発明の第１の実施形態の分散ストレージシステムの構成を示す図である。 本発明の第１の実施形態の制御装置に保持されるサーバテーブルの一例である。 本発明の第１の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。 本発明の第１の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。 本発明の第２の実施形態の分散ストレージシステムの構成を示す図である。 本発明の第２の実施形態におけるダミーアドレスの生成方法を説明するための図である。 本発明の第２の実施形態の制御装置に保持されるサーバテーブルの一例である。 本発明の第２の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。 本発明の第２の実施形態の動作（転送先サーバ選択処理）を説明するためのフローチャートである。 本発明の第２の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。 本発明の第３の実施形態の分散ストレージシステムの構成を示す図である。 本発明の第３の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。 本発明の第３の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。

はじめに本発明の一実施形態の概要について図面を参照して説明する。なお、この概要に付記した図面参照符号は、理解を助けるための一例として各要素に便宜上付記したものであり、本発明を図示の態様に限定することを意図するものではない。

本発明は、その一実施形態において、図１に示すように、それぞれキー情報と対応付けられてデータを格納する複数のサーバ１と、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置２Ａと、制御装置３Ａと、を含む構成にて実現できる。

より具体的には、制御装置３Ａは、パケット転送装置２Ａから受信したキー情報に基づき前記要求パケットの転送先を決定する転送先選択部３３Ａと、前記転送先への経路上のパケット転送装置２Ａに、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するエントリ設定部３４Ａと、を備える。そして、パケット転送装置２Ａは、前記設定されたフローエントリを用いて、前記同一キー情報を含むパケットを前記転送先に転送する。

以上により、転送先サーバの選択ノードの一元化（上記制御装置３Ａが担当）と、リクエスト処理の遅延低減（上記フローエントリにて実現）とを両立することが可能となる。

［第１の実施形態］
続いて、本発明の第１の実施形態について図面を参照して詳細に説明する。図２は、本発明の第１の実施形態の分散ストレージシステムの構成を示す図である。図２を参照すると、データを保存するサーバ１と、パケットを転送するスイッチ（上記パケット転送装置に相当）２と、スイッチ２の制御を行うコントローラ３と、サーバに対してリクエストを送信するクライアント４とを含む構成が示されている。なお、１台のスイッチ２には、１台以上のサーバ１や１台以上のクライアント４が接続されている。また１台のコントローラ３には、１台以上のスイッチ２が接続されている。

スイッチ２は、フローテーブル２１と、パケット転送部２２と、コントローラ接続部２３とを備えている。

フローテーブル２１は、パケットの転送ルールを記載したエントリから構成される。各エントリは、マッチ条件を格納するルール部と、マッチ条件に適合するパケットに適用する処理内容を格納する処理部とから構成される。ルール部には、マッチ条件として、受信したスイッチポート番号、送信先アドレス、送信元アドレス、ＶＬＡＮ−ＩＤ、Ｌ４の送信元ポート番号、Ｌ４の送信先ポート番号等を表現することができる。また、処理部には転送するスイッチポート番号、マルチキャスト等を表現することができる。

パケット転送部２２は、フローテーブル２１から受信したパケットに適合するマッチ条件を持つエントリを検索し、パケットの転送等を行う。具体的には、パケット転送部２２は、パケットのヘッダ部分と各エントリのルール部とを照合し、マッチした場合に処理部に格納された処理内容を実行する。前記フローテーブル２１及びパケット転送部２２によるフローテーブルのサーチや処理実行は、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）を用いた構成とすることで高速化に実行することができる。一方、どのエントリともマッチしなかった場合、パケット転送部２２は、コントローラ接続部２３を介して、パケットをコントローラ３に送信し、エントリ設定を依頼する。つまり、エントリにマッチした方が、マッチしない場合と比べて、高速にパケットを転送することができる。

コントローラ接続部２３は、受信したパケットのうち、どのエントリにもマッチしなかったパケットをコントローラ３に転送する。

コントローラ３は、サーバテーブル３１と、サーバテーブル管理部３２と、転送先サーバ選択部３３と、エントリ設定部３４とを備えている。

サーバテーブル管理部３２は、カテゴリと担当するサーバ１の対応を管理するサーバテーブル３１を管理する。サーバテーブル３１の各カテゴリには、そのカテゴリを担当するサーバ１のサーバ情報（アドレス、接続されているスイッチ２のポート番号などを含む）が登録される。各カテゴリには、必ず１つ以上のサーバ情報が登録される。図３は、このようなサーバテーブルの例である。

転送先サーバ選択部３３は、スイッチ２からパケットを受信すると、受信パケットとサーバテーブル３１をもとに、転送先サーバを選択する。本実施形態では、パケットの送信先アドレスの上位ビットを、サーバテーブル３１のカテゴリＩＤとマッピングさせ、該当するカテゴリＩＤに登録されたサーバ１を転送先サーバとして選択することとする。

エントリ設定部３４は、転送先サーバ選択部３３が選択したサーバ１に対して、受信パケットが転送されるようフローテーブル２１のエントリを生成し、スイッチ２に対して設定する。またサーバ１が処理結果のレスポンスをクライアント４に送信する時に、そのパケットがクライアント４に転送されるようフローテーブル２１のエントリを生成し、スイッチ２に対して設定する。

なおエントリ設定部３４は、クライアント４からサーバ１へのリクエストパケットと、サーバ１からクライアント４へのレスポンスパケットを区別できる。スイッチ２から受信したパケットの送信元アドレスが、サーバテーブル３１で管理しているサーバ１のアドレスの一つと一致すれば、サーバ１からクライアント４へのレスポンスパケット、サーバテーブル３１で管理されているどのアドレスとも一致しなければ、クライアント４からサーバ１へのリクエストパケットと判断できる。

以上のようなスイッチ２及びコントローラ３は、非特許文献１、２に記載されているオープンフロースイッチと、オープンフローコントローラをベースとして実現できる。

クライアント４は、要求部４１と、アドレス設定部４２と、パケット送受信部４３とを備える各種端末等である。

要求部４１は、サーバ１に対するＫｅｙ―Ｖａｌｕｅ型データの書き込み要求や読み込み要求などのリクエストパケットを生成する。

アドレス設定部４２は、リクエストパケットの送信先アドレス、送信元アドレスを設定する。送信先アドレスとしては、リクエストに含まれるＫｅｙ情報や要求種別に応じたダミーアドレスを設定する。ここでは、リクエストに含まれるＫｅｙを、文字列として所定のハッシュ関数に入力し、所定ビット（例えば、３２ビット）のハッシュ値を計算し、このハッシュ値をダミーアドレスとすることとする。送信元アドレスには、クライアント４の正しいアドレスを設定する。

パケット送受信部４３は、要求部４１からのリクエストパケットをスイッチ２に送信し、またスイッチ２から受信したレスポンスパケットを要求部４１に通知する。

なお、図２に示したスイッチ２、コントローラ３、クライアント４の各部（処理手段）は、これらの装置を構成するコンピュータに、そのハードウェアを用いて、上記した各処理を実行させるコンピュータプログラムにより実現することもできる。

続いて、本実施形態の動作について図面を参照して詳細に説明する。以下の説明では、クライアント４からの（ｋｅｙ１，ｖａｌｕｅ１）というデータの書き込み要求を、４台のサーバ１の中から適切なサーバ１に転送して処理させることを想定する。コントローラ３は既に、４台のサーバ１を検出しており、そのサーバテーブル管理部３２により、図３に示すようなサーバテーブルが作成されているものとする。

はじめに、クライアント４からサーバ１への書き込みリクエストの送信動作について説明する。図４は、本発明の第１の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。

図４を参照すると、まず、クライアント４の要求部４１が（ｋｅｙ１，ｖａｌｕｅ１）の書き込み要求を生成する（ステップＡ１）。次に、アドレス設定部４２がｋｅｙ１を文字列と見なした上で、所定ビット（例えば、３２ビット）のハッシュ値を計算する（ステップＡ２）。ここでは、計算されたハッシュ値の上位２ビットが“１０”であったとする。そしてパケットの送信先アドレスとして上記ハッシュ値を設定し、また送信元アドレスとしてクライアントの正しいアドレスを設定する（ステップＡ３）。次にパケット送受信部４３がリクエストをスイッチ２に送信する（ステップＡ４）。

スイッチ２はパケットを受信すると（ステップＡ５）、パケット転送部２２がフローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＡ６）。エントリが見つからなければ（ステップＡ６のＮｏ）、コントローラ接続部２３はコントローラ３に対して前記パケットを送信する（ステップＡ７）。

コントローラ３は、パケットを受信すると（ステップＡ８）、転送先サーバ選択部３３は、受信したパケットの送信先アドレスと、サーバテーブル３１をもとに転送先サーバを選択する（ステップＡ９）。具体的には、転送先サーバ選択部３３は、サーバテーブル３１から、送信先アドレスの上位ビットに対応するカテゴリＩＤが割り当てられている転送先サーバを選択する。ここでは、ハッシュ値の上位２ビットが“１０”（＝２）であるので、転送先サーバ選択部３３は、転送先サーバとして、カテゴリＩＤ＝２のサーバＳ２を選択する。

次に、エントリ設定部３４は、転送先サーバ選択部３３が選択した転送先サーバに対してパケットが転送されるように、エントリを生成し、クライアント４と前記選択したサーバ１間の経路上のスイッチ２に設定する（ステップＡ１０）。例えば、サーバＳ２が選択された場合、フローエントリの条件部を「送信先アドレス：上位２ビットが“１０”」、処理部を「転送先スイッチポート番号：Ｐ２」（Ｐ２はサーバＳ２が接続されているスイッチポート番号）としたエントリを生成し、スイッチ２に設定する。その後、パケット転送部２２が再度パケットにマッチするエントリがあるか確認する（ステップＡ６）と、ステップＡ１０でエントリが設定されているため、今回はマッチしたエントリが見つかることになる。

なお、ステップＡ６において、マッチしたエントリが見つかれば（ステップＡ６のＹｅｓ）、スイッチ２は、その処理部の内容に従ってパケットを転送する（ステップＡ１１）。例えば、ステップＡ１０で前述したエントリが設定され、そのエントリにマッチしたとすると、パケットはポート番号Ｐ２からサーバＳ２に送信される。サーバ１はリクエストを受信すると、リクエストに合った処理をする（ステップＡ１２）。

なおこれ以降、スイッチ２が「送信先アドレス：上位２ビットが“１０”」に該当するパケットを受信すると、送信元のクライアント４のアドレスに関係なく、コントローラ３にパケットを問い合わせることなく、スイッチポートＰ２から当該パケットを送信することになる。

続いて、前記リクエストパケットを受け取ったサーバ１からクライアント４へのレスポンスの送信動作について説明する。図５は、本発明の第１の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。

図５を参照すると、まずサーバ１がレスポンスパケットを送信する（ステップＢ１）。スイッチ２がパケットを受信すると（ステップＢ２）、パケット転送部２２がフローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＢ３）。エントリが見つからなければ（ステップＢ３のＮｏ）、コントローラ接続部２３がコントローラ３に対して前記レスポンスパケットを送信する（ステップＢ４）。

コントローラ３は、エントリ設定部３４にてクライアント４にパケットが転送されるようフローテーブル２１のエントリを生成し、サーバ１と宛先のクライアント４間の経路上のスイッチ２に設定する（ステップＢ５）。その後、パケット転送部２２が再度パケットにマッチするエントリがあるか確認する（ステップＢ３）。

ステップＢ３において、マッチしたエントリが見つかれば（ステップＢ３のＹｅｓ）、スイッチ２は、そのエントリの処理部の内容に従ってパケットを転送する（ステップＢ６）。クライアント４はレスポンスを受信すると、レスポンスに合った処理をする（ステップＢ７）。

以上のように、本発明の第１の実施形態によれば、パケット転送部２２が設定したエントリに適合するパケットは、フローテーブル２１をもとに高速に転送される。また、転送先サーバの選択ノードは、コントローラ３に一元化されている。従って、転送先サーバの選択ノードの一元化と、リクエスト処理の遅延低減との両立が実現されている。

また、本発明の第１の実施形態では、さらに、エントリ設定部３４が、送信先アドレス全体すなわちハッシュ値全体ではなく、上位ビットをもとにエントリを生成するよう構成したため、パケット転送時にフローテーブル２１のエントリにヒットする確率が高くなり、パケット転送における遅延をさらに低減させることができる。

また、本発明の第１の実施形態では、アドレス設定部４２が、送信先アドレスとして、ダミーアドレスを設定し、実際のサーバ１のアドレスを設定する必要がないよう構成されているため、新規のクライアント４を追加したとしても、セットアップ時にサーバ情報を設定する必要がなく、導入が容易である。

［第２の実施形態］
続いて、書き込み時にレプリケーションを行うようにした本発明の第２の実施形態について図面を参照して詳細に説明する。図６は、本発明の第２の実施形態の分散ストレージシステムの構成を示す図である。

図６を参照すると、本発明の第１の実施形態の構成と同様に、サーバ１と、スイッチ２と、コントローラ３と、クライアント４Ａとを含む構成が示されている。このうちクライアント４Ａは、本発明の第１の実施形態の構成と比べて、同期制御部４４が追加されている点において異なっている。

同期制御部４４は、要求部４１が書き込み要求を送信すると、書き込み要求内にリクエストＩＤを追記する。またパケット送受信部４３で書き込み要求に対するレスポンスを受信すると、レスポンスに含まれるリクエストＩＤを参照する。リクエストＩＤごとにすでに返ってきたレスポンス数を管理しており、返ってきたレスポンス数が、あらかじめ設定されたレプリケーション数に達したレスポンスについてのみ要求部４１に返す。返す時には、レスポンスの中に１つでもエラーが含まれていればエラーのレスポンスを返し、１つもエラーが含まれていなければ正常のレスポンスを返す。また要求部４１が読み込み要求を送信する時、及び、読み込み要求に対するレスポンスを受信した時には、同期制御部４４は何もしない。

またアドレス設定部４２は、リクエストパケットの送信先アドレス、送信元アドレスを設定する。送信先アドレスとしては、リクエストに含まれるＫｅｙ情報や要求種別に応じたダミーアドレスを設定する。以上の点は、本発明の第１の実施形態と同様であるが、本実施形態では、リクエストに含まれるＫｅｙから、所定ビット（例えば、３２ビット）のハッシュ値を計算し、このハッシュ値の最下位ビットにリクエスト種別（書き込み要求：１、読み込み要求：０）で上書きした値をダミーアドレスとすることとする。

図７は、本発明の第２の実施形態におけるダミーアドレスの生成方法を説明するための図である。Ｋｅｙ１のハッシュ値を用いる点は、第１の実施形態と同様であるが、その末尾のビットをリクエスト種別で上書きしてダミーアドレスを生成している。

またコントローラ３の転送先サーバ選択部３３は、スイッチ２からパケットを受信すると、受信パケットとサーバテーブル３１をもとに、転送先サーバを選択する。具体的には、本発明の第１の実施形態と同様に、ここでは、サーバテーブル３１から、パケットの送信先アドレスの上位ビットに対応するカテゴリＩＤに割り当てられたサーバを選択する。更に、本実施形態では、転送先サーバ選択部３３は、最下位ビットのリクエスト種別が１（＝書き込み要求）であれば、予め設定されたレプリケーション数だけ転送先サーバを選択し、最下位ビットのリクエスト種別が０（＝読み込み要求）であれば１台だけ転送先サーバを選択する。

その他本発明の第２の実施形態の構成は、上記した本発明の第１の実施形態の構成と同じであるので、説明は省略する。

続いて、本実施形態の動作について図面を参照して詳細に説明する。以下の説明では、クライアント４からの（ｋｅｙ１，ｖａｌｕｅ１）というデータの書き込み要求を、１２台のサーバ１の中から適切なサーバ１に転送して処理させることを想定する。またレプリケーション数として３が設定されており、サーバテーブル管理部３２によってすでに図８に示すようなサーバテーブルが作成されているものとする。

はじめに、クライアント４からサーバ１への書き込みリクエストの送信動作について説明する。図９は、本発明の第２の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。

図９を参照すると、まず、クライアント４の要求部４１が（ｋｅｙ１，ｖａｌｕｅ１）の書き込み要求を生成する（ステップＣ１）。次に、同期制御部４４は、書き込み要求内にリクエストＩＤを追記する（ステップＣ２）。次に、アドレス設定部４２がｋｅｙ１を文字列と見なした上で、所定ビット（例えば、３２ビット）のハッシュ値を計算する（ステップＣ３）。ここでは、ハッシュ値の上位２ビットが“１０”であったとする。そしてパケットの送信先アドレスとして上記ハッシュ値とリクエスト種別（＝１）を設定し（図７参照）、また送信元アドレスとしてクライアントの正しいアドレスを設定する（ステップＣ４）。次にパケット送受信部４３は、リクエストをスイッチ２に送信する（ステップＣ５）。

スイッチ２はパケットを受信すると（ステップＣ６）、フローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＣ７）。エントリが見つからなければ（ステップＣ７のＮｏ）、コントローラ接続部２３は、パケットをコントローラ３に送信する（ステップＣ８）。

コントローラ３がパケットを受信すると（ステップＣ９）、転送先サーバ選択部３３は、受信したパケットの送信先アドレスと、サーバテーブル３１をもとに転送先サーバを選択する（ステップＣ１０）。

図１０は、上記ステップＣ１０の詳細を表したフローチャートである。図１０を参照すると、まずパケットの送信先アドレスの上位ビットを、サーバテーブル３１のカテゴリＩＤにマッピングさせてカテゴリＩＤを選択する（図１０のステップＤ１）。次に最下位ビットのリクエスト種別を参照し（ステップＤ２）、１（＝書き込み要求）であれば（ステップＤ２のＹｅｓ）、あらかじめ設定されたレプリケーション数だけ転送先サーバを選択する（ステップＤ３）。一方、最下位ビットのリクエスト種別が０（＝読み込み要求）であれば（ステップＤ２のＮｏ）、１台だけ転送先サーバを選択する（ステップＤ４）。例えば、ハッシュ値の上位２ビットが“１０”（＝２）でかつ最下位ビットが“１”であれば、カテゴリＩＤ２に登録されたサーバＳ６、Ｓ７、Ｓ８を転送先サーバとして選択する。

再度、図９を参照すると、次に、エントリ設定部３４は、転送先サーバ選択部３３が選択した転送先サーバに対してパケットが転送されるように、エントリを生成し、スイッチ２に設定する（ステップＣ１１）。例えば、Ｓ６、Ｓ７、Ｓ８が選択された場合、条件部として「送信先アドレス：上位２ビットが“１０”、最下位ビットが“１”」、処理部として「転送先スイッチポート番号：Ｐ６、Ｐ７、Ｐ８」（＝それぞれサーバＳ６、Ｓ７、Ｓ８が接続されているスイッチポート番号）となるエントリを生成して、スイッチ２に設定する。

その後、パケット転送部２２が再度パケットにマッチするエントリがあるか確認する（ステップＣ７）。ステップＣ１１でエントリが設定されているため、今回はマッチしたエントリが見つかることになる。

ステップＣ７において、マッチしたエントリが見つかれば（ステップＣ７のＹｅｓ）、スイッチ２は、見つかったエントリの処理部の内容に従ってパケットを転送する（ステップＣ１２）。例えば、ステップＣ１１で、前述したエントリが設定され、そのエントリにマッチしたとすると、パケットはポート番号Ｐ６、Ｐ７、Ｐ８からそれぞれサーバＳ６、Ｓ７、Ｓ８にマルチキャストで送信される。

サーバ１はリクエストを受信すると、リクエストに合った処理をする（ステップＣ１３）。

なおこれ以降、スイッチ２が「送信先アドレス：上位２ビットが“１０”、最下位ビットが“１”」に該当するパケットを受信すると、送信元のクライアント４のアドレスに関係なく、また、コントローラ３にパケットを問い合わせることもなく、Ｐ６、Ｐ７、Ｐ８から送信することになる。

続いて、前記リクエストパケットを受け取ったサーバ１からクライアント４へのレスポンスの送信動作について説明する。図１１は、本発明の第２の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。

図１１を参照すると、まずサーバ１がリクエストに含まれていたリクエストＩＤを含めてレスポンスを送信する（図１１のステップＥ１）。

スイッチ２がパケットを受信すると（ステップＥ２）、パケット転送部２２がフローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＥ３）。エントリが見つからなければ（ステップＥ３のＮｏ）、コントローラ接続部２３がコントローラ３に対してパケットを送信する（ステップＥ４）。

コントローラ３は、エントリ設定部３４にてクライアント４にパケットが転送されるようフローテーブル２１のエントリを生成し、スイッチ２に対して設定する（ステップＥ５）。その後、パケット転送部２２が再度パケットにマッチするエントリがあるか確認する（ステップＥ３）。

ステップＥ３において、マッチしたエントリが見つかれば（ステップＥ３のＹｅｓ）、スイッチ２は、見つかったエントリの処理部の内容に従ってパケットを転送する（ステップＥ６）。

クライアント４の同期制御部４４がレスポンスを受信する（ステップＥ７）と、リクエストＩＤを参照し、該リクエストＩＤの返ってきたレスポンス数がレプリケーション数に達したかどうか確認する（ステップＥ８）。返ってきたレスポンス数がレプリケーション数に達した場合（ステップＥ８のＹｅｓ）、同期制御部４４は、要求部４１にレスポンスを返し（ステップＥ９）、要求部４１はレスポンスに合った処理をする（ステップＥ１０）。一方、返ってきたレスポンス数がレプリケーション数に達していない場合（ステップＥ８のＮｏ）、何もしない。

続いて。読み込み要求時の動作につて説明する。ここではｋｅｙ１に対するデータの読み込み要求を、１２台のサーバ１の中から適切なサーバ１に転送して処理させることを想定する。

まず、クライアント４からサーバ１へのリクエストの送信動作について説明する。読み込み要求のリクエストの送信動作は、本発明の第１の実施形態のリクエストの送信動作で示した図４と同様である。

ただしステップＡ３において、コントローラ３がパケットの送信先アドレスとして、ステップＡ２で求めた上記ハッシュ値とリクエスト種別（＝０）をもとに設定し、また送信元アドレスとしてクライアントの正しいアドレスを設定する。

またステップＡ９において、転送先サーバ選択部３３は、受信したパケットの送信先アドレスと、サーバテーブル３１をもとに転送先サーバを選択するが、詳細に説明すると、図１０の通りとなる。例えば、ハッシュ値の上位３ビットが“１００”でかつ最下位ビットが“０”であれば、カテゴリＩＤ２の中から転送先サーバとしてサーバＳ６を選択し、ハッシュ値の上位３ビットが“１０１”でかつ最下位ビットが“０”であれば、転送先サーバとしてサーバＳ７を選択する。このように同一カテゴリＩＤへの読み込み要求は、同一カテゴリＩＤでデータがレプリケーションされているはずなので、ロードバランシングされるように選択することができる。

上記以外の動作は、本発明の第１の実施形態のリクエストの送信動作と同様であるので、説明は省略する。

上記読み込み要求に対するサーバ１からクライアント４へのレスポンスの送信動作は、本発明の第１の実施形態のレスポンスの送信動作と同様であるので、説明は省略する。

以上のように、本発明の第２の実施形態では、データのレプリケーションを行う時に、クライアント４からサーバ１に向けてマルチキャストを送信するのではなく、スイッチ２からマルチキャストを送信するよう構成されているため、ネットワーク全体で流れるパケット量を抑え、フラッディングが発生しにくいという特有の利点がある。

また本発明の第２の実施形態では、読み込み要求が同一レプリケーションを持つサーバ間で負荷分散されているので、サーバの負荷を抑えることができる。

［第３の実施形態］
続いて、クライアント４とスイッチ２との間に中継ノード（フロントエンド６）を配置し、ダミーアドレスの生成をこの中継ノードで行うようにした本発明の第３の実施形態について図面を参照して詳細に説明する。図１２は、本発明の第３の実施形態の分散ストレージシステムの構成を示す図である。

図１２を参照すると、本発明の第１の実施形態の構成と同様に、サーバ１と、スイッチ２と、コントローラ３と、クライアント４Ｂと、ロードバランサ５と、フロントエンド６とを含む構成が示されている。

ロードバランサ５は、パケット転送部５１を備えた負荷分散装置である。パケット転送部５１は、クライアント４Ｂから受信したリクエストを、接続されたフロントエンド６の一つに転送する。転送時にはパケットの送信先アドレスを転送先のフロントエンド６のアドレスに変更する。また、パケット転送部５１は、フロントエンド６から受信したレスポンスを、クライアント４Ｂに転送する。

フロントエンド６は、リクエストの前処理を行う装置であり、アドレス設定部６１およびパケット送受信部６２を備える。

アドレス設定部６１は、ロードバランサ５から受信したリクエストの送信先アドレスを設定する。送信先アドレスとしては、リクエストに含まれるＫｅｙ情報や要求種別に応じたダミーアドレスを設定する。ここでは、リクエストに含まれるＫｅｙから所定ビット（例えば、３２ビット）のハッシュ値を計算し、ハッシュ値をダミーアドレスとすることとする。送信元アドレスは、パケットにもともと設定されていたクライアント４Ｂのアドレスのままである。

パケット送受信部６２は、ロードバランサ５からリクエストを受信し、アドレス設定部６１によって処理が行われたリクエストをスイッチ２に送信する。またスイッチ２から受信したレスポンスをロードバランサ５に送信する。

またクライアント４Ｂは、アドレス設定部４２が送信先アドレスとしてロードバランサ５のアドレスを設定し、送信元アドレスとしてクライアント４Ｂの正しいアドレスを設定する。

これ以外の構成は、本発明の第１の実施形態の構成と同じなので、説明は省略する。

続いて、本実施形態の動作について図面を参照して詳細に説明する。以下の説明では、クライアント４からの（ｋｅｙ１，ｖａｌｕｅ１）というデータの書き込み要求を、４台のサーバ１の中から適切なサーバ１に転送して処理させることを想定する。４台のサーバ１はすでにコントローラ３に検出されており、サーバテーブル管理部３２によってすでに図３に示すようなサーバテーブルが作成されているものとする。

はじめに、クライアント４からサーバ１への書き込みリクエストの送信動作について説明する。図１３は、本発明の第３の実施形態の動作（書き込み要求時）を説明するためのフローチャートである。

図１３を参照すると、まず、クライアント４の要求部４１が（ｋｅｙ１，ｖａｌｕｅ１）の書き込み要求を生成する（ステップＦ１）。次に、アドレス設定部４２がパケットの送信先アドレスとしてロードバランサ５のアドレスを設定し、また送信元アドレスとしてクライアントの正しいアドレスを設定する（ステップＦ２）。次にパケット送受信部４３が、ロードバランサ５に対してリクエストを送信する（ステップＦ３）。

ロードバランサ５はリクエストを受信すると（ステップＦ４）、接続されたフロントエンド６の１つにリクエストを転送する（ステップＦ５）。

フロントエンド６はリクエストを受信すると（ステップＦ６）、アドレス設定部６１がリクエストに含まれるｋｅｙ１から、所定ビット（例えば、３２ビット）のハッシュ値を計算する（ステップＦ７）。ここでは、ハッシュ値の上位２ビットが“１０”であったとする。そしてパケットの送信先アドレスとして上記ハッシュ値を設定し、また送信元アドレスとして、パケットにもともと設定されていたクライアント４の正しいアドレスを設定する（ステップＦ８）。そして、フロントエンド６は、スイッチ２に対してリクエストを送信する（ステップＦ９）。

スイッチ２はパケットを受信すると（ステップＦ１０）、パケット転送部２２にてフローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＦ１１）。エントリが見つからなければ（ステップＦ１１のＮｏ）、コントローラ接続部２３がコントローラ３に対してパケットを送信する（ステップＦ１２）。

コントローラ３はパケットを受信すると（ステップＦ１３）、転送先サーバ選択部３３にて、受信したパケットの送信先アドレスと、サーバテーブル３１をもとに転送先サーバを選択する。ここではパケットの送信先アドレスの上位ビットを、サーバテーブル３１のカテゴリＩＤとマッピングさせ、送信先アドレスの上位ビットに応じて転送先サーバを選択する（ステップＦ１４）。ここでは、ハッシュ値の上位２ビットが“１０”（＝２）であるため、転送先サーバ選択部３３は、転送先サーバとしてカテゴリＩＤ２に登録されたサーバＳ２を選択する。

次にエントリ設定部３４は、転送先サーバ選択部３３が選択した転送先サーバに対してパケットが転送されるように、エントリを生成し、スイッチ２に設定する（ステップＦ１５）。例えば、サーバＳ２が選択された場合、エントリの条件部として「送信先アドレス：上位２ビットが“１０”」、処理部として「転送先スイッチポート番号：Ｐ２」（＝サーバＳ２が接続されているスイッチポート番号）となるエントリを生成して、スイッチ２に設定する。

その後、パケット転送部２２は再度パケットにマッチするエントリがあるか確認する（ステップＦ１１）。ステップＦ１５でエントリが設定されているため、今回はマッチしたエントリが見つかることになる。

ステップＦ１１において、マッチしたエントリが見つかれば（ステップＦ１１のＹｅｓ）、スイッチ２は、見つかったエントリの処理部の内容に従ってパケットを転送する（ステップＦ１６）。例えば、ステップＦ１５で前述したエントリが設定され、そのエントリにマッチしたとすると、パケットはポート番号Ｐ２からサーバＳ２に送信される。

サーバ１はリクエストを受信すると、リクエストに合った処理をする（ステップＦ１７）。

なおこれ以降、スイッチ２が「送信先アドレス：上位２ビットが“１０”」に該当するパケットを受信すると、送信元のクライアント４のアドレスに関係なく、コントローラ３にパケットを問い合わせることなく、スイッチポートＰ２から送信することになる。

続いて、前記リクエストパケットを受け取ったサーバ１からクライアント４へのレスポンスの送信動作について説明する。図１４は、本発明の第３の実施形態の動作（サーバからの応答時）を説明するためのフローチャートである。

図１４を参照すると、まずサーバ１がリクエストに対するレスポンスを送信する（図１４のステップＧ１）。

スイッチ２はパケットを受信すると（ステップＧ２）、パケット転送部２２にてフローテーブル２１を参照して、受信パケットにマッチするエントリがあるか確認する（ステップＧ３）。エントリが見つからなければ（ステップＧ３のＮｏ）、コントローラ接続部２３がパケットをコントローラ３に送信する（ステップＧ４）。

コントローラ３は、エントリ設定部３４にてクライアント４にパケットが転送されるようフローテーブル２１のエントリを生成し、スイッチ２に対して設定する（ステップＧ５）。

その後、スイッチ２のパケット転送部２２は再度パケットにマッチするエントリがあるか確認する（ステップＧ３）。

ステップＧ３において、マッチしたエントリが見つかれば（ステップＧ３のＹｅｓ）、スイッチ２は、見つかったエントリの処理部の内容に従ってパケットを転送する（ステップＧ６）。

フロントエンド６はレスポンスを受信するとロードバランサ５に転送し（ステップＧ７）、ロードバランサがレスポンスを受信するとクライアント４に転送する（ステップＧ８）。

クライアント４はレスポンスを受信すると、レスポンスに合った処理をする（ステップＧ９）。

以上のように、本発明の第３の実施形態では、送信先アドレスのダミーアドレス化をロードバランサ５よりサーバ１側に位置するフロントエンド６によって行うよう構成されているため、クライアント４が、ロードバランサ５より手前で、コントローラ３に制御されない形式のスイッチに接続されていても良い。

以上、本発明の実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、上記した実施形態では、ハッシュ計算を用いて、フローエントリのルール部と照合するアドレスを作成するものとして説明したが、その他方式により、Ｋｅｙからフロー識別子等を作成する方法も採用可能である。

また、上記した実施形態では、クライアント４又はフロントエンド６に、アドレス設定部を設けて、クライアント４側又はフロントエンド６側でハッシュ値を生成するものとして説明したが、クライアント４又はフロントエンド６ではハッシュ値の生成は行わず、キー情報をそのまま送信することとしてもよい。この場合、コントローラ３がキー情報からハッシュ値を生成したり、キー情報から一意に求められるフロー識別子を生成することになる。そして、コントローラ３が経路上のスイッチ２に、該当パケットのヘッダ領域等にこれらハッシュ値やフロー識別子を埋め込む処理や追加ヘッダを付加させる処理を行わせることでも同様の制御を実現できる。

前記したフロー識別子としては、種々のものを用いることができる。例えば、ＫｅｙをＡＳＣＩＩコードに沿って数値化し、それをｍｏｄ計算（例えば、ｍｏｄ ２^３２）で剰余を計算した結果を、送信先アドレスとしても構わない。

なお、上記の特許文献および非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。

１ サーバ
２ スイッチ
２Ａ パケット転送装置
３ コントローラ
３Ａ 制御装置
４、４Ａ、４Ｂ クライアント
５ ロードバランサ
６ フロントエンド
２１ フローテーブル
２２、５１ パケット転送部
２３ コントローラ接続部
３１ サーバテーブル
３２ サーバテーブル管理部
３３ 転送先サーバ選択部
３３Ａ 転送先選択部
３４ エントリ設定部
３４Ａ エントリ設定部
４１ 要求部
４２、６１ アドレス設定部
４３、６２ パケット送受信部
４４ 同期制御部

Claims (9)

1. それぞれキー情報と対応付けられたデータを格納する複数のサーバと、
   前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、
   前記パケットに含まれるキー情報に基づき前記パケットの転送先を決定する転送先選択部と、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するエントリ設定部と、を備える制御装置と、を含み、
   前記パケット転送装置は、前記設定されたフローエントリを用いて、前記同一キー情報を含むパケットを前記転送先に転送すること、
   を特徴とする分散ストレージシステム。
2. 前記パケットには、前記キー情報のハッシュ値を用いて生成された送信先アドレスが設定され、
   前記フローエントリのマッチ条件として、前記ハッシュ値の所定ビットを用いる請求項１の分散ストレージシステム。
3. 前記転送先選択部は、前記キー情報からハッシュ値を生成し、前記生成したハッシュ値の所定ビットを用いて前記パケットの転送先を決定する請求項１の分散ストレージシステム。
4. 前記パケットに要求種別情報が含まれており、該要求種別情報が書き込み要求である場合、前記転送先選択部は、所定数の転送先を選択し、
   前記所定数のレプリケーションを行う請求項１から３いずれか一の分散ストレージシステム。
5. 前記所定数のレプリケーションが完了したか否かを確認する同期制御部がクライアント側に設けられている請求項４の分散ストレージシステム。
6. 前記パケットの送信元と前記パケット転送装置との間に中継ノードが配置され、
   前記中継ノードが、前記パケットの送信元から受信したパケットを、キー情報のハッシュ値を用いて生成された送信先アドレスを持つ前記サーバ宛のパケットに変換する請求項１、２、４、５いずれか一の分散ストレージシステム。
7. それぞれキー情報と対応付けられてデータを格納する複数のサーバと、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、に接続され、
   前記パケットに含まれるキー情報に基づき前記要求パケットの転送先を決定する転送先選択部と、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するエントリ設定部と、を備える制御装置。
8. パケット転送装置から、値と組になったキー情報を含む新規パケットの転送先の決定要求を受け付けるステップと、
   前記制御装置が、前記パケットに含まれるキー情報に基づき、複数のサーバの中から前記パケットの転送先を決定し、前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定するステップと、を含む負荷分散方法。
9. それぞれキー情報と対応付けられてデータを格納する複数のサーバと、前記キー情報を含む前記サーバ宛の新規パケットを受信すると、制御装置に対して、前記複数のサーバの中から転送先の決定を要求するパケット転送装置と、に接続された制御装置に搭載されたコンピュータに、
   前記パケットに含まれるキー情報に基づき前記パケットの転送先を決定する処理と、
   前記転送先への経路上のパケット転送装置に、以後同一キー情報を含むパケットを前記転送先へ転送させるフローエントリを設定する処理とを実行させるプログラム。

Images