JP7647078B2 - 情報処理装置、重複除去方法及び重複除去プログラム - Google Patents

Description

本発明は、情報処理装置、重複除去方法及び重複除去プログラムに関する。

ＩＣＴ（Information and Communication Technology）インフラストラクチャのアーキテクチャとしてコンポーザブルアーキテクチャが検討されている。コンポーザブルアーキテクチャでは、コンピュートノード（Compute Node）とストレージノード（Storage Node）を仮想化して統合管理をすることが可能であるとともに、コンピュートノードとストレージノードを独立にスケールアウトすることが可能である。コンポーザブルアーキテクチャでは、ストレージノード側はＪＢＯＤ（Just a Bunch Of Disks）／ＪＢＯＦ（Just a Bunch Of Flash）であり、重複除去などのストレージ機能はコンピュートノード側で実現される。したがって、コンポーザブルアーキテクチャは、安価でかつスケールアウト可能なストレージノードを実現する。

図１３は、コンポーザブルアーキテクチャを説明するための図である。図１３に示すように、コンピュートノード９１とストレージノード９２は統合管理される。コンポーザブルアーキテクチャでは、コンピュートノード９１のＲＡＭ（Random Access Memory）９１ａは、コンピュート、重複除去、その他ストレージ機能などに使用される。重複除去に使用されるＲＡＭ９１ａの量が多いと、コンピュートノード９１で使用されるＲＡＭ９１ａの量が少なくなる。このため、コンポーザブルアーキテクチャでは、ＲＡＭ使用効率の高い重複除去方式が必要になる。

図１４は、重複除去を説明するための図である。図１４に示すように、書き込みデータは所定の大きさのチャンクに分割され、チャンクごとにフィンガープリントと呼ばれるハッシュ値が計算される。そして、チャンクの格納場所とフィンガープリントを対応付けるインデックスが参照され、同一のフィンガープリントがある場合には、チャンクは重複しているので、ディスク９２ａへの書き込みは行われない。一方、同一のフィンガープリントがない場合には、チャンクは重複していないので、ディスクへの書き込みが行われる。なお、ディスク９２ａは、ストレージノード９２に含まれる。また、新規のチャンクがディスク９２ａへ書き込まれると、チャンクの格納場所とチャンクのフィンガープリントがインデックスに登録される。

図１４では、書き込みデータがＡ、Ｂ、Ｃ’、Ｄのチャンクから構成され、Ａ、Ｂ、Ｃ、Ｄのフィンガープリントがインデックスに登録されているので、新規のチャンクＣ’がディスク９２ａに書き込まれる。

インデックスはＲＡＭ９１ａに記憶されるため、ＲＡＭ使用効率の高い重複除去を実現しようとすると、インデックスを小さくすることが考えられる。例えば、チャンクサイズが４ＫＢ（キロバイト）で１０ＴＢ（テラバイト）分のユニークデータがあるとし、１チャンク当たり４０Ｂ（バイト）のメタデータがインデックス用に必要である。すると、インデックスの容量は、４０×（１０×１０¹²÷（４×１０³））＝１０¹¹Ｂ＝１００ＧＢである。

そこで、チャンクを複数まとめたセグメントごとに重複除去を行うことで、インデックスを小さくすることが考えられる。例えば、セグメントサイズを６４ＫＢとすると、インデックスの容量を１／１６の６．２５ＧＢまで減らすことができる。インデックスとして使用されるＲＡＭ９１ａの容量を減らすことで、例えばキャッシュとして使用されるＲＡＭ９１ａの容量を増やすことができ、ストレージノード９２へのアクセス性能を向上することができる。

なお、バックアップに関する従来技術として、ファイル単位での差分バックアップの処理負荷を軽減することが可能なストレージ制御装置がある。このストレージ制御装置は、コピーオンライト方式で作成された第１スナップショットに含まれるすべてのファイルを、バックアップ領域にコピーする。その後、このストレージ制御装置は、第２スナップショットを作成する。そして、このストレージ制御装置は、第２スナップショットに含まれるすべてのファイルに関するメタデータが記録された、第２スナップショットにおけるメタデータ領域のうち、第１スナップショットの作成後に更新された領域Ｍ１，Ｍ２を特定する。このストレージ制御装置は、第１スナップショットの作成後に更新されたデータブロックの位置を管理するための管理情報に基づいて領域Ｍ１，Ｍ２を特定する。そして、このストレージ制御装置は、領域Ｍ１，Ｍ２に含まれるメタデータに基づいて、第１スナップショットの作成後に更新されたファイルＦ１，Ｆ２を特定して、バックアップ領域にコピーする。

