(57)【特許請求の範囲】
【請求項１】
分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれによって分散して管理されたキー情報及び値情報を含むレコードに対するガベージコレクション処理が、各サーバがそれぞれ有し、容量をランダムに変化させた複数の部分テーブルごとの分割時に実行されるように、前記部分テーブルごとのガベージコレクション処理の実行時期を決定する決定部と、
前記決定部によって決定された実行時期に、対象となる部分テーブルに対するガベージコレクション処理を実行する実行部と、
を備えたことを特徴とするガベージコレクション実行装置。
【請求項２】
前記決定部は、前記部分テーブルの分割時に前記ガベージコレクション処理が実行される場合に、分割後の容量が所定の範囲内で変化するように前記部分テーブルを分割させ、
前記実行部は、前記部分テーブルの分割時にガベージコレクション処理を実行することを特徴とする請求項１に記載のガベージコレクション実行装置。 
【請求項３】
前記決定部は、所定の時間間隔で前記部分テーブルごとに前記ガベージコレクション処理を実行した場合の削減容量を予測し、前記削減容量が最大となる部分テーブルを前記ガベージコレクション処理の対象と決定し、
前記実行部は、前記決定部によって決定された部分テーブルに対するガベージコレクション処理を実行することを特徴とする請求項１に記載のガベージコレクション実行装置。
【請求項４】
前記決定部は、前記レコードが前記部分テーブルに登録された時点から所定の期間が経過した場合に、当該レコードが前記ガベージコレクション処理によって削除されうる削除対象レコードと判定し、前記部分テーブルに含まれる前記削除対象レコードの合計容量を前記削除容量として予測することを特徴とする請求項３に記載のガベージコレクション実行装置。 
【請求項５】
前記実行部は、前記決定部によって前記ガベージコレクション処理の対象として決定された部分テーブルにおける前記削除容量が所定の閾値を上回った場合に、当該部分テーブルに対するガベージコレクション処理を実行することを特徴とする請求項３又は４に記載のガベージコレクション実行装置。 
【請求項６】
分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる装置によって実行されるガベージコレクション実行方法であって、
前記分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれによって分散して管理されたキー情報及び値情報を含むレコードに対するガベージコレクション処理が、各サーバがそれぞれ有し、容量をランダムに変化させた複数の部分テーブルごとの分割時に実行されるように、前記部分テーブルごとのガベージコレクション処理の実行時期を決定する決定工程と、
前記決定工程によって決定された実行時期に、対象となる部分テーブルに対するガベージコレクション処理を実行する実行工程と、
を含んだことを特徴とするガベージコレクション実行方法。 
【請求項７】
分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる装置によって実行されるガベージコレクション実行プログラムであって、
前記分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれによって分散して管理されたキー情報及び値情報を含むレコードに対するガベージコレクション処理が、各サーバがそれぞれ有し、容量をランダムに変化させた複数の部分テーブルごとの分割時に実行されるように、前記部分テーブルごとのガベージコレクション処理の実行時期を決定する決定ステップと、
前記決定ステップによって決定された実行時期に、対象となる部分テーブルに対するガベージコレクション処理を実行する実行ステップと、
を前記装置に実行させることを特徴とするガベージコレクション実行プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ガベージコレクション実行装置、ガベージコレクション実行方法及びガベージコレクション実行プログラムに関する。
【背景技術】
【０００２】
従来、クラウドコンピューティングの進展とともに、分散Ｋｅｙ−Ｖａｌｕｅストアを利用したさまざまなシステムが提案されている。分散Ｋｅｙ−Ｖａｌｕｅストアは、「Ｋｅｙ（キー）」と「Ｖａｌｕｅ（値）」とのペアによってデータを管理するデータベースであり、例えば、Ｇｏｏｇｌｅ（登録商標）社のＢｉｇｔａｂｌｅや、オープンソースのＨＢａｓｅ、Ｈｙｐｅｒｔａｂｌｅなどが知られている。
【０００３】
例えば、ＢｉｇｔａｂｌｅのＰＣクラスタ上のサーバ群それぞれで、いくつかの範囲に分割したテーブル（部分テーブル）を管理する。そして、各サーバにおいては、ログ先行書き込み用ログファイル（以下、ＷＡＬ（Write  Ahead  Logging）ログと記す）が備えられ、書き込み要求に対する永続性が担保される。Ｂｉｇｔａｂｌｅ（分散Ｋｅｙ−Ｖａｌｕｅストア）は、ＧＦＳ(分散ファイルシステム)上にファイルを作成する。
【０００４】
ここで、分散ファイルシステムを利用した分散Ｋｅｙ−Ｖａｌｕｅストアにおいては、一度追加された（Ｋｅｙ,  Ｖａｌｕｅ）は、削除などのオペレーションが実行されたとしても削除フラグの付いた（Ｋｅｙ,  Ｖａｌｕｅ）が新たに追加されるだけで、元の（Ｋｅｙ,  Ｖａｌｕｅ）が削除されない。そのため、不要な（Ｋｅｙ,  Ｖａｌｕｅ）が分散ファイルシステムのディスク容量を無駄に占有し、検索処理効率を低下させてしまう。
【０００５】
そこで、このような分散Ｋｅｙ−Ｖａｌｕｅストアにおいては、各サーバにおいてガベージコレクション処理を実行することによってディスク占有量の適正化を実行する。例えば、分散Ｋｅｙ−Ｖａｌｕｅストアにおけるガベージコレクション処理では、永続化された全ての追加、更新、削除ファイルを一端読み込み、削除するべきレコード群をすべて削除した上で、新たな永続化ファイルを分散ファイルシステム上に作成する。すなわち、ガベージコレクション処理は、全ての情報を分散ファイルシステムから読み込み、ほぼ全ての情報（削除を実行した後のファイル）を分散ファイルシステムに書き込む。
【０００６】
上述したように、分散Ｋｅｙ−Ｖａｌｕｅストアにおけるガベージコレクション処理は、不要なファイルを削除することで、分散ファイルシステムのディスク占有量を削減して検索処理効率を向上させるが、全てのファイルを対象として処理が実行されるため、処理負荷が極めて高く、単純に頻度を上げて実行することができない。すなわち、ガベージコレクション処理の実行時には、ディスク占有量とリソース負荷（例えば、ディスクＩ／Ｏ、ネットワーク、ＣＰＵ（Central  Processing  Unit）などへの負荷）との間のトレードオフの関係が重要となる。
【０００７】
そこで、このような問題に対して、ガベージコレクション処理の実行間隔を設定する手法や、ユーザに対してガベージコレクション処理の実行コマンドを提供する手法、追加されるレコードの増加に伴って実行される部分テーブルの分割時にガベージコレクション処理を実行する手法などが知られている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber, “Bigtable: A Distributed Storage System for Structured Data,” OSDI(2006)
【非特許文献２】S. Ghemawat, H. Gobioff, S.-T. Leung, “The Google File System, ” SOSP(2003)
【非特許文献３】A. Khurana, “HBase,” Hadoop Day(2010)
【非特許文献４】D. Judd, “Hypertable: An Open Source, High Performance, Scalable Database,” OSCON(2008)
【非特許文献５】M. Burrows, “The Chubby lock service for loosely-coupled distributed systems,”OSDI(2006)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、上述した従来技術では、ガベージコレクション処理が短期間に集中して発生することで、リソース負荷が増大する場合があった。例えば、ガベージコレクション処理の実行間隔を設定する手法では、全部分テーブルを対象として１つの実行間隔しか設定することができないため、部分テーブルごとに実行されるガベージコレクション処理の実行タイミングが重なり、負荷分散ができない。また、ユーザに対してガベージコレクション実行コマンドを提供する手法では、ユーザが分散Ｋｅｙ−Ｖａｌｕｅストアに関する十分なスキルを有していない場合、適切なタイミングでガベージコレクション処理を実行することができない。また、上述した部分テーブルの分割時にガベージコレクション処理を実行する手法では、追加されるファイルが増加するに従って部分テーブルの分割が短期間に集中して発生することから、結果的に、ガベージコレクション処理も短期間に集中して発生することとなり、負荷分散ができない。
【００１０】
そこで、本願に係る技術は、上述した従来技術の問題に鑑みてなされたものであって、ガベージコレクションの発生を分散させることで、リソース負荷を分散することを可能にするガベージコレクション実行装置、ガベージコレクション実行方法及びガベージコレクション実行プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、本願に係るガベージコレクション実行装置は、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれにおいて所定の容量で形成された複数の部分テーブルによって分散して管理されたキー情報及び値情報を含むレコードに対するガベージコレクション処理を、前記サーバそれぞれで前記部分テーブルごとに時系列上分散して実行されるように前記部分テーブルごとの実行時期を決定する決定部と、前記決定部によって決定された実行時期に、対象となる部分テーブルに対するガベージコレクション処理を実行する実行部とを備えたことを特徴とする。
【発明の効果】
【００１２】
本願に係るガベージコレクション実行装置は、ガベージコレクションの発生を分散させることで、リソース負荷を分散することを可能にする。
【図面の簡単な説明】
【００１３】
【図１】図１は、第１の実施形態に係る分散ファイルシステムを利用した分散Ｋｅｙ−Ｖａｌｕｅストアの構成の一例を示す図である。
【図２】図２は、第１の実施形態に係るスレーブサーバによるレコードの管理を説明するための図である。
【図３】図３は、第１の実施形態に係るスレーブサーバによるガベージコレクション処理を説明するための図である。
【図４】図４は、従来技術に係る課題を説明するための図である。
【図５】図５は、第１の実施形態に係るスレーブサーバの構成の一例を示す図である。
【図６】図６は、第１の実施形態に係るスレーブサーバによって実行されるエリア分割とガベージコレクション処理の一例を説明するための図である。
【図７】図７は、第１の実施形態に係るガベージコレクション決定部による処理の手順を示すフローチャートである。
【図８】図８は、第１の実施形態に係るガベージコレクション実行部による処理の手順を示すフローチャートである。
【図９】図９は、第２の実施形態に係るガベージコレクション決定部による削除容量の予測を説明するための図である。
【図１０】図１０は、第２の実施形態に係るスレーブサーバによって実行されるガベージコレクション処理の一例を説明するための図である。
【図１１】図１１は、第２の実施形態に係るガベージコレクション決定部による処理の手順を示すフローチャートである。
【図１２】図１２は、第３の実施形態に係るガベージコレクション実行プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１４】
以下に添付図面を参照して、本願に係るガベージコレクション実行装置、ガベージコレクション実行方法及びガベージコレクション実行プログラムの実施形態を詳細に説明する。なお、以下では、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれるスレーブサーバを本願に係るガベージコレクション実行装置として機能させた場合を例に挙げて説明する。また、本願に係るガベージコレクション実行装置、ガベージコレクション実行方法及びガベージコレクション実行プログラムは、以下の実施形態により限定されるものではない。
【００１５】
（第１の実施形態）
まず、分散ファイルシステムを利用した分散Ｋｅｙ−Ｖａｌｕｅストアの一例を説明する。図１は、第１の実施形態に係る分散ファイルシステムを利用した分散Ｋｅｙ−Ｖａｌｕｅストアの構成の一例を示す図である。図１に示すように、第１の実施形態に係る分散ファイルシステムを利用した分散Ｋｅｙ−Ｖａｌｕｅストアは、スレーブサーバ１００Ａ〜１００Ｃと、マスターサーバ２００と、ネットワークスイッチ３００とを有し、スレーブサーバ１００Ａ〜１００Ｃとマスターサーバ２００とがネットワークスイッチ３００を介してそれぞれ接続される。なお、図１においては、スレーブサーバ１００Ａ〜１００Ｃが図示されているが、実際には、さらに複数のスレーブサーバがネットワークスイッチ３００に接続されている。
【００１６】
そして、分散Ｋｅｙ−Ｖａｌｕｅストアは、例えば、ネットワークスイッチ３００を介してアクセスされるユーザのデータを「Ｋｅｙ（キー情報）」と「Ｖａｌｕｅ（値情報）」とのペアを含むレコードを、スレーブサーバ上に形成された部分テーブル（以下、エリアと記す）で管理する。一例を挙げると、分散Ｋｅｙ−Ｖａｌｕｅストアは、図１に示すように、Ｋｅｙによってソートされたレコードのテーブルを分割して、スレーブサーバ１００Ａ〜１００Ｃで管理する。ここで、テーブルの分割は、レコードのエントリ数に基づいて実行される場合であってもよく、或いは、データサイズに基づいて実行される場合であってもよい。
【００１７】
ネットワークスイッチ３００は、ユーザによって操作される図示しないクライアント装置のアクセス先のスレーブサーバを切り替える。マスターサーバ２００は、スレーブサーバ１００Ａ〜１００Ｃへの各種指示要求を行う。例えば、マスターサーバ２００は、テーブルにおけるどのエリアをどのスレーブサーバに配置するかを決定して、各スレーブサーバに指示要求を行う。一例を挙げると、マスターサーバ２００は、図１に示すように、Ｋｅｙ１からＫｅｙ９９までのエリアと、Ｋｅｙ３００からＫｅｙ３９９までのエリアとをスレーブサーバ１００Ａに配置する。
【００１８】
スレーブサーバ１００Ａ〜１００Ｃは、マスターサーバ２００によって配置されたエリアを管理し、自身が管理するエリアに対する検索・更新といったレコードに対する処理をユーザからの指示に従って実行する。例えば、スレーブサーバ１００Ａは、Ｋｅｙ１からＫｅｙ９９までのエリアに対する検索の指示要求をユーザから受付けて、受付けた指示要求を実行する。なお、分散ファイルシステムにおいては、複数のサーバに各レコードのレプリケーションが格納されている。
【００１９】
ここで、分散Ｋｅｙ−Ｖａｌｕｅストアでは、一度追加されたレコードに対して削除や更新などのオペレーションが実行された場合でも、当該レコードが削除されたり、更新されたりすることはない。例えば、ユーザがスレーブサーバ１００Ａによって管理された(Ｋｅｙ３０２,Ｖａｌｕｅ３０２)に対して削除のオペレーションを実行した場合に、スレーブサーバ１００Ａは、図１に示すように、Ｄ(Ｋｅｙ３０２,Ｖａｌｕｅ３０２) を管理する。すなわち、分散Ｋｅｙ−Ｖａｌｕｅストアは、レコードの更新や削除がユーザから要求された場合、既に格納済みの(Ｋｅｙ,Ｖａｌｕｅ)ペアを更新するのではなく、更新や削除を意味する新たな（Ｋｅｙ’,Ｖａｌｕｅ’)を追加する。以下、Ｄ(Ｋｅｙ,Ｖａｌｕｅ)は、(Ｋｅｙ,Ｖａｌｕｅ)を削除することを意味することとする。また、Ｕ(Ｋｅｙ,Ｖａｌｕｅ’)は、Ｋｅｙ に対応する(Ｋｅｙ,Ｖａｌｕｅ)を(Ｋｅｙ,Ｖａｌｕｅ’)に更新することを意味することとする。なお、削除と同様に、格納されたデータを更新するのではなく、内部的にはＵ(Ｋｅｙ,Ｖａｌｕｅ’)という新たなペアを追加する。スレーブサーバ１００Ａ〜スレーブサーバ１００Ｃは、検索があった場合、同一のＫｅｙに関する追加、更新、削除を示す(Ｋｅｙ,Ｖａｌｕｅ)群から必要な(Ｋｅｙ,Ｖａｌｕｅ)のみをユーザに返却する。
【００２０】
次に、スレーブサーバに対するレコードの管理の詳細について図２を用いて説明する。なお、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれるスレーブサーバは、それぞれ同様の管理を行うため、図２においては、図１に示すスレーブサーバ１００Ａを例に挙げて説明する。図２は、第１の実施形態に係るスレーブサーバ１００Ａによるレコードの管理を説明するための図である。
【００２１】
例えば、スレーブサーバ１００Ａは、図２に示すように、１つのＷＡＬログ（ログ先行書き込み用ログファイル）と、複数のエリア（エリア１及びエリア２）とを有する。エリア１及びエリア２は、図２に示すように、メモリ上のバッファと、複数のソート済みＫｅｙＶａｌｕｅファイルを有する。そして、エリア１及びエリア２は、所定の容量が設定され、格納されたレコードの容量が所定の容量を超える場合に、分割される。例えば、エリア１に格納されたレコードの容量が所定の容量を超える場合に、エリア１が分割され、エリア１に格納されたレコードは分割後のエリアで管理される。
【００２２】
ここで、図２の（１）に示すように、ユーザから（ｎｅｗＫｅｙ，ｎｅｗＶａｌｕｅ）の追加要求を受付けると、スレーブサーバ１００Ａは、まず、（２）に示すように、（ｎｅｗＫｅｙ，ｎｅｗＶａｌｕｅ）をＷＡＬログへ書き込む。このＷＡＬログへの書き込みは、ファイルの最後尾に追記されることで実現され、書き込みが成功した場合に、レコードの永続性が保証される。
【００２３】
その後、図２の（３）に示すように、スレーブサーバ１００Ａは、（ｎｅｗＫｅｙ，ｎｅｗＶａｌｕｅ）をエリア１内のメモリ上バッファへ書き込む。さらに、メモリ上バッファ内の容量が大きくなると、（４）に示すように、スレーブサーバ１００Ａは、メモリ上バッファのレコード（ｎｅｗＫｅｙ，ｎｅｗＶａｌｕｅ）を、Ｋｅｙによってソートした後、分散ファイルシステム上のソート済みＫｅｙＶａｌｕｅファイルに書き出し、メモリ上バッファをクリアする。なお、図２においては、ソート済みＫｅｙＶａｌｕｅファイルを別ファイルに書き込んでいるが、実施形態はこれに限定されることはなく、例えば、１つのファイルに追記で書き込む場合であってもよい。
【００２４】
上述したように、スレーブサーバ１００Ａは、メモリ上の一時的な（Ｋｅｙ，Ｖａｌｕｅ）群を分散ファイルシステム上のソート済みＫｅｙＶａｌｕｅファイルに書き込むことでレコードを永続化させる。なお、ユーザからレコードの検索要求を受信した場合、スレーブサーバ１００Ａは、メモリ上バッファと、ソート済みＫｅｙＶａｌｕｅファイルとを読み込み、検索結果をユーザへ返却する。
【００２５】
上述したレコードの追加は、削除や更新を示すレコードも同様に実行される。例えば、スレーブサーバ１００Ａは、図２に示すように、Ｄ（Ｋｅｙ１０，Ｖａｌｕｅ１０）をエリア２内のメモリ上バッファへ書き込む。そして、スレーブサーバ１００Ａは、メモリ上バッファのＤ（Ｋｅｙ１０，Ｖａｌｕｅ１０）を、Ｋｅｙ１によってソートした後、分散ファイルシステム上のソート済みＫｅｙＶａｌｕｅファイルに格納する。
【００２６】
これは、削除対象である（Ｋｅｙ１０，Ｖａｌｕｅ１０）が既にソート済みＫｅｙＶａｌｕｅファイルとして永続化されており、全てのソート済みＫｅｙＶａｌｕｅファイルを読み込まない限り削除対象の（Ｋｅｙ１０，Ｖａｌｕｅ１０）がどこに存在するかわからないためである。これにより、ソート済みＫｅｙＶａｌｕｅファイルへの書き込み時に対象となる（Ｋｅｙ１０，Ｖａｌｕｅ１０）を検索・更新する必要がないため、書き込みスループットを向上させることができる。
【００２７】
次に、スレーブサーバによるガベージコレクション処理について図３を用いて説明する。なお、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれるスレーブサーバは、それぞれ同様のガベージコレクションを行うため、図３においては、図１に示すスレーブサーバ１００Ａを例に挙げて説明する。図３は、第１の実施形態に係るスレーブサーバ１００Ａによるガベージコレクション処理を説明するための図である。
【００２８】
例えば、スレーブサーバ１００Ａは、図３の（１）に示すように、エリア１の全てのレコード（メモリ上バッファ内の（Ｋｅｙ，Ｖａｌｕｅ）、及び、ソート済みＫｅｙＶａｌｕｅファイル）を読み込み、削除するべきレコード（例えば、Ｄ（Ｋｅｙ，Ｖａｌｕｅ）及び対象となる（Ｋｅｙ，Ｖａｌｕｅ））を削除したうえで新しいファイルを作成する。そして、（２）に示すように、スレーブサーバ１００Ａは、既存のファイルとメモリ上の（Ｋｅｙ，Ｖａｌｕｅ）をすべて削除する。
【００２９】
上述したように、ガベージコレクション処理は、エリアごとに既存の全てのレコードを読み込み、削除するべきレコードを削除したうえで、削除後の全てのレコードを書き込む。したがって、ガベージコレクション処理は、ディスクＩ／Ｏや、ＣＰＵ、ネットワークなどのリソースを大量に消費する。従って、従来、ガベージコレクション処理の実行タイミングに関する種々の手法が開示されているが、いずれの手法においても十分な負荷分散を実行することができない。以下、従来技術に係る課題について説明する。図４は、従来技術に係る課題を説明するための図である。
【００３０】
図４においては、（Ａ）にガベージコレクション処理の実行間隔を設定する手法について示し、（Ｂ）にユーザにガベージコレクション処理の実行コマンドを提供する手法について示し、（Ｃ）にエリアの分割時にガベージコレクションを実行する手法について示す。また、図４の上段の矩形と矢印で示された図は、矩形がエリアを示し、矩形の長さが分割サイズを示し、レコードの追加に伴ってエリアが分割されていく状態を示す。また、図４の中段の図は、横軸が時間（ｔ）を示し、縦軸がガベージコレクション（ＧＣ）の発生数を示す。
【００３１】
まず、ガベージコレクション処理の実行間隔を設定する手法では、ガベージコレクション処理の実行間隔を、全てのエリアで１つしか設定することができないため、図４の（Ａ）に示すように、エリア群の各ガベージコレクション処理の実行タイミングが重なってしまい、時間軸に対する負荷分散ができない。すなわち、ガベージコレクション処理の実行間隔を設定する手法では、ディスクＩ／Ｏや、ネットワーク、ＣＰＵの負荷が高い状態が一定の間隔で発生するということに他ならない。実際、分散ファイルシステムの初期の段階では、ガベージコレクション処理を実行した場合の負荷の高い状態が１時間程度で終了するが、管理されるデータ量（レコード量）が増大するに従い、負荷が高い状態が長くなるという問題も指摘されている。これは、データ量の増加に伴いエリアが増加し、ガベージコレクション処理の発生数が増加するためである。
【００３２】
また、ユーザにガベージコレクション処理の実行コマンドを提供する手法では、図４の（Ｂ）に示すように、ガベージコレクション処理の実行時（ＧＣ実行）にエリア数の同数のガベージコレクション処理が実行され、負荷分散ができない。さらに、ユーザにガベージコレクション処理の実行コマンドを提供する手法では、ユーザがシステムの内部を十分に理解していない限り、きわめて難しい。例えば、システムの内部を十分に理解していない場合、ガベージコレクション処理を実行し過ぎて、ＣＰＵ やディスクＩ／Ｏ に対する負荷を高めてしまい、本来ユーザに提供するべき、（Ｋｅｙ，Ｖａｌｕｅ）の追加、更新、削除、検索といった機能のスループットやレスポンスタイムが悪化させる場合がある。逆に、ガベージコレクション処理の実行が少な過ぎて、分散ファイルシステム上のディスク占有量が減少せずにディスクフルなどの問題を引き起こす場合がある。
【００３３】
また、エリアの分割時（分割前）にガベージコレクション処理を実行する手法では、レコードのエリアへの書き込みがランダムに行われ、各エリアへのレコードの蓄積状況も平準化されるため、図４の（Ｃ）に示すように、各エリアで発生する分割のタイミングがほぼ同時となる（一定期間内に集中する）。その結果、エリアの分割時にガベージコレクション処理を実行する手法では、ほぼ同時に発生するエリアの分割時にディスクＩ／Ｏや、ネットワーク、ＣＰＵの負荷が高い状態となる。すなわち、管理されるデータが増加するに従って、短時間に集中して発生するガベージコレクション処理の発生数が増加し、リソース負荷も増加することとなる。なお、図４の（Ｃ）において、エリアが分割される時間がＴ→Ｔ２→Ｔ４ となっているのは、一度分割が行われるとエリアの数が２倍になり、同じ速度で（Ｋｅｙ，Ｖａｌｕｅ）を投入した場合には、エリア分割までに、２倍の時間を要するためである。
【００３４】
上述したように、従来技術においては、いずれの手法においても、短時間に集中して発生するガベージコレクション処理数が大きい。そこで、本願に係るスレーブサーバは、ガベージコレクションの発生を分散させることで、リソース負荷を抑制する。図５は、第１の実施形態に係るスレーブサーバ１００Ａの構成の一例を示す図である。なお、分散ファイルシステムに含まれるスレーブサーバは同様の構成を有していることから、図１においてはスレーブサーバ１００Ａを例に挙げて説明する。
【００３５】
図５に示すように、スレーブサーバ１００Ａは、通信制御Ｉ／Ｆ部１１０と、入力部１２０と、表示部１３０と、記憶部１４０と、制御部１５０とを有する。通信制御Ｉ／Ｆ部１１０は、ユーザによって操作されるユーザ端末装置と、制御部１５０との間でやり取りする各種情報に関する通信を制御する。例えば、通信制御Ｉ／Ｆ部１１０は、レコードの検索・追加・更新・削除などに係る通信を制御する。また、通信制御Ｉ／Ｆ部１１０は、マスターサーバ２００と制御部１５０との間でやり取りする各種情報に関する通信を制御する。また、通信制御Ｉ／Ｆ部１１０は、入力部１２０及び表示部１３０と、制御部１５０との間での各種情報のやり取りを制御する。
【００３６】
入力部１２０は、例えば、キーボードやマウスなどであり、分散Ｋｅｙ−Ｖａｌｕｅストアの管理者による種々の情報の入力処理を受付ける。表示部１３０は、例えば、ディスプレイなどであり、分散Ｋｅｙ−Ｖａｌｕｅストアの管理者に対して処理結果を表示出力する。
【００３７】
記憶部１４０は、図５に示すように、データ記憶領域１４１と、ソート済みファイル記憶領域１４２とを有する。記憶部１４０は、例えば、ハードディスク、光ディスクなどの記憶装置、または、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子であり、スレーブサーバ１００Ａによって実行される各種プログラムなどを記憶する。
【００３８】
データ記憶領域１４１は、レコード（Ｋｅｙ，Ｖａｌｕｅ）を記憶する記憶領域であり、例えば、図２に示すメモリ上バッファである。ソート済みファイル記憶領域１４２は、Ｋｅｙによってソートされたレコードを記憶する記憶領域であり、例えば、図２に示すソート済みＫｅｙＶａｌｕｅファイルである。そして、これらソート済みＫｅｙＶａｌｕｅファイルが分散ファイルシステムに該当し、これらのファイルのレプリカが複数のサーバで管理されることで、信頼性を保持する。
【００３９】
制御部１５０は、図５に示すように、ガベージコレクション決定部１５１と、ガベージコレクション実行部１５２とを有する。制御部１５０は、例えば、ＣＰＵやＭＰＵ（Micro  Processing  Unit）などの電子回路やＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路であり、スレーブサーバ１００Ａの全体制御を実行する。なお、図示していないが、制御部１５０は、レコードの検索・追加・削除・更新などの処理を実行する機能部や、レコードをソートする機能部、エリアを分割する機能部などを有する。
【００４０】
ガベージコレクション決定部１５１は、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれにおいて所定の容量で形成された複数のエリアによって分散して管理されたＫｅｙ及びＶａｌｕｅを含むレコードに対するガベージコレクション処理を、サーバそれぞれでエリアごとに時系列上分散して実行されるようにエリアごとの実行時期を決定する。具体的には、ガベージコレクション決定部１５１は、エリアの分割時にガベージコレクション処理が実行される場合に、所定の容量が所定の範囲内で変化するようにエリアを分割させる。
【００４１】
例えば、ガベージコレクション決定部１５１は、ユーザによってレコードの追加が実行されるごとに、エリアが分割される閾値となるエリアベースサイズと、エリアベースサイズにランダムな変化を与える変動サイズと、現在のエリアサイズとを取得する。そして、ガベージコレクション決定部１５１は、取得した変動サイズ以下で０以上のランダムな値（Ｒ）を生成する。
【００４２】
ここで、ガベージコレクション決定部１５１は、エリアベースサイズの値に、生成したＲを加算した値が現在のエリアサイズの値を上回っているか否かを判定して、上回っている場合に、ガベージコレクション処理をスケジューリングする。すなわち、ガベージコレクション決定部１５１は、現在のエリアサイズの値が、エリアを分割する閾値にランダムな値を加えた値を上回った場合に、エリアを分割するように決定するとともに、ガベージコレクション処理を実行するように、後述するガベージコレクション実行部１５２に通知する。
【００４３】
これにより、分割されるエリアサイズをランダムに変化させことができ、エリアの分割の発生を時系列上分散させることができる。その結果、ガベージコレクション処理の実行も時系列上分散させることができ、リソース負荷を分散することができる。なお、変動サイズは、分散ファイルシステムの管理者、或いは、ユーザによって任意に設定することができる。
【００４４】
ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によって決定された実行時期に、対象となるエリアに対するガベージコレクション処理を実行する。具体的には、ガベージコレクション実行部１５２は、エリアの分割時にガベージコレクション処理を実行する。すなわち、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によってエリアサイズがランダムに変化された各エリアの分割時にガベージコレクション処理を実行する。
【００４５】
図６は、第１の実施形態に係るスレーブサーバ１００Ａによって実行されるエリア分割とガベージコレクション処理の一例を説明するための図である。ここで、図６の上段の矩形と矢印で示された図は、矩形がエリアを示し、矩形の長さが分割サイズを示し、レコードの追加に伴ってエリアが分割されていく状態を示す。また、図６の下段の図は、横軸が時間（ｔ）を示し、縦軸がガベージコレクション（ＧＣ）の発生数を示す。
【００４６】
例えば、スレーブサーバ１００Ａによって実行されるエリア分割は、図６の上段に示すように、分割されるごとにエリアサイズがランダムに変化する。上述したように、各エリアへのレコードの蓄積状況は平準化されることから、エリアの分割が発生するタイミングはエリアごとに異なったものとなる。従って、エリアの分割時にガベージコレクション処理を実行すると、図６の下段に示すように、ガベージコレクション処理が時系列上分散されて実行されることとなる。言い換えると、スレーブサーバ１００Ａは、一定時間間隔ごとに発生するガベージコレクション処理の数を均一化する（特定時間間隔内の集中的なガベージコレクション処理の発生を抑止する）ことができる。
【００４７】
次に、第１の実施形態に係るスレーブサーバ１００Ａによる処理の手順について、図７及び図８を用いて説明する。図７は、第１の実施形態に係るガベージコレクション決定部１５１による処理の手順を示すフローチャートである。第１の実施形態に係るガベージコレクション決定部１５１は、ユーザによってレコードが追加されると、図７に示すように、エリアベースサイズ、変動サイズ、現在のエリアサイズを取得する（ステップＳ１０１）。
【００４８】
そして、ガベージコレクション決定部１５１は、０以上変動サイズ以下で、ランダム値（Ｒ）を生成して（ステップＳ１０２）、エリアベースサイズ＋Ｒが現在のエリアサイズを下回っているか否かを判定する（ステップＳ１０３）。ここで、エリアベースサイズ＋Ｒが現在のエリアサイズを下回っている場合には（ステップＳ１０３肯定）、ガベージコレクション決定部１５１は、ガベージコレクション処理をスケジューリングして（ステップＳ１０４）、処理を終了する。
【００４９】
一方、エリアベースサイズ＋Ｒが現在のエリアサイズを下回っていない場合には（ステップＳ１０３否定）、ガベージコレクション決定部１５１は、ガベージコレクション処理をスケジューリングせずに、処理を終了する。
【００５０】
図８は、第１の実施形態に係るガベージコレクション実行部１５２による処理の手順を示すフローチャートである。なお、図８においては、ガベージコレクション決定部１５１によってガベージコレクション処理がスケジューリングされた後の処理について示す。
【００５１】
第１の実施形態に係るガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によってガベージコレクション処理がスケジューリングされると、図８に示すように、スケジューリングされたガベージコレクションタスクを取得する（ステップＳ２０１）。具体的には、ガベージコレクション実行部１５２は、ガベージコレクション処理を実行する対象となるエリアの情報を取得する。
【００５２】
そして、ガベージコレクション実行部１５２は、取得したエリアにおける既存のソート済みＫｅｙＶａｌｕｅファイル群から更新・削除を反映したうえで、新たなソート済みＫｅｙＶａｌｕｅファイルを生成して（ステップＳ２０２）、処理を終了する。
【００５３】
［第１の実施形態の効果］
上述したように、第１の実施形態によれば、ガベージコレクション決定部１５１は、分散Ｋｅｙ−Ｖａｌｕｅストアに含まれる複数のサーバそれぞれにおいて所定の容量で形成された複数のエリアによって分散して管理されたＫｅｙ及びＶａｌｕｅを含むレコードに対するガベージコレクション処理を、サーバそれぞれでエリアごとに時系列上分散して実行されるようにエリアごとの実行時期を決定する。そして、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によって決定された実行時期に、対象となるエリアに対するガベージコレクション処理を実行する。従って、第１の実施形態に係るスレーブサーバ１００Ａは、ガベージコレクション処理の実行を時系列上分散して実行させることができ、リソース負荷を分散することを可能にする。
【００５４】
また、第１の実施形態によれば、ガベージコレクション決定部１５１は、エリアの分割時にガベージコレクション処理が実行される場合に、所定の容量が所定の範囲内で変化するようにエリアを分割させる。そして、ガベージコレクション実行部１５２は、エリアの分割時にガベージコレクション処理を実行する。従って、第１の実施形態に係るスレーブサーバ１００Ａは、既存の技術を用いて容易にガベージコレクション処理の実行を時系列上分散させることができ、リソース負荷の分散を容易に実行することを可能にする。
【００５５】
（第２の実施形態）
上述した第１の実施形態においては、エリアサイズをランダムに変化させることで、エリアの分割のタイミングを分散させ、エリアの分割時にガベージコレクションを実行する場合について説明した。第２の実施形態では、ガベージコレクション処理によって削減される容量を予測し、予測結果に応じて、ガベージコレクション処理を実行する場合について説明する。なお、第２の実施形態に係るスレーブサーバは、第１の実施形態に係るスレーブサーバ１００Ａと比較して、ガベージコレクション決定部１５１及びガベージコレクション実行部１５２による処理内容のみが異なる。以下、これらを中心に説明する。
【００５６】
第２の実施形態に係るガベージコレクション決定部１５１は、所定の時間間隔でエリアごとにガベージコレクション処理を実行した場合の削減容量を予測し、予測した削減容量が最大となるエリアをガベージコレクション処理の対象と決定する。具体的には、ガベージコレクション決定部１５１は、レコードがエリアに登録された時点から所定の期間が経過した場合に、当該レコードがガベージコレクション処理によって削除されうる削除対象レコードと判定し、エリアに含まれる削除対象レコードの合計容量を削除容量として予測する。
【００５７】
ここで、第２の実施形態に係るスレーブサーバ１００Ａでは、（Ｋｅｙ，Ｖａｌｕｅ）に（Ｋｅｙ，Ｖａｌｕｅ）が登録された時刻を示すＴｉｍｅｓｔａｍｐを加えたレコードを用いる。すなわち、第２の実施形態に係るスレーブサーバ１００Ａは、記憶部１４０に（Ｋｅｙ，Ｔｉｍｅｓｔａｍｐ，Ｖａｌｕｅ）タプルを格納する。なお、Ｔｉｍｅｓｔａｍｐは、（Ｋｅｙ，Ｖａｌｕｅ）が追加される際に、ユーザによって設定される場合であってもよく、或いは、制御部１５０によって登録される場合であってもよい。制御部１５０によって登録される場合には、制御部１５０は、（Ｋｅｙ，Ｖａｌｕｅ）が追加された時刻を登録する機能部をさらに有する。
【００５８】
例えば、ガベージコレクション決定部１５１は、所定の時間が経過するごとに、以下に示す式（１）により、エリアごとにガベージコレクション処理による削除容量を予測する。なお、式（１）における「tpds：Total  Prediction  of  Deleting  Size」は、削除されると予測される全容量を示す関数である。また、式（１）における「Area[i]」は、スレーブサーバ内の各エリアを示し、（１≦i≦Ｎ：正の整数）である。また、式（１）における「Area[i].SortedKVF[j]」は、各エリアに格納されたソート済みＫｅｙＶａｌｕｅファイルを示し、（１≦j≦Ｍ：正の整数）である。また、式（１）における「pds」は、削除されると予測される容量を示す関数である。
【００５９】
【数１】
0005575828.tif 000002
【００６０】
すなわち、ガベージコレクション決定部１５１は、式（１）に示すように、エリアごとに、削除されうるソート済みＫｅｙＶａｌｕｅファイルの合計値を算出することで、削除容量を予測する。
【００６１】
ここで、式（１）に含まれる「pds」は、以下の式（２）によって定義される。なお、式（２）における「SortedKVF[j].size」は、レコードサイズを示す。また、式（２）における「SortedKVF[j].maxts」は、エリア内の最新のレコードを示し、「SortedKVF[j].mints」は、エリア内の最古のレコードを示す。これは、登録されている各レコードが（Ｋｅｙ，Ｔｉｍｅｓｔａｍｐ，Ｖａｌｕｅ）を要素とする集合であることから原理上、最大のＴｉｍｅｓｔａｍｐを有するもの（最新）と最小のＴｉｍｅｓｔａｍｐを有するもの（最古）とがあり、それを用いることができる。また、式（２）における「ＣＴ：Current  Time」は、現時点での時刻を示し、「ＰＶ：Period  of  Validity」は、レコードの有効期限を示す。
【００６２】
【数２】
0005575828.tif 000003
【００６３】
すなわち、ガベージコレクション決定部１５１は、式（２）に示すように、レコードの有効期限が切れている場合（SortedKVF[j].maxts≦ＣＴ−ＰＶ）には、レコードのサイズを削除容量とし、レコードの有効期限が切れていない場合（ＣＴ−ＰＶ≦SortedKVF[j].mints）には、削除容量を「０」とする。ここで、ガベージコレクション決定部１５１は、有効期限が切れている容量を線形に予測する。すなわち、ガベージコレクション決定部１５１は、時間経過に従って、削除できる量が線形に増加するという前提に従って、削除容量を予測する。
【００６４】
図９は、第２の実施形態に係るガベージコレクション決定部１５１による削除容量の予測を説明するための図である。ここで、図９の（Ａ）においては、横軸が時刻（ｔ）を示す。そして、図９の（Ａ）においては、１つのエリアに含まれる全ての「SortedKVF[j](１≦j≦Ｍ)」をそれぞれ示す線分を横軸上に示す。すなわち、図９の（Ａ）に示す線分は、図９の（Ｂ）に示すように、左端が「SortedKVF[j].mints」を示し、右端が「SortedKVF[j].maxts」を示し、長さが「SortedKVF[j].size」を示す。
【００６５】
例えば、ガベージコレクション決定部１５１は、図９の（Ａ）において有効期間（「ＣＴ」と「ＣＴ−ＰＶ」との間）にあるソート済みＫｅｙＶａｌｕｅファイルについては、削除対象とはせず、削除容量を「０」とする。一方、無効期間にあるソート済みＫｅｙＶａｌｕｅファイルについては、削除容量をソート済みＫｅｙＶａｌｕｅファイルのサイズとする。そして、ガベージコレクション決定部１５１は、無効期間と有効期間との両方にかかるソート済みＫｅｙＶａｌｕｅファイルについては、式（２）の第２式を用いて削除容量を算出する。すなわち、式（２）に示すように、（SortedKVF[j].mints≦ＣＴ−ＰＶ≦SortedKVF[j].maxts）の場合には、ガベージコレクション決定部１５１は、期限切れとなった割合を算出して、全体のレコードサイズにおける当該割合のサイズを削除容量として算出する。
【００６６】
ガベージコレクション決定部１５１は、式（１）及び式（２）を用いて各エリアの削除容量を算出して、以下の式（３）によりガベージコレクション処理の対象となるエリアを抽出する。なお、式（３）における「gct：garbage  collection  target」は、現時点でガベージコレクション処理を実行した場合に最も削除量が大きいエリアを返却する関数である。また、式（３）における「Areas」は、{Area[j]|１≦j≦Ｍ}で表される集合を示す。
【００６７】
【数３】
0005575828.tif 000004
【００６８】
すなわち、ガベージコレクション決定部１５１は、「Area」を引数にもつ関数「gct」により、現時点でガベージコレクションを実行した場合に、最も削除量が大きいエリアを返却する。ここで、ガベージコレクション決定部１５１は、以下に示す式（４）により、削除容量が一定量を超えない場合にガベージコレクション処理を実行しないように制御する。なお、式（４）における「gtc_over_mds」は、返却されたエリアに対する削除量が一定量を満たさない場合に、ガベージコレクション処理を行わないことを示す「０」を示す関数である。また、式（４）における「ＭＤＳ：Minimum  Deleting  Size」は、ガベージコレクション処理を実行するか否かの閾値を示す。
【００６９】
【数４】
0005575828.tif 000005
【００７０】
すなわち、ガベージコレクション決定部１５１は、現時点でガベージコレクション処理を実行した場合のエリアの削除容量がＭＤＳを超えていた場合に、当該エリアに関する情報をガベージコレクション実行部１５２に通知する。一方、現時点でガベージコレクション処理を実行した場合のエリアの削除容量がＭＤＳ以下の場合には、ガベージコレクション決定部１５１は、ガベージコレクション処理を実行しないことを示す「０」をガベージコレクション実行部１５２に通知する。
【００７１】
上述したように、ガベージコレクション決定部１５１は、有効期限が切れているか否かに基づく削除容量をエリアごとに算出し、算出した削除容量が最大となるエリアをガベージコレクション処理の対象として決定する。そして、ガベージコレクション決定部１５１は、対象としたエリアの削除容量が一定量（ＭＤＳ）を超えたことを条件にガベージコレクション処理を実行させる。なお、上述した有効期限及びＭＤＳは、分散ファイルシステムの管理者、或いは、ユーザによって任意に設定することができる。例えば、有効期限として、Ｗｅｂ情報などの保持期限などとして「３０日」を設定する場合であってもよい。
【００７２】
第２の実施形態に係るガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によって決定されたエリアに対するガベージコレクション処理を実行する。具体的には、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によってガベージコレクション処理の対象として決定されたエリアにおける削除容量がＭＤＳを上回った場合に、当該エリアに対するガベージコレクション処理を実行する。すなわち、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１からエリアの情報が通知された場合に、通知されたエリアに対するガベージコレクション処理を実行する。
【００７３】
図１０は、第２の実施形態に係るスレーブサーバによって実行されるガベージコレクション処理の一例を説明するための図である。ここで、図１０の上段の矩形と矢印で示された図は、矩形がエリアを示し、矩形の長さが分割サイズを示し、レコードの追加に伴ってエリアが分割されていく状態を示す。また、図１０の下段の図は、横軸が時間（ｔ）を示し、縦軸がガベージコレクション（ＧＣ）の発生数を示す。また、図１０の下段に示す黒三角形は、ガベージコレクション処理が実行されたことを示し、点線の三角形は、ガベージコレクション処理が実行されていないことを示す。
【００７４】
例えば、第２の実施形態に係るスレーブサーバ１００Ａによって実行されるガベージコレクション処理は、図１０の下段に示すように、１つのエリアに対するガベージコレクション処理が時系列上分散されて実行される。すなわち、スレーブサーバ１００Ａは、特定時間間隔内の集中的なガベージコレクション処理の発生を抑止することができる。
【００７５】
次に、第２の実施形態に係るスレーブサーバ１００Ａによる処理の手順について、図１１を用いて説明する。なお、第２の実施形態に係るガベージコレクション実行部１５２によるガベージコレクション処理は、第１の実施形態と同様である（図８参照）。図１１は、第２の実施形態に係るガベージコレクション決定部１５１による処理の手順を示すフローチャートである。第２の実施形態に係るガベージコレクション決定部１５１は、図１１に示すように、一定時間が経過すると（ステップＳ３０１肯定）、各エリアについて、推定される削除データ量を算出する（ステップＳ３０２）。
【００７６】
そして、ガベージコレクション決定部１５１は、削除容量が最大となるエリアを抽出して（ステップＳ３０３）、抽出したエリアの削除容量がＭＤＳを上回るか否かを判定する（ステップＳ３０４）。ここで、抽出したエリアの削除容量がＭＤＳを上回る場合には（ステップＳ３０４肯定）、ガベージコレクション決定部１５１は、該当するエリアに対するガベージコレクション処理をスケジューリングして（ステップＳ３０５）、処理を終了する。
【００７７】
一方、抽出したエリアの削除容量がＭＤＳを上回らない場合には（ステップＳ３０４否定）、ガベージコレクション決定部１５１は、ガベージコレクション処理をスケジューリングせずに、処理を終了する。なお、一定時間経過するまで、ガベージコレクション決定部１５１は、待機状態である（ステップＳ３０１否定）。
【００７８】
［第２の実施形態の効果］
上述したように、第２の実施形態によれば、ガベージコレクション決定部１５１は、所定の時間間隔でエリアごとにガベージコレクション処理を実行した場合の削減容量を予測し、削減容量が最大となるエリアをガベージコレクション処理の対象と決定する。そして、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によって決定されたエリアに対するガベージコレクション処理を実行する。従って、第２の実施形態に係るスレーブサーバ１００Ａは、ディスク占有量とリソース負荷との間のトレードオフをコントロールすることができ、リソース負荷を分散することを可能にする。
【００７９】
また、第２の実施形態によれば、ガベージコレクション決定部１５１は、レコードがエリアに登録された時点から所定の期間が経過した場合に、当該レコードがガベージコレクション処理によって削除されうる削除対象レコードと判定し、エリアに含まれる削除対象レコードの合計容量を削除容量として予測する。従って、第２の実施形態に係るスレーブサーバ１００Ａは、不要なレコードを確実に削除するようにガベージコレクション処理を実行させることを可能にする。
【００８０】
また、第２の実施形態によれば、ガベージコレクション実行部１５２は、ガベージコレクション決定部１５１によってガベージコレクション処理の対象として決定されたエリアにおける削除容量が所定の閾値を上回った場合に、当該エリアに対するガベージコレクション処理を実行する。従って、第２の実施形態に係るスレーブサーバ１００Ａは、効果的なガベージコレクション処理を実行することを可能にする。
【００８１】
（第３の実施形態）
これまで第１の実施形態及び第２の実施形態を説明したが、本願に係る実施形態は、第１の実施形態及び第２の実施形態に限定されるものではない。すなわち、これらの実施形態は、その他の様々な形態で実行されることが可能であり、種々の省略、置き換え、変更を行うことができる。
【００８２】
例えば、各装置の分散・統合の具体的形態（例えば、図５の形態）は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合することができる。一例を挙げると、ガベージコレクション決定部１５１及びガベージコレクション実行部１５２とを一つの処理部として統合してもよく、一方、ガベージコレクション決定部１５１を、削除容量を予測する予測部と、削除対象エリアを抽出する抽出部とに分散してもよい。
【００８３】
また、制御部１５０をスレーブサーバ１００Ａの外部装置としてネットワーク経由で接続するようにしてもよく、或いは、ガベージコレクション決定部１５１及びガベージコレクション実行部１５２とを別の装置がそれぞれ有し、ネットワークに接続されて協働することで、上述したスレーブサーバ１００Ａの機能を実現するようにしてもよい。
【００８４】
上述した実施形態で説明したスレーブサーバ１００Ａは、あらかじめ用意されたプログラムをコンピュータで実行することで実現することもできる。そこで、以下では、図５に示したスレーブサーバ１００Ａと同様の機能を実現するガベージコレクション実行プログラムを実行するコンピュータの一例を説明する。
【００８５】
図１２は、第３の実施形態に係るガベージコレクション実行プログラムを実行するコンピュータ１０００を示す図である。図１２に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ（Central  Processing  Unit）１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００８６】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。 
【００８７】
ここで、図１２に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ（Operating  System）１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。第３の実施形態に係るガベージコレクション実行プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０９０に記憶される。具体的には、上記実施形態で説明したガベージコレクション決定部１５１と同様の情報処理を実行するガベージコレクション決定ステップと、ガベージコレクション実行部１５２と同様の情報処理を実行するガベージコレクション実行ステップとが記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。 
【００８８】
また、上記実施形態で説明したデータベースに記憶されるデータのように、性能分析プログラムによる情報処理に用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュールやプログラムデータを必要に応じてＲＡＭ１０１２に読み出して、ガベージコレクション決定ステップと、ガベージコレクション実行ステップとを実行する。
【００８９】
なお、性能分析プログラムに係るプログラムモジュールやプログラムデータは、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、情報送受信プログラムに係るプログラムモジュールやプログラムデータは、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００９０】
これらの実施形態やその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００９１】
１００Ａ、１００Ｂ、１００Ｃ  スレーブサーバ
１１０  通信制御Ｉ／Ｆ部
１２０  入力部
１３０  表示部
１４０  記憶部
１４１  データ記憶領域
１４２  ソート済みファイル記憶領域
１５０  制御部
１５１  ガベージコレクション決定部
１５２  ガベージコレクション実行部
２００  マスターサーバ
３００  ネットワークスイッチ
【図１】
0005575828.tif 000006
【図２】
0005575828.tif 000007
【図３】
0005575828.tif 000008
【図４】
0005575828.tif 000009
【図５】
0005575828.tif 000010
【図６】
0005575828.tif 000011
【図７】
0005575828.tif 000012
【図８】
0005575828.tif 000013
【図９】
0005575828.tif 000014
【図１０】
0005575828.tif 000015
【図１１】
0005575828.tif 000016
【図１２】
0005575828.tif 000017