(57)【要約】【課題】記憶部への書き込みサイズの増加によるアクセス性能低下を防止する技術を提供する。【解決手段】コンピュータに、第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、第２記憶部に格納されているいずれかのグループを選択し、選択されたグループに含まれるデータのうち、第２記憶部における、データアクセス要求に対応するデータへのアクセス状況に応じて、選択されたグループを分割し、分割して得られたグループ単位で、それぞれのグループに含まれるデータを第１記憶部に格納する処理を実行させるデータ格納制御プログラムにより、上記課題の解決を図る。【選択図】図２
2016162243.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループを選択し、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、前記データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割し、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する
処理を実行させるデータ格納制御プログラム。
【請求項２】
前記コンピュータに、さらに、
前記分割の結果に基づいて、前記データと前記グループとを対応付けたグループ管理情報を更新し、
データアクセス要求に対応するデータが前記第２記憶部にない場合、前記グループ管理情報に基づいて、該データアクセス要求に対応するデータが属するグループに含まれるデータを前記第１記憶部から取得する
ことを特徴とする請求項１に記載のデータ格納制御プログラム。
【請求項３】
前記分割において、
前記選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータ数を用いて、基準となるグループのサイズを算出し、
前記選択されたグループのサイズと前記基準となるグループのサイズとを比較し、比較結果に応じて、該第２グループを分割する
ことを特徴とする請求項１または２に記載のデータ格納制御プログラム。
【請求項４】
前記分割において、
前記選択されたグループに含まれるデータから、前記基準となるグループのサイズよりも大きいサイズのデータを分離し、分離した該データをそれぞれ、相互に別グループとする
ことを特徴とする請求項１〜３のうちいずれか１項に記載のデータ格納制御プログラム。
【請求項５】
前記分割において、
前記選択されたグループに含まれるデータのうち、前記データアクセス要求に応じてアクセスされたデータを分離し、分離した該データをまとめて１つのグループとする
ことを特徴とする請求項１〜４のうちいずれか１項に記載のデータ格納制御プログラム。
【請求項６】
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループを選択する選択部と、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割する分割部と、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する書込部と
を備えることを特徴とするデータ格納制御装置。
【請求項７】
コンピュータが、
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループである第２グループを選択し（Ｓ２０）、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、前記データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割し、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する
ことを特徴とするデータ格納制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの格納を制御する技術に関する。
【背景技術】
【０００２】
ストレージ装置は、サイズの小さなデータへの不規則なアクセスにおけるスループットが低く、シーケンシャルアクセスのコストに比べて、ランダムアクセスのコストが高い。このスループットを向上させる技術として、キャッシュ技術がある。
【０００３】
キャッシュ技術は、処理速度の速い制御装置が低速の記憶装置からデータをより速く読み出す場合にメモリを使用して処理時間を短縮する技術である。制御装置が低速の記憶装置からデータを読み出した場合、その読み出したデータを一時的にメモリに保持しておくことで、次回からはハードディスクより読み書きが早いメモリからデータを読み出せる。このようなキャッシュ技術に関して、例えば、特許文献１〜３がある。
【０００４】
キャッシュ技術の１つとして、Least Recently Used（ＬＲＵ）キャッシュ技術がある。ＬＲＵキャッシュ技術は、小容量で高速な記憶装置（例えば、キャッシュメモリ）がいっぱいになったとき、その中にあるデータのうち、未使用の時間が最も長いデータを大容量で低速な記憶装置（例えば、主記憶装置）に保存する、というのが基本のアルゴリズムである。ＬＲＵキャッシュ技術は、アプリケーションプログラムのロジックを知らなくても効果を得られるアルゴリズムであり、短期間のうちに（キャッシュに載っているうちに）同じデータに繰り返しアクセスする場合にのみ効果を発揮する。キャッシュメモリの量によってデータのキャッシュ生存期間が決まるが、そのキャッシュ生存期間を超えるサイクルでの繰り返しアクセスには効果がない。
【０００５】
ＬＲＵキャッシュ技術を改善した技術として、データを記憶する第１の記憶部と、第１の記憶部に比して高速にアクセス可能な記憶部であって、データを記憶する第２の記憶部と、を有するデータ管理装置による、データ管理方法がある（例えば、特許文献１）。データ管理装置は、入力されたデータ要求に応じたデータを第１又は第２の記憶部から読み出して出力する。データ管理装置は、入力されたデータ要求の履歴に基づき第１又は第２の記憶部に記憶されたデータ間の関連性を解析する。データ管理装置は、解析の結果に基づき第１又は第２の記憶部に記憶されたデータをグループ分けする。データ管理装置は、グループ分けされたグループ毎に第２のデータ記憶部にデータを記憶させる。これにより、要求されたデータを高速に出力することができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０００−３５７１２５号公報
【特許文献２】特開２０００−２５０８０９号公報
【特許文献３】特開２００２−２５１３２２号公報
【特許文献４】国際公開第２０１３／１１４５３８号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記データ管理技術では、書き戻しの単位であるグループサイズが大きくなりすぎると、グループ全体の読み出しコストが増加するため、アクセス性能を下げることになる。
【０００８】
逆に、グループサイズを小さくしすぎると、特定のデータと関連するデータが、同一のセグメントに全て含まれない状態となり、余分なアクセスが発生するから、アクセス性能を下げることになる。
【０００９】
また、上記データ管理技術では、アクセスパターンから得られた関連性に基づき同一セグメントに含めるデータを決めている。しかし、セグメントサイズを決定するために関連性を用いる場合は、個別のデータの関連性（関連性があるかないか）よりも、全体のデータの関連性に対する個別のデータの関連性の位置づけを用いる必要があるが、上記技術ではそれが考慮されていない。
【００１０】
本発明では、一側面として、記憶部への書き込みサイズの増加によるアクセス性能低下を防止する技術を提供する。
【課題を解決するための手段】
【００１１】
本発明の一側面にかかるデータ格納制御プログラムは、コンピュータに、次の処理を実行させる。すなわち、コンピュータは、第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、第２記憶部に格納されているいずれかのグループを選択する。コンピュータは、選択された前記グループに含まれるデータのうち、第２記憶部における、データアクセス要求に対応するデータへのアクセス状況に応じて、選択されたグループを分割する。コンピュータは、分割して得られたグループ単位で、それぞれのグループに含まれるデータを第１記憶部に格納する。
【発明の効果】
【００１２】
本発明によれば、記憶部への書き込みサイズの増加によるアクセス性能低下を防止することができる。
【図面の簡単な説明】
【００１３】
【図１】データ再配置技術におけるグループのサイズに起因する課題について説明するための図である。
【図２】本実施形態におけるデータ格納制御装置の一例を示す。
【図３】本実施形態におけるデータ管理装置のハードウエア構成例である。
【図４】本実施形態におけるデータ管理装置の機能構成例である。
【図５】本実施形態における、データ構造について説明するための図である。
【図６】本実施形態におけるデータ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。
【図７】図６の状態に続き、データ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。
【図８】図７の状態に続き、データ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。
【図９】図８に示す状態において関連性解析部がグループを変更する前後のグループ配置を示す図である。
【図１０】グループ配置部により変更された後のグループ管理テーブルにおけるデータとグループの対応付けを示す図である。
【図１１】図１０の状態に続き、データ管理装置に対してアクセス要求Ｒｑが複数回なされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。
【図１２】図１１の状態に続き、データ管理装置１００に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。
【図１３】図１２の状態において関連性解析部がグループを決定する前後のグループ配置を示す図である。
【図１４】本実施形態におけるデータ管理装置によって実行されるアクセス要求の際に行われる処理の全体の流れを示すフローチャートの一例である。
【図１５】関連性解析部により実行される関連性解析処理（Ｓ７）の流れを示すフローチャートの一例である。
【図１６】本実施形態における、メモリ装置から記憶装置へのデータの書き戻しを行う場合、書き戻し対象のグループサイズに応じて、書き戻し対象のグループを分割する処理を説明するための図である。
【図１７】本実施形態におけるメモリ装置にあるいずれかのグループを記憶装置に書き戻す場合の処理フローを示す。
【図１８】本実施形態におけるグループ分割処理（Ｓ２４）の詳細フローを示す。
【発明を実施するための形態】
【００１４】
データ管理方法の１つに、例えば、特許文献４で用いられているデータ再配置管理技術（以下、「ＤＬＭ」と称する）がある。ＤＬＭの動作には、以下が挙げられる。ＤＬＭは、関連するデータをグループ化し、連続した領域としてストレージに格納する。データにアクセスする場合は、ＤＬＭは、そのデータが所属するグループごと読み出してメモリにキャッシュする。グループへのアクセスは１度のランダムアクセスで済むことが期待される。グループは単一のデータよりもサイズが大きくなるのでアクセスコストが増加するが、ランダムアクセスのコストと比較すると増加分はわずかである。メモリの容量が不足した場合は、ＤＬＭは、メモリにおいてアクセスのないグループから順にディスクに書き戻す。書き戻す際には、ＤＬＭは、グループ単位でＬＲＵ方式によりメモリからディスクへデータを書き戻す。
【００１５】
ＤＬＭ技術を用いることにより、メモリにキャッシュされているグループに含まれるデータへは、グループがディスクに書き戻されるまでは追加のストレージアクセスコストなしでアクセスできる。つまり何個のデータにアクセスしてもグループへのアクセスコスト1回分≒データへのアクセスコスト１個分で賄える（データサイズの増加よるアクセスコストの増加は小さいため）。つまり、短期間のうちに同じグループに属するデータにアクセスする場合に効果を発揮する。ＬＲＵのように同一データでなくてもよい。先読みキャッシュのような効果を得られる。ＬＲＵと同様に、アプリケーションのロジックを知らなくても効果が得られる。
【００１６】
ここで、データ再配置技術において、グループがメモリにキャッシュされている間にグループ内の何個のデータにアクセスしたかを、データ再利用数と呼ぶことにする。ただし同じデータに複数回アクセスした回数はカウントしない。本実施形態では、異なる何個のデータにアクセスしたかをカウントする。
【００１７】
このように、ＡＬは、大量のデータを保管することができるデータストアにおいて、データをある塊の”グループ”として保管する。ＤＬＭは、データへのアクセス毎にアクセスパターンを解析し、アクセスパターンで関係性が高い（ほぼ同時にアクセスされる）データ同士は同じグループに保管する。これにより、ＤＬＭは、遅いデータ保管装置から速いデータ保管装置に関係性の高いデータを一度に読み込むことが可能になり、データアクセスの効率化を実現する。
【００１８】
また、ランダムアクセスのコストは、グループに付き1回のアクセスである。したがって、近いタイミングでアクセスされる確率（アクセスパターン関連性）が高いデータを再配置して同じグループにうまくまとめることができれば、ランダムアクセスのコストを大幅に削減できる。
【００１９】
ＤＬＭはほとんどのデータが数Ｂｙｔｅ〜数ＫＢと小さいときに大きな効果を発揮する。
【００２０】
ところが、以下の課題がある。
課題１：大き過ぎるグループサイズ
ＤＬＭにおけるストレージへの読み書きの単位であるグループが大きくなり過ぎると、（単一データに対する読み書きと比較して）コストが増加するため、（ＤＬＭの効果を考慮しても）性能が下がる。これは、グループが大きくなるとアクセスコストが増加するので、その元を取るためのデータ再利用数の閾値が上昇するのが原因である。
【００２１】
ここで、アクセスコストは、ランダムアクセスの固定コストに、サイズに依存した変動コストを加えたコストである。サイズに依存するコストはランダムアクセスのコストに比べて小さいものの、全く無視できるというわけではない。
【００２２】
データ再利用数は、データ再利用数が大きい理想的なアクセスパターンでないと、その閾値を超えられない。しかし、アクセスパターンはアプリケーションロジックに依存するもので、変動し得るし、常に理想的なアクセスパターンとは限らない。閾値が上昇すればするほど、閾値を超えられるアクセスパターンの割合は減少する。
【００２３】
下記の仮定及び図１を用いてＤＬＭの性能の特性について説明する。
図１（Ａ）は、大きすぎるグループサイズに起因する課題について説明するための図である。
【００２４】
（アクセスコスト）
・ランダムアクセスのコストは１０であるとする。
・個々のデータは全て同じサイズで、個々のデータに対するアクセスコストは１１であるとする（サイズ由来のコストは１であるとする。）
・小さいグループはアクセスコスト２０、大きいグループは３０であるとする。
【００２５】
（関連性）
・Ａ〜Ｂの関連性は１００％、つまりＡとＢは必ずセットでアクセスされるとする。
・Ｃ〜Ｄの関連性も１００％であるとする。
・｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝にも関連性があり、この関連性を変化させる。
・今回はＡ〜Ｄ以外のデータは存在するが、アクセスしないものとする。
【００２６】
（分析）
（１）｛Ａ，Ｂ｝のみにアクセスする場合（｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝の関連性０％）
ＬＲＵでは、コストは１１×２＝２２となる。それに対して、ＤＬＭで｛Ａ，Ｂ｝が小さいグループに配置されていた場合、コストは２０となる。ＤＬＭで｛Ａ，Ｂ｝が大きいグループに配置されていた場合、コストは３０となる。
つまりコストはＤＬＭ小グループ＜ＬＲＵ＜ＤＬＭ大グループの順となり、ＤＬＭ大グループはＬＲＵに比べて５０％のコスト悪化となる。
【００２７】
（２）｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝の関連性２５％の場合
ＬＲＵでは、コスト１１×２＋０．２５×１１×２＝２７．５となる。それに対して、ＤＬＭ（小さいグループ）では２０＋０．２５×２０＝２５となる。ＤＬＭ（大きいグループ）では３０となる。
つまりコストはＤＬＭ小グループ＜ＬＲＵ＜ＤＬＭ大グループとなり、ＤＬＭ大グループはＬＲＵに比べて９％のコスト悪化となる。
【００２８】
（３）｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝の関連性５０％の場合
ＬＲＵではコスト１１×２＋０．５×１１×２＝３３となる。それに対して、ＤＬＭ（小さいグループ）では２０＋０．５×２０＝３０となる。ＤＬＭ（大きいグループ）では３０となる。
つまりコストはＤＬＭ小グループ＝ＤＬＭ大グループ＜ＬＲＵとなる。
【００２９】
（４）｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝に必ずアクセスする場合（｛Ａ，Ｂ｝〜｛Ｃ，Ｄ｝の関連性１００％）
ＬＲＵでは、コストは１１×４＝４４となる。それに対して、ＤＬＭで｛Ａ，Ｂ｝，｛Ｃ，Ｄ｝が別々の小さいグループに配置されていた場合、コストは４０となる。また、ＤＬＭで｛Ａ，Ｂ｝，｛Ｃ，Ｄ｝が大きいグループ１つに配置されていた場合、コストは３０となる。
つまりコストはＤＬＭ大グループ＜ＤＬＭ小グループ＜ＬＲＵとなる。
【００３０】
したがって、上記（１）〜（４）より、ＤＬＭはグループのアクセスコストがリスクとなり、グループのサイズが大き過ぎると関連性によってはＬＲＵの性能を下回ることがある。
【００３１】
逆に、グループが小さ過ぎると、関連性を持つデータを十分グループに格納できず、性能が十分上がらない。これについて、図１（Ｂ）を用いて説明する。
【００３２】
図１（Ｂ）は、小さ過ぎるグループサイズに起因する課題について説明するための図である。グループのサイズに上限が設定されており、図１（Ｂ）の｛Ａ，Ｂ｝に属するグループは既にデータがいっぱいになっているものとする。
【００３３】
｛Ａ，Ｂ｝に対してＣの関連性が強いため同一グループに格納したいが、グループが既にいっぱいであるため格納できない。
【００３４】
また、ＤＬＭでは、アクセスパターンから得られたデータ間の関連性に基づきグループ化（再配置）するデータを決定している。しかし、グループのサイズを決定するために、データ間の関連性を用いる場合は、個別のデータの関連性よりも、全体のデータの関連性の位置づけを用いる必要がある。ところが、ＤＬＭのアルゴリズムの中でそのような作業を行うことは困難である。これについて、図１（Ｃ）を用いて説明する。
【００３５】
図１（Ｃ）は、グループ化アルゴリズムとグループサイズに起因する課題について説明するための図である。図１（Ｃ）では、データ間にて関連性のあるデータ同士を線で関連付けており、特に、強い関連性は太線で示している。また、関連性の強さが所定の閾値以上のデータ同士を集めてグループ化している。
【００３６】
ほとんどのデータはお互いにある程度の関連性を持っているが、関連性が強いデータもあれば、関連性が弱いデータもある。
【００３７】
単純に関連性のあるデータ全てを同じグループにまとめようとすると、全データが単一グループに収まることになってしまう。
【００３８】
全体から見て、関連性が相対的に強いデータのみをグループ化できればよいのだが、その場合は全ての関連性の強さを把握しなければない。しかし、限られたメモリ・ストレージアクセスのスループットで全ての関連性の強さを把握することは困難である。
【００３９】
図１（Ｃ）では、関連性の弱いデータを無視してグループ化している。しかし、データや関連性の一部分しか見通せない場合、無視してよい関連性の強さの閾値を見出すのは困難である。
【００４０】
仮に、グループサイズの上限を固定値で設定したとしても、図１（Ｄ）に示すように課題がある。
【００４１】
図１（Ｄ）は、グループサイズの上限を設定した場合に起こりうる課題について説明するための図である。図１（Ｄ）において、左上のグループは右上のグループのデータを取り込み同一のグループにする場合を想定する。
【００４２】
しかしながら、ここでは、各グループのサイズ上限がデータ６個と設定されているため、どれかのデータを放出しない限り、右上のグループのデータを取り込めない。実際には、左上のグループはいずれも関連性が強いため、グループサイズ上限を超えても右上のグループを取り込んだ方が性能向上しやすい。
【００４３】
また、以下のような課題もある。再利用数を向上させるために、グループサイズを拡大する場合、グループの読み出しコストも増加するために、性能向上に至らない。また、再利用数を向上させるために、メモリを増やしてグループのメモリ上滞在時間を延ばす場合、効果はあるが、メモリは高価である。また、再利用数を向上させるために、再配置をより積極的に行う場合、再配置アルゴリズムは複雑で、簡単には再利用数を向上させることはできない。再配置にもコストが必要で、単純に性能が向上するわけではない。特にハードディスクドライブ（ＨＤＤ）のアクセスコストを増やさない範囲での再配置には、限度がある。また、グループサイズを縮小する場合、グループサイズを小さくすると再利用数も低下するため、単純には性能は向上しない。
【００４４】
そこで、本実施形態に係るＤＬＭは、グループがＨＤＤから読み出されてメモリ上にキャッシュとして存在する際に、参照されたデータをマークしてそのグループにおいてマークされたデータ数（再利用数）を測定する。
【００４５】
また、本実施形態に係るＤＬＭは、グループがＨＤＤに書き戻される際に、以下の処理を行う。すなわち、ＤＬＭは、再利用数から、最適グループサイズを算出する。ＤＬＭは、グループが最適グループサイズを上回る場合は、複数のグループに分割して、それぞれのサイズが最適グループサイズを下回るようにＨＤＤに書き戻す。ＤＬＭは、それ単独で最適グループサイズを上回る巨大データを、ディスクに書き戻す時に独立したグループとして分割して格納する。ＤＬＭは、グループが最適グループサイズを上回らない場合は、通常通りにそのグループをディスクに書き戻す。
【００４６】
以下に、本実施形態の詳細について説明する。
図２は、本実施形態におけるデータ格納制御装置の一例を示す。データ格納制御装置１は、選択部２、分割部３、書込部４、第１記憶部７、第２記憶部８を含む。
【００４７】
選択部２は、第１記憶部７から取得したデータを格納する第２記憶部８の空き容量不足が発生した場合、第２記憶部８に格納されているいずれかのグループを選択する。空き容量不足が発生した場合とは、例えば、受け付けたデータアクセス要求に対応するデータが第２記憶部８にない場合や、第２記憶部８において予め設定した閾値を超えてデータが格納されている場合等がある。選択部２の一例として、入出録管理部２１が挙げられる。第１記憶部７の一例として、記憶装置４０が挙げられる。第２記憶部８の一例として、メモリ装置３０が挙げられる。
【００４８】
分割部３は、選択されたグループに含まれるデータのうち、第２記憶部８における、データアクセス要求に対応するデータへのアクセス状況に応じて、選択されたグループを分割する。分割部３の一例として、分割管理部２６が挙げられる。
【００４９】
書込部４は、分割して得られたグループ単位で、それぞれのグループに含まれるデータを第１記憶部７に格納する。書込部４の一例として、書戻部２７が挙げられる。
【００５０】
このように構成することにより、記憶部７への書き込みサイズの増加によるアクセス性能低下を防止することができる。
【００５１】
データ格納制御装置１は、さらに、更新部５、取得部６を含む。
更新部５は、分割の結果に基づいて、データとグループとを対応付けたグループ管理情報を更新する。更新部５の一例として、分割管理部２６が挙げられる。グループ管理情報の一例として、グループ管理テーブル３０Ａが挙げられる。
【００５２】
取得部６は、データアクセス要求に対応するデータが第２記憶部８にない場合、グループ管理情報に基づいて、データアクセス要求に対応するデータが属するグループに含まれるデータを第１記憶部７から取得する。取得部６の一例として、入出力管理部２１が挙げられる。
【００５３】
このように構成することにより、複数のデータをグループ毎に管理し、グループ単位で、第１記憶部からデータを取得することができる。
【００５４】
分割部３は、選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータ数を用いて、基準となるグループのサイズを算出する。そして、分割部３は、選択されたグループのサイズと基準となるグループのサイズとを比較し、比較結果に応じて、第２グループを分割する。
【００５５】
このように構成することにより、データアクセス要求に応じてアクセスされたデータ数を用いて、最適グループサイズを算出し、書込対象のグループのサイズと最適グループサイズとの比較結果に応じて、第２グループを、より適した分割することができる。
【００５６】
分割部３は、選択されたグループに含まれるデータから、前記基準となるグループのサイズよりも大きいサイズのデータを分離し、分離した該データをそれぞれ、相互に別グループとしてもよい。
【００５７】
このように構成することにより、第２グループに含まれるデータのうち、データ単体で，最適グループサイズを超えるデータは、その単体のデータのみを含むグループに分割することができる。
【００５８】
分割部３は、選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータを分離し、分離した該データをまとめて１つのグループとしてもよい。
【００５９】
このように構成することにより、メモリ装置に保持された同一グループ内のデータのうち、再利用されたデータは関連性がより強いといえるので、それらを１つのグループとし、再利用されていないデータと分ける。これにより、関連性の強いデータを含むグループを保持しつつ、グループサイズを小さくすることができる。
【００６０】
図３は、本実施形態におけるデータ管理装置のハードウエア構成例である。データ管理装置１００は、例えばＣＰＵ（Central Processing Unit）２０と、メモリ装置３０と、記憶装置４０とを備える。また、データ管理装置１００は、通信ネットワーク（以下、単に、ネットワークと称する）６０を介して情報処理装置の一例であるクライアントコンピュータ７０に接続されている。
【００６１】
ＣＰＵ２０は、例えば、プログラムカウンタや命令デコーダ、各種演算器、ＬＳＵ（Load Store Unit）、汎用レジスタ等を有する演算処理装置としてのプロセッサである。
【００６２】
メモリ装置３０は、記憶装置４０に比して高速にアクセス可能な記憶装置である。メモリ装置３０としては、例えば、ＲＡＭ（Random Access Memory）、フラッシュメモリ等である。記憶装置４０は、例えば、ＨＤＤ（Hard Disk Drive）等である。
【００６３】
記憶装置４０には、データ管理装置１００が提供するデータがグループ単位で記憶されている。グループとは、データへのアクセス要求（以下、アクセス要求と称する）の履歴により関連性が認められるデータの集合であり、後述するようにＣＰＵ２０の処理によって内容が更新される。アクセス要求は、リード（READ）アクセス要求及びライト（WRITE）アクセス要求を含む。
【００６４】
メモリ装置３０には、例えば記憶装置４０に格納されたグループのうち高頻度にアクセスされるグループが記憶装置４０から読み出されて格納される。これによって、データ管理装置１００は、入力されたアクセス要求に対して高速にデータを出力することができる。
【００６５】
データ管理装置１００は、上記の構成に加えて、ＢＩＯＳ（Basic Input/Output System）を格納したＲＯＭ、プログラムメモリ等を有する。ＣＰＵ２０が実行するプログラムは、ネットワーク６０を介して取得されてもよいし、可搬型メモリやＣＤ−ＲＯＭ等のコンピュータ読み取り可能な可搬型記録媒体がデータ管理装置１００に装着されることにより取得されてもよい。
【００６６】
図４は、本実施形態におけるデータ管理装置の機能構成例である。データ管理装置１００は、ＣＰＵ２０がプログラムを実行することにより機能する機能部として、入出力管理部２１と、解析要否判断部２２と、関連性解析部２３と、グループ配置部２４と、フラグ付与部２５、分割管理部２６、書戻部２７を含む。
【００６７】
メモリ装置３０は、記憶装置４０から読み出したデータを格納するデータ格納領域３２と、読み出したデータを管理するための管理領域３１を含む。管理領域３１には、グループ管理テーブル３０Ａ，関連性保管テーブル３０Ｂが格納されている。グループ管理テーブル３０Ａは、メモリ装置３０に読み出したデータが属するグループを特定する情報を格納する。関連性保管テーブル３０Ｂは、アクセス要求のあったデータ毎に、前回アクセス要求のあったデータを累積して管理するテーブルである。データ格納領域３２には、記憶装置４０からグループ単位で読み出したデータが格納される。
【００６８】
入出力管理部２１は、クライアントコンピュータ７０等の要求元から入力されたアクセス要求に応じてメモリ装置３０及び記憶装置４０を検索し、アクセス要求に対応するデータを要求元に送信する。なお、アクセス要求は、クライアントコンピュータ７０が送信するだけでなく、データ管理装置１００において実行されているプロセスその他の主体がアクセス要求の発行元となる場合もあり得る。また、データ管理装置１００に入出力装置が接続されている場合、ユーザが入出力装置に対してアクセス要求を入力することも想定される。
【００６９】
アクセス要求が入力されると、入出力管理部２１は、まずメモリ装置３０を検索する。アクセス要求の対象となるデータがメモリ装置３０上に存在する場合に、入出力管理部２１は、データをメモリ装置３０から読み出して要求元に返信する。
【００７０】
また、入出力管理部２１は、アクセス要求の対象となるデータがメモリ装置３０上に存在しない場合には、記憶装置４０を検索する。入出力管理部２１は、アクセス要求の対象となるデータが記憶装置４０上に存在する場合に、グループ管理テーブル３０Ａを用いて、要求されたデータの属するグループに含まれる全データを記憶装置４０から読み出す。そして、入出力管理部２１は、その読み出したグループの全データのうち、要求されたデータを要求元に返信する。このとき、入出力管理部２１は、その読み出したグループに含まれる全データを記憶装置４０からメモリ装置３０に格納する。このとき、入出力管理部２１は、記憶装置４０からデータを読み出してメモリ装置３０に格納する場合、後述するように、各データに再利用フラグを付与する。
【００７１】
なお、上記では、入出力管理部２１は、記憶装置４０から読み出したグループに含まれる全データのメモリ装置３０への格納処理を、アクセス要求があったタイミングで行う場合について説明したが、これに限定されない。例えば、入出力管理部２１は、一定期間のアクセス頻度を取得してアクセス頻度が高いグループを優先的に記憶装置４０から読み出してメモリ装置３０に格納してもよい。
【００７２】
解析要否判断部２２は、関連性保管テーブル３０Ｂを用いて、連続するアクセス要求間でアクセス対象のデータが属するグループが同じかどうかを判定することにより、関連性解析部２３に関連性の解析を行わせるか否かを決定する。
【００７３】
関連性解析部２３は、解析要否判断部２２の判定結果に基づいて、関連性保管テーブル３０Ｂから、今回のアクセス要求の対象データの属するグループの全データと、前回のアクセス要求の対象データの属するグループの全データとの関連性を解析する。関連性解析部２３は、その解析結果に基づいてデータのグループの決定を行う。
【００７４】
グループ配置部２４は、関連性解析部２３の決定に従い、グループ管理テーブル３０Ａのグループの配置を更新する。
【００７５】
フラグ付与部２５は、記憶装置４０からグループ単位でデータが読み出されてメモリ装置３０に格納される場合、各データに再利用フラグ（初期値＝０）を付ける。アクセス要求の対象となるデータがメモリ装置３０から読み出された場合、フラグ付与部２５は、その読み出されたデータの再利用フラグを１に更新する。
【００７６】
分割管理部２６は、メモリ装置３０上にあるグループを記憶装置４０に書き戻す場合、その書き戻し対象グループ内にて、再利用フラグ＝１の付いたデータ数（再利用数）を計測する。このとき、分割管理部２６は、再利用数と、後述する計算式とを用いて、最適グループサイズを算出する。書き戻し対象グループのサイズが最適グループサイズを超える場合、分割管理部２６は、書き戻し対象グループを複数のグループに分割する。このとき、分割管理部２６は、書き戻し対象グループ（分割して得られたグループも含む）に属する各データから再利用フラグを消去する。分割管理部２６は、グループ管理テーブル３０Ａに格納されたデータとグループとの関係情報を、分割されたグループに従って更新する。
【００７７】
書戻部２７は、書き戻し対象グループ（分割して得られたグループも含む）毎に、グループに属する全データを記憶装置４０に書き戻す。
【００７８】
解析要否判断部２２、関連性解析部２３、グループ配置部２４、フラグ付与部２５、分割管理部２６、書戻部２７の詳細な処理内容については後述する。
【００７９】
図５は、本実施形態における、データ構造について説明するための図である。記憶装置４０では、データは、「データ名」、「データ内容」を含む。「データ名」は、データを一意に識別するための情報である。「データ内容」は、「データ名」より特定されるデータの内容（値）である。
【００８０】
入出力管理部２１は、アクセス要求が指定するデータがメモリ装置３０になく、かつ記憶装置４０上に存在する場合に、記憶装置４０からそのデータを読み出して要求元に返信すると共に、そのデータをメモリ装置３０に格納する。
【００８１】
このとき、フラグ付与部２５は、記憶装置４０から読み出したデータに、再利用フラグを付与してメモリ装置３０に格納する。付与される再利用フラグの初期値は、「０」である。アクセス要求が指定するデータがメモリ装置３０上に存在する場合に、入出力管理部２１がそのデータをメモリ装置３０から読み出した場合、フラグ付与部２５は、メモリ装置３０上で、その読み出したデータに付与された再利用フラグを「１」に更新する。
【００８２】
記憶装置４０からグループ毎に読み出したデータがメモリ装置３０に格納され続けてメモリ装置３０の容量が不足した場合、書戻部２７は、最も長くアクセスされていないグループから順に記憶装置４０へ書き戻す。すなわち、メモリ装置３０の容量が不足した場合、書戻部２７は、例えば、ＬＲＵ方式によりグループを選択し、そのグループに含まれるデータを記憶装置４０に書き戻す。メモリ装置３０から記憶装置４０へデータを書き戻す場合、分割管理部２６によりその書き戻すデータから再利用フラグが削除された後、書戻部２７は、データを書き戻す。
【００８３】
次に、グループ管理テーブル３０Ａ、及び関連性保管テーブル３０Ｂに格納されるデータが、入出力管理部２１に入力されたアクセス要求に応じて変化する様子について説明する。
【００８４】
図６は、本実施形態におけるデータ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。アクセス要求Ｒｑは、Ｒｅａｄ（Ｘ，Ｙ）で示される。Ｒｅａｄ（Ｘ，Ｙ）の表記は、前回のアクセス要求の対象がデータＹ，今回のアクセス要求の対象がデータＸであることを示す。具体的には、データ管理装置１００に入力されるアクセス要求Ｒｑには、同じ要求元が前回のアクセス要求の対象データＹを識別可能な情報が記述されているものとする。この前回のアクセス要求の対象データＹの情報は、例えばクライアントコンピュータ７０が自ら把握してもよいし、データ管理装置１００側で要求元毎に把握することもできる。この場合、データ管理装置１００は、いずれかのメモリ装置３０やレジスタ等に要求元毎のアクセス要求の履歴を保存しておく。
【００８５】
なお、説明の便宜上、図６において、メモリ装置３０には、データＡ〜Ｄが格納されているとする。このとき、データＡ〜Ｄのそれぞれには、フラグ付与部２５により再利用フラグ＝０が付与されているとする。
【００８６】
図６の状態では、Ｒｅａｄ（Ａ，Ｎｏｎｅ）すなわちデータＡへのアクセス要求が入出力管理部２１に対してなされたとする。この場合、入出力管理部２１は、メモリ装置３０からデータＡを読み出して要求元に出力する。この場合、フラグ付与部２５は、メモリ装置３０に保持されたデータＡの再利用フラグを１に更新する。
【００８７】
また、入出力管理部２１は、今回のアクセス要求から、前回のアクセス要求の対象データの情報を参照して、関連性保管テーブル３０Ｂを更新する。ここで、図６に示すように、Ｒｅａｄ（Ａ，Ｎｏｎｅ）であり、前回値がＮｏｎｅすなわち存在しない状態であるので、入出力管理部２１は、関連性保管テーブル３０Ｂを更新しない。
【００８８】
図７は、図６の状態に続き、データ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。図７では、図６と同じ要求元から（以下同様）Ｒｅａｄ（Ｂ，Ａ）、すなわちデータＢに対するアクセス要求がデータ管理装置１００に対してなされたとする。前回のアクセス要求の対象は、データＡである。
【００８９】
この場合、入出力管理部２１は、メモリ装置３０からデータＢを読み出して要求元に送信する。この場合、フラグ付与部２５は、メモリ装置３０に保持されたデータＢの再利用フラグを１に更新する。
【００９０】
また、入出力管理部２１は、今回のアクセス要求から、前回のアクセス要求の対象データを参照して、関連性保管テーブル３０Ｂを更新する。図７に示す状態では、Ｒｅａｄ（Ｂ，Ａ）より前回のアクセス要求の対象データがＡであるので、入出力管理部２１は関連性保管テーブル３０Ｂにおける今回のアクセス要求の対象データ、すなわちＢの欄に、データＡを示す値を一回分書き込む。
【００９１】
関連性保管テーブル３０Ｂが更新されると、解析要否判断部２２は、今回のアクセス要求の対象データと前回のアクセス要求の対象データが同じグループに属するか否かに応じて、関連性解析部２３による関連性解析が必要か否かを判断する。図７に示す状態では、今回のアクセス要求の対象データＢと前回のアクセス要求の対象データＡが同じグループＧ１に属するため、解析要否判断部２２は関連性解析が不要と判断する。
【００９２】
図８は、図７の状態に続き、データ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。図７では、Ｒｅａｄ（Ｃ，Ｂ）すなわちデータＣを読み込む要求がデータ管理装置１００に対してなされたとする。前回のアクセス要求の対象データはＢである。
【００９３】
入出力管理部２１は、メモリ装置３０からデータＣを読み出して要求元に送信する。この場合、フラグ付与部２５は、メモリ装置３０に保持されたデータＢの再利用フラグを１に更新する。
【００９４】
また、入出力管理部２１は、前回のアクセス要求の対象データを参照して関連性保管テーブル３０Ｂを更新する。図８に示す状態では、前回のアクセス要求の対象データがＢであるので、入出力管理部２１は、関連性保管テーブル３０Ｂにおける今回のアクセス要求の対象データ、すなわちＣの欄に、データＢを示す値を一回分書き込む。
【００９５】
関連性保管テーブル３０Ｂが更新されると、解析要否判断部２２は、今回のアクセス要求の対象データと前回のアクセス要求の対象データが同じグループに属するか否かに応じて、関連性解析部２３による関連性解析が必要か否かを判断する。図８に示す状態では、今回のアクセス要求の対象データＣと前回のアクセス要求の対象データＢとは異なるグループに属するため、解析要否判断部２２は関連性解析が必要と判断する。
【００９６】
関連性解析部２３は、例えばグラフ分割の手法を用いて、データ間の関連性を解析する。関連性解析部２３の処理については、図９を用いて説明する。
【００９７】
図９は、図８に示す状態において関連性解析部２３がグループを変更する前後のグループ配置を示す図である。図８において、矢印の元側が変更前のグループを示し、矢印の先側が変更後のグループを示す。図８において、データＡ、Ｂ等を結ぶ実線の数が、図１５で説明する指標値Ｃｉｊに相当し、破線がグループの境界線を示している。図１５で説明する「異なるグループに属することになるデータの組についての指標値Ｃｉｊの合計」は、指標値Ｃｉｊを仮想的な結合線の数とみなしたときに、切断される結合線の数に相当する。図９の場合、グループ｛Ａ、Ｂ、Ｃ｝とグループ｛Ｄ｝の境界線によって切断される実線の数はゼロであり、このグループ分けにおける指標値Ｃｉｊの合計はゼロであることが分かる。
【００９８】
関連性解析部２３が新たなグループを決定すると、グループ配置部２４が、グループ管理テーブル３０Ａのデータとグループの対応付けを変更する。これについては、図１０を用いて説明する。
【００９９】
図１０は、グループ配置部により変更された後のグループ管理テーブルにおけるデータとグループの対応付けを示す図である。図８と比較して、図１０では、グループ管理テーブル３０Ａにおいて、データＣの属するグループがＧ２からＧ１へ変更されている。
【０１００】
図１１は、図１０の状態に続き、データ管理装置に対してアクセス要求Ｒｑが複数回なされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。図１１に示すアクセス要求Ｒｑは、いずれも今回のアクセス要求の対象データと前回のアクセス要求の対象データとが同じグループに属するため、関連性保管テーブル３０Ｂが更新され、関連性解析及びデータとグループの対応付けの変更は行われない。
【０１０１】
図１２は、図１１の状態に続き、データ管理装置に対してアクセス要求Ｒｑがなされた場合のグループ管理テーブルと関連性保管テーブルとを示す図である。この状態において解析要否判断部２２は、今回のアクセス要求の対象データＤと前回のアクセス要求の対象データＡとが異なるグループに属するため、関連性解析が必要と判断する。このとき、フラグ付与部２５は、メモリ装置３０に保持されたデータＤの再利用フラグを１に更新する。
【０１０２】
図１２の状態では、既にデータＡ、Ｂ、Ｃの間で関連性保管テーブル３０Ｂに複数の履歴が蓄積されている。従って、図１５で説明するように、Ａ−Ｂ間、Ａ−Ｃ間、Ｂ−Ｃ間の指標値Ｃｉｊは比較的大きく算出され、Ａ−Ｄ間の指標値Ｃｉｊは比較的小さく算出されることになる。この結果、図１３に示すように、関連性解析部２３はデータとグループの対応付けを変更しない。
【０１０３】
図１３は、図１２の状態において関連性解析部がグループを決定する前後のグループ配置を示す図である。図１２の場合、Ａ−Ｂ間、Ａ−Ｃ間、Ｂ−Ｃ間の指標値Ｃｉｊはそれぞれ３であるに対して、Ａ−Ｄ間の指標値Ｃｉｊは１である。したがって、Ａ−Ｄ間の関係性に比べて、Ａ−Ｂ間、Ａ−Ｃ間、Ｂ−Ｃ間の関係性が強いので、グループの再編成は行われない。
【０１０４】
図１４は、本実施形態におけるデータ管理装置によって実行されるアクセス要求の際に行われる処理の全体の流れを示すフローチャートの一例である。本フローチャートは、データ管理装置１００に対してアクセス要求がなされる度に実行される。
【０１０５】
まず、入出力管理部２１が、アクセス要求の対象データをメモリ装置３０又は記憶装置４０から読み出して要求元に送信する（Ｓ１）。このとき、アクセス要求の対象データがメモリ装置３０に存在しない場合、入出力管理部２１は、グループ管理テーブル３０Ａを用いて、アクセス要求の対象データが属するグループの全データを記憶装置４０から読み出す（Ｓ２で「Ｎｏ」）。そして、入出力管理部２１は、読み出したグループの全データのうち、アクセス要求の対象データを要求元に送信する。このとき、フラグ付与部２５は、図５で説明したように、記憶装置４０から読み出したデータに再利用フラグ＝０を付与し、その再利用フラグ＝０を付与したデータをメモリ装置３０に格納する（Ｓ４）。
【０１０６】
また、アクセス要求の対象データがメモリ装置３０に存在した場合（Ｓ２で「Ｙｅｓ」）、フラグ付与部２５は、その対象データの再利用フラグを１で付与する（Ｓ３）。
【０１０７】
次に、入出力管理部２１は、アクセス要求に含まれる前回のアクセス要求の対象データを参照して関連性保管テーブル３０Ｂを更新する（Ｓ５）。
【０１０８】
関連性保管テーブル３０Ｂが更新されると、解析要否判断部２２が、関連性解析部２３による関連性解析が必要か否か、すなわち今回のアクセス要求の対象データと前回のアクセス要求の対象データとが異なるグループに属するか否かを判断する（Ｓ６）。関連性解析が不要と判断された場合、すなわち、今回のアクセス要求の対象データと前回のアクセス要求の対象データとが同じグループに属する場合（Ｓ６で「Ｎｏ」）、データ管理装置１００は本フローチャートの処理を終了する。
【０１０９】
関連性解析が必要と判断された場合、すなわち今回のアクセス要求の対象データと前回のアクセス要求の対象データとが異なるグループに属する場合（Ｓ６で「Ｙｅｓ」）、関連性解析部２３は、データの関連性を解析する（Ｓ７）。Ｓ７の処理については、図１５で詳述する。
【０１１０】
次に、グループ配置部２４が、関連性解析部２３の解析結果に基づき、データとグループの対応付けの変更が必要か否か、すなわち、グループの再編成をする必要があるかを判断する（Ｓ８）。データとグループの対応付けの変更が不要と判断された場合（Ｓ８で「Ｎｏ」）、データ管理装置１００は本フローチャートの処理を終了する。
【０１１１】
データとグループの対応付けの変更が必要と判断した場合（Ｓ８で「Ｙｅｓ」）、グループ配置部２４は、図１０で説明したように、グループ管理テーブル３０Ａのデータとグループの対応付けを変更する（Ｓ９）。
【０１１２】
図１５は、関連性解析部により実行される関連性解析処理（Ｓ７）の流れを示すフローチャートの一例である。
【０１１３】
まず、関連性解析部２３は、今回のアクセス要求の対象データの属するグループと、前回のアクセス要求の対象データの属するグループの双方に含まれるデータを全て読み込む（Ｓ１１）。
【０１１４】
次に、関連性解析部２３は、読み込んだデータから二つのデータｉ，ｊを取り出してＳ１０２〜Ｓ１０６の処理を行うことを、全てのｉ，ｊの組み合わせ（ｉ≠ｊ）について行う。図１５において、ｍは、Ｓ１００において読み込んだデータの種類の数である。
【０１１５】
関連性解析部２３は、関連性保管テーブル３０Ｂに格納されたデータｉ欄の履歴におけるデータｊの数Ｃｉｊ*をカウントする（Ｓ１２）。次に、関連性解析部２３は、関連性保管テーブル３０Ｂに格納されたデータｊ欄の履歴におけるデータｉの数Ｃｊｉ*をカウントする（Ｓ１３）。
【０１１６】
次に、関連性解析部２３は、Ｃｉｊ*とＣｊｉ*を加算してデータｉとｊの関連性を示す指標値Ｃｉｊを算出する（Ｓ１４）。図８の場合、ＣAB＝１、ＣAC＝０、ＣAD＝０、ＣBC＝１、ＣBD＝０、ＣCD＝０が得られる。
【０１１７】
関連性解析部２３は、全てのｉ，ｊについてＳ１０２〜Ｓ１０６の処理を行うと、グループ内の最大データ数（例えば３個）を満たす範囲内で、データ数ｍを分割する全てのグループパターンを設定する（Ｓ１５）。図８の例ではデータの個数が４個（データＡ〜Ｄ）であり、最大データ数が３個であるとする。このとき、グループパターンは、３：１で分けた場合には４通り（（ＡＢＣ）（Ｄ）、（ＢＣＤ）（Ａ）、（ＣＤＡ）（Ｂ）、（ＡＢＤ）（Ｃ））となる。また、２：２で分けた場合には６通り（（ＡＢ）（ＣＤ）、（ＡＣ）（ＢＤ）、（ＡＤ）（ＢＣ）、（ＢＣ）（ＡＤ）、（ＢＤ）（ＡＣ）、（ＣＤ）（ＡＢ））となる。このように、全部で１０通りのグループパターンが設定される。
【０１１８】
次に、関連性解析部２３は、各グループパターンを採用した場合に、異なるグループに属することになったデータ同士の指標値Ｃｉｊを全て抽出して合計する（Ｓ１６）。
【０１１９】
そして、関連性解析部２３は、異なるグループに属することになるデータの組についての指標値Ｃｉｊの合計が最も小さいグループパターンを選択し、新たなグループを決定する（Ｓ１７）。図８の場合には、以下のようになる。
（ＡＢＣ）（Ｄ）：ＣAD＋ＣBD＋ＣCD＝０
（ＢＣＤ）（Ａ）：ＣAB＋ＣAC＋ＣAD＝１
（ＣＤＡ）（Ｂ）：ＣAB＋ＣBC＋ＣBD＝２
（ＡＢＤ）（Ｃ）：ＣAC＋ＣBC＋ＣCD＝１
（ＡＢ）（ＣＤ）：ＣAC＋ＣAD＋ＣBC＋ＣBD＝１
（ＡＣ）（ＢＤ）：ＣAB＋ＣAD＋ＣBC＋ＣCD＝２
（ＡＤ）（ＢＣ）：ＣAD＋ＣAC＋ＣBD＋ＣCD＝１
（ＢＣ）（ＡＤ）：ＣAB＋ＣBD＋ＣAC＋ＣCD＝１
（ＢＤ）（ＡＣ）：ＣAB＋ＣBC＋ＣAD＋ＣCD＝２
（ＣＤ）（ＡＢ）：ＣAC＋ＣBC＋ＣAD＋ＣBD＝１
これより、グループ（ＡＢＣ）と、グループ（Ｄ）のグループパターンの指標値Ｃｉｊの合計が０となり、最も小さいので、関連性解析部２３は、このグループパターン（ＡＢＣ）（Ｄ）を新たなグループとして決定する。
【０１２０】
次に、メモリ装置３０から記憶装置４０へのデータの書き戻しを行う場合のグループの分割処理について説明する。
【０１２１】
図１６は、本実施形態における、メモリ装置３０から記憶装置４０へのデータの書き戻しを行う場合、書き戻し対象のグループサイズに応じて、書き戻し対象のグループを分割する処理を説明するための図である。
【０１２２】
メモリ装置３０から記憶装置４０へのデータの書き戻しを行う場合、書き戻し対象のグループサイズが最適グループサイズよりも大きい場合、分割管理部２６は、書き戻し対象のグループを分割する。この場合、書戻部２７は、書き戻し対象の全グループ（分割されて得られたグループも含む）を記憶装置４０に書き戻す。なお、最適グループサイズについては後述する。
【０１２３】
図１７は、本実施形態におけるメモリ装置にあるいずれかのグループを記憶装置に書き戻す場合の処理フローを示す。
【０１２４】
メモリ装置３０の容量が不足した場合、入出力管理部２１は、次の処理を行う。メモリ装置３０の容量が不足した場合とは、例えば、記憶装置４０から読み出したグループをメモリ装置３０へ格納しようとしたときにメモリ装置３０の容量が不足した場合、または、メモリ装置３０に予め設定した閾値を超えてデータが格納されている場合等である。このような場合、入出力管理部２１は、メモリ装置３０に格納されたグループから、いずれかのグループを書込対象グループとして選択する（Ｓ２０）。ここで、いずれかのグループとは、例えばＬＲＵ方式により決定されるグループ、すなわち、最もアクセスされていないグループである。
【０１２５】
分割管理部２６は、選択した書込対象グループにおいて再利用フラグの付いたデータ数（再利用数）を算出する（Ｓ２１）。
【０１２６】
分割管理部２６は、以下の式（１）を用いて、再利用数から、最適グループサイズを算出する（Ｓ２２）。ここで、以下の最適サイズの算出式について説明する。再利用数をｕで表す。最適グループサイズをｓで表す。以下のパラメータは、最適グループサイズの算出にて用いるパラメータである。なお、ランダムアクセスのコストａと、シーケンシャルアクセスのコストｂは、記憶装置に予め設定されている。
・ランダムアクセスのコスト：ａ［ｍｓ］
・シーケンシャルアクセスのコスト：ｂ［ＭＢ／ｓ］＝ｂ［ＫＢ／ｓ］
・再利用フラグ＝１を有するデータのサイズ合計：ｄ
【０１２７】
このとき、ＬＲＵのコストＣlは、Ｃl＝ｕａ＋ｄ／ｂで表される。また、ＤＬＭのコストは、Ｃa＝ａ＋ｓ／ｂで表される。ここで、Ｃl＞Ｃaが要求されるから、最適グループサイズは、
ｓ＜（ｕ−１）ａｂ＋ｄ            （１）
で示される。
【０１２８】
分割管理部２６は、書込対象グループのサイズ＞最適グループサイズであるか否かを判定する（Ｓ２３）。書込対象グループのサイズ≦最適グループサイズである場合（Ｓ２３で「Ｎｏ」）、Ｓ２６の処理へ進む。
【０１２９】
書込対象グループのサイズ＞最適グループサイズである場合（Ｓ２３で「Ｙｅｓ」）、分割管理部２６は、グループ分割処理を実行する（Ｓ２４）。ここでは、分割管理部２６は、書込対象グループのサイズが最適グループサイズより小さくなるように現在のグループを分割し、分割して得られたグループも、そのサイズが最適グループサイズより小さくなるように分割する。Ｓ２５の処理については、図１８で詳述する。
【０１３０】
分割管理部２６は、Ｓ２４にて分割されたグループに従って、グループ管理テーブル３０Ａの情報を更新する（Ｓ２５）。
【０１３１】
分割管理部２６は、書込対象グループに含まれる全データから再利用フラグの項目を削除する（Ｓ２６）。このとき、書込対象グループが複数のグループに分割されている場合には、書戻部２７は、その分割されて得られた全グループに含まれる全データから再利用フラグの項目を削除する。
【０１３２】
書戻部２７は、書込対象グループを記憶装置に書き戻す。このとき、書込対象グループが複数のグループに分割されている場合には、書戻部２７は、その分割されて得られた全グループを記憶装置に書き戻す（Ｓ２７）。
【０１３３】
図１８は、本実施形態におけるグループ分割処理（Ｓ２５）の詳細フローを示す。以下では、分割の基礎となる書込対象グループを「対象グループ」と称する。分割管理部２６は、対象グループから、データサイズが最適グループサイズを超える１以上のデータを分離し、それぞれそのデータが１つだけ含まれるグループとする（Ｓ３１）。
【０１３４】
分割管理部２６は、対象グループのサイズ＜最適グループサイズであるか否かを判定する（Ｓ３２）。対象グループのサイズ＜最適グループサイズである場合（Ｓ３２で「Ｙｅｓ」）、本フローは終了する。
【０１３５】
対象グループのサイズ≧最適グループサイズである場合（Ｓ３２で「Ｎｏ」）、分割管理部２６は、対象グループから、再利用フラグ＝１がついたデータを分離し、その分離したデータをまとめて１つのグループとする（Ｓ３３）。
【０１３６】
分割管理部２６は、再び、対象グループのサイズ＜最適グループサイズであるか否かを判定する（Ｓ３４）。対象グループのサイズ＜最適グループサイズである場合（Ｓ３４で「Ｙｅｓ」）、本フローは終了する。
【０１３７】
対象グループのサイズ≧最適グループサイズである場合（Ｓ３２で「Ｎｏ」）、分割管理部２６は、対象グループに残ったデータを大きさ順（大きい順または小さい順）にソートする（Ｓ３５）。
【０１３８】
分割管理部２６は、新しいグループを作成する（Ｓ３６）。分割管理部２６は、対象グループに残ったデータのうち、最も大きなデータを新しいグループに移す（Ｓ３７）。
【０１３９】
分割管理部２６は、対象グループが空か否か、すなわち、対象グループ内にデータが残っているか否かを判定する（Ｓ３８）。対象グループが空である場合（Ｓ３８で「Ｙｅｓ」）、本フローは終了する。
【０１４０】
対象グループが空でない場合（Ｓ３８で「Ｎｏ」）、分割管理部２６は、対象グループのサイズ＞最適グループサイズであるか否かを判定する（Ｓ３９）。対象グループのサイズ＞最適グループサイズである場合（Ｓ３９で「Ｙｅｓ」）、Ｓ３７の処理へ戻る。対象グループのサイズ≦最適グループサイズである場合（Ｓ３９で「Ｎｏ」）、Ｓ３６の処理へ戻る。
【０１４１】
本実施形態によれば、再利用数から最適なグループサイズを算出し、そのサイズ以下になるようにグループを分割することにより、再利用数とグループサイズのミスマッチを防ぎ、ＤＬＭの性能低下を防ぐことができる。
【０１４２】
必要に応じてグループサイズを分割することにより、大き過ぎるグループサイズから来る性能低下が抑止される。また、再配置アルゴリズムには何ら制限を設けていないため、グループサイズが小さくなり過ぎることもない。単にＬＲＵの性能を下回る可能性が高いときに、グループを小さくすることができる。
【０１４３】
再配置アルゴリズムとは独立した手法で、定量的に観測されたデータを基にディスクに書き戻す時にグループを分割するため、高度な再配置アルゴリズムを用いる必要もない。
【０１４４】
グループサイズの上限を設定するわけではないので、依然として柔軟なグループ化（再配置）が可能である。直近でアクセスされた（関連性の強い）データは分割されない。
【０１４５】
なお、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または実施形態を取ることができる。
【０１４６】
上記実施形態に関し、さらに以下の付記を開示する。
（付記１）
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループを選択する選択部と、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割する分割部と、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する書込部と
を備えることを特徴とするデータ格納制御装置。
（付記２）
前記データ格納制御装置は、さらに、
前記分割の結果に基づいて、前記データと前記グループとを対応付けたグループ管理情報を更新する更新部と、
データアクセス要求に対応するデータが前記第２記憶部にない場合、前記グループ管理情報に基づいて、該データアクセス要求に対応するデータが属するグループに含まれるデータを前記第１記憶部から取得する取得部
を備えることを特徴とする付記１に記載のことを特徴とするデータ格納制御装置。
（付記３）
前記分割部は、
前記選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータ数を用いて、基準となるグループのサイズを算出し、
前記選択されたグループのサイズと前記基準となるグループのサイズとを比較し、比較結果に応じて、該選択されたグループを分割する
ことを特徴とする付記１または２に記載のデータ格納制御装置。
（付記４）
前記分割部は、
前記選択されたグループに含まれるデータから、前記基準となるグループのサイズよりも大きいサイズのデータを分離し、分離した該データをそれぞれ、相互に別グループとする
ことを特徴とする付記１〜３のうちいずれか１項に記載のデータ格納制御装置。
（付記５）
前記分割部は、
前記選択されたグループに含まれるデータのうち、前記データアクセス要求に応じてアクセスされたデータを分離し、分離した該データをまとめて１つのグループとする
ことを特徴とする付記１〜４のうちいずれか１項に記載のデータ格納制御装置。
（付記６）
コンピュータに、
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループを選択し、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、前記データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割し、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する
処理を実行させるデータ格納制御プログラム。
（付記７）
前記コンピュータに、さらに、
前記分割の結果に基づいて、前記データと前記グループとを対応付けたグループ管理情報を更新し、
データアクセス要求に対応するデータが前記第２記憶部にない場合、前記グループ管理情報に基づいて、該データアクセス要求に対応するデータが属するグループに含まれるデータを前記第１記憶部から取得する
ことを特徴とする付記６に記載のデータ格納制御プログラム。
（付記８）
前記分割において、
前記選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータ数を用いて、基準となるグループのサイズを算出し、
前記選択されたグループのサイズと前記基準となるグループのサイズとを比較し、比較結果に応じて、該第２グループを分割する
ことを特徴とする付記６または７に記載のデータ格納制御プログラム。
（付記９）
前記分割において、
前記選択されたグループに含まれるデータから、前記基準となるグループのサイズよりも大きいサイズのデータを分離し、分離した該データをそれぞれ、相互に別グループとする
ことを特徴とする付記６〜８のうちいずれか１項に記載のデータ格納制御プログラム。
（付記１０）
前記分割において、
前記選択されたグループに含まれるデータのうち、前記データアクセス要求に応じてアクセスされたデータを分離し、分離した該データをまとめて１つのグループとする
ことを特徴とする付記６〜９のうちいずれか１項に記載のデータ格納制御プログラム。
（付記１１）
コンピュータが、
第１記憶部から取得したデータを格納する第２記憶部の空き容量不足が発生した場合、該第２記憶部に格納されているいずれかのグループである第２グループを選択し、
選択された前記グループに含まれるデータのうち、前記第２記憶部における、前記データアクセス要求に対応するデータへのアクセス状況に応じて、前記選択されたグループを分割し、
分割して得られたグループ単位で、それぞれのグループに含まれるデータを前記第１記憶部に格納する
ことを特徴とするデータ格納制御方法。
（付記１２）
前記コンピュータに、さらに、
前記分割の結果に基づいて、前記データと前記グループとを対応付けたグループ管理情報を更新し、
データアクセス要求に対応するデータが前記第２記憶部にない場合、前記グループ管理情報に基づいて、該データアクセス要求に対応するデータが属するグループに含まれるデータを前記第１記憶部から取得する
ことを特徴とする付記１１に記載のデータ格納制御方法。
（付記１３）
前記分割において、
前記選択されたグループに含まれるデータのうち、データアクセス要求に応じてアクセスされたデータ数を用いて、基準となるグループのサイズを算出し、
前記選択されたグループのサイズと前記基準となるグループのサイズとを比較し、比較結果に応じて、該第２グループを分割する
ことを特徴とする付記１１または１２に記載のデータ格納制御方法。
（付記１４）
前記分割において、
前記選択されたグループに含まれるデータから、前記基準となるグループのサイズよりも大きいサイズのデータを分離し、分離した該データをそれぞれ、相互に別グループとする
ことを特徴とする付記１１〜１３のうちいずれか１項に記載のデータ格納制御方法。
（付記１５）
前記分割において、
前記選択されたグループに含まれるデータのうち、前記データアクセス要求に応じてアクセスされたデータを分離し、分離した該データをまとめて１つのグループとする
ことを特徴とする付記１１〜１４のうちいずれか１項に記載のデータ格納制御方法。
【符号の説明】
【０１４７】
１      データ格納制御装置
２      選択部
３      分割部
４      更新部
５      取得部
７      第１記憶部
８      第２記憶部
１００  データ管理装置
２０    ＣＰＵ
２１    入出力管理部
２２    解析要否判断部
２３    関連性解析部
２４    グループ配置部
２５    フラグ付与部
２６    分割管理部
２７    書戻部
３０    メモリ装置
３０Ａ  グループ管理テーブル
３０Ｂ  関連性保管テーブル
３１    管理領域
３２    データ格納領域
４０    記憶装置
【図２】
2016162243.tif 000003
【図３】
2016162243.tif 000004
【図４】
2016162243.tif 000005
【図５】
2016162243.tif 000006
【図６】
2016162243.tif 000007
【図７】
2016162243.tif 000008
【図８】
2016162243.tif 000009
【図９】
2016162243.tif 000010
【図１０】
2016162243.tif 000011
【図１１】
2016162243.tif 000012
【図１２】
2016162243.tif 000013
【図１３】
2016162243.tif 000014
【図１４】
2016162243.tif 000015
【図１５】
2016162243.tif 000016
【図１６】
2016162243.tif 000017
【図１７】
2016162243.tif 000018
【図１８】
2016162243.tif 000019
【図１】
2016162243.tif 000020
【手続補正書】
【提出日】平成28年1月19日(2016.1.19)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
次に、関連性解析部２３は、読み込んだデータから二つのデータｉ，ｊを取り出してＳ１２〜Ｓ１４の処理を行うことを、全てのｉ，ｊの組み合わせ（ｉ≠ｊ）について行う。図１５において、ｍは、Ｓ１１において読み込んだデータの種類の数である。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
関連性解析部２３は、全てのｉ，ｊについてＳ１２〜Ｓ１４の処理を行うと、グループ内の最大データ数（例えば３個）を満たす範囲内で、データ数ｍを分割する全てのグループパターンを設定する（Ｓ１５）。図８の例ではデータの個数が４個（データＡ〜Ｄ）であり、最大データ数が３個であるとする。このとき、グループパターンは、３：１で分けた場合には４通り（（ＡＢＣ）（Ｄ）、（ＢＣＤ）（Ａ）、（ＣＤＡ）（Ｂ）、（ＡＢＤ）（Ｃ））となる。また、２：２で分けた場合には６通り（（ＡＢ）（ＣＤ）、（ＡＣ）（ＢＤ）、（ＡＤ）（ＢＣ）、（ＢＣ）（ＡＤ）、（ＢＤ）（ＡＣ）、（ＣＤ）（ＡＢ））となる。このように、全部で１０通りのグループパターンが設定される。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図１７
【補正方法】変更
【補正の内容】
【図１７】
2016162243.tif 000021
【手続補正４】
【補正対象書類名】図面
【補正対象項目名】図１８
【補正方法】変更
【補正の内容】
【図１８】
2016162243.tif 000022