JP2016526717A

JP2016526717A - ハイブリッドガベージコレクション

Info

Publication number: JP2016526717A
Application number: JP2016519652A
Authority: JP
Inventors: バラス，フランク; ハント，タッド
Original assignee: エグザブロックス・コーポレーション
Priority date: 2013-06-12
Filing date: 2014-06-12
Publication date: 2016-09-05
Also published as: EP3008647A4; EP3008647A1; US20140372490A1; US9514137B2; WO2014201270A1

Abstract

ファイルシステムにおけるオブジェクトのハイブリッドガベージコレクションのための方法が開示される。方法の実施例は、ファイルシステムにおけるそれぞれのオブジェクトを、参照カウンタ、失効時間、およびバージョン識別子に割り当てるステップを含む。オブジェクトの参照カウンタがゼロでない間、オブジェクトはファイルシステムの中に保持され得る。オブジェクトの参照カウンタがゼロであるとの決定後に、オブジェクトは、オブジェクトに関連付けされた失効時間までファイルシステムの中に保持され得る。オブジェクトを参照しているリファレンスが検出された場合、オブジェクトの失効時間は、オブジェクトとリファレンスの失効時間のうち最新のものに更新される。さらに、オブジェクトのバージョン識別子が既定のバージョン番号より大きい間、オブジェクトはファイルシステムの中に保持され得る。

Description

本発明開示は、一般的には、データ処理に関し、より特定的には、ハイブリッドガベージコレクション方法に関する。

本特許出願は、米国特許仮出願第６１／８３４０９７号（２０１３年６月１２日提出）について優先権の利益を主張する。前出の発明開示は、全ての目的のために、ここにおいて参照として包含されている。

このセクションにおいて記述されるアプローチは遂行され得るものであるが、以前に考えられ、または、遂行されたアプローチである必要はない。従って、そうでないものと示されていなければ、このセクションにおいて記述されるあらゆるアプローチは、それらが単にこのセクションに包含されているせいで、従来技術であるとしてみなされることを決めてかかるべきではない。

コンピュータシステムにおいては、ハードディスク（ＨＤＤ）、半導体ディスク（ＳＳＤ）、または他のいくつかのストレージ上のファイルシステムにおけるデータは、たいてい、オブジェクト（ｏｂｊｅｃｔ）およびオブジェクトを指し示すリファレンス（ｒｅｆｅｒｅｎｃｅ）として編成されている。一つのオブジェクトは、そのオブジェクトを指し示す多くのリファレンスを有してよく、加えて、オブジェクト自身が、他のオブジェクトを指し示すリファレンスを保持することができる。従って、典型的には、データが、データブロックのツリー（ｔｒｅｅ）として編成されている。

種々のストレージデバイスのリソースを効率的に操作するためには、もはや必要とされないオブジェクトを除去するためのプロシージャを設定することが重要である。

従来のファイルシステムは、データオブジェクトの最後のバージョンだけを保持する。従来のファイルシステムにおけるガベージコレクション（ｇａｒｂａｇｅｃｏｌｌｅｃｔｉｏｎ）は、もはや他のオブジェクトによって参照されないオブジェクトを見つけ出し、かつ、除去するために、全てのオブジェクトのデータベースを分析する特別なプロセスを実行すること、を含んでいる。

従来のガベージコレクション技術のいくつかは、参照カウント（ｒｅｆｅｒｅｎｃｅｃｏｕｎｔｉｎｇ）を使用する。参照カウントは、オンザフライ（ｏｎｔｈｅｆｌｙ）で所与のオブジェクトを指し示しているリファレンスの数量を追跡する。オブジェクトを指し示すリファレンスが存在しない場合、そのオブジェクトはもはや使用されていないものであって、オブジェクトデータベースから除去され得るものである。そして、このオブジェクトによって使用されているストレージデバイス上のスペースは、占有されていないものとしてラベル付けされ、そして、他のオブジェクトのために使用され得る。

この概要は、以下の詳細な説明において、さらに詳しく記述されるコンセプトについて、簡素化された形式において選定されたコンセプトを紹介するために提供されるものである。この概要は、特許請求される技術的事項の主要な機能または本質的な機能を特定するように意図されたものではない。また、特許請求される技術的事項の範囲を決定するための補助として使用されるように意図されたものでもない。

ここにおいて開示される技術は、ファイルシステムにおけるガベージコレクションに関する。ファイルシステムは、システムにおける全部のオブジェクトの全てのバージョンを初期的に保持するように設定され得る。どんなに変更が小さくてもである。このアプローチによって、全ファイルシステムに係るファイルおよびスナップショットの多くのバックアップバージョンを生成することができる。しかしながら、ファイルシステムにおいて全部のオブジェクトの以前のバージョンを保持することは、巨大な数のデータオブジェクトを生じるだろうし、ついには、ストレージスペースを使い果たしてしまう。従って、この問題を克服するためには、特別なガベージコレクション技術が必要とされる。それは、定期的に以前のバージョンを間引き、保持するのに十分重要であると考えられるスナップショットだけを保持するものである。

いくつかの実施例においては、オブジェクトの以前のバージョンが保持されるべき時間インターバルが定められ得る。例えば、一つのガベージコレクションルールは、最後の５分間以内で捉えられた全てのスナップショットを保持するように設定されてよい。最後の２４時間以内で捉えられたそれぞれのスナップショットに対しては１時間毎に一つのバージョンを保持し、かつ、より古い時間期間に関連するスナップショットに対して１日毎に一つのバージョンを保持するものである。

