(57)【要約】【課題】評価値推定アルゴリズムにおいて突発的なデータスパイクを高速に検出できるようにする。【解決手段】評価対象コンテンツに対するカウント値と複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて評価対象コンテンツの評価値を算出する算出部１９と、複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認する確認部１３と、複数のコンテンツに対する各カウント値の合計値が所定値に達した場合に、複数のコンテンツの各カウント値を縮小する処理部１４とを備える【選択図】図１
2014016780.tif 000002
【特許請求の範囲】
【請求項１】
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価装置において、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認する確認部と、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小する処理部と、
を備えることを特徴とする評価装置。
【請求項２】
前記処理部が、
前記複数のコンテンツに対する各カウント値を（１−α）倍（ただし、０＜α＜１）することにより縮小することを特徴とする請求項１記載の評価装置。
【請求項３】
前記処理部が、
前記複数のコンテンツに対する縮小後の各カウント値の小数点以下を切り上げることで整数値にすることを特徴とする請求項１又は２記載の評価装置。
【請求項４】
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各カウント値に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なうことを特徴とする請求項１〜３のいずれか１項に記載の評価装置。
【請求項５】
複数のコンテンツを分散して格納する複数のノード装置と、
前記複数のコンテンツのうちの評価対象コンテンツに対するアクセス数と、前記複数のコンテンツに対する各アクセス数の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、
前記複数のコンテンツに対する各アクセス数の合計値が所定値に達したかを確認する確認部と、
前記複数のコンテンツに対する各アクセス数の合計値が前記所定値に達した場合に、前記複数のコンテンツの各アクセス数を縮小する処理部と、
を備えることを特徴とする分散格納システム。
【請求項６】
前記処理部が、
前記複数のコンテンツに対する各アクセス数を（１−α）倍（ただし、０＜α＜１）することにより縮小することを特徴とする請求項５記載の分散格納システム。
【請求項７】
前記処理部が、
前記複数のコンテンツに対する縮小後の各アクセス数の小数点以下を切り上げることで整数値にすることを特徴とする請求項５又は６記載の分散格納システム。
【請求項８】
前記評価値推定アルゴリズムはSpace Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各アクセス数に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なうことを特徴とする請求項５〜７のいずれか１項に記載の分散格納システム。
【請求項９】
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価方法において、
コンピュータが、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認し、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小し、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出することを特徴とする評価方法。
【請求項１０】
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価プログラムにおいて、
コンピュータに、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認させ、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小させ、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出させることを特徴とする評価プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、評価装置，分散格納システム，評価方法及び評価プログラムに関する。
【背景技術】
【０００２】
例えば、ビッグデータを扱う分散ストレージシステムではデータスパイクという現象が知られている。
データスパイクとは、特定の人気のあるデータに極端にアクセスが集中することで、このデータスパイクが発生すると、人気データを持つサーバにのみアクセスが集中することになりそのサーバのレスポンス性能が低下してしまう。
【０００３】
サーバのレスポンス性能の低下は、人気のあるデータを見つけてその処理を負荷が少ない他のサーバに肩代わりさせることで解決することができるが、それにあたってデータの人気度をサーバ内部で把握する必要がある。
ここで、データの人気度Ｐは、データへのアクセス回数をＣ、データを持つサーバへの合計アクセス回数をＮとすると、Ｐ＝Ｃ／Ｎで求めることができる。ただし、Ｎ＝ΣiＣiである。しかしながら、人気度Ｐを誤差なく求めようとすると、データごとにアクセス回数を記録する必要があるのでメモリ消費量がデータの個数に比例して増加する。そのため、ビッグデータのような膨大な数のデータを扱う分散ストレージシステム上でこの手法を採用すると、メモリ消費量が膨大になってしまうという問題がある。
【０００４】
このような問題を解決するために、人気度を最大誤差εの範囲で推定するアルゴリズムがいくつか提案されている。これらのアルゴリズムは人気度の誤差を許容することで必要なメモリ使用量の削減を実現する。これにより、ビッグデータを扱う分散ストレージシステム上でもメモリ使用量を気にすることなく人気度を最大誤差εの範囲で推定することができる。
【０００５】
これらのアルゴリズムの中でも、特にSpace Savingアルゴリズムは高速・低メモリ・高精度であることが知られている。以下、Space Savingアルゴリズムの概略について説明する。
図６はSpace SavingアルゴリズムにおけるStream-Summaryデータ構造を例示する図、図７はそのカウント更新アルゴリズムを例示する図である。
【０００６】
Space Savingアルゴリズムは、図６に示すStream-Summaryデータ構造を、図７に示すアルゴリズムによって更新することで、データＤに対する人気度を最大誤差εで推定する。
Stream-Summaryは、データ名及びカウントからなる要素（最大で１／ε個）と、それを管理するバケットとを備えるデータ構造である。各バケットはカウントが同じ要素をリスト構造で管理しており、バケットは管理している要素のカウント値で昇順にソートされたソート済みリスト（図示省略）によって管理される。
【０００７】
カウントはデータへのアクセスがあるたびにインクリメントされ、データＤの推定人気度はデータＤのカウントＣとカウントの合計値Ｎを用いてＣ／Ｎとして表される（Ｎ＝ΣiＣi）。
図８はSpace Savingアルゴリズムによる処理を説明するフローチャートである。
先ず、ステップＡ１において、所定の停止条件があるか否かを確認し、停止条件がある場合には（ステップＡ１のＹＥＳルート参照）、処理を終了する。停止条件がない場合には（ステップＡ１のＮＯルート参照）、次に、ステップＡ２において、データＤへのアクセスがあったか否かを確認する。
【０００８】
データＤへのアクセスがない場合には（ステップＡ２のＮＯルート参照）、ステップＡ１に戻る。
データＤへのアクセスがあった場合には（ステップＡ２のＹＥＳルート参照）、ステップＡ３において、データＤがStream-Summaryに要素として含まれているか否かを確認する。
【０００９】
データＤがStream-Summaryに要素として含まれていた場合（ステップＡ３のＹＥＳルート参照）、ステップＡ５において、その要素のカウントをインクリメントする。又、このカウントのインクリメントにより、データＤを管理するバケットが変更される際はデータＤを管理するバケットの変更を行なう。そして、ステップＡ１に戻る。
データＤがStream-Summaryに含まれていない場合には（ステップＡ３のＮＯルート参照）、ステップＡ４において、Stream-Summaryの要素数に空きがあるかを調べる。すなわち、Stream-Summaryの要素数が１／εよりも小さいか否かを確認する。要素数が１／εよりも小さい場合には（ステップＡ４のＹＥＳルート参照）、Stream-Summaryの最大要素数に達していないので、ステップＡ６において、データＤをカウント＝１としてStream-Summaryに追加する。その後、ステップＡ１に戻る。
【００１０】
要素数が１／ε以上の場合には（ステップＡ４のＮＯルート参照）、要素数が最大要素数まで達していて空きがない状態である。この場合には、ステップＡ７において、先頭バケットが管理しているリストの先頭要素（カウントをminCountとする）を削除する一方で、データＤをカウント（＝minCount＋１）としてStream-Summaryに追加する。これにより、カウントが最小の要素とデータＤとの入れ替えを行なう。その後、ステップＡ１に戻る。
【００１１】
このように、Space Savingアルゴリズムによれば、人気度をデータの個数によらないメモリ消費量で算出することができる
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Ahmed Metwally, Divyakant Agrawal, Amr El Abbadi著、「An integrated efficient solution for computing frequent and top-k elements in data streams」、ACM Transactions on Database Systems (TODS)、2006年9月、Volume 31, Issue 3, p. 1095-1133
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、このような従来のSpace Savingアルゴリズムではデータスパイクを高速に検出することはできないという課題がある。
Space Saving アルゴリズムは動作開始時点から現時点までのすべてのカウントをもとにして人気度の推定を行なう。従って、動作開始時点から十分なアクセスがあった後に発生する突発的なデータスパイクを敏感に検出することができない。データスパイクが引き起こすはずの人気度の変動がデータスパイク発生前の過去の人気度に引きずられて小さくなってしまうからである。
【００１４】
１つの側面では、本発明は、評価値推定アルゴリズムにおいて突発的なデータスパイクを高速に検出できるようにすることを目的とする。
なお、前記目的に限らず、後述する発明を実施するための形態に示す各構成により導かれる作用効果であって、従来の技術によっては得られない作用効果を奏することも本発明の他の目的の１つとして位置付けることができる。
【課題を解決するための手段】
【００１５】
このため、この評価装置は、複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価装置において、前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認する確認部と、前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小する処理部と、を備える。
【００１６】
また、この分散格納システムは、複数のコンテンツを分散して格納する複数のノード装置と、前記複数のコンテンツのうちの評価対象コンテンツに対するアクセス数と、前記複数のコンテンツに対する各アクセス数の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、前記複数のコンテンツに対する各アクセス数の合計値が所定値に達したかを確認する確認部と、前記複数のコンテンツに対する各アクセス数の合計値が前記所定値に達した場合に、前記複数のコンテンツの各アクセス数を縮小する処理部と、を備える。
【００１７】
さらに、この評価方法は、複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価方法において、コンピュータが、前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認し、前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小し、前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する。
【００１８】
また、この評価プログラムは、複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価プログラムにおいて、コンピュータに、前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認させ、前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小させ、前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出させる。
【発明の効果】
【００１９】
一実施形態によれば、評価値推定アルゴリズムにおいて突発的なデータスパイクを高速に検出できる。
【図面の簡単な説明】
【００２０】
【図１】実施形態の一例としての管理サーバをそなえる分散ストレージシステムの機能構成を模式的に示す図である。
【図２】実施形態の一例としての管理サーバをそなえる分散ストレージシステムの構成を模式的に示す図である。
【図３】実施形態の一例としての分散ストレージシステムにおけるカウンタ値の更新手法を説明するフローチャートである。
【図４】実施形態の一例としての分散ストレージシステムにおけるシュリンク処理部がカウンタ値を縮小した際の処理を説明するフローチャートである。
【図５】実施形態の一例としての分散ストレージシステムにおけるカウントシュリンク処理のアルゴリズムを例示する図である。
【図６】Space SavingアルゴリズムにおけるStream-Summaryデータ構造を例示する図である。
【図７】Space Savingアルゴリズムにおけるカウント更新アルゴリズムを例示する図である。
【図８】Space Savingアルゴリズムによる処理を説明するフローチャートである。
【発明を実施するための形態】
【００２１】
以下、図面を参照して本評価装置，分散格納システム，評価方法及び評価プログラムに係る実施の形態を説明する。ただし、以下に示す実施形態はあくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。又、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能等を含むことができる。
【００２２】
図１は実施形態の一例としての管理サーバ（評価装置）をそなえる分散ストレージシステム（分散格納システム）の機能構成を模式的に示す図、図２はその管理サーバをそなえる分散ストレージシステムの構成を模式的に示す図である。
分散ストレージシステム１は、図２に示すように、管理サーバ１０，プロキシサーバ４０，クライアント６０及びストレージサーバノード（ストレージ装置）３０−１〜３０−６を備える。ただし、図１中においては、便宜上、クライアント６０及びプロキシサーバ４０の図示を省略している。
【００２３】
図２に示す例においては、管理サーバ１０及び各ストレージサーバノード３０−１〜３０−６と各プロキシサーバ４０とは、例えばLocal Area Network（ＬＡＮ）５０を介して、相互に通信可能に接続されている。又、各プロキシサーバ４０と各クライアント６０とは、公衆回線網等のネットワーク５１を介して、相互に通信可能に接続されている。
分散ストレージシステム１は、複数のストレージサーバノード３０−１〜３０−６がそれぞれ有するディスク領域をまとめて、あたかも一つのストレージのように取り扱うことを可能とする。この分散ストレージシステム１においては、複数のデータファイル（データ，コンテンツ）を複数のストレージサーバノード３０−１〜３０−６に分散して配置される。
【００２４】
以下、ストレージサーバノードを示す符号としては、複数のストレージサーバノードのうち１つを特定する必要があるときには符号３０−１〜３０−６を用いるが、任意のストレージサーバノードを指すときには符号３０を用いる。
ストレージサーバノード３０は、サーバ機能を備えたコンピュータであり、記憶装置３４を備える。
【００２５】
記憶装置３４は種々のデータやプログラムを格納する記憶装置であって、例えば、Hard Disk Drive（ＨＤＤ）やSolid State Drive（ＳＳＤ）である。又、記憶装置３４として、例えば、複数の記憶装置によりRedundant Arrays of Inexpensive Disks（ＲＡＩＤ）を構成してもよく、種々変形して実施することができる。
この記憶装置３４には、各クライアント６０からリードもしくはライトされるデータファイルが格納される。
【００２６】
そして、本分散ストレージシステム１は、これらの複数のストレージサーバノード３０の記憶装置３４にデータ（コンテンツ，評価対象コンテンツ）を分散して格納する。
図２に示す例においては、本分散ストレージシステム１に６つのストレージサーバノード３０が備えられているが、これに限定されるものではなく、５つ以下もしくは７以上のストレージサーバノード３０をそなえてもよい。
【００２７】
クライアント６０は、例えば、パーソナルコンピュータ等の情報処理装置であり、プロキシサーバ４０を介して、ストレージサーバノード３０に格納されたデータ（コンテンツ）に対するリードやライトの要求（リード／ライト要求）を行なう。図１及び図２に示す例においては、分散ストレージシステム１に２つのクライアント６０が備えられているが、これに限定されるものではなく、１つもしくは３以上のクライアント６０をそなえてもよい。
【００２８】
クライアント６０は、例えば、アクセス対象のファイル名（オブジェクト名）等のデータを特定する情報とともにリード／ライト要求をプロキシサーバ４０に対して送信する。以下、クライアント６０からアクセスを行なうコンテンツを単にデータという場合がある。
プロキシサーバ４０は、クライアント６０に代わってストレージサーバノード３０へのデータアクセスを行なう。各プロキシサーバ４０は、サーバ機能を備えたコンピュータ等の情報処理装置であり、互いに同様の構成を備える。図１及び図２に示す例においては、分散ストレージシステム１に２つのプロキシサーバ４０が備えられているが、これに限定されるものではなく、１つもしくは３以上のプロキシサーバ４０をそなえてもよい。
【００２９】
プロキシサーバ４０は、それぞれ分散表４１を備える。分散表４１は、データファイルを特定する情報に対して当該データファイルの格納位置を関連付けて構成される。プロキシサーバ４０は、クライアント６０からデータファイルへのリード／ライト要求を受信すると、受信したファイル名に基づいて分散表４１を参照して、アクセス対象のデータファイルの格納場所を確認する。プロキシサーバ４０は、このデータファイルの格納場所に対応するストレージサーバノード３０に対してリード／ライト要求を送信する。又。プロキシサーバ４０は、ストレージサーバノード３０からリード／ライト要求に対するリプライを受信すると、リード／ライト要求の送信元のクライアント６０に対して、そのリプライを転送する。
【００３０】
なお、プロキシサーバ４０としての機能は、既知の種々の手法で実現され、その詳細な説明は省略する。
管理サーバ１０は、サーバ機能を備えたコンピュータ等の情報処理装置であり、本分散ストレージシステム１における各種設定や制御を行なう。
管理サーバ１０は、図１に示すように、Central Processing Unit（ＣＰＵ）１０１，Random Access Memory（ＲＡＭ）１０２，Read Only Memory（ＲＯＭ）１０３，キーボード１０４，ポインティングデバイス１０５，記憶装置１０６及び表示装置１０７を備える。
【００３１】
記憶装置１０６はＣＰＵ１０１が実行するOperating System（ＯＳ）やプログラム，種々のデータ等を格納する記憶装置であって、例えば、ＨＤＤやＳＳＤである。又、記憶装置１０６として、例えば、複数の記憶装置によりＲＡＩＤを構成してもよく、種々変形して実施することができる。
【００３２】
ＲＯＭ１０３は、ＣＰＵ１０１が実行するプログラムや各種データ等を格納する記憶装置である。ＲＡＭ１０２は、種々のデータやプログラムを格納する記憶領域であって、ＣＰＵ１０１がプログラムを実行する際に、データやプログラムを格納・展開して用いる。又、このＲＡＭ１０２には、パケット情報１５，要素情報１６及びカウント合計値Ｎが格納される。
【００３３】
パケット情報１５は、後述する人気度推定部（算出部）１９のバケット管理部１１がSpace Savingアルゴリズムを用いて人気度を推定する際に用いるバケットに関する情報である。Stream-Summaryデータ構造において、バケットには同じカウントのデータ（要素）が関連付けられる。パケット情報１５は、各バケットが関連付けられたデータのカウントや、バケットに関連付けられたデータ（要素）を特定する情報を備える。なお、カウントの値（カウント値）はそのデータ（コンテンツ）に対して行なわれたアクセス数 を表す。なお、Space Savingアルゴリズムにおいては、カウント値は、厳密にはアクセス数の近似値であるが、便宜上、単にアクセス数と表す。
【００３４】
要素情報１６は、後述する人気度推定部１９の要素管理部１２がSpace Savingアルゴリズムを用いて人気度を推定する際に用いる要素に関する情報であり、Stream-Summaryデータ構造の要素についての情報である。要素情報１６は、要素として登録されたデータを識別する情報（例えば、格納先アドレスやデータ名）と、そのデータに対するアクセス数を示すカウント値とを含む。
【００３５】
カウント合計値Ｎは、要素情報１６に登録された各データのカウント値の合計である。
キーボード１０４及びポインティングデバイス１０５は利用者が各種入力操作を行なう入力装置である。ポインティングデバイス１０５は、例えば、タッチパッドやマウスである。ディスプレイ１０７は、各種情報やメッセージを表示する出力装置である。
なお、キーボード１０４やポインティングデバイス１０５及びディスプレイ１０７としての機能は、これらの機能をそなえたタッチパネルディスプレイで実現してもよく、種々変形して実施することができる。
【００３６】
ＣＰＵ１０１は、種々の制御や演算を行なう処理装置であり、ＲＯＭ１０３等に格納されたＯＳやプログラムを実行することにより、種々の機能を実現する。具体的には、ＣＰＵ１０１は、図１に示すように、人気度推定部１９，カウント合計値管理部１３，シュリンク処理部１４及びデータ管理部１８として機能する。
なお、これらの人気度推定部１９，カウント合計値管理部１３，シュリンク処理部１４及びデータ管理部１８としての機能を実現するためのプログラム（評価プログラム）は、例えばフレキシブルディスク，ＣＤ（ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ等），ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−ＲＡＭ，ＤＶＤ−Ｒ，ＤＶＤ＋Ｒ，ＤＶＤ−ＲＷ，ＤＶＤ＋ＲＷ，ＨＤ  ＤＶＤ等），ブルーレイディスク，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。
【００３７】
人気度推定部１９，カウント合計値管理部１３，シュリンク処理部１４及びデータ管理部１８としての機能を実現する際には、内部記憶装置（本実施形態ではＲＡＭ１０２やＲＯＭ１０３）に格納されたプログラムがコンピュータのマイクロプロセッサ（本実施形態ではＣＰＵ１０１）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。
【００３８】
なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、管理サーバ１０がコンピュータとしての機能を有しているのである。
【００３９】
データ管理部１８は、本分散ストレージシステム１における各ストレージサーバノード３０が保持するデータを管理する。
データ管理部１８は、本分散ストレージシステム１に備えられた複数のストレージサーバノード３０間において、一部のストレージサーバノード３０に負荷が集中することのないように、人気度の高いデータを複数のストレージサーバノード３０に分散して再配置（移動）させる。
【００４０】
データ管理部１８は、人気度推定部１９により算出された人気度（評価値）に基づいて、人気度の高いデータを特定する。
また、データ管理部１８は、ストレージサーバノード３０間でデータの再配置を行なった場合には、プロキシサーバ４０に対して、データの再配置の結果を通知し、分散表４１を更新させる。
【００４１】
人気度推定部（算出部）１９は、本分散ストレージシステム１における各ストレージサーバノード３０の各データ（評価対象コンテンツ）の人気度（評価値）を算出する。
クライアント６０から、ストレージサーバノード３０のコンテンツに対してアクセスが行なわれると、ストレージサーバノード３０もしくはプロキシサーバ４０は、少なくともアクセスが行なわれたデータを識別する情報を管理サーバ１０に対して通知する。
【００４２】
人気度推定部１９は、バケット管理部１１及び要素管理部１２としての機能を備え、各データについての人気度を、Space Savingアルゴリズム（評価値推定アルゴリズム）を用いて推定する。すなわち、人気度推定部１９は、図６に示したStream-Summaryデータ構造を管理する。そして、本分散ストレージシステム１における各ストレージサーバノード３０の各データに対してアクセスが行なわれる度に、図７に示したカウント更新アルゴリズムを実行することで、データに対する人気度を最大誤差εで推定する。
【００４３】
バケット管理部１１は、前述したＲＡＭ１０２のバケット情報１５を用いて、Stream-Summaryデータ構造におけるバケットを管理する。このStream-Summaryデータ構造においては、図６に例示したように、データ（コンテンツ）Ｄを要素Ｅとして管理し、又、各データに対するアクセス数をカウント値として管理する。
バケット管理部１１は、バケット情報１５の作成や削除を行ない、又、同じカウント値が同じ要素を管理する。バケット管理部１１は、バケットを、各バケットが持つ要素のカウント値でソートしたソート済みリスト（図示省略）で管理する。
【００４４】
また、本分散ストレージシステム１においては、バケット管理部１１は、後述するシュリンク処理部１４がデータのカウント値を変更（縮小）した場合には、変更後のカウント値に応じて、バケットへ要素の関連付けを再度行なう。
後述の如くシュリンク処理部１４がデータのカウント値を変更することにより、Stream-Summaryデータ構造において隣接するバケットにおいて、互いに同じカウントのデータを有することになる場合がある。この場合、バケット管理部１１が、変更後の各データのカウント値に応じてバケットへの関連付けを再度行なうことにより、変更前は異なるバケットのデータが同じバケットに関連付けられる場合がある。以下、変更後の各データのカウント値に応じてバケットへの関連付けを再度行なうことにより、変更前はバケットが異なっていたデータを同一のバケットに関連付けることを、バケットをマージすると言う場合がある。
【００４５】
そして、人気度推定部１９は、評価対象のデータ（評価対象コンテンツ）の人気度Ｐを、そのデータのカウント値Ｃと、後述するカウント合計値管理部１３によって管理されるカウント合計値Ｎとを用いて、人気度Ｐ＝Ｃ／Ｎを算出することにより求める。
要素管理部１２は、前述したＲＡＭ１０２の要素情報１６を用いて、Stream-Summaryデータ構造における要素を管理する。Stream-Summaryデータ構造において、最大誤差εとした場合に、要素管理部１２は、最大で１／ε個の要素を管理する。すなわち、要素情報１６においては、最大で１／ε個の要素が登録される。
【００４６】
要素管理部１２は、要素情報１６の作成や削除を行ない、要素として登録されたデータについてのカウント値の更新等を行なう。
すなわち、要素管理部１２は、データへのアクセスが行なわれる度に、そのカウント値を更新する。なお、データに対してアクセスが行なわれたことは、プロキシサーバ４０から取得されてもよく、又、各ストレージサーバノード３０から通知されてもよい。
【００４７】
また、本分散ストレージシステム１においては、バケット管理部１１は、後述するシュリンク処理部１４が各データのカウント値を変更した場合には、要素情報１２における各データのカウント値を変更された値で更新する。
カウント合計値管理部１３は、前述したＲＡＭ１０２のカウント合計値Ｎを用いて、各データのカウント値の合計を管理する。カウント合計値管理部１３は、要素管理部１２によって管理されている１／ε個の全てのデータの各カウント値を合計し、ＲＡＭ１０２にカウント合計値Ｎとして格納する。
【００４８】
また、本分散ストレージシステム１においては、バケット管理部１１は、後述するシュリンク処理部１４が各データのカウント値を変更した場合には、変更されたカウント値を用いて合計をし直し、カウント合計値Ｎを更新する。
シュリンク処理部（処理部）１４は、カウント合計値Ｎを予め設定された閾値Ｎｔと比較し、カウント合計値Ｎが閾値Ｎｔよりも大きくなった場合に、要素情報１６に登録された全てのデータのカウント値を一律に小さくする。具体的には、シュリンク処理部１４は、各データのカウント値を（１−α）倍することで縮小（シュリンク）させて更新する。ただし、０＜α＜１である。例えば、α＝０．８７５もしくは７／８である。
【００４９】
すなわち 、シュリンク処理部１４は、人気度が平滑化係数をαとした指数移動平均となるように時間軸に沿った重み付けを行なう。
また、シュリンク処理部１４は、各データのカウント値を（１−α）倍した結果において、小数点以下を繰り上げる。以下、各データのカウント値を（１−α）倍して縮小することをカウントシュリンクという場合がある。
【００５０】
これにより、前述の如く、ＲＡＭ１０２のカウント合計値Ｎも縮小される。縮 小後のカウント合計値Nの値は縮小前の（１−α）倍の値に上述のデータのカウント値を（１−α）倍する際の丸め誤差をすべて含んだ値となる。
上述の如く構成された、実施形態の一例としての分散ストレージシステム１におけるカウンタ値の更新手法を、図３に示すフローチャート（ステップＢ１〜Ｂ９）に従って説明する。
【００５１】
先ず、ステップＢ１において、所定の停止条件があるか否かを確認し、停止条件がある場合には（ステップＢ１のＹＥＳルート参照）、処理を終了する。停止条件がない場合には（ステップＢ１のＮＯルート参照）、次に、ステップＢ２において、データＤへのアクセスがあったか否かを確認する。
データＤへのアクセスがない場合には（ステップＢ２のＮＯルート参照）、ステップＢ１に戻る。
【００５２】
データＤへのアクセスがあった場合には（ステップＢ２のＹＥＳルート参照）、ステップＢ３において、データＤがStream-Summaryに要素として含まれているか否かを確認する。
データＤがStream-Summaryに要素として含まれていた場合（ステップＢ３のＹＥＳルート参照）、ステップＢ５において、その要素のカウントをインクリメントする。又、このカウントのインクリメントにより、データＤを管理するバケットが変更される際はデータＤを管理するバケットの変更を行なう。
【００５３】
そして、ステップＢ８において、シュリンク処理部１４が、カウント合計値Ｎが閾値Ｎｔに達したかを確認する。カウント合計値Ｎが閾値Ｎｔに達していない場合には（ステップＢ８のＮＯルート参照）、ステップＢ１に戻る。
カウント合計値Ｎが閾値Ｎｔに達している場合には（ステップＢ８のＹＥＳルート参照）、ステップＢ９において、シュリンク処理部１４が、要素情報１６に登録されている 全てのデータのカウント値を（１−α）倍することにより、各カウント値を縮小する（カウントシュリンク）。その後、ステップＢ１に戻る。
【００５４】
また、データＤがStream-Summaryに含まれていない場合には（ステップＢ３のＮＯルート参照）、ステップＢ４において、Stream-Summaryの要素数に空きがあるかを調べる。すなわち、Stream-Summaryの要素数が１／εよりも小さいか否かを確認する。要素数が１／εよりも小さい場合には（ステップＢ４のＹＥＳルート参照）、Stream-Summaryの最大要素数に達していない。そこで、ステップＢ６において、そのデータＤをカウント＝１としてStream-Summaryに追加する。その後、ステップＢ８に移行する。
【００５５】
要素数が１／ε以上の場合には（ステップＢ４のＮＯルート参照）、要素数が最大要素数まで達していて空きがない状態である。この場合には、ステップＢ７において、先頭バケットが管理しているリストの先頭要素（カウントをminCountとする）を削除する一方で、データＤをカウント（＝minCount＋１）としてStream-Summaryに追加する。これにより、カウントが最小の要素とデータＤとの入れ替えを行なう。その後、ステップＢ８に移行する。
【００５６】
このようにして更新されたStream-Summaryデータ構造を参照することにより、各データのカウント値（アクセス数）の近似値を取得することができる。特に、アクセスが頻繁に行なわれたデータに対するアクセス数（カウント値）を取得することができ、人気度推定部１９がそのカウント値とカウント合計値Ｎとを用いて人気度Ｐを算出する。
次に、実施形態の一例としての分散ストレージシステム１におけるシュリンク処理部１４によるカウントシュリンク処理を、図５を参照しながら、図４に示すフローチャート（ステップＣ１〜Ｃ４）に従って説明する。図５はカウントシュリンク処理のアルゴリズムを例示する図である。なお、この図５に示す例においては、カウントシュリンク処理をプログラムの形式で示している。
【００５７】
カウントシュリンク処理は、前述した図３のフローチャートのステップＢ８において、カウント合計値Ｎが閾値Ｎｔに達したことが検知された場合に実行される。図５に示す例においては、カウントシュリンク処理を“SHRINK ALL COUNTERS”という関数名で表している。又、図５ に示す例においては、カウント合計値Ｎの算出に変数“totalCount”を用いている。
【００５８】
先ず、ステップＣ１において、カウント合計値Ｎを０リセットしてから（図５の矢印Ｐ１参照）、シュリンク処理部１４が、要素情報１６に登録された個々の要素Ｅについてのカウント値を（１−α）倍して縮小する（図５の矢印Ｐ２参照）。この要素Ｅのカウント値を（１−α）倍して縮小する処理は、要素情報１６に登録された全ての要素Ｅに対して行なわれる。
【００５９】
また、（１−α）倍された要素Ｅのカウンタ値はそれぞれカウント合計値Ｎに加算され、“totalCount”の値を逐次更新する（図５の矢印Ｐ３参照）。又、図５中においては、バケットに含まれる全ての要素に対して（１−α）倍及びカウント合計値の更新を順次行ない、更に、これらの処理を全てのバケットに対して行なっている。
その後、ステップＣ２において、バケット管理部１１が、ステップＣ１においてカウント値の縮小を行なったことにより同じカウントの要素を管理するバケットが生じたかを確認する（図５の矢印Ｐ４参照）。
【００６０】
同じカウントの要素を管理するバケットが複数ある場合には（ステップＣ２のＹＥＳルート参照）、ステップＣ４において、それらの同じカウントの要素を管理するバケットをマージする（図５の矢印Ｐ５参照）。その後、ステップＣ２に戻る。
同じカウントの要素を管理するバケットがない場合には（ステップＣ２のＮＯルート参照）、ステップＣ３において、カウント合計値Ｎを“totalCount”の値を用いて更新する（図５の矢印Ｐ６参照）。その後、処理を終了する。
【００６１】
このように、実施形態の一例としての分散ストレージシステム１によれば、カウント合計値ＮがＮｔに達した場合に、全ての要素のカウンタ値を（１−α）倍することにより縮小する。これに伴い、カウント合計値Ｎも（１−α）Ｎに近い値に縮小される。
これにより、各データの人気度Ｐ（＝Ｃ／Ｎ）を算出するための除数であるカウント合計値Ｎが縮小されるので、各データのカウント値Ｃの変動が人気度Ｐに反映され易くなり、データスパイクを検出し易くすることができる。すなわち、過去のアクセスが人気度に与える影響を小さくして、データスパイクが引き起こす人気度の変動を大きくすることができる。つまり、最近の人気度が重視されるよう、時間軸に沿った人気度の重み付けを実現することができる。
【００６２】
そして、開示の技術は上述した実施形態に限定されるものではなく、本実施形態の趣旨を逸脱しない範囲で種々変形して実施することができる。本実施形態の各構成及び各処理は、必要に応じて取捨選択することができ、あるいは適宜組み合わせてもよい。
例えば、上述した実施形態においては、管理装置１０に、人気度推定部１９，カウント合計値管理部１３，シュリンク処理部１４及びデータ管理部１８としての機能を備えているが、これに限定されるものではない。これらの人気度推定部１９，カウント合計値管理部１３，シュリンク処理部１４及びデータ管理部１８としての機能の少なくとも一部を、ストレージサーバノード３０に備えてもよい。
【００６３】
すなわち、ストレージサーバノード３０が評価装置としての機能をそなえ、その記憶装置３４に格納されたデータ（コンテンツ）の人気度を算出し、人気度の高いデータを他のストレージサーバノード３０に分散して再配置（移動）させてもよい。
また、上述した実施形態においては、人気度推定部１９が、各データについての人気度を、評価値推定アルゴリズムとしてSpace Savingアルゴリズムを用いて推定しているが、これに限定されるものではない。すなわち、Space Savingアルゴリズム以外の評価値推定アルゴリズムを用いて人気度の推定を行なってもよく、シュリンク処理部１４は、この評価値推定アルゴリズムにおいて用いられるデータのカウント値を小さくしてもよい。
【００６４】
なお、上述した開示により本実施形態を当業者によって実施・製造することが可能である。
以上の実施形態に関し、更に以下の付記を開示する。
（付記１）
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価装置において、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認する確認部と、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小する処理部と、
を備えることを特徴とする評価装置。
【００６５】
（付記２）
前記処理部が、前記複数のコンテンツに対する各カウント値を（１−α）倍（ただし、０＜α＜１）することにより、それぞれ縮小することを特徴とする付記１記載の評価装置。
（付記３）
前記処理部が、前記複数のコンテンツに対する縮小後のカウント値の小数点以下を切り上げることで整数値にすることを特徴とする付記１又は２記載の評価装置。
【００６６】
（付記４）
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各カウント値に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なうことを特徴とする付記１〜３のいずれか１項に記載の評価装置。
【００６７】
（付記５）
複数のコンテンツを分散して格納する複数のノード装置と、
前記複数のコンテンツのうちの評価対象コンテンツに対するアクセス数と、前記複数のコンテンツに対する各アクセス数の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出する算出部と、
前記複数のコンテンツに対する各アクセス数の合計値が所定値に達したかを確認する確認部と、
前記複数のコンテンツに対する各アクセス数の合計値が前記所定値に達した場合に、前記複数のコンテンツの各アクセス数を縮小する処理部と、
を備えることを特徴とする分散格納システム。
【００６８】
（付記６）
前記処理部が、前記複数のコンテンツに対する各アクセス数を（１−α）倍（ただし、０＜α＜１）することにより、それぞれ縮小することを特徴とする付記５記載の分散格納システム。
（付記７）
前記処理部が、前記複数のコンテンツに対する縮小後の各アクセス数を小数点以下を切り上げることで整数値にすることを特徴とする付記５又は６記載の分散格納システム。
【００６９】
（付記８）
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する各アクセス数に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なうことを特徴とする付記５〜７のいずれか１項に記載の分散格納システム。
【００７０】
（付記９）
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価方法において、
コンピュータが、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認し、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小し、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出することを特徴とする評価方法。
【００７１】
（付記１０）
前記複数のコンテンツの各カウント値を（１−α）倍（ただし、０＜α＜１）することにより縮小することを特徴とする付記９記載の評価方法。
（付記１１）
前記複数のコンテンツに対する縮小後の各カウント値の小数点以下を切り上げることで整数値にすることを特徴とする付記９又は１０記載の評価方法。
【００７２】
（付記１２）
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各カウント値に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なうことを特徴とする付記９〜１１のいずれか１項に記載の評価方法。
【００７３】
（付記１３）
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価プログラムにおいて、
コンピュータに、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認させ、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小させ、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出させることを特徴とする評価プログラム。
【００７４】
（付記１４）
前記複数のコンテンツの各カウント値を（１−α）倍（ただし、０＜α＜１）することにより縮小させることを特徴とする付記１３記載の評価プログラム。
（付記１５）
前記複数のコンテンツに対する縮小後の各カウント値の小数点以下を切り上げることで整数値にさせることを特徴とする付記１３又は１４記載の評価プログラム。
【００７５】
（付記１６）
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各カウント値に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なわせることを特徴とする付記１３〜１５のいずれか１項に記載の評価プログラム。
【００７６】
（付記１７）
複数のコンテンツのうちの評価対象コンテンツについての評価値を推定する評価プログラムを記録したコンピュータ読取可能な記録媒体であって、
前記評価プログラムが、コンピュータに、
前記複数のコンテンツに対する各カウント値の合計値が所定値に達したかを確認させ、
前記複数のコンテンツに対する各カウント値の合計値が前記所定値に達した場合に、前記複数のコンテンツの各カウント値を縮小させ、
前記評価対象コンテンツに対するカウント値と前記複数のコンテンツに対する各カウント値の合計値とに基づき、評価値推定アルゴリズムを用いて前記評価対象コンテンツの評価値を算出させることを特徴とする評価プログラムを記録したコンピュータ読取可能な記録媒体。
【００７７】
（付記１８）
前記複数のコンテンツの各カウント値を（１−α）倍（ただし、０＜α＜１）することにより縮小させることを特徴とする、付記１７記載の評価プログラムを記録したコンピュータ読取可能な記録媒体。
（付記１９）
前記複数のコンテンツに対する縮小後の各カウント値の小数点以下を切り上げることで整数値にさせることを特徴とする付記１７又は１８記載の評価プログラムを記録したコンピュータ読取可能な記録媒体。
【００７８】
（付記２０）
前記評価値推定アルゴリズムは、Space Savingアルゴリズムであり、
前記複数のコンテンツに対する縮小後の各カウント値に合わせて、前記Space SavingアルゴリズムのStream-Summaryデータ構造におけるバケットの関連付けを行なわせることを特徴とする付記１７〜１９のいずれか１項に記載の評価プログラムを記録したコンピュータ読取可能な記録媒体。
【符号の説明】
【００７９】
１    分散ストレージシステム（分散格納システム）
１０    管理サーバ（評価装置）
１１    バケット管理部
１２    要素管理部
１３    カウント合計値管理部
１４    シュリンク処理部（処理部）
１５    バケット情報
１６    要素情報
１８    データ管理部
３０−１〜３０−６，３０    ストレージサーバノード
４０    プロキシサーバ
５０    ＬＡＮ
５１    ネットワーク
６０    クライアント
１０１    ＣＰＵ
１０２    ＲＡＭ
１０３    ＲＯＭ
１０４    キーボード
１０５    ポインティングデバイス
３４，１０６    記憶装置
１０７    ディスプレイ
【図１】
2014016780.tif 000003
【図２】
2014016780.tif 000004
【図３】
2014016780.tif 000005
【図４】
2014016780.tif 000006
【図５】
2014016780.tif 000007
【図６】
2014016780.tif 000008
【図７】
2014016780.tif 000009
【図８】
2014016780.tif 000010