また、重複除去に関する従来技術として、先にハッシュコード同士を比較することにより、データ同士を比較する対象を絞り込み、重複データを高速に検出する記憶制御装置がある。この記憶制御装置は、ホストから受信されるデータにハッシュコードを設定する。論理ボリュームにはハッシュコード付きのデータが記憶される。そして、この記憶制御装置は、比較対象の各データについて、それぞれのハッシュコード同士を比較する。ハッシュコードが一致する場合、この記憶制御装置は、対象のデータ同士を比較し、重複データであるか否かを判定する。重複データが検出された場合、この記憶制御装置は、重複データを排除する。

米国特許出願公開第２０１９／０２５０８１８号明細書 特開２０１８－０２８７１５号公報 特開２００９－２５１７２５号公報

セグメントごとに重複除去を行うと重複除去率が低下するという問題がある。図１５は、セグメントごとに重複除去を行った場合の重複除去率の低下を説明するための図である。図１５に示すように、アプリケーション３がチャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントＡのディスク９２ａへの書き込みを指示すると、セグメントＡのフィンガープリントＡが計算され、重複インデックスが参照される。フィンガープリントＡは重複インデックスにないので、セグメントＡがディスク９２ａに書き込まれるとともに、フィンガープリントＡと格納先が重複インデックスに登録される。

その後、セグメントＡのチャンクｃがチャンクｃ’に更新され、アプリケーション３がチャンクａ、チャンクｂ、チャンクｃ’、チャンクｄから構成されるセグメントＢのディスク９２ａへの書き込みを指示する。すると、セグメントＢのフィンガープリントＢが計算され、重複インデックスが参照される。フィンガープリントＢは重複インデックスにないので、セグメントＢがディスク９２ａに書き込まれるとともに、フィンガープリントＢと格納先が重複インデックスに登録される。

このように、セグメントＢはセグメントＡと一部だけが異なるが、セグメントＢの全体がディスク９２ａに書き込まれるため、チャンクａ、チャンクｂ、チャンクｄは重複してディスク９２ａに書き込まれる。

本発明は、１つの側面では、セグメントのように所定数のチャンクをまとめた単位ごとに重複除去を行う場合に、重複除去率を向上させ、ストレージリソースを有効活用することを目的とする。

１つの態様では、情報処理装置は、類似判定部と書き込み部とを有する。前記類似判定部は、記憶装置への第１の大きさの書き込みデータに類似する類似データが前記記憶装置にあるか否かを判定する。前記書き込み部は、前記類似判定部により類似データがあると判定された場合に、前記書き込みデータと前記類似データに基づいて格納データを生成し、生成した格納データを前記記憶装置に書き込む。

１つの側面では、本発明は、重複除去率を向上させ、ストレージリソースを有効活用することができる。

図１は、実施例に係るコンピュートノードによる類似検出を説明するための図である。 図２は、実施例に係るコンピュートノードの構成を示す図である。 図３は、重複インデックスの一例を示す図である。 図４は、類似インデックスの一例を示す図である。 図５は、重複除去用のハッシュ関数と類似判定用のハッシュ関数を説明するための図である。 図６は、論物アドレスマッピング情報の一例を示す図である。 図７は、差分の計算方法を説明するための図である。 図８は、書き込み処理のフローを示すフローチャートである。 図９は、マッピング情報更新処理のフローを示すフローチャートである。 図１０は、従来の重複管理と実施例に係る重複管理を比較した図である。 図１１は、新セグメントと類似セグメントの排他的論理和を取って圧縮してからディスクに書き込む方法を説明するための図である。 図１２は、新セグメントと類似セグメントの排他的論理和を取る場合の論物アドレスマッピング情報の一例を示す図である。 図１３は、コンポーザブルアーキテクチャを説明するための図である。 図１４は、重複除去を説明するための図である。 図１５は、セグメントごとに重複除去を行った場合の重複除去率の低下を説明するための図である。

以下に、本願の開示する情報処理装置、重複除去方法及び重複除去プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。