いくつかの実施例において、データオブジェクトは、データブロックのツリーとして編成され得る。ストレージデバイスのクラスタにわたって広がるデータブロックを用いるものである。従って、規定のスナップショットの失効時間をデータツリーにおけるルートリファレンスから全てのリファレンスブロックへ伝播する（ｐｒｏｐａｇａｔｅ）技術が提供される。

いくつかの実施例において、ファイルシステムにおけるオブジェクトのハイブリッドガベージコレクションのための方法は、関連する参照カウンタ、失効時間、および、ファイルシステムにおけるオブジェクトのバージョン識別子を含んでよい。本方法により、オブジェクトの参照カウンタがゼロでない間、オブジェクトをファイルシステムの中に保持することができる。本方法は、さらに、オブジェクトに関連付けされた失効時間になるまでオブジェクトをファイルシステムの中に保持することを含んでよい。その時点でオブジェクトの参照カウンタはゼロになっている。加えて、本方法により、オブジェクトに関連付けされたバージョン識別子が、既定の最大バージョンより大きい間、オブジェクトをファイルシステムの中に保持することができる。

いくつかの実施例において、本方法は、オブジェクトを参照している既存のリファレンスに関連付けされた参照カウンタがゼロであると決定することを含んでよい。決定に応じて、オブジェクトの参照カウンタが１だけ減らされ、かつ、オブジェクトに関連付けされた失効時間が、オブジェクトの失効時間およびリファレンスの失効時間のうち最新のものに設定されてよい。

いくつかの実施例において、本方法は、さらに、オブジェクトに関連付けされた参照カウンタがゼロであり、かつ、オブジェクトを参照している新たなリファレンスがまさに追加されることを決定することを含んでよい。決定に応じて、参照カウンタが１だけ増やされてよく、かつ、このオブジェクトによって参照される全てのオブジェクトが、同様に、１だけ増やされた参照カウンタを有する。オブジェクトに関連付けされた失効時間が、オブジェクトの失効時間および新たなリファレンスの失効時間のうち最新のものに同時に更新されてよい。さらなる実施例においては、ファイルシステムにおけるオブジェクトの初期の失効時間が、オブジェクトの現在および新たなバージョンの追加の間の経過時間期間を使用して計算され得る。

本発明開示のさらなる実施例において、本方法のステップは、インストラクションを含んでいるマシンで読取り可能な媒体上に保管されており、一つまたはそれ以上のプロセッサによって実行されると、上記のステップを実施する。なおも、さらなる実施例においては、ハードウェアシステム、またはデバイスが上記のステップを実施するように適合され得る。他の機能、実施例、および具現化が以下に説明される。

実施例が、例示として、かつ、限定するものとしてではなく、添付の図面における図において説明される。ここで、類似の参照番号は、類似のエレメントを示している。
図１は、自身について指し示しているいくつかのリファレンスを伴い、かつ、関連する属性を有するデータオブジェクトに係る一つの実施例を示している。図２は、２つの他のオブジェクトを指し示しているリファレンスの除去、および、削除されているリファレンスからオブジェクトへの参照カウンタと失効時間（ｅｘｐｉｒａｔｉｏｎｔｉｍｅ）の伝播に係る一つの実施例を示している。図３は、親（ｐａｒｅｎｔ）オブジェクトの参照カウンタがゼロになるか、又は、ゼロに設定されたときの、親オブジェクトから子（ｃｈｉｌｄ）オブジェクトへの参照カウンタと失効時間の伝播のための方法を示すフローチャートである。図４は、アーカイブオブジェクトに対する新たなリファレンスの追加に係る一つの実施例を示している。図５は、ライブオブジェクトからアーカイブオブジェクトへの参照カウンタと失効時間の伝播のための方法を示すフローチャートである。図６は、ルートディレクトリ、サブディレクトリ、およびサブディレクトリにおけるファイルを含んでいるファイルシステムのスナップショットの履歴に係る一つの実施例を示している。図７は、コンピュータシステムの電子的形態の例におけるマシンのためのコンピューティングデバイスの図式表現を示している。その中では、ここにおいて説明されるあらゆる一つまたはそれ以上の方法をマシンに実施させるための一式のインストラクションが実行され得る。

以降の詳細な説明は、添付の図面に対する参照を含んでいる。図面は、詳細な説明の一部を形成している。図面は、実施例に従った説明を示している。これらの実施例は、ここにおいて「例（”ｅｘａｍｐｌｅ”）」としても参照されるが、当業者が本発明の技術的事項を実施することができるよう、十分に詳細に記述される。実施例は組み合わせられ、他の実施例が利用され得る。もしくは、構造的、論理的、および電気的な変更が、特許請求される範囲から逸脱することなく行われ得る。以降の詳細な説明は、従って、限定的な意味に理解されるべきではなく、請求の範囲は、添付の請求項およびその均等物によって定められるものである。この文書において、用語「一つの（”ａ”と”ａｎ”）」は、特許関連文書において一般的であるように、一つ、または、一つ以上を含むように使用されている。この文書において、用語「または”ｏｒ”」は、排他的でない”ｏｒ”を参照するように使用されている。そうでないものと示されていなければ、「ＡまたはＢ（”ＡｏｒＢ”）」は、「ＡであるがＢでない（”Ａ” ｂｕｔｎｏｔＢ”）」、「ＢであるがＡでない（”Ｂ” ｂｕｔｎｏｔＡ”）」、および「ＡおよびＢ（”ＡａｎｄＢ”）」を含むようにである。

