(57)【特許請求の範囲】
【請求項１】
少なくとも１つのプロセッサに連結されたストレージデバイスを含む文書管理システムで更新されたファイルへのアクセスを提供する方法であって、
フラッシュ変換階層（ＦＴＬ：ｆｌａｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）マップは、ファイルシステムによって維持される論理的ページナンバー（ＬＰＮ：ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）と前記ストレージデバイスによって維持される物理的ページナンバー（ＰＰＮ：ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）との間のＦＴＬによって維持され、
前記方法は、
第１ファイルへのアクセスが維持される間、前記第１ファイルの変更されたコンテンツ及び前記変更されたコンテンツがコピーされる第２ファイルの生成を含む更新（アップデート）を受信するアプリケーションに応答して送信される第１コマンドを、前記プロセッサから前記ストレージデバイスによって受信する段階であって、前記第１コマンドのパラメータは、前記第１ファイルに対応するＬＰＮの第１リスト及び前記第２ファイルに対応するＬＰＮの第２リストを含み、前記ＬＰＮの第１リストは、前記ストレージデバイスにおける前記第１ファイルの格納位置を示すＰＰＮの第１リストにマッピングされ、前記ＬＰＮの第２リストは、前記ストレージデバイスにおける前記第２ファイルの格納位置を示すＰＰＮの第２リストにマッピングされる前記受信する段階と、
前記ＬＰＮの第１リストが前記ＰＰＮの第２リストに順にマッピングされるように前記ＬＰＮの第１リストをアトミックに（ａｔｏｍｉｃａｌｌｙ）再マッピングする段階であって、前記ＬＰＮの第１リストの各ＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップにマッピングが生成される前記再マッピングする段階と、
前記再マッピングする段階とは非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）、前記ＰＰＮの第１リストへの前記ＬＰＮの第１リストのマッピングを除去（ｔｒｉｍｍｉｎｇ）する段階であって、前記ＬＰＮの第１リストのすべてのＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第１リストの対応するＰＰＮとの間の前記ＦＴＬマップでマッピングが解除（ｒｅｍｏｖｅ）される前記除去する段階と、
前記ＰＰＮの第２リストへの前記ＬＰＮの第２リストのマッピングをアンマッピング（ｕｎｍａｐｐｉｎｇ）する段階であって、前記ＬＰＮの第２リストのすべてのＬＰＮに対し、前記ＬＰＮの第２リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間のマッピングが、前記ＦＴＬマップで解除される前記アンマッピングする段階と、を含み、
ガベージコレクションによってページが回収（ｒｅｃｌａｉｍ）されるまで、非同期的に除去（ｔｒｉｍ）される前記ページにアクセスする同時的プロセス（ｃｏｎｃｕｒｒｅｎｔ  ｐｒｏｃｅｓｓｅｓ）を可能にする弱いマッピングを提供する段階と、
前記ガベージコレクション、書き込みコマンド、又はトリムコマンドにより、前記弱いマッピングを解除（ｒｅｍｏｖｉｎｇ）する段階と、をさらに含むことを特徴とする方法。
【請求項２】
前記第１コマンドは、ＳＷＡＴ（ｓｗａｐ  ａｎｄ  ｔｒｉｍ）コマンドを含み、ＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）に発行されることを特徴とする請求項１に記載の方法。
【請求項３】
前記ＳＷＡＴコマンドは、アプリケーション又はオペレーティングシステムによる呼び出しに応答して、ストレージデバイスドライバＡＰＩから前記ストレージデバイスに発行されることを特徴とする請求項２に記載の方法。
【請求項４】
前記ＬＰＮの第１リスト及び前記ＬＰＮの第２リストに含まれるＬＰＮは、前記ＬＰＮの第１リスト及び前記ＬＰＮの第２リストによって決められた順序に沿ってアトミックに再マッピングされることを特徴とする請求項２に記載の方法。
【請求項５】
システムであって、
フラッシュ変換階層（ＦＴＬ：ｆｌａｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）マップは、ファイルシステムによって維持される論理的ページナンバー（ＬＰＮ：ｌｏｇｉｋａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）とストレージデバイスによって維持される物理的ページナンバー（ＰＰＮ：ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）との間のＦＴＬによって維持され、
前記システムは、
プロセッサ及びメモリを含むコンピュータと、
前記プロセッサと前記メモリの外部に位置する前記ストレージデバイスと、を備え、
前記ストレージデバイスは、
第１ファイルへのアクセスが維持される間、前記第１ファイルの変更されたコンテンツ及び前記変更されたコンテンツがコピーされる第２ファイルの生成を含む更新（アップデート）を受信するアプリケーションに応答して送信される第１コマンドを、前記プロセッサから受信するように構成され、
前記第１コマンドのパラメータは、前記第１ファイルに対応するＬＰＮの第１リスト及び前記第２ファイルに対応するＬＰＮの第２リストを含み、
前記ＬＰＮの第１リストは、前記ストレージデバイスにおける前記第１ファイルの格納位置を示すＰＰＮの第１リストにマッピングされ、前記ＬＰＮの第２リストは、前記ストレージデバイスにおける前記第２ファイルの格納位置を示すＰＰＮの第２リストにマッピングされ、
前記ストレージデバイスは、
前記ＬＰＮの第１リストが前記ＰＰＮの第２リストに順にマッピングされるように前記ＬＰＮの第１リストをアトミックに（ａｔｏｍｉｃａｌｌｙ）再マッピングするように構成され、
前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップに、前記ＬＰＮの第１リストの各ＬＰＮに対するマッピングが生成され、
前記ストレージデバイスは、
前記再マッピングの実行とは非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）、前記ＰＰＮの第１リストへの前記ＬＰＮの第１リストのマッピングを除去（ｔｒｉｍｍｉｎｇ）するように構成され、
前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第１リストの対応するＰＰＮとの間の前記ＦＴＬマップで、前記ＬＰＮの第１リストのすべてのＬＰＮに対するマッピングが解除（ｒｅｍｏｖｅ）され、
前記ストレージデバイスは、
前記第２リストのＰＰＮへの前記ＬＰＮの第２リストの前記マッピングをアンマッピング（ｕｎｍａｐｐｉｎｇ）するように構成され、
前記ＬＰＮの第２リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップで、前記ＬＰＮの第２リストのすべてのＬＰＮに対するマッピングが解除され、
ガベージコレクションによってページが回収（ｒｅｃｌａｉｍ）されるまで、前記非同期的に除去（ｔｒｉｍ）される前記ページにアクセスする同時的プロセス（ｃｏｎｃｕｒｒｅｎｔ  ｐｒｏｃｅｓｓｅｓ）を可能にする弱いマッピングが提供され、
前記弱いマッピングは、前記ガベージコレクション、書き込みコマンド、又はトリムコマンドによって解除（ｒｅｍｏｖｅ）されることを特徴とするシステム。
【請求項６】
前記第１コマンドは、ＳＷＡＴ（ｓｗａｐ  ａｎｄ  ｔｒｉｍ）コマンドを含み、ＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）を介して発行されることを特徴とする請求項５に記載のシステム。
【請求項７】
前記ＬＰＮの第１リスト及び前記ＬＰＮの第２リストに含まれるＬＰＮは、前記ＬＰＮの第１リスト及び前記ＬＰＮの第２リストによって決められた順序に沿ってアトミックに再マッピングされることを特徴とする請求項６に記載のシステム。
【請求項８】
前記ＳＷＡＴコマンドは、アプリケーション又はオペレーティングシステムによる呼び出しに応答して、ストレージデバイスドライバＡＰＩから前記ストレージデバイスに発行されることを特徴とする請求項６に記載のシステム。
【請求項９】
少なくとも１つのプロセッサに連結されたストレージデバイスを含む文書管理システムで更新されたファイルへのアクセスを提供するプログラムが記載されたコンピュータ読み取り可能な非一時的記録媒体であって、
フラッシュ変換階層（ＦＴＬ：ｆｌａｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）マップは、ファイルシステムによって維持される論理的ページナンバー（ＬＰＮ：ｌｏｇｉｋａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）と前記ストレージデバイスによって維持される物理的ページナンバー（ＰＰＮ：ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）との間のＦＴＬによって維持され、
前記プログラムは、
第１ファイルへのアクセスが維持される間、前記第１ファイルの変更されたコンテンツ及び前記変更されたコンテンツがコピーされる第２ファイルの生成を含む更新（アップデート）を受信するアプリケーションに応答して送信される第１コマンドを、前記プロセッサから前記ストレージデバイスによって受信する段階であって、前記第１コマンドのパラメータは、前記第１ファイルに対応するＬＰＮの第１リスト及び前記第２ファイルに対応するＬＰＮの第２リストを含み、前記ＬＰＮの第１リストは、前記ストレージデバイスにおける前記第１ファイルの格納位置を示すＰＰＮの第１リストにマッピングされ、前記ＬＰＮの第２リストは、前記ストレージデバイスにおける前記第２ファイルの格納位置を示すＰＰＮの第２リストにマッピングされる前記受信する段階と、
前記ＬＰＮの第１リストが前記ＰＰＮの第２リストに順にマッピングされるように前記ＬＰＮの第１リストをアトミックに（ａｔｏｍｉｃａｌｌｙ）再マッピングする段階であって、前記ＬＰＮの第１リストの各ＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップにマッピングが生成される前記再マッピングする段階と、
前記再マッピングする段階とは非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）、前記ＰＰＮの第１リストへの前記ＬＰＮの第１リストのマッピングを除去（ｔｒｉｍｍｉｎｇ）する段階であって、前記ＬＰＮの第１リストのすべてのＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第１リストの対応するＰＰＮとの間の前記ＦＴＬマップでマッピングが解除（ｒｅｍｏｖｅ）される前記除去する段階と、
前記ＰＰＮの第２リストへの前記ＬＰＮの第２リストのマッピングをアンマッピング（ｕｎｍａｐｐｉｎｇ）する段階であって、前記ＬＰＮの第２リストのすべてのＬＰＮに対し、前記ＬＰＮの第２リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間のマッピングが、前記ＦＴＬマップで解除される前記アンマッピングする段階と、をコンピュータに実行させ、
前記プログラムは、ガベージコレクションによってページが回収（ｒｅｃｌａｉｍ）されるまで、前記非同期的に除去（ｔｒｉｍ）される前記ページにアクセスする同時的プロセス（ｃｏｎｃｕｒｒｅｎｔ  ｐｒｏｃｅｓｓｅｓ）を可能にする弱いマッピングを提供する段階と、
前記ガベージコレクション、書き込みコマンド、又はトリムコマンドにより、前記弱いマッピングを解除（ｒｅｍｏｖｉｎｇ）する段階と、をさらにコンピュータに実行させることを特徴とするコンピュータ読み取り可能な非一時的記録媒体。
【請求項１０】
少なくとも一つのプロセッサ含む外部コンピュータに連結されたストレージデバイスによって遂行される、更新されたファイルへのアクセスを提供する方法であって、
フラッシュ変換階層（ＦＴＬ：ｆｌａｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）マップは、ファイルシステムによって維持される論理的ページナンバー（ＬＰＮ：ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）と前記ストレージデバイスによって維持される物理的ページナンバー（ＰＰＮ：ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）との間のＦＴＬによって維持され、
前記方法は、
第１ファイルへのアクセスが維持される間、前記第１ファイルの変更されたコンテンツ及び前記変更されたコンテンツがコピーされる第２ファイルの生成を含む更新（アップデート）を受信するアプリケーションに応答して送信される第１コマンドを、前記プロセッサから前記ストレージデバイスによって受信する段階であって、前記第１コマンドのパラメータは、前記第１ファイルに対応するＬＰＮの第１リスト及び前記第２ファイルに対応するＬＰＮの第２リストを含み、前記ＬＰＮの第１リストは、前記ストレージデバイスにおける前記第１ファイルの格納位置を示すＰＰＮの第１リストにマッピングされ、前記ＬＰＮの第２リストは、前記ストレージデバイスにおける前記第２ファイルの格納位置を示すＰＰＮの第２リストにマッピングされる前記受信する段階と、
前記ＬＰＮの第１リストが前記ＰＰＮの第２リストに順にマッピングされるように前記ＬＰＮの第１リストをアトミックに（ａｔｏｍｉｃａｌｌｙ）再マッピングする段階であって、前記ＬＰＮの第１リストの各ＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップにマッピングが生成される前記再マッピングする段階と、
前記再マッピングする段階とは非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）、前記ＰＰＮの第１リストへの前記ＬＰＮの第１リストのマッピングを除去（ｔｒｉｍｍｉｎｇ）する段階であって、前記ＬＰＮの第１リストのすべてのＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第１リストの対応するＰＰＮとの間の前記ＦＴＬマップでマッピングが解除（ｒｅｍｏｖｅ）される前記除去する段階と、
前記ＰＰＮの第２リストへの前記ＬＰＮの第２リストのマッピングをアンマッピング（ｕｎｍａｐｐｉｎｇ）する段階であって、前記ＬＰＮの第２リストのすべてのＬＰＮに対し、前記ＬＰＮの第２リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間のマッピングが、前記ＦＴＬマップで解除される前記アンマッピングする段階と、を含み、
ガベージコレクションによってページが回収（ｒｅｃｌａｉｍ）されるまで、前記非同期的に除去（ｔｒｉｍ）される前記ページにアクセスする同時的プロセス（ｃｏｎｃｕｒｒｅｎｔ  ｐｒｏｃｅｓｓｅｓ）を可能にする弱いマッピングを提供する段階と、
前記ガベージコレクション、書き込みコマンド、又はトリムコマンドにより、前記弱いマッピングを解除（ｒｅｍｏｖｉｎｇ）する段階と、をさらに含むことを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はファイル管理システムに関し、更に詳細には、更新されたファイルへのアクセスを提供する方法、それに係るコンピュータ、及びコンピュータ読出し可能である媒体に格納された実行可能なソフトウェア製品に関する。
【背景技術】
【０００２】
ファイル管理システムはファイルの最新に更新されたバージョンを追跡するためにデータ構造をアップデート（ｕｐｄａｔｅ、以下、「更新」という）する。このプロセスにおいて、一部のシステムは、古いバージョン（ｔｈｅ  ｏｌｄｅｒ  ｖｅｒｓｉｏｎ）に上書きする代わりにファイルの他のバージョンを生成し、暫らくの間、ファイルの古いバージョンを維持する。結果的にシステムは、新しいバージョンにファイルが更新されている最中であっても、ファイルの古いバージョンを読出しアクセスできる。例えば、使用者がブログページを更新する場合、使用者がブログページを更新している最中に他のユーザはブログページの古いバージョンを読出しできる。システムは、新しいファイルにアクセスし、古いファイルを新しいファイルにより置換するためにシステム情報を更新する必要がある。通常、この更新は、システムのデータ構造に対して一連のカスケード型の更新を引き起こし、これはストレージに多くの書込みを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
従って、上記の問題を解決さるためになされた本発明の目的は、システムのデータ構造に対して一連のカスケード型の更新を引き起こすことなく、更新されたファイルへの読出しアクセスを提供できる改良された方法及びシステムを提供できることにある。
【０００４】
本発明の目的は向上された寿命、向上された信頼性、及び向上された性能を有するファイルアクセス方法、コンピュータ、及びコンピュータ読出し可能である媒体に実行可能なソフトウェア製品が提供することにある。
【課題を解決するための手段】
【０００５】
本発明の一実施形態は、論理的ページナンバ（ＬＰＮ、ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）の第１リスト及び更新のための論理的ページナンバ（ＬＰＮ）の第２リストを受信することに応答して、少なくとも１つのプロセッサによって遂行される、更新されたファイルに対するアクセスを提供する方法に係る。
少なくとも１つのプロセッサに連結されたストレージデバイスを含む文書管理システムで更新されたファイルへのアクセスを提供する方法であって、フラッシュ変換階層（ＦＴＬ：ｆｌａｓｈ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）マップは、ファイルシステムによって維持される論理的ページナンバー（ＬＰＮ：ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）と前記ストレージデバイスによって維持される物理的ページナンバー（ＰＰＮ：ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒ）との間のＦＴＬによって維持され、前記方法は、第１ファイルへのアクセスが維持される間、前記第１ファイルの変更されたコンテンツ及び前記変更されたコンテンツがコピーされる第２ファイルの生成を含む更新（アップデート）を受信するアプリケーションに応答して送信される第１コマンドを、前記プロセッサから前記ストレージデバイスによって受信する段階であって、前記第１コマンドのパラメータは、前記第１ファイルに対応するＬＰＮの第１リスト及び前記第２ファイルに対応するＬＰＮの第２リストを含み、前記ＬＰＮの第１リストは、前記ストレージデバイスにおける前記第１ファイルの格納位置を示すＰＰＮの第１リストにマッピングされ、前記ＬＰＮの第２リストは、前記ストレージデバイスにおける前記第２ファイルの格納位置を示すＰＰＮの第２リストにマッピングされる前記受信する段階と、前記ＬＰＮの第１リストが前記ＰＰＮの第２リストに順にマッピングされるように前記ＬＰＮの第１リストをアトミックに（ａｔｏｍｉｃａｌｌｙ）再マッピングする段階であって、前記ＬＰＮの第１リストの各ＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間の前記ＦＴＬマップにマッピングが生成される前記再マッピングする段階と、前記再マッピングする段階とは非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）、前記ＰＰＮの第１リストへの前記ＬＰＮの第１リストのマッピングを除去（ｔｒｉｍｍｉｎｇ）する段階であって、前記ＬＰＮの第１リストのすべてのＬＰＮに対し、前記ＬＰＮの第１リストのＬＰＮと前記ＰＰＮの第１リストの対応するＰＰＮとの間の前記ＦＴＬマップでマッピングが解除（ｒｅｍｏｖｅ）される前記除去する段階と、前記ＰＰＮの第２リストへの前記ＬＰＮの第２リストのマッピングをアンマッピング（ｕｎｍａｐｐｉｎｇ）する段階であって、前記ＬＰＮの第２リストのすべてのＬＰＮに対し、前記ＬＰＮの第２リストのＬＰＮと前記ＰＰＮの第２リストの対応するＰＰＮとの間のマッピングが、前記ＦＴＬマップで解除される前記アンマッピングする段階と、を含み、ガベージコレクションによってページが回収（ｒｅｃｌａｉｍ）されるまで、非同期的に除去（ｔｒｉｍ）される前記ページにアクセスする同時的プロセス（ｃｏｎｃｕｒｒｅｎｔ  ｐｒｏｃｅｓｓｅｓ）を可能にする弱いマッピングを提供する段階と、前記ガベージコレクション、書き込みコマンド、又はトリムコマンドにより、前記弱いマッピングを解除（ｒｅｍｏｖｉｎｇ）する段階と、をさらに含むことを特徴とする。
【発明の効果】
【０００６】
本発明によれば、
ＬＰＮの第１リストはＰＰＮの第１リストにマッピングされ、ＬＰＮの第２リストはＰＰＮの第２リストにマッピングされた後、ＬＰＮの第１リストをアトミックに再マッピングしてＬＰＮの第１リストをＰＰＮの第２リストにマッピングし、ＬＰＮの第１リストからＰＰＮの第１リストへのマッピングを非同期的に除去するので、システムのデータ構造に対して一連のカスケード型の更新を引き起こすことなく、更新されたファイルへの読出しアクセスを提供できる。
よって、向上された寿命、向上された信頼性、及び向上された性能を有するファイルアクセス方法、コンピュータ、及びコンピュータ読出し可能である媒体に実行可能なソフトウェア製品が提供できる。
【図面の簡単な説明】
【０００７】
【図１】本発明の実施形態によるファイル管理システムを示すブロック図である。
【図２】ファイルを更新するための、従来一般的なファイル管理システムを示す図面である。
【図３】本発明の実施形態によって更新の間にファイルに対するアクセスを提供するためのファイル管理システムによって遂行される手続を示す順序図である。
【図４】図３の手続を図式的に示す図面である。
【図５】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図６】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図７】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図８】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図９】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図１０】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図１１】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図１２】フォワードマッピングテーブルＦＭＴ、物理的ページナンバのリスト、及びリバースマッピングテーブルＲＭＴの多様な状態を示す図面である。
【図１３】使用されないページに対する例示的なＳＷＡＴコマンドを示す。
【図１４】マッピングがない基本論理的ページナンバに対する例示的なＳＷＡＴコマンドを示す。
【図１５】反復的なＳＷＡＴコマンドの例を示す。
【発明を実施するための形態】
【０００８】
添付された図面に図解した本発明の実施例を詳細に説明する。類似な構成要素は類似な参照番号を称する。以下に、本発明の技術的な思想を説明するために図面を参照して実施形態を説明する。
【０００９】
本発明の長所、及び特徴、及びこれを達成するための方法は以下の実施形態の詳細な説明及び添付された図面を参照することで、容易に理解できよう。しかし、本発明の技術的な思想は多様な他の形態に具現でき、本明細書に開示された実施形態に限定されない。本実施形態は、むしろ、本発明の開示が完璧になされ、当業者に本発明の技術的な思想が完全に伝達されるように提供される。本発明の技術的な思想は添付された特許請求範囲によって定義される。
【００１０】
図面で階層（ｌａｙｅｒｓ）及び領域（ｒｅｇｉｏｎｓ）の厚さは明確性のために誇張される場合がある。
【００１１】
本文（特に以下の特許請求範囲）における単数用語及び類似な用語の使用は、本文中において異なって言及されるか、或いは明確に文脈と矛盾しない限り、単数及び複数を全て含むと理解される。異なって言及されない限り、“含む”（ｃｏｍｐｒｉｓｉｎｇ、ｈａｖｉｎｇ、ｉｎｃｌｕｄｉｎｇ、及びｃｏｎｔａｉｎｉｎｇ）の用語は開放形の意味として理解される。
【００１２】
本文で使用される構成要素（ｃｏｍｐｏｎｅｎｔ、以下、「要素」という）又はモジュール（ｍｏｄｕｌｅ）の用語は、特定動作を遂行するＦＰＧＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙ）又はＡＳＩＣ（ａｐｐｌｉｃａｔｉｏｎ  ｓｐｅｃｉｆｉｃ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）のようなハードウェア要素、又はソフトウェア要素を意味する。しかし、これに限定されない。
要素又はモジュールは有利にアドレス指定可能なストレージ媒体内に位置するように構成され、１つ又はそれ以上のプロセッサ上で遂行するように構成できる。即ち、例えば、要素又はモジュールは、ソフトウェア要素、客体指向のソフトウェア要素（ｏｂｊｅｃｔ−ｏｒｉｅｎｔｅｄ  ｓｏｆｔｗａｒｅ  ｃｏｍｐｏｎｅｎｔｓ）、クラス要素（ｃｌａｓｓ  ｃｏｍｐｏｎｅｎｔｓ）、及び作業要素（ｔａｓｋ  ｃｏｍｐｏｎｅｎｔｓ）、プロセス（ｐｒｏｃｅｓｓｅｓ）、機能（ｆｕｎｃｔｉｏｎｓ）、属性（ａｔｔｒｉｂｕｔｅｓ）、手続（ｐｒｏｃｅｄｕｒｅｓ）、サブルーチン（ｓｕｂｒｏｕｔｉｎｅｓ）、プログラムコードのセグメント（ｓｅｇｍｅｎｔｓ  ｏｆ  ｐｒｏｇｒａｍ  ｃｏｄｅ）、ドライバ（ｄｒｉｖｅｒｓ）、ファームウェア（ｆｉｒｍｗａｒｅ）、マイクロコード（ｍｉｃｒｏｃｏｄｅ）、回路（ｃｉｒｃｕｉｔｒｙ）、データ（ｄａｔａ）、データベース（ｄａｔａｂａｓｅｓ）、データ構造（ｄａｔａ  ｓｔｒｕｃｔｕｒｅｓ）、テーブル（ｔａｂｌｅｓ）、アレイ（ａｒｒａｙｓ）等のような要素を含むことができる。要素又はモジュールのために提供される機能は幾つかの要素又はモジュールに組合わされる。
【００１３】
異なって定義されない限り、本文で使用される全ての技術的、科学的用語は本発明が属する技術分野において通常の技術者によって共通的に理解される同一な意味を有する。本文で提供される例示的な用語又は全ての例示の使用は単なる本発明を説明するために使用され、本発明の特許請求の範囲が異なって限定されない。更に、特に異なって定義されない限り、一般的に使用される辞書で定義された全ての用語は異なって定義されない。
【００１４】
図１は本発明の実施形態によるファイル管理システムを示すブロック図である。ファイル管理システム１０は電子文書又はファイルを追跡し、格納するコンピュータ１２を含む。一実施形態で、コンピュータ１２はデスクトップコンピュータ、ラップトップ、又はワークステーションを含む。他の実施形態で、コンピュータ１２はネットワーク（未図示）を通じてクライアントコンピュータと通信するサーバを含む。コンピュータ１２は高速ストレージ１８（例えば、ソリッドステートドライブ（ＳＳＤ））のようなストレージディバイス、プロセッサ１４、及びメモリ１６を含む一般的なコンピュータを構成する要素を含む。
【００１５】
プロセッサ１４は１つ又はそれ以上のコアを有するシングルプロセッサ又はマルチプロセッサを含む。プロセッサ１４はメモリ１６からのプログラム命令語を実行する。ソフトウェアの例示的な形態はアプリケーション２０、運営システム（ＯＳ）２２、ファイルシステム２４、及び高速ストレージ１８のためにデバイスドライバ・アプリケーションプログラミングインタフェイス２６（ｄｅｖｉｃｅ  ｄｒｉｖｅｒ  ＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ））を含む。
【００１６】
本発明が属する技術分野で広く公知されているように、アプリケーション２０はプロセッサ１４によって実行されて、コンピュータ１２の運転中にコンピュータ１２に作業を遂行させるコンピュータソフトウェアを代表する。例えば、アプリケーション２０はＷｅｂブラウザ、ワードプロセッサ、及びデータベースプログラムを含む。一般的に、アプリケーション２０はファイル２８を生成し、変更、又は更新する。運営システム２２はコンピュータ１２の動作を制御し、管理するシステムソフトウェアである。運営システム２２はマイクロソフトウインドゥズ（Ｗｉｎｄｏｗｓ）、Ｍａｃ  ＯＳ  Ｘ、及びＬｉｎｕｘ（登録商標）を含む。
【００１７】
ファイルシステム２４はファイル２８のような情報を高速ストレージ１８のようなデータ格納装置にどのようにして格納し、検索し、更新するかを制御するソフトウェアである。一部のアプリケーション／ファイル形態は、ファイル２８にページのようなデータが高速ストレージ１８又は他のコンピュータストレージの装置の何処に格納されるかを特定するために論理的ページナンバリング（ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒｉｎｇ）を使用する。
更に詳細には、論理的ページナンバリング（ｌｏｇｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒｉｎｇ）とは、論理的ページナンバ（ＬＰＮ）３０を高速ストレージ１８上の特定格納位置にマッピングしてファイル２８内のページに割当てる概念である。
【００１８】
デバイスドライバ・アプリケーションプログラミングインタフェイスＡＰＩ（ａｐｐｌｉｃａｔｉｏｎ  ｐｒｏｇｒａｍｍｉｎｇ  ｉｎｔｅｒｆａｃｅ）２６は、ここでは、アプリケーション２０、運営システム２２、及びファイルシステム２４が高速ストレージ１８と通信できるようにする。デバイスドライバＡＰＩ（２６）は高速ストレージ１８からデータを受信するか、或いは格納するためのコマンドを提供する。
【００１９】
一実施形態で、高速ストレージ１８は高速ストレージ１８に格納されたページのアドレスを提供するために物理的ページナンバリング（ｐｈｙｓｉｃａｌ  ｐａｇｅ  ｎｕｍｂｅｒｉｎｇ）を使用する。アドレスのこのような形態は特定の格納位置にマッピングできる物理的ページナンバ（ＰＰＮ）３２と称される。一実施形態で、高速ストレージ１８はＳＳＤ（ｓｏｌｉｄ−ｓｔａｔｅ  ｄｒｉｖｅ、又は、ｓｏｌｉｄ−ｓｔａｔｅ  ｄｉｓｋ）を含む。ＳＳＤはメモリとして集積回路を使用してデータを持続的に格納するファイル２８などのデータ格納装置である。一実施形態で、ＳＳＤはＮＡＮＤフラッシュメモリ又はランダムアクセスメモリＲＡＭを使用する。
【００２０】
一実施形態で、高速ストレージ１８はコンピュータ１２に論理セクタインタフェイスを提供しながら、高速ストレージ１８を管理するファイル変換階層ＦＴＬ（ｆｉｌｅ  ｔｒａｎｓｌａｔｉｏｎ  ｌａｙｅｒ）３４、又は同等の構成を更に含む。このように、ＦＴＬ（３４）はファイルシステム２４によって維持される論理的ページナンバ（ＬＰＮ）３０及び高速ストレージ１８によって維持される物理的ページナンバ（ＰＰＮ）３２のマッピング関係を制御する。他の実施形態で、例示的な実施形態はＳＳＤと他の形態のストレージ装置を使用する。
【００２１】
図２は、ファイルを更新するための、従来一般的なファイル管理システムを示す図面である。図示された実施形態はアプリケーションが使用者のマルチページブログ（ｍｕｌｔｉｐａｇｅ  ｂｌｏｇ）を示すファイル２００を維持する場合を想定する。使用者がブログを更新するたびに、アプリケーションはファイル２００をメモリに読出し、これによってコンテンツを変更する。更新が遂行される間に、システムは変更されたファイルがコピーされた新しいファイル２０４を生成する。このように使用者がブログを更新している間に、他の使用者は相変わらず古いファイル２０２（ｏｌｄ  ｆｉｌｅ）にアクセスし、読出しができる。使用者がブログ作成を終了し、ページを提出する時点で、アプリケーションは新しいファイル２０４にスイッチし、古いファイル２０２を削除する。
【００２２】
ファイルが実際に格納されたストレージシステムが物理的ページナンバ（ＰＰＮ）２０８を維持する一方、ファイルシステムは古いファイル２０２及び新しいファイル２０４のページのために論理的ページナンバ（ＬＰＮ）２０６を維持する。このような実施形態で、ストレージ装置が第４、第５の論理的ページナンバＬＰＮ４、ＬＰＮ５を第０、第１の物理的ページナンバＰＰＮ０、ＰＰＮ１の各々にマッピングする一方、ファイルシステムは古いファイル２０２のページを第４、第５の論理的ページナンバＬＰＮ４、ＬＰＮ５にマッピングする。同様に、新しいファイル２０４のページは第２４、第２５の論理的ページナンバＬＰＮ２４、ＬＰＮ２５にマッピングされ、第２４、第２５の論理的ページナンバＬＰＮ２４、ＬＰＮ２５は第１１、第１２の物理的ページナンバＰＰＮ１１、ＰＰＮ１２の各々にマッピングされる。
【００２３】
このような従来のシステムの問題点は、古いファイル２０２を置換する新しいファイル２０４にアクセスするために、システムがある時点でシステム情報に関する更新を必要とすることである。通常、この更新は、システムのデータ構造に対して一連のカスケード型の更新を引き起こし、ストレージへの多くの書込みを発生させる。
【００２４】
システム情報は各ファイル／文書に対するメタデータを含む。例えば、メタデータは文書が格納された日付、ファイルを格納した使用者の識別子を含む。メタデータは一般的にデータ構造に格納される。このようなデータ構造の一実施形態はＢ−ツリーであって、格納されたデータを分類（ｓｏｒｔ）して維持し、データ件数に対して対数的にしか増加しない時間内に検索、縦続的アクセス、挿入、及び削除を可能にするツリーデータ構造である。
各ファイル２００のためにメタデータ又は論理的ページナンバ２０６のリストはＢ−ツリーのリーフノード（ｌｅａｆ  ｎｏｄｅ）によって維持される。一般的に、ファイル２００当たりに１つのリーフノードが存在する。ファイル２００の名前がＢ−ツリーのリーフレベル付近に格納された場合、そのノードからルートノードまでの経路上の全てのノードはノードの変化を反映するように更新する必要がある。従って、カスケード型の更新及びストレージへの書込みが発生する。
【００２５】
例えば、上述されたように使用者がブログを更新する毎に、アプリケーションは該ブログを含むファイル情報の更新を必要とし、少なくとも１つのディスク書込みを誘発する。更に多くのユーザが存在する場合、更に多くのディスク書込みが誘発される。
【００２６】
例示的な実施形態は、システムデータ構造を更新することなく、新しい更新ファイルに対するアクセスを提供するための改良された方法及びシステムを指向し、これによりシステムにおける、カスケード型の更新及び過度なディスク書込みが除去されるか、或いは最小化される。
【００２７】
例示的な実施形態はこのような問題点を解決するために、新しいストレージ（例えば、ＳＳＤ）コマンド及びアプリケーションプログラミングインタフェイス（ＡＰＩ、Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）を提供する。即ち、ファイルの新しいバージョンに、システムデータ構造を更新することなくアクセスできる場合、最新のデータシステム情報を反映するためのストレージ書込みを、カスケード型の更新が除去されているので、顕著に削減、又は回避できる。
この単純化された実施形態はこれだけに留まらず、Ｂ−ツリー、文書ロギング、シャドーページング、ダブルバッファ書込み、及びその他の、多数のアプリケーションは、この例示的な実施形態に適用可能な特徴を有する。
【００２８】
本発明の例示的な実施形態は、ここでＳＷＡＴ（ＳＷａｐ  Ａｎｄ  Ｔｒｉｍ）コマンドと称するコマンド及び関連されたＡＰＩを提案する。論理的ページナンバ（ＬＰＮ）リストのペアが与えられた場合、ＳＷＡＴコマンドはアトミックに（ａｔｏｍｉｃａｌｌｙ）リストの論理的ページナンバ（ＬＰＮ）のマッピングを順にスワップ又は再マッピングし、使用されない論理的ページナンバ（ｕｎｕｓｅｄ  ＬＰＮ）は除去（ｔｒｉｍ）する。
更に、ガーベッジ・コレクションによって再クレームされる前まで、非同期的に除去（ｔｒｉｍ）されるべきページにアクセスする同時的プロセスを可能にする弱いマッピングコンセプト（ｗｅａｋ  ｍａｐｐｉｎｇ  ｃｏｎｃｅｐｔ）が提供される。
【００２９】
図３は本発明の一実施形態によって、更新の間にファイルに対するアクセスを提供するための、ファイル管理システム１０によって遂行されるプロセスを示す順序図である。図４は該プロセスを図式化した図面である。
【００３０】
図１、図３、及び図４を参照すれば、ブロック３００に示すステップにおいて、ＳＷＡＴ動作に先立つプロセスを示し、古いファイルの基本ページの変更（ｍｏｄｉｆｙｉｎｇ  ｂａｓｅ  ｐａｇｅ（ｓ））を含む更新を受信することに応答してプロセスが開始され、古いファイル（ｏｌｄ  ｆｉｌｅ）へのアクセスが維持されている間に、目標ページの変更されたコンテンツがコピーされた新しいファイル（ｎｅｗ  ｆｉｌｅ）を生成する。
【００３１】
即ち、図４に示すように、更新されつつあるファイル４００に対応してファイルの古いバージョン（即ち、古いファイル（ｏｌｄ  ｆｉｌｅ）４０２）へのアクセスが一時的に維持される一方で、変更された目標ページを含むファイルの新しいバージョン（即ち、新しいファイル（ｎｅｗ  ｆｉｌｅ）４０４）が生成される。ファイル４００はアプリケーション２０の１つ又は運営システム２２を通じて更新される。
【００３２】
ＳＷＡＴ動作の直前の段階では、ファイルシステム２４は、古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト（ＬＰＮの第１リストとも言う）４０６（例えば、ＬＰＮ４、ＬＰＮ５からなる）を使用して古いファイル４０２に対するページの論理的な格納位置を表現し、他方、高速ストレージ１８は古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト（ＰＰＮの第１リストとも言う）４０８（例えば、ＰＰＮ０、ＰＰＮ１からなる）を使用して古いファイル４０２に対するページの物理的な格納位置を示す。
同様に、新しいファイル４０４に対するページの論理的な格納位置は新しいファイルの論理的ページナンバ（ＬＰＮ）の目標リスト（ＬＰＮの第２リストとも言う）４１０（例えば、ＬＰＮ２４、ＬＰＮ２５からなる）を使用して表現され、高速ストレージ１８における新しいファイル４０４に対する目標ページの物理的な格納位置は新しいファイルの物理的なページナンバ（ＰＰＮ）の目標リスト（ＰＰＮの第２リストとも言う）４１２（例えば、ＰＰＮ１１、ＰＰＮ１２からなる）を使用して表現される。
【００３３】
図３及び図４を再び参照すれば、ブロック３０２に示すステップにおいて、ＳＷＡＴ動作の前半プロセスが示され、委託された新しいファイル４０４への更新に対応して、古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト４０６のマッピング先は、古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８から新しいファイルの物理的ページナンバ（ＰＰＮ）の目標リスト４１２に、図４において矢印４１４により示したように、アトミックに（即ち、基本リスト中のページごとに）スワップ又は再マッピングされる。
図４に示したように、古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト４０６（即ち、ＬＰＮ４、ＬＰＮ５）の物理的なマッピング先は、新しいファイル４０４の物理的ページナンバ（ＰＰＮ）の目標リスト４１２（即ち、ＰＰＮ１１、ＰＰＮ１２）に再マッピングされる。更に詳細に、ＳＷＡＴコマンドが実行される時、ＬＰＮ４はＰＰＮ１１にマッピングされ、ＬＰＮ５はＰＰＮ１２にマッピングされる。結果的に、ＳＷＡＴ  ＡＰＩはファイル情報を更新する必要を無くする。
【００３４】
更に、ブロック３０４に示すステップにおいて、ＳＷＡＴ動作の後半プロセスが示され、古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト４０６から古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８へのマッピングは、非同期的に（ａｓｙｎｃｈｒｏｎｏｕｓｌｙ）除去（ｔｒｉｍ）され、古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８内の物理的ページナンバ（ＰＰＮ）に対応するページを解放（ｒｅｌｅａｓｉｎｇ）する。
具体的には、図４に例示したように、このように、古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト４０６から古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８（ＰＰＮ０、ＰＰＮ１）へのマッピングを除去した後に、古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８に属する物理的ページナンバ（ＰＰＮ０、ＰＰＮ１）を有するページは、参照番号“４１６”を付した“Ｘ”表示のように解放される。
【００３５】
ＳＷＡＴコマンドが実行される時、新しいファイル４０４（実際には、これは最早、「新しいファイル」ではない）は古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト４０８に属する物理的なページにマッピングされる。新しい物理的なページがガーベッジ・コレクションによって再活用される時までは、新しいファイル４０４は揮発性の読出し専用になり、使用者が新しい物理的ページ（即ち、古いファイル４０２の物理的ページのコンテンツを保持している）を読出すのを可能にする。
【００３６】
以下の説明及び図面はＳＷＡＴ動作がＳＳＤに適用される時、マッピングテーブルがどのようにして更新されるかを示す。本実施形態はフォワードマッピングテーブル（ＦＭＴ、Ｆｏｒｗａｒｄ  Ｍａｐｐｉｎｇ  Ｔａｂｌｅ）及びリバースマッピングテーブル（ＲＭＴ、Ｒｅｖｅｒｓｅ  Ｍａｐｐｉｎｇ  Ｔａｂｌｅ）の２つのマッピングテーブルを使用する。マッピング形態はＳ（強、Ｓｔｒｏｎｇ）又はＷ（弱、Ｗｅａｋ）として表示される。フォワードマッピングテーブル及びリバースマッピングテーブルのアレイ表現は単に説明の便宜のためである。即ちこのような説明は、ターゲット性能乃至利用可能な資源等に基づき、アレイ、リスト、ツリー、ハッシュ・マップ等の異なるデータ構造によっても具現できる。
【００３７】
ＳＷＡＴコマンドは、フォワードマッピングテーブルＦＭＴ及びリバースマッピングテーブルＲＭＴの全ての論理的ページナンバ（ＬＰＮ）の２つのリストのマッピングをアトミック方式にスワップし、目標に対するマッピングを弱（ＷＥＡＫ）にする。弱いマッピングは少なくともガーベッジ・コレクションが発生する時、除去（解除）される。例示的な実施形態が以下の図面で説明される。
【００３８】
図５乃至図１２はリバースマッピングテーブルＲＭＴ、物理的ページナンバ（ＰＰＮ）のリスト、及びフォワードマッピングテーブルＦＭＴの多様な状態を示す図面である。図５に示したように、ＦＭＴ（５００）は、論理的ページナンバＬＰＮが整列された論理的ページナンバＬＰＮ行、物理的ページナンバＰＰＮが整列された物理的ページナンバＰＰＮ行、及び同一列の論理的ページナンバＬＰＮと物理的ページナンバＰＰＮとの間の強（Ｓ）又は弱（Ｗ）マッピングに対応する値を含むマッピング型を示す行を含む。図５の実施形態は、ＦＭＴ（５００）がＬＰＮ＿Ａ及びＰＰＮ＿Ｘが強いマッピングを有することを示すエントリを含む場合を想定する。本実施形態はＳＷＡＴコマンドがＬＰＮ＿Ａ及びＬＰＮ＿Ｂに対して発行され、その次にＬＰＮ＿Ｂ及びＬＰＮ＿Ｃに対するＳＷＡＴコマンドが発行される場合を想定する。
第１ＳＷＡＴコマンドの実行は、ＦＭＴ（５００）において、ＬＰＮ＿ＡからＰＰＮ＿Ｙへのフォワードマッピング情報を更新し、ＬＰＮ＿ＢからＰＰＮ＿Ｘへのフォワードマッピング情報を更新する。更に該第１ＳＷＡＴコマンドの実行は、ＲＭＰ（５０２）において、ＰＰＮ＿ＸからＬＰＮ＿Ｂ及びＬＰＮ＿Ａへのリバースマッピング情報を更新する。ＬＰＮ＿Ｂ及びＰＰＮ＿Ｘの間の結果的なマッピングは、ＲＭＴ（５０２）におけるＬＰＮ＿Ｂのための太枠によって表示されるように「強」く（ｓｔｒｏｎｇ）、ＬＰＮ＿Ａ及びＰＰＮ＿Ｘの間の結果的なマッピングは、ＲＭＴ（５０２）におけるＬＰＮ＿Ａのための細枠によって表示されるように「弱」い（ｗｅａｋ）。弱いマッピングは直ちに除去されるか、或いはガーベッジ・コレクション時間中に除去される。
【００３９】
以下の場合の中で１つは弱いマッピングを除去する。１）ガーベッジ・コレクション、２）書込みコマンド、３）トリムコマンド、又は、４）他のＳＷＡＴコマンド。
【００４０】
弱いマッピングを有するＬＰＮに対する書込みは新しいＰＰＮに対する強いマッピングを生成し、弱いマッピングを除去する。例えば、図６に示すように、書込みコマンドＷＲＩＴＥ＿Ａを通じてＬＰＮ＿Ａへの書込みは新しいＰＰＮ＿Ｙを割当て、ＦＭＴ（５００）におけるＬＰＮ＿Ａのフォワードマッピング先をＰＰＮ＿Ｙに更新する。これと並行して、ＲＭＴ（５０２）は、ＰＰＮ＿ＸのリバースマップリストからＬＰＮ＿Ａのための弱いマッピングを除去し、ＰＰＮ＿ＹのリバースマップリストにＬＰＮ＿Ａのために新しいリバースマッピングを追加するように更新される。
【００４１】
ＰＰＮとの強いマッピングを有するＬＰＮへの書込みは、新しいＰＰＮへの強いマッピングを生成し、古いＰＰＮに対する全ての弱いマッピングを除去する。例えば、図７に示すように、書込みコマンドＷＲＩＴＥ＿Ｂを通じてＬＰＮ＿Ｂへの書込みは新しいＰＰＮ＿Ｙを割当て、ＦＭＴ（５００）におけるＬＰＮ＿Ｂのフォワードマッピング先をＰＰＮ＿Ｙに更新する。これはＬＰＮ＿Ａの弱いマッピングを無用化（ｍａｋｅ＿ｓｔａｌｅ）し、このマッピングは直ちに又はガーベッジ・コレクション時間中に除去される。これと並行して、ＲＭＴ（５０２）は、ＰＰＮ＿ＸのリバースマップリストからＬＰＮ＿Ｂのためのエントリを除去するように更新され、ＰＰＮ＿ＹのリバースマップリストにＬＰＮ＿Ｂのための新しいエントリを追加し、ＬＰＮ＿ＡのためのエントリはＰＰＮ＿Ｘのリストから直ちに、又はガーベッジ・コレクション時間中に除去される。
【００４２】
弱いマッピングを有するＬＰＮに対するＴＲＩＭは弱いマッピングを直ちに除去する。例えば、図８に示したように、ＴＲＩＭコマンド、ＴＲＩＭ＿Ａを通じてＬＰＮ＿Ａに対するＴＲＩＭはＰＰＮ＿ＸへのＬＰＮ＿Ａからのフォワードマッピングを除去する。これと並行して、ＲＭＴ（５０２）はＰＰＮ＿ＸのリバースマップリストからＬＰＮ＿Ａのためのエントリを除去するように更新される。
【００４３】
ＰＰＮへの強いマッピングを有するＬＰＮに対するＴＲＩＭはＰＰＮへの全てのマッピングを除去する。例えば、図９に示したように、ＬＰＮ＿ＢへのＴＲＩＭはＬＰＮ＿Ｂのフォワードマッピングを除去する。これはＬＰＮ＿Ａの弱いマッピングを無用化し、このようなマッピングは直ちに、又はガーベッジ・コレクション時間中に除去される。これと並行して、ＲＭＴ（５０２）は、ＰＰＮ＿ＸのリバースマップリストからＬＰＮ＿Ｂのためのエントリを除去するように更新され、ＬＰＮ＿ＡのためのエントリはＰＰＮ＿Ｘのリバースマップリストから直ちに、又はガーベッジ・コレクション時間中に除去される。
【００４４】
弱いマッピングも有する物理的ページナンバ（ＰＰＮ）への強いマッピングを有する、基本ＬＰＮ（ｂａｓｅ  ＬＰＮ）としてのＬＰＮに係るＳＷＡＴはＰＰＮに対する全ての弱いマッピングを除去する。例えば、図１０に示すように、基本ＬＰＮとしてのＬＰＮ＿Ｂ、及び目標ＬＰＮとしてのＬＰＮ＿Ｃを有するＳＷＡＴは、ＰＰＮ＿ＸへのＬＰＮ＿Ｃのフォワードマッピングエントリを弱くする。ＰＰＮ＿Ｘが単に弱いマッピングを有するので、弱いマッピングは結果的に直ちに、又はガーベッジ・コレクション時間中に除去される。これと共に、ＬＰＮ＿ＣのためのエントリがＲＭＴ（５０２）におけるＰＰＮ＿Ｘのリバースマップリストに追加される。ＲＭＴ（５０２）に含まれたＰＰＮ＿Ｘの全ての弱いマッピングは直ちに、又はガーベッジ・コレクション時間中に除去される。
【００４５】
他のＬＰＮへの強いマッピングを有するＰＰＮへの弱いマッピングを基本ＬＰＮとして有するＬＰＮに係るＳＷＡＴは該ＬＰＮの弱いマッピングを除去する。該弱いマッピングは無用になっていない（ｎｏｔ＿ｓｔａｌｅ）ので、このような弱いマッピングは強いマッピングのように看做される。例えば、図１１に示したように、基本ＬＰＮとしてのＬＰＮ＿Ａ及び目標ＬＰＮとしてのＬＰＮ＿Ｃを有するＳＷＡＴはＦＭＴ（５００）からＬＰＮ＿Ａの弱いマッピングを除去し、ＰＰＮ＿Ｚへの強いマッピングを生成する。これはＰＰＮ＿ＸへのＬＰＮ＿Ｃのマッピングを弱くし、結果的に、ＰＰＮ＿Ｘは強いマッピング及び弱いマッピングを全て有する。これと共に、ＲＭＴ（５０２）はＬＰＮ＿Ｃのために弱いマッピングエントリをＰＰＮ＿Ｘのリバースマップリストに追加し、ＬＰＮ＿Ａのために強いマッピングエントリをＰＰＮ＿Ｚのリバースマップリストに追加するように更新される。
【００４６】
他のＬＰＮへの弱いマッピングを有するＰＰＮへの弱いマッピングを基本ＬＰＮとして有するＬＰＮに係るＳＷＡＴは該ＬＰＮの弱いマッピングを除去する。該弱いマッピングは無用になっている（ｓｔａｌｅ）ので、このような弱いマッピングはマッピングではない（ｎｏ−ｍａｐｐｉｎｇ）と看做される。例えば、図１２に示したように、基本ＬＰＮとしてＬＰＮ＿Ａ及び目標ＬＰＮとしてＬＰＮ＿Ｂを有するＳＷＡＴは、ＦＭＴ（５００）からＬＰＮ＿Ａの弱いマッピングを除去し、ＬＰＮ＿ＡからＰＰＮ＿Ｚへの強いマッピングを生成する。これはＬＰＮ＿Ａ及びＬＰＮ＿Ｂの全てがＰＰＮ＿Ｚを共有するようにし、結果的に、ＰＰＮ＿Ｚは強いマッピング及び弱いマッピングを全て有する。これと共に、ＲＭＴ（５０２）はＬＰＮ＿Ａのために強いマッピングエントリ及びＬＰＮ＿Ｂのために弱いマッピングエントリがＰＰＮ＿Ｚのリバースマップリストに追加されるように更新される。
【００４７】
ガーベッジ・コレクション又はトリムコマンドが弱いマッピングを除去する場合、ＬＰＮは無効化（ｉｎｖａｌｉｄ）され、該論理的ページナンバ（ＬＰＮ）のページに対する読出しは、例えば「０ｘＦＦ」のような、予め決められた値を返還する。弱いマッピングを有する論理的ページに対する書込み動作は新しい物理的ページを割当て、強いＰＰＮマッピングを生成する。ある論理的ページが現在使用されない場合、（即ち、物理的ページマッピングがない場合）目標ページはその現在のマッピングを維持するが、該マッピングは弱いマッピングになる。ＳＷＡＴコマンドは、強いマッピング、弱いマッピング、又は、マッピングがない、の３種の何れかを有する論理的ページに係わって動作する。基本ＬＰＮはこの３つの場合の中の何れかであるが、目標ＬＰＮは強いマッピングを有する。基本ＬＰＮが弱いマッピングを有する場合、マッピングを有しないと看做される。物理的ページは最大Ｎ個の弱いマッピング（デフォルトに、Ｎは１）を有する。以下で、更に詳細に説明される。
【００４８】
例えば、図４で、ＳＷＡＴコマンドは２つのＬＰＮリスト、即ち、ＬＰＮの基本リスト（例えば、ＬＰＮ４、ＬＰＮ５からなる）、及びＬＰＮの目標リスト（例えば、ＬＰＮ２５、ＬＰＮ２５からなる）に対して動作する。本実施形態で、各リストは二つのページを含む。このような実施形態で、ＬＰＮ４及びＬＰＮ５は基本リストに含まれ、本来（ｏｒｉｇｉｎａｌｌｙ）、ＰＰＮ０及びＰＰＮ１の各々への強いマッピングを有する。ＬＰＮ２４及びＬＰＮ２５は目標リストに含まれ、本来ＰＰＮ１１及びＰＰＮ１２の各々への強いマッピングを有する。このような２つのリストに対するＳＷＡＴコマンドを実行すると、ＬＰＮ４とＰＰＮ１１との間の１つの強いマッピング、及び、ＬＰＮ５とＰＰＮ１２との間の他の強いマッピングを生成し（図４に実線矢印４１４で示される）、更に、ＬＰＮ２４とＰＰＮ０との間の１つの弱いマッピング、及び、ＬＰＮ２５とＰＰＮ１との間の他の弱いマッピングを生成する（図４に破線矢印で示される）。
【００４９】
物理的ページが他のどのＬＰＮへの強いマッピングも含まない場合、該物理的ページはガーベッジ・コレクションの対象となる資格がある。ＳＷＡＴコマンド動作が完了すると、目標リスト内のＬＰＮに対する弱いマッピングが生成される。結果的に、ガーベッジ・コレクションは、例えば図４に示したＬＰＮ２４及びＬＰＮ２５に対する弱いマッピングを除去してＰＰＮ０及びＰＰＮ１に対応する物理的ページの全てを回収（ｒｅｃｌａｉｍ）する。論理的ページ（例えば、ＬＰＮ２４及びＬＰＮ２５に対応する）はガーベッジ・コレクションが発生される前に読み出され得る。論理的ページが書込まれた場合、弱いマッピングは除去され、新しい物理的なページへの強いマッピングが生成される。マッピングの変更はアトミックに遂行される。
【００５０】
図１３は使用されないページに対するＳＷＡＴコマンドの例を示す。図１３で、基本リスト中のＬＰＮ４及びＬＰＮ５は使用されない（ｕｎｕｅｓｅｄ又はｅｍｐｔｙ）論理的ページであり、目標リスト中のＬＰＮ２４及びＬＰＮ２５はＰＰＮ１１及びＰＰＮ１２への強いマッピングを有する。上述された実施形態のように、このような２つのリストに対するＳＷＡＴコマンドを完了すると、ＬＰＮ４とＬＰＮ１１との間の１つの強いマッピング、及びＬＰＮ５とＰＰＮ１２との間の他の強いマッピングを生成する。ＬＰＮ４及びＬＰＮ５が使用されないので、ＬＰＮ２４及びＬＰＮ２５は各々の元のマッピングを維持するが、マッピング強度は強から弱に変わり、これはＳＷＡＴ動作の結果であることを示す。
【００５１】
マッピングがない基本ＬＰＮとしてのＬＰＮに対するＳＷＡＴは該ＬＰＮに対する新しい有効な弱いマッピングを生成する。例えば、図１４に示したように、基本ＬＰＮとしてのＬＰＮ＿Ａ及び目標ＬＰＮとしてＬＰＮ＿Ｂに対するＳＷＡＴはＰＰＮ＿ＸへのＬＰＮ＿Ａの新しい弱いマッピングをＦＭＴ（５００）において生成する。これはＬＰＮ＿Ａ及びＬＰＮ＿ＢがＰＰＮ＿Ｘを共有するようにし、結果的に、ＰＰＮ＿Ｘは強いマッピング及び弱いマッピングの全てを有する。これと共に、ＲＭＴ（５０２）はＬＰＮ＿Ｂに対する強いマッピングエントリ及びＬＰＮ＿Ａに対する弱いマッピングエントリがＰＰＮ＿ＸのリバースマップリストＲＭＴ（５０２）に追加されるように更新される。
【００５２】
或る物理的ページが強いＬＰＮマッピングを有しない場合、該物理的ページはガーベッジ・コレクションの対象になる資格がある。従って例えば図１３において、強いマッピングがＰＰＮ１１及びＰＰＮ１２に対して存在するので、共有された物理的なページＰＰＮ１１及びＰＰＮ１２はガーベッジ・コレクションで生き残る。結果的に、強いＬＰＮ４及びＬＰＮ５マッピングが除去されるか、或いはガーベッジ・コレクションがページを再活用しない限り、ＬＰＮ２４及びＬＰＮ２５はＰＰＮ１１及びＰＰＮ１２にアクセスするため各々、使用可能になる。
【００５３】
ガーベッジ・コレクションが共有された物理的ページＰＰＮ＿Ｘ（又はＰＰＮ１１及びＰＰＮ１２）を再配置した場合、これによって強いマッピング及び弱いマッピングの全ては移動しなければならない。
【００５４】
図１５は反複されるＳＷＡＴコマンドの例を示す。反復されたＳＷＡＴ動作が図示したように発生する場合、物理的ページ（例えば、ＰＰＮ１１）は、複数の相異なる弱いＬＰＮマッピング（例えば、ＬＰＮ４及びＬＰＮ２４）を有する。デフォールトには、物理的ページは１つの強いマッピング（例えば、ＬＰＮ４及びＰＰＮ１１の間のマッピング）及び１つの選択的な弱いマッピングを有する。しかし、１つの物理的なページがサポート可能なＬＰＮの個数の最大値は、予め決められたパラメータによって定義され、具現化依存（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ−ｄｅｐｅｎｄｅｎｔ）である（実際の具現化に使える資源により限定される）。
【００５５】
例示的な実施形態によれば、本発明に係るＳＷＡＴコマンド及びＡＰＩは、現存する従来技術に対して多様な長所を提供する。ＳＷＡＴコマンドはＯＳに対して何らの変更も要求せず、一部のファームウェアを僅かに変更するだけでＳＳＤ装置の全ての形態に適用可能である。ＳＷＡＴコマンドはアプリケーションからのディスク書込みの回数を減少させることでＳＳＤの耐久性を顕著に向上させる。ＳＷＡＴコマンドは使用されない格納空間を予め積極的に回収することで、システムの性能を向上させる。更に、ＳＷＡＴコマンドはアプリケーション、特に、多重バージョンの同時制御に係るアプリケーションの性能上の顕著な便益を提供する。
【００５６】
以下では、ＳＷＡＴコマンドの或る実施形態が更に詳細に説明される。ファイル（の更新）がアプリケーション２０を通じて委託される時、運営システム２２又はファイルシステム２４の中の何れか１つは装置ドライバＡＰＩ（２６）を呼出す。装置ドライバＡＰＩ（２６）は高速ストレージ１８に対してＳＷＡＴコマンドを発行する。
【００５７】
一実施形態で、コマンドは新しいファイルＬＰＮ４１０の目標リスト及び古いファイルＬＰＮ４０６の基本リストからなるＬＰＮリストのペアを定義する。高速ストレージ１８のフラッシュ変換階層３４（ＦＴＬ、Ｆｌａｓｈ  Ｔｒａｎｓｌａｔｉｏｎ  Ｌａｙｅｒ）は古いファイルＬＰＮ４０６の基本リスト及び新しいファイルＬＰＮ４１０の目標リストを受信し、予め決められた順序に従ってＬＰＮのペアのＬＰＮのマッピングをアトミックに再マッピングする。上述されたように、ＳＷＡＴコマンドはアトミックした動作を遂行する。
【００５８】
ＳＷＡＴコマンドは、ＳＡＴＡ、ＳＡＳ、ＰＣＩｅ、ｅＭＭＣ、ＵＦＳなどの任意の型のストレージプロトコルにおいて、ベンダー固有コマンド（ｖｅｎｄｏｒ  ｓｐｅｃｉｆｉｃ  ｃｏｍｍａｎｄ）により具現される。ＳＷＡＴコマンドの思想及び実施例は、特定の実施例に関して本発明を説明する下記のＡＰＩ擬似コード（ｐｓｅｕｄｏ−ｃｏｄｅ）を参照すると更に良く理解されるであろう。
この擬似コードは、特定のコーディング言語を表現することも、まして、このコーディング言語をコンパイルすることも意図しておらず、単純に、システムの動作をより形式的な用語により表現することを意図している
これらは明確性のためにのみ提供され、本発明はこれに限定されない。本発明及び本発明の技術的な思想は方法、装置、本文に特定に記載されないコードの多様な形態のアプリケーションを含む。
【００５９】
0006788386.tif 000002
0006788386.tif 000003
0006788386.tif 000004
0006788386.tif 000005
0006788386.tif 000006
【００６０】
本発明は、上述の実施形態によって説明されたが、本発明の技術的思想範囲内で実施形態は変形されよう。例えば、例示的な実施形態はハードウェア、ソフトウェア、プログラム命令語を含むコンピュータ読出し可能な媒体、又はそれらの組合わせを使用して具現される。本発明に従って書かれたソフトウェアはメモリ、ハードディスク、又はＣＤ／ＤＶＤ−ＲＯＭなどのコンピュータ読出し可能な媒体に格納され、プロセッサによって実行される。従って、多様な変形が添付された特許請求範囲の思想と範囲内で当業者によって具現されよう。
【符号の説明】
【００６１】
１０      システム、ファイル管理システム
１２      コンピュータ
１４      プロセッサ
１６      メモリ
１８      高速ストレージ、ソリッドステートドライブ（ＳＳＤ）
２０      アプリケーション
２２      運営システム（ＯＳ）
２４      ファイルシステム
２６      デバイスドライバＡＰＩ
２８、２００、４００      ファイル
３０、２０６      論理的ページナンバ（ＬＰＮ）
３２、２０８      物理的ページナンバ（ＰＰＮ）
３４      フラッシュ変換階層
２０２、４０２      古いファイル
２０４、４０４      新しいファイル
３００      ブロック（ＳＷＡＴ動作に先立つプロセスを示すステップ）
３０２      ブロック（ＳＷＡＴ動作の前半プロセスを示すステップ）
３０４      ブロック（ＳＷＡＴ動作の後半プロセスを示すステップ）
４０６      古いファイルの論理的ページナンバ（ＬＰＮ）の基本リスト、古いファイルの論理的ページナンバ（ＬＰＮ）
４０８      古いファイルの物理的ページナンバ（ＰＰＮ）の基本リスト、古いファイルの物理的ページナンバ（ＬＰＮ）
４１０      新しいファイルの論理的ページナンバ（ＬＰＮ）の目標リスト、新しいファイルの論理的ページナンバ（ＬＰＮ）
４１２      新しいファイルの物理的ページナンバ（ＰＰＮ）の目標リスト、新しいファイルの物理的ページナンバ（ＬＰＮ）
４１４      矢印、実線矢印
４１６      “Ｘ”印
５００      フォワードマッピングテーブル（ＦＭＴ）
５０２      リバースマッピングテーブル（ＲＭＴ）
【図１】
0006788386.tif 000007
【図２】
0006788386.tif 000008
【図３】
0006788386.tif 000009
【図４】
0006788386.tif 000010
【図５】
0006788386.tif 000011
【図６】
0006788386.tif 000012
【図７】
0006788386.tif 000013
【図８】
0006788386.tif 000014
【図９】
0006788386.tif 000015
【図１０】
0006788386.tif 000016
【図１１】
0006788386.tif 000017
【図１２】
0006788386.tif 000018
【図１３】
0006788386.tif 000019
【図１４】
0006788386.tif 000020
【図１５】
0006788386.tif 000021