(57)【要約】【課題】  オブジェクトを冗長的に複数の配置先に配置している場合に、配置先が減った場合でも、オブジェクトを効率よくアクセスする。【解決手段】  オブジェクト配置装置は、０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、リングのM個の区間とM個の登録された配置先の対応情報とを、記憶するリング記憶手段のアクセス手段と、入力されたオブジェクトの固有情報を、リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の所定方向に隣接する区間に対応する配置先に、オブジェクトを配置することを決定する配置先決定手段と、を備える。【選択図】      図１
2015203797.tif 000002
【特許請求の範囲】
【請求項１】
０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、前記リングのM個の区間とM個の登録された配置先の対応情報とを、記憶するリング記憶手段のアクセス手段と、
入力されたオブジェクトの固有情報を、前記リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の前記所定方向に隣接する区間に対応する配置先に、前記オブジェクトを配置することを決定する配置先決定手段と、を備えるオブジェクト配置装置。
【請求項２】
前記対応情報から配置先の削除を指示されると、削除される配置先に対応する区間である削除装置区間の前記所定方向に隣接する区間の始点を前記削除装置区間の始点に変更し、間隔が前記数値範囲の１／（M−１）に拡張された各区間が、前記削除装置区間の始点を基準に前記リング上の順番を変えずに配置されるように、前記リングを更新する構成変更手段を、さらに備える請求項１のオブジェクト配置装置。
【請求項３】
前記配置先決定手段は、障害許容台数X（X≧３）を入力されると、
2015203797.tif 000004
の整数部C0を算出し、オブジェクトをX+C0+１台の配置先に配置する、請求項２のオブジェクト配置装置。
【請求項４】
前記配置先決定手段は、ａ）固有情報のハッシュ値を包含する区間に対応する配置先にオブジェクトを配置することを決定し、ｂ）前記障害許容台数Xを入力されると、Cの少数部C1と前記所定値／Mの積C2を算出し、区間の始点とハッシュ値の差異がC2以上であるオブジェクトは、X+C0台の配置先に配置する、請求項３のオブジェクト配置装置。
【請求項５】
新たな配置先の登録を指示されると、前記リングの何れかの区間を選択し、間隔が前記数値範囲の１／（M+１）に縮小された各区間が、選択された区間の始点を基準に前記リング上の順番を変えずに配置されるように前記リングを更新し、前記新たな配置先と、前記選択された区間と前記所定方向の逆方向に隣接する区間とを対応付けて前記対応情報に登録する構成変更手段を、さらに備える請求項１のオブジェクト配置装置。
【請求項６】
０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、前記リングのM個の区間とM個の登録された配置先の対応情報とを、記憶して、
入力されたオブジェクトの固有情報を、前記リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の前記所定方向に隣接する区間に対応する配置先に、前記オブジェクトを配置することを決定する、オブジェクト配置方法。
【請求項７】
前記対応情報から配置先の削除を指示されると、削除される配置先に対応する区間である削除方法区間の前記所定方向に隣接する区間の始点を前記削除方法区間の始点に変更し、間隔が前記数値範囲の１／（M−１）に拡張された各区間が、前記削除方法区間の始点を基準に前記リング上の順番を変えずに配置されるように、前記リングを更新する請求項６のオブジェクト配置方法。
【請求項８】
障害許容台数X（X≧３）を入力されると、
2015203797.tif 000005
の整数部C0を算出し、オブジェクトをX+C0+１台の配置先に配置する、請求項７のオブジェクト配置方法。
【請求項９】
ａ）固有情報のハッシュ値を包含する区間に対応する配置先にオブジェクトを配置することを決定し、ｂ）前記障害許容台数Xを入力されると、Cの少数部C1と前記所定値／Mの積C2を算出し、区間の始点とハッシュ値の差異がC2以上であるオブジェクトは、X+C0台の配置先に配置する、請求項７のオブジェクト配置方法。
【請求項１０】
コンピュータに、請求項６乃至９の何れか１項に記載のオブジェクト配置方法を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、オブジェクト配置装置、オブジェクト配置方法、及び、プログラム、特に、オブジェクトを冗長的に分散配置するオブジェクト配置装置、オブジェクト配置方法、及び、プログラムに関する。
【背景技術】
【０００２】
複数の記憶装置、記憶媒体、場所、物理的な値などの配置先にオブジェクトを配置する際、オブジェクトの配置先の決定方法が問題になる。オブジェクトにアクセスする際、該オブジェクトと配置先の対応を高速に決定できない場合、オブジェクトに高速にアクセスすることが難しくなる。ここで、オブジェクトは、例えば、データ通信網を使って送付されるプログラム、データである。オブジェクトは、輸送機関を使って送付される、物理的な書類、装置等の物であっても良い。
【０００３】
オブジェクトの配置先の決定方法として、オブジェクトの識別子などをアルゴリズムで処理して決定する方法が有る。該方法は、オブジェクトの識別子情報と配置先の情報をアルゴリズムに入力して、該オブジェクトを配置する配置先を特定する。
【０００４】
特許文献１は、この方法の一例を開示する。特許文献１の装置は、オブジェクトの識別子をシードとして特殊な疑似乱数発生装置により疑似乱数を発生する。該装置は、発生した乱数値と記憶装置の対応表を記憶している。そのうえで、該装置は、対応する記憶装置がある疑似乱数を発生するまで疑似乱数の発生を繰り返して、オブジェクトを配置する記憶装置を決定する。
【０００５】
該装置で用いる疑似乱数発生部は、発生する疑似乱数の値域を拡大縮小することが可能であり、値域を拡大縮小する前後で、重なる値域内の疑似乱数は同じ値を同じ順番で出力する。また、この疑似乱数発生部は、疑似乱数の値域を拡大縮小した後もすべての疑似乱数を同じ確率で出力する。
【０００６】
該装置は、この乱数を用いて、オブジェクトに高速にアクセスすること、および、オブジェクトの一様な分散を可能にする。さらに、該装置は、記憶装置の増減があった場合でもオブジェクトの移動を少なく抑える。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】ＷＯ２０１２／０２３３８４
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１に開示されている装置は、オブジェクト保護のために、一つのオブジェクトを複数の配置先に分散して、冗長的に配置することができる。このような冗長的な配置において、配置先が１つ減ると、減った後に第１の配置先として選ばれる配置先にオブジェクトが存在しない場合がある。
【０００９】
該装置は、第１の配置先にアクセスしてオブジェクトを取得できないと（図１２の１、２）、第２以降の配置先、即ち、オブジェクトが冗長的に配置された配置先にアクセスして取得する（図１２の３、４）。従って、配置先からオブジェクトを入手する際の処理が複雑、かつ、遅くなる。
【００１０】
本発明は、上記課題を解決する、オブジェクト配置手段を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明の一実施形態にかかるオブジェクト配置装置は、０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、前記リングのM個の区間とM個の登録された配置先の対応情報とを、記憶するリング記憶手段のアクセス手段と、入力されたオブジェクトの固有情報を、前記リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の前記所定方向に隣接する区間に対応する配置先に、前記オブジェクトを配置することを決定する配置先決定手段と、を備える。
【００１２】
本発明の一実施形態にかかるオブジェクト配置方法は、０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、前記リングのM個の区間とM個の登録された配置先の対応情報とを、記憶して、入力されたオブジェクトの固有情報を、前記リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の前記所定方向に隣接する区間に対応する配置先に、前記オブジェクトを配置することを決定する。
【発明の効果】
【００１３】
本発明は、オブジェクトの配置先を、複数の配置先の中から、オブジェクトの固有情報をアルゴリズムで処理して決定する装置を対象とする。本発明は、当該装置がオブジェクトを冗長的に複数の配置先に配置している場合に、配置先が減った場合でも、オブジェクトを効率よくアクセスできる、オブジェクトの配置手段を提供する。
【図面の簡単な説明】
【００１４】
【図１】図１は、第１の実施の形態にかかるオブジェクト配置システム５０の構成図である。
【図２】図２は、リング記憶部４０に記憶されるデータの構造を示す。
【図３】図３は、図２のデータ例が示すハッシュリングを示す。
【図４】図４は、配置先決定部１３が、供給装置３２から受信したオブジェクトを何れかの配置先装置３０に配置するときのフローチャートである。
【図５】図５は、配置先決定部１３が、利用装置３１から要求されたオブジェクトを何れかの配置先装置３０から読み込むときのフローチャートである。
【図６】図６は、構成変更部１１が、新たな配置先装置３０をリング記憶部４０に登録するときのフローチャートである。
【図７】図７は、図３のハッシュリングに配置先装置３０を追加した後のハッシュリングを示す。
【図８】図８は、構成変更部１１が、指定された配置先装置３０をリング記憶部４０から削除するときのフローチャートである。
【図９】図９は、図３のハッシュリングから配置先装置３０を削除した後のハッシュリングを示す。
【図１０】図１０は、コンピュータを用いて、上述したオブジェクト配置装置１０を実現したときのハードウェア構成を示す図である。
【図１１】図１１は、第２の実施の形態にかかるオブジェクト配置装置１０の構成図である。
【図１２】図１２は、公知文献の技術の課題を示す図である。
【発明を実施するための形態】
【００１５】
＜第１の実施の形態＞
図１は、本実施の形態にかかるオブジェクト配置システム５０の構成図である。オブジェクト配置システム５０は、オブジェクト配置装置１０、並びオブジェクト配置装置１０に接続された、リング記憶部４０、配置先装置３０、利用装置３１、供給装置３２、および、端末装置３３を包含する。各装置は、信号ケーブル、または、通信ネットワーク３４を経由して接続されている。配置先装置３０、利用装置３１、および、供給装置３２は、一台のオブジェクト配置装置１０に対して各々複数接続されていても良い。
【００１６】
オブジェクト配置装置１０は、供給装置３２からオブジェクトを取得して、配置先装置３０を選択して、オブジェクトを選択した配置先装置３０に格納する。また、オブジェクト配置装置１０は、利用装置３１からオブジェクトのアクセス要求を取得して、当該オブジェクトを格納している配置先装置３０を特定して、特定した配置先装置３０から当該オブジェクトを得て要求元の利用装置３１に送信する。同一の装置が、状況に応じて、利用装置３１として機能したり、供給装置３２として機能したりしても良い。配置先装置３０は、データベースサーバ装置、あるいは、ファイルサーバ装置と呼ばれるコンピュータであっても良いし、ストレージ装置、ディスク装置であっても良い。
【００１７】
ここで、オブジェクトは、通信ネットワーク３４を使って送付されるデータ、プログラム、ドキュメント、画像、音楽、その他のデータである。
【００１８】
オブジェクト配置装置１０は、構成変更部１１、アクセス部１２、および、配置先決定部１３を包含する。配置先決定部１３は、オブジェクトを格納する配置先装置３０を選択して当該オブジェクトをそこに送信したり、オブジェクトを格納している配置先装置３０を特定して当該オブジェクトをそこから受信したりする。以降、この選択、及び、特定をまとめて、決定と呼ぶことがある。
【００１９】
アクセス部１２はリング記憶部４０の入出力を行う。リング記憶部４０は、配置先決定部１３が参照する配置先装置３０の情報を記憶している。構成変更部１１は、端末装置３３から入力された指示に従って、リング記憶部４０内の情報に新たな配置先装置３０を登録したり、リング記憶部４０内の情報から配置先装置３０を削除したりする。
【００２０】
ここで、構成変更部１１、アクセス部１２、および、配置先決定部１３は、論理回路で構成される。構成変更部１１、アクセス部１２、および、配置先決定部１３は、コンピュータであるオブジェクト配置装置１０のＣＰＵ（Central Processing Unit）がソフトウェアを実行することにより実現されても良い。リング記憶部４０は、ディスク装置等の記憶装置である。
【００２１】
図２は、リング記憶部４０に記憶されるデータの構造を示す。リング記憶部４０は、各配置先装置３０に結びつけて、配置先定義４１と区間の始点４２を包含するレコードを格納する。配置先定義４１は、当該レコードが結びつけられている配置先装置３０に関する定義情報、例えば、通信アドレス、識別子、通信に必要となるパラメータ情報である。
【００２２】
区間の始点４２は、当該レコードが結びつけられている配置先装置３０に割り当てられているハッシュリングの区間の識別情報、例えば、始点である。配置先決定部１３は、例えば、オブジェクトの固有情報のハッシュ値を求め、当該ハッシュ値が包含される区間に結びつけられている配置先装置３０を、当該オブジェクトの配置先として決定する。
【００２３】
図２が示すデータ例は、配置先装置ａ、ｂ、ｃ、ｄの４台の配置先装置３０が登録されており、各々の装置は、０、３０、６０、９０を始点とする各区間に割り当てられていることを示す。
【００２４】
図３は、図２のデータ例が示すハッシュリングを示す。ハッシュリングは、０から所定値（この例では１２０）までの数値範囲を、等間隔に分割して作成された区間を、小さい順に時計回りに並べたリングである。区間の数は、配置先装置３０の数と一致している。図３は、０から３０迄のａ区間（３０は含まず）、３０から６０迄のｂ区間（６０は含まず）、６０から９０迄のｃ区間（９０は含まず）、９０から１２０あるいは０迄のｄ区間（１２０あるいは０は含まず）の４つの区間からなるハッシュリングの例を示す。なお、ハッシュリングの値の加減は、リングの長さを法とする剰余算により行われる。
【００２５】
上記所定値は、ハッシュリングの長さと呼ばれ、例えば、オブジェクト配置システム５０の管理者により、パラメータとしてオブジェクト配置装置１０に与えられる。
【００２６】
図４は、配置先決定部１３が、供給装置３２から受信したオブジェクトを何れかの配置先装置３０に配置するときのフローチャートである。まず、配置先決定部１３は、受信したオブジェクトの固有情報、例えば、識別子を、ハッシュ関数に入力してハッシュ値を得る（Ｓ１１）。
【００２７】
ハッシュ関数は、同じ情報を入力した場合に同じハッシュ値を返し、異なる情報を入力した場合は、多くの場合で異なるハッシュ値を返す。また、ハッシュ関数は、ハッシュ値がハッシュ値の値域にほぼ一様に分布するようにハッシュ値を出力する。ハッシュ値の値域は、ハッシュリングの長さと一致する。即ち、ハッシュ値は、ハッシュリング上の１点を特定する。
【００２８】
配置先決定部１３は、ハッシュ値を包含する区間を決定し（Ｓ１２）、決定された区間と結びついている配置先装置３０を第１の配置先”と決定する（Ｓ１３）。
【００２９】
配置先決定部１３は、決定された区間の時計回りに進んだ（Ｘ+Ｎ-１）個の区間と結びついている配置先装置３０を第２以降の配置先と決定する（Ｓ１４）。なお、第２以降の配置先への配置は、配置先装置３０が削除されたり障害を発生したりした場合でも、当該オブジェクトを読み出すことができるようにする目的で行う。第１の配置先を含めたオブジェクトの配置数（Ｘ+Ｎ）の決定方法は後述する。
【００３０】
最後に、配置先決定部１３は、決定した配置先装置３０に、供給装置３２から受信したオブジェクトを送信する（Ｓ１５）。
【００３１】
図５は、配置先決定部１３が、利用装置３１から要求されたオブジェクトを何れかの配置先装置３０から読み込むときのフローチャートである。まず、配置先決定部１３は、受信したオブジェクトの固有情報、例えば、識別子を、前述したハッシュ関数に入力してハッシュ値を得る（Ｓ２１）。
【００３２】
配置先決定部１３は、ハッシュ値を包含する区間を決定し（Ｓ２２）、決定された区間と結びついている配置先装置３０からオブジェクトを読み込んで（Ｓ２３）、要求元の利用装置３１に出力する（Ｓ２４）。
【００３３】
本実施形態のオブジェクト配置装置１０は、配置先装置３０の増減があっても、オブジェクトのハッシュ値から特定される第１の配置先にオブジェクトが存在するようにオブジェクトを冗長的に配置する。
【００３４】
図６は、構成変更部１１が、新たな配置先装置３０をリング記憶部４０に登録するときのフローチャートである。
【００３５】
まず、構成変更部１１は、リング記憶部４０に登録されている最初の区間、例えば、図３の例において値０を始点とする区間ａを選択する（Ｓ３１）。構成変更部１１は、リング記憶部４０に登録されている他の任意の区間を選択しても良い。
【００３６】
次に、構成変更部１１は、ハッシュリングの長さを、追加した後の配置先装置３０の数で割り、長さＡを得る（Ｓ３２）。図３の例では、長さＡは、１２０／（４＋１）の計算の結果、２４となる。
【００３７】
構成変更部１１は、選んだ区間の始点（点Ａ）からハッシュリングの反時計回りに長さＡだけ進んだ点（点Ｂ）を始点とする区間を、追加した配置先装置３０に結び付ける（Ｓ３３）。
【００３８】
図７は、図３のハッシュリングに配置先装置３０を追加した後のハッシュリングを示す。このハッシュリングにおいて、点Ａは値０（１２０）の点であり、点Ｂは値９６（１２０−２４）の点である。新たな配置先装置３０（以降、配置先装置ｅと称する）は、点Ｂを始点とする新たな区間ｅと結びつけられる。
【００３９】
この処理は、リング記憶部４０に格納されている表（図２）に、最下行を追加し、追加した配置先装置３０の情報を当該行の配置先定義４１に格納し、値９６を当該行の区間の始点４２に格納することに相当する。
【００４０】
次に、構成変更部１１は、点Ｂの値を基準に、ハッシュリング上の各区間の順番を変えないように、各区間を長さＡに縮小する（Ｓ３４）。構成変更部１１は、図３の例において、点Ｂ（値９６）基準に、順次長さＡ（２４）を、時計回りに各区間の始点４２に加算していく。これらの区間の始点４２は、順次、９６+２４＝０、０+２４=２４、２４+２４＝４８、４８+２４＝７２となる。
【００４１】
この後、構成変更部１１は、変更後のハッシュリングに合わせた、オブジェクトの配置変更を開始する（Ｓ３５）。
【００４２】
なお、配置先決定部１３は、上記の配置変更が終了するまでは、ハッシュ値が区間ｅに包含されるオブジェクトの第１の配置先を、新たに追加された配置先装置３０ではなく、区間ａと結びついている配置先装置ａとする。また、配置先決定部１３は、新たに追加された配置先装置３０を、ハッシュ値が区間ｅに包含されるオブジェクトの第２の配置先とする。この第１の配置先と第２の配置先の一時的な入れ替えは、配置変更が終了する迄の間、ハッシュ値が区間ｅに包含されるオブジェクトが、第１の配置先に格納されていることを保証する為である。配置変更中あっても、ハッシュ値が他の区間に包含されるオブジェクトは、第１の配置先に格納されている。
【００４３】
なお、リング記憶部４０に初めて配置先装置３０を登録する際、構成変更部１１は、当該配置先装置３０に結びつけられる区間の始点４２には、例えば、０を設定する。構成変更部１１は、リングの長さ未満の他の任意の値を設定しても良い。
【００４４】
図８は、構成変更部１１が、指定された配置先装置３０をリング記憶部４０から削除するときのフローチャートである。
【００４５】
まず、構成変更部１１は、ハッシュリングの長さを、削除した後の配置先装置３０の数で割り、長さＢを得る（Ｓ４１）。図３の例では、長さＡは、１２０／（４−１）の計算の結果、４０となる。
【００４６】
次に、構成変更部１１は、削除する配置先装置３０が結びついている区間からハッシュリングの時計回りに隣接する区間の始点を、削除する配置先が結びついている区間の始点（点Ｃ）に移動する（Ｓ４２）。
【００４７】
図９は、図３のハッシュリングから配置先装置３０を削除した後のハッシュリングを示す。構成変更部１１は、例えば、区間ｂに結びついていた配置先装置３０を削除するとき、区間ｂからハッシュリングの時計回りに隣接する区間ｃの始点（変更前は値６０）を、点Ｃ（値３０）に移動する。
【００４８】
次に、構成変更部１１は、点Ｃの値を基準に、ハッシュリング上の各区間の順番を変えないように、各区間を長さＢに伸長する（Ｓ４３）。構成変更部１１は、図３の例において、点Ｃ（値３０）基準に、順次長さＢ（４０）を、時計回りに各区間の始点４２に加算していく。これらの区間の始点４２は、順次、３０+４０＝７０、７０+４０=１１０となる。
【００４９】
この処理は、リング記憶部４０に格納されている表（図２）から、第２行を削除し、残った行の区間の始点４２を書き換えることに相当する。
【００５０】
図４で説明したように、配置先決定部１３は、オブジェクトを配置先装置３０に配置するとき、Ｘ+Ｎ台の配置先装置３０に冗長的に配置する。ここで、Ｎは１以上の値である。この冗長配置は、Ｘ台の配置先装置３０がアクセス不能になった際にも、オブジェクトがそのハッシュ値から特定される第１の配置先に存在することを保証するために行う。配置先装置３０は、障害を発生した時、または、削除されたときアクセス不能になる。ここで、Ｘは障害許容台数と称し、例えば、パラメータとしてオブジェクト配置装置１０に設定される。
【００５１】
或る配置先装置３０がアクセス不能になると、図８及び図９を使って説明したハッシュリングの変更が行われる。このような、ハッシュリングの変更を、以降、縮退変更と称する。配置先決定部１３は、縮退変更がオブジェクトの配置変更する時間なく、連続してＸ回発生しても、オブジェクトが第１の配置先から取得できるようにする為Ｘ＋Ｎ台にオブジェクトを配置する。
【００５２】
縮退が１回だけ発生した場合は、図８及び図９の説明から明らかなように、２台の配置先装置３０にオブジェクトが配置されていれば問題ない。しかし、オブジェクトが３台以上の配置先装置３０に配置され、そのうち２台以上がアクセス不能になって、縮退が連続して発生すると問題が発生しうる。縮退変更時、図８及び図９で説明したような区間のずれが発生するからである。縮退が連続して発生すると、構成変更部１１は、ずれが生じた状態から、縮退変更を行うことになる。
【００５３】
リング記憶部４０に登録されている配置先装置３０の台数をＭとした時、１回目の縮退変更で発生したずれは、区間の長さが１／Ｍから１／（Ｍ−１）に伸長したことにより発生する。
【００５４】
従って、Ｘ回目の縮退前に生じているずれｃは、次式で求めることができる。
2015203797.tif 000003
【００５５】
以降、ｃの整数部をｃ０、小数部をｃ１と称する。
【００５６】
Ｘ箇所の配置先装置３０がアクセス不能になった際にも、オブジェクトがそのハッシュ値から特定される第１の配置先に存在することを保証するためには配置先決定部１３は、Ｎを、ｃ０+１（即ち、ｃの小数点を切り上げた値）にすればよい。
【００５７】
または、配置先決定部１３は、そのハッシュ値が、小数点部分の区間に包含されるオブジェクトだけをＸ＋ｃ０＋１台の配置先装置３０に配置してもよい。即ち、ｃ２＝ｃ１*リングの長さ/Ｍとしたときに、配置先決定部１３は、ハッシュ値の区間の始点からの距離がｃ２未満であるオブジェクトに限りＸ＋ｃ０＋１台の配置先装置３０に配置してもよい。配置先決定部１３は、その他のオブジェクトは、Ｘ＋ｃ０台の配置先装置３０に配置すればよい。この配置の方が、配置先装置３０の記憶域を節約できる。
【００５８】
配置先決定部１３は、このようなｃの計算を以下の手順で行っても良い。
【００５９】
１.１  Ａ＝Ｍ−１、Ｂ＝１、Ｃ＝０とする。
【００６０】
１.２  ＢがＸ−１未満だったらＣにＢ／Ａを足す。
【００６１】
１.３  Ａから１を引き、Ｂに１を加える。
【００６２】
１.４  １．２に戻る。
＜具体例の説明＞
以降、図２、図３のハッシュリングを例に、オブジェクト配置装置１０の動作を説明する。また、障害許容数Ｘは１とする。この場合、前述したように、配置先決定部１３は、オブジェクトを２か所に配置する。
【００６３】
オブジェクトａのハッシュ値が１２だとする。この場合、第１の配置先は区間ａと結びついている配置先装置ａ、第２の配置先は区間ｂと結びついている配置先装置ｂとなる。
【００６４】
配置先装置ａを第１の配置先としたオブジェクトは、必ず配置先装置ｂを第２の配置先とする。そのため、配置先装置ａを第１の配置先とした複数のオブジェクトを、まとめて、第１、第２の配置先の各々に送ることが可能である。これは、配置先装置ｂ、ｃ、ｄを第１の配置先装置３０としたオブジェクトついてもあてはまる。つまり、オブジェクト配置装置１０は、第１の配置先が同じ複数のオブジェクトをまとめて、配置先装置３０に送ることが可能である。
【００６５】
また、各配置先装置３０に結びついている区間の長さは等しく、ハッシュ関数は値域内で一様になるようにハッシュ値を出力する。したがって、オブジェクト配置装置１０は、全ての配置先に一様にオブジェクトを配置する。
【００６６】
ここで、構成変更部１１は、例えば、配置先装置ｅを追加する。オブジェクト配置装置１０は、例えば、配置先装置ａと結びついている区間ａの始点（点Ａ）を基準に配置先装置ｅを追加する。図７が、配置先装置ｅ追加後のハッシュリングであることは、すでに述べた。
【００６７】
ここでオブジェクトは、配置先装置ｅ追加後のハッシュリングで決定される第１の配置先に存在する。以下、具体的に説明する。
【００６８】
配置先装置ｅを追加する前に値０から値２３にあったオブジェクトは、配置先装置ａを第１の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後も配置先装置ａを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００６９】
配置先装置ｅを追加する前に値２４から値３０にあったオブジェクトは、配置先装置ｂを第２の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ｂを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７０】
配置先装置ｅを追加する前に値３０から値４７にあったオブジェクトは、配置先装置ｂを第１の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後も配置先装置ｂを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７１】
配置先装置ｅを追加する前に値４８から値５９にあったオブジェクトは、配置先装置ｃを第２の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ｃを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７２】
配置先装置ｅを追加する前に値６０から値７１にあったオブジェクトは、配置先装置ｃを第１の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ｃを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７３】
配置先装置ｅを追加する前に値７２から値８９にあったオブジェクトは、配置先装置ｄを第２の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ｄを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７４】
配置先装置ｅを追加する前に値９０から値９５にあったオブジェクトは、配置先装置ｄを第１の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ｄを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７５】
配置先装置ｅを追加する前に値９６から値１１９にあったオブジェクトは、配置先装置ａを第２の配置先としていた。そして、それらのオブジェクトは、配置先装置ｅを追加した後は配置先装置ａを第１の配置先としている。（追加した配置先装置３０の区間ｅのオブジェクトは、ハッシュリング上で時計回り見たときに次にある区間の配置先装置３０を第１の配置先とする。）よって、オブジェクトは配置先装置ｅ追加後の第１の配置先に存在する。
【００７６】
このように全てのオブジェクトは、配置先装置ｅ追加後の第１の配置先に存在する。
【００７７】
この状態から、構成変更部１１は、変更後のハッシュリングに合わせて、必要な全てのオブジェクトの配置先を変更する。その後、構成変更部１１が、再度、配置先装置３０を増やした場合も、全てのオブジェクトは、配置先の再追加後も、各オブジェクトの第１の配置先に存在する。
【００７８】
構成変更部１１は、図３のハッシュリングから、例えば、区間ｂと結びついている配置先装置ｂを削除する。図９が、配置先装置ｂ削除後のハッシュリングであることは、すでに述べた。
【００７９】
ここでオブジェクトは、配置先装置ｂ削除後のハッシュリングで決定される第１の配置先に存在する。以下、具体的に説明する。
【００８０】
配置先装置ｂを削除する前に値０から値２９にあったオブジェクトは、配置先装置ａを第１の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後も配置先装置ａを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８１】
配置先装置ｂを削除する前に値３０から値５９にあったオブジェクトは、配置先装置ｃを第２の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後は配置先装置ｃを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８２】
配置先装置ｂを削除する前に値６０から値６９にあったオブジェクトは、配置先装置ｃを第１の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後も配置先装置ｃを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８３】
配置先装置ｂを削除する前に値７０から値８９にあったオブジェクトは、配置先装置ｄを第２の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後は配置先装置ｄを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８４】
配置先装置ｂを削除する前に値９０から値１０９にあったオブジェクトは、配置先装置ｄを第１の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後も配置先装置ｄを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８５】
配置先装置ｂを削除する前に値１１０から値１１９にあったオブジェクトは、配置先装置ａを第２の配置先としていた。そして、それらのオブジェクトは配置先装置ｂを削除した後は配置先装置ａを第１の配置先としている。よって、それらのオブジェクトは配置先装置ｂ削除後の第１の配置先に存在する。
【００８６】
このように全てのオブジェクトは、配置先装置ｂ削除後も第１の配置先に存在する。
【００８７】
以上から明らかなように、本発明にかかるオブジェクト配置装置１０を用いてオブジェクトを配置することによって、以下の効果を発揮することができる。
【００８８】
１．オブジェクト配置装置１０は、オブジェクトを各配置先装置３０に一様に配置できる。その理由は、各区間の長さが均等で、配置先決定部１３がハッシュ値を値域内で一様に発生するからである。
【００８９】
２．オブジェクト配置装置１０は、オブジェクトを配置する場合にオブジェクトをまとめて送ることが可能である。その理由は、第１の配置先が同じオブジェクトは、第２以降の配置先も同じであるからである。配置先決定部１３は、第１の配置先が同じ複数のオブジェクトをまとめて配置先装置３０に送ることができる。
【００９０】
３．配置先装置３０をリング記憶部４０に１つ追加した場合において、オブジェクトは、追加後もオブジェクトの第１の配置先に存在する。したがって、オブジェクト配置装置１０は、オブジェクトに効率よくアクセスできる。その理由は、配置先決定部１３が、オビジェクトを、ハッシュリングの連続した区間に冗長配置するからである。
４．１つのオブジェクトの配置数未満の数の配置先をリング記憶部４０から削除した場合において、オブジェクトは、削除後もオブジェクトの第１の配置先に存在する。したがって、オブジェクト配置装置１０は、オブジェクトに効率よくアクセスできる。その第１の理由は、配置先決定部１３が、オビジェクトを、ハッシュリングの連続した区間に冗長配置するからである。その第２の理由は、配置先決定部１３が、配置先装置３０の削除に備えて、区間のずれを考慮してオブジェクトの配置数を決定するからである。
【００９１】
図１０は、コンピュータを用いて、上述したオブジェクト配置装置１０を実現したときのハードウェア構成を例示的に説明する図である。
【００９２】
このハードウェアは、ＣＰＵ２１、ＲＯＭ２２（Read Only Memory）、ＲＡＭ２３（Random Access Memory）、ＨＤＤ２４（Hard Disk Drive）、通信Ｉ／Ｆ２５（InterFace）を備え、これらの構成がバス２６（通信線）を介して接続された一般的なコンピュータである。
【００９３】
上述したオブジェクト配置装置１０は、図１０に示したハードウェアに、ブロック構成図（図１）或いはフローチャート（図４、図５、図６、図８）の機能あるいは処理を実現可能なコンピュータプログラムを供給することで実現される。当該コンピュータプログラムは、ＲＡＭ２３またはＨＤＤ２４等の記憶デバイスに格納され、ＣＰＵ２１によって読み出され実行される。
【００９４】
当該ハードウェア内へのコンピュータプログラムの供給方法は、一般的な手順を採用することができる。その方法は、例えば、ＣＤ−ＲＯＭ等の各種記録媒体を介して当該装置内にインストールする方法や、インターネット等の通信回線を介して外部よりダウンロードする方法である。そして、このような場合、本発明は、係るコンピュータプログラムのコード或いは記憶媒体によって構成される。
【００９５】
また、上述したオブジェクト配置装置１０は、ブロック構成図或いはフローチャートの機能あるいは処理を実現可能な専用の論理回路、ＲＯＭ２２、ＲＡＭ２３、ＨＤＤ２４によって実現されてもよい。
＜変形例＞
オブジェクトは、輸送機関などにより運搬される、物理的な物であっても良い。この場合、配置先は、配置先装置３０ではなく、例えば、配置先店舗、配置先倉庫である。本変形例において、オブジェクト配置装置１０は、オブジェクトを配置する配置先倉庫を決定して、その決定情報を出力するだけで良い。オブジェクトの送付は、当該決定情報に基づいて、例えば、人手で行っても良い。
【００９６】
また、ハッシュリングは、区間を、小さい順に反時計回りに並べたリングであっても良い。この場合、上述の説明における、“時計回り”及び“反時計回り”という表現は、逆転する。
＜第２の実施の形態＞
図１１は、本実施の形態にかかるオブジェクト配置装置１０の構成図である。オブジェクト配置装置１０は、リング記憶部４０のアクセス部１２と配置先決定部１３とを備える。
【００９７】
リング記憶部４０は、０から所定値までの数値範囲を等間隔に分割して作成されたM（M≧２）個の区間が、小さい順に時計または反時計回りの所定方向に並んでいるリングと、リングのM個の区間とM個の登録された配置先の対応情報とを、記憶する。
【００９８】
配置先決定部１３は、入力されたオブジェクトの固有情報を、リングの何れかの区間に一意にマッピングし、マッピングされた区間および当該区間の所定方向に隣接する区間に対応する配置先に、オブジェクトを配置することを決定する。
【００９９】
１つのオブジェクトの配置数未満の数の配置先をリング記憶部４０から削除した場合において、オブジェクトは、削除後もオブジェクトの第１の配置先に存在する。その理由は、配置先決定部１３が、オビジェクトを、ハッシュリングの連続した区間に冗長配置するからである。
【０１００】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１０１】
１０    オブジェクト配置装置
１１    構成変更部
１２    アクセス部
１３    配置先決定部
２１    ＣＰＵ
２２    ＲＯＭ
２３    ＲＡＭ
２４    ＨＤＤ
２５    通信Ｉ／Ｆ
２６    バス
３０    配置先装置
３１    利用装置
３２    供給装置
３３    端末装置
３４    通信ネットワーク
４０    リング記憶部
４１    配置先定義
４２    区間の始点
５０    オブジェクト配置システム
【図１】
2015203797.tif 000006
【図２】
2015203797.tif 000007
【図３】
2015203797.tif 000008
【図４】
2015203797.tif 000009
【図５】
2015203797.tif 000010
【図６】
2015203797.tif 000011
【図７】
2015203797.tif 000012
【図８】
2015203797.tif 000013
【図９】
2015203797.tif 000014
【図１０】
2015203797.tif 000015
【図１１】
2015203797.tif 000016
【図１２】
2015203797.tif 000017