ここにおいて開示される実施例に係る技術は、種々の技術を使用して実施されてよい。例えば、ここにおいて説明される方法は、コンピュータシステム上で実行されるソフトウェアにおいて実施されてよく、もしくは、マイクロプロセッサまたは他の特別にデザインされた特定用途向け集積回路（ＡＳＩＣ）の組合せ、プログラム可能な論理デバイス、または種々のこれらの組合せ、のいずれかを利用しているハードウェアにおいて実施されてよい。特に、ここにおいて説明される方法は、ディスクドライブ、またはコンピュータで読取り可能な媒体といった、ストレージ媒体上に存する一連のコンピュータで実行可能なインストラクションによって実施されてよい。ここにおいて開示される方法は、コンピュータ（例えば、デスクトップコンピュータ、タブレットコンピュータ、ラップトップコンピュータ）、ゲームコンソール、ハンドヘルドゲームマシン、携帯電話、スマートフォン、スマートテレビシステム、等によって実施され得ることに注意すべきである。

所定の実施例において、ファイルシステムにおけるデータは、データオブジェクトのグラフとして表される。いくつかのオブジェクトは、他のデータオブジェクトに対するポインタ、リファレンスとしても知られているもの、を保持することができる。同時に、データオブジェクトは、それを指し示しているいくつかの他のオブジェクトによって参照され得る。これらのポインタまたはリファレンスは、これらに限定されるわけではないが、参照されるオブジェクトに対するキー識別子（ｋｅｙｉｄｅｎｔｉｆｉｅｒ）を保管することを含む、多くの方法で保管され得る。ここで、キー識別子は、いくつかの実施例においては、オブジェクトのコンテンツのハッシュ（ｈａｓｈ）として表されてよい。

いくつかの実施例においては、少なくとも３つの属性が、ファイルシステムにおけるそれぞれのデータオブジェクトと関連付けされ得る。これらの属性は、参照カウンタ（ＲＣ）、失効時間（ＥｘｐＴｉｍｅ）、およびスナップショット（またはバージョン）識別番号（ＳｎａｐＩＤ）を含んでよい。

参照カウンタＲＣは、どれだけ多くの他のオブジェクトが、このオブジェクトを指し示しているかを示している。参照カウンタは、そのオブジェクトを指し示す新たなリファレンスが追加されたときに、１だけ増やされる。そして、そのオブジェクトを指し示す既存のリファレンスが除去されたときに、１だけ減らされる。

失効時間ＥｘｐＴｉｍｅは、オブジェクトに対する参照カウンタがゼロになるか、ゼロに設定された後で、オブジェクトがオブジェクトストア（ｏｂｊｅｃｔｓｔｏｒｅ）の中に保持されるべき時間期間である。この時間は、絶対値または相対値を使用して保管されてよく、かつ、リニアタイム（ｌｉｎｅａｒｔｉｍｅ）または番号付けされた一連の顕著なイベントのいずれかとして表されてよい。ゼロである参照カウンタを伴う非失効（ｎｏｎ−ｅｘｐｉｒｅｄ）オブジェクトは、アーカイブオブジェクトとして参照され得る。アーカイブオブジェクトは、オブジェクトがリファレンスを有さず、かつ、失効するまで除去されない。しかしながら、単にオブジェクトが未だ除去されていないからといって、それがアーカイブオブジェクトであることを意味するものではない。ライブ（ｌｉｖｅ）リファレンスを有さず、かつ、失効しており、しかし、未だに除去されていない、といったオブジェクトは、「ゾンビ（”Ｚｏｍｂｉｅ”）」オブジェクトとして参照され得る。１に等しいか、それ以上である参照カウンタを伴うオブジェクトは、ライブオブジェクトとして参照され得る。スナップ識別番号は、ファイルシステムのどのスナップショットバージョンが所与のオブジェクトと関連するかを示している。

スナップショット識別番号ＳｎａｐＩＤは、単調に増加し、かつ、ルートオブジェクトにおいて記録されたＳｎａｐＩＤから計算される。新たなルートオブジェクトを結果として生じるものである。

図１は、データオブジェクトＣに係る一つの実施例を示している。２つの他のオブジェクトＡおよびＢが、オブジェクトＣを参照しており、そのため、オブジェクトＣの参照カウンタは２に等しい。

オブジェクトの参照カウンタがゼロになり、かつ、そのオブジェクトが少なくとも一つの子オブジェクトを指し示している場合には、子オブジェクトの失効時間は、親の失効時間および子オブジェクトの失効時間のうち最新のものに再設定（ｒｅｓｅｔ）される。このルールは、子オブジェクトが、少なくとも親オブジェクトと同じだけ長くファイルシステムの中に保持されることを保証するものである。

図２に示される一つの実施例において、オブジェクトＡは、オブジェクトＢとＣを参照している。オブジェクトＡの参照カウンタがゼロになるので、オブジェクトＡは、ライブオブジェクトからアーカイブオブジェクトへ移される。オブジェクトＢとＣの参照カウンタは、１だけ減らされる。オブジェクトＡの失効時間は、オブジェクトＢとＣの失効時間を設定するために使用される。