まず、実施例に係るコンピュートノード（情報処理装置）による類似検出について説明する。図１は、実施例に係るコンピュートノードによる類似検出を説明するための図である。なお、図１では、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントＡがディスク２ａに既に書き込まれているとする。図１に示すように、アプリケーション３がチャンクａ、チャンクｂ、チャンクｃ’、チャンクｄから構成されるセグメントＢのディスク２ａへの書き込みを指示する（ｔ１）。

すると、実施例に係るコンピュートノードは、重複除去用のフィンガープリントＢを計算し、重複インデックスを参照する。そして、フィンガープリントＢは重複インデックスにないので、実施例に係るコンピュートノードは、類似検出用のフィンガープリントを計算し、類似インデックスを参照する。ここで、類似検出用のフィンガープリントとは、類似したセグメントに関して値が同じになるフィンガープリントである。セグメントＢは、セグメントＡと類似するので、セグメントＢの類似検出用のフィンガープリントとしてフィンガープリントＡが計算される。

そして、実施例に係るコンピュートノードは、セグメントＢはセグメントＡと類似検出用のフィンガープリントが同じであるので、セグメントＢに似たセグメントＡがあることを特定する（ｔ２）。そして、実施例に係るコンピュートノードは、ディスク２ａから似たセグメントＡを読み出し、似たセグメントＡとの差分を計算し、差分をディスク２ａへ書き込む（ｔ３）。図１では、差分はチャンクｃ’であるので、チャンクｃ’がディスク２ａへ書き込まれる。

このように、実施例に係るコンピュートノードは、類似インデックスを用いて類似する既存の類似セグメントを特定し、特定した類似セグメントとの差分をディスク２ａへ書き込むので、重複除去率の低下を防ぐことができる。

次に、実施例に係るコンピュートノードの構成について説明する。図２は、実施例に係るコンピュートノードの構成を示す図である。図２に示すように、実施例に係るコンピュートノード１は、ＲＡＭ１ａと、ＣＰＵ（Central Processing Unit）１ｂと、Ｉ／Ｆ１ｃと、ＯＤＤ（Optical Disk Drive）１ｄと、ＬＡＮ（Local Area Network）インタフェース１ｅとを有する。

ＲＡＭ１ａは、プログラムやプログラムの実行に必要なデータなどを記憶するメモリである。ＲＡＭ１ａは、重複インデックス１１と、類似インデックス１２と、論物アドレスマッピング情報１３と、キャッシュデータ１４とを記憶する。

重複インデックス１１は、セグメントごとの重複除去に用いられるインデックスである。図３は、重複インデックス１１の一例を示す図である。図３に示すように、重複インデックス１１は、セグメントとフィンガープリントと構成チャンク物理アドレスとを対応付ける。セグメントは、重複除去が行われる単位データである。フィンガープリントは、セグメントのハッシュ値である。構成チャンク物理アドレスは、セグメントを構成するチャンクが格納されるディスク２ａの物理アドレスである。

例えば、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントのフィンガープリントは「０ｘｄｅａｄｂｅｅｆ」である。ここで、「０ｘ」は１６進数を表す。また、チャンクａ、チャンクｂ、チャンクｃ及びチャンクｄの物理アドレスは、それぞれ「２００」、「２０１」、「２０２」及び「２０３」である。

チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントがある状態でチャンクａ、チャンクｂ、チャンクｃ’、チャンクｄから構成されるセグメントが書き込まれると、チャンクｃ’だけが書き込まれる。チャンクａ、チャンクｂ及びチャンクｄについては、すでに存在する物理アドレスが参照される。

類似インデックス１２は、類似するセグメントの特定に用いられるインデックスである。図４は、類似インデックス１２の一例を示す図である。図４に示すように、類似インデックス１２は、セグメントとフィンガープリントと構成チャンク物理アドレスとを対応付ける。セグメントは、類似判定が行われる単位データである。フィンガープリントは、セグメントのハッシュ値である。構成チャンク物理アドレスは、セグメントを構成するチャンクが格納されるディスク２ａの物理アドレスである。

例えば、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントのフィンガープリントは「０ｘｂａａｄｆ００ｄ」である。また、チャンクａ、チャンクｂ、チャンクｃ及びチャンクｄの物理アドレスは、それぞれ「２００」、「２０１」、「２０２」及び「２０３」である。

