(57)【特許請求の範囲】
【請求項１】
要求元処理装置からの情報のアクセスが行われるストレージを管理するストレージ管理装置において実行されるストレージ管理方法であって、
データサンプリング手段が、前記情報を構成するデータユニットのうち所定数のデータユニットを前記ストレージからランダムに取得し、
サンプル重複率算出手段が、前記取得したデータユニットが互いに重複している割合であるサンプルユニット重複率を算出し、
全重複率推定手段が、前記算出したサンプルユニット重複率を用いた所定関数により前記ストレージに格納されているデータユニット全体が互いに重複している割合である全データユニット重複率を推定し、
推定結果出力手段が、前記推定した全データユニット重複率を出力装置に出力し、
前記所定関数は、ヒープス（Heaps）の法則を用いた関数である
ことを特徴とするストレージ管理方法。
【請求項２】
要求元処理装置からの情報のアクセスが行われるストレージを管理するストレージ管理装置であって、
前記情報を構成するデータユニットのうち所定数のデータユニットを前記ストレージからランダムに取得するデータサンプリング手段と、
前記取得したデータユニットが互いに重複している割合であるサンプルユニット重複率を算出するサンプル重複率算出手段と、
前記算出したサンプルユニット重複率を用いた所定関数により前記ストレージに格納されているデータユニット全体が互いに重複している割合である全データユニット重複率を推定する全重複率推定手段と、
前記推定した全データユニット重複率を出力装置に出力する推定結果出力手段と、
を備え、
前記所定関数は、ヒープス（Heaps）の法則を用いた関数である
ことを特徴とするストレージ管理装置
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サービス提供者がネットワークを介して利用者へ提供する情報格納サービス等のストレージサービスに関し、特に、ストレージサービスにおけるストレージの重複除去技術に関する。
【背景技術】
【０００２】
昨今、ストレージ（ハードディスク等に確保されたメモリ領域）を顧客に貸し出し、課金するビジネス（ストレージサービス）がストレージサービスプロバイダ（Storage Service Provider：ＳＳＰ）という名前で成長している。具体的には、ストレージサービスプロバイダ側で顧客のサーバ（要求元処理装置）に対応させたストレージを用意し、顧客はストレージサービスプロバイダに対して必要な分だけストレージの容量を要求し、その容量分だけのレンタル料を支払うシステムである。
【０００３】
顧客は、ストレージの容量分に対応した料金を支払うことになるため、同じ内容のデータを重複して格納するという無駄が生じることは望まない。このような無駄を排除する技術が重複除去技術である。すなわち、重複排除技術とは、データ（以下、対象データと称する）をストレージに格納する際に、既に同じ内容のデータが当該ストレージに格納されているかを検出し、つまりデータの重複を検出し、既に格納されていれば当該対象データを例えばリンクで置き換えることにより重複データを１つにまとめる（排除する）技術をいう（例えば、特許文献１、２参照。）。また、既に重複している同じ内容のデータを１つだけ残して他を除去する技術をいう。
【０００４】
このような重複除去技術を用いた重複除去システムは、ストレージあるいはファイルの内容を一定の単位に切り、暗号化ハッシュなど衝突に関して安全なハッシュ値をとり、ハッシュ値の比較によって重複の判定を行う。重複したデータは記録しないことでストレージシステムの容量を削減することが目的である。
【０００５】
この重複排除技術によれば、データの格納に必要なストレージの容量をより少なくすることができる。こうしたストレージの有効利用は、電力消費や設置場所の使用率を抑えることにもつながる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００９−８０６７１号公報
【特許文献２】特開２０１１−１１８７１２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述のような従来の技術においては、下記のような問題点がある。
顧客は、システムに対して負荷がかかり、かつ、処理時間もかかってしまう重複除去のデメリットと、重複除去を行うことによりストレージの無駄、ひいてはコストの無駄を省くというメリットとを天秤にかけ、最も適切なタイミングで重複除去を行うことを望む。データの重複度はストレージの利用状況により異なるので、重複除去システムの導入に際しては、あらかじめ重複度の測定を行い、削減により得られる得失を判定する必要がある。
【０００８】
従来の方法では、すべてのデータを読んで重複率を測定しなければならなかった。しかし、ストレージの容量が大きい場合にはそれが不可能な場合が多い。すなわち、処理時間がかかったり、重複率測定のためのデータの読み書きに負荷がかかり通常のサービスに影響したりするからである。また、ストレージの容量の一部を読んで、得られた重複率を使用する場合は、読んだ量により重複率は変化するので、正確な重複率とは言えない。極端なケースを言えば、１ブロックしか読まなければ、重複は発生しないので、０％の重複率となる。このようにサンプル数が少ないと重複率は少ない傾向があり、間違った結論になる可能性がある。また、先頭の１０％を読むというような方法の場合、読み出す場所による重複の偏りを避けることができない。
【０００９】
１つの側面では、本発明は、重複データの量またはその除去にかかる時間の予測のための処理時間の短縮化を図ることが可能なストレージ管理方法およびストレージ管理装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、上記課題を解決するため、下記のような構成を採用した。
すなわち、本発明のストレージ管理方法の一観点によれば、要求元処理装置からの情報のアクセスが行われるストレージを管理するストレージ管理装置において実行されるストレージ管理方法であって、データサンプリング手段が、前記情報を構成するデータユニットのうち所定数のデータユニットを前記ストレージからランダムに取得し、サンプル重複率算出手段が、前記取得したデータユニットが互いに重複している割合であるサンプルユニット重複率を算出し、全重複率推定手段が、前記算出したサンプルユニット重複率を用いた所定関数により前記ストレージに格納されているデータユニット全体が互いに重複している割合である全データユニット重複率を推定し、推定結果出力手段が、前記推定した全データユニット重複率を出力装置に出力し、前記所定関数は、ヒープス（Heaps）の法則を用いた関数であることを特徴とするストレージ管理方法が提供される。
【発明の効果】
【００１１】
本発明によれば、重複データの量またはその除去にかかる時間の予測のための処理時間の短縮化を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明を適用したストレージ管理装置の機能ブロックを示す図である。
【図２】サンプリングしたデータユニットの数（サンプル数）とユニークデータ数との関係を示す図である。
【図３】（ｓ−ｋ）Ｃ（ａ）をｙ軸、ｋをｘ軸にとって両者の関係をグラフに表した図（その１）である。
【図４】（ｓ−ｋ）Ｃ（ａ）をｙ軸、ｋをｘ軸にとって両者の関係をグラフに表した図（その２）である。
【図５】（ｓ−ｋ）Ｃ（ａ）をｙ軸、ｋをｘ軸にとって両者の関係をグラフに表した図（その３）である。
【図６】本発明を適用したストレージ管理処理の流れを示すフローチャートである。
【図７】ユニークデータ数とサンプル数の関係を示す図である。
【図８】ユニークデータ数とサンプル数の関係を両対数グラフで表わした図である。
【図９】サンプリング率と推定率との関係を示す図である。
【図１０】本発明を適用したストレージ管理装置のハードウエア構成を示す図である。
【図１１】情報処理装置にプログラムやデータを提供する方法を示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
図１は、本発明を適用したストレージ管理装置の機能ブロックを示す図である。
図１において、ストレージ管理装置１は、サンプル取得機能１１、サンプル値記憶機能１２、格納部１３、ユニークデータ判定機能１４、推定機能１５、及び出力部１６を備え、顧客のサーバである要求元処理装置からの情報のアクセスが行われるストレージ２を管理する。
【００１４】
サンプル取得機能１１は、前記情報を構成するデータユニットのうち所定数のデータユニットを、サンプル２１として前記ストレージ２からランダムに取得する。ランダムに取得するのは、場所による偏りを避けるためであり、例えば、ターゲットとなるストレージ２のオフセットの選び方をランダムにする。
【００１５】
サンプル値記憶機能１２は、サンプル取得機能１１が取得したサンプル２１のストレージ２における格納場所及びサンプル２１のデータを格納部１３に格納する。
ユニークデータ判定機能１４は、前記サンプル取得機能１１によって取得したサンプル２１が互いに重複している割合であるサンプルユニット重複率を算出する。サンプルユニット重複率に算出方法については後述する。
【００１６】
推定機能１５は、前記ユニークデータ判定機能１４によって算出したサンプルユニット重複率を用いた所定関数により、前記ストレージ２に格納されているデータユニット全体が互いに重複している割合である全データユニット重複率を推定する。
【００１７】
そして、出力部１６は、前記推定機能１５によって推定した全データユニット重複率を出力する。
このように、本発明を適用したストレージ管理装置１は、全データユニットの重複率を算出するのではなく、サンプリングするサンプル２１の数量と重複率の関係に注目することで、サンプリングにより効率的に全データユニットの重複率を推定する。これにより、ストレージ２の重複除去を適用する判断のためのベンチマークツールとして用いることが出来る。また、動的に全データユニットの重複率を推定することで、システムの状況をモニタリングすることができる。
【００１８】
また、上記サンプリングを継続的に繰り返し行い、その間のサンプルユニット重複率を断続的に算出する。そして、全データユニット重複率を推定するのに十分なサンプリング回数となったところで、サンプル数と重複率の所定関数による近似を行い、その関数から全データユニットの重複率を推定する。
【００１９】
ここで、上記所定関数としては、様々な関数を用いることが出来る。例えば、第１の関数としては、前記取得したデータユニットの所定数と前記サンプルユニット重複率との関係を近似したｎ次関数である。例えば、２次関数である。また、第２の関数として、ジップ（Zipf）分布に従う場合、ヒープス（Heaps）の法則を用いた関数を適用できる。
【００２０】
次に、重複率について説明する。
説明を簡単にするために、ストレージ２に格納されているデータユニットを集合で表わす。
【００２１】
例えば、ストレージ２に格納されている全データユニットが、集合｛「Ａ」，「Ｂ」，「Ｂ」，「Ｂ」，「Ｃ」，「Ｄ」，「Ｄ」，「Ｄ」，「Ｄ」，「Ｄ」｝の１０個で構成されているとする。この集合を構成するデータユニットの種類は、「Ａ」「Ｂ」「Ｃ」「Ｄ」の４種類（４個）である。
【００２２】
この場合、全データの数は「１０」、ユニークなデータの数は「４」である。ここで、全データの数に占めるユニークなデータの数をユニークデータ率という。上記例の場合は、ユニークデータ率は「０．４（４０％）」である。
重複率は、全体（１（１００％））からユニークデータ率（０．４）を引いた値「０．６（６０％）」となる。
【００２３】
図２は、サンプリングしたデータユニットの数（サンプル数）とユニークデータ数との関係を示す図である。
図２に示すように、サンプル数の増加に伴いユニークデータ数も増加する。この関係は、所定の関数で表わすことができる。ただし、この関数の特徴は、サンプル数の少ない領域（サンプリング領域２２）においては増加の幅が大きいが、サンプル数が多くなるにつれて増加の幅は小さくなっている。そして、この関数の特徴から、サンプリング領域におけるサンプル数とユニークデータ数との関係から、全てのデータユニットをサンプリングした場合の領域（最終領域２３）におけるユニークデータ数を推定することが可能となる。
【００２４】
ここで、複数個あるものは何回目のサンプリングで発見されるかに注目する。
例えば、ａ個の玉をｂ個の箱に入れた場合を考える。なお、各箱に玉は何個でも入るものとする。
【００２５】
このような場合、左端から箱を開けたときにｋ回目に初めて玉が出てくる確率Ｐ（ｋ）は、下記の式（１）のようになる。
Ｐ（ｋ）＝（（ｂ−ｋ＋１）Ｈ（ａ））／（（ｂ）Ｈ（ａ））＝（（ｂ＋ａ−ｋ）Ｃ（ａ））／（（ｂ＋ａ−１）Ｃ（ａ））    ・・・式（１）
Ｈは重複組み合わせの数、Ｃは二項係数、Ｋは定数項である。
【００２６】
ここで、ｓ＝ｂ＋ａとすると、確率Ｐ（ｋ）は、下記の式（２）のようになる。
Ｐ（ｋ）＝Ｋ（ｓ−ｋ）（ｓ−１−ｋ）…（ｓ−ａ＋１−ｋ）    ・・・式（２）
このＰ（ｋ）は、ｋの多項式となる。
【００２７】
そして、１≦ｋ≦ｂの範囲ですべての項が正であり、ｋ＝ｂのとき、ｓ−ａ＋１−ｋ＝１となる。
また、ｂ＝１００、ａ＝１，…，２９で、（ｓ−ｋ）Ｃ（ａ）とｋとの関係をグラフにする。
【００２８】
図３、図４及び図５は、（ｓ−ｋ）Ｃ（ａ）をｙ軸、ｋをｘ軸にとって両者の関係をグラフに表した図であり、それぞれｙ軸のスケールが異なる。
図３乃至図５からわかるように、ａの値にかかわらず、どの曲線も同様の形状をしている。ｋの値が小さい領域では、両者の関係は、直線で近似できる。また、増加率は線形で負の値となっている。
【００２９】
上述したように、本発明を適用した実施の形態では、複数個あるものは何回目のサンプリングで発見されるかに注目している。
一般に、最初の方のサンプリングで見つかり、最後のサンプリングで初めて見つかる可能性は低い。
【００３０】
ここで、サンプル数をＳ、ユニークデータ数をＵとすると、下記の式（３）、式（４）が成り立つ。
ｄＵ／ｄＳ＝−ａ0×Ｓ＋ａ1  （ａi≧０）    ・・・式（３）
Ｕ＝−ａ0／２×Ｓ2＋ａ1×Ｓ＋ａ2    ・・・式（４）
【００３１】
図６は、本発明を適用したストレージ管理処理の流れを示すフローチャートである。
図６に示したストレージ管理処理は、図１を用いて説明したストレージ管理装置１において実行される。
【００３２】
ステップＳ６０１において、全体のブロック個数をＮ、通算のサンプル数をＳ（初期値：０）、累積ユニークデータ数をＵ（初期値：０）、及び１回当たりのサンプル数をｎとして設定する。
そして、下記ステップＳ６０２乃至Ｓ６０５を、十分なサンプリング回数であるｒ回繰り返す。
【００３３】
まず、ステップＳ６０２において、ストレージ２に格納されているデータユニットのうち、メモリ１３を参照することで未だ取得していないデータユニットｎ個を、新たなサンプル２１として前記ストレージ２からランダムに取得する。
【００３４】
ステップＳ６０３において、直前のステップＳ６０２で取得したサンプル２１を、過去にステップＳ６０２で取得したサンプル２１と比較し、ユニークなサンプル２１の数をｘとする。そして、Ｓ＋ｎをＳに代入し、Ｕ＋ｘをＵに代入する。
【００３５】
次に、ステップＳ６０４において、データのＳ,Ｕの組を上述のｎ次関数、例えば２次関数にあてはめ、最小二乗法により係数ａ0，ａ1，ａ2を求める。Ｓ＝Ｎの場合のＵ、つまりＵ（Ｎ）＝−ａ0／２×Ｎ＋ａ1×Ｎ＋ａ2を計算し、Ｕの推定値とする。
【００３６】
そして、ステップＳ６０５において、計算したＵ（Ｎ）の値が、前回計算した値と比較して、十分に小さい場合、例えば所定範囲内の場合、十分なサンプリング回数（ｒ）に達したと判断し（ステップＳ６０５：Ｙｅｓ）、本ストレージ管理処理を終了する。他方、比較した値が所定範囲内に入らなかった場合（ステップＳ６０５：Ｎｏ）、ステップＳ６０２に戻る。
【００３７】
上述したように、サンプル数と重複度の関係は、２次関数等のｎ次関数で近似できることを説明してきた。ｎ次関数による近似により、全体の重複度の推定がランダムサンプリングにより可能になる。したがって、必要な時間が短縮できる。
【００３８】
ところで、本発明を適用したストレージ管理方法およびストレージ管理装置は、上記ｎ次関数の代わりに他の関数を用いることも可能である。
図７は、ユニークデータ数とサンプル数の関係を示す図であり、図８は、ユニークデータ数とサンプル数の関係を両対数グラフで表わした図であり、図９は、サンプリング率と推定率との関係を示す図である。
【００３９】
図７に示すように、サンプル数の増加に伴いユニークデータ数も増加する。そして、ユニークデータ数の対数とサンプル数の対数の関係をグラフで表わすと、図８に示すように、直線で近似することができる。
【００４０】
このような関係に近いものがヒープス（Heaps）の法則と呼ばれるものである。
ヒープスの法則は、一般的に下記の式（５）のように表わされる。
Ｍ＝ｋＴb    ・・・式（５）
【００４１】
ここで、Ｍはユニークデータ数、Ｔはサンプル数、ｋは所定の定数であり、１０〜１００の範囲が好ましい。また、ｂは所定の定数であり、０．４〜０．６の範囲が好ましい。
【００４２】
このヒープスの法則を表わした関数の両対数をとると、下記の式（６）のようになる。
log（Ｍ）＝ｂ×log（Ｔ）＋log（ｋ）    ・・・式（６）
このヒープスの法則を表わした関数は、冪関数であるので、両対数グラフにおいて線形になる。
【００４３】
図１０は、本発明を適用したストレージ管理装置のハードウエア構成を示す図である。
図１に示すストレージ管理装置は、例えば図１０に示す情報処理装置（コンピュータ）１０００を使用して実現することができる。図１０に示す情報処理装置１０００は、ＣＰＵ（Central Processing Unit）１００１、メモリ１００２、入力装置１００３、出力装置１００４、外部記録装置１００５、媒体駆動装置１００６、及びネットワーク接続装置１００７を備える。また、これらはバス１００８により互いに接続されている。
【００４４】
メモリ１００２は、例えば、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）、フラッシュメモリ等の半導体メモリであり、ストレージ管理処理に用いられるプログラム及びデータを格納する。メモリ１００２に記憶されるプログラムには、前述の図６に示すストレージ管理処理を実行するプログラムが含まれる。例えば、ＣＰＵ１００１は、メモリ１００２を利用してプログラムを実行することにより、上述のストレージ管理処理を行う。メモリ１００２は、図１の格納部１３としても使用できる。
【００４５】
入力装置１００３は、例えば、キーボード、ポインティングデバイス等であり、オペレータからの指示や情報の入力に用いられる。出力装置１００４は、例えば、表示装置、プリンタ、スピーカ等であり、操作者への問い合わせや処理結果の出力に用いられる。出力装置１００４は、図１の出力部１６としても使用できる。
【００４６】
外部記録装置１００５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。この外部記録装置１００５には、ハードディスクドライブも含まれる。情報処理装置１０００は、この外部記録装置１００５にプログラム及びデータを格納しておき、それらをメモリ１００２にロードして使用することができる。
【００４７】
媒体駆動装置１００６は、可搬型記録媒体１００９を駆動し、その記録内容にアクセスする。可搬型記録媒体１００９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。この可搬型記録媒体１００９には、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）、ＤＶＤ（Digital Versatile Disk）、ＵＳＢ（Universal Serial Bus）メモリ等も含まれる。操作者は、この可搬型記録媒体１００９にプログラム及びデータを格納しておき、それらをメモリ１００２にロードして使用することができる。
【００４８】
このように、ストレージ管理処理に用いられるプログラム及びデータを格納するコンピュータ読み取り可能な記録媒体には、メモリ１００２、外部記録装置１００５、及び可搬型記録媒体１００９のような、物理的な（非一時的な）記録媒体が含まれる。
【００４９】
ネットワーク接続装置１００７は、ＬＡＮ（Local Area Network）等の有線または無線の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェースである。情報処理装置１０００は、プログラム及びデータを外部の装置からネットワーク接続装置１００７を介して受け取り、それらをメモリ１００２にロードして使用することができる。ネットワーク接続装置１００７は、図１の出力部１３としても使用できる。
【００５０】
図１１は、情報処理装置にプログラムやデータを提供する方法を示す図である。
例えば、外部記録装置１００５に格納したプログラムやデータは、情報処理装置１００のメモリ１００２にロードされる。また、ネットワーク接続装置１００７を介して接続可能な外部装置は、プログラムやデータ１１２０を搬送する搬送信号を生成し、通信ネットワーク上の任意の伝送媒体を介して情報処理装置１０００に送信する。
【００５１】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【符号の説明】
【００５２】
１      ストレージ管理装置
２      ストレージ
１１      サンプル取得機能
１２      サンプル値記憶機能
１３      格納部
１４      ユニークデータ判定機能
１５      推定機能
１６      出力部
２２      サンプリング領域
２３      最終領域
１０００      情報処理装置
１００１      ＣＰＵ
１００２      メモリ
１００３      入力装置
１００４      出力装置
１００５      外部記録装置
１００６      媒体駆動装置
１００７      ネットワーク接続装置
１００８      バス
１００９      可搬型記録媒体
１１２０      プログラムやデータ
【図１】
0005923999.tif 000002
【図２】
0005923999.tif 000003
【図６】
0005923999.tif 000004
【図１０】
0005923999.tif 000005
【図１１】
0005923999.tif 000006
【図３】
0005923999.tif 000007
【図４】
0005923999.tif 000008
【図５】
0005923999.tif 000009
【図７】
0005923999.tif 000010
【図８】
0005923999.tif 000011
【図９】
0005923999.tif 000012