図３は、親オブジェクトの参照カウンタがゼロになるか、又は、ゼロに設定されたときの、親オブジェクトから子オブジェクトへの参照カウンタと失効時間の伝播（ｐｒｏｐａｇａｔｉｏｎ）のための方法３００を示すフローチャートである。ステップ３０２において、方法３００は、手始めに、親オブジェクトの参照カウンタがゼロになるか、又は、ゼロに設定されることを決定する。ステップ３０４において、方法３００は、全ての子オブジェクトに対して、参照カウンタを１だけ減らして、方法３００を継続する。ステップ３０６において、方法３００は、全ての子オブジェクトに対して、失効時間を子オブジェクトおよび親オブジェクトの失効時間のうち最新のものに再設定して、方法３００を進行する。

アーカイブオブジェクトは、他のいくつかのオブジェクトが、そのオブジェクトを指し示すこと開始する場合に、再びライブ（ｌｉｖｅ）になり得る。図４は、２つのアーカイブオブジェクトＡとＢを示している。両方がライブであるときに、オブジェクトＡはオブジェクトＢを参照する。オブジェクトＡに対するリファレンスとしてオブジェクトＣが追加されている。従って、オブジェクトＡの参照カウンタは、１に戻るように再設定され、かつ、失効時間が、オブジェクトＡおよびその親オブジェクトＣの失効時間のうち最新のものに再設定される。オブジェクトＡの参照カウンタがゼロではないので、オブジェクトＡはライブになり、そして、今ではアーカイブオブジェクトＢを指し示している。従って、参照カウンタと失効時間は、オブジェクトＢ、および、存在する場合には子オブジェクトへと伝播される。

図５は、ライブ親オブジェクトからアーカイブ子オブジェクトへの参照カウンタと照明時間の伝播のための方法５００を示すフローチャートである。ステップ５０２において、方法５００は、手始めに、アーカイブオブジェクトに対して新たなライブオブジェクトが追加されることを決定する。ステップ５０４において、方法５００は、アーカイブオブジェクトの参照カウンタを１に再設定して進行する。ステップ５０６において、方法５００は、アーカイブオブジェクトの失効時間を、新たなライブリファレンスおよびアーカイブオブジェクトの失効時間のうち最新のものに設定すること、を含み得る。方法５００のオペレーションの結果として、アーカイブオブジェクトはライブオブジェクトになる。

いくつかの実施例において、ファイルシステムは、アイノード（Ｉｎｏｄｅ）として参照される特別なタイプのリファレンスオブジェクトを含み得る。アイノードは、ファイルシステムのスナップショット履歴を編成するために使用される。ファイルシステムにおけるそれぞれのデータエンティティは、リンクされたアイノードのチェイン（ｃｈａｉｎ）と関連付けられる。チェインにおけるアイノードは、データエンティティの異なるバージョンを参照する。データエンティティが変更される毎に、新たなアイノードがチェインの最後に追加される。データエンティティの最後のバージョンを指し示している最後のアイノードを用いるものである。

データにおける変更は、その親エンティティへ伝播される。親エンティティは、つまり、このデータエンティティが在るディレクトリである。システムの一つの変更の中に含まれる全てのエンティティは、それらのチェインのトップにおいて新たなアイノードを受け取る。一つのファイルシステム変更において作成された全てのアイノードには、同一のスナップＩＤ（ＳｎａｐＩＤ）属性が割り当てられる。スナップＩＤは、ファイルシステムにおいて変更が生じたときに、いつでも、ある値により増やされる。

アイノードオブジェクトは、参照カウンタに対する特別なルールを有している。ライブディレクトリによって直接的に参照されるチェインにおける最初のアイノードの参照カウンタは、決して１より小さくはない。チェインにおける最後のアイノードは、追加のリファレンスを獲得する。単に、それがアイノードの最新のライブバージョンであるからである。このことが、ライブディレクトリによって参照されるアイノードバージョンにも生じる場合には、２であるカウントを有することになる。チェインにおける他の全てのアイノードの参照カウンタは、ゼロに設定される。新たなアイノードがチェインのトップに追加される毎に、その参照カウンタは１に設定され、そして、チェインにおいて前にあるものの参照カウンタは、１だけ減らされる。このアイノード及びこのアイノードによって参照されるデータエンティティは、アーカイブオブジェクトになり、そして、それらの失効時間の後で両方が除去され得る。そのアイノードの失効時間は、また、アイノードが発生するときに計算される。失効ポリシに従ったものであり、かつ、以前のアイノードバージョンの開始および終了時間の知識を使用するものである。

ファイルシステムの一つの実施例が、図６に示されている。この典型的なシステムは、一つのディレクトリＤ、および、このディレクトリの中に存在しているＦと名付けられた一つのファイルを伴うシステムに対応している。リンクされたアイノードＩ１２、Ｉ１３、およびＩ１４のチェインは、ファイルＦと関連付けされている。アイノードＩ１１３とアイノードＩ１４は、ファイルＦの一つのバージョンをそれぞれ指し示している。アイノードＩ１２は、ファイルＦの作成によって生じたファイルシステムにおける変更に対応している。アイノードＩ１２は、ファイルの一つのバージョンを指し示していない。ファイルＦは、それが作成されたときに中身が空だったからである。アイノードＩ１２、Ｉ１３、およびＩ１４に対応する変更は、ファイルＦの親であるディレクトリＤへ伝播される。この伝播のおかげで、ディレクトリＤと関連付けされたアイノードのチェインは、アイノードＩ２、Ｉ３、およびＩ４を受け取る。オブジェクトのスナップＩＤが左上のコーナーに示されており、そして、アイノードと一つの変更において作成されたオブジェクトは、同一の値のスナップＩＤを有している。

