書込みレコードの重複を排除する記憶装置、及びその書込み方法
【課題】記憶装置の記録レコードの重複を排除する書込み（Deduplication）方法を提供する。
【解決手段】記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含み、ホストからレコード（新レコード）の書込み要求を受取るステップと、新レコードのハッシュ値（新Ｓ）を計算するステップと、バッファ２に新Ｓが存在するか確認するステップと、前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、前記比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込むステップと含む。
【解決手段】記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含み、ホストからレコード（新レコード）の書込み要求を受取るステップと、新レコードのハッシュ値（新Ｓ）を計算するステップと、バッファ２に新Ｓが存在するか確認するステップと、前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、前記比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込むステップと含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置において記録媒体への書込みデータ（レコードとも言う）の重複を排除する技術（Deduplication、以下、デデュプリケーション、デデュプ、またはＤｅｄｕｐと言う）方法に関する。特に、本発明は、テープ記憶装置（テープドライブとも言う）においてテープへの書込まれたレコードの重複書込を排除する技術に関する。
【背景技術】
【０００２】
ストレッジの使用量を削減する手法として、デデュプリケーションと言われる手法が存在する。ストレッジ上に同じ内容を含むファイルが複数存在する場合に、従来のように同じ内容のデータをファイルの数だけ異なる場所に保存することはしない。この技術は、データをストレッジ上の一箇所にのみ保存する。前述のどのファイルを参照する場合も同じ実体を参照し、変更が行われた場合のみその内容を新たに別の場所に保存する。この技術は、全体としてストレッジ容量の使用量を削減する手法である。削減される使用量は記憶するデータの内容に依存するが、使用方法によっては従来の１／１０〜１／２０にできる。
【０００３】
ホストはテープにデータを書き込む場合、テープドライブに対してレコードと呼ばれる可変長の単位でデータの書き込みを行う。テープメディアの容量は、１ＴＢ程度である。テープドライブにおいてＤｅｄｕｐを機能させる場合、新たに書き込むデータが既に書き込まれたデータと同一のものであることを確認するために時間がかかるという問題がある。
【０００４】
テープドライブ（例えばＩＢＭのエンタープライズテープドライブである ＴＳ１１２０）の場合 、テープ媒体に物理的位置に順に書込み読み出しを実行するシーケンシャル・デバイス（レコードを記録媒体の物理的位置に順に記録する記憶装置）である。一般にＤｅｄｕｐ技術では、書込みデータと記録データの重複か否かを示すハッシュ（ｈａｓｈ）の生成及び対比などが必要である。シーケンシャル・デバイスが、上位装置から新たに書き込むデータを受取り、そのデータが以前書き込んだデータと同一であることが期待される。この場合、シーケンシャル・デバイスは、以前書き込んだデータを読み出すために所定のテープ位置に移動してから書込むべき元のテープ位置に戻るまで平均２分程度の時間がかかる。そのため、現在テープドライブ単体でＤｅｄｕｐ機能をサポートする製品は存在しない。
【０００５】
特許文献１は、電力消費低減のため２台のストレッジの同期をとる際に差分のみをコピーする方法である。この方法は、テープドライブ単独でＤｅｄｕｐを実施することはしない。
【０００６】
特許文献２は、既にdeduplicationされたデータをテープなどにバックアップを取るための手法である。この手法は、テープドライブ単独でＤｅｄｕｐを実施する方法ではない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−２０８５８号公報
【特許文献２】特開２００８−２８２３８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以上のように、シーケンシャル・デバイス、例えばテープドライブでは、新たに書き込むデータと記録媒体上のデータとを対比するのに、テープ移動のためのオバーヘッドが大きい。そのため、現在テープドライブ単体でＤｅｄｕｐ機能を付加するとことを考慮されていない。
【０００９】
本発明の目的は、記録媒体に記録されたデータの重複を排除する書込み方法、及び、その方法を実装した記憶装置（特にテープドライブ）を提供することである。
【課題を解決するための手段】
【００１０】
以下ステップの番号は、図３または図４のステップの番号に対応する。
上記の目的を達成する本発明は、記憶装置への書込みレコードの重複を排除する書込み方法である。前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む。
この方法は、
１．ホストからレコード（新レコード）の書込み要求を受取るステップと、
２．新レコードのハッシュ値（新Ｓ）を計算するステップと、
３．バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認するステップと、
４．前記確認ステップ３でバッファ２に新Ｓが存在する場合、新データが前記新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、
５．前記比較ステップ４で新レコードと前記レコードが一致する場合（Ｙｅｓ）は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込むステップと、を含む。
【００１１】
この方法は更に、前記比較ステップ４で新レコードと前記バッファ２に保存されたレコードとが一致しない場合（Ｎｏ）、バッファ１に保存された頻度を１増分し（７．１）、新レコードの頻度が所定値以上の場合（７．２）、バッファ２に新レコード内容を新Ｓ及びポインタと併せて保存するステップと（７．３）、
９．前記ステップ７の処理後、新データを記録媒体に書込むステップと、を実行させることを特徴とする。
【００１２】
この方法は更に、６．前記確認ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認するステップと、
前記確認ステップ６でバッファ１に新Ｓが存在する場合（Ｙｅｓ）、バッファ１に保存された頻度を１増分し（７．１）、新レコードの頻度が所定値以上の場合（７．２）、バッファ２に新レコード内容を新Ｓ及びポインタに併せて保存するステップと（７．３）、
９．ステップ７の処理後、新データを記録媒体に書込むステップとを含むことを特徴とする。
【００１３】
この方法は更に、６．前記確認ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認するステップと、
８．前記確認ステップでバッファ１に新Ｓが存在しない場合（Ｎｏ）、新レコードの新Ｓについてポインタ及び頻度１をバッファ１に保存するステップと、
９．ステップ８の処理後、新データを記録媒体に書込むステップと、を含むことを特徴とする。
【００１４】
この方法は、バッファ１は、テープ上に全てのレコードをハッシュ値について保存したエントリを有し、バッファ２は、前記エントリのうち書込み頻度が所定値以上について新レコードの内容を前記ハッシュ及びポインタと結びつけて保存するエントリを有することを特徴とする。
【００１５】
この方法は、前記所定値が記録媒体に重複して記録された同一レコード数に対して（バッファ２の容量）／（記録媒体の容量）の値に基づいて決定されることを特徴とする。
【００１６】
この方法は、前記所定値が記録媒体に重複して記録された同一レコードの数に対して設定された上限値により決定されることを特徴とする。
【００１７】
上記の目的を達成する本発明は、記憶装置から記録レコードを読み出す方法である。
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む。この方法は、
１．ホストからポインタを指定したレコードの読出し命令を受取るステップと、
２．前記レコードに関するデータをテープから読出すステップと、
３．前記レコードのデータがテープに記録された前記レコードのポインタであるかを確認するステップと、
４．前記確認ステップ３で前記データがポインタである場合、前記ポインタに対応するレコードがバッファ２上に存在するか確認するステップと、
５．前記確認ステップでバッファ２に前記ポインタに対応するレコードが存在する場合、バッファ２から前記レコードを読み出してホストに送るステップと、を含む。
【００１８】
この方法は、６．前記ポインタに対応するレコードがバッファ２に存在するか確認する４ステップで、対応レコードが存在しない場合前記データが（Ｎｏ）、前記ポインタが指しているテープ上のレコードを読み出すステップと、
７．前記レコードを読み出し要求の前記レコードとして読み出してホストに送るステップと、を含むことを特徴とする。
【００１９】
更に上記の目的を達成する本発明は、書込みデータの重複排除するための記憶装置である。この記憶装置は、
記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、
レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２と、
記録媒体へのレコードの書込を制御する書込み制御手段とを含み、
前記書込み制御手段は、
１．ホストからレコード（新レコード）の書込み要求を受取る手段と、
２．新レコードのハッシュ値（新Ｓ）を計算する手段と、
３．バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認する手段と、
４．前記確認ステップ３でバッファ２に新Ｓが存在する場合、新データが前記新Ｓに対応する（結びつく）レコードと一致するかを比較する手段と、
５．前記比較ステップ４で新レコードと前記レコードが一致する場合（Ｙｅｓ）は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとしてテープに書込む手段とを含む書込み制御を有することを特徴とする。
【００２０】
本発明によれば、記憶装置における書込みデータの重複を極力排除する方法を提供して、大容量の記録媒体の有効利用を可能にする。
【図面の簡単な説明】
【００２１】
【図１】本実施形態が適用されるテープドライブ１０の構成例を示す。
【図２】実施例の構成要素（バッファ１、バッファ２、テープ）及び本発明の重複データの書込み及び読み出し機構を示す。
【図３】ホストからテープドライブにレコードを書き込む場合のテープドライブの重複排除の書込み方法のフローチャートを示す。
【図４】本発明の重複排除の書込み方法のより記録されたレコードを読み出すフローチャートを示す。
【発明を実施するための形態】
【００２２】
以下において、本発明のテープドライブにおける重複データの排除の方法について、典型的な実施形態（以下「実施例」という）が説明される。これら実施例は例示であり、テープドライブ以外の記憶装置に提供することを排除しない。
【００２３】
テープドライブ単体でＤｅｄｕｐをサポートする手法を考案した。テープドライブが持つ一時記憶領域（例えばＤＲＡＭ）を新たにＤｅｄｕｐのための２つのバッファを用意する。バッファ１は、すでに書き込まれたレコードのレコードＮｏとレコードに格納されたデータのハッシュ値を対応させたテーブルを保存する。バッファ２は、書込み頻度の高いレコードをハッシュ値又はレコードＮｏに紐付けて保存する。書込み頻度（「頻度」とも言う）は、同じレコードについてのホストから書込み要求回数であり、一つのレコードについての重複レコードデータの数を意味する。レコードＮｏは、ホストが過去込み時に可変長のレコードのＮｏ（番号）を指定する指標である。テープドライブは、Ｎｏに結びつけてレコードの内容をテープに書込み、そのＮｏを指定されたレコードをテープから読み出す。
【００２４】
ホストからテープドライブにレコードを書き込む場合、まずそのレコードのハッシュ値を計算する。そのハッシュ値がバッファ２に格納されていれば、新たに書き込むレコードとバッファ２に格納されたそのハッシュ値に対応するレコードの内容を比較する。比較の結果が同一であることが確認された場合にはレコード本体を書き込む変わりに、すでに書き込んだ同内容のレコードＮｏを持つ特殊なレコードを保存する。レコードＮｏで指定されたテープ上のレコードは、そのレコード自体の内容を示す。
【００２５】
本発明では、テープに書込むデータとして特殊なレコードとしてポインタを与える。ポインタは、レコードを特定するレコードＮｏ及び所定の印（指標）を情報として含む。ポインタにレコードＮｏに含ませるのは、既にテープに書き込まれた他のレコードを特定するレコードＮｏに特定するためである。他のレコードＮｏを含んでいることを示す指標は、読取り情報がホストにより送られたレコード内容自体でなく他のレコードＮｏを含んでいることをテープドライブに区別させるためである。また、ポインタは、テープに書込まれたレコードＮｏではなくバッファ２に保存されたレコードＮｏ（エントリＮｏ）であってもよい。この場合、ポインタの指標は、テープのレコードＮｏとバッファ２に保存されたレコードのＮｏ（エントリＮｏ）とを区別する必要がある。なお、ポインタは、実際のレコード自体の容量より十分小さな値であるため、バッファ1及び２に容量領域を多くは占めない。バッファ１が１００ＭＢ程度の場合、一般的なレコードサイズに基づくレコード数であるならば、全てレコードをバッファ１の各エントリに含ませることが出来る。
【００２６】
本発明の実施例を詳述するために、テープドライブの動きについて説明する。
図１は、本実施形態が適用されるテープドライブ１０の構成例を示す。テープドライブ１０は、ホスト３０から送られた複数のデータ（レコードとも言う）を固定長のデータセット（ＤＳ）単位でテープ記録媒体への書込み（Ｗｒｉｔｅ）または、テープ媒体からＤＳ単位で読み出す（Ｒｅａｄ)。ＤＳは複数の可変長のレコードの集まりであり、固定長のフォーマット構造を有する。
【００２７】
テープドライブ１０は、インターフェイス１１、バッファ１２、チャネル１３、ヘッド１４、モータ１５、テープ２３を巻きつけるリール２２、及びこれらの制御システムを含む。制御システムは、書込み読取り制御１６、ヘッド位置制御システム、及びモータドライバ１８を含む。モータ１５は、２個のモータを設けてよい。テープドライブ１０は、テープカートリッジ２０を着脱可能に搭載する。
【００２８】
テープカートリッジ２０は、リール２１に巻かれたテープ２３を含む。テープ２３は、リール２１、２２の回転に伴い、リール２１からリール２２の方向へ、又は、リール２２からリール２１の方向へ、長手方向に移動する。テープ２３は、磁気テープ以外のテープ媒体でもよい。テープカートリッジは、テープのデータの記録属性（テープディレクトリと呼ばれる）の情報を、カートリッジメモリ（ＣＭ：Cartridge Memory）２５と呼ばれる不揮発性メモリに保持している。テープドライブは、読み出し（Ｒｅａｄ）時に、テープカートリッジ内に装備されたＣＭ２５からディレクトリ情報を読み取り、ヘッド１４に対してテープ２３を目的位置まで高速に移動させる。搭載されたテープカートリッジ２０のＣＭ２５は、テープドライブ１０により非接触的に読み書される。ＣＭは、テープカートリッジの属性情報が保存されたメモリマップを含む。
【００２９】
書込み読取り制御１６は、テープドライブ１０の全体を制御する。この制御を介して、ヘッド１４は、テープ２３が長手方向に移動するとき、テープ２３に対して情報を書き込んだり、テープ２３から情報を読出したりする。また、モータ１５は、リール２１、２２を回転させる。１つのモータ１５を表しているが、リール２１、２２の各々に１つずつのモータを設けるのが好ましい。
【００３０】
例えば、インターフェイス１１で受け付けたコマンドに従って、データのテープ２３への書込みやテープ２３からの読取りを制御する。また、ヘッド位置制御システム１７やモータドライバ１８の制御、及び、書込みデータへの訂正符号の付加・読取りデータのエラー訂正も行う。モータドライバ１８は、モータ１５を駆動する。
【００３１】
インターフェイス１１は、上位装置の一例であるホスト３０との通信を行う。ホスト３０から、テープ２３を目的の位置に移動させるコマンド、テープ２３へのデータの書込みを指示するコマンド、テープ２３からのデータの読取りを指示するコマンドを受け取る。それぞれは、位置決めコマンド、Ｗｒｉｔｅコマンド及び同期コマンド（Ｆｌｕｓｈ）、Ｒｅａｄコマンドに相当する。また、インターフェイス１１は、ホスト３０に対し、これらのコマンドに応じた処理が成功したのか失敗したのかの応答を返す。ホスト３０は、これらコマンドに可変長のデータの位置、数を指定してテープドライブ１０に発行する。
【００３２】
バッファ１２は、テープ２３に書き込むべきデータやテープ２３から読出されたデータを蓄積するメモリである。例えば、メモリはＤＲＡＭによって構成される。また、バッファ１２は、複数の固定長のバッファセグメントからなり、各バッファセグメントが、テープ２３に対する読み書きの単位であるＤＳを格納している。１つのデータセットは、ホスト３０から送られるデータの１つの一部分、または、複数のデータから構成される。読み書きチャネル１３を介して渡されたデータはＤＳ単位（例えば４００ＫＢまたは１．６ＭＢ）として、ヘッド１４によりテープ２３に書込まれる。同期コマンドはバッファ内に保管されたデータをテープに書く込み命令である。
【００３３】
図２は、実施例の構成要素、及び本発明の重複データの書込み及び読み出し機構を示す。バッファ１及び２を用いて頻出データについて重複データを管理する本発明の実施例の説明をする。Ｄｅｄｕｐ用のバッファとして、テープドライブ上に１〜４ＧＢ程度の一時記憶域（バッファ、例えばＤＲＡＭ）を確保できる。テープメディアの容量が１ＴＢ程度であることから、このバッファ容量では当然ならが全てのレコードをバッファに保存することはできない。言い換えると、バッファ容量は絶対的にテープ容量に比べて０．１〜０．４％と小さいためバッファに保存するレコードを取捨選択する必要がある。
【００３４】
バッファ１にはハッシュ値毎のエントリを保存し、各エントリには更に１または複数のレコードＮｏを対応させて含ませてもよい。バッファ２にはハッシュ値及びレコードＮｏに加えレコードの内容そのものを保存する。バッファ２には、レコードＮｏの代わりにレコードＮｏを特定するポインタを含ませてもよい。バッファ１は、全てのデータのハッシュ値とその書込頻度を記録するために利用する。バッファ２は、バッファ1 より書込み頻度が高いことが確認されたデータの本体を記録するために利用する。書込み頻度の観測するためのバッファ１と、レコード本体を保持するバッファ２とを区別する。２つのバッファの独立に管理することにより、任意の時点で書込み頻度の高いデータのみを動的にバッファ２に残すことができる。
【００３５】
図２は、バッファ１及び２を用いて頻出データについて重複データを管理する図の説明を示す。バッファ１は、すでにテープ書込まれた全てのレコードについて、そのレコードの・ハッシュ値、及び、・書込み頻度を記録する。バッファ１の各エントリ（各枠）は、ハッシュ値についてテープに記録されている全てのレコード（Ａ，Ｂ，Ｃ・・・）を保存したエントリを含むディレクトリのようなものである。各エントリは、レコードＮｏを含ませてもよい。全てのレコードについてこれらの値を保存しても１００ＭＢ程度のバッファ容量で足りる。レコードＡ，Ｂは同じハッシュ値を有するとして同じエントリに含まれている。頻度は同じハッシュ値を与える全てのレコードについての値である。ここでハッシュ値は、可変長なレコードを代表する数値を得る少ない桁数の固定長データで集約して代表値である。なおハッシュ値が同じでも最終的にレコード内容が一致するとか限らない。最終的にはハッシュ値が同一であることを前提として、レコードの内容自体を対比することにより最終的な一致を確認する。
【００３６】
バッファ２を構成する各エントリに、レコード内容をレコードＮｏ及びハッシュ値に紐付けて保存する。図２ではレコードＡ、Ｂ、Ｃ・・・のそれぞれのハッシュ値に結びつけて保存される。レコードＡ、Ｂ、Ｃは比較的頻度の大きいデータであるため、バッファ２に保存されている。バッファ１及び２は合計でも1〜４ＧＢであり、テープ容量（〜１ＴＢ程度）に対して０．５％以下である。書込み頻度の所定値は、テープの全容量に対してバッファ２の大きさを考慮して決定される。書込み頻度が所定値以上のレコードについて、レコード内容をハッシュ及びポインタと結びつけてバッファ２に保存される。なお図２では、簡単のために各エントリにはポインタではなく単にレコードＮｏのみを表示している。レコードが所定値以上の書込み頻度であれば、今後も書込み要求される可能性が高いとしてバッファ２に保存する。一定以上の書込み頻度のレコードを、限られた容量のバッファ２に保持しておけば、レコードの対比確認のパフォーマンス、テープ容量の節約、及び読みよりパフォーマンスに向上が図られる。所定値は、テープに重複して記録された同一レコードの数に対して（バッファ２の容量）／（テープ容量）の値に基づいて与えられる。また所定値は、テープに記録され重複レコード数の上限値により決定されてもよい。所定値が、少なくとも３以上であるとしてもよい。新たに書込み要求されたレコードの頻度は所定値より小さい場合は、バッファに保存されず、テープ上のデータを参照するのみである。また、バッファ２に保存されるレコードに容量の不足が生じた場合、所定値を変動させて空き領域を確保できる。所定値を大きくすることにより、既に保存されていたレコードであっても、頻度が所定値より小さくなったものをバッファ２から削除する。バッファ２から削除による整理が行われても、テープ上には本来のレコードＮｏにレコード内容は記録されているので、データの保全性（Ｄａｔａ Ｉｎｔｅｒｇｉｒｉｔｙ）は保証される。
【００３７】
図２に基づいて、重複の書込み機構を説明する。ホストから新たなレコード（新レコード）を受け取ると、テープドライブはデータバッファ上に保管された新レコードのハッシュ値を算出する。このハッシュ値をバッファ２の各エントリに保存されたハッシュ値と対比して存在を確認する。この確認は、バッファ２の各エントリに保管されたデータと新レコードとの間で行われ、テープから読み出す必要はない。この確認においてデータが一致した場合は、テープにはバッファ２のエントリに一致したレコードＮｏのテープ上に既に書き込まれたレコードＡ，Ｂ，Ｃ・・・のＮｏを含むポインタを書込む。テープドライブは、このポインタはテープ上にレコードＡのＮｏを指している。この比較確認においてバッファ２には同一ハッシュ値は存在するがエントリも存在しない場合、所定値以上のテープ上に重複レコードがないことを意味する。この場合はレコード書込みの頻度が所定値に達するまでテープドライブは通常の書込みをテープに行う。バッファ１においてエントリも存在しないレコードの場合、バッファ１に新レコードのエントリ（ハッシュ値、頻度、及びレコードＮｏ）を新たに設ける。バッファ２にレコードの内容自体をデータＮｏ及びハッシュ値に結びつけて保持する。なお、バッファ２でのレコード内容の保存は、容量を限定するする必要上所定値以上の頻度ものに限定される。言い換えると、レコードの書込み頻度が所定値に達するまではテープには重複してレコードの書込が行われる。
【００３８】
図２に基づいて、本発明により書込まれたレコードの読み出し機構を説明する。ホストからレコードＮｏを指定してレコードを読み出す命令を受け取った場合、テープドライブはテープ上のポインタを読み取ったかを確認する。ポインタの存在は、バッファ２でのレコードの保持の可能性を確認できる。読み出し要求レコードがバッファ２に存在する場合は、バッファ２から読み出してテープ自体の元来のデータを読みだす必要はない。読み出しレコードがバッファ２に存在しない場合は、通常通りテープから読み出す操作を行う。
【００３９】
図３は、ホストからテープドライブにレコードを書き込む場合のテープドライブの重複排除の書込み方法のフローチャートを示す。
（１）ホストから新たなレコード（新レコード）の書き込み要求をテープドライブは受取る。
（２）テープドライブは、新レコードのハッシュ値（新Ｓ）を計算する。
（３）バッファ２に新Ｓが存在するか確認する。
なおバッファ１において頻度が所定値以上である場合にバッファ２にＳのレコード内容が存在すると判断してもよい。
（４）確認ステップ３においてバッファ２に新Ｓが存在する判断された場合、新データがバッファ２のエントリ中において新Ｓに結びつくレコードと一致するかを比較する。
（５）比較ステップ４において新レコードとバッファ２に保存されたレコードが一致する場合（Ｙｅｓ）、既にテープに書込み済みレコードのＮｏを含むポインタを新レコードの書込みデータとしてテープに書込む。図２を参照すると、テープに書込むポインタＡ，Ｂ，Ｃの確保には、既にバッファ２の各エントリに保存されたレコードＡ，Ｂ，ＣのＮｏを利用できる。ポインタは、後でテープドライブが読み取りデータがレコードＮｏであることを判断できるようにその指標も含む。
（６）ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認する。
（７．１）確認ステップ６においてバッファ１に新Ｓが存在する場合（Ｙｅｓ）、または、比較ステップ４においてバッファ２に保存されたレコードと一致しない場合（Ｎｏ）、バッファ１に所定のエントリの頻度のカウンターを１つ増加させる。頻度は同一のハッシュ値のレコード書込みの頻度を示す。
（７．２）バッファに保存された新レコードの頻度が所定値以上か確認する。
（７．３）確認ステップ（７．２）において頻度が所定値以上の場合（Ｙｅｓ）、バッファ２のエントリに、新レコードの内容を新しいハッシュ値及び新レコードのＮｏと併せて保存する。
（８）テープドライブは、確認ステップ６でバッファ１に新Ｓが存在しない場合（Ｎｏ）、新レコードの新ＳについてレコードＮｏ及び頻度＝１をバッファ１に保存する。
（９）テープドライブは、レコードをテープに書き込む。
・ステップ８の処理後、新データをテープに書込む。
・確認するステップ（７．２）において新レコードの書込み頻度は所定値以下の場合（Ｎｏ）、バッファ２への新レコードＮｏ及びレコード内容の保存はスキップされる。その後、このステップ９において通常のレコード書込みを行う。この通常書込みは、頻度が所定値に達するまではテープに同一レコードの書込みを許容する。バッファ２の容量にテープ容量に対して制限的な値１％以下であるため、完全なレコードの重複書込を排除するのは現実的でない。本発明の方法は、大容量の記憶装置に対してレコードの重複回数の上限値を設けることが出来でき、容量の有効利用できる点で意義はある。
【００４０】
図４は、本発明の重複排除の書込み方法のより記録されたレコードを読み出すフローチャートを示す。一つの実装例として、ホストからテープドライブにデータを読み出す場合のテープドライブの振る舞いを読み出し方法のステップを説明する。
（１）テープドライブは、ホストからレコードの読み出し要求を受取る。
ホストは、レコードＮｏを指定してテープドライブにレコードの読出し命令を出す。
（２）テープドライブは、テープから指定されたレコードを読み出す。
（３）テープドライブは、読み出したレコードがテープに記録された他のレコードへのポインタかを確認する。読み出されたデータが、ポインタである場合は所定の指標でもってレコードＮｏであることがわかる。なお、その指標がレコードＮｏまたはバッファ２のエントリＮｏのどちらかを示す。
・指標がテープのレコードの場合、レコードＮｏで指定されたレコードが読み出し対象である。
・指標がバッファ２のレコードの場合、バッファ２のエントリＮｏで指定されたエントリ内のレコード内容を読み出し対象である。
・なお、このステップ３においてポインタでない場合（Ｎｏ）、ステップ７において通常通りのテープからレコードを読み出す。
（４）ステップ３においてポインタである場合（Ｙｅｓ）、ポインタに対応するレコードがバッファ２に存在するかを確認する。
（５）ステップ４においてレコードが存在する場合（Ｙｅｓ）、バッファ２ に格納されたポインタに対応するレコードを読み出してホストに送る。また、ポインタがバッファ２のエントリへの指標である場合、そのエントリＮｏで指定されたレコードが読み出し対象となる。
（６）ステップ４においてレコードが存在しない場合（Ｎｏ）、ポインタが指し示すレコードをテープから読み出す。ポインタがテープのレコードのレコードＮｏのための指標と確認される場合である。その指標により、テープドライブは、テープから読み取られたレコードＮｏで指定されたレコードが読み出し対象とされる。
（７）テープドライブは通常通り読み出したレコードをホストに送る。
・読み出しステップ６において読み出されたレコードをホストに送る。
・確認ステップ３においてレコードがポインタでない場合（Ｎｏ）、読み出したレコードをホストに送る。
【００４１】
バッファ１及びバッファ２の内容の保持には、既存のテープドライブが詳細なテープディレクトリを保存するための特別なデータセット（Housekeeping データセット）を利用できる。テープドライブは、テープカートリッジを取り出すとき、このデータセットにバッファ１及び２のエントリの内容を保存する。テープをテープドライブに挿入した直後に、テープディレクトリを読み出す手法を用いることにより、テープに記録された特別なデータセットからバッファ1及び２の内容を引き出せばよい。また、テープドライブは、不揮発性メモリ（例えばＣＭ）を利用することによりテープドライブからテープ媒体を取り出す操作が行われてもバッファ１及びバッファ２の内容を保持し続けることができる。
【００４２】
本発明の書込み方法は、テープへのアクセスを省略できるため書込みパフォーマンスに大きな影響を与えることなくＤｅｄｕｐを可能とし、テープ容量を有効利用できる。
【００４３】
以上の本発明の実施は、典型的なシーケンシャル・デバイスであるテープドライブについて説明された。２つの区別された一時記憶装置ランダムアクセスはメインの記憶容量に対して１％に満たない容量である。この一時記憶領域を本発明のように利用することは、重複したレコードの書込み回数を管理できる点で有利である。したがって、本発明の適用範囲はテープドライブに限定されず、本発明はランダムアクセスの記憶装置、典型的にはＤＡＳＤにも適用できる。
【符号の説明】
【００４４】
１０…テープドライブ、
１１…インターフェイス、
１２…バッファ（ＤＲＡＭ）、
１３…読み書きチャネル、
１４…ヘッド、
１５…モータ、
１６…書込み読取り制御（コントローラ）、
１７…ヘッド位置制御システム、
１８…モータドライバ、
２０…カートリッジ、
２１，２２…リール、
【技術分野】
【０００１】
本発明は、記憶装置において記録媒体への書込みデータ（レコードとも言う）の重複を排除する技術（Deduplication、以下、デデュプリケーション、デデュプ、またはＤｅｄｕｐと言う）方法に関する。特に、本発明は、テープ記憶装置（テープドライブとも言う）においてテープへの書込まれたレコードの重複書込を排除する技術に関する。
【背景技術】
【０００２】
ストレッジの使用量を削減する手法として、デデュプリケーションと言われる手法が存在する。ストレッジ上に同じ内容を含むファイルが複数存在する場合に、従来のように同じ内容のデータをファイルの数だけ異なる場所に保存することはしない。この技術は、データをストレッジ上の一箇所にのみ保存する。前述のどのファイルを参照する場合も同じ実体を参照し、変更が行われた場合のみその内容を新たに別の場所に保存する。この技術は、全体としてストレッジ容量の使用量を削減する手法である。削減される使用量は記憶するデータの内容に依存するが、使用方法によっては従来の１／１０〜１／２０にできる。
【０００３】
ホストはテープにデータを書き込む場合、テープドライブに対してレコードと呼ばれる可変長の単位でデータの書き込みを行う。テープメディアの容量は、１ＴＢ程度である。テープドライブにおいてＤｅｄｕｐを機能させる場合、新たに書き込むデータが既に書き込まれたデータと同一のものであることを確認するために時間がかかるという問題がある。
【０００４】
テープドライブ（例えばＩＢＭのエンタープライズテープドライブである ＴＳ１１２０）の場合 、テープ媒体に物理的位置に順に書込み読み出しを実行するシーケンシャル・デバイス（レコードを記録媒体の物理的位置に順に記録する記憶装置）である。一般にＤｅｄｕｐ技術では、書込みデータと記録データの重複か否かを示すハッシュ（ｈａｓｈ）の生成及び対比などが必要である。シーケンシャル・デバイスが、上位装置から新たに書き込むデータを受取り、そのデータが以前書き込んだデータと同一であることが期待される。この場合、シーケンシャル・デバイスは、以前書き込んだデータを読み出すために所定のテープ位置に移動してから書込むべき元のテープ位置に戻るまで平均２分程度の時間がかかる。そのため、現在テープドライブ単体でＤｅｄｕｐ機能をサポートする製品は存在しない。
【０００５】
特許文献１は、電力消費低減のため２台のストレッジの同期をとる際に差分のみをコピーする方法である。この方法は、テープドライブ単独でＤｅｄｕｐを実施することはしない。
【０００６】
特許文献２は、既にdeduplicationされたデータをテープなどにバックアップを取るための手法である。この手法は、テープドライブ単独でＤｅｄｕｐを実施する方法ではない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００９−２０８５８号公報
【特許文献２】特開２００８−２８２３８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以上のように、シーケンシャル・デバイス、例えばテープドライブでは、新たに書き込むデータと記録媒体上のデータとを対比するのに、テープ移動のためのオバーヘッドが大きい。そのため、現在テープドライブ単体でＤｅｄｕｐ機能を付加するとことを考慮されていない。
【０００９】
本発明の目的は、記録媒体に記録されたデータの重複を排除する書込み方法、及び、その方法を実装した記憶装置（特にテープドライブ）を提供することである。
【課題を解決するための手段】
【００１０】
以下ステップの番号は、図３または図４のステップの番号に対応する。
上記の目的を達成する本発明は、記憶装置への書込みレコードの重複を排除する書込み方法である。前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む。
この方法は、
１．ホストからレコード（新レコード）の書込み要求を受取るステップと、
２．新レコードのハッシュ値（新Ｓ）を計算するステップと、
３．バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認するステップと、
４．前記確認ステップ３でバッファ２に新Ｓが存在する場合、新データが前記新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、
５．前記比較ステップ４で新レコードと前記レコードが一致する場合（Ｙｅｓ）は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込むステップと、を含む。
【００１１】
この方法は更に、前記比較ステップ４で新レコードと前記バッファ２に保存されたレコードとが一致しない場合（Ｎｏ）、バッファ１に保存された頻度を１増分し（７．１）、新レコードの頻度が所定値以上の場合（７．２）、バッファ２に新レコード内容を新Ｓ及びポインタと併せて保存するステップと（７．３）、
９．前記ステップ７の処理後、新データを記録媒体に書込むステップと、を実行させることを特徴とする。
【００１２】
この方法は更に、６．前記確認ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認するステップと、
前記確認ステップ６でバッファ１に新Ｓが存在する場合（Ｙｅｓ）、バッファ１に保存された頻度を１増分し（７．１）、新レコードの頻度が所定値以上の場合（７．２）、バッファ２に新レコード内容を新Ｓ及びポインタに併せて保存するステップと（７．３）、
９．ステップ７の処理後、新データを記録媒体に書込むステップとを含むことを特徴とする。
【００１３】
この方法は更に、６．前記確認ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認するステップと、
８．前記確認ステップでバッファ１に新Ｓが存在しない場合（Ｎｏ）、新レコードの新Ｓについてポインタ及び頻度１をバッファ１に保存するステップと、
９．ステップ８の処理後、新データを記録媒体に書込むステップと、を含むことを特徴とする。
【００１４】
この方法は、バッファ１は、テープ上に全てのレコードをハッシュ値について保存したエントリを有し、バッファ２は、前記エントリのうち書込み頻度が所定値以上について新レコードの内容を前記ハッシュ及びポインタと結びつけて保存するエントリを有することを特徴とする。
【００１５】
この方法は、前記所定値が記録媒体に重複して記録された同一レコード数に対して（バッファ２の容量）／（記録媒体の容量）の値に基づいて決定されることを特徴とする。
【００１６】
この方法は、前記所定値が記録媒体に重複して記録された同一レコードの数に対して設定された上限値により決定されることを特徴とする。
【００１７】
上記の目的を達成する本発明は、記憶装置から記録レコードを読み出す方法である。
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む。この方法は、
１．ホストからポインタを指定したレコードの読出し命令を受取るステップと、
２．前記レコードに関するデータをテープから読出すステップと、
３．前記レコードのデータがテープに記録された前記レコードのポインタであるかを確認するステップと、
４．前記確認ステップ３で前記データがポインタである場合、前記ポインタに対応するレコードがバッファ２上に存在するか確認するステップと、
５．前記確認ステップでバッファ２に前記ポインタに対応するレコードが存在する場合、バッファ２から前記レコードを読み出してホストに送るステップと、を含む。
【００１８】
この方法は、６．前記ポインタに対応するレコードがバッファ２に存在するか確認する４ステップで、対応レコードが存在しない場合前記データが（Ｎｏ）、前記ポインタが指しているテープ上のレコードを読み出すステップと、
７．前記レコードを読み出し要求の前記レコードとして読み出してホストに送るステップと、を含むことを特徴とする。
【００１９】
更に上記の目的を達成する本発明は、書込みデータの重複排除するための記憶装置である。この記憶装置は、
記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、
レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２と、
記録媒体へのレコードの書込を制御する書込み制御手段とを含み、
前記書込み制御手段は、
１．ホストからレコード（新レコード）の書込み要求を受取る手段と、
２．新レコードのハッシュ値（新Ｓ）を計算する手段と、
３．バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認する手段と、
４．前記確認ステップ３でバッファ２に新Ｓが存在する場合、新データが前記新Ｓに対応する（結びつく）レコードと一致するかを比較する手段と、
５．前記比較ステップ４で新レコードと前記レコードが一致する場合（Ｙｅｓ）は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとしてテープに書込む手段とを含む書込み制御を有することを特徴とする。
【００２０】
本発明によれば、記憶装置における書込みデータの重複を極力排除する方法を提供して、大容量の記録媒体の有効利用を可能にする。
【図面の簡単な説明】
【００２１】
【図１】本実施形態が適用されるテープドライブ１０の構成例を示す。
【図２】実施例の構成要素（バッファ１、バッファ２、テープ）及び本発明の重複データの書込み及び読み出し機構を示す。
【図３】ホストからテープドライブにレコードを書き込む場合のテープドライブの重複排除の書込み方法のフローチャートを示す。
【図４】本発明の重複排除の書込み方法のより記録されたレコードを読み出すフローチャートを示す。
【発明を実施するための形態】
【００２２】
以下において、本発明のテープドライブにおける重複データの排除の方法について、典型的な実施形態（以下「実施例」という）が説明される。これら実施例は例示であり、テープドライブ以外の記憶装置に提供することを排除しない。
【００２３】
テープドライブ単体でＤｅｄｕｐをサポートする手法を考案した。テープドライブが持つ一時記憶領域（例えばＤＲＡＭ）を新たにＤｅｄｕｐのための２つのバッファを用意する。バッファ１は、すでに書き込まれたレコードのレコードＮｏとレコードに格納されたデータのハッシュ値を対応させたテーブルを保存する。バッファ２は、書込み頻度の高いレコードをハッシュ値又はレコードＮｏに紐付けて保存する。書込み頻度（「頻度」とも言う）は、同じレコードについてのホストから書込み要求回数であり、一つのレコードについての重複レコードデータの数を意味する。レコードＮｏは、ホストが過去込み時に可変長のレコードのＮｏ（番号）を指定する指標である。テープドライブは、Ｎｏに結びつけてレコードの内容をテープに書込み、そのＮｏを指定されたレコードをテープから読み出す。
【００２４】
ホストからテープドライブにレコードを書き込む場合、まずそのレコードのハッシュ値を計算する。そのハッシュ値がバッファ２に格納されていれば、新たに書き込むレコードとバッファ２に格納されたそのハッシュ値に対応するレコードの内容を比較する。比較の結果が同一であることが確認された場合にはレコード本体を書き込む変わりに、すでに書き込んだ同内容のレコードＮｏを持つ特殊なレコードを保存する。レコードＮｏで指定されたテープ上のレコードは、そのレコード自体の内容を示す。
【００２５】
本発明では、テープに書込むデータとして特殊なレコードとしてポインタを与える。ポインタは、レコードを特定するレコードＮｏ及び所定の印（指標）を情報として含む。ポインタにレコードＮｏに含ませるのは、既にテープに書き込まれた他のレコードを特定するレコードＮｏに特定するためである。他のレコードＮｏを含んでいることを示す指標は、読取り情報がホストにより送られたレコード内容自体でなく他のレコードＮｏを含んでいることをテープドライブに区別させるためである。また、ポインタは、テープに書込まれたレコードＮｏではなくバッファ２に保存されたレコードＮｏ（エントリＮｏ）であってもよい。この場合、ポインタの指標は、テープのレコードＮｏとバッファ２に保存されたレコードのＮｏ（エントリＮｏ）とを区別する必要がある。なお、ポインタは、実際のレコード自体の容量より十分小さな値であるため、バッファ1及び２に容量領域を多くは占めない。バッファ１が１００ＭＢ程度の場合、一般的なレコードサイズに基づくレコード数であるならば、全てレコードをバッファ１の各エントリに含ませることが出来る。
【００２６】
本発明の実施例を詳述するために、テープドライブの動きについて説明する。
図１は、本実施形態が適用されるテープドライブ１０の構成例を示す。テープドライブ１０は、ホスト３０から送られた複数のデータ（レコードとも言う）を固定長のデータセット（ＤＳ）単位でテープ記録媒体への書込み（Ｗｒｉｔｅ）または、テープ媒体からＤＳ単位で読み出す（Ｒｅａｄ)。ＤＳは複数の可変長のレコードの集まりであり、固定長のフォーマット構造を有する。
【００２７】
テープドライブ１０は、インターフェイス１１、バッファ１２、チャネル１３、ヘッド１４、モータ１５、テープ２３を巻きつけるリール２２、及びこれらの制御システムを含む。制御システムは、書込み読取り制御１６、ヘッド位置制御システム、及びモータドライバ１８を含む。モータ１５は、２個のモータを設けてよい。テープドライブ１０は、テープカートリッジ２０を着脱可能に搭載する。
【００２８】
テープカートリッジ２０は、リール２１に巻かれたテープ２３を含む。テープ２３は、リール２１、２２の回転に伴い、リール２１からリール２２の方向へ、又は、リール２２からリール２１の方向へ、長手方向に移動する。テープ２３は、磁気テープ以外のテープ媒体でもよい。テープカートリッジは、テープのデータの記録属性（テープディレクトリと呼ばれる）の情報を、カートリッジメモリ（ＣＭ：Cartridge Memory）２５と呼ばれる不揮発性メモリに保持している。テープドライブは、読み出し（Ｒｅａｄ）時に、テープカートリッジ内に装備されたＣＭ２５からディレクトリ情報を読み取り、ヘッド１４に対してテープ２３を目的位置まで高速に移動させる。搭載されたテープカートリッジ２０のＣＭ２５は、テープドライブ１０により非接触的に読み書される。ＣＭは、テープカートリッジの属性情報が保存されたメモリマップを含む。
【００２９】
書込み読取り制御１６は、テープドライブ１０の全体を制御する。この制御を介して、ヘッド１４は、テープ２３が長手方向に移動するとき、テープ２３に対して情報を書き込んだり、テープ２３から情報を読出したりする。また、モータ１５は、リール２１、２２を回転させる。１つのモータ１５を表しているが、リール２１、２２の各々に１つずつのモータを設けるのが好ましい。
【００３０】
例えば、インターフェイス１１で受け付けたコマンドに従って、データのテープ２３への書込みやテープ２３からの読取りを制御する。また、ヘッド位置制御システム１７やモータドライバ１８の制御、及び、書込みデータへの訂正符号の付加・読取りデータのエラー訂正も行う。モータドライバ１８は、モータ１５を駆動する。
【００３１】
インターフェイス１１は、上位装置の一例であるホスト３０との通信を行う。ホスト３０から、テープ２３を目的の位置に移動させるコマンド、テープ２３へのデータの書込みを指示するコマンド、テープ２３からのデータの読取りを指示するコマンドを受け取る。それぞれは、位置決めコマンド、Ｗｒｉｔｅコマンド及び同期コマンド（Ｆｌｕｓｈ）、Ｒｅａｄコマンドに相当する。また、インターフェイス１１は、ホスト３０に対し、これらのコマンドに応じた処理が成功したのか失敗したのかの応答を返す。ホスト３０は、これらコマンドに可変長のデータの位置、数を指定してテープドライブ１０に発行する。
【００３２】
バッファ１２は、テープ２３に書き込むべきデータやテープ２３から読出されたデータを蓄積するメモリである。例えば、メモリはＤＲＡＭによって構成される。また、バッファ１２は、複数の固定長のバッファセグメントからなり、各バッファセグメントが、テープ２３に対する読み書きの単位であるＤＳを格納している。１つのデータセットは、ホスト３０から送られるデータの１つの一部分、または、複数のデータから構成される。読み書きチャネル１３を介して渡されたデータはＤＳ単位（例えば４００ＫＢまたは１．６ＭＢ）として、ヘッド１４によりテープ２３に書込まれる。同期コマンドはバッファ内に保管されたデータをテープに書く込み命令である。
【００３３】
図２は、実施例の構成要素、及び本発明の重複データの書込み及び読み出し機構を示す。バッファ１及び２を用いて頻出データについて重複データを管理する本発明の実施例の説明をする。Ｄｅｄｕｐ用のバッファとして、テープドライブ上に１〜４ＧＢ程度の一時記憶域（バッファ、例えばＤＲＡＭ）を確保できる。テープメディアの容量が１ＴＢ程度であることから、このバッファ容量では当然ならが全てのレコードをバッファに保存することはできない。言い換えると、バッファ容量は絶対的にテープ容量に比べて０．１〜０．４％と小さいためバッファに保存するレコードを取捨選択する必要がある。
【００３４】
バッファ１にはハッシュ値毎のエントリを保存し、各エントリには更に１または複数のレコードＮｏを対応させて含ませてもよい。バッファ２にはハッシュ値及びレコードＮｏに加えレコードの内容そのものを保存する。バッファ２には、レコードＮｏの代わりにレコードＮｏを特定するポインタを含ませてもよい。バッファ１は、全てのデータのハッシュ値とその書込頻度を記録するために利用する。バッファ２は、バッファ1 より書込み頻度が高いことが確認されたデータの本体を記録するために利用する。書込み頻度の観測するためのバッファ１と、レコード本体を保持するバッファ２とを区別する。２つのバッファの独立に管理することにより、任意の時点で書込み頻度の高いデータのみを動的にバッファ２に残すことができる。
【００３５】
図２は、バッファ１及び２を用いて頻出データについて重複データを管理する図の説明を示す。バッファ１は、すでにテープ書込まれた全てのレコードについて、そのレコードの・ハッシュ値、及び、・書込み頻度を記録する。バッファ１の各エントリ（各枠）は、ハッシュ値についてテープに記録されている全てのレコード（Ａ，Ｂ，Ｃ・・・）を保存したエントリを含むディレクトリのようなものである。各エントリは、レコードＮｏを含ませてもよい。全てのレコードについてこれらの値を保存しても１００ＭＢ程度のバッファ容量で足りる。レコードＡ，Ｂは同じハッシュ値を有するとして同じエントリに含まれている。頻度は同じハッシュ値を与える全てのレコードについての値である。ここでハッシュ値は、可変長なレコードを代表する数値を得る少ない桁数の固定長データで集約して代表値である。なおハッシュ値が同じでも最終的にレコード内容が一致するとか限らない。最終的にはハッシュ値が同一であることを前提として、レコードの内容自体を対比することにより最終的な一致を確認する。
【００３６】
バッファ２を構成する各エントリに、レコード内容をレコードＮｏ及びハッシュ値に紐付けて保存する。図２ではレコードＡ、Ｂ、Ｃ・・・のそれぞれのハッシュ値に結びつけて保存される。レコードＡ、Ｂ、Ｃは比較的頻度の大きいデータであるため、バッファ２に保存されている。バッファ１及び２は合計でも1〜４ＧＢであり、テープ容量（〜１ＴＢ程度）に対して０．５％以下である。書込み頻度の所定値は、テープの全容量に対してバッファ２の大きさを考慮して決定される。書込み頻度が所定値以上のレコードについて、レコード内容をハッシュ及びポインタと結びつけてバッファ２に保存される。なお図２では、簡単のために各エントリにはポインタではなく単にレコードＮｏのみを表示している。レコードが所定値以上の書込み頻度であれば、今後も書込み要求される可能性が高いとしてバッファ２に保存する。一定以上の書込み頻度のレコードを、限られた容量のバッファ２に保持しておけば、レコードの対比確認のパフォーマンス、テープ容量の節約、及び読みよりパフォーマンスに向上が図られる。所定値は、テープに重複して記録された同一レコードの数に対して（バッファ２の容量）／（テープ容量）の値に基づいて与えられる。また所定値は、テープに記録され重複レコード数の上限値により決定されてもよい。所定値が、少なくとも３以上であるとしてもよい。新たに書込み要求されたレコードの頻度は所定値より小さい場合は、バッファに保存されず、テープ上のデータを参照するのみである。また、バッファ２に保存されるレコードに容量の不足が生じた場合、所定値を変動させて空き領域を確保できる。所定値を大きくすることにより、既に保存されていたレコードであっても、頻度が所定値より小さくなったものをバッファ２から削除する。バッファ２から削除による整理が行われても、テープ上には本来のレコードＮｏにレコード内容は記録されているので、データの保全性（Ｄａｔａ Ｉｎｔｅｒｇｉｒｉｔｙ）は保証される。
【００３７】
図２に基づいて、重複の書込み機構を説明する。ホストから新たなレコード（新レコード）を受け取ると、テープドライブはデータバッファ上に保管された新レコードのハッシュ値を算出する。このハッシュ値をバッファ２の各エントリに保存されたハッシュ値と対比して存在を確認する。この確認は、バッファ２の各エントリに保管されたデータと新レコードとの間で行われ、テープから読み出す必要はない。この確認においてデータが一致した場合は、テープにはバッファ２のエントリに一致したレコードＮｏのテープ上に既に書き込まれたレコードＡ，Ｂ，Ｃ・・・のＮｏを含むポインタを書込む。テープドライブは、このポインタはテープ上にレコードＡのＮｏを指している。この比較確認においてバッファ２には同一ハッシュ値は存在するがエントリも存在しない場合、所定値以上のテープ上に重複レコードがないことを意味する。この場合はレコード書込みの頻度が所定値に達するまでテープドライブは通常の書込みをテープに行う。バッファ１においてエントリも存在しないレコードの場合、バッファ１に新レコードのエントリ（ハッシュ値、頻度、及びレコードＮｏ）を新たに設ける。バッファ２にレコードの内容自体をデータＮｏ及びハッシュ値に結びつけて保持する。なお、バッファ２でのレコード内容の保存は、容量を限定するする必要上所定値以上の頻度ものに限定される。言い換えると、レコードの書込み頻度が所定値に達するまではテープには重複してレコードの書込が行われる。
【００３８】
図２に基づいて、本発明により書込まれたレコードの読み出し機構を説明する。ホストからレコードＮｏを指定してレコードを読み出す命令を受け取った場合、テープドライブはテープ上のポインタを読み取ったかを確認する。ポインタの存在は、バッファ２でのレコードの保持の可能性を確認できる。読み出し要求レコードがバッファ２に存在する場合は、バッファ２から読み出してテープ自体の元来のデータを読みだす必要はない。読み出しレコードがバッファ２に存在しない場合は、通常通りテープから読み出す操作を行う。
【００３９】
図３は、ホストからテープドライブにレコードを書き込む場合のテープドライブの重複排除の書込み方法のフローチャートを示す。
（１）ホストから新たなレコード（新レコード）の書き込み要求をテープドライブは受取る。
（２）テープドライブは、新レコードのハッシュ値（新Ｓ）を計算する。
（３）バッファ２に新Ｓが存在するか確認する。
なおバッファ１において頻度が所定値以上である場合にバッファ２にＳのレコード内容が存在すると判断してもよい。
（４）確認ステップ３においてバッファ２に新Ｓが存在する判断された場合、新データがバッファ２のエントリ中において新Ｓに結びつくレコードと一致するかを比較する。
（５）比較ステップ４において新レコードとバッファ２に保存されたレコードが一致する場合（Ｙｅｓ）、既にテープに書込み済みレコードのＮｏを含むポインタを新レコードの書込みデータとしてテープに書込む。図２を参照すると、テープに書込むポインタＡ，Ｂ，Ｃの確保には、既にバッファ２の各エントリに保存されたレコードＡ，Ｂ，ＣのＮｏを利用できる。ポインタは、後でテープドライブが読み取りデータがレコードＮｏであることを判断できるようにその指標も含む。
（６）ステップ３でバッファ２に新Ｓが存在しない場合（Ｎｏ）、バッファ１に新Ｓが存在するかを確認する。
（７．１）確認ステップ６においてバッファ１に新Ｓが存在する場合（Ｙｅｓ）、または、比較ステップ４においてバッファ２に保存されたレコードと一致しない場合（Ｎｏ）、バッファ１に所定のエントリの頻度のカウンターを１つ増加させる。頻度は同一のハッシュ値のレコード書込みの頻度を示す。
（７．２）バッファに保存された新レコードの頻度が所定値以上か確認する。
（７．３）確認ステップ（７．２）において頻度が所定値以上の場合（Ｙｅｓ）、バッファ２のエントリに、新レコードの内容を新しいハッシュ値及び新レコードのＮｏと併せて保存する。
（８）テープドライブは、確認ステップ６でバッファ１に新Ｓが存在しない場合（Ｎｏ）、新レコードの新ＳについてレコードＮｏ及び頻度＝１をバッファ１に保存する。
（９）テープドライブは、レコードをテープに書き込む。
・ステップ８の処理後、新データをテープに書込む。
・確認するステップ（７．２）において新レコードの書込み頻度は所定値以下の場合（Ｎｏ）、バッファ２への新レコードＮｏ及びレコード内容の保存はスキップされる。その後、このステップ９において通常のレコード書込みを行う。この通常書込みは、頻度が所定値に達するまではテープに同一レコードの書込みを許容する。バッファ２の容量にテープ容量に対して制限的な値１％以下であるため、完全なレコードの重複書込を排除するのは現実的でない。本発明の方法は、大容量の記憶装置に対してレコードの重複回数の上限値を設けることが出来でき、容量の有効利用できる点で意義はある。
【００４０】
図４は、本発明の重複排除の書込み方法のより記録されたレコードを読み出すフローチャートを示す。一つの実装例として、ホストからテープドライブにデータを読み出す場合のテープドライブの振る舞いを読み出し方法のステップを説明する。
（１）テープドライブは、ホストからレコードの読み出し要求を受取る。
ホストは、レコードＮｏを指定してテープドライブにレコードの読出し命令を出す。
（２）テープドライブは、テープから指定されたレコードを読み出す。
（３）テープドライブは、読み出したレコードがテープに記録された他のレコードへのポインタかを確認する。読み出されたデータが、ポインタである場合は所定の指標でもってレコードＮｏであることがわかる。なお、その指標がレコードＮｏまたはバッファ２のエントリＮｏのどちらかを示す。
・指標がテープのレコードの場合、レコードＮｏで指定されたレコードが読み出し対象である。
・指標がバッファ２のレコードの場合、バッファ２のエントリＮｏで指定されたエントリ内のレコード内容を読み出し対象である。
・なお、このステップ３においてポインタでない場合（Ｎｏ）、ステップ７において通常通りのテープからレコードを読み出す。
（４）ステップ３においてポインタである場合（Ｙｅｓ）、ポインタに対応するレコードがバッファ２に存在するかを確認する。
（５）ステップ４においてレコードが存在する場合（Ｙｅｓ）、バッファ２ に格納されたポインタに対応するレコードを読み出してホストに送る。また、ポインタがバッファ２のエントリへの指標である場合、そのエントリＮｏで指定されたレコードが読み出し対象となる。
（６）ステップ４においてレコードが存在しない場合（Ｎｏ）、ポインタが指し示すレコードをテープから読み出す。ポインタがテープのレコードのレコードＮｏのための指標と確認される場合である。その指標により、テープドライブは、テープから読み取られたレコードＮｏで指定されたレコードが読み出し対象とされる。
（７）テープドライブは通常通り読み出したレコードをホストに送る。
・読み出しステップ６において読み出されたレコードをホストに送る。
・確認ステップ３においてレコードがポインタでない場合（Ｎｏ）、読み出したレコードをホストに送る。
【００４１】
バッファ１及びバッファ２の内容の保持には、既存のテープドライブが詳細なテープディレクトリを保存するための特別なデータセット（Housekeeping データセット）を利用できる。テープドライブは、テープカートリッジを取り出すとき、このデータセットにバッファ１及び２のエントリの内容を保存する。テープをテープドライブに挿入した直後に、テープディレクトリを読み出す手法を用いることにより、テープに記録された特別なデータセットからバッファ1及び２の内容を引き出せばよい。また、テープドライブは、不揮発性メモリ（例えばＣＭ）を利用することによりテープドライブからテープ媒体を取り出す操作が行われてもバッファ１及びバッファ２の内容を保持し続けることができる。
【００４２】
本発明の書込み方法は、テープへのアクセスを省略できるため書込みパフォーマンスに大きな影響を与えることなくＤｅｄｕｐを可能とし、テープ容量を有効利用できる。
【００４３】
以上の本発明の実施は、典型的なシーケンシャル・デバイスであるテープドライブについて説明された。２つの区別された一時記憶装置ランダムアクセスはメインの記憶容量に対して１％に満たない容量である。この一時記憶領域を本発明のように利用することは、重複したレコードの書込み回数を管理できる点で有利である。したがって、本発明の適用範囲はテープドライブに限定されず、本発明はランダムアクセスの記憶装置、典型的にはＤＡＳＤにも適用できる。
【符号の説明】
【００４４】
１０…テープドライブ、
１１…インターフェイス、
１２…バッファ（ＤＲＡＭ）、
１３…読み書きチャネル、
１４…ヘッド、
１５…モータ、
１６…書込み読取り制御（コントローラ）、
１７…ヘッド位置制御システム、
１８…モータドライバ、
２０…カートリッジ、
２１，２２…リール、
【特許請求の範囲】
【請求項１】
記憶装置への書込みレコードの重複を排除する書込み方法であって、
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む、前記方法であって、
ホストからレコード（新レコード）の書込み要求を受取るステップと、
新レコードのハッシュ値（新Ｓ）を計算するステップと、
バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認するステップと、
前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、
前記比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新レコードの書込みデータとして記録媒体に書込むステップと、
を含む重複排除の書込み方法。
【請求項２】
前記方法は更に、前記比較ステップで新レコードと前記バッファ２に保存されたレコードとが一致しない場合、バッファ１に記録された頻度を１増分し、新レコードの頻度が所定値以上の場合、バッファ２に新レコード内容を新Ｓ及びポインタと併せて保存するステップと、
前記保存ステップの処理後、新データを記録媒体に書込むステップと、を実行させる請求項１に記載の方法。
【請求項３】
前記方法は更に、前記確認ステップでバッファ２に新Ｓが存在しない場合、バッファ１に新Ｓが存在するかを確認するステップと、
前記確認ステップでバッファ１に新Ｓが存在する場合、バッファ１に記録された頻度を１増分し、新レコードの頻度が所定値以上の場合、バッファ２に新レコード内容を新Ｓ及びポインタを保存するステップと、
前記保存ステップの処理後、新データを記録媒体に書込むステップと、を含む請求項１に記載の方法。
【請求項４】
前記方法は更に、前記確認ステップでバッファ２に新Ｓが存在しない場合、バッファ１に新Ｓが存在するかを確認するステップと、
前記バッファ１での確認ステップでバッファ１に新Ｓが存在しない場合、新レコードの新Ｓについてポインタ及び頻度１をバッファ１に保存するステップと、
前記バッファ１での保存ステップの処理後、新データを記録媒体に書込むステップと、を実行させる請求項１に記載の方法。
【請求項５】
バッファ１は、記録媒体に記録された全てのレコードをハッシュ値について保存したエントリを有し、
バッファ２は、前記エントリのうち書込み頻度が所定値以上について新レコードの内容を前記ハッシュ及びポインタと結びつけて保存するエントリを有す、請求項１〜４の何れか１に記載の方法。
【請求項６】
前記所定値は、記録媒体に重複して記録された同一レコードの数に対して（バッファ２の容量）／（記録媒体の容量）の値に基づいて決定される請求項５に記載の方法。
【請求項７】
前記所定値は、記録媒体に重複して記録された同一レコードの数に対して設定された上限値により決定された請求項６に記載の方法。
【請求項８】
記憶装置から記録レコードを読み出す方法であって、
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む、前記方法であって、
ホストからポインタを指定したレコードの読出し命令を受取るステップと、
前記レコードに関するデータを記録媒体から読出すステップと、
前記レコードのデータが記録媒体に記録された前記レコードのポインタであるかを確認するステップと、
前記確認ステップで前記データがポインタである場合、前記ポインタに対応するレコードがバッファ２上に存在するか確認するステップと、
前記確認ステップでバッファ２に前記ポインタに対応するレコードが存在する場合、バッファ２から前記レコードを読み出してホストに送るステップと、
を実行する読み出し方法。
【請求項９】
前記ポインタに対応するレコードがバッファ２に存在するか確認するステップで、対応レコードが存在しない場合前記データが、前記ポインタが指している記録媒体上のレコードを読み出すステップと、
前記レコードを読み出し要求の前記レコードとして読み出してホストに送るステップと、を含む請求項８に記載の方法。
【請求項１０】
書込みレコードの重複を排除する記憶装置であって、
記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、
レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２と、
記録媒体へのレコードの書込を制御する書込み制御手段とを含み、
前記書込み制御手段は、
ホストからレコード（新レコード）の書込み要求を受取る手段と、
新レコードのハッシュ値（新Ｓ）を計算する手段と、
バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認する手段と、
前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較する手段と、
前記レコードの一致の比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込む手段とを含む書込み制御を有する、記憶装置。
【請求項１】
記憶装置への書込みレコードの重複を排除する書込み方法であって、
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む、前記方法であって、
ホストからレコード（新レコード）の書込み要求を受取るステップと、
新レコードのハッシュ値（新Ｓ）を計算するステップと、
バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認するステップと、
前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較するステップと、
前記比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新レコードの書込みデータとして記録媒体に書込むステップと、
を含む重複排除の書込み方法。
【請求項２】
前記方法は更に、前記比較ステップで新レコードと前記バッファ２に保存されたレコードとが一致しない場合、バッファ１に記録された頻度を１増分し、新レコードの頻度が所定値以上の場合、バッファ２に新レコード内容を新Ｓ及びポインタと併せて保存するステップと、
前記保存ステップの処理後、新データを記録媒体に書込むステップと、を実行させる請求項１に記載の方法。
【請求項３】
前記方法は更に、前記確認ステップでバッファ２に新Ｓが存在しない場合、バッファ１に新Ｓが存在するかを確認するステップと、
前記確認ステップでバッファ１に新Ｓが存在する場合、バッファ１に記録された頻度を１増分し、新レコードの頻度が所定値以上の場合、バッファ２に新レコード内容を新Ｓ及びポインタを保存するステップと、
前記保存ステップの処理後、新データを記録媒体に書込むステップと、を含む請求項１に記載の方法。
【請求項４】
前記方法は更に、前記確認ステップでバッファ２に新Ｓが存在しない場合、バッファ１に新Ｓが存在するかを確認するステップと、
前記バッファ１での確認ステップでバッファ１に新Ｓが存在しない場合、新レコードの新Ｓについてポインタ及び頻度１をバッファ１に保存するステップと、
前記バッファ１での保存ステップの処理後、新データを記録媒体に書込むステップと、を実行させる請求項１に記載の方法。
【請求項５】
バッファ１は、記録媒体に記録された全てのレコードをハッシュ値について保存したエントリを有し、
バッファ２は、前記エントリのうち書込み頻度が所定値以上について新レコードの内容を前記ハッシュ及びポインタと結びつけて保存するエントリを有す、請求項１〜４の何れか１に記載の方法。
【請求項６】
前記所定値は、記録媒体に重複して記録された同一レコードの数に対して（バッファ２の容量）／（記録媒体の容量）の値に基づいて決定される請求項５に記載の方法。
【請求項７】
前記所定値は、記録媒体に重複して記録された同一レコードの数に対して設定された上限値により決定された請求項６に記載の方法。
【請求項８】
記憶装置から記録レコードを読み出す方法であって、
前記記憶装置は、記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２とを含む、前記方法であって、
ホストからポインタを指定したレコードの読出し命令を受取るステップと、
前記レコードに関するデータを記録媒体から読出すステップと、
前記レコードのデータが記録媒体に記録された前記レコードのポインタであるかを確認するステップと、
前記確認ステップで前記データがポインタである場合、前記ポインタに対応するレコードがバッファ２上に存在するか確認するステップと、
前記確認ステップでバッファ２に前記ポインタに対応するレコードが存在する場合、バッファ２から前記レコードを読み出してホストに送るステップと、
を実行する読み出し方法。
【請求項９】
前記ポインタに対応するレコードがバッファ２に存在するか確認するステップで、対応レコードが存在しない場合前記データが、前記ポインタが指している記録媒体上のレコードを読み出すステップと、
前記レコードを読み出し要求の前記レコードとして読み出してホストに送るステップと、を含む請求項８に記載の方法。
【請求項１０】
書込みレコードの重複を排除する記憶装置であって、
記録媒体に記録されたレコードのＮｏ、レコードのハッシュ値、及び書込み頻度を保存するバッファ１と、
レコードの内容を前記レコードＮｏ及びハッシュ値に結びつけて保存するバッファ２と、
記録媒体へのレコードの書込を制御する書込み制御手段とを含み、
前記書込み制御手段は、
ホストからレコード（新レコード）の書込み要求を受取る手段と、
新レコードのハッシュ値（新Ｓ）を計算する手段と、
バッファ２に新データのハッシュ値（新Ｓ）が存在するか確認する手段と、
前記確認ステップでバッファ２に新Ｓが存在する場合、新データが新Ｓに対応するバッファ２に保存されたレコードと一致するかを比較する手段と、
前記レコードの一致の比較ステップで新レコードと前記レコードが一致する場合は、既に記録媒体またはバッファに保存済みレコードへのポインタ（レコードＮｏ）を新データの書込みデータとして記録媒体に書込む手段とを含む書込み制御を有する、記憶装置。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−９４２２０（Ｐ２０１２−９４２２０Ａ）
【公開日】平成２４年５月１７日（２０１２．５．１７）
【国際特許分類】
【出願番号】特願２０１０−２４２２３８（Ｐ２０１０−２４２２３８）
【出願日】平成２２年１０月２８日（２０１０．１０．２８）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
【公開日】平成２４年５月１７日（２０１２．５．１７）
【国際特許分類】
【出願日】平成２２年１０月２８日（２０１０．１０．２８）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【Ｆターム（参考）】
[ Back to top ]