"記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を備え、前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ストレージシステム。請求項1に記載のストレージシステムであって、前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ストレージシステム。請求項2に記載のストレージシステムであって、前記データ解放制御部は、現在の時間帯に対して直前の時間帯以前に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントする、ストレージシステム。請求項3に記載のストレージシステムであって、前記データ解放制御部は、前記データ格納制御部にて直前の時間帯に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記記憶装置内への格納を完了した後に、前記被参照数をカウントする、ストレージシステム。請求項2に記載のストレージシステムであって、前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントしているときに、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを前記データ解放制御部による解放の対象から除外する設定を行う、ストレージシステム。請求項5に記載のストレージシステムであって、前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数のカウントが終了した後に、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータの前記被参照数が正の値、あるいは、当該記憶対象データあるいはアドレスデータが前記データ解放制御部による解放の対象から除外されている場合に、前記新たな書き込みに対応する前記記憶対象データあるいは前記アドレスデータの参照を行う、ストレージシステム。情報処理装置に、記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ことを実現させるためのプログラムを記憶した記憶媒体。請求項7に記載のプログラムを記憶した記憶媒体であって、前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、プログラムを記憶した記憶媒体。記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納し、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、前記記憶対象データあるいは前記アドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータに対して、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、情報処理方法。請求項9に記載の情報処理方法であって、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、情報処理方法。非特許文献1に開示のストレージシステムにおける削除処理手順は、誰も必要としなくなったブロックを削除して、その記憶領域を再利用するという、これまでのガーベジコレクションとある意味で類似する。しかしながら、削除処理は、重複排除、分散ストレージ構成、および、障害耐性に対する要求によって、著しく複雑である。例えば、削除実行中は重複排除を不能にするという単純な解決策は、記憶領域の消費を増やすことになるため、受け入れられない。削除実行中であっても常に重複排除を可能にするのが、より良いアプローチである。このため、本発明の目的は、上述した課題である、データの重複排除を実現しつつ、記憶領域の有効利用を図ることができるストレージシステムを提供することにある。本発明の一形態であるストレージシステムは、記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を備え、前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、という構成をとる。また、本発明の他の形態であるプログラムを記憶した記憶媒体は、情報処理装置に、記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ことを実現させるためのプログラムを記憶した記憶媒体である。また、本発明の他の形態である情報処理方法は、記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納し、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、前記記憶対象データあるいは前記アドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータに対して、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、という構成をとる。本発明は、以上のように構成されることにより、データの重複排除を実現しつつ、記憶領域の有効利用を図ることができるストレージシステムを提供することができる。<実施形態1>本実施形態では、次の事項を述べる。まず第1に、分散型重複排除ブロック格納における削除要件を特定する。第2に、この要件を満たし、商用システムに既に導入されているアルゴリズムを提示する。第3に、削除処理手順に関する評価結果について論じ、その効果と、削除がクリティカルなユーザのオペレーションに与える影響について述べる。また、本実施形態は、以下のように構成されている。まず、削除要件を概説する。続いて、ユーザから見た削除の意味と、関連するデータモデルを定義する。続いて、非特許文献1に開示のストレージシステムで削除を実施する上で直面する問題点を述べる。続いて、本発明における削除処理のアルゴリズムを詳細に述べる。続いて、実施される削除処理がこれまでの要求にどのように対応しているか、および、その性能について説明する。続いて、本発明に関連する技術について述べる。続いて、結論と今後の研究について述べる。[削除要件]あらゆるシステムにおいて、削除を行うためには、まずユーザにデータを選択的に削除してもらい、残すと決定したデータを保存してもらう必要がある。通常、データが削除対象としてマークされると、ストレージの有効利用の観点から効率化のために直ちに記憶領域の再利用が行われる。しかし、主記憶装置とは異なり、補助記憶装置では使用しない領域の回復を遅らせることができる。重複排除されたストレージは、はるかに記憶領域が効率化されており、またCASContentAddressableStorageシステムにとって記憶領域の再利用は非常に複雑であるため、直ちにデータを削除することはそれほど重要ではない。企業で利用されるバックアップシステムでは、バックアップ、復旧、復元等のユーザの操作が削除によって受ける影響を最小限に抑える必要がある。このような機能を常時利用できることが期待されており、削除の実行によりその性能が影響を受けることが全くないとは言えないとしても、ほとんどあってはならない。削除の実行を読出し専用期間に限定すると、バックアップ時間を再設定しなければならなくなるため、この方法を許容するのは難しいことが以前のストレージシステムでわかっている。また、継続的なバックアップポリシーの場合には、このような制限は事実上不可能である。削除処理を実行するとシステムリソースを消費するため、システム全体の性能に影響が出る。この影響を削減することが、削除処理を実施する上での1つの目標である。さらに、削除処理は、システム全体に対応させる必要がある。データ処理能力とディスク容量を比例的に変更することで、削除処理が全体的な性能に与える影響を同じレベルに保つことができると考えられる。また、システム内の装置とディスクの数が増えれば、ハードウェアが故障する可能性も増える。確実にシステムを利用できるようにするためには、ディスク、ノード、およびネットワークに複数の障害が発生しても、削除処理が継続できる必要がある。また、データ削除能力はシステムの運用にとって不可欠であるため、永久的なデータ障害が発生した場合でも削除処理の再スタートと終了が可能であるべきであり、このため、実際のところ、ユーザデータの回復性よりも削除の回復性の方が高くなっているべきである。さらに、大事な点として、削除を完了するために、重要なストレージの追加が必要になってはならない。[ユーザから見た意味][データモデル]非特許文献1に開示のストレージシステムのユーザから見た基本的なデータ単位は、ブロックである。ブロックは、バイナリデータに加えて、他のブロックへのポインタを含むことができる。ブロックアドレスは、ブロックのデータ内容から生成され、他にもブロックがある場合は他のブロックへのポインタも含む。コンテンツアドレス指定とは、ブロックが不変であることを意味する。そうでない場合はブロックのアドレスは変わる場合があるからである。なお、本発明のシステムでは、ブロックには、通常ブロックregularblocksと検索可能ブロックsearchableblocksという2つの異なる種類があることとする。検索可能ブロックは、通常ブロックの読出しに必要な暗号化コンテンツによって生成されるアドレスではなく、関連する検索キーで読み出すことができる。検索キーは、任意の文字列でもよく、検索可能ブロックの書込み時に、バイナリデータやポインタと共にユーザから提供される。検索可能ブロックは、このキーでしか読み出すことができないため、このシステムでは内容の異なる2つの検索可能ブロックに同じキーを設定することはできない。検索可能ブロックには通常アドレスはなく、他のブロックからポインタで参照することはできない。非特許文献1に開示のストレージシステムは重複排除機能を持つため、通常ブロックの書込みによって戻されたアドレスは、この重複する書込みのベースブロックと言われる既存のブロックを参照することができる。重複排除は、検索可能ブロックについても機能する。このような種類のブロックと関連する操作によって、システムはブロックのグラフを作成することができる。ブロックは不変であり、このグラフは非循環である。参照先ブロックが存在しない状況が発生することを防ぐため、システムは、まず参照先ブロックを書き込んで当該ブロックのコンテンツからブロックアドレスを生成する。その後、そのアドレスを参照するブロックを書き込む。そのため、ブロックのグラフは、ボトムアップに葉から根に向かってのみ構築される。[削除処理単位]本システムでは、個々のブロックを取り除く方法を提供するのではなく、ある検索可能ブロックから到達できる、不必要となった全てのブロックをマークする。詳しく説明すると、検索可能ブロックには、保存ルートretentionrootsと削除ルートdeletionrootsという2つのサブタイプがある。保存ルートと削除ルートは、もしそれらの検索可能キーが等しければ、保存ルートは削除ルートと一致するといえる。保存ルートは、そこから到達可能なブロックを、保存するブロックとしてマークし、削除ルートは、一致する保存ルートのこの性質を取り消すものである。なお、検索可能ブロックのサブタイプを区別するために追加のマーカーを使用するため、実際には、キーの一意性の要件は保存ルートにのみ適用される。保存ルートは、システム内に一致する削除ルートがなければ生きているといえ、生きている保存ルートから到達できる通常ブロックは生きている。ブロックが生きていない場合は死んでいるという。理論上は、削除を行うためにブロックのグラフ全体をマークするのでなく、単一のブロックを削除する操作を行うことが可能である。ただし、そうすると個々のブロックの削除を追跡し続けることが困難となり、また最も重要な点として、システム内の他の既存ブロックから参照されているブロックを削除することで、懸垂参照danglingreferenceが発生する恐れがある。また、悪意あるユーザは、適切な検索キーがわかれば他のユーザのブロックを削除できてしまうという問題があるが、この問題は検索可能ブロックのキーをユーザ固有のIDで暗号化することで簡単に解決される。[エポック世代を用いた削除とユーザとの同期]削除実行中にポインタ参照先付きのブロックを書き込むと、削除に関して上記のような問題が発生する。ユーザが、新たな通常ブロックAを書き込み、またブロックAを指す保存ルートRを書き込んで、このブロックを保存したいとする。システムが返したブロックAのアドレスは、保存ルートRのコンテンツに挿入される必要があるため、保存ルートRの書込み要求を出す前に、ブロックAの書込みを無事完了しなければならない。この2つの書込みを行う間に削除処理が実行されると、上述したようにブロックAは死んでいるので、当該ブロックAは削除される。この問題を解決するために、生きているブロック群を拡張し、ユーザが維持できるブロックとそこから到達可能なブロックを、全て生きているブロックに含める。ユーザは全てのブロックを維持することが可能になるため、ユーザが記憶できるブロックを制限する。そのために、いわゆるエポック世代に基づいて構築される仮想時刻を導入する。エポックとは、世代の前進操作を表現するグローバルカウンタである。このシステムでは、いかなる時点も、現在エポックと呼ぶ唯一のエポック時刻で表すこととする。ユーザによって取得される各ブロックアドレスは、当該アドレスと対応付けられたエポックを有する。システムは、書込みに関して、対応付けられたエポックTを持つアドレスは、エポックTおよびT1でのみ使用できることを確認する。読出しについては、ユーザは古いエポックが対応付けられたアドレスを使用することもできるが、そのブロックが削除されている場合、読出しは失敗となる。あるブロックのアドレスについては、このアドレスの取得方法によってエポックが変わってくる。エポックの割当てに関するルールを図1に示す。この詳細なレベルは完全を期すためにここで提示するが、後にも説明する。ポインタのない通常ブロックを書き込む場合、システムは、ブロックアドレスとそれに対応付けられた現在エポックを返却する。書き込まれるブロックがポインタを含む場合、この書込みと共に返却されるエポックは、このブロックに挿入される複数のブロックアドレスのエポックの中で最小値のものとなる図1で示されるミニマムルール。検索可能ブロックには通常アドレスがないため、エポックは割り当てられない。書込み時に返却されるエポックは、書き込まれるブロックの重複状況に依存しない。ブロックアドレスは、ポインタ参照付きのブロックを読み出すことによって取得することもできる。あるブロックを読み出すことによって得られる複数のポインタのエポックは同一である。ポインタ付きの通常ブロックのエポックは、読み出したブロックのアドレスに対応付けられたエポックと等しい。ポインタ付きの検索可能ブロックの場合、ポインタのエポックは現在エポックと等しい。ツリー構築のプロセスでは、ユーザは既に書き込まれたブロックのアドレスを保持し、それを親ブロックに挿入する必要がある。しかし、エポック導入後は、現在と前回のエポックがスタンプされたアドレスのみが、その後のブロック作成で使用される。エポックがTからT1へ進む前進操作の適用と、エポックTを持つ全てのブロックアドレスを破棄するために、全てのユーザにその事実が通知される。ここで、ポインタの破棄とは、生きている保存ルートによって参照されるツリーに、これらのポインタを入れることを意味する。これは、エポックがT2に進む前に完了する必要がある。エポックT2では、T1よりも小さいエポックが対応付けられたアドレスを持つポインタが一つでもあれば、システムはそのポインタを持つブロックの書込みを拒否する。また、システムは、生きていない保存ルートを読み出そうとした場合もこれを拒否し、ユーザが維持できるブロックアドレス群を制限する。これらの制約は、正しく行動しているユーザには関係ないが、システムが正しい削除処理を行うために不可欠である。上記のエポックによる制約を導入し実施することで、削除する際に、除去するアクセス不能の古いブロックを特定することができる一方、ユーザはシステムへの新規データの書込みとアクセス可能なブロックの読出しを継続することができる。[削除の課題][ルート群の決定]一般的なガーベジコレクションでは、オブジェクトへの到達可否は、通常、実行されるプログラムのグローバルかつアクティブなローカル変数で構成されるルート群に関して決定される。生きているオブジェクトは、ルート群に直接属しているか、または、グラフのトラバーサルによってルート群から到達できる。プログラム実行時に、ガーベジコレクションはプログラム変数について十分な知識があるため、ルート群の計算は十分に理解される。非特許文献1に開示のストレージシステム等のシステムでは、ルート群には、グローバル変数に該当する生きている保存ルートだけでなく、ユーザがまだ記憶しているアドレスのブロックプログラミング言語のローカル変数のようなものも含まれるため、もっと難しい。上記で述べたように、もしユーザのブロックアドレスを記憶する権利に何の制限もなければ、非特許文献1に開示のストレージシステムでは、ルート群はすべてのブロックで構成されることになる。本発明では、エポックの制約を導入することで、ルート群を限定し、削除を可能にしている。その結果、ルート群は、1生きている保存ルート、および2ユーザが維持するアドレスのうち、エポックの制約により現在または前回のエポックのみを持つ、書込みに適したアドレス、のみを含む。[重複排除の影響]削除処理によってストレージの消費が増加することを避けるために、削除処理中は重複排除を不能にするという解決策は取らない。その結果、削除されるはずのブロックを重複排除の副次的結果として復活させることができる。このようなブロックを保存することは、この削除アルゴリズムにおける根本的な課題である。[分散]分散型ストレージシステムでは、ノードの追加、除去、障害によってノード構成が変わることがよくある。その結果、システム内でのデータ分散も変わってくる。削除アルゴリズムは、場所の変化にかかわらず必要なデータやメタデータを探せなくてはならない。ここまでは、非特許文献1に開示のストレージシステムにおけるユーザから見たブロックについて述べてきたが、削除処理が機能する内部データ組織は、ユーザから見えるものとは実質的に異なる。非特許文献1に開示のストレージシステムの内部はスーパーノードで構成されている。各スーパーノードは、対応するハッシュスペースの先頭部分で特定される。スーパーノードのハッシュスペースは、互いに連結されておらず、ハッシュスペース全体をカバーしている。各スーパーノードは、当該スーパーノードのハッシュスペースに属する自身のコンテンツに基づいたハッシュ値を有する、ユーザが書込みまたは読出しを行うブロックによる。スーパーノード自身は、固定数のピアに分割される。書込みの際、ブロックには削除符号が付けられ、結果として生じる複数のフラグメントがピアに分配される。ピアは、受信したフラグメントを、各ピア毎に異なるフラグメントコンテナに加える。ピア自身は通常、物理的な装置を介して分散されることで、ノード障害に対する回復力を提供する。削除アルゴリズムは、1つのブロックから生じる全てのフラグメントを保存するかまたは除去するかについて一貫した決定を下す必要がある。[障害耐性]削除処理は、ほどほどの数のノードやディスクの障害があっても進められるものでなければならない。さらに、削除は、断続的なネットワーク障害により一時的に利用不能だが、また後で再現するノードにも対応する必要がある。特に、削除アルゴリズムは、既に死んだ装置に関連して発見された論理的に除去されたブロックのフラグメントを、まだ生きているものと区別できなければならない。[物理的リソースの利用]非特許文献1に開示のストレージシステムは永続的なストレージであるため、フラグメントがディスク上に維持されることは明白である。特に、ポインタで参照されたブロックのアドレスを親ブロックから検索するには、少なくとも1回のディスクアクセスが必要である。削除アルゴリズムは、ディスク、メモリ、およびネットワークのアクセスパターンを考慮して、これらのリソースを効果的に利用する必要がある。[削除アルゴリズム][概要]非特許文献1に開示のストレージシステムは、十分に知られている参照数カウント方法の技術を使用している。各ブロックは、カウンタ主を参照する他のブロックの数を追跡する参照カウンタを持つ。ただし、新たなブロックが書き込まれても、参照されたブロックのカウンタはすぐには変更されない。このような即時更新は、システム内のあらゆる場所に配置されているすべての子ブロックにランダムなI/Oが発生する可能性があるため、非常にコストがかかると思われる。その代わりに、参照カウンタは、バックグラウンド削除処理の実行により周期的に更新される。ブロックのカウンタは永続的なものであり、ブロックのフラグメントを格納する全てのピアに複製される。全てのフラグメントについて、削除中のカウンタには2つのバージョンがある。永続性のある有効なものと、削除アルゴリズムの部分的な結果を格納するために用いられる一時的なものである。ピアに障害が発生した場合、一時的なカウンタは破棄することができ、永続的なカウンタに何ら害は及ばない。削除処理には、周期的に実行される次の2つのフェーズがある。まず、ガーベジ識別garbageidentificationのフェーズで、新たなカウンタ値が計算される。この後に、領域解放spacereclamationのフェーズがあり、ここでは最初のフェーズで識別されたガーベジを取り除くことで、ストレージの記憶領域スペースを再利用できるようにする。上記で述べたように、補助記憶装置では直ちに記憶領域を再利用する必要がないため、このように2つのフェーズに分けることができる。さらに、ガーベジ識別と領域解放とを平行して進めると、重複書込みによって必要となる特別な処理があるため、前者の期間が長くなる。その場合、書込みを重複と認識するために、システムは、どのピアでもブロックの再利用が開始されていないことを確認しなければならず、それを行うためには重複書込みと物理的再利用とを同期させる必要がある。以下では、削除処理によるガーベジ識別フェーズについてのみ説明する。このフェーズを実行する毎に、ある時点までの書込みブロックのカウンタを計算する。図2に示すように、実行が開始されると、ブロックは連結していない3つのクラスに分類される。第1クラスには、成功した前回の削除が開始される前に書き込まれたブロックが含まれる。これを完了ブロックdoneblocksという。第2クラスには、それより後で、かつ今回の削除が開始される前に書き込まれたブロックが含まれ、これを処理対象ブロックtodoblocksという。また、今回の削除が開始された後に書き込まれたブロックを新規ブロックnewblocksといい、これは第3クラスに分類される。処理対象ブロックは、処理対象ブロックと完了ブロックとの両方に対する未処理の参照を反映して、今回の削除処理で処理される。そのため、カウンタがインクリメントおよびデクリメントする完了ブロックまたは処理対象ブロックがある。新規ブロックは、今回の削除処理の実行では処理されないため、現時点では他のブロックカウンタの値に影響を与えることはない。この影響は次回の削除実行時に計算される。特に、新規の削除ルートはすべて、今回の削除には何の影響も与えない。次の削除が終了するまで、すべての新規ブロックは単に保存され、そのカウンタは特別な初期値に設定される。次回の削除実行時には、そのときの処理対象ブロックとなる新規ブロックのみが処理される。つまり、カウンタの更新処理がインクリメントする。削除処理の実行は、いずれのスーパーノードにおいても、ピアのサブセットにより同期して実施されるよう、複数のサブフェーズで進められる。まず、すべてのスーパーノードで削除処理アルゴリズムの当初の参加者を選択する。この計算には、データの状態が良好なピアしか関与できない。例えば、ポインタを持つすべてのブロックがそのピアの現在位置にいなければ、ピアは削除アルゴリズムの各ステップを実施できない。選択されたピアを良好なピアと言い、各々が同一のタスクを実施してガーベジブロックを識別する。つまり、削除計算はかなりの冗長性を持つ。残りのピアは、削除アルゴリズムではアイドル状態にあり、削除が終了した後、バックグラウンドで他のピアから最終カウンタを受信する。次に、他のブロックをポインタで参照しているすべての処理対象ブロックを読み込む。このポインタは分散され、対象となるブロックのカウンタをインクリメントする。インクリメントする際、初期値を0として扱う。インクリメントしたら、デクリメントを開始するブロックを特定する必要がある。これには、一致する削除ルートがある保存ルート、およびカウンタがインクリメントしなかった通常の処理対象ブロックが含まれる今のところ、これらを指す新規ブロックはないものとする。これらのブロックのカウンタを0に変更する。このように識別されたガーベジから出ているポインタはすべて、これらのガーベジが指すブロックのカウンタをデクリメントさせる。ただし、デクリメントすることにより、カウンタが0になるブロックが出てくる可能性がある。そのため、再度新たなガーベジを識別することもあり、新たなガーベジがみつからなくなるまでデクリメントを繰り返す。新たなカウンタへの切替えは2段階のコミットで行う。これについては後ほど説明する。コミット後、ガーベジブロックは読出し不能となり、これらが占有していた記憶領域はバックグラウンドで再利用される。ピアに障害が発生すれば、良好なピアが減少する。いずれかのスーパーノードで良好なピアの数が構成可能な最小限の数を下回った場合、削除プロセス全体が中断され、部分的な結果は破棄される。上記の削除処理は、新たな書込みがなければスムーズに機能する。新たな書込みがある場合は非常に複雑な問題が生じる。これについては次に述べる。[複雑な問題]図3aは、削除処理開始の直前にブロックAが書き込まれ、当該ブロックAを指す保存ルートRが、その時点の直後に書き込まれた場合を示す。これについて検討する。ここで、ブロックAは新規のルートR以外にはどこからも指されていないため、識別プロセスでは対象とならなかった。その結果、ブロックAは誤って排除される。なお、図3aは、削除開始後にブロックAに対して保存ルートが書き込まれた場合を示すが、ブロックAは削除してはならない。この問題を解決するために、上述したエポックの制約を利用する。ユーザは前回のエポックより古いアドレスを保持できない。そのため、エポックを2段階で進めて、1回目と2回目に進んだエポックの間に書き込まれたブロックのインクリメントを送信すればよい。これを図4に示す。ただし、これらのブロックからデクリメントは送信しない。その理由は、新規ブロックを排除する可能性があるため、新規ブロックは無条件で保存するという前提に反するからである。したがって、図4に示すように、常にエポックを1前進させ次の世代にシフトする。2回目のエポックの前進により、削除開始前に取得したブロックAのアドレスはユーザによって破棄されるため、ブロックAに対する新たな参照は作成されない。ブロックAを参照することができる新規ブロックは、1回目と2回目のエポックの前進の間に書き込まれたブロックだけである。しかし、厳密に言うと、これらのブロックから追加のインクリメントが送信されている。次の問題は重複排除によるもので、これを図3bに示す。今回の削除開始時にどのブロックからも指されていない処理対象ブロックAについて検討する。ユーザが、重複するブロックAを書込み、その後、当該ブロックAを指すルートRを書き込んだ場合、どちらも保存しなければならない。しかし、ブロックAは他の処理対象ブロックからも古いブロックからも指されてないため、削除処理ではガーベジとして識別される。ブロックAを除去するのは間違いであり、データを失うことになる。この問題を解決するために、重複する書込みのベースブロックは、書込みの際にいわゆる非削除マーカーundeletemarkerを設定して、今回の削除プロセスでは除去不能とマークする。除去されそうになってつまり、新たに計算されたカウンタが0非削除マーカーが設定されたブロックは常に、削除完了時にカウンタを初期値に戻すことでそのブロックを保存する。削除進行中でなければ、重複する書込みにマーカーは設定されない。新たなカウンタ値がすべて計算されたら、新たな非削除マーカーが重複する書込みに設定されることはない。非削除マーカーの書き込みを続けると、マーカーの設定と、それを使ってカウンタを初期値に戻す作業が、延々と続いてしまうからである。そのかわりに、いわゆるベースブロックフィルタリングを用いて、削除される予定のベースブロックに対する書込みを重複として解決しないようにする。ベースブロックの、暫定的だがコミットの準備が整っているカウンタが正の場合、または、非削除マーカーが設定されている場合に限り、書込みを重複排除する。それ以外の場合は、ベースブロックとなる可能性のあるブロックがシステム内に存在する場合でも、全く新しいブロックとして書き込まれる。削除の実行が完了すると、カウンタ値が初期値に設定された非削除ブロックが存在することがある。次回削除を実行する際には、これらのブロックを本当に維持すべきかどうかを決定する必要がある。これは、必要に応じて追加の再帰的インクリメントによって行う。少なくとも1つの新たな削除処理対象ブロックから指されている非削除ブロックについては、指されたブロックに対して繰り返しインクリメントを送信する。なお、最後に完了した削除に関連して、非削除ブロックは他の非削除ブロックまたは新規ブロックからのみ参照されることができる。ある非削除ブロックが新規ブロックから指されている場合、その非削除ブロックは上記の再帰的インクリメント処理によって到達される。到達されない非削除ブロックは、今回の削除でガーベジとして識別される。[詳細[削除とエポックの変更]図4に示すように、1回の削除の実行で、1つのエポック全部および次のエポックの一部について削除を行う。最初のエポックを準備エポックといい、ここでは上述したとおり古いエポックのアドレスをユーザが破棄する。次のエポックを削除マーキングエポックといい、実際に削除計算を行う。削除の実行の最後が現在のエポックにぶつかる理由はない。エポック前進の操作はシステム内の他の主体によって調整されているため、すべてのユーザが古いアドレスの処分を確認した場合にのみ次の前進が実施される。[カウンタのインクリメント]エポックが2回前進して良好なピアが選択されると、処理対象ブロックに基づくバッチインクリメントが開始されるソースのインクリメントは図4参照。ポインタを持つ処理対象ブロック内のブロックのアドレスを良好なピアが読み出し、対のアドレスsourceaddressdestinationaddressが送信先アドレスに関与するスーパーノードの良好なピアに向けて送られる。送信先である良好なピアは、メッセージを受信しても対象のブロックのカウンタをインクリメントしない。その理由は2つある。まず、メッセージはネットワークを介して複製されうるため、複数回にわたってカウンタがインクリメントされる可能性がある。さらに、ランダムなブロックに何度もアクセスして一つずつインクリメントするのは効率が悪い。その代わりに、受信したポインタをすべてローカルストレージに一時的に保存し、その後、読み出して固有のものとし、バッチ処理で仮のカウンタに適用する。バッチでのインクリメントの後、システムはカウンタがインクリメントされたブロックで削除されていないものをみつけて、上述した再帰的インクリメントを行う。インクリメントが完了した時点で、保存ルートまたは削除ルートではなく通常の処理対象ブロックの中に、初期値設定のままになっているもの、つまり新たなポインタによって参照されていないブロックが含まれている場合がある。これらのブロックはすべて、以下に述べるデクリメントアルゴリズムに追加的に入力される。[カウンタのデクリメント]カウンタのデクリメントは最初に特定されたガーベジのルートから開始し、上述したように、新たなガーベジがみつからなくなるまで繰り返し行う。1回のデクリメントの分散と実際のデクリメントは、インクリメントとほぼ同様に機能する、カウンタ値を増加するのではなく減少する点が異なる。[新たなカウンタのコミット]最後のデクリメントが終了したら、計算したカウンタが等しいかどうかをスーパーノードごとに検証する。カウンタが一致しないスーパーノードがあれば、それはソフトウェアの障害を意味する。不一致がみつかった場合、削除プロセスは中断される。検証に成功したら、仮のカウンタを永久的なものにすることによって、システムで使用できる準備が整う。良好なピアは適切なコミットフェーズに入ることを決定し、コミットフェーズでシステムは新たなカウンタをスタートする。この時点から、障害後に再起動された各ノードがカウンタコミットを完了させる。切り替えはすべてのフラグメントのコンテナのメタデータを交換するだけなので、切り替え自体に時間はかからない。[非削除マーカーの組織と取扱い]上述のとおり、重複する書込みが削除処理中に発生すると、各良好なピアにおいて特別な非削除マーカーを書き込む必要が生じる。非削除マーカーは新規ブロックには設定されない。なぜなら新規ブロックは今回の削除の実行では決して削除されないからである。デクリメントの後、新たなカウンタ値が0で非削除マーカーが設定されたブロックについては、カウンタを初期値にリセットすることでガーベジとして扱われなくなる。ブロック書込みの一部としての重複排除は基本的なオペレーションであり、その性能はシステム全体の性能にとって重大である。そのため、非削除マーカーを設定することは非常に効率的である。これは、非削除マーカーを良好なピアのメモリにビットマップとして保存しておくことで達成される。すべてのスーパーノードに十分な良好なピアがある限り削除が進められるため、これは安全である。[ベースブロックフィルタリング処理]コミットが開始されると、非削除マーカーの書込みは行われない。そのかわりに、書込み中に特定されたベースブロックとなる可能性のあるすべてのブロックについては、今回の削除で削除されないことを確認する。これは、すべての良好なピアに対するクエリーで行うことができる。ピアの回答が肯定になるのは、このブロックに対して非削除マーカーが設定されている場合、または、最近計算されて仮のままになっているこのブロックのカウンタが正の値の場合のみである。回答が肯定だった場合は重複排除を行い、そうでない場合は新規ブロックが書き込まれる。すべての良好なピアから回答を受信したら、収集したすべての回答の論理的結合として最終回答を計算する。その理由は、ベースブロックとなる可能性があるブロックが今回の削除実行終了後に保存されているためには、すべての良好なピアの回答が肯定でなければならないからである。一部の回答には一貫性がない場合がある。なぜなら、以前に発行された非削除マーカーの書込みでは、いくつかの良好なピアにのみ設定された非削除マーカーを残すのに失敗することもあるからだ。[カウンタに対する非削除マーカーの適用]非削除マーカーに関して一貫性のなさが発見されたら、スーパーノード内のすべての良好なピアから集めたビットに論理的結合を適用して一貫性を持たせ、その結果をすべての良好なピアに戻す。その後、非削除マーカーが設定され計算されたカウンタ値が最終値の0と等しい各ブロックについて、このカウンタ値を初期値の0に変更する。[記憶領域再利用の概要]ガーベジ識別の結果、ブロックカウンタがゼロになるものがある。このようなブロックはもう読み出すことはできないが、ストレージのリソースを占有し続ける。このリソースを再利用するには、このブロックのフラグメントが格納されたすべてのコンテナをリライトする必要があり、これは大変重い動作である。不要な重い作業を避けるために、ストレージリソースは、それが必要になった場合または再利用を行うフリーサイクルがあるときに、再利用される。できるだけ早くなるべく多くのストレージリソースを再利用するためには、除去するフラグメントの割合が最も高いコンテナを優先する。[削除正確性分析]上述した削除処理が正確であること、つまり上記で定義したルート群から到達できるブロックを除去しないこと、について述べる。理想的には、ガーベジコレクションによってルート群から到達できないすべてのブロックを除去できることも示したい。しかし、ユーザはいかなる時点でもメモリからブロックのアドレスを削除できるため、それらのブロックは今回のルート群からは除外する。例えば、ユーザが全く新しい通常ブロックを書き込むことができる一方、ガーベジ識別が進められ、このブロックのアドレスは直ちに忘れられる。それでも、そのアドレスで参照されるブロックはルート群からは到達できないが除去されない。したがって、削除によって大きく分類されたブロックを除去することのみを証明する。以下に、主題を証明するのに有効な補題を述べる。[補題5.1]システムエポックT-1に書き込まれた保存ルートから到達できる、エポックT-2に関連付けられたアドレスを持つブロックは、エポックTにて終了する削除の実行では保存される。[証明]上述したように、T-1に書き込まれた保持ルートからインクリメントが送信され、その保持ルートから到達できるすべてのブロック、特にエポックT-2の特定のブロックに伝播する。ここで、主張を証明する上で役立つ用語を導入する。1回目の前進から削除実行が終了するまでのガーベジ識別中に実行された、読出し、書込み、および取得アドレスを忘れる等のユーザの動作を検討する。これらの動作の数は有限であり、ある順序にしたがって行われる。これらに連続する自然数を割り当てるとする。順序を定めたら、書込みが有効なアドレスに対して制限のあるユーザによって記憶される一連のアドレスのシークエンスは、数1式のように表わされる。つまり、エポックTでは、ユーザはエポックT-2またはそれ以前のアドレスを維持しないものとする。さらに、1回目の前進の生きている保存ルートから成る群のパラレルシークエンス数2式を定義する。Ri群は1回目の前進の後に新たに書き込まれた各ルートによって変化する。1回目の前進の後に書き込まれた削除ルートはここでは考慮しない。その理由は、今回の削除実行に何ら影響を与えないからである。数3式で、Uiを改変する動作は通常ブロックの書込み、あらゆるタイプのブロックの読出し、および維持していたアドレスを忘れることである。Riを改変する動作は保持ルートの書込みである。いずれの動作も、これらの群の1つだけを変化させる。なお、i番目のとき、Uiのあらゆるメンバーは読出可能である。削除手続きの正確さを証明するためには、Snから到達できるすべてのブロックが保存されていることを示せばよい。これについては更に強力な命題を提示する。[定理5.2]正確性プロパティ以下に示すSi群のメンバーはエポックTにおいて終了した削除実行によって保存される。1.Riに属するすべての保存ルート。2.T-1またはTに等しい、対応付けされたエポックのUiに含まれるすべてのアドレス。3.Rnからのいずれかの保存ルートにより参照されている場合、エポックT-2におけるUiに含まれるアドレス。4.1、2、3から到達できるすべてのブロック。[証明]。数学的帰納法によって証明を進める。基礎:S0はT-2の生きている保持ルートとアドレスしか含有できない。これらの保持ルートから到達できるブロックは削除処理によって除去されない。なぜなら適用される参照カウントの自然の特性だからである。T-2からのアドレスは、補題5.1による命題を満足させる。帰納ステップ:Siがこの命題を満足させるとすると、次のいずれか1つの動作の結果、SiからSi1が生成される。1忘れられたアドレスを除去することでSi1に命題を自明に満足させる。2Riに属する保存ルートから読み出したアドレスを追加する。読み出されたアドレスは帰納仮説によって命題を満足させる。3UiからのエポックT-2のポインタを持つブロックから読み出されたアドレスを追加する。読み出されるアドレスはエポックT-2からのものであり図1参照、[補題5.1]によってRnからの保持ルートから到達可能な場合は保存される。4UiからのエポックT-1またはTのポインタを持つ、ブロックから読み出されたアドレスを追加する。読み出されたアドレスはUiから到達可能でエポックT-1またはTにあるため、帰納仮説によって保存される。5ポインタのない通常ブロックを書き込むことによって取得したアドレスを追加する。取得したアドレスはエポックT-1またはTからのものとなる。このブロックが重複排除されていない場合、今回のガーベジ識別では削除されない。そうでない場合、非削除マーカーが設定されるか、またはベースブロックフィルタリングによって削除実行が終了した後にブロックが生きていることを確認する。どちらも、このベースブロックが今回の削除によって削除されないことを確実にする。6ポインタを持つブロックを書き込むことで取得したアドレスを追加する。ただし、挿入したアドレスの少なくとも1つはエポックT-2からのものである。図1で述べた、いわゆるミニマムルールにより、このような戻りアドレスはエポックT-2に対応付けられ、[補題5.1]により条件付きで保存される。7ポインタ付きのブロックを書き込むことで取得されるアドレスを追加する。挿入されるアドレスはすべてエポックT-1またはTのものである。ここでも、このブロックが重複排除されていない場合、今回の削除では除去されない。この書込みが重複として解決された場合、ベースブロックは5と同様に保存される。参照されるブロックはUiに含まれるため、帰納仮説によって保存される。8システムのエポックT-1の間に保持ルートを書き込んでRiを拡張する。この保持ルートから読み出せるブロックについては、インクリメントのプロセスでカバーされているため、保存される。9システムのエポックTの間に保持ルートを書き込んでRiを拡張する。この保持ルートには、帰納仮説によって保存されるUiからの、T-1およびTからの挿入アドレスのみが含まれる。ここで、削除によって除去されるブロックのクラスを定義する。[定理5.3]非空虚プロパティ削除の実行では、削除開始前に書き込まれ、かつ同時に以下の状態であるものをガーベジブロックと識別する。1.削除開始前に生きているいかなる保存ルートからも到達できず、2.1回目および2回目の前進の前に書き込まれたいかなる保持ルートからも到達できず、3.今回の実行中の重複排除でベースブロックとして使用されない。[証明]インクリメントとデクリメントとの境界の設定から、これらのブロックはカウンタ計算が0となる。削除処理中に行われる重複排除で、もしこれらのブロックがベースブロックとして使用されなかった場合、0カウンタは有効となり、これらのブロックは除去される。[削除要件の対処]削除アルゴリズムは、上述したあらゆる用件を満たす。このアルゴリズムは先に説明したように、十分に定義されたブロックの生存判断ロジックsemanticsを特徴として持つ。生きているブロックはすべて保存され、死んだブロックはほぼ削除される。削除アルゴリズムは保守的なものであるため、ガーベジブロックの可能性があるものでもシステムによって一時的に維持される場合もある。しかし、これらのブロックは次回の削除処理までの間、維持されるだけであり、次回の削除処理でガーベジとして識別される。クライアントは、削除処理実行中でも、途切れることなくシステムへの書込みができる。これは、上述したエポック制約のおかげである。非削除マーカーという軽量のメカニズムにより、削除実行中でも、良好な重複排除の効果と書込性能を実現できる。以下で述べる性能評価では、ユーザから見た全体的なシステム性能において、削除処理が極めて限定的な性能低下しかもたらさないことを示している。これは、以下のような設計での決定による。すなわち、1領域解放と参照カウンタの更新を遅延させる、2仮のカウンタに対するインクリメントとデクリメントの効果的な分散およびその適用をバッチで行う、3最も高い割合でスペースが得られるコンテナから、領域解放を開始する、および4良好なピアのメモリに非削除マーカーを保持する、という点である。削除計算が複数のスーパーノードに分散されることから、削除アルゴリズムの拡張性は、システム全体の拡張性に類似する。削除処理は、ユーザによる書込みと読出しのためのデータ配置に対処するのと同様に、内部DHTを用いてシステムの動的性質に対処する。削除処理はピアの障害に耐性を持つ。ピアでの計算に冗長性があるため、ガーベジ識別処理を途中で停止することはほとんどない。各スーパーノードに十分な数の良好なピアがある限り、識別処理を継続する。上記で述べたカウンタの検証は、最も有害なソフトウェアの障害から削除処理を保護するものである。[性能評価]別段の記載がない限り、実験はすべて4つのストレージノードSN、2つのアクセスノードANからなるコンテンツアドレスストレージシステムを使用している。すべてのサーバはRedHatEL5.3Linuxを実行し、2QuadCoreの3GHzのCPUと、4GigEカードを搭載している。各SNは、24GBのRAMと、12台の1TBのSATAディスクを搭載し、各ANは8GBのRAMと限られたローカルストレージを搭載している。実験は、33圧縮可能な平均ブロックサイズ64KBで実施した。データブロックは、9つのオリジナルと、3つの冗長フラグメントとして書き込まれ、3つの障害に対する耐性を有する。別段の記載がない限り、デフォルトリソース分割ポリシを使用し、全ての実験において、ユーザの動作書込みと読出しに70、削除関連のタスクに30のシステムリソースを使用した。[書込み/読出し帯域幅]この実験は、ガーベジ識別がユーザの書込み/読出し性能に与える影響を測定するものである。3つのグループからそれぞれ5つの値、計15のデータポイントを、重複排除率0から100まで25ごとに集計した。各グループにおける最初の測定は、削除を実行していない状態での特定の重複排除率での書込み帯域幅の測定である。2番目と3番目のデータポイントは同様のベースシナリオで集計した。まず、空のシステムに4TBの非重複データを入力し、削除を実行してブロックのカウンタを計算した。次に、400GBの新規データをロードし、400GBの既存データを削除した。これらの2つのデータポイントの違いは、使用したリソース分散ポリシである。2番目のデータポイントは書込みに100使用するリソース分割ポリシを用いたが、3番目のデータポイントはリソースの30を削除処理に向けるデフォルトリソース分割ポリシを用いた。読取りについては同様の実験を3回行ったが、書込みデータの代わりに、最初にロードしたデータの連続するいくつかのフラグメントを読み出すテストを行った。2つのANを利用し、各実験で多数のストリームを書き込んでクライアント側がボトルネックにならないかどうかを確認した。図5にその結果を示す。図5を見ると、非常に重複しているストリームで書込みの帯域幅が最も激しく落ちていることがわかる。その場合、CPUがボトルネックであり、ガーベジ識別プロセスは、例えば非削除マーカーの書込みのためにかなりのCPUサイクルを必要とする。重複排除がもっと少ないストリームの場合は、書込み性能は設定されたリソース分配ポリシと一致する。削除処理が読出しに与える影響は、書込みに与える影響よりも少ない。その理由は、本発明におけるストレージシステムの読出し手続きは帯域幅を犠牲にして読出しレイテンシを短くしているため、読出し時はCPUとディスクリソースをフルに利用しないからである。その結果、削除のニーズは読出しレイテンシに大きな影響を与えることなく受け入れられる。[ガーベジ識別時間]上記の実験を行う一方、さらにガーベジ識別の時間を測定した。デフォルトのリソース分割ポリシの場合の結果を図6に示す。2回目の削除実行時のガーベジ識別時間を測定した。削除時間については、ディスクがボトルネックになる。ディスクは非重複書込みによって集中的に使用されるため、そのような書込みがある場合に削除時間が最も長くなる。読出し中は、読出しレイテンシが短いため全てのディスクが使われることはない。その結果、読出し中の削除時間は短い。削除が最もCPUサイクルを必要とするのは、重複する書込みのために非削除マーカーを設定するときである。デフォルトのリソース分割ポリシでは削除に十分なCPUサイクルが当てられるが、その結果、上記で説明したように書込み性能が低下する。[領域解放]領域解放の時間を測定した5回の実験の各々において、500GBのデータを書き込み、その内の50GBを削除したが、再利用を終了させるには多様な分量のデータをリライトする必要がある。図7aは領域解放にかかる時間とリライトするデータ量とがほぼ線形の関係にあることを示している。これは、領域解放にかかる時間が、カウンタが0のブロックを保持するコンテナの数と比例するからである。上述したように、領域解放の際にはこのようなブロックを持つコンテナをリライトしなければならない。コンテナのリライトは重いオペレーションであるため、予想されるように、リライトするコンテナが多いほど領域解放にかかる時間が長くなる。[削除の拡張性]1~4個のSNを使って削除の拡張性を調べる実験を行った。システムに4MBの非重複データを入力し、そのうちの5を除去するようマークして削除を開始した。図7bは、2つのノードでのガーベジ識別は単一のノードの場合に比べて約2倍の速度であることを示している。3つ以上に増やせばこのフェーズをほぼ線状に短縮できるが、傾斜は緩やかになる。ノードの数が増えても削除処理で行われる作業は変わらず、全てのノード間で分散されるため、ノードの数が増えれば削除にかかる時間が短くなる。[ノード障害後の削除性能]ノード障害が識別時間に与える影響を測定する実験を3回行った。各実験は、当初4つのSNを使い、2TBの非重複データをシステムに入力して、その5を除去するようマークした。1回目の実験ではガーベジ識別のみを行った。2回目の実験では、1つのSNをシャットダウンし、ガーベジ識別を開始して、良好なピアが選択されてシャットダウンしたSNが再起動するのを待った。3回目の実験では、ガーベジ識別を開始する直前に1つのSNをシャットダウンした。各実験で、良好なピアを選択する時点からガーベジ識別が終了する時点までの時間を測定した。その結果を図8に示す。2番目の時間が長いのは、良好なピアが選択された後にSNの1つが再起動されており、このノードがガーベジ識別に参加しなかったためである。そのため、識別中に行う作業が4つではなく3つのSN間で分けられた。3番目の時間は2番目よりもさらに長い。その理由は、データの再構築に必要なバックグラウンドのタスクが、ガーベジ識別処理全体に渡って実行されていたからである。なお、識別の最中に障害が発生した場合、その処理は何とか終了までたどり着く。その時間は3番目の実験でかかった期間より長くはならない。[関連技術]本発明における削除処理は、よく知られている動的データ構造を持つプログラミング言語における並行ガーベジコレクション非特許文献2,3に類似する点もあるが、大きく異なる点がある。また、本発明における削除は、コンテンツアドレスストレージシステムの重複排除機能、拡張性、および障害耐性によって、より複雑になっている一方で、プログラミング言語のガーベジコレクションとは異なりブロックのグラフが非循環でなければならないため、削除が簡易になっている。本発明における削除は、遅延参照カウント非特許文献2に基づいている。マークアンドスイープ非特許文献4を用いて削除を行うこともできたが、削除処理毎にすべてのデータをトラバースすることを避けるために、この方法は取らなかった。グループ化されたマークアンドスイープ非特許文献5はこの問題に対処しており、バックアップをグループ分けして前回アルゴリズムが実行された後で削除されたファイルを含むグループのオブジェクトを含むコンテナのみをスイープする。バックアップデータの重複排除率は高いため、古いバックアップを1つ除去すると、再利用されるデータはほとんどないかもしれないが共有データを持つ多くのコンテナをスイープすることになる可能性がある。しかし、参照カウント方式の場合、その心配はない。本発明における非削除マーカーは、三色のマークアンドスイープ非特許文献2で読出しの際に白のオブジェクトをグレーにするのと、ある意味で類似する。重複排除がなければ、分散型ストレージシステムにおける削除は比較的簡単で、Glacier非特許文献6のようにリースで行うこともできれば、UrsaMinor非特許文献7のように簡易な旧バージョンの再利用で行うこともできる。しかし、重複排除がある場合は、前述の理由により難しくなる。例えば、Venti非特許文献8、DeepStore非特許文献9、SparseIndexing非特許文献10は削除を実行していない。他のクラスのシステムはストレージユニットに対してガーベジコレクションを行っているが、通常のオペレーションに影響を与えている。MAD2非特許文献11は指紋を参照カウントしているが、物理的な削除期間中は関連するすべてのタンカーをフリーズさせている。DDE非特許文献12はクライアントが保有するすべてのデータのロックを無効にして参照されるブロックを開放する。バックグラウンドでのdedupv1非特許文献13,14は、非参照ブロックをガーベジコレクション候補としてマークするが、システムがアイドルの場合にのみこれらのブロックを除去する。これ以外の技術として、SIS非特許文献15とFARSITE非特許文献16ではバックポインタ参照リストを使用し、DeDe非特許文献17は帯域外の更新されたグローバルハッシュインデックスの一部を排他的にスキャンするときに使用しないブロックを回収する。DataDomain特許文献1,2,非特許文献18は、インライン重複排除を行う集中型のシステムでガーベジコレクションを提供する。除去するブロックはBloomフィルタを使用して選択するため、結果としてシステム内に多少のガーベジが残る。EMCCentra特許文献3,非特許文献19,20はコンテンツユニットを明示的に削除するが、削除と重複排除をどのように並列に行うかについては述べていない。ExtremeBinning非特許文献21は、ビン内で重複排除をローカライズし、これによりガーベジコレクションが簡単になると述べているが、詳細は説明されていない。[結論と今後の研究]重複排除機能を持つ拡張性のあるストレージのための削除アルゴリズムについて述べた。この削除処理は、商用システムであるコンテンツアドレス型のストレージシステムに既に実装されている。このアルゴリズムは無停止、つまり削除処理中でもユーザによる書込みと読出しを継続できるものである。さらに、高度のアベイラビィティ、ユーザのオペレーションに関する性能への影響が低いこと、複数のディスク、ノード、またはネットワークの障害に対する耐性、システムの成長に合わせた構成の変化への適応等、重要な機能に関する要件にも対応している。削除が全体的なパフォーマンスに与える影響は、計算力またはディスク容量を変更するという観点から無理なく調整できる。また、古いデータと新たに書き込まれたデータとの間に境界を作るエポックのメカニズムによって、静止点をとり、カウンタ計算中も読み書きできるため、継続的なアベイラビリティが実現できる。したがって、現行のバックアップは、バックグラウンドで実行される削除処理の影響を受けない。実際のところ、無停止削除処理のための明確な意味論を定義する上でエポックの導入は不可欠である。一方、削除動作はバッチで行われてネットワーク全体に分散されるため、性能への影響は小さい。重要な点は、非削除マーカーがメインメモリに保存されるため、ユーザの書込みに対応するマーカーのオーバーヘッドが小さいことである。障害耐性は、良好なピアに対応付けられる計算の冗長性により実現される。選択されたピアが重要な計算を冗長的に行うため、そのいくつかがクラッシュした場合でも削除処理を進めることができる。また、良好なピアは削除処理の拡張性にも関与し、システム規模に応じて性能のスケーラビリティを確保することができる。削除の拡張性は、削除動作を各スーパーノードと対応付けることにより、集中的なコンポーネントなしで実現される。現在、削除は完全に機能しているが、エンドユーザのために重要な特長をさらに改良することができると思われる。削除手続きはオペレーションを停止させずに行われるため、最も改良が求められるのは性能のさらなる強化である。考えられる改良点の1つは、ポインタを持つブロック用に別のコンテナを導入することである。これにより、カウンタをインクリメントするフェーズが高速化されると思われる。性能の向上以外では、今後の研究を行う上での方向性として、中間の削除結果のチェックポイントを設けて削除を再スタートできるようにすることも挙げられる。<実施形態2>本発明の第2の実施形態を、図9乃至図20を参照して説明する。図9は、システム全体の構成を示すブロック図である。図10は、ストレージシステムの概略を示すブロック図であり、図11は、構成を示す機能ブロック図である。図12乃至図20は、ストレージシステムの動作を説明するための説明図である。ここで、本実施形態では、ストレージシステムが、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、1台のコンピュータで構成されていてもよい。図9に示すように、本発明におけるストレージシステム10は、ネットワークNを介してバックアップ処理を制御するバックアップシステム11に接続している。そして、バックアップシステム11は、ネットワークNを介して接続されたバックアップ対象装置12に格納されているバックアップ対象データ記憶対象データを取得し、ストレージシステム10に対して記憶するよう要求する。これにより、ストレージシステム10は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。そして、図10に示すように、本実施形態におけるストレージシステム10は、複数のサーバコンピュータが接続されて構成を採っている。具体的に、ストレージシステム10は、ストレージシステム10自体における記憶再生動作を制御するサーバコンピュータであるアクセラレータノード10Aと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード10Bと、を備えている。なお、アクセラレータノード10Aの数とストレージノード10Bの数は、図10に示したものに限定されず、さらに多くの各ノード10A,10Bが接続されて構成されていてもよい。さらに、本実施形態におけるストレージシステム10は、データを分割及び冗長化し、分散して複数の記憶装置に記憶すると共に、記憶するデータの内容に応じて設定される固有のコンテンツアドレスによって、当該データを格納した格納位置を特定するコンテンツアドレスストレージシステムである。このコンテンツアドレスストレージシステムについては、後に詳述する。なお、以下では、ストレージシステム10が1つのシステムであるとして、当該ストレージシステム10が備えている構成及び機能を説明する。つまり、以下に説明するストレージシステム10が有する構成及び機能は、アクセラレータノード10Aあるいはストレージノード10Bのいずれに備えられていてもよい。なお、ストレージシステム10は、図2に示すように、必ずしもアクセラレータノード10Aとストレージノード10Bとを備えていることに限定されず、いかなる構成であってもよく、例えば、1台のコンピュータにて構成されていてもよい。さらには、ストレージシステム10は、コンテンツアドレスストレージシステムであることにも限定されない。図11に、ストレージシステム10の構成を示す。この図に示すように、ストレージシステム10は、データを記憶する記憶装置31と、当該記憶装置31に対するデータの記憶及び読み出し動作を制御するデータ格納制御部21と、記憶装置31に格納されているが既に使用されなくなったデータの記憶領域を解放して再利用可能とするデータ解放制御部22と、を備えている。なお、実際には、データ格納制御部21とデータ解放制御部22とは、図10に示したアクセラレータノード10A及びストレージノード10Bが備えているCPUCentralProcessingUnitなどの複数の演算装置にプログラムが組み込まれることで構成されている。また、記憶装置31は、図10に示したアクセラレータノード10A及びストレージノード10Bが備えているハードディスクなどの記憶装置にて構成されている。なお、上記プログラムは、例えば、CD-ROMなどの記憶媒体に格納された状態でストレージシステム10に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム10に提供されてもよい。以下、上記データ格納制御部21と上記データ解放制御部22の構成について詳述する。はじめに、データ格納制御部21によるコンテンツアドレス方式のデータの記憶及び読み出し方法を、図12乃至図14を参照して説明する。まず、データ格納制御部21は、図13の矢印Y1に示すように、バックアップ対象データAの入力を受けると、図12及び図13の矢印Y2に示すように、当該バックアップ対象データAを、可変容量例えば、平均64KB、あるいは、所定容量例えば、64KBのブロックデータDに分割する。そして、このブロックデータDのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値H内容識別情報を算出する矢印Y3。例えば、ハッシュ値Hは、予め設定されたハッシュ関数を用いて、ブロックデータDのデータ内容から算出する。なお、このデータ格納制御部21による処理は、アクセラレータノード10Aにて実行される。そして、上記データ格納制御部21は、バックアップ対象データAのブロックデータDのハッシュ値Hを用いて、当該ブロックデータDが既に記憶装置31に格納されているか否かを調べる。具体的には、まず、既に格納されているブロックデータDは、そのハッシュ値Hと格納位置を表すコンテンツアドレスCAが、関連付けてMFIMainFragmentIndexファイルに登録されている。従って、データ格納制御部21は、格納前に算出したブロックデータDのハッシュ値HがMFIファイル内に存在している場合には、既に同一内容のブロックデータDが格納されていると判断できる図13の矢印Y4。この場合には、格納前のブロックデータDのハッシュ値Hと一致したMFI内のハッシュ値Hに関連付けられているコンテンツアドレスCAを、当該MFIファイルから取得する。そして、このコンテンツアドレスCAアドレスデータを、記憶要求にかかるブロックデータDのコンテンツアドレスCAとして記憶する。あるいは、既に格納されているブロックデータDを参照するコンテンツアドレスCAをさらに参照する他のアドレスデータをツリー構造にて記憶する。これにより、このコンテンツアドレスCAにて参照される既に格納されているデータが、記憶要求されたブロックデータDとして使用されることとなり、当該記憶要求にかかるブロックデータDは記憶する必要がなくなる。また、データ格納制御部21は、は、上述したように重複チェック部23にてまだ記憶されていないと判断されたブロックデータDを圧縮して、図13の矢印Y5に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図12の符号D1~D9に示すように、9つのフラグメントデータ分割データ41に分割する。さらに、データ格納制御部21は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ41に追加する。例えば、図12の符号D10~D12に示すように、3つのフラグメントデータ冗長データ42を追加する。これにより、9つの分割データ41と、3つの冗長データとにより構成される12個のフラグメントデータからなるデータセット40を生成する。なお、上記データ格納制御部21による処理は、1つのストレージノード10Bによって実行される。そして、データ格納制御部21は、生成されたデータセットを構成する各フラグメントデータを、記憶装置31に形成された各記憶領域に、それぞれ分散して格納する。例えば、図12に示すように、12個のフラグメントデータD1~D12を生成した場合には、12個の記憶装置31内にそれぞれ形成したデータ格納ファイルF1~F12データ格納領域に、各フラグメントデータD1~D12を1つずつそれぞれ格納する図13の矢印Y6参照。また、データ格納制御部21は、上述したように記憶装置31に格納したフラグメントデータD1~D12の格納位置、つまり、当該フラグメントデータD1~D12にて復元されるブロックデータDの格納位置を表す、コンテンツアドレスCAを生成して管理する。具体的には、格納したブロックデータDの内容に基づいて算出したハッシュ値Hの一部ショートハッシュ例えば、ハッシュ値Hの先頭8Bバイトと、論理格納位置を表す情報と、を組み合わせて、コンテンツアドレスCAを生成する。そして、このコンテンツアドレスCAを、ストレージシステム10内のファイルシステム、つまり、アクセラレータノード10Aに返却する図13の矢印Y7。すると、アクセラレータノード10Aは、バックアップ対象データのファイル名などの識別情報と、コンテンツアドレスCAとを関連付けてファイルシステムで管理する。また、データ格納制御部21は、ブロックデータDのコンテンツアドレスCAと、当該ブロックデータDのハッシュ値Hと、を関連付けて、各ストレージノード10BがMFIファイルにて管理する。このように、上記コンテンツアドレスCAは、ファイルを特定する情報やハッシュ値Hなどと関連付けられて、アクセラレータノード10Aやストレージノード10Bの記憶装置31に格納される。さらに、データ格納制御部21は、上述したように格納したバックアップ対象データを読み出す制御を行う。例えば、ストレージシステム10に対して、特定のファイルを指定して読み出し要求があると図14の矢印Y11参照、まず、ファイルシステムに基づいて、読み出し要求にかかるファイルに対応するハッシュ値の一部であるショートハッシュと論理位置の情報からなるコンテンツアドレスCAを指定する図14の矢印Y12参照。そして、データ格納制御部21は、コンテンツアドレスCAがMFIファイルに登録されているか否かを調べる図14の矢印13参照。登録されていなければ、要求されたデータは格納されていないため、エラーを返却する。一方、読み出し要求にかかるコンテンツアドレスCAが登録されている場合には、上記コンテンツアドレスCAにて指定される格納位置を特定し、この特定された格納位置に格納されている各フラグメントデータを、読み出し要求されたデータとして読み出す図14の矢印Y14参照。このとき、各フラグメントが格納されているデータ格納ファイルF1~F12と、当該データ格納ファイルのうち1つのフラグメントデータの格納位置が分かれば、同一の格納位置から他のフラグメントデータの格納位置を特定することができる。そして、データ格納制御部21は、読み出し要求に応じて読み出した各フラグメントデータからブロックデータDを復元する図14の矢印Y15参照。さらに、データ格納制御部21は、復元したブロックデータDを複数連結し、ファイルAなどの一群のデータに復元して、読み出し制御を行っているアクセラレータノード10Aに返却する図14の矢印Y16参照。ここで、データ格納制御部21は、時系列で区分した時間帯毎に、記憶対象データを上述したように記憶装置31に記憶する。具体的に、図15あるいは図16に示すように、所定の時間が経過する毎に、その時間帯を表す世代エポックを設定して、新規の記憶対象データの書き込み処理を行う。このとき、記憶装置31に書き込まれたデータがどの世代で書き込まれたかを区別できるよう、各ブロックデータにその世代を識別する情報を付加して記憶する。あるいは、各ブロックデータに書き込まれた世代の識別情報を対応付けて別途記憶するなどして管理してもよい。上記世代の遷移について、図16を参照して説明する。現在、書き込み対象となっている世代を新規ブロック世代とすると、その一つ前の世代が処理対象ブロック世代であり、さらに一つ前の世代は完了ブロック世代となる。逆に言うと、図15に示すように、符号1に示す現在の新規ブロック世代は、次の時間帯2になると処理対象ブロック世代となり、また、現在の時間帯1における処理対象ブロック世代は次の時間帯2になると完了ブロック世代と言うように、時間の経過に応じて、順次、世代が変化していく。そして、データ格納制御部21は、現在の新規ブロック世代で書き込まれる記憶対象データが存在する場合には、当該新規ブロック世代の世代、つまり、次の世代に移り変わる前に、記憶対象データの記憶装置31への書き込みを完成させる必要がある。例えば、データ格納制御部21は、図16に示すように、完了ブロック世代で、Block6からBlock4、Block5へと順に参照するBlock1、Block2、Block3からなる記憶対象データを格納して保存する。このとき、これら新たに保存されたブロックデータは、保存されたブロックであることを表すRetention1ブロックに参照される。なお、例えば、Block4、Block5、Block6はアドレスデータであり、図16の網掛けで示すBlock1、Block2、Block3は実データである。そして、次の世代である処理対象ブロック世代にて、上記Block6を構成するブロックデータBlock3がBlock3xに変更されたとすると、新たなブロックデータBlock3x図16の斜線で示すと、これを参照するBlock5x、Block6xが処理対象ブロック世代に格納されることとなる。つまり、この処理対象ブロック世代では、Block6の代わりに、Block6xからBlock4、Block5xへと順に参照されるBlock1、Block2、Block3xからなるブロックデータが格納されることとなる。但し、Block1、Block2は既に記憶装置31に格納されているブロックデータが参照されることとなる。そして、このとき、Block6xにて参照されるブロックデータが新たに保存されたため、Block6xブロックは、保存されたブロックであることを表すRetention2ブロックに参照される。また、Block6xに変更されたBlock6は削除されるため、削除されたことを表すDeletion1ブロックに参照される。さらに、上述同様に次の世代である新規ブロック世代になり、上記Block6xを構成するブロックデータBlock2がBlock2yに変更されたとすると、新たなブロックデータBlock2y図16の斜線で示すと、これを参照するBlock4y、Block6yが新規ブロック世代に格納されることとなる。つまり、この新規ブロック世代では、Block6xの代わりに、Block6yからBlock4y、Block5xへと順に参照されるBlock1、Block2y、Block3xからなるブロックデータが格納されることとなる。但し、Block1は既に記憶装置31に格納されているブロックデータが参照されることとなる。そして、このとき、Block6yにて参照されるブロックデータが新たに保存されたため、Block6yブロックは、保存されたブロックであることを表すRetention2ブロックに参照される。また、そして、Block6yに変更されたBlock6xは削除されるため、削除されたことを表すDeletion2ブロックに参照される。次に、データ解放制御部22について説明する。データ解放制御部22は、図11に示すように、参照数カウント部23とデータ解放部24とを備えており、それぞれ以下の処理を実行する。まず、参照数カウント部23は、上述した世代が変わる毎に、つまり、現在の新規ブロック世代となる度に、過去に世代で記憶装置31に書き込まれたデータのうち、別のアドレスデータから参照されていない記憶対象データあるいはアドレスデータを削除し、かかるデータが格納されていた記憶装置31内の記憶領域を解放する削除処理を実行する。具体的に、参照数カウント部23は、現在の新規ブロック世代に対して直前の世代である処理対象ブロック世代に書き込まれたデータ以下、ブロックデータと呼ぶに対して、他のアドレスデータから参照されている数を表す被参照数をカウントする。被参照数のカウントは、Retentionブロックに参照されているルート上に位置するブロックデータである場合は、1とする。また、Deletionブロックに参照されているルート上に位置するブロックデータである場合は、-1とする。例えば、図17の場合は、現在の新規ブロック世代に対して直前の処理対象ブロック世代内の各ブロックデータの被参照数がカウントされるが、処理対象ブロック世代内のRetention1の書き込みしか確定していないため、当該Retention1から参照される各ブロックデータBlock1~Block6の被参照数がそれぞれ1となる。そして、時間が経過して次の世代に移行した図18の場合には、新規ブロック世代の直前の処理対象ブロック世代で確定したRetention1とDeletion1に参照される各ブロックデータの被参照数が、それぞれ増減される。すると、点線で囲まれたBlock3、Block5、Block6の被参照数が0となる。これにより、いずれのアドレスデータからも参照されなくなったブロックデータの被参照数は0となるため、かかるブロックデータを検出することが容易となる。そして、データ解放部24は、新規ブロック世代にて実行される削除処理の最後に、あるいは、一定の時間間隔にて実行され、被参照数が0となったブロックデータを記憶装置31内から削除する。このとき、さらにデータ解放部24は、削除したブロックデータが格納されていた記憶装置31内の記憶領域を解放する。つまり、いずれのアドレスデータからも参照されなくなったブロックデータの読み出しができないようにするだけではなく、かかるブロックデータが記憶されていた記憶領域を再利用可能なよう、当該記憶領域を解放する。なお、データ解放部24による記憶領域の解放処理は、いかなるタイミングで実行されてもよい。ここで、上記参照数カウント部23は、図19に示すように、削除処理を同期フェーズ、削除マークフェーズ、コミットフェーズの3段階で行う。同期フェーズでは、ストレージシステム10に書き込まれたデータの記憶装置31への書き込みを完了させる。つまり、直前の世代で書き込まれたデータのうち、書き込み途中であるデータが存在する場合には、かかるデータを記憶装置31に書き込み、図18に示すようなツリー構造を完成させる。続いて、削除マークフェーズでは、記憶装置31の書き込みが完了したブロックデータの被参照数をカウントする処理を行う。これにより、ブロックデータのツリー構造、つまり、参照関係が確定してから被参照数をカウントすることができるため、より確実に参照されていないデータの解放を実現できる。但し、上述した削除マークフェーズにおける被参照数のカウント中には、カウント対象となっているブロックデータを参照して重複排除される新たにデータの書き込みが行われる場合がある。すると、カウントしているブロックデータの被参照数を確定できず、場合によっては被参照数が0となるブロックデータを、新たな書き込みデータが参照する場合も生じ、後に削除されてしまう場合も起こりうる。例えば、図20に示すように、新規ブロック世代でBlock3の被参照数がカウントされている最中に当該Block3を参照する新たな書き込みが発生すると、かかるBlock3は参照されているにも関わらず後に削除されてしまうことも起こりうる。かかる状況を避けるために、参照数カウント部23は、削除マークフェーズにてブロックデータの被参照数をカウントしているときに新たな書き込みが生じ、過去の世代で格納されたブロックデータを参照している場合には、当該ブロックデータにUndeleteMakerというフラグを設定する。そして、このUndeleteMakerというフラグは、設定されていることにより、データ解放部24による解放の対象から除外する印である。従って、図20の例では、新規ブロック世代の時点ではブロックデータBlock3の被参照数が0になるが、UndeleteMakerが設定されるため、削除及び解放されない。そして、さらに次の世代となると、Block3の被参照数が再度カウントされ1になるため、削除されない。また、コミットフェーズでは、削除マークフェーズでカウントしたブロックデータの被参照数を、システムに反映させる。そして、システムに反映された被参照数が後にデータ解放部24にて把握されることで、被参照数が0であるブロックデータが削除され、その記憶領域が解放されることとなる。但し、上述したコミットフェーズにおいて被参照数をシステムに反映している最中にも、カウントされたブロックデータを参照して重複排除される新たにデータの書き込みが行われる場合がある。すると、被参照数が0とカウントされたブロックデータを、新たな書き込みデータが参照する場合も生じ、後に削除されてしまう場合も起こりうる。例えば、図20に示すように、新規ブロック世代でBlock3の被参照数のカウントが終了した後に当該Block3を参照する新たな書き込みが発生すると、かかるBlock3は参照されているにも関わらず後に削除されてしまうことも起こりうる。かかる状況を避けるために、参照数カウント部23は、コミットフェーズにてブロックデータの被参照数をシステムに反映しているときに新たな書き込みが生じた場合には、被参照数が正の値つまり、被参照数>0であるブロックデータ、あるいは、上述したUndeleteMakerが設定されているブロックデータ、に対する参照のみを許可する。これにより、新たな書き込みにより、後に削除される可能性の高いブロックデータが参照されて重複排除処理が行われることを抑制できる。上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム図21参照、プログラムを記憶した記憶媒体、情報処理方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。付記1記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置110に格納すると共に、当該記憶装置110に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置110に格納する場合に、当該記憶装置110に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置110に格納するデータ格納制御部101と、前記記憶装置110に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置110内の記憶領域を解放するデータ解放制御部102と、を備え、前記データ格納制御部101は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置110に格納し、前記データ解放制御部102は、現在の時間帯に対して過去の時間帯に前記記憶装置110に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置110内の記憶領域を解放する、ストレージシステム。付記2付記1に記載のストレージシステムであって、前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ストレージシステム。付記3付記2に記載のストレージシステムであって、前記データ解放制御部は、現在の時間帯に対して直前の時間帯以前に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントする、ストレージシステム。付記4付記3に記載のストレージシステムであって、前記データ解放制御部は、前記データ格納制御部にて直前の時間帯に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記記憶装置内への格納を完了した後に、前記被参照数をカウントする、ストレージシステム。付記5付記2に記載のストレージシステムであって、前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントしているときに、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを前記データ解放制御部による解放の対象から除外する設定を行う、ストレージシステム。付記6付記5に記載のストレージシステムであって、前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数のカウントが終了した後に、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータの前記被参照数が正の値、あるいは、当該記憶対象データあるいはアドレスデータが前記データ解放制御部による解放の対象から除外されている場合に、前記新たな書き込みに対応する前記記憶対象データあるいは前記アドレスデータの参照を行う、ストレージシステム。付記7情報処理装置に、記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、ことを実現させるためのプログラムを記憶した記憶媒体。付記8付記7に記載のプログラムを記憶した記憶媒体であって、前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、プログラムを記憶した記憶媒体。付記9記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納し、前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、前記記憶対象データあるいは前記アドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータに対して、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、情報処理方法。付記10付記9に記載の情報処理方法であって、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が0である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、情報処理方法。"