いくつかの実施例において、アイノードとアイノードによって参照されるデータオブジェクトに対する失効時間は、このアイノードの寿命（ｌｉｆｅｔｉｍｅ）に基づいて決定され得る。寿命は、チェインのトップにおいてアイノードが作成された瞬間から、別のアイノードがそのアイノードをクローズする瞬間までに経過した時間である。図６に示されている実施例において、アイノードＩ１２の寿命はＴ２であり、アイノードＩ１３の寿命はＴ３である。

このように、所定の実施例においては、より大きいポリシインターバルをその寿命がクロス（ｃｒｏｓｓ）するアイノードは、失効がより遅いものであり、そして、その逆も同様であり、より小さなポリシインターバルだけをその寿命がクロスするか、またはポリシインターバルをクロスしないアイノードは、失効がより早いものである。

いくつかの実施例において、スナップＩＤの範囲は、その範囲に属するオブジェクトを、ガベージコレクションプロセスによる除去から保護するように定められ得る。フラックススナップ（Ｆｌｕｘｓｎａｐ）と呼ばれる特別な境界パラメータが、スナップＩＤの範囲を確立するために使用され得る。ガベージコレクションは、フラックススナップより大きいか等しいスナップＩＤを伴うオブジェクトを除去することが禁じられる。ファイルシステムの寿命の最中に、フラックススナップは、ガベージコレクションからの保護のために、狭い範囲へと移動され得る。新たに作成されたオブジェクトは、フラックススナップより大きいか等しいスナップＩＤを割り当てることによって一時的に保護され得る。そして、次に、これらのオブジェクトがライブオブジェクトになり、かつ、より長く保持されることが意味される場合には、フラックススナップが先に進むことを許可される前に、ゼロでない（ｎｏｎ−ｚｅｒｏ）参照カウンタが割り当てられる。一旦、フラックススナップが先に進むと、参照カウンタによって保護されてきていないあらゆるオブジェクトが、除去について適格となる。

いくつかの実施例において、一つのアイノードのファイルシステムコンセプトのバージョンは、それぞれのアイノードの種々のバージョンに対するリファレンスを含んでいるイミュータブル（ｉｍｍｕｔａｂｌｅ）オブジェクトのツリーを使用して表わされてよい。ここで、アイノード自身は、以前のアイノードバージョンに対するリファレンスを含む必要はない。オブジェクトのツリーとしてのアイノードのこの表現は、それぞれのアイノードのバージョンのチェインとしてのアイノードの表現について、追加であっても、または、代わりであってもよい。アイノードがイミュータブルオブジェクトのツリーとして表される、そうした実施例においては、上述された、アイノードのための特別なルールが適用される必要はない。そして、この表現に対するオブジェクトは、参照カウントおよび失効時間のための一般的なルールに従ってよい。

図７は、コンピュータシステム７００の電子的形態の例におけるマシンのためのコンピューティングデバイスの図式表現を示している。その中では、ここにおいて説明されるあらゆる一つまたはそれ以上の方法をマシンに実施させるための一式のインストラクションが実行され得る。種々の実施例において、マシンは、スタンドアロン機器として動作し、または、他のマシンに接続されてよい（例えば、ネットワーク）。ネットワークされた展開において、マシンは、サーバ−クライアント環境におけるサーバまたはクライアントマシンの能力において動作し、または、ピアツーピア（ｐｅｅｒ−ｔｏ−ｐｅｅｒ）（または分散）ネットワーク環境におけるピアマシンとして動作し得る。マシンは、パーソナルコンピュータ（ＰＣ）、タブレットＰＣ，セットトップボックス（ＳＴＢ）、パーソナルデジタルアシスタント、携帯電話、ポータブル音楽プレーヤ（例えば、ムービングピクチャーエキスパーツグループ・オーディオレイヤ３（ＭＰ３）プレーヤといった、ポータブルハードドライブオーディオデバイス）、ゲームパッド、ポータブルゲームコンソール、車載コンピュータ、スマートホームコンピュータ、または、マシンによって行われるべきアクションを特定する一式のインストラクションを（シーケンシャルに、または、そうではなく）実行することができるあらゆるマシン、であってよい。さらに、一つのマシンだけが図示されているが、用語「マシン（”ｍａｃｈｉｎｅ”）」は、また、ここにおいて説明されるあらゆる一つまたはそれ以上の方法をマシンに実施させるための一式（または複数セット）のインストラクションを個別又は協同して実施するマシンのあらゆるコレクション（ｃｏｌｌｅｃｔｉｏｎ）を含むものと理解されるものである。

コンピュータシステム７００の実施例は、一つのプロセッサまたは複数のプロセッサ７０５（例えば、中央処理装置（ＣＰＵ）、グラフィクス処理装置（ＧＰＵ）、もしくは両方）、および、メインメモリ７１０とスタティックメモリ７１５、を含んでいる。メインメモリとスタティックメモリは、バス７２０を介して相互に通信する。コンピュータシステム７００は、さらに、ビデオディスプレイ装置７２５（例えば、液晶ディスプレイ）を含んでよい。コンピュータシステム７００は、また、少なくとも一つの入力デバイス７３０を含んでよい。英数字入力デバイス（例えば、キーボード）、カーソルコントロールデバイス（例えば、マウス）、マイクロフォン、デジタルカメラ、ビデオカメラ、等といったものである。コンピュータシステム７００は、また、ディスクドライブ装置７３５、信号生成デバイス７４０（例えば、スピーカ）、およびネットワークインターフェイスデバイス７４５、を含んでいる。