図５は、重複除去用のハッシュ関数と類似判定用のハッシュ関数を説明するための図である。図５（ａ）は、重複除去用のハッシュ関数が取る値を示し、図５（ｂ）は、類似判定用のハッシュ関数が取る値を示す。図５において、Ａ、Ｂは類似データである。図５（ａ）に示すように、重複除去用には、生成される値に偏りがなく、似たデータの入力に対して近い値が生成されず、衝突（異なる入力に対して同じ値を出力）が起きづらいハッシュ関数が使用される。例えば、ＳＨＡ－１関数などが重複除去用のハッシュ関数として用いられる。図５（ａ）では、ＡとＢのハッシュ値はまったく異なる。

一方、図５（ｂ）に示すように、類似判定用には、類似する入力に対しては同じ値となり、そうでない場合は異なる値を取るハッシュ関数が使用される。類似の定義例としては、ハミング距離などがある。例えば、ＬＳＨ（Locality Sensitive Hashing）の一種であるｍｉｎＨａｓｈなどが類似判定用のハッシュ関数として用いられる。図５（ｂ）では、ＡとＢのハッシュ値は同じになる。

図２に戻って、論物アドレスマッピング情報１３は、チャンクについて論理アドレスと物理アドレスを対応付ける情報である。図６は、論物アドレスマッピング情報１３の一例を示す図である。図６に示すように、論物アドレスマッピング情報１３は、チャンクと論理アドレスと物理アドレスとを対応付ける。チャンクは、論理アドレスと物理アドレスが対応付けられるデータである。論理アドレスは、アプリケーション３においてチャンクが格納されるアドレスである。物理アドレスは、ディスク２ａにおいてチャンクが格納されるアドレスである。例えば、チャンクａの論理アドレスは「１００」であり、物理アドレスは「２００」である。

キャッシュデータ１４は、ディスク２ａが記憶する一部のデータである。キャッシュデータ１４は、ディスク２ａが記憶するデータへのアクセスを高速化するために用いられる。

ＣＰＵ１ｂは、ＲＡＭ１ａに記憶された重複除去プログラムを実行することにより、重複判定部２１と、類似判定部２２と、差分処理部２３と、更新部２４とを実現する。重複除去プログラムは、コンピュートノード１により読み出し可能な記録媒体の一例であるＤＶＤに記憶され、ＯＤＤ１ｄによってＤＶＤから読み出されてディスク２ａにインストールされる。あるいは、重複除去プログラムは、ＬＡＮインタフェース１ｅを介して接続されたコンピュータシステムのデータベース等に記憶され、これらのデータベースから読み出されてディスク２ａにインストールされる。そして、インストールされた重複除去プログラムは、ディスク２ａからＲＡＭ１ａに読み出されてＣＰＵ１ｂによって実行される。

重複判定部２１は、新セグメントのフィンガープリントを重複除去用のハッシュ関数を用いて計算し、新セグメントがディスク２ａが記憶するいずれかのセグメントと重複するか否かを重複インデックス１１を用いて判定する。ここで、新セグメントは、新たにディスク２ａに書き込まれるセグメントである。

類似判定部２２は、新セグメントのフィンガープリントを類似判定用のハッシュ関数を用いて計算し、新セグメントがディスク２ａが記憶するいずれかのセグメントと類似するか否かを類似インデックス１２を用いて判定する。

差分処理部２３は、新セグメントと類似セグメントの間の差分を計算し、計算した差分をディスク２ａに書き込む。差分処理部２３は、セグメントをチャンクに分解し、チャンク単位で一致するか否かを判定する。そして、差分処理部２３は、新セグメントを構成するチャンクのうち、既存のチャンクと一致しないチャンクを差分として特定する。差分処理部２３は、チャンクが一致するか否かをハッシュ値を用いて判定する。差分処理部２３は、例えば、ハッシュ関数として、ＳＨＡ－１、ｍｄ５などを用いる。なお、差分処理部２３は、チャンクが一致するか否かをハッシュ値を用いないで判定してもよい。また、差分処理部２３は、特許請求の範囲の書込み部に対応する。

図７は、差分の計算方法を説明するための図である。図７に示すように、新セグメントがチャンクａ、チャンクｂ、チャンクｃ’、チャンクｄから構成され、書き込み済みセグメントがチャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成される場合、差分処理部２３は、チャンクｃ’を差分として特定する。

