(57)【要約】      （修正有）【課題】スパイクの原因であるデータを効率的に検出する。【解決手段】アクセス数管理方法は、データへのアクセス回数を単位時間毎に計数すると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部１４に格納し、データ格納部１４に格納されている管理データセットの数が所定数に達した場合に、データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除し、データ格納部１４に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する処理を含む。【選択図】図４
2014146246.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
データへのアクセス回数を単位時間毎に計数させると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納させ、
前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させ、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断させる
ことを特徴とするアクセス数管理プログラム。
【請求項２】
前記データ格納部に格納されている管理データセットは、直近の前記単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第１のグループと、直近の前記単位時間より前の単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第２のグループとに分けられ、
前記管理データセットを削除させる処理において、
前記データ格納部に格納されている管理データセットの数が前記所定数に達した場合に、前記第２のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させる
ことを特徴とする請求項１記載のアクセス数管理プログラム。
【請求項３】
前記コンピュータに、さらに、
前記第１のグループに属する管理データセットの数が第２の所定数に達した場合に、前記第１のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させる
ことを特徴とする請求項２記載のアクセス数管理プログラム。
【請求項４】
前記コンピュータに、さらに、
前記単位時間毎に、前記第１のグループに属する管理データセットを前記第２のグループに移動させると共に、前記データ格納部に格納されてから所定時間以上経過した管理データセットを削除させ、
前記管理データセットを前記データ格納部に格納させる処理において、
直近の前記単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットを、前記データ格納部における前記第１のグループの領域に格納させる
ことを特徴とする請求項２記載のアクセス数管理プログラム。
【請求項５】
データ格納部と、
データへのアクセス回数を単位時間毎に計数し、当該アクセス回数と当該データの識別情報とを含む管理データセットを前記データ格納部に格納すると共に、前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除する第１処理部と、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する第２処理部と
を有するアクセス数管理装置。
【請求項６】
コンピュータが、
データへのアクセス回数を単位時間毎に計数すると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納し、
前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除し、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する
ことを特徴とするアクセス数管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクセス数管理プログラム、アクセス数管理装置及びアクセス数管理方法に関する。
【背景技術】
【０００２】
分散ストレージシステムは、例えばＨＤＤ（Hard Disk Drive）或いはＳＳＤ（Solid State Drive）のようなストレージ装置を備えたサーバを複数台有するストレージシステムである。近年、ビッグデータと呼ばれるような大量のデータを扱えるようにするため、分散ストレージシステムの研究開発が盛んに行われている。
【０００３】
分散ストレージシステムの特徴として、容易に性能及び容量を拡張できることと、データの複製（レプリカとも呼ばれる）により高信頼性を確保できることとがある。例えばサーバの台数を増減することで、分散ストレージシステムにかかる負荷の変動或いはデータの総容量の変動に容易に対処することができる。また、同じデータの複製を複数のサーバが持つことによってデータの冗長化を行い、データの可用性及び耐久性を向上させることができる。
【０００４】
このような分散ストレージシステムに関して、スパイクと呼ばれる負荷パターンが引き起こす性能劣化が問題になっている。スパイクは、特定のデータにのみアクセスが集中するような負荷パターンのことである。アクセスは特定のデータにのみ集中しているため、単純にサーバの台数を増やしたとしてもデータの複製を持っているノードにしかアクセスが行われず、性能劣化を防ぐことができない。
【０００５】
性能劣化を防ぐためには、スパイクの原因であるデータを短時間（例えば数秒程度）で検出してデータの複製を増やすことが求められる。但し、スパイクは頻繁に起こる事象ではなく稀に発生する事象であるため、スパイクを検出するために定常的に多くのリソースを消費することは好ましくない。よって、スパイクの原因であるデータを多くのリソースを使用することなく効率的に検出することが求められる。
【０００６】
アクセス頻度の解析に関して、スペースセービングアルゴリズム（Space-Saving algorithm）というアルゴリズムが知られている。スペースセービングアルゴリズムは、データの人気度を誤差εで求めるアルゴリズムである。スペースセービングアルゴリズムを利用したアクセス頻度の解析について、図１乃至図３に示した例を用いて説明する。
【０００７】
図１においては、バケット１０１乃至１０３と、要素１０４乃至１０７とが示されている。バケットは、カウンタの値が同じである要素をリストによって管理する機構（例えばインスタンス）である。要素は、データの人気度を管理する機構（例えばインスタンス）であり、値としてデータの識別情報とカウンタの値とを含む。ここで、要素数の上限は１／εであり、固定されている。バケットが管理する要素のカウンタの値が大きいほどバケットは右側に配置され、同じカウンタの値を含む要素はリストによって連結される。
【０００８】
図２を用いて、図１に示した状態においてメインページにアクセスがあった場合について説明する。メインページにアクセスがあった場合、要素１０６のカウンタの値がインクリメントされ、要素１０８になる。ここで、バケット１０２が管理する要素は無くなり、バケット１０２は不要になるため、バケット１０２はバケット１０３にマージされる。
【０００９】
図３を用いて、図２の下段に示した状態においてＭ氏作品の記事にアクセスがあった場合について説明する。なお、図３における要素数の上限１／εは４とする。図２の下段に示した状態においては、Ｍ氏作品の記事についての要素が無い。但し、要素数は上限である４に達しているため、単純に要素を追加することはできない。そこで、スペースセービングアルゴリズムにおいては、要素のうちカウンタの値が最少である要素１０４（ここでは、検索ページについての要素）を削除し、Ｍ氏作品についての要素１１０を追加する。ここで、要素１１０のカウンタの値は、要素１０４のカウンタの値を１インクリメントした「９１」とする。また、カウンタの値が９１である要素を管理するためのバケット１０９がバケット１０１とバケット１０３との間に追加される。
【００１０】
スペースセービングアルゴリズムは、アクセス数の計数に利用する要素の数が１／εであり、固定されている。そのため、例えばビッグデータのように多種多様なデータにアクセスが行われる場合であっても、リソース（例えばメモリ）の使用量は一定である。しかし、カウンタの値は、スペースセービングアルゴリズムの実行を開始した時点から現時点までのアクセス回数の累計である。すなわち、データに人気が無かった期間のアクセス回数を含むアクセス回数が計数される。そのため、長時間スペースセービングアルゴリズムを実行した後に急激にアクセス数が増加するようなケースが発生した場合には対処することができない。
【００１１】
また、アクセス履歴の管理に関して以下のような技術が存在する。具体的には、アクセス履歴管理手段は、メインメモリ上にファイルごとのアクセス履歴を作成する。アクセス履歴管理手段は、アクセス履歴の作成から一定時間経過後、１つのアクセス履歴セルチェーン中に生成日が同一であるアクセス履歴セルが複数ある場合にはそれらを１つのアクセス履歴セルへ統合する。また、アクセス履歴管理手段は、さらに所定の時間が経過した後は、アクセス履歴セルチェーンからアクセス履歴を削除する。しかし、この技術においては、アクセス履歴の統合或いは削除が行われるまでに多数のファイルにアクセスが行われた場合には、一時的に多量のデータを保持することになる。すなわち、リソースを大量に消費するため効率的ではない。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi, "Efficient computation of frequent and top-k elements in data streams", ICDT'05 Proceedings of the 10th international conference on Database Theory, p.398-412, 2005
【特許文献】
【００１３】
【特許文献１】特開２０１１−１００４１９号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
従って、本発明の目的は、１つの側面では、スパイクの原因であるデータを効率的に検出するための技術を提供することである。
【課題を解決するための手段】
【００１５】
本発明に係るアクセス数管理方法は、データへのアクセス回数を単位時間毎に計数すると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納し、データ格納部に格納されている管理データセットの数が所定数に達した場合に、データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除し、データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する処理を含む。
【発明の効果】
【００１６】
スパイクの原因であるデータを効率的に検出できるようになる。
【図面の簡単な説明】
【００１７】
【図１】図１は、スペースセービングアルゴリズムについて説明するための図である。
【図２】図２は、スペースセービングアルゴリズムについて説明するための図である。
【図３】図３は、スペースセービングアルゴリズムについて説明するための図である。
【図４】図４は、本実施の形態におけるシステム概要を示す図である。
【図５】図５は、単位時間が経過する毎に行われる処理について説明するための図である。
【図６】図６は、単位時間が経過する毎に行われる処理について説明するための図である。
【図７】図７は、単位時間が経過する毎に行われる処理について説明するための図である。
【図８】図８は、要素について説明するための図である。
【図９】図９は、バケットについて説明するための図である。
【図１０】図１０は、データへのアクセスがあった際に要素及びバケットを特定する方法について説明するための図である。
【図１１】図１１は、メインの処理フローを示す図である。
【図１２】図１２は、要素の移動について説明するための図である。
【図１３】図１３は、要素の移動について説明するための図である。
【図１４】図１４は、古い要素の削除について説明するための図である。
【図１５】図１５は、古い要素の削除について説明するための図である。
【図１６】図１６は、要素を追加した場合におけるリストの管理の具体例を示す図である。
【図１７】図１７は、要素を削除した場合におけるリストの管理の具体例を示す図である。
【図１８】図１８は、カウント処理の処理フローを示す図である。
【図１９】図１９は、カウント処理の具体例を示す図である。
【図２０】図２０は、カウント処理の具体例を示す図である。
【図２１】図２１は、カウント処理の具体例を示す図である。
【図２２】図２２は、カウント処理の具体例を示す図である。
【図２３】図２３は、スパイクの原因であるデータを検出する処理の処理フローを示す図である。
【図２４】図２４は、負荷分散について説明するための図である。
【図２５】図２５は、負荷分散について説明するための図である。
【図２６】図２６は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１８】
本実施の形態におけるシステム概要を図４に示す。例えばインターネットであるネットワーク５には、ユーザ端末３１乃至３３とサーバ１とが接続されている。ユーザ端末３１乃至３３は、ウェブページの閲覧等を要求するリクエストをサーバ１に送信する。これに応じ、ウェブページ等のデータを含むレスポンスをユーザ端末３１乃至３３に送信する。ユーザ端末３１乃至３３は、サーバ１から受信したレスポンスに含まれるデータをユーザ端末３１乃至３３の表示画面等に表示することにより、ユーザがウェブページ等を閲覧できるようにする。サーバ１は、負荷分散のため複数設けられている。
【００１９】
サーバ１は、受信部１１と、リクエスト処理部１２と、更新部１３と、データ格納部１４と、検出部１５と、移動部１６と、タイマ１７とを含む。
【００２０】
受信部１１は、ユーザ端末３１乃至３３から受信したリクエストを、リクエスト処理部１２及び更新部１３に出力する。リクエスト処理部１２は、受信部１１からリクエストを受け取ると、リクエストに応じた処理を実行する。例えば、リクエストにおいて指定されているデータを図示しないＨＤＤ等から読み出し、リクエストの送信元のユーザ端末に送信する。更新部１３は、受信部１１から受け取ったリクエストに含まれるデータ（例えば、アクセスするデータの識別情報）を用いて、データ格納部１４に格納されているデータを更新する。タイマ１７は、所定の単位時間（例えば数秒）が経過する毎に、単位時間が経過したことを移動部１６に通知する。移動部１６は、単位時間が経過する毎に、データ格納部１４に格納されているデータを更新する処理を実行する。検出部１５は、データ格納部１４に格納されているデータを用いて、スパイクの原因であるデータを検出する。
【００２１】
次に、図５乃至図７を用いて、単位時間が経過する毎に行われる処理について説明する。本実施の形態は、図１乃至図３を用いて説明したスペースセービングアルゴリズムの考え方を取り入れるが、通常のスペースセービングアルゴリズムと異なり要素は２つのグループに分類される。図５に示すように、要素は、カウントサイドと呼ばれるグループと、履歴サイドと呼ばれるグループとに分類される。カウントサイドに属する要素はアクセス回数を計数するための要素であり、履歴サイドに属する要素はアクセス回数の履歴を保持するための要素である。図５において、カウントサイドに属する要素は要素５０１及び５０２であり、履歴サイドに属する要素は要素５０３乃至５０６である。以下では、バケットの上に配置されている要素をカウントサイドの要素とし、バケットの下に配置されている要素を履歴サイドの要素とする。
【００２２】
カウントサイドにおいては、単位時間におけるアクセス回数がデータ毎に計数される。図５の例では、「４０４エラー」というデータに９０回アクセスがあり、「Ｍ氏記事」というデータに９９回アクセスがある。単位時間が経過すると、要素数が少ないカウントサイドに属する要素は、移動部１６によって、要素数が多い履歴サイドに移動される。図６の例では、カウントサイドに属する要素５０１及び５０２が履歴サイドに移動される。カウンタの値が９０である要素は要素５０１以外にも存在するため、要素５０１は要素５０４の右側に連結される。さらに、図７に示すように、単位時間が経過すると古い要素である要素５０３は削除される。なお、「古い要素」とは、所定時間（例えば単位時間の数倍の長さである時間）以上前に生成された要素である。図７において、カウントサイドに属する要素は無いが、次の単位時間内にデータに対するアクセスがあると、カウントサイドに要素が生成される。
【００２３】
図８及び図９を用いて、要素及びバケットについて説明する。本実施の形態における要素は、図８の８０１に示したようなクラスにより実現される。図８の８０２は、クラス８０１から生成されたインスタンスの値の一例である。この例では、インスタンスの値には、データの識別情報と、カウンタの値と、カウントサイドに属する場合において前に接続されている要素の識別情報と、カウントサイドに属する場合において後に接続されている要素の識別情報と、管理するバケットについての情報と、履歴サイドに属する場合において前に接続されている要素の識別情報と、履歴サイドに属する場合において後に接続されている要素の識別情報とが含まれる。
【００２４】
また、本実施の形態におけるバケットは、図９の９０１に示したようなクラスにより実現される。図９の９０２は、クラス９０１から生成されたインスタンスの値の一例である。この例では、インスタンスの値には、カウントサイドにおける先頭の要素の識別情報と、カウントサイドにおける末尾の要素の識別情報と、履歴サイドにおける先頭の要素の識別情報と、履歴サイドにおける末尾の要素の識別情報と、左側に接続されているバケットの識別情報と、右側に接続されているバケットについての識別情報とが含まれる。
【００２５】
図８及び図９に示したようなインスタンスの値は、データ格納部１４に格納される。
【００２６】
なお、図８において「ｏｗｎｅｒ」が定義されているのは、要素を高速に見つけるためである。これについて、図１０を用いて説明する。図１０に示すように、データへのアクセスがあった場合には、要素名（又はデータの識別情報）と要素とを対応付けたハッシュ表１００１を調べる（図１０における（１））。ハッシュ表を調べることにより、要素を特定することができる（図１０における（２））。ここで、要素における「ｏｗｎｅｒ」の値を参照すれば、要素が属するバケットを特定することができる（図１０における（３））。なお、理論上は、バケットが管理する要素を１つずつ探せばよいので「ｏｗｎｅｒ」は不要であるが、かかる時間のオーダーはＯ記法でＯ（最大要素数）であるため、要素を見つけるのに非常に時間がかかる。そこで、このような方法を採用する。
【００２７】
次に、図１１乃至図２５を用いて、サーバ１の動作について説明する。まず、図１１乃至図２２を用いて、単位時間毎に行う処理及びアクセスが有った場合に行う処理について説明する。
【００２８】
まず、サーバ１における移動部１６は、停止条件を満たすか判断する（図１１：ステップＳ１）。停止条件とは、例えば、ユーザからサーバ１の停止を指示されるという条件である。停止条件を満たす場合（ステップＳ１：Ｙｅｓルート）、処理を終了する。一方、停止条件を満たさない場合（ステップＳ１：Ｎｏルート）、移動部１６は、前回の処理（ここでは、ステップＳ５及びＳ７の処理）から単位時間が経過したか判断する（ステップＳ３）。タイマ１７から単位時間が経過したことを通知されていれば、移動部１６は、前回の処理から単位時間が経過したと判断する。
【００２９】
前回の処理から単位時間が経過した場合（ステップＳ３：Ｙｅｓルート）、移動部１６は、カウントサイドに属する要素を履歴サイドに移動する（ステップＳ５）。具体的には、移動部１６は、データ格納部１４に格納されている、カウントサイドにおける要素についてのデータ（例えば、接続関係に関する値）を書き換える。
【００３０】
移動部１６は、データ格納部１４に格納されている、履歴サイドにおける古い要素についてのデータを削除する（ステップＳ７）。そしてステップＳ１の処理に戻る。
【００３１】
図１２及び図１３を用いて、要素の移動について説明する。本実施の形態においては、移動部１６及び更新部１３が、図１２の１１２０に示すような、要素のリストからなる固定長の循環配列をデータ格納部１４において管理する。図１２においては、実線１１０１に接続されている要素は現在のフェイズで追加した要素のリストに含まれる要素であり、一点鎖線１１０２に接続されている要素は１つ前のフェイズで追加した要素のリストに含まれる要素であり、点線１１０３に接続されている要素は２つ前のフェイズで追加した要素のリストに含まれる要素である。「フェイズ」とは、移動部１６が処理を行ってから次に処理を行うまでの段階（この段階の長さは単位時間である）のことである。
【００３２】
ステップＳ５においては、例えば図１３に示すように、移動部１６は、現在のフェイズで追加した要素（図１３の例では、要素１１０４及び１１０５）を履歴サイドに移動する。但し、移動部１６は、図１２の１１２０に示したリストの構造自体は変えず、要素の順序を維持したままにする。
【００３３】
図１４及び図１５を用いて、古い要素の削除について説明する。図１４の例では、３つ以上前のフェイズで追加した要素が古い要素であるとする。この場合、２つ前のフェイズで追加した要素のリストに含まれる要素１１０６は、次は３つ前のフェイズで追加した要素のリストに含まれる要素になるため、ステップＳ７の処理により削除される。古い要素の削除が完了すると、図１５に示すように、現在のフェイズで追加した要素のリストは１つ前のフェイズで追加した要素のリストになり、１つ前のフェイズで追加した要素のリストは２つ前のフェイズで追加した要素のリストになる。但し、リストにおける要素の順序は変更されない。
【００３４】
本実施の形態におけるリストの管理について、図１６及び図１７に他の具体的を示す。図１６に、要素を追加した場合におけるリストの管理の具体例を示す。図１６の例では、現在のフェイズで追加した要素のリストの先頭に要素１１０９が追加されている。元々、現在のフェイズで追加した要素のリストには要素１１０８が含まれていたため、要素の追加後のリストにおいては、要素１１０８と要素１１０９とが連結されている。なお、他のリストにおける要素の順序は変更されない。
【００３５】
図１７に、要素を削除した場合におけるリストの管理の具体例を示す。図１７においては、１つ前のフェイズで追加した要素のリストに含まれる要素１１１０が削除される。この場合、１つ前のフェイズで追加した要素のリストに元々含まれている要素１１１１は、このリストに先頭になる。なお、他のリストにおける要素の順序は変更されない。
【００３６】
図１１の説明に戻り、前回の処理から単位時間が経過していない場合（ステップＳ３：Ｎｏルート）、更新部１３は、サーバ１が保持するデータに対するアクセスが有るか判断する（ステップＳ９）。ステップＳ９においては、更新部１３は、受信部１１からリクエストを受け取ったか否かにより判断する。
【００３７】
データに対するアクセスが無い場合（ステップＳ９：Ｎｏルート）、データ格納部１４に格納されているデータを更新しなくてもよいため、ステップＳ１の処理に戻る。データに対するアクセスが有る場合（ステップＳ９：Ｙｅｓルート）、更新部１３は、カウント処理を実行する（ステップＳ１１）。カウント処理については、図１８乃至図２２を用いて説明する。なお、カウント処理については、アクセスが有ったデータをデータＤとする。
【００３８】
更新部１３は、カウントサイドにデータＤについての要素が含まれるか判断する（図１８：ステップＳ２１）。カウントサイドにデータＤについての要素が含まれるか否かは、例えば図１０に示したハッシュ表にデータＤに対応する要素があるか否かによって判断する。
【００３９】
カウントサイドにデータＤが含まれる場合（ステップＳ２１：Ｙｅｓルート）、カウントサイドにおけるデータＤについての要素を更新すればよいので、更新部１３は、カウントサイドにおいて、データＤについてのカウンタの値をインクリメントする（ステップＳ２３）。
【００４０】
図１９を用いて、ステップＳ２３の処理について具体的に説明する。ステップＳ２３において履歴サイドに属する要素は関係しないので、図１９において履歴サイドは省略する。例えば図１９の上段に示すような状態である場合において、「Ｍ氏記事」というデータにアクセスがあったとする。ここで、「Ｍ氏記事」というデータについての要素はカウントサイドに含まれる要素１９０１である。従って、ステップＳ２３の処理によって、要素１９０１のカウンタの値をインクリメントする。すると、図１９の下段に示すような状態になる。「Ｍ氏記事」というデータのアクセス回数は６回であったが、ステップＳ２３の処理によって７回に更新される。また、カウンタの値が７である要素１９０１を管理するバケット１９０２が追加される。
【００４１】
図１８の説明に戻り、カウントサイドにデータＤについての要素が含まれない場合（ステップＳ２１：Ｎｏルート）、更新部１３は、Ｗ＝１／εであるか判断する（ステップＳ２５）。ここで、Ｗはカウントサイドに含まれる要素の数であり、εは誤差係数である。１／εは、カウントサイドに含まれる要素の数の上限を表す。１／εは、例えば数千程度の値である。
【００４２】
Ｗ＝１／εである場合（ステップＳ２５：Ｙｅｓルート）、更新部１３は、カウントサイドにおいてカウンタの値が最少である要素をデータ格納部１４から削除する（ステップＳ２７）。また、更新部１３は、データＤについての要素を、カウンタの値＝（ステップＳ２７において削除された要素のカウンタの値＋１）としてカウントサイドに追加する（ステップＳ２９）。
【００４３】
図２０を用いて、ステップＳ２７及びＳ２９の処理について具体的に説明する。ステップＳ２７及びＳ２９において履歴サイドに属する要素は関係しないので、図２０において履歴サイドは省略する。例えば図２０の上段に示すような状態である場合において、「Ｍ氏作品の記事」というデータにアクセスがあったとする。ここで、「Ｍ氏作品の記事」というデータについての要素はカウントサイドに含まれていない。従って、ステップＳ２７の処理によって、カウントサイドにおいてカウンタの値が最少である要素２００１は削除される。また、ステップＳ２９の処理によって、「Ｍ氏作品の記事」というデータについての要素がカウントサイドに追加される。ここで、追加された要素のカウンタの値は、削除された要素のカウンタの値である１＋１＝２である。カウンタの値が１である要素を管理するバケット２００２は削除され、カウンタの値が２である要素を管理するバケット２００４が追加される。これらの処理によって、図２０の下段に示すような状態になる。
【００４４】
図１８の説明に戻り、Ｗ＝１／εではない場合（ステップＳ２５：Ｎｏルート）、更新部１３は、Ｗ＋Ｈ＝（１／ε）＋Ｃであるか判断する（ステップＳ３１）。ここで、Ｈは履歴サイドに属する要素の数であり、Ｃは履歴サイドに残る要素の個数を表す。Ｃは、例えば数十程度の値であり、１／εと比較して十分に小さな値である。
【００４５】
なお、以上のような定義をすると、カウントサイドに属する要素の数の最大値は１／εであり、履歴サイドに属する要素の数の最大値は（１／ε）＋Ｃである。これにより、履歴サイドにおいてカウンタの値が上位Ｃ位内の要素は履歴サイドに残ることになる。
【００４６】
Ｗ＋Ｈ＝（１／ε）＋Ｃではない場合（ステップＳ３１：Ｎｏルート）、更新部１３は、データＤについての要素を、カウンタの値＝１としてカウントサイドに追加する（ステップＳ３５）。
【００４７】
図２１を用いて、ステップＳ３１のＮｏルートに進む場合の処理について具体的に説明する。例えば要素及びバケットが図２１の上段に示すような状態である場合において、１／ε＝４且つＣ＝２である、すなわち（１／ε）＋Ｃ＝６であるとする。この場合、カウントサイドにおける要素の数と履歴サイドにおける要素の数との合計は上限である６に達していない。よって、ステップＳ３５の処理によって、「検索ページ」というデータについての要素２１０１がカウントサイドに追加される。ここで、追加された要素のカウンタの値は１である。また、カウンタの値が１である要素を管理するバケット２１０２が追加される。これらの処理によって、図２２の下段に示すような状態になる。
【００４８】
Ｗ＋Ｈ＝（１／ε）＋Ｃである場合（ステップＳ３１：Ｙｅｓルート）、更新部１３は、履歴サイドにおいてカウンタの値が最少である要素をデータ格納部１４から削除する（ステップＳ３３）。更新部１３は、また、更新部１３は、データＤについての要素を、カウンタの値＝１としてカウントサイドに追加する（ステップＳ３５）。そして処理を終了する。
【００４９】
図２２を用いて、ステップＳ３１のＹｅｓルートに進む場合の処理について具体的に説明する。例えば要素及びバケットが図２２の上段に示すような状態である場合において、１／ε＝４且つＣ＝２である、すなわち（１／ε）＋Ｃ＝６であるとする。この場合、カウントサイドにおける要素の数と履歴サイドにおける要素の数との合計は上限である６に達している。よって、ステップＳ３３の処理によって、履歴サイドにおいてカウンタの値が最少である要素２２０３が削除される。また、ステップＳ３５の処理によって、「検索ページ」というデータについての要素２２０１がカウントサイドに追加される。ここで、追加された要素のカウンタの値は１である。また、カウンタの値が１である要素を管理するバケット２２０２が追加される。これらの処理によって、図２２の下段に示すような状態になる。
【００５０】
以上のように、スペースセービングアルゴリズムの考え方を取り入れた本実施の形態の方法であれば、高速に処理を行うことができる。また、例えばビッグデータのようにアクセス対象のデータが多種多様であっても、要素数の上限を（１／ε）＋Ｃと定めているので、リソースの使用量は一定である。また、システムが動作を開始してから長時間経過した後に突発的なスパイクが発生したとしても、スパイクの原因であるデータを検出可能である。これは、動作開始時点から現時点までのアクセス回数ではなく、単位時間毎に計数したアクセス回数を利用しているためである。
【００５１】
なお、Ｗ＋Ｈの値が上限に達している場合、カウントサイドに新しい要素が来るたびに、履歴サイドにおいてはカウンタの値が最少である要素が削除される。ここで、ｋを古いとみなされる要素を決定するための係数とし、Ｔを単位時間の長さとする。すると、移動部１６が定期的に（すなわち単位時間毎に）処理を行う際、ｋＴ秒前からＴ秒前までの期間においてカウンタの値が上位Ｃ位内の要素が履歴サイドに残ることになる。この時、カウントサイドにはＴ秒前から現在までに生成された要素があるため、要素の移動処理が終わった段階での履歴サイドにおいてカウンタの値が上位Ｃ位内の要素は、ｋＴ秒前から現在に至るまでの間でカウンタの値が上位Ｃ位内の要素と同じになる。
【００５２】
スペースセービングアルゴリズムの考え方を取り入れているためカウンタの値は実際のアクセス数とは若干異なる値になるが、１／εをうまく選べばカウンタの値はアクセス回数とほとんど同じ回数になる。よって、カウンタの値が上位Ｃ位内の要素は、ｋＴ秒間中にアクセス頻度が上位Ｃ位内の要素とみなすことができる。検出部１５は、この上位Ｃ位内の要素のみを探せば、スパイクの原因となっているデータを見つけることができる。また、要素数は最大でも（１／ε）＋Ｃ個であるため、データの種類が多様になってもそれに比例してメモリを消費することがなくなり、省メモリを実現できる。
【００５３】
次に、図２３乃至図２５を用いて、スパイクの原因であるデータを検出する処理について説明する。
【００５４】
まず、検出部１５は、データ格納部１４に格納されているアクセス回数を解析することにより、スパイクの発生に関する条件を満たすデータが有るか判断する（ステップＳ４１）。ステップＳ４１においては、例えば、直近の単位時間における特定のデータへのアクセス回数が所定の閾値以上であるという条件を満たすか判断する。また、例えば、特定のデータへのアクセス回数の増加率が所定の閾値以上であるという条件を満たすか判断する。
【００５５】
スパイクの発生に関する条件を満たすデータが無い場合（ステップＳ４１：Ｎｏルート）、ステップＳ４１の処理に戻る。一方、スパイクの発生に関する条件を満たすデータが有る場合（ステップＳ４１：Ｙｅｓルート）、検出部１５は、負荷分散のための処理を実行する（ステップＳ４３）。そして処理を終了する。
【００５６】
図２４及び図２５を用いて、負荷分散のための処理について説明する。図２４及び図２５において、サーバ２４０１乃至２４０９はアクセスの対象となるデータをＨＤＤに保持するサーバであり、サーバ２４１０乃至２４１２はリクエストの割り振りを行うサーバである。例えば図２４に示すように、著名であるＭ氏が死去したというニュースが有り、非常に多くのユーザがＭ氏の死去に関する記事を閲覧しようとしたと仮定する。Ｍ氏の死去に関する記事のデータを保持するサーバは、サーバ２４０１、２４０５及び２４０９である。ここで、ユーザ端末からのアクセスが想定よりもはるかに多いような場合には、Ｍ氏の死去に関する記事のデータを保持するサーバ２４０１、２４０５及び２４０９のレスポンスが低下することになる。そして、ユーザはＭ氏の死去に関する記事を閲覧することができなくなる。
【００５７】
そこで、本実施の形態におけるステップＳ４３においては、例えば図２５に示すような処理を実行する。具体的には、スパイクの原因である、Ｍ氏の死去に関する記事のデータを検出したサーバ２４０９が、当該データの複製を追加するように他のサーバ（ここでは、サーバ２４０３、２４０６及び２４０７）に要求する。これに応じて、サーバ２４０３、２４０６及び２４０７はＭ氏の死去に関する記事のデータをＨＤＤに追加する。また、サーバ２４０９は、リクエストの割り振りを行うサーバ２４１０乃至２４１２に、サーバ２４０３、２４０６及び２４０７に対してもリクエストを割り振るように要求する。これにより、サーバ２４０１、２４０３、２４０５、２４０６、２４０７及び２４０９にリクエストが割り振られるようになり、サーバ２４０１、２４０５及び２４０９は性能劣化から回復する。そして、ユーザはＭ氏の死去に関する記事を閲覧できるようになる。
【００５８】
なお、ここではサーバ２４０９に性能劣化が発生する例を示したが、本実施の形態の処理によれば、スパイクの原因であるデータを高速で検出できるため、性能劣化が発生する前に負荷分散を行うことが可能である。
【００５９】
以上本発明の一実施の形態を説明したが、本発明はこれに限定されるものではない。例えば、上で説明したサーバ１の機能ブロック構成は実際のプログラムモジュール構成に一致しない場合もある。
【００６０】
また、上で説明した各テーブルの構成は一例であって、上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００６１】
なお、カウンタサイドから履歴サイドに要素を移動する際、バケットに履歴サイドの要素が既に存在する場合がある。このような場合、履歴サイドが元々履歴サイドであれば、移動する要素をリストの最後尾に連結する。一方、履歴サイドが元々はカウントサイドであった場合には、移動する要素をリストの先頭に連結する。このようにすることで、それまで履歴サイドにあった要素ほどリストの先頭に近付くようになる。
【００６２】
なお、上で述べたサーバ１及びユーザ端末３１乃至３３は、コンピュータ装置であって、図２６に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本発明の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００６３】
以上述べた本発明の実施の形態をまとめると、以下のようになる。
【００６４】
本実施の形態に係るアクセス数管理方法は、（Ａ）データへのアクセス回数を単位時間毎に計数すると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納し、（Ｂ）データ格納部に格納されている管理データセットの数が所定数に達した場合に、データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除し、（Ｃ）データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する処理を含む。
【００６５】
このようにすれば、データ格納部に格納されるアクセス回数は累積のアクセス回数ではなくなり、またアクセス回数が多いデータについての管理データセットほどデータ格納部に残るので、スパイクの原因であるデータを効率的に検出できるようになる。
【００６６】
また、上で述べたデータ格納部に格納されている管理データセットは、直近の単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第１のグループと、直近の単位時間より前の単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第２のグループとに分けられていてもよい。そして、上で述べた管理データセットを削除する処理において、（ｂ１）データ格納部に格納されている管理データセットの数が所定数に達した場合に、第２のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除してもよい。このようにすれば、直近の単位時間におけるアクセス回数を含む管理データセットは削除されないので、直近の単位時間におけるアクセス回数が検出の結果に反映されやすくなる。
【００６７】
また、本アクセス数管理方法が、（Ｄ）第１のグループに属する管理データセットの数が第２の所定数に達した場合に、１のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除する処理をさらに含んでもよい。このようにすれば、第１のグループに属する管理データセットによってデータ格納部が占有されることがなくなる。
【００６８】
また、本アクセス数管理方法が、（Ｅ）単位時間毎に、第１のグループに属する管理データセットを第２のグループに移動すると共に、データ格納部に格納されてから所定時間以上経過した管理データセットを削除する処理をさらに含んでもよい。そして、上で述べた管理データセットをデータ格納部に格納させる処理において、（ａ１）直近の単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットを、データ格納部における第１のグループの領域に格納してもよい。このようにすれば、単位時間毎の計数を適切に行うことができるようになると共に、古い管理データセットを参照しないことを保証できるようになる。
【００６９】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００７０】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７１】
（付記１）
コンピュータに、
データへのアクセス回数を単位時間毎に計数させると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納させ、
前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させ、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断させる
ことを特徴とするアクセス数管理プログラム。
【００７２】
（付記２）
前記データ格納部に格納されている管理データセットは、直近の前記単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第１のグループと、直近の前記単位時間より前の単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットが属する第２のグループとに分けられ、
前記管理データセットを削除させる処理において、
前記データ格納部に格納されている管理データセットの数が前記所定数に達した場合に、前記第２のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させる
ことを特徴とする付記１記載のアクセス数管理プログラム。
【００７３】
（付記３）
前記コンピュータに、さらに、
前記第１のグループに属する管理データセットの数が第２の所定数に達した場合に、前記第１のグループに属する管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除させる
ことを特徴とする付記２記載のアクセス数管理プログラム。
【００７４】
（付記４）
前記コンピュータに、さらに、
前記単位時間毎に、前記第１のグループに属する管理データセットを前記第２のグループに移動させると共に、前記データ格納部に格納されてから所定時間以上経過した管理データセットを削除させ、
前記管理データセットを前記データ格納部に格納させる処理において、
直近の前記単位時間におけるアクセス回数とデータの識別情報とを含む管理データセットを、前記データ格納部における前記第１のグループの領域に格納させる
ことを特徴とする付記２記載のアクセス数管理プログラム。
【００７５】
（付記５）
データ格納部と、
データへのアクセス回数を単位時間毎に計数し、当該アクセス回数と当該データの識別情報とを含む管理データセットを前記データ格納部に格納すると共に、前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除する第１処理部と、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する第２処理部と
を有するアクセス数管理装置。
【００７６】
（付記６）
コンピュータが、
データへのアクセス回数を単位時間毎に計数すると共に、当該アクセス回数と当該データの識別情報とを含む管理データセットをデータ格納部に格納し、
前記データ格納部に格納されている管理データセットの数が所定数に達した場合に、前記データ格納部に格納されている管理データセットのうち当該管理データセットに含まれるアクセス回数が最少である管理データセットを削除し、
前記データ格納部に格納されている管理データセットに含まれるアクセス回数を用いて、アクセスの急増に関する条件を満たすデータが有るか判断する
ことを特徴とするアクセス数管理方法。
【符号の説明】
【００７７】
１  サーバ    １１  受信部
１２  リクエスト処理部    １３  更新部
１４  データ格納部    １５  検出部
１６  移動部    １７  タイマ
３１，３２，３３  ユーザ端末    ５  ネットワーク
【図１】
2014146246.tif 000003
【図２】
2014146246.tif 000004
【図３】
2014146246.tif 000005
【図４】
2014146246.tif 000006
【図５】
2014146246.tif 000007
【図６】
2014146246.tif 000008
【図７】
2014146246.tif 000009
【図８】
2014146246.tif 000010
【図９】
2014146246.tif 000011
【図１０】
2014146246.tif 000012
【図１１】
2014146246.tif 000013
【図１２】
2014146246.tif 000014
【図１３】
2014146246.tif 000015
【図１４】
2014146246.tif 000016
【図１５】
2014146246.tif 000017
【図１６】
2014146246.tif 000018
【図１７】
2014146246.tif 000019
【図１８】
2014146246.tif 000020
【図１９】
2014146246.tif 000021
【図２０】
2014146246.tif 000022
【図２１】
2014146246.tif 000023
【図２２】
2014146246.tif 000024
【図２３】
2014146246.tif 000025
【図２４】
2014146246.tif 000026
【図２５】
2014146246.tif 000027
【図２６】
2014146246.tif 000028