ディスクドライブ装置７３５は、コンピュータで読取り可能な媒体７５０を含んでおり、ここにおいて説明されるあらゆる一つまたはそれ以上の方法または機能を具現し又は利用される、一つまたはそれ以上のインストラクションおよびデータ構造（例えば、インストラクション７５５）を保管する。インストラクション７５５は、また、コンピュータシステム７００による実行の最中に、メインメモリ７１０の中、及び/又は、プロセッサ７０５の中に、完全に又は少なくとも部分的に、存在してもよい。メインメモリ７１０とプロセッサ７０５は、また、マシンで読取り可能な媒体も構成する。

インストラクション７５５は、さらに、ネットワークインターフェイスデバイス７４５を介してネットワーク７６０にわたり、送信または受信され得る。ネットワークインターフェイスデバイスは、数多くのよく知られた転送プロトコル（例えば、ハイパーテキストトランスファープロトコル（ＨＴＴＰ）、ＣＡＮ、シリアル（Ｓｅｒｉａｌ）、およびＭｏｄｂｕｓ）のうちのどれでも一つを利用している。例えば、ネットワーク７６０は、以下のうち一つまたはそれ以上を含んでよい。インターネット、ローカルイントラネット、ＰＡＮ（ＰｅｒｓｏｎａｌＡｒｅａＮｅｔｗｏｒｋ）、ＬＡＮ（ＬｏｃａｌＡｒｅａＮｅｔｗｏｒｋ）、ＷＡＮ（ＷｉｄｅＡｒｅａＮｅｔｗｏｒｋ）、ＭＡＮ（ＭｅｔｒｏｐｏｌｉｔａｎＡｒｅａＮｅｔｗｏｒｋ）、仮想プライベートネットワーク（ＶＰＮ）、ストレージエリアネットワーク（ＳＡＮ）、フレームリレー接続、高度インテリジェントネットワーク（ＡＩＮ）接続、同期型光ネットワーク（ＳＯＮＥＴ）接続、デジタルＴ１、Ｔ３、Ｅ１、またはＥ３ライン、デジタルデータサービス（ＤＤＳ）接続、ＤＳＬ（ＤｉｇｉｔａｌＳｕｂｓｃｒｉｂｅｒＬｉｎｅ）接続、イーサネット接続、ＩＳＤＮ（ＩｎｅｇｒａｔｅｄＳｅｒｖｉｃｅｓＤｉｇｉｔａｌＮｅｔｗｏｒｋ）ライン、ケーブルモデム、ＡＴＭ（ＡｓｙｎｃｈｒｏｎｏｕｓＴｒａｎｓｆｅｒＭｏｄｅ）接続、もしくは、ＦＤＤＩ（ＦｉｂｅｒＤｉｓｔｒｉｂｕｔｅｄＤａｔａＩｎｔｅｒｆａｃｅ）又はＣＤＤＩ（ＣｏｐｐｅｒＤｉｓｔｒｉｂｕｔｅｄＤａｔａＩｎｔｅｒｆａｃｅ）接続、である。さらに、通信は、また、種々の無線ネットワークのうちあらゆるものに対するリンクも含んでよい。無線ネットワークは、ＧＰＲＳ（ＧｌｏｂａｌＰａｃｋｅｔＲａｄｉｏＳｅｒｖｉｃｅ）、ＧＳＭ（ＧｌｏｂａｌＳｙｓｔｅｍｆｏｒＭｏｂｉｌｅＣｏｍｍｕｎｉｃａｔｉｏｎ）、ＣＤＭＡ（ＣｏｄｅＤｉｖｉｓｏｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ）又はＴＤＭＡ（ＴｉｍｅＤｉｖｉｓｏｎＭｕｌｔｉｐｌｅＡｃｃｅｓｓ）、携帯電話ネットワーク、ＧＰＳ、ＣＤＰＤ（ｃｅｌｌｕｌａｒｄｉｇｉｔａｌｐａｃｋｅｔｄａｔａ）、ＲＩＭ（ＲｅｓｅａｒｃｈｉｎＭｏｔｉｏｎ社）のデュ―プレックスページングネットワーク、ブルートゥース（登録商標）ラジオ、もしくは、ＩＥＥＥ８０２．１１ベースのラジオ周波数ネットワーク、を含んでいる。

実施例においては、一つの媒体であるようにコンピュータで読取り可能な媒体７５０が示されているが、用語「コンピュータで読取り可能な媒体（”ｃｏｍｐｕｔｅｒ−ｒｅａｄａｂｌｅｍｅｄｉｕｍ”）」は、インストラクションの一つまたはそれ以上のセットを保管する一つの媒体または複数の媒体（例えば、集中または分散データベース、及び/又は、関連するキャッシュおよびサーバ）を含むものと捉えられるべきである。用語「コンピュータで読取り可能な媒体」は、また、マシンによる実行のための一式のインストラクションを保管し、エンコードし、または運搬することができるあらゆる媒体を含むものと捉えられるべきであり、本アプリケーションに係るあらゆる一つまたはそれ以上の方法をマシンに実行させる。もしくは、そうした一式のインストラクションによって使用され、又は関連付けされるデータ構造を保管し、エンコードし、または運搬することができるあらゆる媒体を含むものと捉えられるべきである。用語「コンピュータで読取り可能な媒体」は、従って、これらに限定されるわけではないが、半導体メモリ、光および磁気媒体を含むものと捉えられるべきである。そうした媒体は、また、限定するものではないが、ハードディスク、フロッピー（登録商標）ディスク、フラッシュメモリカード、デジタルビデオディスク（ＤＶＤ）、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、等も含み得る。