更新部２４は、新セグメントが重複セグメントである場合には、新セグメントを構成するチャンクの論理アドレスと、書き込み済みの対応するチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する。

また、更新部２４は、新セグメントが類似セグメントである場合には、以下のように論物アドレスマッピング情報１３を更新する。すなわち、更新部２４は、新セグメントを構成するチャンクの論理アドレスと、書き込み済みの対応するチャンク又は新たにディスク２ａに書き込まれたチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する。

また、更新部２４は、新セグメントが重複セグメントでもなく類似セグメントでもない新規セグメントとして書き込まれた場合には、書き込まれたチャンクの論理アドレスと、書き込まれたチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する。

また、更新部２４は、新セグメントが重複セグメント以外のセグメントである場合には、重複インデックス１１及び類似インデックス１２を更新する。

Ｉ／Ｆ１ｃは、コンピュートノード１をディスク２ａに接続するインタフェースである。ディスク２ａは、論物アドレスマッピング情報３１とデータ３２を記憶する。論物アドレスマッピング情報３１は、ＲＡＭ１ａに読み出されて論物アドレスマッピング情報１３として記憶される。更新された論物アドレスマッピング情報１３は、論物アドレスマッピング情報３１としてディスク２ａに格納される。

次に、書き込み処理のフローについて説明する。図８は、書き込み処理のフローを示すフローチャートである。図８に示すように、コンピュートノード１は、入力チャンクをライトバッファに貯め（ステップＳ１）、入力チャンクが一定サイズ（セグメントサイズ）貯まったらセグメント化する（ステップＳ２）。

そして、コンピュートノード１は、セグメント単位で重複除去用ハッシュ値及び類似判定用ハッシュ値を計算し（ステップＳ３）、重複除去用ハッシュ値を用いて重複インデックス１１を検索して、重複セグメントがあるか否かを判定する（ステップＳ４）。そして、重複セグメントがある場合には、コンピュートノード１は、ステップＳ８へ進む。

一方、重複セグメントがない場合には、コンピュートノード１は、類似セグメントがあるか否かを判定し（ステップＳ５）、類似セグメントがない場合には、新規セグメントとして書き込む（ステップＳ６）。一方、類似セグメントがある場合には、コンピュートノード１は、類似セグメントとの差分を取って差分のみ書き込む（ステップＳ７）。

そして、コンピュートノード１は、論物アドレスマッピング情報１３などを更新するマッピング情報更新処理を行う（ステップＳ８）。

このように、コンピュートノード１は、類似セグメントがある場合に類似セグメントとの差分を取って差分のみをディスク２ａに書き込むので、重複除去率の低下を防ぐことができる。

図９は、マッピング情報更新処理のフローを示すフローチャートである。図９に示すように、コンピュートノード１は、新セグメントが重複セグメントであるか否かを判定する（ステップＳ１１）。そして、重複セグメントである場合には、コンピュートノード１は、重複セグメントを構成するチャンクの論理アドレスと既存の対応するチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する（ステップＳ１６）。

一方、重複セグメントでない場合には、コンピュートノード１は、重複インデックス１１及び類似インデックス１２を更新し（ステップＳ１２）、類似セグメントとして差分のみ書き込みを行ったか否かを判定する（ステップＳ１３）。そして、差分のみの書き込みを行っていない場合には、コンピュートノード１は、書き込まれたチャンクの論理アドレスと、書き込まれたチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する（ステップＳ１４）。

一方、差分のみ書き込みを行った場合には、コンピュートノード１は、書き込まれたチャンクの論理アドレスと、既存の対応するチャンク又は新たに書き込まれたチャンクの物理アドレスを論物アドレスマッピング情報１３に追記する（ステップＳ１５）。

このように、コンピュートノード１は、セグメント単位での重複インデックス１１及び類似インデックス１２と、チャンク単位での論物アドレスマッピング情報１３を用いることで、ディスク２ａへの書き込みを適切に管理することができる。

図１０は、従来の重複管理と実施例に係る重複管理を比較した図である。図１０（ａ）は従来の重複管理を示し、図１０（ｂ）は実施例に係る重複管理を示す。図１０に示すように、アプリケーション３がセグメント内の一部のチャンクを更新した場合、従来は更新前のセグメントと更新後のセグメントの両方がディスク２ａに格納されるが、実施例では、更新前のセグメントと差分のみ格納される。

