(57)【要約】  オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更部１０２と、前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定部１０１と、を備え、前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である配置装置。
2016006222.tif 000002
【特許請求の範囲】
【請求項１】
オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、  を備え、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置装置。
【請求項２】
前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する推定手段  をさらに備える請求項１に記載の配置装置。
【請求項３】
前記推定手段は、  前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す  請求項２に記載の配置装置。
【請求項４】
前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置する配置手段をさらに備え、  前記配置手段は、前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  請求項１乃至３のいずれかに記載の配置装置。
【請求項５】
前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記決定手段は、前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記変更手段は、前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する、  請求項１乃至４のいずれかに記載の配置装置。
【請求項６】
前記決定手段は、前記特性値が取りうる値が分布する領域が分割された１つ以上の範囲の各々がいずれかに割り当てられている前記１つ以上の配置先のうち、前記特性値を含む前記範囲に割り当てられている前記配置先を、前記オブジェクトが配置される前記配置先として決定し、  前記変更手段は、前記範囲に割り当てる前記配置先を、さらに、前記配置先の各々について、当該配置先に割り当てられている前記範囲の大きさの合計が、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記範囲を変更する  請求項５に記載の配置装置。
【請求項７】
前記決定手段は、異なる複数の前記オブジェクト情報から導出される前記特性値が、前記領域に、一様又はほぼ一様に分布するように、前記オブジェクトに付与された前記オブジェクト情報に基づいて前記特性値を導出する  請求項５又は６に記載の配置装置。
【請求項８】
前記オブジェクトが配置される前記配置先として決定された前記配置先に、前記オブジェクトを配置する配置手段  をさらに備える請求項１乃至７のいずれかに記載の配置装置。
【請求項９】
前記配置先の各々と、請求項１乃至８のいずれかに記載の配置装置とを含む配置システム。
【請求項１０】
オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更し、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置方法。
【請求項１１】
前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する  請求項１０に記載の配置方法。
【請求項１２】
前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す  請求項１１に記載の配置方法。
【請求項１３】
前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置し、  前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  請求項１０乃至１２のいずれかに記載の配置方法。
【請求項１４】
前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する、  請求項１０乃至１３のいずれかに記載の配置方法。
【請求項１５】
コンピュータを、  オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、  して動作させ、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置プログラムを記憶する記録媒体。
【請求項１６】
コンピュータを、  前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する推定手段と、  して動作させる配置プログラムを記憶する請求項１５に記載の記録媒体。
【請求項１７】
コンピュータを、  前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す前記推定手段と、  して動作させる配置プログラムを記憶する請求項１６に記載の記録媒体。
【請求項１８】
コンピュータを、さらに、  前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置する配置手段として動作させ、  前記配置手段は、前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  配置プログラムを記憶する請求項１５乃至１７のいずれか１項に記載の記録媒体。
【請求項１９】
コンピュータを、  前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する前記決定手段と、  前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する前記変更手段と、  して動作させる配置プログラムを記憶する請求項１５乃至１８のいずれか１項に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、オブジェクトの配置先を決定する技術に関する。
【背景技術】
【０００２】  複数の配置先のいずれかに配置されたオブジェクトを取り出すためには、オブジェクトが配置された配置先を特定する必要がある。オブジェクトが配置される配置先は、例えば、記憶装置、記憶媒体、場所、あるいは物理的な位置などである。例えば、オブジェクトと、そのオブジェクトが配置されている配置先との関連（関連性）を記憶しておくことによって、オブジェクトが配置された配置先を特定することができる。オブジェクトが配置された配置先を高速に特定できない場合、オブジェクトに高速にアクセスすることは難しい。オブジェクトとそのオブジェクトが配置されている配置先との関連をすべて記憶する場合、オブジェクトの数の増加に伴って、オブジェクトと配置先との関連を記憶するのに必要な記憶容量も増加する。膨大な数のオブジェクトが配置される場合、膨大な数の関連を記憶する必要がある。さらに、記憶されている膨大な数の関連を、消失しないよう維持する必要がある。膨大な数の関連を記憶するためには、膨大な数の関連を格納する記憶装置のコストが必要である。記憶されている膨大な数の関連を、消失しないように維持するためには、さらにコストが必要である。【０００３】  オブジェクトとそのオブジェクトの配置先との関係を記憶することなく、オブジェクトが配置される配置先を特定する方法として、例えば、オブジェクトの識別子などに基づき、オブジェクトの配置先を一意に決定する方法がある。【０００４】  そのような技術が使用される装置の例が、例えば、特許文献１において開示されている。特許文献１の装置は、オブジェクトの識別子をシードとして疑似乱数を発生させる。その疑似乱数は、シードに対して一意に定まる。また、その疑似乱数の発生確率は、その疑似乱数の値域において一様である。特許文献１の装置は、値の範囲と配置先との関連が記録される表に基づき、発生した疑似乱数が含まれる値の範囲に関連する配置先を、そのオブジェクトの配置先として決定する。特許文献１の装置は、配置先に関連する値の範囲に含まれる疑似乱数が発生するまで、疑似乱数の発生を繰り返す。【０００５】  特許文献２には、データアイテムを分散配置する分散システムの運用中に、データアイテムの配置先を決定する分散配置アルゴリズムを変更する分散配置装置が記載されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】国際公開第２０１２／０２３３８４号
【特許文献２】国際公開第２０１３／００５８１２号
【発明の概要】
【発明が解決しようとする課題】
【０００７】  特許文献１に記載されている装置は、配置先に、追加などの変更が行われた場合、オブジェクトを再配置する。【０００８】  特許文献２の装置は、分散配置アルゴリズムが変更された場合、データアイテムの配置先を変更する再配置を行う。【０００９】  ところが、配置先に配置されているオブジェクトの数が増大した場合、オブジェクトの再配置に必要な、時間やコストが増大する。【００１０】  本発明の目的の一つは、規則に従って決定される、オブジェクトが配置される配置先が、配置先の追加によって変化する場合における、オブジェクトの配置に係る処理コストを低減できる配置装置等を提供することにある。
【課題を解決するための手段】
【００１１】  本発明の一態様に係る配置装置は、オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、を備え、前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である。【００１２】  本発明の一態様に係る配置方法は、オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更し、前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である。【００１３】  本発明の一態様に係る配置プログラムは、コンピュータを、オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、して動作させ、前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である。本発明は、上述の配置プログラムを記憶する記録媒体によっても実現される。
【発明の効果】
【００１４】  本発明には、規則に従って決定される、オブジェクトが配置される配置先が、配置先の追加によって変化する場合における、オブジェクトの配置に係る処理コストを低減できるという効果がある。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の第１の実施形態に係る配置システム１０の構成を示すブロック図である。
【図２】図２は、第１の実施形態の配置装置１００の、配置先が追加される場合における動作の例を表すフローチャートである。
【図３】図３は、第１の実施形態の配置装置１００の、オブジェクトが配置される配置先を決定する動作の例を表すフローチャートである。
【図４】図４は、第１の実施形態の配置装置１００の、いずれかの配置先に配置されているオブジェクトを取り出す動作を表すフローチャートである。
【図５】図５は、仮想ノードが配置されたハッシュリングの例を模式的に表す第１の図である。
【図６】図６は、仮想ノードが配置されたハッシュリングの例を模式的に表す第２の図である。
【図７】図７は、第１の実施形態の変形例の配置システム１０Ａの構成の例を表すブロック図である。
【図８】図８は、本発明の第２の実施形態の配置装置１００Ｂの構成の例を表すブロック図である。
【図９】図９は、本発明の各実施形態に係る配置装置及び配置実行装置を実現することができる、コンピュータ１０００のハードウェア構成の一例を表す図である。
【発明を実施するための形態】
【００１６】  次に、本発明を模範的に実施する形態について図面を参照して詳細に説明する。なお、以下に説明する実施形態は、請求の範囲に係る発明を限定しない。また実施形態の中で説明されている構成の組み合わせの全てが、発明の構成に必須であるとは限らない。
【００１７】  ＜第１の実施形態＞  まず、本発明の第１の実施形態の配置システム１０について、図面を参照して詳細に説明する。
【００１８】  図１は、本実施形態に係る配置システム１０の構成を示すブロック図である。図１を参照すると、本実施形態の配置システム１０は、配置装置１００と、１つ以上のサーバ（サーバ３０１〜サーバ３０Ｎ）とを含む。サーバ３０１〜サーバ３０Ｎは、図１において、サーバアレイ３００と表記されている。配置装置１００と各サーバとは、互いに通信可能に接続されている。以下の説明において、各サーバは、配置先とも表記される。すなわち、サーバ３０１〜サーバ３０Ｎは、それぞれ、配置先３０１〜配置先３０Ｎとも表記される。配置装置１００は、さらに、指示装置４００と通信可能に接続されている。
【００１９】  各配置先（すなわち、配置先３０１〜配置先３０Ｎの各々）は、例えば、オブジェクトを配置することができる記憶領域を含む。各配置先は、後述される配置要求に応じて、オブジェクトを記憶領域に記憶する。各配置先は、後述される取り出し要求に応じて、記憶領域に格納されているオブジェクトを取り出す。そして、各配置先は、取り出したオブジェクトを取り出し要求の送信元に送る。
【００２０】  オブジェクトは、例えば、ひとまとまりのデータ（データセット）である。オブジェクトには、オブジェクト情報が付与されている。オブジェクト情報は、例えば、オブジェクトの識別子である。オブジェクト情報は、例えば、オブジェクトの例えば性質などを表す属性を含んでいてもよい。オブジェクト情報は、オブジェクトの識別子を含んでいてもよい。オブジェクト情報は、オブジェクトに固有な情報であればよい。
【００２１】  なお、本発明の各実施形態では、同一のオブジェクトとして扱われるオブジェクトには、オブジェクトの中身が更新されても、同一のオブジェクト情報が付与される。また、異なるオブジェクトとして扱われるオブジェクトには、異なるオブジェクト情報が付与される。さらに、１つの配置先に同一のオブジェクトとして扱われるオブジェクトが複数回配置される場合、その配置先に配置されているそのオブジェクトは、最も後に配置されたオブジェクトに置き換えられる。
【００２２】  本実施形態では、配置先は、例えば、配置システム１０の管理者の操作によって、増加し得る。配置先の増加は、例えば、配置先を１つずつ追加することによって行われる。また、配置先の増加は、例えば、最後に追加された配置先の記憶領域を増加させることによっても行われる。最後に追加された配置先以外の配置先の記憶領域は、増加しない。本発明の各実施形態では、「配置先を追加すること」は、配置先の数を増加させること、及び、最後に追加された配置先の配置できるオブジェクトの量を増加させることの少なくともいずれかを表す。配置先の空き容量は、その配置先に新たに配置することができるオブジェクトの量を表す値である。オブジェクトの量は、例えば、オブジェクトのサイズが同じである場合、オブジェクトの数によって表されていてもよい。オブジェクトの量は、オブジェクトのサイズによって表されていてもよい。
【００２３】  指示装置４００は、配置装置１００に、オブジェクトを配置先のいずれかに配置する要求である配置要求を送信する。配置要求は、例えば、あらかじめ定められた信号である。指示装置４００は、例えば、配置要求に加えて、その配置要求によって配置を要求するオブジェクトを、配置装置１００に送信すればよい。指示装置４００は、配置要求として、オブジェクトを、配置装置１００に送信してもよい。すなわち、指示装置４００は、オブジェクトを配置装置１００に送信することによって、そのオブジェクトの配置を要求してもよい。
【００２４】  指示装置４００は、配置装置１００に、さらに、配置先のいずれかに配置されているオブジェクトを取り出す要求である取り出し要求を送信する。取り出し要求は、例えば、あらかじめ定められた信号である。指示装置４００は、例えば、取り出し要求に加えて、その取り出し要求によって取り出しを要求するオブジェクトの識別子及びオブジェクト情報を、配置装置１００に送信すればよい。指示装置４００は、取り出し要求として、取り出しを要求するオブジェクトの識別子及びオブジェクト情報を、配置装置１００に送信してもよい。すなわち、指示装置４００は、オブジェクトの識別子及びオブジェクト情報を送信することによって、そのオブジェクトの取り出しを要求してもよい。さらに、オブジェクト情報がオブジェクトの識別子である場合、指示装置４００は、オブジェクトの識別子を送信することによって、オブジェクトの取り出しを要求すればよい。
【００２５】  配置装置１００は、決定部１０１と、変更部１０２と、配置先情報記憶部１０３と、推定部１０４と、要求処理部１０５と、配置部１０６と、検出部１０７と、取り出し部１０８とを含む。図１に示す例では、配置装置１００に含まれる配置決定部１１０が、決定部１０１と、変更部１０２と、配置先情報記憶部１０３と、推定部１０４とを含む。
【００２６】  要求処理部１０５は、前述の、配置要求と、取り出し要求とを、指示装置４００から受信する。配置要求を受信した場合、要求処理部１０５は、受信したオブジェクトを配置する配置先を決定する指示である配置先決定指示と、受信したオブジェクトのオブジェクト情報とを、配置決定部１１０に送信する。配置決定部１１０に含まれる決定部１０１が、送信された配置先決定指示とオブジェクトのオブジェクト情報とを受信する。決定部１０１は、受信したオブジェクト情報と、配置先決定指示を受信した際の配置先とに対して一意に、配置先を決定する。決定部１０１については、後で詳細に説明する。
【００２７】  配置部１０６は、配置指示によって配置を指示されたオブジェクトを、決定部１０１によって決定された配置先に配置する。配置部１０６は、配置指示と、オブジェクトを配置する配置先の識別子と、配置先に配置するオブジェクトとを、決定部１０１から受け取ればよい。オブジェクトの配置が行われた場合、配置部１０６は、オブジェクトの配置が成功したことを表す応答を、要求処理部１０５を介して、指示装置４００に送信してもよい。
【００２８】  要求処理部１０５が取り出し要求を受信した場合、要求処理部１０５は、配置先推定指示と、受信したオブジェクト情報とを、配置決定部１１０に送信する。配置先推定指示は、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補を推定する指示である。配置決定部１１０に含まれる推定部１０４が、送信された配置先推定指示とオブジェクト情報とを受信する。推定部１０４は、受信したオブジェクト情報と、配置先が追加された順番とに基づいて、そのオブジェクト情報が付与されているオブジェクトが配置されている可能性がある配置先である、配置先の候補を推定する。推定部１０４は、さらに、配置先の候補に含まれる配置先のうち、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先を特定してもよい。推定部１０４は、さらに、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の中で、追加された順番が最も後である配置先を特定してもよい。推定部１０４については、後で詳細に説明する。推定部１０４は、特定した配置先の識別子を、例えば要求処理部１０５を介して、取り出し部１０８に送信してもよい。推定部１０４は、特定された配置先の識別子とオブジェクトの識別子と取り出し要求とを、取り出し部１０８に送信してもよい。推定部１０４は、推定した配置先の候補を表すデータ値を、例えば要求処理部１０５を介して、取り出し部１０８に送信してもよい。取り出し部１０８は、推定された配置先の候補を表すデータ値とオブジェクトの識別子と取り出し要求とを、取り出し部１０８に送信してもよい。
【００２９】  取り出し部１０８は、推定部１０４によって特定された、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の識別子を受信した場合、その配置先にオブジェクトの取り出しを要求すればよい。あるいは、取り出し部１０８は、推定部１０４によって配置先の候補として推定された配置先の各々に対して、オブジェクトの取り出しを要求すればよい。取り出し部１０８は、例えば、配置先の候補として推定された配置先のうち、追加の順番が最も後である配置先から順に、追加の順番に関して降順で、配置先を選択してもよい。そして、取り出し部１０８は、選択された配置先に、取り出しが要求されたオブジェクトの識別子と、その識別子によって特定されるオブジェクトの取り出し要求を送信すればよい。オブジェクトの識別子と取り出し要求とを受信した配置先は、その配置先に、受信した識別子によって特定されるオブジェクトが配置されているか否かを判定すればよい。受信した識別子によって特定されるオブジェクトが配置されている配置先は、そのオブジェクトを取り出し部１０８に送ればよい。受信した識別子によって特定されるオブジェクトが配置されていない配置先は、オブジェクトが配置されていないことを表す応答を、取り出し部１０８に送信すればよい。取り出し部１０８は、配置先からオブジェクトを受け取った場合、そのオブジェクトを、例えば要求処理部１０５を介して、指示装置４００に送ればよい。
【００３０】  取り出し部１０８は、配置先の候補の各々に、オブジェクトの識別子と、オブジェクトの有無を確認する要求とを送信してもよい。その場合、配置先は、受信した識別子によって特定されるオブジェクトが配置されているか否かを確認する処理を行えばよい。そして、配置先は、オブジェクトが配置されているか否かを表す応答を、取り出し部１０８に送信すればよい。取り出し部１０８は、オブジェクトが配置されていることを表す応答を送信した配置先に対して、オブジェクトの識別子と取り出し要求とを送信すればよい。
【００３１】  指示装置４００は、いずれかの配置先にオブジェクトを、その配置先から削除する削除要求を、配置装置１００に送信してもよい。その場合、指示装置４００は、例えば、削除するオブジェクトの識別子とオブジェクト情報と削除要求とを要求処理部１０５に送信する。その場合、要求処理部１０５及び取り出し部１０８は、取り出し要求を受信した場合と同様に動作する。ただし、この場合、配置先に送信される要求は削除要求である。また、識別子によって特定されるオブジェクトは、そのオブジェクトが配置されている配置先によって削除される。
【００３２】  検出部１０７は、配置先として動作するサーバを特定する。そして、検出部１０７は、特定された配置先の各々から、その配置先の空き容量を取得する。検出部１０７は、さらに、配置先の追加を検出する。すなわち、検出部１０７は、配置先の数の増加及び最後に追加された配置先の記憶領域の増加を検出する。検出部１０７は、例えば、新たに追加されたことが検出された配置先の識別子を、配置決定部１１０に含まれる変更部１０２に送信すればよい。検出部１０７は、例えば、新たに追加されたことが検出された配置先の識別子を、各配置先の追加された順番を特定することができるように、配置先情報記憶部１０３に格納してもよい。検出部１０７は、取得した、配置先の各々の空き容量を、変更部１０２に送信する。検出部１０７は、取得した、配置先の各々の空き容量を、配置先情報記憶部１０３に格納してもよい。
【００３３】  次に、配置決定部１１０に含まれる、決定部１０１と、変更部１０２と、配置先情報記憶部１０３と、推定部１０４とについて説明する。
【００３４】  決定部１０１は、例えば、配置先決定指示及びオブジェクト情報を受信するのに応じて、オブジェクトが配置されうる１つ以上の配置先のうち、オブジェクトが配置される配置先を決定する。決定部１０１は、例えば、配置先の各々の空き容量に応じて、上述の１つ以上の配置先の組み合わせと、オブジェクトに付与されているオブジェクト情報とに基づいて、オブジェクトが配置される配置先を一意に決定する規則に従って定まる配置先を選択する。規則は、例えば、そのオブジェクト情報を、前述の一つ以上の配置先のいずれかに結びつける、オブジェクトを使用して行う処理の手順である。決定部１０１は、選択された配置先を、オブジェクトが配置される配置先に決定する。本実施形態では、前述の規則は、異なるオブジェクト情報が付与された複数のオブジェクトの各々を、その規則に従って定まる配置先に配置する場合、各配置先に、その配置先の空き容量に応じた数の配置先が配置されるように、配置先を定める。より具体的には、その規則は、各配置先に、例えば、その配置先の空き容量に比例又はほぼ比例する数の配置先が配置されるように、配置先を定める。後述されるように、例えば配置先が追加されるのに応じて、変更部１０２が、各配置先に、例えば、その配置先の空き容量に比例又はほぼ比例する数の配置先が配置されるように、その規則を変更する。その際、変更部１０２は、さらに、いずれのオブジェクトが配置される配置先も、規則の変更によって、最後に追加された配置先以外の配置先に変化しないように、規則の変更を行う。
【００３５】  次に、決定部１０１による、オブジェクトが配置される配置先の決定について説明する。具体的には、決定部１０１は、まず、オブジェクトに付与されているオブジェクト情報に基づいて一意に定まる値である特性値を算出する。決定部１０１が導出する特性値は、例えば、あり得るさまざまなオブジェクト情報に対して、一様又はほぼ一様に分布する値であればよい。特性値は、例えば、オブジェクト情報のハッシュである。その場合、決定部１０１は、ハッシュを生成させる、所定のハッシュ関数を使用して、オブジェクト情報のハッシュを導出すればよい。特性値は、例えば、オブジェクト情報をシード値として使用することによって導出される疑似乱数の値であってもよい。その場合、決定部１０１は、オブジェクト情報をシード値として使用して、疑似乱数を発生させる、所定の疑似乱数生成関数を初期化すればよい。そして、決定部１０１は、その疑似乱数生成関数を使用して、疑似乱数を発生させればよい。
【００３６】  特性値が取りうる値の集合は、後述されるように、変更部１０２によって、１つ以上の部分集合に分割されている。特性値が取りうる値の集合は、全ての部分集合の和である。いずれの２つの部分集合も重複しない。各部分集合は、いずれかの配置先に、割り当てられている。一つの配置先に複数の部分集合が割り当てられていてもよい。配置先に対する部分集合の割り当ては、配置先に割り当てられる部分集合の大きさの和が、配置先の空き容量の大きさに応じた値であるように、変更部１０２によって決められている。特性値が取りうる値の集合は、例えば、上述のハッシュを発生させるハッシュ関数の値域である。特性値が取りうる値の集合は、例えば、上述の疑似乱数を発生させる疑似乱数生成関数の値域であってもよい。それらの場合、値域が複数の分割された範囲の各々が、上述の部分集合である。２つ以上の範囲が、１つの部分集合であってもよい。
【００３７】  決定部１０１は、導出した特性値が含まれる部分集合を特定する。決定部１０１は、特性値が含まれる部分集合が割り当てられている配置先を、オブジェクトが配置される配置先として決定する。決定部１０１は、決定した配置先の識別子を配置部１０６に送信する。オブジェクトが配置される配置先を決定する上述の規則は、例えば、オブジェクト情報に基づき導出された特性値が含まれる部分集合に関連付けられている配置先を、そのオブジェクト情報が付与されているオブジェクトが配置される配置先に決定することである。その規則は、部分集合と、その部分集合が割り当てられている配置先との組み合わせによって具体的に定まる。本実施形態では、配置先の追加に応じた規則の変更は、例えば、部分集合の分割による新しい部分集合を生成すること、及び、生成された部分集合を追加された配置先に割り当てることによって行われる。
【００３８】  変更部１０２は、配置先が追加されるのに応じて、配置先を決定する規則を変更する。変更部１０２は、検出手段１０７によって配置先の追加が検出されるのに応じて、配置先を決定する規則を変更すればよい。変更部１０２は、その規則に従って決定される、いずれのオブジェクトが配置される配置先も、規則の変更によって、最後に追加された配置先以外の配置先に変化しないように、規則の変更を行う。上述の規則は、具体的には、各配置先への部分集合の割り当てである。規則の変更は、具体的には、例えば、少なくともいずれかの配置先に割り当てられる部分集合の変更である。
【００３９】  以下では、変更部１０２について、さらに詳しく説明する。
【００４０】  配置システム１０が動作を開始したときに配置先が存在しない場合、変更部１０２は、最初に配置先が追加されるのに応じて、追加された配置先の空き容量を、例えば検出部１０７から受信すればよい。変更部１０２は、あらかじめ定められた方法で、部分集合を生成すればよい。変更部１０２は、生成した部分集合の各々を追加された配置先に割り当てればよい。
【００４１】  配置システム１０が動作を開始したときに配置先が存在する場合、配置システム１０が動作を開始すると、変更部１０２は、まず、配置システム１０が動作を開始した時点において存在する配置先の各々の空き容量を、例えば検出部１０７から受信すればよい。変更部１０２は、あらかじめ定められた方法で、部分集合を生成すればよい。変更部１０２は、配置先に割り当てられる部分集合の大きさの和が、その配置先の空き容量に応じた値になるように、生成した部分集合の各々をいずれかの配置先に割り当てればよい。
【００４２】  検出部１０７によって配置先の追加が検出された場合、変更部１０２は、各配置先の空き容量を、例えば検出部１０７から受信する。変更部１０２は、配置先に割り当てられる部分集合の大きさの和が、その配置先の空き容量に応じた値になるように、各配置先に割り当てられている部分集合を変更する。ただし、変更部１０２は、部分集合の割り当て先を、最後に追加された配置先以外の部分集合に変更しない。すなわち、変更部１０２は、各配置先に割り当てられている部分集合を、最後に追加された配置先以外の配置先に割り当てない。例えば、変更部１０２は、最後に追加された配置先以外の配置先に割り当てられている部分集合の少なくともいずれかを、最後に追加された配置先に割り当てることによって、各配置先に割り当てられている部分集合を変更する。変更部１０２は、最後に追加された配置先以外の配置先に割り当てられている部分集合を、さらに分割することによって、部分集合を生成してもよい。変更部１０２は、生成した部分集合を、最後に追加された配置先に割り当ててもよい。変更部１０２は、例えば、オブジェクトがいずれかの配置先に格納されることによって、配置先の空き容量が変化した場合に、以上のように、各配置先に割り当てられている部分集合を変更してもよい。
【００４３】  配置先に部分集合を割り当てた場合、及び、配置先に割り当てられている部分集合を変更した場合、変更部１０２は、各配置先に割り当てられている部分集合を表すデータ値を、配置先情報記憶部１０３に格納する。変更部１０２は、配置先への部分集合の割り当ての履歴を特定できる形で、各配置先に割り当てられている部分集合を表すデータ値を、配置先情報記憶部１０３に格納すればよい。変更部１０２は、例えば、配置先情報記憶部１０３に格納する、各配置先に割り当てられている部分集合を表すデータ値に、最後に追加された配置先の識別子を関連付けてもよい。変更部１０２は、例えば、割り当てを変更した後、最後に追加された配置先の識別子が関連付けられた、各配置先に割り当てられている部分集合を表すデータ値を、配置先情報記憶部１０３に格納してもよい。
【００４４】  前述のように部分集合が値の範囲である場合、変更部１０２は、例えば、各範囲について、前述のデータ値として、範囲の識別子、及び、上限値及び下限値の少なくともいずれかを、配置先情報記憶部１０３に格納すればよい。変更部１０２は、さらに、配置先の各々について、配置先の識別子と、その識別子によって表される配置先に割り当てられている範囲の識別子とを配置先情報記憶部１０３に格納すればよい。なお、複数の範囲が重複しない場合、各範囲を、例えば、下限値のみによって特定することができる。例えば、各範囲の上限値が、その範囲の下限値より大きい、他の範囲の下限値の中で、最小の下限値であると定義することによって、各範囲を下限値によって特定することができる。逆に、各範囲の下限値が、その範囲の上限値より小さい、他の範囲の上限値の中で、最大の上限値であると定義することによって、各範囲を上限値によって特定することができる。
【００４５】  配置先情報記憶部１０３は、各配置先の、追加された順番を特定できる情報を記憶する。配置先情報記憶部１０３は、各配置先の空き容量を記憶していてもよい。配置先情報記憶部１０３は、さらに、各配置先に割り当てられている部分集合を特定する情報を記憶してもよい。
【００４６】  推定部１０４は、例えば、配置先推定指示及びオブジェクト情報を受信するのに応じて、そのオブジェクト情報が付与されたオブジェクトが格納されている可能性がある配置先の候補を特定する。
【００４７】  推定部１０４は、まず、配置先推定指示を受信した際の各配置先と、オブジェクト情報に基づいて算出される特性値とに基づいて、上述の決定部１０１が配置先を決定する方法と同様の方法で、オブジェクトが配置される配置先を特定すればよい。推定部１０４は、特定された配置先を、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補に追加する。例えば、推定部１０４は、特定された配置先の識別子を、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補のリストに追加すればよい。推定部１０４は、決定部１０１に、配置先のリストとオブジェクト情報とを送信してもよい。そして、決定部１０１が、上述のように、オブジェクトが配置される配置先を決定してもよい。そして、推定部１０４は、決定された配置先の識別子を、決定部１０１から受信してもよい。その場合、推定部１０４は、識別子を受信した配置先を、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補に追加する。
【００４８】  さらに、推定部１０４は、配置先の候補に追加した配置先が追加される直前の、各配置先の組み合わせと、受信したオブジェクト情報とに基づいて、オブジェクトが配置される配置先を特定する。推定部１０４は、特定された配置先を、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補に追加する。推定部１０４は、以上の動作を、最初の配置先が、受信したオブジェクト情報が付与されているオブジェクトが配置されている配置先の候補に追加されるまで繰り返す。配置システム１０が動作を開始する際、配置先が存在しない場合、最初の配置先は、例えば、最初に配置システム１０に追加された配置先である。配置システム１０が動作を開始する際、既に配置先が存在する場合、最初の配置先は、例えば、配置システム１０が動作を開始した際に存在していた配置先である。そして、推定部１０４は、配置先の候補を取り出し部１０８に送信する。推定部１０４は、配置先の候補に含まれる各配置先の識別子を送信すればよい。
【００４９】  次に、本実施形態の配置装置１００の動作について、図面を参照して詳細に説明する。
【００５０】  図２は、本実施形態の配置装置１００の、配置先が追加される場合における動作の例を表すフローチャートである。配置装置１００は、例えば定期的に、図２に示す動作を行えばよい。
【００５１】  まず、検出部１０７が、配置先が追加されたか否かを検出する（ステップＳ１０１）。検出部１０７は、動作している配置先を検出すればよい。そして、検出部１０７は、動作している配置先が増加した場合、配置先が追加されたことを検出すればよい。検出部１０７は、追加された配置先の識別子を、例えば、追加された配置先から取得する。検出部１０７は、さらに、各配置先から、空き容量を取得する。その場合、各配置先は、検出部１０７からの、識別子及び空き容量を表す情報を送信する要求に応じて、識別子及び空き容量を表す情報を送信するよう設計されていればよい。本発明の各実施形態の説明において、空き容量を表す情報を、単に、空き容量とも表記する。例えば、「空き容量を取得する」は、空き容量を表す情報を取得することを意味する。検出部１０７は、変更部１０２を介して、配置先情報記憶部１０３に、追加された配置先の識別子を、追加された順番を特定できる形式で格納する。検出部１０７は、変更部１０２を介して、各配置先の空き容量を配置先情報記憶部１０３に格納してもよい。検出部１０７は、最後に追加された配置先に配置できるオブジェクトの量が増加した場合、配置先が追加されたことを検出してもよい。その場合、検出部１０７は、追加された配置先の識別子を配置先情報記憶部１０３に格納しなくてよい。本実施形態では、前述のように、配置先の数は１つずつ増加する。また、最後に追加された配置先の記憶領域は、増加し得る。しかし、配置先の数は減少しない。また、最後に追加された配置先以外の配置先の記憶領域は、増加しない。配置先を追加した管理者が、例えば図示されない端末装置を操作することによって、追加した配置先の識別子を検出部１０７に通知してもよい。
【００５２】  配置先が追加されたことが検出されなかった場合（ステップＳ１０２においてＮｏ）、配置装置１００は、図２に示す動作を終了する。配置先が追加されたことが検出された場合（ステップＳ１０２においてＹｅｓ）、変更部１０２は、各配置先の空き容量に応じて、追加された配置先に割り当てる集合の大きさを算出する（ステップＳ１０３）。変更部１０２は、各配置先に割り当てられている部分集合の少なくとも一部の、導出された大きさの部分集合を、規則に従って選択する（ステップＳ１０４）。変更部１０２は、最後に追加された配置先以外の配置先に割り当てられている部分集合を分割してもよい。そして、変更部１０２は、例えば、分割された部分集合の一方を選択してもよい。変更部１０２は、大きさの和が導出された大きさである複数の部分集合を選択してもよい。変更部１０２は、選択した部分集合を、追加された配置先に割り当てる（ステップＳ１０５）。そして、変更部１０２は、各配置先に対する部分集合の割り当てを表すデータ値を、配置先情報記憶部１０３に格納する。
【００５３】  次に、本実施形態の配置装置１００の、オブジェクトが配置される配置先を決定する動作について、図面を参照して詳細に説明する。
【００５４】  図３は、本実施形態の配置装置１００の、オブジェクトが配置される配置先を決定する動作の例を表すフローチャートである。図３を参照すると、まず、要求処理部１０５が、指示装置４００からオブジェクトと配置指示とを受け取る（ステップＳ２０１）。受信したオブジェクトには、例えばオブジェクトの属性や識別子などのオブジェクト情報が付与されている。指示装置４００は、オブジェクトに加えて、オブジェクト情報を送信すればよい。要求処理部１０５は、オブジェクトに加えて、オブジェクト情報を受信すればよい。決定部１０１は、受け取ったオブジェクトに付与されているオブジェクト情報に基づいてオブジェクトの特性値を導出する（ステップＳ２０２）。前述のように、オブジェクトの特性値は、例えば、オブジェクト情報のハッシュである。オブジェクトの特性値は、例えば、オブジェクト情報をシードとして使用することによって導出された、疑似乱数であってもよい。前述のように、各配置先への部分集合の割り当てを表すデータ値は、配置先情報記憶部１０３に格納されている。決定部１０１は、各配置先に割り当てられている部分集合の中で、導出された特性値が含まれる部分集合が割り当てられている配置先を特定する（ステップＳ２０３）。そして、決定部１０１は、特定された配置先を、オブジェクトが配置される配置先に決定する（ステップＳ２０４）。配置部１０６は、受け取ったオブジェクトを、決定された配置先に配置する（ステップＳ２０５）。
【００５５】  配置先が追加された場合、配置先が追加される前にいずれかの配置先に格納されていたデータの、ステップＳ２０４において決定される配置先が、新しく追加された配置先に変化する場合がある。その場合、例えば配置部１０６が、決定部１０１によって決定される配置先が、配置先の追加によって変化するオブジェクトを、変化後の配置先に移動させてもよい。以下の説明では、本実施形態の配置装置１００は、配置先の追加によって決定される配置先が変化するオブジェクトの移動を行わない。
【００５６】  次に、本実施形態の配置装置１００の、いずれかの配置先に配置されているオブジェクトを取り出す動作について、図面を参照して詳細に説明する。
【００５７】  図４は、本実施形態の配置装置１００の、いずれかの配置先に配置されているオブジェクトを取り出す動作を表すフローチャートである。図４を参照すると、まず、要求処理部１０５が、取り出し要求とオブジェクト情報とを、指示装置４００から受信する（ステップＳ３０１）。次に、推定部１０４は、受信したオブジェクト情報に基づいて、特性値を導出する（ステップＳ３０２）。ステップＳ３０２において導出される特性値は、ステップＳ２０２において導出される特性値と同じ種類の特性値である。次に、推定部１０４は、導出された特性値が含まれる部分集合に含まれている配置先を特定する（ステップＳ３０３）。推定部１０４によるステップＳ３０３における動作は、図３に示す、決定部１０１によるステップＳ２０３における動作と同じである。
【００５８】  特定した配置先が、最初の配置先ではない場合（ステップＳ３０４においてＮｏ）、推定部１０４は、特定した配置先に、対象オブジェクトが配置されているか否かを判定する（ステップＳ３０５）。対象オブジェクトは、受信したオブジェクト情報が付与されているオブジェクトである。推定部１０４は、まず、特定した配置先に、受信したオブジェクトの識別子によって特定される対象オブジェクトが配置されているか否かを問い合わせるアクセスを行えばよい。推定部１０４は、そのアクセスを、例えば、要求処理部１０５や読み出し部１０８を介して行えばよい。そのアクセスが行われるのに応じて、対象オブジェクトが配置されている配置先は、対象オブジェクトが配置されていることを表す応答を、推定部１０４に対して送信すればよい。対象オブジェクトが配置されていない配置先は、そのアクセスに対して、例えばエラーを返せばよい。
【００５９】  特定した配置先に、対象オブジェクトが配置されている場合（ステップＳ３０５においてＹｅｓ）、特定された配置先は、対象オブジェクトが配置されている配置先の中で、最も後に追加された配置先である。その場合、推定部１０４は、取り出し部１０８に、特定した配置先の識別子を送信する。そして、配置装置１００は、ステップＳ３０７以降の動作を行う。
【００６０】  特定した配置先に、対象オブジェクトが配置されていない場合（ステップＳ３０５においてＮｏ）、推定部１０４は、特定された配置先が追加される直前に、各配置先に割り当てられていた部分集合を特定する（ステップＳ３０６）。初期状態は、例えば、オブジェクトが配置される前の状態である。配置装置１００は、ステップＳ３０６の動作の後、ステップＳ３０３からの動作を繰り返す。
【００６１】  特定した配置先が、前述の最初の配置先である場合（ステップＳ３０４においてＹｅｓ）、推定部１０４は、例えば、取り出し部１０８に、特定した配置先の識別子を送信する。そして、配置装置１００はステップＳ３０７以降の動作を行う。
【００６２】  例えば取り出し部１０８が、推定部１０４によって特定された配置先に、受信したオブジェクト情報が付与されたオブジェクトである対象オブジェクトの取り出し要求を送信する（ステップＳ３０７）。対象オブジェクトが配置されている配置先は、対象オブジェクトの取り出し要求に対して、対象オブジェクトを返送する。取り出し部１０８は、対象オブジェクトが配置されている配置先から、対象オブジェクトを受け取る。すなわち、取り出し部１０８は、対象オブジェクトが配置されている配置先から、対象オブジェクトを取り出す（ステップＳ３０８）。取り出し部１０８は、取り出した対象オブジェクトを、指示装置４００に送る。
【００６３】  同じオブジェクト（例えば、同じオブジェクト情報及び識別子が付与されているオブジェクト）が、複数回配置された場合、そのオブジェクトが配置される配置先として決定される配置先は、決定の際に存在する配置先の組み合わせによって異なる可能性がある。すなわち、同じオブジェクトが複数の配置先に配置されている可能性がある。対象オブジェクトが、更新されながら複数回配置された場合、最新の状態のオブジェクトは、そのオブジェクトが配置されている配置先の中で、最も後に追加された配置先に配置されている。そのような場合であっても、上述のステップＳ３０３からステップＳ３０６までの動作の繰り返しによって、推定部１０４は、対象オブジェクトが配置されている配置先の中で、最も遅く追加された配置先を特定することができる。
【００６４】  上述の特許文献１に記載されている装置は、以下の特徴を満たす。
【００６５】  特徴１：オブジェクトが配置される配置先は、そのオブジェクトの識別子を使用して導出される値と、配置先と値の範囲とを関連付ける情報とに基づいて、を一意に決定される。
【００６６】  特徴２：オブジェクトは、すべての配置先に配置される。
【００６７】  特徴３：配置先が追加された場合であっても、オブジェクトはすべての配置先にほぼ一様に配置される。オブジェクトを一様に配置するために、最小限のオブジェクトのみが移動させられる。
【００６８】  本実施形態の配置装置１００は、上述の特徴１及び特徴２を備える。さらに、配置装置１００は、配置先の追加に応じてオブジェクトを移動させなくても、配置されるオブジェクトの数が増えるのに従って、オブジェクトが各配置先にほぼ一様に配置された状態になる。
【００６９】  以上の説明では、オブジェクトはひとまとまりのデータである。しかし、オブジェクトは、例えば物体などであってもよい。その場合、各配置先は、オブジェクトを配置できる場所を備えていればよい。そして、配置部１０６は、オブジェクトを各配置先まで運搬可能な運搬装置であればよい。取り出し部１０８は、オブジェクトを各配置先から運搬可能な運搬装置であればよい。
【００７０】  以上で説明した本実施形態には、規則に従って決定される、オブジェクトが配置される配置先が、配置先の追加によって変化する場合における、オブジェクトの配置に係る処理コストを低減できるという第１の効果がある。
【００７１】  その理由は、変更部１０２が、オブジェクトが配置される配置先を一意に決定する規則を、その規則によって定まる配置先が最後に追加された配置先以外の配置先に変化しないように、各配置先の空き容量に基づいて変更するからである。そして、決定部１０１が、変更部１０２によって変更された規則に従って、オブジェクトの配置先を決定するからである。
【００７２】  配置されたオブジェクトの再配置を行わない場合、オブジェクトを取り出す際、取り出されるオブジェクトが配置されている配置先を特定する必要がある。取り出されるオブジェクトが配置されている配置先の特定は、例えば、オブジェクトが配置されている可能性がある全ての配置先にオブジェクトの有無を確認することによって行われる。本実施形態では、オブジェクトが配置される配置先が、配置先の追加によって、配置先が追加されたときに存在する任意の配置先に変更され得る場合と比較して、オブジェクトが配置される配置先として決定された可能性がある配置先の数が限定される。従って、配置されたオブジェクトの再配置を行わない場合、取り出されるオブジェクトの配置先を特定する処理コストの上昇を低減することができる。すなわち、この場合、本実施形態の配置装置１００は、配置先の追加に応じてオブジェクトを再配置する処理コストを削減するのに加えて、取り出されるオブジェクトの配置先を特定する処理コストの上昇を低減することができる。
【００７３】  また、本実施形態の変更部１０２によって規則が変更されても、各配置先の空き容量に基づいて変更された規則に従って、オブジェクト情報に基づいて定まるオブジェクトの配置先は、新しく追加された配置先以外の配置先に変化しない。すなわち、変更部１０２は、配置先の追加による、オブジェクトの配置先の変化が最小限になるように、上述の規則を変更する。再配置後の各配置先の空き容量が同じであれば、最後に追加された配置先に対してだけオブジェクトが再配置される場合、最後に追加された配置先以外の配置先の間でオブジェクトが再配置される場合と比較して、再配置されるオブジェクトの量は少ない。すなわち、既に配置されているオブジェクトを、配置先の追加に応じて本実施形態の変更部１０２によって変更された規則に従って再配置する場合、最小限のオブジェクトが再配置される。従って、本実施形態の配置装置１００は、オブジェクトの配置先を一意に決定する規則の変更に応じてオブジェクトを再配置する場合、オブジェクトの再配置の処理コストを低減することができる。
【００７４】  本実施形態には、規則に従って決定される、オブジェクトが配置される配置先が、配置先の追加によって変化した際、既に配置されているオブジェクトを再配置しなくても、各配置先にオブジェクトを均等又はほぼ均等に配置できるという第２の効果がある。
【００７５】  その理由は、変更部１０２が、オブジェクトの配置先を一意に決定する規則を、配置先の各々の空き容量に応じて変更するからである。例えば、変更部１０２は、その規則を、配置先の各々に、空き容量に応じた割合でオブジェクトが配置されるように決定するように変更する。そのことにより、既にいずれかの配置先に配置されているオブジェクトを再配置しなくても、配置されるオブジェクトの数が増加するに従って、各配置先に配置されるオブジェクトの数は均等又はほぼ均等になる。
【００７６】  ＜第１の実施形態の実装例＞  次に、第１の実施形態の実装例について、図面を参照して詳細に説明する。本実装例の説明では、決定部１０１、変更部１０２、及び推定部１０４の具体例について説明する。
【００７７】  上述のように、配置先に配置できるオブジェクトの量の上限は、配置先毎に決められている。配置先は追加されるが、削除されない。最後に追加された配置先に配置できるオブジェクトの量は増加され得る。最後の追加された配置先以外の配置先に配置できるオブジェクトの量は、増加しない。
【００７８】  決定部１０１は、パラメータと、オブジェクト情報と、オブジェクトが配置されうる配置先の組み合わせが同一であれば、同一の配置先をオブジェクトの配置先として選択する規則に従うアルゴリズムに基づいて動作する。そのアルゴリズムが従う規則は、例えば、使用されるパラメータを変更することによって変更される。例えば、変更部１０２がパラメータを調整することによって、決定部１０１が従うアルゴリズムにおいて、各配置先に配置されるオブジェクトの数の比を調整することができる。同様に、配置先が追加された場合、変更部１０２がパラメータを調整することによって、上述のアルゴリズムに基づいて定まるオブジェクトの配置先は、少なくともいずれかのオブジェクトについて、変更される。最後に追加された配置先に配置できるオブジェクトの量が増やされた場合、変更部１０２がパラメータを調整することによって、上述のアルゴリズムに基づいて定まるオブジェクトの配置先は、少なくともいずれかのオブジェクトについて、変更される。ただし、いずれの場合も、上述のアルゴリズムに基づいて定まるオブジェクトの配置先は、最後に追加された配置先以外の配置先に変更されない。
【００７９】  決定部１０１が使用するアルゴリズムの例として、例えば、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇ、Ｒａｎｄｏｍ  Ｓｌｉｃｉｎｇ、及びＡＳＵＲＡ等がある。Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇは、例えば、以下に示す参考文献１に記載されている。Ｒａｎｄｏｍ  Ｓｌｉｃｉｎｇは、例えば、以下に示す参考文献２に記載されている。ＡＳＵＲＡは、例えば、上述の特許文献１に記載されている。決定部１０１は、他の同様な特徴を持つアルゴリズムを使用してもよい。
【００８０】  （参考文献１）David Karger et al., “consistent Hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web,” Proceedings of the twenty-ninth annual ACM symposium on Theory of computing.    （参考文献２）Alberto Miranda et al., “Reliable and Randomized Data Distribution Strategies for Large Scale Storage Systems,” Proceedings of the 18th International Conference on High Performance Computing (HiPC), 2011.  このような、決定部１０１によって使用されるアルゴリズムにおけるパラメータは、次のような決まりの下に変更される。
【００８１】  １．変更部１０２は、配置先が追加された際、配置先に新たに配置できるオブジェクトの量に合わせて、各配置先に配置することが期待されるオブジェクトの量の比を調整するように、アルゴリズムのパラメータを変更する。変更部１０２は、追加された配置先に関連するパラメータを変更する。
【００８２】  ２．変更部１０２は、いずれかの配置先に配置可能なオブジェクトの量が増えた場合、配置可能なオブジェクトの量が増えた配置先に関連するパラメータを変更する。
【００８３】  決定部１０１は、以上のようなアルゴリズムを用いて、オブジェクト情報に基づいて配置先を決定する。
【００８４】  推定部１０４は、配置先推定指示とオブジェクト情報とを受信するのに応じて、そのオブジェクト情報が付与されたオブジェクトが配置された配置先の候補を推定する。推定部１０４は、決定部１０１が用いるアルゴリズムと同じ特性を持ったアルゴリズムを、同じ決まりの下に用いて、配置先の候補を推定する。推定部１０４は、配置先が追加されない状態から、最後に追加された配置先が追加された状態までの全ての状態において、オブジェクトの配置先として決定され得る全ての配置先を、配置先候補として特定する。その際、推定部１０４は、例えば、まず、最後に追加された配置先が追加された状態までの全ての状態において、オブジェクトの配置先として決定される配置先を特定する。推定部１０４は、特定した配置先を配置先の候補に追加する。
【００８５】  次に、推定部１０４は、例えば、最後に追加された配置先が追加される前の状態における、オブジェクトの配置先として決定される配置先を特定してもよい。推定部１０４は、追加された時期が新しい順に、順次、追加された配置先が追加される前の状態における、オブジェクトの配置先として決定される配置先を特定してもよい。推定部１０４は、特定した配置先が配置先の候補に含まれない場合、特定した配置先を配置先の候補に追加する。推定部１０４は、配置先が追加されてない状態における、オブジェクトの配置先として決定される配置先が特定されるまで、以上の配置先の特定を繰り返せばよい。
【００８６】  推定部１０４は、例えば、最後に追加された配置先ではなく、特定された配置先が追加される前の状態における、オブジェクトの配置先として決定される配置先を特定してもよい。推定部１０４は、特定された配置先が追加される前の状態における、オブジェクトの配置先として決定される配置先の特定を繰り返せばよい。推定部１０４は、特定した配置先を配置先の候補に追加する。この場合も、推定部１０４は、配置先が追加されてない状態における、オブジェクトの配置先として決定される配置先が特定されるまで、以上の配置先の特定を繰り返せばよい。
【００８７】  以上のように配置先の候補を推定することによって、推定部１０４が配置先推定指示を受信するまでに、オブジェクトの配置先として決定された可能性がある全ての配置先を選ぶことができる。ほとんどの場合、推定部１０４は、配置先推定指示を受信した際の全ての配置先の一部を、配置先の候補として特定する。
【００８８】  以下では、決定部１０１が、配置先を決定するアルゴリズムとして、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇを用いる例について説明する。以下の説明では、配置先に配置可能なオブジェクトの量は、全ての配置先において同じである。各配置先に配置可能なオブジェクトの量は、Ｘ個である。前述の最初の配置先の数は、１つである。配置先は、順次、３カ所まで増やされる。
【００８９】  Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇでは、ハッシュ関数の値域がマッピングされたハッシュリングと呼ばれる仮想的なリングが用いられる。ハッシュ関数の全ての出力値は、例えば、小さい方から順に、時計回りに、リングの１点に割り当てられる。そして、ハッシュ関数の出力の最小値及び最大値は、リング上で隣接する２点に割り当てられる。
【００９０】  最初の配置先を、「配置先Ａ」と表記する。前述のように、最初の配置先は、最初に追加された配置先である。最初の配置先は、オブジェクトが配置される前の初期状態において存在する配置先であってもよい。変更部１０２は、配置先が追加されるのに応じて、ハッシュリング上に、追加された配置先に関連付けられたヴァーチャルノードを配置する。以下の説明において、ヴァーチャルノードは、「仮想ノード」とも表記される。変更部１０２は、配置先Ａが追加されるのに応じて、配置先Ａに関連付けられた、所定個数のヴァーチャルノードを、ハッシュリング上に配置する。配置システム１０の動作開始時に配置先Ａが配置先として存在する場合、変更部１０２は、配置システム１０が動作を開始するのに応じて、配置先Ａに関連付けられた、所定個数のヴァーチャルノードを、ハッシュリング上に配置すればよい。変更部１０２は、ヴァーチャルノードが配置される位置を、以下のように、所定のハッシュ関数によって決定すればよい。変更部１０２は、例えば、まず、カウンタをリセットする。そして、変更部１０２は、例えば、配置先の識別子と、カウンタの値とに基づき、ハッシュ関数によってハッシュを計算すればよい。変更部１０２は、計算したハッシュが割り当てられている位置に、配置先Ａに関連付けられたヴァーチャルノードを配置する。変更部１０２は、あらかじめ決めた数の、配置先Ａに関連付けられたヴァーチャルノードを配置するまで、カウンタを所定値ずつ増加させながら、ハッシュの計算とヴァーチャルノードの配置とを繰り返せばよい。例えば、最初の配置先に関連付けられるヴァーチャルノードの数が１００個である場合、変更部１０２は、配置先の識別子と順次増加させられるカウンタの値とに基づき、１００個のハッシュを計算する。変更部１０２は、ハッシュリング上の、計算した１００個のハッシュの各々が割り当てられている位置に、配置先Ａに関連付けられたヴァーチャルノードを配置する。なお、最初の配置先に関連付けられるヴァーチャルノードの数は、例えば数百など、他の値であってもよい。
【００９１】  ハッシュリングは、ヴァーチャルノードが配置された位置において、仮想的に分割される。そして、分割されたそれぞれの区間は、例えば、その区間の起点に配置されているヴァーチャルノードに割り当てられる。区間の起点は、例えば、時計回りでその区間の最初の点である。以下の説明において、ハッシュリングが分割された区間を、「範囲」とも表記する。
【００９２】  図５は、仮想ノードが配置されたハッシュリングの例を模式的に表す第１の図である。図５に示す例では、６つの仮想ノードが配置されている。そして、ハッシュリングは、６つの仮想ノードが配置されている点によって、範囲１から範囲６までの６つの区間に分割されている。そして、例えば、範囲１によって表される区間が、仮想ノード１に割り当てられる。図５において、ハッシュ関数の値域の下限値は、「０」によって表される点に割り当てられている。「０」によって表される点を含む区間である範囲６は、仮想ノード６に割り当てられる。
【００９３】  決定部１０１は、変更部１０２によってヴァーチャルノードが配置されたハッシュリングを使用して、例えば以下のように、オブジェクトの配置先を決定する。決定部１０１は、配置先を決定するオブジェクトに付与されているオブジェクト情報のハッシュを計算する。計算されるハッシュが、上述の特性値である。決定部１０１は、ハッシュリング上で、計算したハッシュが割り当てられている位置が、ハッシュリング上のどの区間に含まれるかを特定する。決定部１０１は、計算したハッシュが割り当てられている位置が含まれる区間が割り当てられているヴァーチャルノードを特定する。決定部１０１は、特定したヴァーチャルノードに関連付けられている配置先を、そのオブジェクトが配置される配置先として決定する。
【００９４】  図５に示す例で、オブジェクト情報のハッシュが「Ｘ」によって示される点に割り当てられている場合、その点は、範囲２に含まれる。範囲２が割り当てられているヴァーチャルノードは「仮想ノード２」である。この場合、決定部１０１は、オブジェクトが配置される配置先を、「仮想ノード２」に関連付けられている配置先に決定する。
【００９５】  他の配置先が追加されるまで、配置先Ａのみが配置先として存在する。従って、ハッシュリング上に配置されている全てのヴァーチャルノードに配置先Ａが関連付けられている。従って、配置先Ａ以外の配置先が存在しない状態では、決定部１０１は、常に、配置先Ａを、オブジェクトが配置される配置先に決定する。そして、配置先Ａ以外の配置先が存在しない状態では、上述の配置部１０６は、オブジェクトを常に配置先Ａに配置する。
【００９６】  推定部１０４は、同様に、オブジェクトが配置されている配置先の候補として、配置先Ａのみを推定する。配置先Ａ以外の配置先が存在しない状態では、上述の取り出し部１０８は、取り出し要求に応じて、常に配置先Ａからオブジェクトを取り出す。
【００９７】  配置先として配置先Ａのみが存在する状態では、決定部１０１は、配置先Ａを、オブジェクトが配置される配置先に決定する。
【００９８】  また、この場合、推定部１０４は、オブジェクトが配置されている配置先の候補には、配置先Ａのみが含まれる。
【００９９】  配置先Ｂが追加された場合、検出部１０７は、配置先Ｂが追加されたことを検出する。
【０１００】  配置先Ｂが追加されるのに応じて、変更部１０２は、以下のように、配置先の各々について、空き容量に応じた数のヴァーチャルノードが配置されるように、配置先Ｂに関連付けられたヴァーチャルノードの数を導出する。変更部１０２は、導出された数の、配置先Ｂに関連付けられたヴァーチャルノードを、ハッシュリング上に配置する。変更部１０２は、配置先Ｂに関連付けられたヴァーチャルノードをハッシュリング上に新たに配置することによって、新たに配置されたヴァーチャルノードの数の区間を生成する。変更部１０２は、配置Ａに関連付けられているヴァーチャルノードに割り当てられている区間を、新たにヴァーチャルノードが配置された場所で分割することによって、それらの区間を生成する。
【０１０１】  図６は、仮想ノードが配置されたハッシュリングの例を模式的に表す第２の図である。図６に示す例では、図５に示すハッシュリングに、仮想ノード７及び仮想ノード８が追加されている。図６に示す例では、仮想ノード２と仮想ノード３との間に仮想ノード７が追加されている。さらに、仮想ノード３と仮想ノード４との間に仮想ノード８が追加されている。仮想ノード７の追加によって、図５における範囲２は、図６に示す例では、仮想ノード７が配置された位置において、範囲２Ｂ及び範囲７に分割されている。仮想ノード８の追加によって、図５における範囲３は、図６に示す例では、仮想ノード８が配置された位置において、範囲３Ｂ及び範囲８に分割されている。図６に示すように、仮想ノードに追加によって、既に配置されている仮想ノードに割り当てられている区間が分割される。そして、分割によって生成された区間のうちの一方は、分割された区間が割り当てられていた仮想ノードに引き続き割り当てられる。そして、分割によって生成された区間のうちの他方は、追加された仮想ノードに割り当てられる。
【０１０２】  配置先Ｂが追加された際、配置先ＡにすでにＹ個のオブジェクトが配置されていれば、各配置先にＸ個のオブジェクトを配置できるので、配置先Ａに新たに配置できるオブジェクトの量は、（Ｘ−Ｙ）個である。変更部１０２は、配置先Ａに関連付けられたヴァーチャルノードの数にＸ／（Ｘ−Ｙ）をかけた数の、配置先Ｂに関連付けられたヴァーチャルノードを、ハッシュリング上に配置する。前述の「／」は、割り算を表す演算子である。変更部１０２は、上述のように、例えば、配置先Ｂの識別子及びカウンタのハッシュが割り当てられている位置に、配置先Ｂに関連付けられたヴァーチャルノードを配置すればよい。このことによって、配置先Ａ及び配置先Ｂに新たに配置されるオブジェクトの数の比は、配置先Ａ及び配置先Ｂの空き容量の比に近づくことが期待できる。各配置先に空き容量の比に応じた数のオブジェクトが配置されると、各配置先の空き容量は、ほぼ同時に尽きることが期待される。すなわち、各配置先にほぼ均等にオブジェクトが配置されることが期待される。
【０１０３】  なお、配置先の追加が、配置先Ｂの容量の追加である場合、配置先Ｂに関連付けられているヴァーチャルノードが、ハッシュリングに配置されている。また、配置先Ｂに配置されているオブジェクトが存在する可能性がある。容量の追加によって配置先Ｂに配置できるオブジェクトの量がＸ個になり、配置先Ｂに配置されているオブジェクトの量がＹ１個である場合、配置先Ｂに新たに配置できるオブジェクトの量は、（Ｘ−Ｙ１）個である。その場合、変更部１０２は、配置先Ａに関連付けられたヴァーチャルノードの数に（Ｘ−Ｙ１）／（Ｘ−Ｙ）をかけた数の、配置先Ｂに関連付けられたヴァーチャルノードを配置されるように、配置先Ｂに関連付けられたヴァーチャルノードを追加すればよい。
【０１０４】  そして、決定部１０１は、配置先決定指示を受信するのに応じて、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、オブジェクトの配置先を決定すればよい。本発明の各実施形態において、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従ったオブジェクトの配置先の決定方法は、以下の通りである。すなわち、決定部１０１は、配置されるオブジェクトに付与されているオブジェクト情報のハッシュを算出する。決定部１０１は、ハッシュリング上で、算出されたハッシュが割り当てられる点が含まれる区間を特定する。決定部１０１は、特定された区間が割り当てられているヴァーチャルノードを特定する。決定部１０１は、特定されたヴァーチャルノードに関連付けられている配置先を、前述のオブジェクトが配置される配置先に決定する。
【０１０５】  また、推定部１０４は、配置先推定指示を受信するのに応じて、まず、上述のＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、オブジェクトが配置されている配置先を特定する。すなわち、推定部１０４は、配置されるオブジェクトに付与されているオブジェクト情報のハッシュを算出する。推定部１０４は、ハッシュリング上で、算出されたハッシュが割り当てられる点が含まれる区間を特定する。推定部１０４は、特定された区間が割り当てられているヴァーチャルノードを特定する。推定部１０４は、特定されたヴァーチャルノードに関連付けられている配置先を、前述のオブジェクトが配置される配置先に決定する。推定部１０４は、特定した配置先を、配置先の候補に追加する。特定した配置先が、最初の配置先より後に追加された配置先である場合、推定部１０４は、次の処理を行う。すなわち、推定部１０４は、特定した配置先及び特定した配置先より後に追加された配置先の各々に関連付けられているヴァーチャルノードが、最新のハッシュリングから除かれたハッシュリングを生成する。以下の説明において、特定した配置先及び特定した配置先より後に追加された配置先を、「除外配置先」とも表記する。推定部１０４は、生成したハッシュリングを使用して、再び、同様にＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇの方法に従って、オブジェクトが配置されている配置先を特定する。推定部１０４は、前述の除外配置先に関連付けられているヴァーチャルノードが除かれたハッシュリングを生成する代わりに、除外配置先に関連付けられているヴァーチャルノードを無視しながら、オブジェクトが配置されている配置先を特定してもよい。推定部１０４は、特定された配置先を、配置先の候補に追加する。特定した配置先が、最初の配置先である場合、推定部１０４は、配置先の特定を終了する。
【０１０６】  上述の例では、推定部１０４は、配置先Ａ又は配置先Ｂを、オブジェクトが配置されている配置先として特定する。最初の配置先は、配置先Ａである。推定部１０４は、特定された配置先が配置先Ａである場合、配置先Ａを配置先の候補に追加する。そして、推定部１０４は、配置先の特定を終了する。
【０１０７】  特定した配置先が配置先Ｂである場合、推定部１０４は、配置先Ｂを配置先の候補に追加する。そして、推定部１０４は、配置先Ｂに関連付けられたヴァーチャルノードが除かれたハッシュリングを生成する。そして、推定部１０４は、生成したハッシュリングを使用して、再び、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇの方法に従って、オブジェクトが配置されている配置先を特定する。この場合、生成されたハッシュリングには、配置先Ａに関連付けられたヴァーチャルノードしか存在しない。従って、この場合、推定部１０４は、オブジェクトが配置されている配置先として、配置先Ａを特定する。そして、推定部１０４は、配置先Ａを配置先の候補に追加する。
【０１０８】  以上のように配置先の候補が推定されることによって、オブジェクトが配置先Ａに配置されている場合、配置先Ａは配置先の候補に含まれる。オブジェクトが配置先Ｂに配置されている場合、配置先Ｂは、配置先の候補に含まれる。
【０１０９】  そして、さらに配置先Ｃが追加された場合、検出部１０７は、配置先Ｃが追加されたことを検出する。
【０１１０】  変更部１０２は、配置先Ｃが追加されるのに応じて、ハッシュリング上に、さらに、配置先Ｃに関連付けられたヴァーチャルノードを配置する。
【０１１１】  配置先Ｃが追加された際、配置先ＡにＺ０個のオブジェクトが配置されている場合、配置先Ａに新たに配置できるオブジェクトの数は、（Ｘ−Ｚ０）である。変更部１０２は、配置先Ａに関連付けられているヴァーチャルノードの数にＸ／（Ｘ−Ｚ０）をかけた数の、配置先Ｃに関連付けられたヴァーチャルノードを、ハッシュリングに配置すればよい。変更部１０２は、例えば、上述のように、配置先Ｃの識別子及びカウンタにハッシュが割り当てられている位置に、配置先Ｃに関連付けられているヴァーチャルノードを配置すればよい。このことにより、上述のように、各配置先にほぼ均等にオブジェクトが配置されることが期待できる。
【０１１２】  また、例えば、配置先Ｃが追加された際、配置先ＢにＺ１個のオブジェクトが配置されている場合、配置先Ｂに新たに配置できるオブジェクトの数は、（Ｘ−Ｚ１）である。変更部１０２は、ハッシュリングに配置されている、配置先Ｂに関連付けられたヴァーチャルノードの数に対する、配置先Ｂのヴァーチャルノードの数にＸ／（Ｘ−Ｚ１）をかけた数の増加数を算出すればよい。そして、変更部１０２は、算出された増加数の、配置先Ｂに関連付けられたヴァーチャルノードを、ハッシュリングに追加すればよい。
【０１１３】  Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇの性質と配置先Ａと配置先Ｂのヴァーチャルノードの数によって、配置先Ａのヴァーチャルノードの数にＸ／（Ｘ−Ｚ０）をかけた数と配置先Ｂのヴァーチャルノードの数にＸ／（Ｘ−Ｚ１）をかけた数はほぼ同一になる。そのため、変更部１０２は、配置先Ｃのヴァーチャルノードの数を計算するために、配置先Ａ及び配置先Ｂのどちらのヴァーチャルノードの数を使用してもよい。
【０１１４】  決定部１０１は、上述のＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、オブジェクトの配置先を決定する。
【０１１５】  推定部１０４は、配置先推定指示を受信するのに応じて、まず、上述のように、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、配置先推定指示を受信した際の配置先が全て存在する状態において、オブジェクトが配置される配置先を特定する。特定された配置先が、最初の配置先（すなわち、上述の例では配置先Ａ）でない場合、推定部１０４は、特定された配置先が追加される直前のハッシュリングを生成する。すなわち、推定部１０４は、特定された配置先及びその配置先より後に追加された配置先に関連付けられているヴァーチャルノードが、最新のハッシュリングから除かれたハッシュリングを生成する。推定部１０４は、生成されたハッシュリングを使用して、上述のＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、特定された配置先が追加される直前の状態で、上述のオブジェクトが配置される配置先を特定する。
【０１１６】  例えば、配置先推定指示を受信した際の配置先において、オブジェクトが配置されている配置先として、配置先Ｂが特定された場合、推定部１０４は、配置先Ｂを配置先の候補に追加する。そして、推定部１０４は、配置先Ｂ及び配置先Ｃに関連付けられているヴァーチャルノードが除かれたハッシュリングを生成する。推定部１０４は、生成したハッシュリングを使用して、再度、上述のＣｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、オブジェクトが配置される配置先を特定する。この例では、配置先Ｂ及び配置先Ｃに関連付けられているヴァーチャルノードが除かれたハッシュリングには、配置先Ａに関連付けられているヴァーチャルノードのみが存在する。従って、この場合、推定部１０４は、オブジェクトが配置される配置先として、必ず配置先Ａを特定する。そして、推定部１０４は、配置先Ａを配置先の候補に追加する。配置先Ａは最初の配置先であるので、推定部１０４は、配置先の候補の特定を終了する。
【０１１７】  以上のように配置先の候補が推定されることによって、オブジェクトが配置先Ａに配置されている場合、配置先Ａは配置先の候補に含まれる。オブジェクトが配置先Ｂに配置されている場合、配置先Ｂは配置先の候補に含まれる。オブジェクトが配置先Ｃに配置されている場合、配置先Ｃは配置先の候補に含まれる。
【０１１８】  ハッシュリング上に配置先Ａに関連付けられているヴァーチャルノードのみが配置されている場合、決定部１０１は、ハッシュリングを使用した判定の処理を行わなくてよい。この場合、決定部１０１は、オブジェクトが配置される配置先を、判定の処理を行うことなく、配置先Ａに決定すればよい。同様に、この場合、推定部１０４は、配置先の候補を推定する処理を行うことなく、配置先Ａが、オブジェクトが配置されている配置先の候補であると推定すればよい。
【０１１９】  以上では、配置先の追加によって配置先が３つに増加する場合の、オブジェクトを配置する配置先の決定方法及びオブジェクトが配置されている配置先の推定方法について説明した。一般的には、例えば、推定部１０４は、次のような手順で、オブジェクトが配置されている配置先の候補を推定することができる。
【０１２０】  ステップ１  存在する全ての配置先に関連付けられているヴァーチャルノードが配置されたハッシュリングを生成する。
【０１２１】  ステップ２  生成されたハッシュリングを使用して、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく方法に従って、オブジェクトが配置されている配置先を特定する。
【０１２２】  ステップ３  特定した配置先を、オブジェクトが配置されている配置先の候補に追加する。
【０１２３】  ステップ４  特定した配置先が最初の配置先である場合、動作を終了する。
【０１２４】  ステップ５  特定した配置先及び特定した配置先より後に追加された配置先に関連付けられているヴァーチャルノードが除かれたハッシュリングを生成する。
【０１２５】  ステップ６  ステップ２に戻る。
【０１２６】  ステップ２において、配置先Ａに対関連付けられているヴァーチャルノードのみがハッシュリングに配置されている場合、推定部１０４は、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇに基づく判定の処理を行わずに、配置先Ａを配置先の候補に追加してもよい。
【０１２７】  また、ステップ５は、存在する全ての配置先に関連付けられているヴァーチャルノードが配置されたハッシュリングから、除外配置先に関連付けられているヴァーチャルノードが除外されたハッシュリングを生成する動作である。前述のように、除外配置先は、オブジェクトが配置されている配置先として特定された配置先及び特定された配置先より後に追加された配置先を表す。前述のように、推定部１０４は、ステップ５の、除外配置先に関連付けられているヴァーチャルノードが除外されたハッシュリングを生成する動作を行わなくてもよい。その場合、ステップ２において、除外配置先に関連付けられているヴァーチャルノードを存在しないと見なして、配置先を特定すればよい。
【０１２８】  オブジェクトは、推定部１０４によって推定された配置先の候補に含まれる配置先のいずれかに配置されている。また、推定された配置先の候補に含まれる配置先の数は、多くの場合で存在する全ての配置先の数よりも少ない。取り出し部１０８は、オブジェクトの取り出しのたびに、全ての配置先に対して、取り出されるオブジェクトの有無を確認する必要はない。オブジェクトの取り出しを行う取り出し部１０８は、配置先の候補に含まれる配置先だけに対して、取り出されるオブジェクトの有無を確認するアクセスを行えばよい。オブジェクトの有無を確認するアクセスが行われた配置先は、そのオブジェクトを保持しているか否かを判定する処理を実行する。
【０１２９】  以上のように配置先の候補を推定する場合、使用され始めた時期の早い配置先ほど、配置先の候補に含まれる可能性が高い。例えば、最初の配置先は、以上のように推定された配置先の候補に必ず含まれる。取り出し部１０８が、取り出されるオブジェクトの有無を確認するアクセスを、配置先の候補に含まれる全ての配置先に行う場合、使用され始めた時期の早い配置先ほど、オブジェクトの有無を確認するアクセスが行われる頻度が高い。取り出し部１０８は、例えば、最初の配置先に対して、オブジェクトの取り出しを行う度に、オブジェクトの有無を確認するアクセスを行う。そのような場合、オブジェクトの有無を確認するアクセスの数に応じて、アクセスされる配置先における、オブジェクトを保持しているか否かを判定する処理の負荷が増加する。各配置先は、ブルームフィルタを用いることによって、オブジェクトを保持しているか否かを判定する処理の負荷を軽減してもよい。各配置先は、ブルームフィルタを使用して、例えば、配置されているオブジェクトの識別子を記憶すればよい。そして、配置先は、オブジェクトの有無を確認するアクセスが行われた際、ブルームフィルタを使用して、そのオブジェクトが配置されている可能性があるか否かを判定すればよい。判定の結果、オブジェクトが配置されている可能性がある場合、配置先は、そのオブジェクトが配置されているか否かを判定する、実際に処理を行えばよい。ブルームフィルタを使用してオブジェクトが配置されている可能性があるか否かを判定する処理の負荷より、オブジェクトの有無を確認する処理負荷が高い場合、ブルームフィルタを用いることによって、配置先の負荷を軽減できる。
【０１３０】  また、配置先の候補に複数の配置先が含まれる場合、配置装置１００から配置先への多数のアクセスが発生することによって、オブジェクトへのアクセス速度が遅くなる可能性がある。アクセス数の増加によるアクセス速度の減少を防ぐために、取り出し部１０８は、例えば、配置先の候補に含まれる配置先の数が所定数より大きい場合、アクセスされる頻度が高い配置先への複数のアクセスをまとめてもよい。取り出し部１０８は、複数のアクセスをまとめることによって、アクセスの回数を減少させることができる。それにより、取り出し部１０８は、アクセス数の増加によるアクセス速度の減少を防ぐことができる。取り出し部１０８は、例えば、あらかじめ実験的に特定した、アクセス頻度が高い配置先へのアクセスを、すぐに実行せずに、バッファすればよい。取り出し部１０８は、例えば、時間、時刻、アクセス数、又はそれらの組み合わせなどに対する条件が満たされた場合、バッファされているアクセスを、まとめて送ればよい。これにより、頻繁にアクセスされる配置先へのアクセスの数を減らすことができる。配置先の候補に含まれる配置先の数が所定数より少ない場合、取り出し部１０８は、アクセスされる頻度が高い配置先へのアクセスであっても、すぐにアクセスを行えばよい。その場合、アクセスをバッファすることによる、オブジェクトへのアクセス速度の低下を防ぐことができる。
【０１３１】  ＜第１の実施形態の変形例＞  図７は、第１の実施形態の変形例の配置システム１０Ａの構成の例を表すブロック図である。配置システム１０Ａは、配置装置１００Ａと、配置実行装置２００と、サーバアレイ３００とを含む。配置実行装置２００は、配置装置１００Ａ、サーバアレイ３００に含まれる各配置先、及び、指示装置４００が、それぞれ通信可能に接続されている。サーバアレイ３００及び指示装置４００は、それぞれ、第１の実施形態のサーバアレイ３００及び指示装置４００と同じである。配置装置１００Ａの各構成要素は、第１の実施形態の配置装置１００の、配置決定部１１０に含まれる、同一の符号が付与された構成要素と同じである。配置実行装置２００の各構成要素は、第１の実施形態の配置装置１００の同一の符号が付与された構成要素と同じである。ただし、配置部１０６は、オブジェクトを配置する指示である配置指示と、オブジェクトを配置する配置先の識別子と、配置先に配置するオブジェクトとを、要求処理部１０５から受け取ればよい。決定部１０１は、決定した配置先の識別子を、例えば要求処理部１０５を介して、配置部１０６に送信する。推定部１０４は、配置先の候補を、例えば要求処理部１０５を介して、取り出し部１０８に送信する。推定部１０４は、例えば、要求処理部１０５を介して、取り出し部１０８に、特定した配置先の識別子を送信する。オブジェクトは、配置装置１００Ａに含まれる決定部１０１や推定部１０４を介して送られない。オブジェクトは、要求処理部１０５と、配置部１０６又は取り出し部１０８との間で送られる。本変形例の配置システム１０Ａは、第１の実施形態の配置システム１０と同じ動作を行う。
【０１３２】  ＜第２の実施形態＞  次に、本発明の第２の実施形態について、図面を参照して詳細に説明する。
【０１３３】  図８は、本実施形態の配置装置１００Ｂの構成の例を表すブロック図である。
【０１３４】  図８を参照すると、本実施形態の配置装置１００Ｂは、変更部１０２と、決定部１０１と、を備える。変更部１０２は、オブジェクトに付与されたオブジェクト情報に基づいて、オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、配置先の増加が行われるのに応じて、変更する。その際、変更部１０２は、その規則を、その規則に従ってオブジェクト情報に基づいて定まる配置先が、最後に追加された配置先以外の配置先に変化しないように、空き容量に基づいて変更する。その空き容量は、配置先の各々に新たに配置できるオブジェクトの量を表す。決定部１０１は、オブジェクト情報を受信するのに応じて、規則に従って、オブジェクト情報に基づいて定まる配置先を、オブジェクト情報が付与されているオブジェクトが配置される配置先として決定する。配置先の増加は、新しい配置先の追加、又は、最後に追加された配置先の新たに配置できるオブジェクトの量である空き容量の増加である。
【０１３５】  図８に示す例では、決定部１０１及び変更部１０２が、配置決定部１１０Ｂと表記されている。配置決定部１１０Ｂは、図７に示す配置装置１００Ａのように、配置実行装置２００に通信可能に接続された装置であってもよい。
【０１３６】  以上で説明した本実施形態には、第１の実施形態の第１の効果がある。その理由は、第１の実施形態の第１の効果が生じる理由と同じである。
【０１３７】  ＜他の実施形態＞  配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、及び配置実行装置２００は、それぞれ、コンピュータ及びコンピュータを制御するプログラム、又は、専用のハードウェアにより実現することができる。配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、及び配置実行装置２００は、コンピュータ及びコンピュータを制御するプログラムと、専用のハードウェアとの組合せにより実現することもできる。
【０１３８】  図９は、配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、及び配置実行装置２００を実現することができる、コンピュータ１０００のハードウェア構成の一例を表す図である。図９を参照すると、コンピュータ１０００は、プロセッサ１００１と、メモリ１００２と、記憶装置１００３と、Ｉ／Ｏ（Ｉｎｐｕｔ／Ｏｕｔｐｕｔ）インタフェース１００４とを含む。また、コンピュータ１０００は、記録媒体１００５にアクセスすることができる。メモリ１００２と記憶装置１００３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ハードディスクなどの記憶装置である。記録媒体１００５は、例えば、ＲＡＭ、ハードディスクなどの記憶装置、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、可搬記録媒体である。記憶装置１００３が記録媒体１００５であってもよい。プロセッサ１００１は、メモリ１００２と、記憶装置１００３に対して、データやプログラムの読み出しと書き込みを行うことができる。プロセッサ１００１は、Ｉ／Ｏインタフェース１００４を介して、例えば、指示装置４００及び各配置先にアクセスすることができる。プロセッサ１００１は、記録媒体１００５にアクセスすることができる。記録媒体１００５には、コンピュータ１０００を、配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、又は配置実行装置２００として動作させるプログラムが格納されている。
【０１３９】  プロセッサ１００１は、記録媒体１００５に格納されている、コンピュータ１０００を、配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、又は配置実行装置２００として動作させるプログラムを、メモリ１００２にロードする。そして、プロセッサ１００１が、メモリ１００２にロードされたプログラムを実行することにより、コンピュータ１０００は、配置装置１００、配置装置１００Ａ、配置装置１００Ｂ、又は配置実行装置２００として動作する。
【０１４０】  以下に示すグループに含まれる部は、例えば、プログラムを記憶する記録媒体１００５からメモリ１００２に読み込まれた、各部の機能を実現することができる専用のプログラムと、そのプログラムを実行するプロセッサ１００１により実現することができる。上述のグループは、決定部１０１、変更部１０２、推定部１０４、要求処理部１０５、配置部１０６、検出部１０７、及び取り出し部１０８を含む。また、配置先情報記憶部１０３は、コンピュータ１０００が含むメモリ１００２やハードディスク装置等の記憶装置１００３により実現することができる。あるいは、上述のグループに含まれる部、及び、配置先情報記憶部１０３の一部又は全部を、各部の機能を実現する専用の回路によって実現することもできる。
【０１４１】  また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１４２】  （付記１）  オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、  を備え、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置装置。
【０１４３】  （付記２）  前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する推定手段  をさらに備える付記１に記載の配置装置。
【０１４４】  （付記３）  前記推定手段は、  前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す  付記２に記載の配置装置。
【０１４５】  （付記４）  前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置する配置手段をさらに備え、  前記配置手段は、前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  付記１乃至３のいずれかに記載の配置装置。
【０１４６】  （付記５）  前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記決定手段は、前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記変更手段は、前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する、  付記１乃至４のいずれかに記載の配置装置。
【０１４７】  （付記６）  前記決定手段は、前記特性値が取りうる値が分布する領域が分割された１つ以上の範囲の各々がいずれかに割り当てられている前記１つ以上の配置先のうち、前記特性値を含む前記範囲に割り当てられている前記配置先を、前記オブジェクトが配置される前記配置先として決定し、  前記変更手段は、前記範囲に割り当てる前記配置先を、さらに、前記配置先の各々について、当該配置先に割り当てられている前記範囲の大きさの合計が、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記範囲を変更する  付記５に記載の配置装置。
【０１４８】  （付記７）  前記決定手段は、異なる複数の前記オブジェクト情報から導出される前記特性値が、前記領域に、一様又はほぼ一様に分布するように、前記オブジェクトに付与された前記オブジェクト情報に基づいて前記特性値を導出する  付記５又は６に記載の配置装置。
【０１４９】  （付記８）  前記オブジェクトが配置される前記配置先として決定された前記配置先に、前記オブジェクトを配置する配置手段  をさらに備える付記１乃至７のいずれかに記載の配置装置。
【０１５０】  （付記９）  前記配置先の各々と、付記１乃至８のいずれかに記載の配置装置とを含む配置システム。
【０１５１】  （付記１０）  オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更し、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置方法。
【０１５２】  （付記１１）  前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する  付記１０に記載の配置方法。
【０１５３】  （付記１２）  前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す  付記１１に記載の配置方法。
【０１５４】  （付記１３）  前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置し、  前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  付記１０乃至１２のいずれかに記載の配置方法。
【０１５５】  （付記１４）  前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定し、  前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する、  付記１０乃至１３のいずれかに記載の配置方法。
【０１５６】  （付記１５）  前記特性値が取りうる値が分布する領域が分割された１つ以上の範囲の各々がいずれかに割り当てられている前記１つ以上の配置先のうち、前記特性値を含む前記範囲に割り当てられている前記配置先を、前記オブジェクトが配置される前記配置先として決定し、  前記範囲に割り当てる前記配置先を、さらに、前記配置先の各々について、当該配置先に割り当てられている前記範囲の大きさの合計が、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記範囲を変更する  付記１４に記載の配置方法。
【０１５７】  （付記１６）  異なる複数の前記オブジェクト情報から導出される前記特性値が、前記領域に、一様又はほぼ一様に分布するように、前記オブジェクトに付与された前記オブジェクト情報に基づいて前記特性値を導出する  付記１４又は１５に記載の配置方法。
【０１５８】  （付記１７）  前記オブジェクトが配置される前記配置先として決定された前記配置先に、前記オブジェクトを配置する  付記１０乃至１６のいずれかに記載の配置方法。
【０１５９】  （付記１８）  コンピュータを、  オブジェクトに付与されたオブジェクト情報に基づいて、前記オブジェクトが配置されうる１つ以上の配置先のいずれかを一意に定める規則を、前記配置先の増加が行われるのに応じて、前記規則に従って前記オブジェクト情報に基づいて定まる前記配置先が、最後に追加された前記配置先以外の前記配置先に変化しないように、前記配置先の各々に新たに配置できる前記オブジェクトの量を表す空き容量に基づいて変更する変更手段と、  前記オブジェクト情報を受信するのに応じて、前記規則に従って、前記オブジェクト情報に基づいて定まる前記配置先を、前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する決定手段と、  して動作させ、  前記配置先の増加は、新しい前記配置先の追加、又は、最後に追加された前記配置先の新たに配置できるオブジェクトの量である空き容量の増加である、  配置プログラム。
【０１６０】  （付記１９）  コンピュータを、  前記オブジェクト情報を受信するのに応じて、前記配置先の増加が行われる前から、最後の前記配置先の増加が行われた後までの間に、前記規則に従って前記オブジェクト情報に基づいて決定されうる前記配置先の中で、前記オブジェクト情報が付与されているオブジェクトを保持する、最も後に追加された前記配置先を、受信した前記オブジェクト情報が付与された前記オブジェクトが配置されている前記配置先として特定する推定手段と、  して動作させる付記１８に記載の配置プログラム。
【０１６１】  （付記２０）  コンピュータを、  前記規則である対象規則に従って、受信した前記オブジェクト情報に基づいて定まる前記配置先である推定配置先に、前記オブジェクト情報が付与されている前記オブジェクトが配置されているか否かを判定し、前記推定配置先に前記オブジェクトが配置されている場合、前記推定配置先を前記オブジェクト情報が付与されている前記オブジェクトの取り出し先として決定し、前記推定配置先に前記オブジェクトが配置されていない場合、前記推定配置先が追加される直前の前記規則を前記対象規則に配置先にする配置先推定  を、最新の前記規則を最初の前記対象規則とし、前記取り出し先が決定されるか、前記推定配置先が、オブジェクトが配置される前に存在していた前記配置先になるまで繰り返す前記推定手段と、  して動作させる付記１９に記載の配置プログラム。
【０１６２】  （付記２１）  コンピュータを、さらに、  前記オブジェクトが配置される前記配置先として決定された前記配置先に前記オブジェクトを配置する配置手段として動作させ、  前記配置手段は、前記規則が変更されることによって、前記配置先に配置されている前記オブジェクトに付与されている前記オブジェクト情報に基づいて前記規則に従って定まる前記配置先が、前記オブジェクトが配置されている前記配置先と別の前記配置先に変化しても、前記オブジェクト情報を移動させない  付記１８乃至２０のいずれかに記載の配置プログラム。
【０１６３】  （付記２２）  コンピュータを、  前記オブジェクト情報に基づいて一意に算出される特性値が取りうる値の集合が分割された、１つ以上の部分集合の各々が、前記１つ以上の配置先のいずれかに割り当てられ、  前記規則は、前記特性値に基づいて、当該特性値を含む前記部分集合に割り当てられている前記配置先を特定することによって、前記配置先を一意に定める場合に、  前記特性値に基づいて、前記規則によって定まる前記配置先を、前記特性値が導出された前記オブジェクト情報が付与されている前記オブジェクトが配置される前記配置先として決定する前記決定手段と、  前記配置先が追加されるのに応じて、前記部分集合に割り当てる前記配置先を、最後に追加された前記配置先以外の前記配置先に変更しないように、さらに、前記配置先の各々について、当該配置先に割り当てられている前記部分集合の大きさが、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記部分集合を変更することによって、前記規則を変更する前記変更手段と、  して動作させる付記１８乃至２１のいずれかに記載の配置プログラム。
【０１６４】  （付記２３）  コンピュータを、  前記特性値が取りうる値が分布する領域が分割された１つ以上の範囲の各々がいずれかに割り当てられている前記１つ以上の配置先のうち、前記特性値を含む前記範囲に割り当てられている前記配置先を、前記オブジェクトが配置される前記配置先として決定する前記決定手段と、  前記範囲に割り当てる前記配置先を、さらに、前記配置先の各々について、当該配置先に割り当てられている前記範囲の大きさの合計が、前記配置先に新たに配置できる前記オブジェクトの数を表す空き容量に応じた大きさであるように、前記配置先に割り当てられる前記範囲を変更する前記変更手段と、  して動作させる付記２２に記載の配置プログラム。
【０１６５】  （付記２４）  コンピュータを、  異なる複数の前記オブジェクト情報から導出される前記特性値が、前記領域に、一様又はほぼ一様に分布するように、前記オブジェクトに付与された前記オブジェクト情報に基づいて前記特性値を導出する前記決定手段と、  して動作させる付記２２又は２３に記載の配置プログラム。
【０１６６】  （付記２５）  コンピュータを、  前記オブジェクトが配置される前記配置先として決定された前記配置先に、前記オブジェクトを配置する配置手段と、  して動作させる付記１８乃至２４のいずれかに記載の配置プログラム。
【０１６７】  以上、本発明を、上述した実施形態およびその変形例に適用した例として説明した。しかし、本発明の技術的範囲は、上述した各実施形態に記載した範囲には限定されない。当業者には、係る実施形態に対して多様な変更又は改良を加えることが可能であることは明らかである。そのような場合、係る変更又は改良を加えた新たな実施形態も、本発明の技術的範囲に含まれ得る。そしてこのことは、請求の範囲に記載した事項から明らかである。本発明の構成や詳細には、本発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１６８】  この出願は、２０１４年７月１１日に出願された日本出願特願２０１４−１４３３２３を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１６９】  １０    配置システム  １０Ａ    配置システム  １００    配置装置  １００Ａ    配置装置  １００Ｂ    配置装置  １０１    決定部  １０２    変更部  １０３    配置先情報記憶部  １０４    推定部  １０５    要求処理部  １０６    配置部  １０７    検出部  １０８    取り出し部  １１０    配置決定部  １１０Ｂ    配置決定部  ２００    配置実行装置  ３００    サーバアレイ  ３０１    配置先（サーバ）  ３０Ｎ    配置先（サーバ）  ４００    指示装置  １０００    コンピュータ  １００１    プロセッサ  １００２    メモリ  １００３    記憶装置  １００４    Ｉ／Ｏインタフェース  １００５    記録媒体
【図１】
2016006222.tif 000003
【図２】
2016006222.tif 000004
【図３】
2016006222.tif 000005
【図４】
2016006222.tif 000006
【図５】
2016006222.tif 000007
【図６】
2016006222.tif 000008
【図７】
2016006222.tif 000009
【図８】
2016006222.tif 000010
【図９】
2016006222.tif 000011
【国際調査報告】
2016006222.tif 000012
2016006222.tif 000013