ここにおいて説明される実施例は、ハードウェア、又はソフトウェアとハードウェアの組合せにおいてコンピュータ上にインストールされたコンピュータで実行可能なインストラクション（例えば、ソフトウェア）を含むオペレーティング環境において実施され得る。コンピュータで実行可能なインストラクションは、コンピュータプログラミング言語で記述され、もしくは、ファームウェアロジックにおいて具現化され得る。認定された規格に準拠してプログラミング言語で記述された場合、そうしたインストラクションは、種々のハードウェアプラットフォーム上で実行され、そして、種々のオペレーティングシステムに対するインターフェイスのために実行され得る。これらに限定されるわけではないが、本方法を実施するためのコンピュータソフトウェアプログラムは、あらゆる数の適切なプログラミング言語において記述され得る。例えば、ハイパーテキストマークアップ言語（ＨＴＭＬ）、ダイナミックＨＴＭＬ、拡張可能マークアップ言語（ＸＭＬ）、拡張可能スタイルシート言語（ＸＳＬ）、文章スタイル意味指定言語（ＤＳＳＳＬ）、カスケーディングスタイルシート（ＣＳＳ）、同期マルチメディア統合言語（ＳＭＩＬ）、無線マークアップ言語（ＷＭＬ）、ＪａｖａＴＭ、ＪｉｎｉＴＭ、Ｃ、Ｃ＋＋、Ｐｅｒｌ、ＵＮＩＸシェル、ビジュアルベーシックスクリプト、仮想現実マークアップ言語（ＶＲＭＬ）、ＣｏｌｄＦｕｓｉｏｎＴＭまたは他のコンパイラ、アセンブラ、インタープリタまたは他のコンピュータ言語もしくはプラットフォーム、といったものである。

このように、ファイルシステムにおけるオブジェクトのガベージコレクションのための方法が開示される。この方法は、参照カウント技術と失効時間の伝播のハイブリッド（ｈｙｂｒｉｄ）に基づくものである。

所定の実施例に関して具体化が説明されてきたが、本アプリケーションのより広い精神と範囲から逸脱することなく、これらの実施例に対して種々の変更および変形がなされ得ることは明白であろう。従って、明細書と図面は、限定的な意味より、むしろ説明的なものとして考慮されるべきである。

Claims