図１０において、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄのうちチャンクｃがチャンクｃ’に更新される。すると、従来は、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントと、チャンクａ、チャンクｂ、チャンクｃ’、チャンクｄから構成されるセグメントがディスク２ａに格納される。一方、実施例では、チャンクａ、チャンクｂ、チャンクｃ、チャンクｄから構成されるセグメントとチャンクｃ’がディスク２ａに格納される。

したがって、従来の重複管理と比較して、実施例に係る重複管理は、重複除去率を向上することができる。実施例に係る重複管理は、部分更新が多いワークロードに対して、より効果的である。

上述してきたように、実施例では、類似判定部２２が、新たにディスク２ａに書き込まれるセグメントのフィンガープリントを類似判定用のハッシュ関数を用いて計算する。そして、類似判定部２２は、新たにディスク２ａに書き込まれるセグメントがディスク２ａが記憶するいずれかのセグメントと類似するか否かを、計算したフィンガープリントと類似インデックス１２を用いて判定する。そして、新たにディスク２ａに書き込まれるセグメントに類似するセグメントがあると類似判定部２２により判定された場合に、差分処理部２３が、類似するセグメントとの差分を計算し、計算した差分をディスク２ａに書き込む。このため、コンピュートノード１は、セグメント単位で重複管理を行うことで重複インデックス１１のサイズを小さくするとともに、重複除去率の低下を防ぐことができる。したがって、コンピュートノード１は、ストレージリソースを有効活用することができる。

また、実施例では、セグメントは複数のチャンクから構成され、差分処理部２３は、チャンクごとに重複データがあるか否かを判定し、チャンクごとの重複データの有無に基づいて差分を計算するので、差分を適切に計算することができる。

また、実施例では、類似インデックス１２が、セグメントとフィンガープリントと構成チャンク物理アドレスとを対応付け、論物アドレスマッピング情報１３が、チャンクについて論理アドレスと物理アドレスを対応付ける。そして、更新部２４が、新セグメントと類似する類似セグメントがある場合に、類似インデックス１２と論物アドレスマッピング情報１３を更新する。したがって、コンピュートノード１は、類似セグメントを適切に管理することができる。

なお、差分処理部２３は、チャンク単位の比較により差分を取る代わりに、新セグメントと類似セグメントの排他的論理和を取って圧縮してからディスク２ａに書き込んでもよい。図１１は、新セグメントと類似セグメントの排他的論理和を取って圧縮してからディスク２ａに書き込む方法を説明するための図である。図１１（ａ）は書き込み時を示し、図１１（ｂ）は読み出し時を示す。

図１１（ａ）に示すように、書き込み時は、差分処理部２３は、新セグメントと類似セグメントの排他的論理和を取り、圧縮してディスク２ａに書き込む。図１１（ａ）では、「ｘｘｙｙｚｚ」が圧縮済みデータである。そして、読み出し時は、コンピュートノード１は、圧縮済みデータを展開し、類似セグメントと排他的論理和を取って読み出しデータとする。

新セグメントと類似セグメントの排他的論理和を取る場合、コンピュートノード１は、チャンク単位でデータを管理する代わりに、セグメント単位でデータを管理する。図１２は、新セグメントと類似セグメントの排他的論理和を取る場合の論物アドレスマッピング情報１３の一例を示す図である。

図１２に示すように、論物アドレスマッピング情報１３は、セグメントと論理アドレスと物理アドレスとサイズと類似セグメントＰとを対応付ける。セグメントは、論理アドレスと物理アドレスが対応付けられるデータである。論理アドレスは、アプリケーション３においてセグメントが格納されるアドレスである。

物理アドレスは、類似セグメントがない場合には、ディスク２ａにおいてセグメントが格納されるアドレスである。類似セグメントがある場合には、物理アドレスは、ディスク２ａにおいて排他的論理和の圧縮済みデータが格納されるアドレスである。サイズは、ディスク２ａに格納されたセグメント又は圧縮済みデータの大きさである。類似セグメントＰは、類似セグメントへのポインタである。類似セグメントがない場合には、類似セグメントＰは「ｎｕｌｌ」である。

