(57)【特許請求の範囲】
【請求項１】
記憶対象データ、及び、参照先に格納されているデータである前記記憶対象データ又は他のコンテンツアドレスデータを参照し、当該記憶対象データ又は他のコンテンツアドレスデータ内容に基づいて算出された情報と、当該記憶対象データ又は他のコンテンツアドレスデータデータの格納位置を表す情報と、を組み合わせたコンテンツアドレスデータ、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記コンテンツアドレスデータを前記記憶装置に格納する、データ格納制御部と、
前記記憶装置に格納されている前記記憶対象データあるいは前記コンテンツアドレスデータのうち、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を備え、
前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記コンテンツアドレスデータを前記記憶装置に格納し、
前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータのうち、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ストレージシステム。
【請求項２】
請求項１に記載のストレージシステムであって、
前記データ解放制御部は、前記記憶対象データあるいは前記コンテンツアドレスデータにおける別のコンテンツアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ストレージシステム。
【請求項３】
請求項２に記載のストレージシステムであって、
前記データ解放制御部は、現在の時間帯に対して直前の時間帯以前に書き込まれた前記記憶対象データあるいは前記コンテンツアドレスデータの前記被参照数をカウントする、
ストレージシステム。
【請求項４】
請求項３に記載のストレージシステムであって、
前記データ解放制御部は、前記データ格納制御部にて直前の時間帯に書き込まれた前記記憶対象データあるいは前記コンテンツアドレスデータの前記記憶装置内への格納を完了した後に、前記被参照数をカウントする、
ストレージシステム。
【請求項５】
請求項２乃至４のいずれかに記載のストレージシステムであって、
前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記コンテンツアドレスデータの前記被参照数をカウントしているときに、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータを前記データ解放制御部による解放の対象から除外する設定を行う、
ストレージシステム。
【請求項６】
請求項５に記載のストレージシステムであって、
前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記コンテンツアドレスデータの前記被参照数のカウントが終了した後に、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータの前記被参照数が正の値、あるいは、当該記憶対象データあるいは前記コンテンツアドレスデータが前記データ解放制御部による解放の対象から除外されている場合に、前記新たな書き込みに対応する前記記憶対象データあるいは前記コンテンツアドレスデータの参照を行う、
ストレージシステム。
【請求項７】
情報処理装置に、
記憶対象データ、及び、参照先に格納されているデータである前記記憶対象データ又は他のコンテンツアドレスデータを参照し、当該記憶対象データ又は他のコンテンツアドレスデータ内容に基づいて算出された情報と、当該記憶対象データ又は他のコンテンツアドレスデータデータの格納位置を表す情報と、を組み合わせたコンテンツアドレスデータ、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記コンテンツアドレスデータを前記記憶装置に格納するデータ格納制御部と、
前記記憶装置に格納されている前記記憶対象データあるいは前記コンテンツアドレスデータのうち、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、
前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記コンテンツアドレスデータを前記記憶装置に格納し、
前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータのうち、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ことを実現させるためのプログラム。
【請求項８】
請求項７に記載のプログラムであって、
前記データ解放制御部は、前記記憶対象データあるいは前記コンテンツアドレスデータにおける別のコンテンツアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
プログラム。
【請求項９】
記憶対象データ、及び、参照先に格納されているデータである前記記憶対象データ又は他のコンテンツアドレスデータを参照し、当該記憶対象データ又は他のコンテンツアドレスデータ内容に基づいて算出された情報と、当該記憶対象データ又は他のコンテンツアドレスデータデータの格納位置を表す情報と、を組み合わせたコンテンツアドレスデータ、を記憶装置に格納すると共に、
当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記コンテンツアドレスデータを前記記憶装置に格納し、
前記記憶装置に格納されている前記記憶対象データあるいは前記コンテンツアドレスデータのうち、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、
前記記憶対象データあるいは前記コンテンツアドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、
現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記コンテンツアドレスデータに対して、別のコンテンツアドレスデータから参照されていない前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
情報処理方法。
【請求項１０】
請求項９に記載の情報処理方法であって、
前記記憶対象データあるいは前記コンテンツアドレスデータにおける別のコンテンツアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記コンテンツアドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステムにかかり、特に、重複排除機能を有するストレージシステムに関する。
【背景技術】
【０００２】
企業向け市場で成功する補助記憶装置は、いくつかの特徴を同時に提供する必要がある。大容量、高性能、そして高い信頼性は、バックアップやアーカイブ用のストレージ装置に求められる主な機能である。バックアップでは様々な種類の類似データを格納することになるため、重複排除技術は、このようなシステムにおいて当然に新たな重要な特徴となる。重複排除によって、論理的な記憶容量は、記憶装置の利用可能な物理的記憶領域よりもはるかに大きくなる。その結果、実質的に記憶装置の記憶領域を節約できる。重複排除をバックアップストリームに対してon-the-flyで実行すれば、重複ブロックの記憶装置への書き込みを省略できるため、高性能化に寄与する。また、重複排除に必要な計算は分散処理によってスケールするため、高性能化が可能である。その結果、企業にとって最も重要な点であるバックアップ時間を短縮することができる。
【０００３】
非特許文献１に開示のストレージシステムは、上記のあらゆる特徴を提供する商用の分散型ストレージシステムである。つまり、このシステムは、他のブロックへの参照が可能な可変長ブロックの集合体を保持する分散ストレージシステムとみなすことができる。このシステムは、コンテンツに基づいて生成されるブロックアドレスを使用し、既に格納済みの全ブロックに対するグローバルな重複排除機能を提供する。非特許文献１に開示のストレージシステムは、ＤＨＴ（Distributed Hash Table：分散ハッシュテーブル）に基づいて構築され、障害からの自己回復機能を持つ。Erasureコードを使用してデータの冗長コード（パリティ）を生成し、ユーザが選択可能な複数のデータ復元レベルを提供する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】PATTERSON, R. H. Incrementalgarbage collection of data in a secondary storage. Patent, 11 2008. US 7451168.
【特許文献２】PATTERSON, R. H. Probabilisticsummary data structure based encoding for garbage collection. Patent, 04 2010.US 7707166.
【特許文献３】TODD, S. J., KILIAN,M., TEUGELS,T., MARIVOET,K., AND MATTHYS, F. Methods and apparatus for managing deletion ofdata. Patent, 04 2010. US 7698516.
【非特許文献】
【０００５】
【非特許文献１】DUBNICKI, C., GRYZ, L., HELDT, L., KACZMARCZYK, M., KILIAN, W.,STRZELCZAK, P., SZCZEPKOWSKI, J., UNGUREANU, C., AND WELNICKI, M. Hydrastor: ascalable secondary storage. In FAST ’09: Proccedings of the 7th conference onFile and storage technologies (San Francisco, CA, USA, 2009), USENIX Association,pp. 197‐210.
【非特許文献２】WILSON, P. R. Uniprocessorgarbage collection techniques. In IWMM ’92: Proceedings of the InternationalWorkshop on Memory Management (London, UK, 1992), Springer-Verlag, pp. 1‐42.
【非特許文献３】ABDULLAHI, S. E., AND RINGWOOD,G. A. Garbage collecting the internet: a survey of distributed garbagecollection. ACM Comput. Surv. 30, 3 (1998), 330‐373.
【非特許文献４】DIJKSTRA, E. W., LAMPORT, L.,MARTIN, A. J., SCHOLTEN, C. S., AND STEFFENS, E. F. M. On-the-fly garbagecollection:An exercise in cooperation.Commun. ACM 21, 11 (1978), 966‐975.
【非特許文献５】EFSTATHOPOULOS, P., AND GUO, F.Rethinking Deduplication Scalability. In 2nd USENIX Workshop on Hot Topics inStorage and File Systems (Boston, MA, USA, June 2010).
【非特許文献６】HAEBERLEN, A., MISLOVE, A., ANDDRUSCHEL, P. Glacier: highly durable, decentralized storage despite massivecorrelated failures. In NSDI’05: Proceedings of the 2nd conference on Symposiumon Networked Systems Design & Implementation (Berkeley, CA, USA, 2005),USENIX Association, pp. 143‐158.
【非特許文献７】ABD-EL-MALEK, M., II, W. V. C.,CRANOR, C., GANGER, G. R., HENDRICKS, J., KLOSTERMAN, A. J., MESNIER,M. P., PRASAD,M., SALMON, B., SAMBASIVAN, R. R., SINNAMOHIDEEN, S., STRUNK, J. D., THERESKA,E., WACHS,M., AND WYLIE, J. J. Ursa minor: Versatile cluster-based storage. In FAST(2005).
【非特許文献８】QUINLAN, S., AND DORWARD, S.Venti: a new approach to archival storage. In First USENIX conference on Fileand Storage Technologies (Monterey, CA, 2002), USENIX Association, pp. 89‐101.
【非特許文献９】YOU, L. L., POLLACK, K. T., ANDLONG, D. D. E. Deep store: An archival storage system architecture. In ICDE’05: Proceedings of the 21st International Conference on Data Engineering (Washington,DC, USA, 2005), IEEE Computer Society, pp. 804‐8015.
【非特許文献１０】LILLIBRIDGE,M., ESHGHI, K.,BHAGWAT, D., EOLALIKAR, V., TREZIS, G., AND CAMBLE, P. Sparse indexing: Largescale, inline deduplication using sampling and locality. In FAST (2009), pp.111‐123.
【非特許文献１１】WEI, J., JIANG, H., ZHOU, K., ANDFENG, D. Mad2: A calable high-throughput exact deduplication approach fornetwork backup services. In Proceedings of the 26th IEEE Symposium on MassiveStorage Systems and Technologies (MSST) (May 2010).
【非特許文献１２】HONG, B., AND LONG, D. D. E.Duplicate data elimination in a san file system. In In In Proceedings of the21st IEEE / 12th NASA Goddard Conference on Mass Storage Systems andTechnologies (MSST (2004), pp. 301‐314.
【非特許文献１３】MEISTER, D., AND BRINKMANN, A.dedupv1: Improving Deduplication Throughput using Solid State Drives (SSD). In Proceedingsof the 26th IEEE Symposium on Massive Storage Systems and Technologies (MSST) (May2010).
【非特許文献１４】MEISTER, D., AND BRINKMANN, A.dedupv1: Improving deduplication throughput using solid state drives (technicalreport). Tech. rep., April 2010.
【非特許文献１５】BOLOSKY, W. J., CORBIN, S.,GOEBEL, D., AND DOUCEUR, J. R. Single instance storage in windows 2000. In InProceedings of the 4th USENIX Windows Systems Symposium (2000), pp. 13‐24.
【非特許文献１６】ADYA, A., BOLOSKY, W., CASTRO,M., CHAIKEN, R., CERMAK, G., DOUCEUR, J., HOWELL, J., LORCH, J., THEIMER, M.,AND WATTENHOFER, R. Farsite: Federated, available, and reliable storage for anincompletely trusted environment, 2002.
【非特許文献１７】CLEMENTS, A., AHMAD, I.,VILAYANNUR, M., AND LI, J. Decentralized deduplication in san cluster filesystems. In Proceedings of the USENIX Annual Technical Conference (June 2009).
【非特許文献１８】ZHU, B., LI, K., AND PATTERSON,H. Avoiding the disk ottleneck in the data domain deduplication file system. InFAST’08:Proceedings of the 6th USENIX Conference on File and Storage Technologies(Berkeley, CA, USA, 2008), USENIX Association, pp. 1‐14.
【非特許文献１９】EMC Corp. EMC Centera: contentaddressed storage system, January 2008.http://www.emc.com/products/family/emccentera-family.htm?-openfolder=platform.
【非特許文献２０】GUNAWI, H. S., AGRAWAL, N.,ARPACI-DUSSEAU, A. C., ARPACI-DUSSEAU, R. H., AND SCHINDLER, J. Deconstructing CommodityStorage Clusters. In Proceedings of the 32nd International Symposium onComputer Architecture (Madison, WI, June 2005).
【非特許文献２１】BHAGWAT, D., ESHGHI, K., LONG, D.D. E., AND LILLIBRIDGE, M. Extreme binning: Scalable, parallel deduplicationfor chunk-based file backup.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１に開示のストレージシステムにおける削除処理手順は、誰も必要としなくなったブロックを削除して、その記憶領域を再利用するという、これまでのガーベジコレクションとある意味で類似する。しかしながら、削除処理は、重複排除、分散ストレージ構成、および、障害耐性に対する要求によって、著しく複雑である。例えば、削除実行中は重複排除を不能にするという単純な解決策は、記憶領域の消費を増やすことになるため、受け入れられない。削除実行中であっても常に重複排除を可能にするのが、より良いアプローチである。
【０００７】
このため、本発明の目的は、上述した課題である、データの重複排除を実現しつつ、記憶領域の有効利用を図ることができるストレージシステムを提供することにある。
【課題を解決するための手段】
【０００８】
本発明の一形態であるストレージシステムは、
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、
前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を備え、
前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、
前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
という構成をとる。
【０００９】
また、本発明の他の形態であるプログラムを記憶した記憶媒体は、
情報処理装置に、
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、
前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、
前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、
前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ことを実現させるためのプログラムを記憶した記憶媒体である。
【００１０】
また、本発明の他の形態である情報処理方法は、
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納し、
前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、
前記記憶対象データあるいは前記アドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、
現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータに対して、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
という構成をとる。
【発明の効果】
【００１１】
本発明は、以上のように構成されることにより、データの重複排除を実現しつつ、記憶領域の有効利用を図ることができるストレージシステムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】実施形態１におけるエポックの割当てに関するルールを示す図である。
【図２】実施形態１におけるブロックの分類を示す図である。
【図３】実施形態１におけるブロック削除時における問題点を示す図である。
【図４】実施形態１におけるエポックを前進させる様子を示す図である。
【図５】実施形態１におけるユーザオペレーションの帯域幅を示す図である。
【図６】実施形態１におけるユーザ動作進行中のガーベジ識別時間を測定した図である。
【図７】実施形態１における領域解放時間とガーベジ識別時間とを測定した図である。
【図８】実施形態１におけるストレージノードに問題が生じたときのガーベジ識別時間を測定した図である。
【図９】実施形態２におけるストレージシステムを含むシステム全体の構成を示すブロック図である。
【図１０】実施形態２におけるストレージシステムの構成の概略を示すブロック図である。
【図１１】実施形態２におけるストレージシステムの構成を示す機能ブロック図である。
【図１２】図１１に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１３】図１１に開示したストレージシステムにおけるデータ記憶処理の様子を説明するための説明図である。
【図１４】図１１に開示したストレージシステムにおけるデータ読み出し処理の様子を説明するための説明図である。
【図１５】実施形態２における世代の変化を示す図である。
【図１６】実施形態２における書き込まれたデータの様子を示す図である。
【図１７】実施形態２における書き込まれたデータの被参照数の算出例を示す図である。
【図１８】実施形態２における書き込まれたデータの被参照数の算出例を示す図である。
【図１９】実施形態２における削除処理の詳細を示す図である。
【図２０】実施形態２におけるデータ削除時における問題点とその解決方法を説明するための図である。
【図２１】本発明の付記１におけるストレージシステムの構成を示すブロック図である。
【発明を実施するための形態】
【００１３】
＜実施形態１＞
本実施形態では、次の事項を述べる。まず第１に、分散型重複排除ブロック格納における削除要件を特定する。第２に、この要件を満たし、商用システムに既に導入されているアルゴリズムを提示する。第３に、削除処理手順に関する評価結果について論じ、その効果と、削除がクリティカルなユーザのオペレーションに与える影響について述べる。
【００１４】
また、本実施形態は、以下のように構成されている。まず、削除要件を概説する。続いて、ユーザから見た削除の意味と、関連するデータモデルを定義する。続いて、非特許文献１に開示のストレージシステムで削除を実施する上で直面する問題点を述べる。続いて、本発明における削除処理のアルゴリズムを詳細に述べる。続いて、実施される削除処理がこれまでの要求にどのように対応しているか、および、その性能について説明する。続いて、本発明に関連する技術について述べる。続いて、結論と今後の研究について述べる。
【００１５】
［削除要件］
あらゆるシステムにおいて、削除を行うためには、まずユーザにデータを選択的に削除してもらい、残すと決定したデータを保存してもらう必要がある。通常、データが削除対象としてマークされると、ストレージの有効利用の観点から効率化のために直ちに記憶領域の再利用が行われる。しかし、主記憶装置とは異なり、補助記憶装置では使用しない領域の回復を遅らせることができる。重複排除されたストレージは、はるかに記憶領域が効率化されており、またＣＡＳ（Content Addressable Storage）システムにとって記憶領域の再利用は非常に複雑であるため、直ちにデータを削除することはそれほど重要ではない。
【００１６】
企業で利用されるバックアップシステムでは、バックアップ、復旧、復元等のユーザの操作が削除によって受ける影響を最小限に抑える必要がある。このような機能を常時利用できることが期待されており、削除の実行によりその性能が影響を受けることが全くないとは言えないとしても、ほとんどあってはならない。削除の実行を読出し専用期間に限定すると、バックアップ時間を再設定しなければならなくなるため、この方法を許容するのは難しいことが以前のストレージシステムでわかっている。また、継続的なバックアップポリシーの場合には、このような制限は事実上不可能である。
【００１７】
削除処理を実行するとシステムリソースを消費するため、システム全体の性能に影響が出る。この影響を削減することが、削除処理を実施する上での１つの目標である。さらに、削除処理は、システム全体に対応させる必要がある。データ処理能力とディスク容量を比例的に変更することで、削除処理が全体的な性能に与える影響を同じレベルに保つことができると考えられる。
【００１８】
また、システム内の装置とディスクの数が増えれば、ハードウェアが故障する可能性も増える。確実にシステムを利用できるようにするためには、ディスク、ノード、およびネットワークに複数の障害が発生しても、削除処理が継続できる必要がある。また、データ削除能力はシステムの運用にとって不可欠であるため、永久的なデータ障害が発生した場合でも削除処理の再スタートと終了が可能であるべきであり、このため、実際のところ、ユーザデータの回復性よりも削除の回復性の方が高くなっているべきである。
【００１９】
さらに、大事な点として、削除を完了するために、重要なストレージの追加が必要になってはならない。
【００２０】
［ユーザから見た意味］
［データモデル］
非特許文献１に開示のストレージシステムのユーザから見た基本的なデータ単位は、「ブロック」である。ブロックは、バイナリデータに加えて、他のブロックへの「ポインタ」を含むことができる。「ブロックアドレス」は、ブロックのデータ内容から生成され、他にもブロックがある場合は他のブロックへのポインタも含む。「コンテンツアドレス指定」とは、ブロックが不変であることを意味する。そうでない場合はブロックのアドレスは変わる場合があるからである。なお、本発明のシステムでは、ブロックには、「通常ブロック（regular blocks）」と「検索可能ブロック（searchable blocks）」という２つの異なる種類があることとする。
【００２１】
検索可能ブロックは、通常ブロックの読出しに必要な暗号化コンテンツによって生成されるアドレスではなく、関連する検索キーで読み出すことができる。検索キーは、任意の文字列でもよく、検索可能ブロックの書込み時に、バイナリデータやポインタと共にユーザから提供される。検索可能ブロックは、このキーでしか読み出すことができないため、このシステムでは内容の異なる２つの検索可能ブロックに同じキーを設定することはできない。検索可能ブロックには通常アドレスはなく、他のブロックからポインタで参照することはできない。
【００２２】
非特許文献１に開示のストレージシステムは重複排除機能を持つため、通常ブロックの書込みによって戻されたアドレスは、この重複する書込みの「ベースブロック」と言われる既存のブロックを参照することができる。重複排除は、検索可能ブロックについても機能する。
【００２３】
このような種類のブロックと関連する操作によって、システムはブロックのグラフを作成することができる。ブロックは不変であり、このグラフは非循環である。参照先ブロックが存在しない状況が発生することを防ぐため、システムは、まず参照先ブロックを書き込んで当該ブロックのコンテンツからブロックアドレスを生成する。その後、そのアドレスを参照するブロックを書き込む。そのため、ブロックのグラフは、ボトムアップに葉から根に向かってのみ構築される。
【００２４】
［削除処理単位］
本システムでは、個々のブロックを取り除く方法を提供するのではなく、ある検索可能ブロックから到達できる、不必要となった全てのブロックをマークする。詳しく説明すると、検索可能ブロックには、「保存ルート（retention roots）」と「削除ルート（deletion roots）」という２つのサブタイプがある。保存ルートと削除ルートは、もしそれらの検索可能キーが等しければ、保存ルートは削除ルートと一致するといえる。保存ルートは、そこから到達可能なブロックを、保存するブロックとしてマークし、削除ルートは、一致する保存ルートのこの性質を「取り消す」ものである。なお、検索可能ブロックのサブタイプを区別するために追加のマーカーを使用するため、実際には、キーの一意性の要件は保存ルートにのみ適用される。保存ルートは、システム内に一致する削除ルートがなければ「生きている」といえ、生きている保存ルートから到達できる通常ブロックは生きている。ブロックが生きていない場合は「死んでいる」という。
【００２５】
理論上は、削除を行うためにブロックのグラフ全体をマークするのでなく、単一のブロックを削除する操作を行うことが可能である。ただし、そうすると個々のブロックの削除を追跡し続けることが困難となり、また最も重要な点として、システム内の他の既存ブロックから参照されているブロックを削除することで、懸垂参照（dangling reference）が発生する恐れがある。
【００２６】
また、悪意あるユーザは、適切な検索キーがわかれば他のユーザのブロックを削除できてしまうという問題があるが、この問題は検索可能ブロックのキーをユーザ固有のＩＤで暗号化することで簡単に解決される。
【００２７】
［エポック（世代）を用いた削除とユーザとの同期］
削除実行中にポインタ（参照先）付きのブロックを書き込むと、削除に関して上記のような問題が発生する。ユーザが、新たな通常ブロックＡを書き込み、またブロックＡを指す保存ルートＲを書き込んで、このブロックを保存したいとする。システムが返したブロックＡのアドレスは、保存ルートＲのコンテンツに挿入される必要があるため、保存ルートＲの書込み要求を出す前に、ブロックＡの書込みを無事完了しなければならない。この２つの書込みを行う間に削除処理が実行されると、上述したようにブロックＡは死んでいるので、当該ブロックＡは削除される。
【００２８】
この問題を解決するために、生きているブロック群を拡張し、ユーザが維持できるブロックとそこから到達可能なブロックを、全て生きているブロックに含める。ユーザは全てのブロックを維持することが可能になるため、ユーザが記憶できるブロックを制限する。そのために、いわゆる「エポック」（世代）に基づいて構築される仮想時刻を導入する。「エポック」とは、世代の前進操作を表現するグローバルカウンタである。このシステムでは、いかなる時点も、「現在エポック」と呼ぶ唯一のエポック時刻で表すこととする。
【００２９】
ユーザによって取得される各ブロックアドレスは、当該アドレスと対応付けられたエポックを有する。システムは、書込みに関して、対応付けられたエポックＴを持つアドレスは、エポックＴおよびＴ＋１でのみ使用できることを確認する。読出しについては、ユーザは古いエポックが対応付けられたアドレスを使用することもできるが、そのブロックが削除されている場合、読出しは失敗となる。
【００３０】
あるブロックのアドレスについては、このアドレスの取得方法によってエポックが変わってくる。エポックの割当てに関するルールを図１に示す。この詳細なレベルは完全を期すためにここで提示するが、後にも説明する。
【００３１】
ポインタのない通常ブロックを書き込む場合、システムは、ブロックアドレスとそれに対応付けられた現在エポックを返却する。書き込まれるブロックがポインタを含む場合、この書込みと共に返却されるエポックは、このブロックに挿入される複数のブロックアドレスのエポックの中で最小値のものとなる（図１で示される「ミニマムルール」）。検索可能ブロックには通常アドレスがないため、エポックは割り当てられない。書込み時に返却されるエポックは、書き込まれるブロックの重複状況に依存しない。
【００３２】
ブロックアドレスは、ポインタ（参照）付きのブロックを読み出すことによって取得することもできる。あるブロックを読み出すことによって得られる複数のポインタのエポックは同一である。ポインタ付きの通常ブロックのエポックは、読み出したブロックのアドレスに対応付けられたエポックと等しい。ポインタ付きの検索可能ブロックの場合、ポインタのエポックは現在エポックと等しい。
【００３３】
ツリー構築のプロセスでは、ユーザは既に書き込まれたブロックのアドレスを保持し、それを親ブロックに挿入する必要がある。しかし、エポック導入後は、現在と前回のエポックがスタンプされたアドレスのみが、その後のブロック作成で使用される。
【００３４】
エポックがＴからＴ＋１へ進む（前進操作の適用）と、エポックＴを持つ全てのブロックアドレスを破棄するために、全てのユーザにその事実が通知される。ここで、ポインタの破棄とは、生きている保存ルートによって参照されるツリーに、これらのポインタを入れることを意味する。これは、エポックがＴ＋２に進む前に完了する必要がある。エポックＴ＋２では、Ｔ＋１よりも小さいエポックが対応付けられたアドレスを持つポインタが一つでもあれば、システムはそのポインタを持つブロックの書込みを拒否する。また、システムは、生きていない保存ルートを読み出そうとした場合もこれを拒否し、ユーザが維持できるブロックアドレス群を制限する。これらの制約は、正しく行動しているユーザには関係ないが、システムが正しい削除処理を行うために不可欠である。
【００３５】
上記のエポックによる制約を導入し実施することで、削除する際に、除去するアクセス不能の古いブロックを特定することができる一方、ユーザはシステムへの新規データの書込みとアクセス可能なブロックの読出しを継続することができる。
【００３６】
［削除の課題］
［ルート群の決定］
一般的なガーベジコレクションでは、オブジェクトへの到達可否は、通常、実行されるプログラムのグローバルかつアクティブなローカル変数で構成される「ルート群」に関して決定される。“生きているオブジェクト”は、ルート群に直接属しているか、または、グラフのトラバーサルによってルート群から到達できる。プログラム実行時に、ガーベジコレクションはプログラム変数について十分な知識があるため、ルート群の計算は十分に理解される。非特許文献１に開示のストレージシステム等のシステムでは、ルート群には、グローバル変数に該当する生きている保存ルートだけでなく、ユーザがまだ記憶しているアドレスのブロック（プログラミング言語のローカル変数のようなもの）も含まれるため、もっと難しい。上記で述べたように、もしユーザのブロックアドレスを記憶する権利に何の制限もなければ、非特許文献１に開示のストレージシステムでは、ルート群はすべてのブロックで構成されることになる。本発明では、エポックの制約を導入することで、ルート群を限定し、削除を可能にしている。その結果、ルート群は、（１）生きている保存ルート、および（２）ユーザが維持するアドレスのうち、エポックの制約により現在または前回のエポックのみを持つ、書込みに適したアドレス、のみを含む。
【００３７】
［重複排除の影響］
削除処理によってストレージの消費が増加することを避けるために、削除処理中は重複排除を不能にするという解決策は取らない。その結果、削除されるはずのブロックを重複排除の副次的結果として復活させることができる。このようなブロックを保存することは、この削除アルゴリズムにおける根本的な課題である。
【００３８】
［分散］
分散型ストレージシステムでは、ノードの追加、除去、障害によってノード構成が変わることがよくある。その結果、システム内でのデータ分散も変わってくる。削除アルゴリズムは、場所の変化にかかわらず必要なデータやメタデータを探せなくてはならない。
【００３９】
ここまでは、非特許文献１に開示のストレージシステムにおけるユーザから見たブロックについて述べてきたが、削除処理が機能する内部データ組織は、ユーザから見えるものとは実質的に異なる。
【００４０】
非特許文献１に開示のストレージシステムの内部は「スーパーノード」で構成されている。各スーパーノードは、対応するハッシュスペースの先頭部分で特定される。スーパーノードのハッシュスペースは、互いに連結されておらず、ハッシュスペース全体をカバーしている。各スーパーノードは、当該スーパーノードのハッシュスペースに属する自身のコンテンツに基づいたハッシュ値を有する、ユーザが書込みまたは読出しを行うブロックによる。スーパーノード自身は、固定数の「ピア」に分割される。書込みの際、ブロックには削除符号が付けられ、結果として生じる複数の「フラグメント」がピアに分配される。ピアは、受信したフラグメントを、各ピア毎に異なるフラグメントコンテナに加える。ピア自身は通常、物理的な装置を介して分散されることで、ノード障害に対する回復力を提供する。
【００４１】
削除アルゴリズムは、１つのブロックから生じる全てのフラグメントを保存するかまたは除去するかについて一貫した決定を下す必要がある。
【００４２】
［障害耐性］
削除処理は、ほどほどの数のノードやディスクの障害があっても進められるものでなければならない。さらに、削除は、断続的なネットワーク障害により一時的に利用不能だが、また後で再現するノードにも対応する必要がある。特に、削除アルゴリズムは、既に死んだ装置に関連して発見された論理的に除去されたブロックのフラグメントを、まだ生きているものと区別できなければならない。
【００４３】
［物理的リソースの利用］
非特許文献１に開示のストレージシステムは永続的なストレージであるため、フラグメントがディスク上に維持されることは明白である。特に、ポインタで参照されたブロックのアドレスを親ブロックから検索するには、少なくとも１回のディスクアクセスが必要である。削除アルゴリズムは、ディスク、メモリ、およびネットワークのアクセスパターンを考慮して、これらのリソースを効果的に利用する必要がある。
【００４４】
［削除アルゴリズム］
［概要］
非特許文献１に開示のストレージシステムは、十分に知られている参照数カウント方法の技術を使用している。各ブロックは、カウンタ主を参照する他のブロックの数を追跡する参照カウンタを持つ。ただし、新たなブロックが書き込まれても、参照されたブロックのカウンタはすぐには変更されない。このような即時更新は、システム内のあらゆる場所に配置されているすべての子ブロックにランダムなＩ／Ｏが発生する可能性があるため、非常にコストがかかると思われる。その代わりに、参照カウンタは、バックグラウンド削除処理の実行により周期的に更新される。
【００４５】
ブロックのカウンタは永続的なものであり、ブロックのフラグメントを格納する全てのピアに複製される。全てのフラグメントについて、削除中のカウンタには２つのバージョンがある。永続性のある有効なものと、削除アルゴリズムの部分的な結果を格納するために用いられる一時的なものである。ピアに障害が発生した場合、一時的なカウンタは破棄することができ、永続的なカウンタに何ら害は及ばない。
【００４６】
削除処理には、周期的に実行される次の２つのフェーズがある。まず、「ガーベジ識別（garbage identification）」のフェーズで、新たなカウンタ値が計算される。この後に、「領域解放（space reclamation）」のフェーズがあり、ここでは最初のフェーズで識別されたガーベジを取り除くことで、ストレージの記憶領域（スペース）を再利用できるようにする。上記で述べたように、補助記憶装置では直ちに記憶領域を再利用する必要がないため、このように２つのフェーズに分けることができる。さらに、ガーベジ識別と領域解放とを平行して進めると、重複書込みによって必要となる特別な処理があるため、前者の期間が長くなる。その場合、書込みを重複と認識するために、システムは、どのピアでもブロックの再利用が開始されていないことを確認しなければならず、それを行うためには重複書込みと物理的再利用とを同期させる必要がある。
【００４７】
以下では、削除処理による「ガーベジ識別フェーズ」についてのみ説明する。このフェーズを実行する毎に、ある時点までの書込みブロックのカウンタを計算する。図２に示すように、実行が開始されると、ブロックは連結していない３つのクラスに分類される。第１クラスには、成功した前回の削除が開始される前に書き込まれたブロックが含まれる。これを「完了ブロック（done blocks）」という。第２クラスには、それより後で、かつ今回の削除が開始される前に書き込まれたブロックが含まれ、これを「処理対象ブロック（to-do blocks）」という。また、今回の削除が開始された後に書き込まれたブロックを「新規ブロック（new blocks）」といい、これは第３クラスに分類される。
【００４８】
処理対象ブロックは、処理対象ブロックと完了ブロックとの両方に対する未処理の参照を反映して、今回の削除処理で処理される。そのため、カウンタがインクリメントおよびデクリメントする完了ブロックまたは処理対象ブロックがある。新規ブロックは、今回の削除処理の実行では処理されないため、現時点では他のブロックカウンタの値に影響を与えることはない。この影響は次回の削除実行時に計算される。特に、新規の削除ルートはすべて、今回の削除には何の影響も与えない。次の削除が終了するまで、すべての新規ブロックは単に保存され、そのカウンタは特別な「初期値」に設定される。
【００４９】
次回の削除実行時には、そのときの処理対象ブロックとなる新規ブロックのみが処理される。つまり、カウンタの更新処理がインクリメントする。
【００５０】
削除処理の実行は、いずれのスーパーノードにおいても、ピアのサブセットにより同期して実施されるよう、複数のサブフェーズで進められる。
【００５１】
まず、すべてのスーパーノードで削除処理アルゴリズムの当初の参加者を選択する。この計算には、データの状態が良好なピアしか関与できない。例えば、ポインタを持つすべてのブロックがそのピアの現在位置にいなければ、ピアは削除アルゴリズムの各ステップを実施できない。選択されたピアを「良好なピア」と言い、各々が同一のタスクを実施してガーベジブロックを識別する。つまり、削除計算はかなりの冗長性を持つ。残りのピアは、削除アルゴリズムではアイドル状態にあり、削除が終了した後、バックグラウンドで他のピアから最終カウンタを受信する。
【００５２】
次に、他のブロックをポインタで参照しているすべての処理対象ブロックを読み込む。このポインタは分散され、対象となるブロックのカウンタをインクリメントする。インクリメントする際、初期値を「０」として扱う。
【００５３】
インクリメントしたら、デクリメントを開始するブロックを特定する必要がある。これには、一致する削除ルートがある保存ルート、およびカウンタがインクリメントしなかった通常の処理対象ブロックが含まれる（今のところ、これらを指す新規ブロックはないものとする）。これらのブロックのカウンタを０に変更する。
【００５４】
このように識別されたガーベジから出ているポインタはすべて、これらのガーベジが指すブロックのカウンタをデクリメントさせる。ただし、デクリメントすることにより、カウンタが０になるブロックが出てくる可能性がある。そのため、再度新たなガーベジを識別することもあり、新たなガーベジがみつからなくなるまでデクリメントを繰り返す。
【００５５】
新たなカウンタへの切替えは２段階のコミットで行う。これについては後ほど説明する。コミット後、ガーベジブロックは読出し不能となり、これらが占有していた記憶領域はバックグラウンドで再利用される。
【００５６】
ピアに障害が発生すれば、良好なピアが減少する。いずれかのスーパーノードで良好なピアの数が構成可能な最小限の数を下回った場合、削除プロセス全体が中断され、部分的な結果は破棄される。
【００５７】
上記の削除処理は、新たな書込みがなければスムーズに機能する。新たな書込みがある場合は非常に複雑な問題が生じる。これについては次に述べる。
【００５８】
［複雑な問題］
図３（ａ）は、削除処理開始の直前にブロックＡが書き込まれ、当該ブロックＡを指す保存ルートＲが、その時点の直後に書き込まれた場合を示す。これについて検討する。ここで、ブロックＡは新規のルートＲ以外にはどこからも指されていないため、識別プロセスでは対象とならなかった。その結果、ブロックＡは誤って排除される。なお、図３（ａ）は、削除開始後にブロックＡに対して保存ルートが書き込まれた場合を示すが、ブロックＡは削除してはならない。
【００５９】
この問題を解決するために、上述したエポックの制約を利用する。ユーザは前回のエポックより古いアドレスを保持できない。そのため、エポックを２段階で進めて、１回目と２回目に進んだエポックの間に書き込まれたブロックのインクリメントを送信すればよい。これを図４に示す。ただし、これらのブロックからデクリメントは送信しない。その理由は、新規ブロックを排除する可能性があるため、新規ブロックは無条件で保存するという前提に反するからである。したがって、図４に示すように、常にエポックを１前進させ次の世代にシフトする。
【００６０】
２回目のエポックの前進により、削除開始前に取得したブロックＡのアドレスはユーザによって破棄されるため、ブロックＡに対する新たな参照は作成されない。ブロックＡを参照することができる新規ブロックは、１回目と２回目のエポックの前進の間に書き込まれたブロックだけである。しかし、厳密に言うと、これらのブロックから追加のインクリメントが送信されている。
【００６１】
次の問題は重複排除によるもので、これを図３（ｂ）に示す。今回の削除開始時にどのブロックからも指されていない処理対象ブロックＡについて検討する。ユーザが、重複するブロックＡを書込み、その後、当該ブロックＡを指すルートＲを書き込んだ場合、どちらも保存しなければならない。しかし、ブロックＡは他の処理対象ブロックからも古いブロックからも指されてないため、削除処理ではガーベジとして識別される。ブロックＡを除去するのは間違いであり、データを失うことになる。
【００６２】
この問題を解決するために、重複する書込みのベースブロックは、書込みの際にいわゆる「非削除マーカー（undelete marker）」を設定して、今回の削除プロセスでは除去不能とマークする。除去されそうになって（つまり、新たに計算されたカウンタが０）非削除マーカーが設定されたブロックは常に、削除完了時にカウンタを初期値に戻すことでそのブロックを保存する。削除進行中でなければ、重複する書込みにマーカーは設定されない。
【００６３】
新たなカウンタ値がすべて計算されたら、新たな非削除マーカーが重複する書込みに設定されることはない。非削除マーカーの書き込みを続けると、マーカーの設定と、それを使ってカウンタを初期値に戻す作業が、延々と続いてしまうからである。そのかわりに、いわゆる「ベースブロック・フィルタリング」を用いて、削除される予定のベースブロックに対する書込みを重複として解決しないようにする。ベースブロックの、暫定的だがコミットの準備が整っているカウンタが正の場合、または、非削除マーカーが設定されている場合に限り、書込みを重複排除する。それ以外の場合は、ベースブロックとなる可能性のあるブロックがシステム内に存在する場合でも、全く新しいブロックとして書き込まれる。
【００６４】
削除の実行が完了すると、カウンタ値が初期値に設定された非削除ブロックが存在することがある。次回削除を実行する際には、これらのブロックを本当に維持すべきかどうかを決定する必要がある。これは、必要に応じて追加の再帰的インクリメントによって行う。少なくとも１つの新たな削除処理対象ブロックから指されている非削除ブロックについては、指されたブロックに対して繰り返しインクリメントを送信する。
【００６５】
なお、最後に完了した削除に関連して、非削除ブロックは他の非削除ブロックまたは新規ブロックからのみ参照されることができる。ある非削除ブロックが新規ブロックから指されている場合、その非削除ブロックは上記の再帰的インクリメント処理によって到達される。到達されない非削除ブロックは、今回の削除でガーベジとして識別される。
【００６６】
［詳細」
［削除とエポックの変更］
図４に示すように、１回の削除の実行で、１つのエポック全部および次のエポックの一部について削除を行う。最初のエポックを「準備エポック」といい、ここでは上述したとおり古いエポックのアドレスをユーザが破棄する。次のエポックを「削除マーキングエポック」といい、実際に削除計算を行う。削除の実行の最後が現在のエポックにぶつかる理由はない。エポック前進の操作はシステム内の他の主体によって調整されているため、すべてのユーザが古いアドレスの処分を確認した場合にのみ次の前進が実施される。
【００６７】
［カウンタのインクリメント］
エポックが２回前進して良好なピアが選択されると、処理対象ブロックに基づくバッチインクリメントが開始される（ソースのインクリメントは図４参照）。ポインタを持つ処理対象ブロック内のブロックのアドレスを良好なピアが読み出し、対のアドレス（source_address, destination_address）が送信先アドレスに関与するスーパーノードの良好なピアに向けて送られる。送信先である良好なピアは、メッセージを受信しても対象のブロックのカウンタをインクリメントしない。その理由は２つある。まず、メッセージはネットワークを介して複製されうるため、複数回にわたってカウンタがインクリメントされる可能性がある。さらに、ランダムなブロックに何度もアクセスして一つずつインクリメントするのは効率が悪い。その代わりに、受信したポインタをすべてローカルストレージに一時的に保存し、その後、読み出して固有のものとし、バッチ処理で仮のカウンタに適用する。
【００６８】
バッチでのインクリメントの後、システムはカウンタがインクリメントされたブロックで削除されていないものをみつけて、上述した再帰的インクリメントを行う。
【００６９】
インクリメントが完了した時点で、（保存ルートまたは削除ルートではなく）通常の処理対象ブロックの中に、初期値設定のままになっているもの、つまり新たなポインタによって参照されていないブロックが含まれている場合がある。これらのブロックはすべて、以下に述べるデクリメントアルゴリズムに追加的に入力される。
【００７０】
［カウンタのデクリメント］
カウンタのデクリメントは最初に特定されたガーベジのルートから開始し、上述したように、新たなガーベジがみつからなくなるまで繰り返し行う。１回のデクリメントの分散と実際のデクリメントは、インクリメントとほぼ同様に機能する、カウンタ値を増加するのではなく減少する点が異なる。
【００７１】
［新たなカウンタのコミット］
最後のデクリメントが終了したら、計算したカウンタが等しいかどうかをスーパーノードごとに検証する。カウンタが一致しないスーパーノードがあれば、それはソフトウェアの障害を意味する。不一致がみつかった場合、削除プロセスは中断される。検証に成功したら、仮のカウンタを永久的なものにすることによって、システムで使用できる準備が整う。良好なピアは適切なコミットフェーズに入ることを決定し、コミットフェーズでシステムは新たなカウンタをスタートする。この時点から、障害後に再起動された各ノードがカウンタコミットを完了させる。切り替えはすべてのフラグメントのコンテナのメタデータを交換するだけなので、切り替え自体に時間はかからない。
【００７２】
［非削除マーカーの組織と取扱い］
上述のとおり、重複する書込みが削除処理中に発生すると、各良好なピアにおいて特別な非削除マーカーを書き込む必要が生じる。非削除マーカーは新規ブロックには設定されない。なぜなら新規ブロックは今回の削除の実行では決して削除されないからである。
【００７３】
デクリメントの後、新たなカウンタ値が０で非削除マーカーが設定されたブロックについては、カウンタを初期値にリセットすることでガーベジとして扱われなくなる。
【００７４】
ブロック書込みの一部としての重複排除は基本的なオペレーションであり、その性能はシステム全体の性能にとって重大である。そのため、非削除マーカーを設定することは非常に効率的である。これは、非削除マーカーを良好なピアのメモリにビットマップとして保存しておくことで達成される。すべてのスーパーノードに十分な良好なピアがある限り削除が進められるため、これは安全である。
【００７５】
［ベースブロックフィルタリング処理］
コミットが開始されると、非削除マーカーの書込みは行われない。そのかわりに、書込み中に特定されたベースブロックとなる可能性のあるすべてのブロックについては、今回の削除で削除されないことを確認する。これは、すべての良好なピアに対するクエリーで行うことができる。ピアの回答が肯定になるのは、このブロックに対して非削除マーカーが設定されている場合、または、最近計算されて仮のままになっているこのブロックのカウンタが正の値の場合のみである。回答が肯定だった場合は重複排除を行い、そうでない場合は新規ブロックが書き込まれる。
【００７６】
すべての良好なピアから回答を受信したら、収集したすべての回答の論理的結合として最終回答を計算する。その理由は、ベースブロックとなる可能性があるブロックが今回の削除実行終了後に保存されているためには、すべての良好なピアの回答が肯定でなければならないからである。一部の回答には一貫性がない場合がある。なぜなら、以前に発行された非削除マーカーの書込みでは、いくつかの良好なピアにのみ設定された非削除マーカーを残すのに失敗することもあるからだ。
【００７７】
［カウンタに対する非削除マーカーの適用］
非削除マーカーに関して一貫性のなさが発見されたら、スーパーノード内のすべての良好なピアから集めたビットに論理的結合を適用して一貫性を持たせ、その結果をすべての良好なピアに戻す。その後、非削除マーカーが設定され計算されたカウンタ値が最終値の０と等しい各ブロックについて、このカウンタ値を初期値の０に変更する。
【００７８】
［記憶領域再利用の概要］
ガーベジ識別の結果、ブロックカウンタがゼロになるものがある。このようなブロックはもう読み出すことはできないが、ストレージのリソースを占有し続ける。このリソースを再利用するには、このブロックのフラグメントが格納されたすべてのコンテナをリライトする必要があり、これは大変重い動作である。不要な重い作業を避けるために、ストレージリソースは、それが必要になった場合または再利用を行うフリーサイクルがあるときに、再利用される。できるだけ早くなるべく多くのストレージリソースを再利用するためには、除去するフラグメントの割合が最も高いコンテナを優先する。
【００７９】
［削除正確性分析］
上述した削除処理が正確であること、つまり上記で定義したルート群から到達できるブロックを除去しないこと、について述べる。理想的には、ガーベジコレクションによってルート群から到達できないすべてのブロックを除去できることも示したい。しかし、ユーザはいかなる時点でもメモリからブロックのアドレスを削除できるため、それらのブロックは今回のルート群からは除外する。例えば、ユーザが全く新しい通常ブロックを書き込むことができる一方、ガーベジ識別が進められ、このブロックのアドレスは直ちに忘れられる。それでも、そのアドレスで参照されるブロックはルート群からは到達できないが除去されない。したがって、削除によって大きく分類されたブロックを除去することのみを証明する。以下に、主題を証明するのに有効な補題を述べる。
【００８０】
［補題５．１］システムエポックＴ−１に書き込まれた保存ルートから到達できる、エポックＴ−２に関連付けられたアドレスを持つブロックは、エポックＴにて終了する削除の実行では保存される。
【００８１】
［証明］上述したように、Ｔ−１に書き込まれた保持ルートからインクリメントが送信され、その保持ルートから到達できるすべてのブロック、特にエポックＴ−２の特定のブロックに伝播する。
【００８２】
ここで、主張を証明する上で役立つ用語を導入する。１回目の前進から削除実行が終了するまでのガーベジ識別中に実行された、読出し、書込み、および取得アドレスを忘れる等のユーザの動作を検討する。これらの動作の数は有限であり、ある順序にしたがって行われる。これらに連続する自然数を割り当てるとする。順序を定めたら、書込みが有効なアドレスに対して制限のあるユーザによって記憶される一連のアドレスのシークエンスは、数１式のように表わされる。つまり、エポックＴでは、ユーザはエポックＴ−２またはそれ以前のアドレスを維持しないものとする。さらに、１回目の前進の生きている保存ルートから成る群のパラレルシークエンス数２式を定義する。Ｒｉ群は１回目の前進の後に新たに書き込まれた各ルートによって変化する。１回目の前進の後に書き込まれた削除ルートはここでは考慮しない。その理由は、今回の削除実行に何ら影響を与えないからである。数３式で、Ｕｉを改変する動作は通常ブロックの書込み、あらゆるタイプのブロックの読出し、および維持していたアドレスを忘れることである。Ｒｉを改変する動作は保持ルートの書込みである。いずれの動作も、これらの群の１つだけを変化させる。
【数１】
0005382227.tif 000002
【数２】
0005382227.tif 000003
【数３】
0005382227.tif 000004
【００８３】
なお、ｉ番目のとき、Ｕｉのあらゆるメンバーは読出可能である。削除手続きの正確さを証明するためには、Ｓｎから到達できるすべてのブロックが保存されていることを示せばよい。これについては更に強力な命題を提示する。
【００８４】
［定理５．２］（正確性プロパティ）  以下に示すＳｉ群のメンバーはエポックＴにおいて終了した削除実行によって保存される。
１．Ｒｉに属するすべての保存ルート。
２．Ｔ−１またはＴに等しい、対応付けされたエポックのＵｉに含まれるすべてのアドレス。
３．Ｒｎからのいずれかの保存ルートにより参照されている場合、エポックＴ−２におけるＵｉに含まれるアドレス。
４．（１）、（２）、（３）から到達できるすべてのブロック。
【００８５】
［証明］。数学的帰納法によって証明を進める。
基礎：Ｓ０はＴ−２の生きている保持ルートとアドレスしか含有できない。これらの保持ルートから到達できるブロックは削除処理によって除去されない。なぜなら適用される参照カウントの自然の特性だからである。Ｔ−２からのアドレスは、補題５．１による命題を満足させる。
【００８６】
帰納ステップ：Ｓｉがこの命題を満足させるとすると、次のいずれか１つの動作の結果、ＳｉからＳｉ＋１が生成される。（１）忘れられたアドレスを除去することでＳｉ＋１に命題を自明に満足させる。（２）Ｒｉに属する保存ルートから読み出したアドレスを追加する。読み出されたアドレスは帰納仮説によって命題を満足させる。（３）ＵｉからのエポックＴ−２のポインタを持つブロックから読み出されたアドレスを追加する。読み出されるアドレスはエポックＴ−２からのものであり（図１参照）、［補題５．１］によってＲｎからの保持ルートから到達可能な場合は保存される。（４）ＵｉからのエポックＴ−１またはＴのポインタを持つ、ブロックから読み出されたアドレスを追加する。読み出されたアドレスはＵｉから到達可能でエポックＴ−１またはＴにあるため、帰納仮説によって保存される。（５）ポインタのない通常ブロックを書き込むことによって取得したアドレスを追加する。取得したアドレスはエポックＴ−１またはＴからのものとなる。このブロックが重複排除されていない場合、今回のガーベジ識別では削除されない。そうでない場合、非削除マーカーが設定されるか、またはベースブロックフィルタリングによって削除実行が終了した後にブロックが生きていることを確認する。どちらも、このベースブロックが今回の削除によって削除されないことを確実にする。
【００８７】
（６）ポインタを持つブロックを書き込むことで取得したアドレスを追加する。ただし、挿入したアドレスの少なくとも１つはエポックＴ−２からのものである。図１で述べた、いわゆる「ミニマムルール」により、このような戻りアドレスはエポックＴ−２に対応付けられ、［補題５．１］により条件付きで保存される。（７）ポインタ付きのブロックを書き込むことで取得されるアドレスを追加する。挿入されるアドレスはすべてエポックＴ−１またはＴのものである。ここでも、このブロックが重複排除されていない場合、今回の削除では除去されない。この書込みが重複として解決された場合、ベースブロックは（５）と同様に保存される。参照されるブロックはＵｉに含まれるため、帰納仮説によって保存される。（８）システムのエポックＴ−１の間に保持ルートを書き込んでＲｉを拡張する。この保持ルートから読み出せるブロックについては、インクリメントのプロセスでカバーされているため、保存される。（９）システムのエポックＴの間に保持ルートを書き込んでＲｉを拡張する。この保持ルートには、帰納仮説によって保存されるＵｉからの、Ｔ−１およびＴからの挿入アドレスのみが含まれる。
【００８８】
ここで、削除によって除去されるブロックのクラスを定義する。
［定理５．３］（非空虚プロパティ）
削除の実行では、削除開始前に書き込まれ、かつ同時に以下の状態であるものをガーベジブロックと識別する。
１．削除開始前に生きているいかなる保存ルートからも到達できず、
２．１回目および２回目の前進の前に書き込まれたいかなる保持ルートからも到達できず、
３．今回の実行中の重複排除でベースブロックとして使用されない。
【００８９】
［証明］インクリメントとデクリメントとの境界の設定から、これらのブロックはカウンタ計算が０となる。削除処理中に行われる重複排除で、もしこれらのブロックがベースブロックとして使用されなかった場合、０カウンタは有効となり、これらのブロックは除去される。
【００９０】
［削除要件の対処］
削除アルゴリズムは、上述したあらゆる用件を満たす。このアルゴリズムは先に説明したように、十分に定義されたブロックの生存判断ロジック（semantics）を特徴として持つ。“生きているブロック”はすべて保存され、“死んだブロック”はほぼ削除される。削除アルゴリズムは保守的なものであるため、ガーベジブロックの可能性があるものでもシステムによって一時的に維持される場合もある。しかし、これらのブロックは次回の削除処理までの間、維持されるだけであり、次回の削除処理でガーベジとして識別される。
【００９１】
クライアントは、削除処理実行中でも、途切れることなくシステムへの書込みができる。これは、上述したエポック制約のおかげである。非削除マーカーという軽量のメカニズムにより、削除実行中でも、良好な重複排除の効果と書込性能を実現できる。
【００９２】
以下で述べる性能評価では、ユーザから見た全体的なシステム性能において、削除処理が極めて限定的な性能低下しかもたらさないことを示している。これは、以下のような設計での決定による。すなわち、（１）領域解放と参照カウンタの更新を遅延させる、（２）仮のカウンタに対するインクリメントとデクリメントの効果的な分散およびその適用をバッチで行う、（３）最も高い割合でスペースが得られるコンテナから、領域解放を開始する、および（４）良好なピアのメモリに非削除マーカーを保持する、という点である。
【００９３】
削除計算が複数のスーパーノードに分散されることから、削除アルゴリズムの拡張性は、システム全体の拡張性に類似する。削除処理は、ユーザによる書込みと読出しのためのデータ配置に対処するのと同様に、内部ＤＨＴを用いてシステムの動的性質に対処する。
【００９４】
削除処理はピアの障害に耐性を持つ。ピアでの計算に冗長性があるため、ガーベジ識別処理を途中で停止することはほとんどない。各スーパーノードに十分な数の良好なピアがある限り、識別処理を継続する。上記で述べたカウンタの検証は、最も有害なソフトウェアの障害から削除処理を保護するものである。
【００９５】
［性能評価］
別段の記載がない限り、実験はすべて４つのストレージノード（ＳＮ）、２つのアクセスノード（ＡＮ）からなるコンテンツアドレスストレージシステムを使用している。すべてのサーバはＲｅｄＨａｔＥＬ５．３Ｌｉｎｕｘを実行し、２ＱｕａｄＣｏｒｅの３ＧＨｚのＣＰＵと、４ＧｉｇＥカードを搭載している。各ＳＮは、２４ＧＢのＲＡＭと、１２台の１ＴＢのＳＡＴＡディスクを搭載し、各ＡＮは８ＧＢのＲＡＭと限られたローカルストレージを搭載している。
【００９６】
実験は、３３％圧縮可能な平均ブロックサイズ６４ＫＢで実施した。データブロックは、９つのオリジナルと、３つの冗長フラグメントとして書き込まれ、３つの障害に対する耐性を有する。別段の記載がない限り、デフォルトリソース分割ポリシを使用し、全ての実験において、ユーザの動作（書込みと読出し）に７０％、削除関連のタスクに３０％のシステムリソースを使用した。
【００９７】
［書込み／読出し帯域幅］
この実験は、ガーベジ識別がユーザの書込み／読出し性能に与える影響を測定するものである。３つのグループからそれぞれ５つの値、計１５のデータポイントを、重複排除率０％から１００％まで２５％ごとに集計した。各グループにおける最初の測定は、削除を実行していない状態での特定の重複排除率での書込み帯域幅の測定である。２番目と３番目のデータポイントは同様のベースシナリオで集計した。まず、空のシステムに４ＴＢの非重複データを入力し、削除を実行してブロックのカウンタを計算した。次に、４００ＧＢの新規データをロードし、４００ＧＢの既存データを削除した。これらの２つのデータポイントの違いは、使用したリソース分散ポリシである。２番目のデータポイントは書込みに１００％使用するリソース分割ポリシを用いたが、３番目のデータポイントはリソースの３０％を削除処理に向けるデフォルトリソース分割ポリシを用いた。
【００９８】
読取りについては同様の実験を３回行ったが、書込みデータの代わりに、最初にロードしたデータの連続するいくつかのフラグメントを読み出すテストを行った。２つのＡＮを利用し、各実験で多数のストリームを書き込んでクライアント側がボトルネックにならないかどうかを確認した。
【００９９】
図５にその結果を示す。図５を見ると、非常に重複しているストリームで書込みの帯域幅が最も激しく落ちていることがわかる。その場合、ＣＰＵがボトルネックであり、ガーベジ識別プロセスは、例えば非削除マーカーの書込みのためにかなりのＣＰＵサイクルを必要とする。重複排除がもっと少ないストリームの場合は、書込み性能は設定されたリソース分配ポリシと一致する。
【０１００】
削除処理が読出しに与える影響は、書込みに与える影響よりも少ない。その理由は、本発明におけるストレージシステムの読出し手続きは帯域幅を犠牲にして読出しレイテンシを短くしているため、読出し時はＣＰＵとディスクリソースをフルに利用しないからである。その結果、削除のニーズは読出しレイテンシに大きな影響を与えることなく受け入れられる。
【０１０１】
［ガーベジ識別時間］
上記の実験を行う一方、さらにガーベジ識別の時間を測定した。デフォルトのリソース分割ポリシの場合の結果を図６に示す。２回目の削除実行時のガーベジ識別時間を測定した。
【０１０２】
削除時間については、ディスクがボトルネックになる。ディスクは非重複書込みによって集中的に使用されるため、そのような書込みがある場合に削除時間が最も長くなる。読出し中は、読出しレイテンシが短いため全てのディスクが使われることはない。その結果、読出し中の削除時間は短い。削除が最もＣＰＵサイクルを必要とするのは、重複する書込みのために非削除マーカーを設定するときである。デフォルトのリソース分割ポリシでは削除に十分なＣＰＵサイクルが当てられるが、その結果、上記で説明したように書込み性能が低下する。
【０１０３】
［領域解放］
領域解放の時間を測定した５回の実験の各々において、５００ＧＢのデータを書き込み、その内の５０ＧＢを削除したが、再利用を終了させるには多様な分量のデータをリライトする必要がある。図７（ａ）は領域解放にかかる時間とリライトするデータ量とがほぼ線形の関係にあることを示している。これは、領域解放にかかる時間が、カウンタが０のブロックを保持するコンテナの数と比例するからである。上述したように、領域解放の際にはこのようなブロックを持つコンテナをリライトしなければならない。コンテナのリライトは重いオペレーションであるため、予想されるように、リライトするコンテナが多いほど領域解放にかかる時間が長くなる。
【０１０４】
［削除の拡張性］
１〜４個のＳＮを使って削除の拡張性を調べる実験を行った。システムに４ＭＢの非重複データを入力し、そのうちの５％を除去するようマークして削除を開始した。図７（ｂ）は、２つのノードでのガーベジ識別は単一のノードの場合に比べて約２倍の速度であることを示している。３つ以上に増やせばこのフェーズをほぼ線状に短縮できるが、傾斜は緩やかになる。ノードの数が増えても削除処理で行われる作業は変わらず、全てのノード間で分散されるため、ノードの数が増えれば削除にかかる時間が短くなる。
【０１０５】
［ノード障害後の削除性能］
ノード障害が識別時間に与える影響を測定する実験を３回行った。各実験は、当初４つのＳＮを使い、２ＴＢの非重複データをシステムに入力して、その５％を除去するようマークした。１回目の実験ではガーベジ識別のみを行った。２回目の実験では、１つのＳＮをシャットダウンし、ガーベジ識別を開始して、良好なピアが選択されてシャットダウンしたＳＮが再起動するのを待った。３回目の実験では、ガーベジ識別を開始する直前に１つのＳＮをシャットダウンした。各実験で、良好なピアを選択する時点からガーベジ識別が終了する時点までの時間を測定した。
【０１０６】
その結果を図８に示す。２番目の時間が長いのは、良好なピアが選択された後にＳＮの１つが再起動されており、このノードがガーベジ識別に参加しなかったためである。そのため、識別中に行う作業が４つではなく３つのＳＮ間で分けられた。３番目の時間は２番目よりもさらに長い。その理由は、データの再構築に必要なバックグラウンドのタスクが、ガーベジ識別処理全体に渡って実行されていたからである。なお、識別の最中に障害が発生した場合、その処理は何とか終了までたどり着く。その時間は３番目の実験でかかった期間より長くはならない。
【０１０７】
［関連技術］
本発明における削除処理は、よく知られている動的データ構造を持つプログラミング言語における並行ガーベジコレクション（非特許文献２，３）に類似する点もあるが、大きく異なる点がある。また、本発明における削除は、コンテンツアドレスストレージシステムの重複排除機能、拡張性、および障害耐性によって、より複雑になっている一方で、プログラミング言語のガーベジコレクションとは異なりブロックのグラフが非循環でなければならないため、削除が簡易になっている。
【０１０８】
本発明における削除は、遅延参照カウント（非特許文献２）に基づいている。マーク・アンド・スイープ（非特許文献４）を用いて削除を行うこともできたが、削除処理毎にすべてのデータをトラバースすることを避けるために、この方法は取らなかった。グループ化されたマーク・アンド・スイープ（非特許文献５）はこの問題に対処しており、バックアップをグループ分けして前回アルゴリズムが実行された後で削除されたファイルを含むグループのオブジェクトを含むコンテナのみをスイープする。バックアップデータの重複排除率は高いため、古いバックアップを１つ除去すると、再利用されるデータはほとんどないかもしれないが共有データを持つ多くのコンテナをスイープすることになる可能性がある。しかし、参照カウント方式の場合、その心配はない。
【０１０９】
本発明における非削除マーカーは、三色のマーク・アンド・スイープ（非特許文献２）で読出しの際に白のオブジェクトをグレーにするのと、ある意味で類似する。
【０１１０】
重複排除がなければ、分散型ストレージシステムにおける削除は比較的簡単で、Ｇｌａｃｉｅｒ（非特許文献６）のようにリースで行うこともできれば、ＵｒｓａＭｉｎｏｒ（非特許文献７）のように簡易な旧バージョンの再利用で行うこともできる。しかし、重複排除がある場合は、前述の理由により難しくなる。例えば、Ｖｅｎｔｉ（非特許文献８）、ＤｅｅｐＳｔｏｒｅ（非特許文献９）、ＳｐａｒｓｅＩｎｄｅｘｉｎｇ（非特許文献１０）は削除を実行していない。他のクラスのシステムはストレージユニットに対してガーベジコレクションを行っているが、通常のオペレーションに影響を与えている。ＭＡＤ２（非特許文献１１）は指紋を参照カウントしているが、物理的な削除期間中は関連するすべてのタンカーをフリーズさせている。ＤＤＥ（非特許文献１２）はクライアントが保有するすべてのデータのロックを無効にして参照されるブロックを開放する。バックグラウンドでのｄｅｄｕｐｖ１（非特許文献１３，１４）は、非参照ブロックを「ガーベジコレクション候補」としてマークするが、システムがアイドルの場合にのみこれらのブロックを除去する。これ以外の技術として、ＳＩＳ（非特許文献１５）とＦＡＲＳＩＴＥ（非特許文献１６）ではバックポインタ（参照リスト）を使用し、ＤｅＤｅ（非特許文献１７）は帯域外の更新されたグローバルハッシュインデックスの一部を排他的にスキャンするときに使用しないブロックを回収する。
【０１１１】
ＤａｔａＤｏｍａｉｎ（特許文献１，２，非特許文献１８）は、インライン重複排除を行う集中型のシステムでガーベジコレクションを提供する。除去するブロックはＢｌｏｏｍフィルタを使用して選択するため、結果としてシステム内に多少のガーベジが残る。ＥＭＣ  Ｃｅｎｔｒａ（特許文献３，非特許文献１９，２０）はコンテンツユニットを明示的に削除するが、削除と重複排除をどのように並列に行うかについては述べていない。ＥｘｔｒｅｍｅＢｉｎｎｉｎｇ（非特許文献２１）は、ビン内で重複排除をローカライズし、これによりガーベジコレクションが簡単になると述べているが、詳細は説明されていない。
【０１１２】
［結論と今後の研究］
重複排除機能を持つ拡張性のあるストレージのための削除アルゴリズムについて述べた。この削除処理は、商用システムであるコンテンツアドレス型のストレージシステムに既に実装されている。このアルゴリズムは無停止、つまり削除処理中でもユーザによる書込みと読出しを継続できるものである。さらに、高度のアベイラビィティ、ユーザのオペレーションに関する性能への影響が低いこと、複数のディスク、ノード、またはネットワークの障害に対する耐性、システムの成長に合わせた構成の変化への適応等、重要な機能に関する要件にも対応している。削除が全体的なパフォーマンスに与える影響は、計算力またはディスク容量を変更するという観点から無理なく調整できる。
【０１１３】
また、古いデータと新たに書き込まれたデータとの間に境界を作るエポックのメカニズムによって、静止点をとり、カウンタ計算中も読み書きできるため、継続的なアベイラビリティが実現できる。したがって、現行のバックアップは、バックグラウンドで実行される削除処理の影響を受けない。実際のところ、無停止削除処理のための明確な意味論を定義する上でエポックの導入は不可欠である。
【０１１４】
一方、削除動作はバッチで行われてネットワーク全体に分散されるため、性能への影響は小さい。重要な点は、非削除マーカーがメインメモリに保存されるため、ユーザの書込みに対応するマーカーのオーバーヘッドが小さいことである。
【０１１５】
障害耐性は、良好なピアに対応付けられる計算の冗長性により実現される。選択されたピアが重要な計算を冗長的に行うため、そのいくつかがクラッシュした場合でも削除処理を進めることができる。また、良好なピアは削除処理の拡張性にも関与し、システム規模に応じて性能のスケーラビリティを確保することができる。削除の拡張性は、削除動作を各スーパーノードと対応付けることにより、集中的なコンポーネントなしで実現される。
【０１１６】
現在、削除は完全に機能しているが、エンドユーザのために重要な特長をさらに改良することができると思われる。削除手続きはオペレーションを停止させずに行われるため、最も改良が求められるのは性能のさらなる強化である。考えられる改良点の１つは、ポインタを持つブロック用に別のコンテナを導入することである。これにより、カウンタをインクリメントするフェーズが高速化されると思われる。性能の向上以外では、今後の研究を行う上での方向性として、中間の削除結果のチェックポイントを設けて削除を再スタートできるようにすることも挙げられる。
【０１１７】
＜実施形態２＞
本発明の第２の実施形態を、図９乃至図２０を参照して説明する。図９は、システム全体の構成を示すブロック図である。図１０は、ストレージシステムの概略を示すブロック図であり、図１１は、構成を示す機能ブロック図である。図１２乃至図２０は、ストレージシステムの動作を説明するための説明図である。
【０１１８】
ここで、本実施形態では、ストレージシステムが、複数台のサーバコンピュータが接続されて構成されている場合を説明する。但し、本発明におけるストレージシステムは、複数台のコンピュータにて構成されることに限定されず、１台のコンピュータで構成されていてもよい。
【０１１９】
図９に示すように、本発明におけるストレージシステム１０は、ネットワークＮを介してバックアップ処理を制御するバックアップシステム１１に接続している。そして、バックアップシステム１１は、ネットワークＮを介して接続されたバックアップ対象装置１２に格納されているバックアップ対象データ（記憶対象データ）を取得し、ストレージシステム１０に対して記憶するよう要求する。これにより、ストレージシステム１０は、記憶要求されたバックアップ対象データをバックアップ用に記憶する。
【０１２０】
そして、図１０に示すように、本実施形態におけるストレージシステム１０は、複数のサーバコンピュータが接続されて構成を採っている。具体的に、ストレージシステム１０は、ストレージシステム１０自体における記憶再生動作を制御するサーバコンピュータであるアクセラレータノード１０Ａと、データを格納する記憶装置を備えたサーバコンピュータであるストレージノード１０Ｂと、を備えている。なお、アクセラレータノード１０Ａの数とストレージノード１０Ｂの数は、図１０に示したものに限定されず、さらに多くの各ノード１０Ａ，１０Ｂが接続されて構成されていてもよい。
【０１２１】
さらに、本実施形態におけるストレージシステム１０は、データを分割及び冗長化し、分散して複数の記憶装置に記憶すると共に、記憶するデータの内容に応じて設定される固有のコンテンツアドレスによって、当該データを格納した格納位置を特定するコンテンツアドレスストレージシステムである。このコンテンツアドレスストレージシステムについては、後に詳述する。
【０１２２】
なお、以下では、ストレージシステム１０が１つのシステムであるとして、当該ストレージシステム１０が備えている構成及び機能を説明する。つまり、以下に説明するストレージシステム１０が有する構成及び機能は、アクセラレータノード１０Ａあるいはストレージノード１０Ｂのいずれに備えられていてもよい。なお、ストレージシステム１０は、図２に示すように、必ずしもアクセラレータノード１０Ａとストレージノード１０Ｂとを備えていることに限定されず、いかなる構成であってもよく、例えば、１台のコンピュータにて構成されていてもよい。さらには、ストレージシステム１０は、コンテンツアドレスストレージシステムであることにも限定されない。
【０１２３】
図１１に、ストレージシステム１０の構成を示す。この図に示すように、ストレージシステム１０は、データを記憶する記憶装置３１と、当該記憶装置３１に対するデータの記憶及び読み出し動作を制御するデータ格納制御部２１と、記憶装置３１に格納されているが既に使用されなくなったデータの記憶領域を解放して再利用可能とするデータ解放制御部２２と、を備えている。なお、実際には、データ格納制御部２１とデータ解放制御部２２とは、図１０に示したアクセラレータノード１０Ａ及びストレージノード１０Ｂが備えているＣＰＵ（Central Processing Unit）などの複数の演算装置にプログラムが組み込まれることで構成されている。また、記憶装置３１は、図１０に示したアクセラレータノード１０Ａ及びストレージノード１０Ｂが備えているハードディスクなどの記憶装置にて構成されている。
【０１２４】
なお、上記プログラムは、例えば、ＣＤ−ＲＯＭなどの記憶媒体に格納された状態でストレージシステム１０に提供される。あるいは、上記プログラムは、ネットワーク上の他のサーバコンピュータの記憶装置に記憶され、当該他のサーバコンピュータからネットワークを介してストレージシステム１０に提供されてもよい。
【０１２５】
以下、上記データ格納制御部２１と上記データ解放制御部２２の構成について詳述する。はじめに、データ格納制御部２１によるコンテンツアドレス方式のデータの記憶及び読み出し方法を、図１２乃至図１４を参照して説明する。
【０１２６】
まず、データ格納制御部２１は、図１３の矢印Ｙ１に示すように、バックアップ対象データＡの入力を受けると、図１２及び図１３の矢印Ｙ２に示すように、当該バックアップ対象データＡを、可変容量（例えば、平均６４ＫＢ）、あるいは、所定容量（例えば、６４ＫＢ）のブロックデータＤに分割する。そして、このブロックデータＤのデータ内容に基づいて、当該データ内容を代表する固有のハッシュ値Ｈ（内容識別情報）を算出する（矢印Ｙ３）。例えば、ハッシュ値Ｈは、予め設定されたハッシュ関数を用いて、ブロックデータＤのデータ内容から算出する。なお、このデータ格納制御部２１による処理は、アクセラレータノード１０Ａにて実行される。
【０１２７】
そして、上記データ格納制御部２１は、バックアップ対象データＡのブロックデータＤのハッシュ値Ｈを用いて、当該ブロックデータＤが既に記憶装置３１に格納されているか否かを調べる。具体的には、まず、既に格納されているブロックデータＤは、そのハッシュ値Ｈと格納位置を表すコンテンツアドレスＣＡが、関連付けてＭＦＩ（Ｍａｉｎ  Ｆｒａｇｍｅｎｔ  Ｉｎｄｅｘ）ファイルに登録されている。従って、データ格納制御部２１は、格納前に算出したブロックデータＤのハッシュ値ＨがＭＦＩファイル内に存在している場合には、既に同一内容のブロックデータＤが格納されていると判断できる（図１３の矢印Ｙ４）。この場合には、格納前のブロックデータＤのハッシュ値Ｈと一致したＭＦＩ内のハッシュ値Ｈに関連付けられているコンテンツアドレスＣＡを、当該ＭＦＩファイルから取得する。そして、このコンテンツアドレスＣＡ（アドレスデータ）を、記憶要求にかかるブロックデータＤのコンテンツアドレスＣＡとして記憶する。あるいは、既に格納されているブロックデータＤを参照するコンテンツアドレスＣＡをさらに参照する他のアドレスデータをツリー構造にて記憶する。これにより、このコンテンツアドレスＣＡにて参照される既に格納されているデータが、記憶要求されたブロックデータＤとして使用されることとなり、当該記憶要求にかかるブロックデータＤは記憶する必要がなくなる。
【０１２８】
また、データ格納制御部２１は、は、上述したように重複チェック部２３にてまだ記憶されていないと判断されたブロックデータＤを圧縮して、図１３の矢印Ｙ５に示すように、複数の所定の容量のフラグメントデータに分割する。例えば、図１２の符号Ｄ１〜Ｄ９に示すように、９つのフラグメントデータ（分割データ４１）に分割する。さらに、データ格納制御部２１は、分割したフラグメントデータのうちいくつかが欠けた場合であっても、元となるブロックデータを復元可能なよう冗長データを生成し、上記分割したフラグメントデータ４１に追加する。例えば、図１２の符号Ｄ１０〜Ｄ１２に示すように、３つのフラグメントデータ（冗長データ４２）を追加する。これにより、９つの分割データ４１と、３つの冗長データとにより構成される１２個のフラグメントデータからなるデータセット４０を生成する。なお、上記データ格納制御部２１による処理は、１つのストレージノード１０Ｂによって実行される。
【０１２９】
そして、データ格納制御部２１は、生成されたデータセットを構成する各フラグメントデータを、記憶装置３１に形成された各記憶領域に、それぞれ分散して格納する。例えば、図１２に示すように、１２個のフラグメントデータＤ１〜Ｄ１２を生成した場合には、１２個の記憶装置３１内にそれぞれ形成したデータ格納ファイルＦ１〜Ｆ１２（データ格納領域）に、各フラグメントデータＤ１〜Ｄ１２を１つずつそれぞれ格納する（図１３の矢印Ｙ６参照）。
【０１３０】
また、データ格納制御部２１は、上述したように記憶装置３１に格納したフラグメントデータＤ１〜Ｄ１２の格納位置、つまり、当該フラグメントデータＤ１〜Ｄ１２にて復元されるブロックデータＤの格納位置を表す、コンテンツアドレスＣＡを生成して管理する。具体的には、格納したブロックデータＤの内容に基づいて算出したハッシュ値Ｈの一部（ショートハッシュ）（例えば、ハッシュ値Ｈの先頭８Ｂ（バイト））と、論理格納位置を表す情報と、を組み合わせて、コンテンツアドレスＣＡを生成する。そして、このコンテンツアドレスＣＡを、ストレージシステム１０内のファイルシステム、つまり、アクセラレータノード１０Ａに返却する（図１３の矢印Ｙ７）。すると、アクセラレータノード１０Ａは、バックアップ対象データのファイル名などの識別情報と、コンテンツアドレスＣＡとを関連付けてファイルシステムで管理する。
【０１３１】
また、データ格納制御部２１は、ブロックデータＤのコンテンツアドレスＣＡと、当該ブロックデータＤのハッシュ値Ｈと、を関連付けて、各ストレージノード１０ＢがＭＦＩファイルにて管理する。このように、上記コンテンツアドレスＣＡは、ファイルを特定する情報やハッシュ値Ｈなどと関連付けられて、アクセラレータノード１０Ａやストレージノード１０Ｂの記憶装置３１に格納される。
【０１３２】
さらに、データ格納制御部２１は、上述したように格納したバックアップ対象データを読み出す制御を行う。例えば、ストレージシステム１０に対して、特定のファイルを指定して読み出し要求があると（図１４の矢印Ｙ１１参照）、まず、ファイルシステムに基づいて、読み出し要求にかかるファイルに対応するハッシュ値の一部であるショートハッシュと論理位置の情報からなるコンテンツアドレスＣＡを指定する（図１４の矢印Ｙ１２参照）。そして、データ格納制御部２１は、コンテンツアドレスＣＡがＭＦＩファイルに登録されているか否かを調べる（図１４の矢印１３参照）。登録されていなければ、要求されたデータは格納されていないため、エラーを返却する。
【０１３３】
一方、読み出し要求にかかるコンテンツアドレスＣＡが登録されている場合には、上記コンテンツアドレスＣＡにて指定される格納位置を特定し、この特定された格納位置に格納されている各フラグメントデータを、読み出し要求されたデータとして読み出す（図１４の矢印Ｙ１４参照）。このとき、各フラグメントが格納されているデータ格納ファイルＦ１〜Ｆ１２と、当該データ格納ファイルのうち１つのフラグメントデータの格納位置が分かれば、同一の格納位置から他のフラグメントデータの格納位置を特定することができる。
【０１３４】
そして、データ格納制御部２１は、読み出し要求に応じて読み出した各フラグメントデータからブロックデータＤを復元する（図１４の矢印Ｙ１５参照）。さらに、データ格納制御部２１は、復元したブロックデータＤを複数連結し、ファイルＡなどの一群のデータに復元して、読み出し制御を行っているアクセラレータノード１０Ａに返却する（図１４の矢印Ｙ１６参照）。
【０１３５】
ここで、データ格納制御部２１は、時系列で区分した時間帯毎に、記憶対象データを上述したように記憶装置３１に記憶する。具体的に、図１５あるいは図１６に示すように、所定の時間が経過する毎に、その時間帯を表す「世代（エポック）」を設定して、新規の記憶対象データの書き込み処理を行う。このとき、記憶装置３１に書き込まれたデータがどの世代で書き込まれたかを区別できるよう、各ブロックデータにその世代を識別する情報を付加して記憶する。あるいは、各ブロックデータに書き込まれた世代の識別情報を対応付けて別途記憶するなどして管理してもよい。
【０１３６】
上記世代の遷移について、図１６を参照して説明する。現在、書き込み対象となっている世代を「新規ブロック世代」とすると、その一つ前の世代が「処理対象ブロック世代」であり、さらに一つ前の世代は「完了ブロック世代」となる。逆に言うと、図１５に示すように、符号＃１に示す現在の「新規ブロック世代」は、次の時間帯＃２になると「処理対象ブロック世代」となり、また、現在の時間帯＃１における「処理対象ブロック世代」は次の時間帯＃２になると「完了ブロック世代」と言うように、時間の経過に応じて、順次、世代が変化していく。そして、データ格納制御部２１は、現在の「新規ブロック世代」で書き込まれる記憶対象データが存在する場合には、当該「新規ブロック世代」の世代、つまり、次の世代に移り変わる前に、記憶対象データの記憶装置３１への書き込みを完成させる必要がある。
【０１３７】
例えば、データ格納制御部２１は、図１６に示すように、「完了ブロック世代」で、「Block6」から「Block4」、「Block5」へと順に参照する「Block1」、「Block2」、「Block3」からなる記憶対象データを格納して保存する。このとき、これら新たに保存されたブロックデータは、保存されたブロックであることを表す「Retention1」ブロックに参照される。なお、例えば、「Block4」、「Block5」、「Block6」はアドレスデータであり、図１６の網掛けで示す「Block1」、「Block2」、「Block3」は実データである。
【０１３８】
そして、次の世代である「処理対象ブロック世代」にて、上記「Block6」を構成するブロックデータ「Block3」が「Block3x」に変更されたとすると、新たなブロックデータ「Block3x」（図１６の斜線で示す）と、これを参照する「Block5x」、「Block6x」が「処理対象ブロック世代」に格納されることとなる。つまり、この「処理対象ブロック世代」では、「Block6」の代わりに、「Block6x」から「Block4」、「Block5x」へと順に参照される「Block1」、「Block2」、「Block3x」からなるブロックデータが格納されることとなる。但し、「Block1」、「Block2」は既に記憶装置３１に格納されているブロックデータが参照されることとなる。そして、このとき、「Block6x」にて参照されるブロックデータが新たに保存されたため、「Block6x」ブロックは、保存されたブロックであることを表す「Retention2」ブロックに参照される。また、「Block6x」に変更された「Block6」は削除されるため、削除されたことを表す「Deletion1」ブロックに参照される。
【０１３９】
さらに、上述同様に次の世代である「新規ブロック世代」になり、上記「Block6x」を構成するブロックデータ「Block2」が「Block2y」に変更されたとすると、新たなブロックデータ「Block2y」（図１６の斜線で示す）と、これを参照する「Block4y」、「Block6y」が「新規ブロック世代」に格納されることとなる。つまり、この「新規ブロック世代」では、「Block6x」の代わりに、「Block6y」から「Block4y」、「Block5x」へと順に参照される「Block1」、「Block2y」、「Block3x」からなるブロックデータが格納されることとなる。但し、「Block1」は既に記憶装置３１に格納されているブロックデータが参照されることとなる。そして、このとき、「Block6y」にて参照されるブロックデータが新たに保存されたため、「Block6y」ブロックは、保存されたブロックであることを表す「Retention2」ブロックに参照される。また、そして、「Block6y」に変更された「Block6x」は削除されるため、削除されたことを表す「Deletion2」ブロックに参照される。
【０１４０】
次に、データ解放制御部２２について説明する。データ解放制御部２２は、図１１に示すように、参照数カウント部２３とデータ解放部２４とを備えており、それぞれ以下の処理を実行する。
【０１４１】
まず、参照数カウント部２３は、上述した「世代」が変わる毎に、つまり、現在の「新規ブロック世代」となる度に、過去に世代で記憶装置３１に書き込まれたデータのうち、別のアドレスデータから参照されていない記憶対象データあるいはアドレスデータを削除し、かかるデータが格納されていた記憶装置３１内の記憶領域を解放する「削除処理」を実行する。
【０１４２】
具体的に、参照数カウント部２３は、現在の「新規ブロック世代」に対して直前の世代である「処理対象ブロック世代」に書き込まれたデータ（以下、ブロックデータと呼ぶ）に対して、他のアドレスデータから参照されている数を表す「被参照数」をカウントする。被参照数のカウントは、「Retention」ブロックに参照されているルート上に位置するブロックデータである場合は、「＋１」とする。また、「Deletion」ブロックに参照されているルート上に位置するブロックデータである場合は、「−１」とする。例えば、図１７の場合は、現在の「新規ブロック世代」に対して直前の「処理対象ブロック世代」内の各ブロックデータの被参照数がカウントされるが、「処理対象ブロック世代」内の「Retention1」の書き込みしか確定していないため、当該「Retention1」から参照される各ブロックデータ「Block1」〜「Block6」の被参照数がそれぞれ「＋１」となる。そして、時間が経過して次の世代に移行した図１８の場合には、「新規ブロック世代」の直前の「処理対象ブロック世代」で確定した「Retention1」と「Deletion1」に参照される各ブロックデータの被参照数が、それぞれ増減される。すると、点線で囲まれた「Block3」、「Block5」、「Block6」の被参照数が「０」となる。これにより、いずれのアドレスデータからも参照されなくなったブロックデータの被参照数は「０」となるため、かかるブロックデータを検出することが容易となる。
【０１４３】
そして、データ解放部２４は、「新規ブロック世代」にて実行される「削除処理」の最後に、あるいは、一定の時間間隔にて実行され、被参照数が「０」となったブロックデータを記憶装置３１内から削除する。このとき、さらにデータ解放部２４は、削除したブロックデータが格納されていた記憶装置３１内の記憶領域を解放する。つまり、いずれのアドレスデータからも参照されなくなったブロックデータの読み出しができないようにするだけではなく、かかるブロックデータが記憶されていた記憶領域を再利用可能なよう、当該記憶領域を解放する。なお、データ解放部２４による記憶領域の解放処理は、いかなるタイミングで実行されてもよい。
【０１４４】
ここで、上記参照数カウント部２３は、図１９に示すように、「削除処理」を「同期フェーズ」、「削除マークフェーズ」、「コミットフェーズ」の３段階で行う。「同期フェーズ」では、ストレージシステム１０に書き込まれたデータの記憶装置３１への書き込みを完了させる。つまり、直前の世代で書き込まれたデータのうち、書き込み途中であるデータが存在する場合には、かかるデータを記憶装置３１に書き込み、図１８に示すようなツリー構造を完成させる。
【０１４５】
続いて、「削除マークフェーズ」では、記憶装置３１の書き込みが完了したブロックデータの「被参照数」をカウントする処理を行う。これにより、ブロックデータのツリー構造、つまり、参照関係が確定してから「被参照数」をカウントすることができるため、より確実に参照されていないデータの解放を実現できる。
【０１４６】
但し、上述した「削除マークフェーズ」における「被参照数」のカウント中には、カウント対象となっているブロックデータを参照して重複排除される新たにデータの書き込みが行われる場合がある。すると、カウントしているブロックデータの「被参照数」を確定できず、場合によっては「被参照数」が「０」となるブロックデータを、新たな書き込みデータが参照する場合も生じ、後に削除されてしまう場合も起こりうる。例えば、図２０に示すように、「新規ブロック世代」で「Block3」の「被参照数」がカウントされている最中に当該「Block3」を参照する新たな書き込みが発生すると、かかる「Block3」は参照されているにも関わらず後に削除されてしまうことも起こりうる。かかる状況を避けるために、参照数カウント部２３は、「削除マークフェーズ」にてブロックデータの「被参照数」をカウントしているときに新たな書き込みが生じ、過去の世代で格納されたブロックデータを参照している場合には、当該ブロックデータに「Undelete Maker」というフラグを設定する。そして、この「Undelete Maker」というフラグは、設定されていることにより、データ解放部２４による解放の対象から除外する印である。従って、図２０の例では、「新規ブロック世代」の時点ではブロックデータ「Block3」の「被参照数」が「０」になるが、「Undelete Maker」が設定されるため、削除及び解放されない。そして、さらに次の世代となると、「Block3」の被参照数が再度カウントされ「１」になるため、削除されない。
【０１４７】
また、「コミットフェーズ」では、「削除マークフェーズ」でカウントしたブロックデータの「被参照数」を、システムに反映させる。そして、システムに反映された「被参照数」が後にデータ解放部２４にて把握されることで、「被参照数」が「０」であるブロックデータが削除され、その記憶領域が解放されることとなる。
【０１４８】
但し、上述した「コミットフェーズ」において「被参照数」をシステムに反映している最中にも、カウントされたブロックデータを参照して重複排除される新たにデータの書き込みが行われる場合がある。すると、「被参照数」が「０」とカウントされたブロックデータを、新たな書き込みデータが参照する場合も生じ、後に削除されてしまう場合も起こりうる。例えば、図２０に示すように、「新規ブロック世代」で「Block3」の「被参照数」のカウントが終了した後に当該「Block3」を参照する新たな書き込みが発生すると、かかる「Block3」は参照されているにも関わらず後に削除されてしまうことも起こりうる。かかる状況を避けるために、参照数カウント部２３は、「コミットフェーズ」にてブロックデータの「被参照数」をシステムに反映しているときに新たな書き込みが生じた場合には、「被参照数」が正の値（つまり、「被参照数＞０」）であるブロックデータ、あるいは、上述した「Undelete Maker」が設定されているブロックデータ、に対する参照のみを許可する。これにより、新たな書き込みにより、後に削除される可能性の高いブロックデータが参照されて重複排除処理が行われることを抑制できる。
【０１４９】
上記実施形態の一部又は全部は、以下の付記のようにも記載されうる。以下、本発明におけるストレージシステム（図２１参照）、プログラムを記憶した記憶媒体、情報処理方法の構成の概略を説明する。但し、本発明は、以下の構成に限定されない。
【０１５０】
（付記１）
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置１１０に格納すると共に、当該記憶装置１１０に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置１１０に格納する場合に、当該記憶装置１１０に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置１１０に格納するデータ格納制御部１０１と、
前記記憶装置１１０に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置１１０内の記憶領域を解放するデータ解放制御部１０２と、を備え、
前記データ格納制御部１０１は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置１１０に格納し、
前記データ解放制御部１０２は、現在の時間帯に対して過去の時間帯に前記記憶装置１１０に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置１１０内の記憶領域を解放する、
ストレージシステム。
【０１５１】
（付記２）
付記１に記載のストレージシステムであって、
前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ストレージシステム。
【０１５２】
（付記３）
付記２に記載のストレージシステムであって、
前記データ解放制御部は、現在の時間帯に対して直前の時間帯以前に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントする、
ストレージシステム。
【０１５３】
（付記４）
付記３に記載のストレージシステムであって、
前記データ解放制御部は、前記データ格納制御部にて直前の時間帯に書き込まれた前記記憶対象データあるいは前記アドレスデータの前記記憶装置内への格納を完了した後に、前記被参照数をカウントする、
ストレージシステム。
【０１５４】
（付記５）
付記２に記載のストレージシステムであって、
前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数をカウントしているときに、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを前記データ解放制御部による解放の対象から除外する設定を行う、
ストレージシステム。
【０１５５】
（付記６）
付記５に記載のストレージシステムであって、
前記データ格納制御部は、前記データ解放制御部にて前記記憶対象データあるいは前記アドレスデータの前記被参照数のカウントが終了した後に、過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータを参照する新たな書き込みが発生した場合に、その参照先となる過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータの前記被参照数が正の値、あるいは、当該記憶対象データあるいはアドレスデータが前記データ解放制御部による解放の対象から除外されている場合に、前記新たな書き込みに対応する前記記憶対象データあるいは前記アドレスデータの参照を行う、
ストレージシステム。
【０１５６】
（付記７）
情報処理装置に、
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納するデータ格納制御部と、
前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放するデータ解放制御部と、を実現させると共に、
前記データ格納制御部は、時系列で区分した時間帯毎に、前記記憶対象データあるいは前記アドレスデータを前記記憶装置に格納し、
前記データ解放制御部は、現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
ことを実現させるためのプログラムを記憶した記憶媒体。
【０１５７】
（付記８）
付記７に記載のプログラムを記憶した記憶媒体であって、
前記データ解放制御部は、前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
プログラムを記憶した記憶媒体。
【０１５８】
（付記９）
記憶対象データと、参照先に格納されているデータ内容及び格納位置に基づくアドレスデータであり前記記憶対象データ又は他のアドレスデータを参照する前記アドレスデータと、を記憶装置に格納すると共に、当該記憶装置に既に記憶されている前記記憶対象データと同一のデータ内容の他の記憶対象データを前記記憶装置に格納する場合に、当該記憶装置に既に記憶されている前記記憶対象データを前記他の記憶対象データとして参照する前記アドレスデータを前記記憶装置に格納し、
前記記憶装置に格納されている前記記憶対象データあるいは前記アドレスデータのうち、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、と共に、
前記記憶対象データあるいは前記アドレスデータの前記記憶装置への格納処理を、時系列で区分した時間帯毎に行い、
現在の時間帯に対して過去の時間帯に前記記憶装置に格納された前記記憶対象データあるいは前記アドレスデータに対して、別のアドレスデータから参照されていない前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
情報処理方法。
【０１５９】
（付記１０）
付記９に記載の情報処理方法であって、
前記記憶対象データあるいは前記アドレスデータにおける別のアドレスデータから参照されている被参照数をカウントし、当該被参照数が「０」である前記記憶対象データあるいは前記アドレスデータが格納されている前記記憶装置内の記憶領域を解放する、
情報処理方法。
【図１】
0005382227.tif 000005
【図２】
0005382227.tif 000006
【図３】
0005382227.tif 000007
【図４】
0005382227.tif 000008
【図５】
0005382227.tif 000009
【図６】
0005382227.tif 000010
【図７】
0005382227.tif 000011
【図８】
0005382227.tif 000012
【図９】
0005382227.tif 000013
【図１０】
0005382227.tif 000014
【図１１】
0005382227.tif 000015
【図１２】
0005382227.tif 000016
【図１３】
0005382227.tif 000017
【図１４】
0005382227.tif 000018
【図１５】
0005382227.tif 000019
【図１６】
0005382227.tif 000020
【図１７】
0005382227.tif 000021
【図１８】
0005382227.tif 000022
【図１９】
0005382227.tif 000023
【図２０】
0005382227.tif 000024
【図２１】
0005382227.tif 000025