ファイルシステムにおけるオブジェクトのハイブリッドガベージコレクションのためのコンピュータで実行可能な方法であって、
参照カウンタを前記ファイルシステムにおけるオブジェクトと関連付けるステップと、
失効時間を前記オブジェクトと関連付けるステップと、
バージョン識別子を前記オブジェクトと関連付けるステップと、
前記オブジェクトの前記参照カウンタがゼロでない間、前記オブジェクトを前記ファイルシステムの中に保持するステップと、
を含み、
前記オブジェクトの前記参照カウンタがゼロであることの決定に応じて、前記オブジェクトに関連付けされた前記失効時間まで、前記オブジェクトを前記ファイルシステムの中に保持する、
方法。
前記オブジェクトを参照している新たなリファレンスが追加されたことに応じて、前記オブジェクトに関連付けされた前記参照カウンタを１だけ増やす、
請求項１に記載の方法。
前記方法は、さらに、
前記オブジェクトを参照している既存のリファレンスに関連付けされた第２の参照カウンタがゼロであると決定するステップ、を含み、
前記決定に応じて、
前記オブジェクトの前記参照カウンタを１だけ減らし、かつ、
前記オブジェクトに関連付けされた前記失効時間を、前記オブジェクトの失効時間および前記リファレンスの失効時間のうち最新のものに設定する、
請求項１に記載の方法。
前記方法は、さらに、
前記オブジェクトに関連付けされた前記参照カウンタがゼロであり、かつ、前記オブジェクトを参照している新たなリファレンスが追加されて、前記新たなリファレンスに関連付けされた新たな参照カウンタがゼロでない、と決定するステップ、を含み、
前記決定に応じて、
前記オブジェクトに関連付けされた前記参照カウンタを１だけ増やし、かつ、
前記オブジェクトに関連付けされた前記失効時間を、前記オブジェクトの失効時間および前記新たなリファレンスの失効時間のうち最新のものに設定する、
請求項１に記載の方法。
前記バージョン識別子は、前記ファイルシステムの変化と共に単調に増加され、かつ、
前記ファイルシステムの前記変化は、前記ファイルシステムに少なくとも一つの新たなオブジェクトを追加することに対応している、
請求項１に記載の方法。
前記方法は、さらに、
前記少なくとも一つの新たなオブジェクト、および、前記少なくとも一つの新たなオブジェクトの追加により前記ファイルシステムに追加された全てのオブジェクトに対して、同一のバージョン識別子を割り当てるステップ、
を含む、請求項５に記載の方法。
前記方法は、さらに、
前記オブジェクトに関連付けされた前記バージョン識別子が、既定の最大バージョンより大きい間、前記オブジェクトを前記ファイルシステムの中に保持するステップ、
を含む、請求項１に記載の方法。
前記方法は、さらに、
オブジェクトのバージョンを続けて参照するように、リファレンスオブジェクトのチェインを提供するステップ、を含み、
前記チェインにおける２番目のリファレンスオブジェクトは、前記オブジェクトの１番目のバージョンを参照し、
前記チェインにおける最後のリファレンスオブジェクトは、前記オブジェクトの最後から２番目のバージョンを参照し、
前記チェインにおける１番目のリファレンスオブジェクトに関連付けされた参照カウンタが１に設定され、
前記チェインにおける最後のリファレンスオブジェクトに関連付けされた参照カウンタが１に設定され、かつ、
前記チェインにおける前記１番目のリファレンスオブジェクトと前記最後のリファレンスオブジェクトの間にあるリファレンスオブジェクトに関連付けされた参照カウンタがゼロに設定される、
請求項１に記載の方法。
前記方法は、さらに、
前記オブジェクトの新たなバージョンが前記ファイルシステムに追加されたことに応じて、
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた失効時間を決定し、
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた前記参照カウンタをゼロに設定し、かつ、
前記チェインの最後に新たなリファレンスオブジェクトを追加し、前記新たなリファレンスオブジェクトは前記オブジェクトの前記新たなバージョンを参照している、
請求項８に記載の方法。
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた前記失効時間は、前記オブジェクトの前記最後のバージョンおよび前記オブジェクトの前記新たなバージョンの追加の間の時間期間に基づいて計算される、
請求項９に記載の方法。
一つまたはそれ以上のプロセッサによって実行されると、ファイルシステムにおけるオブジェクトのハイブリッドガベージコレクションのための方法を前記一つまたはそれ以上のプロセッサに実施させるインストラクション、が保管された有形のコンピュータで読取り可能な媒体であって、
前記方法は、
参照カウンタを前記ファイルシステムにおけるオブジェクトと関連付けるステップと、
失効時間を前記オブジェクトと関連付けるステップと、
バージョン識別子を前記オブジェクトと関連付けるステップと、
前記オブジェクトの前記参照カウンタがゼロでない間、前記オブジェクトを前記ファイルシステムの中に保持するステップと、
前記オブジェクトの前記参照カウンタがゼロであることの決定に応じて、前記オブジェクトに関連付けされた前記失効時間まで、前記オブジェクトを前記ファイルシステムの中に保持するステップと、
を含む、有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記オブジェクトを参照している新たなリファレンスが追加されたことに応じて、前記オブジェクトに関連付けされた前記参照カウンタを１だけ増やすステップ、
を含む、請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記オブジェクトを参照している既存のリファレンスに関連付けされた第２の参照カウンタがゼロであると決定するステップ、を含み、
前記決定に応じて、
前記オブジェクトの前記参照カウンタを１だけ減らし、かつ、
前記オブジェクトに関連付けされた前記失効時間を、前記オブジェクトの失効時間および前記リファレンスの失効時間のうち最新のものに設定する、
請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記オブジェクトに関連付けされた前記参照カウンタがゼロであり、かつ、前記オブジェクトを参照している新たなリファレンスが追加されて、前記新たなリファレンスに関連付けされた新たな参照カウンタがゼロでない、と決定するステップ、を含み、
前記決定に応じて、
前記オブジェクトに関連付けされた前記参照カウンタを１だけ増やし、かつ、
前記オブジェクトに関連付けされた前記失効時間を、前記オブジェクトの失効時間および前記新たなリファレンスの失効時間のうち最新のものに設定する、
請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記バージョン識別子は、前記ファイルシステムの変化と共に単調に増加され、かつ、
前記ファイルシステムの前記変化は、前記ファイルシステムに少なくとも一つの新たなオブジェクトを追加することに対応している、
請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記少なくとも一つの新たなオブジェクト、および、前記少なくとも一つの新たなオブジェクトの追加により前記ファイルシステムに追加された全てのオブジェクトに対して、同一のバージョン識別子を割り当てるステップ、
請求項１５に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記オブジェクトに関連付けされた前記バージョン識別子が、既定の最大バージョンより大きい間、前記オブジェクトを前記ファイルシステムの中に保持するステップ、
を含む、請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
オブジェクトのバージョンを続けて参照するように、リファレンスオブジェクトのチェインを提供するステップ、を含み、
前記チェインにおける２番目のリファレンスオブジェクトは、前記オブジェクトの１番目のバージョンを参照し、
前記チェインにおける最後のリファレンスオブジェクトは、前記オブジェクトの最後から２番目のバージョンを参照し、
前記チェインにおける１番目のリファレンスオブジェクトに関連付けされた参照カウンタが１に設定され、
前記チェインにおける最後のリファレンスオブジェクトに関連付けされた参照カウンタが１に設定され、かつ、
前記チェインにおける前記１番目のリファレンスオブジェクトと前記最後のリファレンスオブジェクトの間にあるリファレンスオブジェクトに関連付けされた参照カウンタがゼロに設定される、
請求項１１に記載の有形のコンピュータで読取り可能な媒体。
前記方法は、さらに、
前記オブジェクトの新たなバージョンが前記ファイルシステムに追加されたことに応じて、
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた失効時間を決定し、
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた前記参照カウンタをゼロに設定し、かつ、
前記チェインの最後に新たなリファレンスオブジェクトを追加し、前記新たなリファレンスオブジェクトは前記オブジェクトの前記新たなバージョンを参照している、
請求項１８に記載の有形のコンピュータで読取り可能な媒体。
前記チェインにおける前記最後のリファレンスオブジェクトに関連付けされた前記失効時間は、前記オブジェクトの前記最後のバージョンおよび前記オブジェクトの前記新たなバージョンの追加の間の時間期間に基づいて計算される、
請求項１９に記載の有形のコンピュータで読取り可能な媒体。