例えば、セグメントａｂｃｄについては、論理アドレスは「１００－１０３」であり、物理アドレスは「２００」であり、サイズは「８ｋＢ」であり、類似セグメントはない。また、セグメントａｂｃ’ｄについては、論理アドレスは「１０４－１０７」であり、物理アドレスは「２０２」であり、圧縮済みデータのサイズは「４ｋＢ」であり、類似セグメントはａｂｃｄである。

このように、コンピュートノード１は、チャンク単位の比較により差分を取る代わりに、新セグメントと類似セグメントの排他的論理和を取って圧縮することによっても、類似セグメントとの相違を管理することができる。

１，９１ コンピュートノード
１ａ，９１ａ ＲＡＭ
１ｂ ＣＰＵ
１ｃ Ｉ／Ｆ
１ｄ ＯＤＤ
１ｅ ＬＡＮインタフェース
２ａ，９２ａ ディスク
３ アプリケーション
１１ 重複インデックス
１２ 類似インデックス
１３ 論物アドレスマッピング情報
１４ キャッシュデータ
２１ 重複判定部
２２ 類似判定部
２３ 差分処理部
２４ 更新部
３１ 論物アドレスマッピング情報
３２ データ
９２ ストレージノード

Claims (5)

1. 互いに類似するデータに対して互いに異なる値をとる第一ハッシュ関数を用いて記憶装置への書き込みデータと同一の同一データが前記記憶装置にないと判定される場合に、前記書き込みデータに類似する類似データが前記記憶装置にあるか否かを、前記第一ハッシュ関数と異なる第二ハッシュ関数であって、互いに類似するデータに対して互いに同一の値をとる前記第二ハッシュ関数を用いてハミング距離に基づいて判定する類似判定部と、
   前記類似判定部により前記書き込みデータと前記第二ハッシュ関数の値が同一値となる前記類似データが前記記憶装置にあると判定された場合に、前記書き込みデータと前記類似データの差分、または、前記書き込みデータと前記類似データの排他的論理和を前記記憶装置に書き込む書き込み部と、
   を有する情報処理装置。
2. 前記書き込みデータは複数のチャンクに分割され、
   前記類似判定部は、前記チャンクごとに前記書き込みデータと重複する重複データがあるか否かを判定し、前記チャンクごとの重複データの有無に基づいて前記差分を計算する、
   請求項１に記載の情報処理装置。
3. 前記データと該データの類似判定に用いられるフィンガープリントと該データに含まれるチャンクの物理アドレスとを対応付けて類似インデックスとして記憶するとともに、前記チャンクと該チャンクの論理アドレスと物理アドレスとを対応付けて論物情報として記憶する記憶部と、
   前記類似判定部により前記類似データがあると判定された場合に、前記書き込みデータに基づいて前記類似インデックス及び前記論物情報を更新する更新部と、
   をさらに有する請求項２に記載の情報処理装置。
4. コンピュータが、
   互いに類似するデータに対して互いに異なる値をとる第一ハッシュ関数を用いて記憶装置への書き込みデータと同一の同一データが前記記憶装置にないと判定される場合に、前記書き込みデータに類似する類似データが前記記憶装置にあるか否かを、前記第一ハッシュ関数と異なる第二ハッシュ関数であって、互いに類似するデータに対して互いに同一の値をとる前記第二ハッシュ関数を用いてハミング距離に基づいて判定し、
   前記書き込みデータと前記第二ハッシュ関数の値が同一値となる前記類似データが前記記憶装置にあると判定した場合に、前記書き込みデータと前記類似データの差分、または、前記書き込みデータと前記類似データの排他的論理和を前記記憶装置に書き込む、
   処理を実行する重複除去方法。
5. コンピュータに、
   互いに類似するデータに対して互いに異なる値をとる第一ハッシュ関数を用いて記憶装置への書き込みデータと同一の同一データが前記記憶装置にないと判定される場合に、前記書き込みデータに類似する類似データが前記記憶装置にあるか否かを、前記第一ハッシュ関数と異なる第二ハッシュ関数であって、互いに類似するデータに対して互いに同一の値をとる前記第二ハッシュ関数を用いてハミング距離に基づいて判定し、
   前記書き込みデータと前記第二ハッシュ関数の値が同一値となる前記類似データが前記記憶装置にあると判定した場合に、前記書き込みデータと前記類似データの差分、または、前記書き込みデータと前記類似データの排他的論理和を前記記憶装置に書き込む、
   処理を実行させる重複除去プログラム。

Images