JP3201920B2

JP3201920B2 - データ記憶システム及びその操作方法

Info

Publication number: JP3201920B2
Application number: JP03955895A
Authority: JP
Inventors: ジェームズ・ティー・ブラディー; ジョー＝ミン・チェン; オデド・コーン; ジェームズ・ダブリュー・エルドリッジ; ヨラム・ノヴィク; ノーマン・ケイ・オーウチ; ダニト・セゲヴ
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1994-05-11
Filing date: 1995-02-28
Publication date: 2001-08-27
Anticipated expiration: 2016-08-27
Also published as: JPH0863294A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、一般的には情報記憶装
置および方法に関し、より具体的には圧縮データを使用
するデータ記憶装置および方法に関する。

【０００２】

【従来の技術】ディスクなどの大容量記憶媒体上に格納
できるデータの量を拡大し、それにより、顧客データの
単位当たりの記憶装置コストの比率を低下させるため、
データ圧縮が使用されている。データ圧縮を使用する
と、それに付随してディスクのパフォーマンスが向上す
る場合もある。データ圧縮アルゴリズムを既存および将
来の低コスト・ハードウェアで実現することが多くのユ
ーザの関心を集め、データ圧縮の利用がさらに普及する
ものと予想される。

【０００３】ディスク・ベースの製品でデータ圧縮を使
用する場合、従来の方法では、圧縮するデータを同サイ
ズの圧縮単位に分割している。通常、圧縮／圧縮解除ハ
ードウェアの操作対象は、完全な圧縮単位に限られる。
つまり、圧縮／圧縮解除ハードウェアによって圧縮単位
内の特定のデータ要素の前にあるすべてのデータが先に
圧縮解除されない限り、圧縮単位からそのデータ要素を
取り出す（読み取る）ことができない。データ要素を保
管する際は、圧縮／圧縮解除ハードウェアによってその
要素が入っている圧縮単位全体が圧縮されてから、ディ
スクに保管される。したがって、圧縮単位よりかなり小
さい小規模読取り（たとえば、単一レコードなどのデー
タ要素の読取り）を実行する場合、効率が下がることに
なる。

【０００４】さらに、所与の圧縮単位の圧縮係数（比）
はデータによって異なる。その結果、２つの圧縮単位
（未圧縮長が同じ）から長さの異なる圧縮イメージが得
られる場合もある。すべてのディスク空間を使用するた
め、圧縮イメージはディスクに連続して保管される。し
たがって、直接アクセスを可能にするために、圧縮単位
の数に比例するサイズを有するディレクトリに圧縮単位
の位置が保管される。パフォーマンス上の理由から、こ
のディレクトリは高速（かつ比較的高価な）制御メモリ
で実現することが好ましい。このため、コストおよびパ
フォーマンスの観点から圧縮単位の大型化が強く奨励さ
れている。

【０００５】しかし、データ圧縮指向の大容量記憶シス
テム、特に、ディスク・システムには、レコード読取り
などの小規模読取り操作に必要な接続時間と応答時間と
いうパフォーマンス上の重大な欠点がある。この問題を
解決するか少なくとも改善するための従来の手法では、
追加の制御情報が必要なため、大量の制御メモリ空間が
消費される。この制御メモリ空間を半導体メモリで実現
すると、コスト、パッケージのボリューム、および消費
電力の増加が発生する。

【０００６】

【発明が解決しようとする課題】このため、本発明の一
目的は、より小規模の圧縮単位を使用する場合に必要な
ものと比較して、ごく少量の情報をディレクトリに追加
するだけで、レコード読取り操作時の接続時間を短縮す
る方法を提供することにある。

【０００７】本発明の他の目的は、制御情報の追加量を
大幅に増加せずに、圧縮ディスク・トラックからの小規
模読取り操作の実行時に発生する接続時間と応答時間を
ともに短縮することにある。

【０００８】

【課題を解決するための手段】本発明は、ディレクトリ
内のみの使用項目数を増加するのではなく、ディレクト
リとディスクそのものの両方のデータ構造の組合せを使
用して管理する新規の方法を教示する。本発明の技法を
使用すると、各圧縮単位のサイズを縮小するという技法
の場合より、必要な追加ディレクトリ・メモリ量が削減
される。

【０００９】このように、前記およびその他の問題の克
服と、本発明の目的の実現は、少なくとも１個のディス
クで構成されるデータ記憶システムを操作する方法によ
って達成される。本方法は、データ圧縮単位を２以上の
ｎ個の基本圧縮単位に区分するステップを含む。各デー
タ圧縮単位は、複数のディスク・セクタで構成され、ｎ
個の基本圧縮単位のそれぞれは異なる初期セクタから始
まる。次のステップでは、データ圧縮単位をｎ未満のＸ
個の間隔に区分する。Ｘ個の間隔のそれぞれは異なる初
期セクタから始まり、しかもｎ個の基本圧縮単位の１つ
の範囲内にある。本方法のその他のステップとしては、
１／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各間隔
が始まるｎ個の基本圧縮単位の１つの初期セクタをそれ
ぞれ指す複数の第一のポインタを少なくとも１個のディ
スクの外部に格納するステップと、１／Ｘ、２／Ｘ、・
・・、（Ｘ−１）／Ｘという各間隔が始まるｎ個の基本
圧縮単位のそれぞれの各初期セクタ内に、その基本圧縮
単位内で始まる間隔の初期セクタを指す第二のポインタ
を格納するステップと、Ｘ個の間隔の１つの範囲内に位
置するセクタの１つから始まる圧縮データ単位を読み取
るディスク読取り操作に対する応答として、第一のポイ
ンタの１つと第二のポインタの１つにより圧縮データ単
位の開始セクタにアクセスするステップがある。

【００１０】圧縮データ単位の開始セクタは対象セクタ
（ＳＯＩ）と呼ばれ、アクセス・ステップは、ＳＯＩを
含む間隔が始まる目標基本圧縮単位の初期セクタを決定
するために第一のポインタを使用するステップと、目標
基本圧縮単位の初期セクタで少なくとも１個のディスク
から圧縮データの読取りを開始するステップと、第二の
ポインタの値を求めるために読み取ったデータを圧縮解
除するステップと、ＳＯＩを含む間隔の初期セクタに達
するまで圧縮解除データを破棄するステップとを含む。

【００１１】通常、圧縮単位は、複数のセクタで構成さ
れる少なくとも１つの圧縮レコードを含み、アクセス・
ステップは、所定のデータ圧縮比に基づいてセクタの必
要数を予測することで圧縮レコードを格納するために複
数のセクタを割り振る初期ステップを含む。この割振り
ステップは、レコードの実際の圧縮比を求め、そのレコ
ード内の同一文字の最長ランの値を求め、同一文字の最
長ランの値に基づいて実際の圧縮比を調整するステップ
を含む。また、割振りステップは、ディスクの別の領域
に圧縮レコードを再書込みせずに圧縮レコードを後でそ
の位置で更新できるようにするため、予測数に少なくと
も１つの追加セクタを追加するステップを含む。

【００１２】

【実施例】図１のブロック図について説明するが、同図
は本発明により構築および操作されるデータ処理システ
ム１０を示している。システム１０は関連キャッシュ・
メモリ１２ａを有するデータ処理装置１２を含む。この
キャッシュ・メモリ１２ａは不揮発性記憶（ＮＶＳ）装
置で構成することができる。データ処理装置１２、より
具体的にはキャッシュ・メモリ１２ａには、データ経路
１２ｂと、関連のディスク・データ記憶システム１４が
両方向に結合されている。ディスク・データ記憶システ
ム１４は、１つまたは複数のディスク装置で構成するこ
とができる。たとえば、図示の実施例では、ディスク・
データ記憶システム１４が第一のディスク装置１４ａと
第二のディスク装置１４ｂとで構成されている。各ディ
スク装置は、それぞれが第一のデータ記憶面１５ａと第
二のデータ記憶面１５ｂとを有する、１〜ｎ個の個別デ
ィスクで構成することができる。各面は、従来の方法で
複数のトラック１５ｃに区分されている。

【００１３】本発明の好ましい実施例のディスク・デー
タ記憶システム１４は、"A Case for Redundant Arrays
of Inexpensive Disks（RAID）"という論文（ACM SIGM
OD Conference, Chicago, IL, 1988年6月1〜3日, pp. 1
09-116）において D. A. Patterson、G. Gibson、およ
びR. H. Katz が説明しているＲＡＩＤ３またはＲＡＩ
Ｄ５システムに多少似ているＲＡＩＤシステムとして構
成され、操作される。ＲＡＩＤ手法の利点は、ＲＡＩＤ
を使用することでデータ処理装置のディスク・サブシス
テムがプロセッサの速度やメイン・メモリの密度の改良
の連続に遅れずに対応できる点である。

【００１４】前記の論文では、５つのレベルのＲＡＩＤ
が論じられている。レベル１ではミラー・ディスク（デ
ータ・ディスクとチェック・ディスクの両方を含むすべ
てのディスクの完全冗長）を使用し、レベル２ではチェ
ック・ディスクの個数を減らすためにエラー訂正情報用
のハミング・コードを使用し、レベル３ではデータ・デ
ィスク・グループごとに１個のチェック・ディスクを使
用し、レベル４では個々の転送情報を単一ディスク装置
に収容して複数のディスクに分散しないようにした、独
立読取り／書込み操作を使用し、レベル５（ＲＡＩＤ
５）ではデータとデータ保全性（パリティ）情報を、チ
ェック・ディスクを含むすべてのディスクに分散する。

【００１５】ただし、ＲＡＩＤタイプのディスク・デー
タ記憶システムを使用することが本発明を実施する際に
制限として解釈されないことに留意されたい。

【００１６】システム１０は、本発明の教示により動作
するディスク・マネージャ１６をさらに含む。ディスク
・データ記憶システム１４とディスク・マネージャ１６
との間には、必要なディスク・デバイス・ドライバ１８
が結合されている。このドライバ１８は、ディスク装置
１４ａおよび１４ｂの読み書きを可能にするためにロー
・レベルでディスク装置と対話する。ドライバ１８の機
能を理解することと、本発明を理解することとは、密接
な関係があるわけではない。一例にすぎないが、ディス
ク１４ａおよび１４ｂとドライバ１８はいずれも、周知
のＳＣＳＩバスなどのバス１８ａによって接続すること
ができる。

【００１７】ディスク・マネージャ１６は、ｎ個の圧縮
単位のそれぞれに対応する複数の項目（項目_０〜項
目_ｎ）を有するディレクトリ１６ａを含むか、これにア
クセスすることができる。

【００１８】システム１０は、適当なデータ圧縮装置／
圧縮解除装置２０と関連のトラック・バッファ２２とを
さらに含む。トラック・バッファ２２は、データ圧縮装
置２０とドライバ１８を介して記憶システム１４に書き
込むか、ドライバ１８とデータ圧縮解除装置２０を介し
て記憶システム１４から読み取る未圧縮データを格納す
る。データ圧縮装置／圧縮解除装置２０にはラン・レン
グス・カウンタ２０ａが関連付けられている。このカウ
ンタの使い方については、後で詳述する。

【００１９】ここで説明する実施例では、ディスク・ト
ラック１５ｃ（たとえば、４８Ｋバイト）が１つの圧縮
単位に対応するものと想定している。しかし、本発明の
教示は異なるサイズを有する圧縮単位に適用可能である
ことに留意されたい。

【００２０】従来の読取り操作を実行する場合、トラッ
ク（圧縮単位）上の対象レコードの前にあるすべてのデ
ータを圧縮解除してから、対象レコードの圧縮解除が行
われる。このため、圧縮比が２：１であると想定する
と、（トラックの先頭に方向付けするための０．５回転
に続いて）対象レコードに達する前にデータを読み取る
ために平均０．２５回のディスク回転が必要である。こ
の０．２５回転で、ディスク１４ａまたは１４ｂが接続
され、データ転送資源が読取り操作専用になる。したが
って、小規模読取り操作用の圧縮指向ディスク・システ
ムの接続時間は、圧縮を使用しないシステムの同等の接
続時間より大幅に長くなる。しかも、圧縮指向ディスク
・システムでは小規模読取り操作の応答時間（主にシー
クおよび待ち時間によって決まる）が劣化する。

【００２１】トラック内のレコードが参照されたときに
ディスク・システムがそのトラックをバッファ２２（ま
たはキャッシュ１２ａ）に転送しなければならない場
合、圧縮指向ディスク・システムの合計接続時間が増加
しないことに留意されたい。しかし、小規模読取り操作
の場合はこのようなシステムの応答時間が劣化する。

【００２２】次に図２を参照すると、同図にはトラック
１５ｃとディレクトリ１６ａの好ましい論理構成が示さ
れている。ここでは、トラック１５ｃが複数のセクタに
区分されているものと想定する。一例として、各セクタ
の長さが５１２バイトであるとすると、４８Ｋバイトの
トラックは９６個のセクタを含むことになる。ただし、
図２のセクタは、トラック１５ｃに対して一定の比率で
描かれているわけではない。

【００２３】本発明の方法は、１つの単一トラック長圧
縮イメージに圧縮解除するのではなく、整数個の同サイ
ズ（４Ｋバイト）の圧縮基本単位１５ｅにすべての圧縮
単位を圧縮解除するように動作する。したがって、４８
Ｋバイトのトラック（圧縮単位）１５ｃの場合、４Ｋバ
イトの基本単位１５ｅが合計１２個存在する。

【００２４】本方法によれば、ディレクトリ１６ａ内の
各項目１７ａには、圧縮単位の第一の基本単位１５ｅを
指す絶対アドレスを格納するためのフィールド１７ｂが
１つだけ用意される。このため、追加のディレクトリ項
目は不要になり、前記の分割は圧縮単位数の増加に相当
しない。

【００２５】実施上の簡略化のため、各基本単位１５ｅ
が整数個の物理ディスク・セクタ（ブロック）に等しい
ことが好ましい。

【００２６】本発明の方法では、ディレクトリ１６ａと
各基本単位１５ｃの両方に追加の制御構造を提供する。
圧縮トラック内のレコードへの直接アクセスを可能にす
るために、各ディレクトリ項目１７ａには、追加のディ
レクトリ制御構造（フィールド１７ｃ）が追加されてい
る。このフィールド１７ｃは、基本単位１５ｅ内のアド
レスを指すポインタを格納する。以下、これらのポイン
タをセクタ・ポインタと呼ぶ。それぞれのセクタ・ポイ
ンタは、圧縮単位内の事前定義セクタが入っている基本
単位１５ｅを指す。圧縮単位は、Ｘ個の間隔１５ｄに分
割され、各ディレクトリ項目１７ａのフィールド１７ｃ
内のＸ−１個のセクタ・ポインタは、その圧縮単位の１
／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各部の先
頭をマークするセクタが入っているＸ−１個の基本単位
を指している。本発明の好ましい実施例では、１つの圧
縮単位が５個の間隔１５ｄに区分され、各ディレクトリ
項目のフィールド１７ｃ内の４個のセクタ・ポインタは
１／５、２／５、３／５、４／５の各間隔が始まる基本
単位１５ｅの初期セクタ・アドレス（ボリューム、シリ
ンダ、面、セクタ）を指している。図示の例では、フィ
ールド１７ｃに格納されているセクタ・ポインタが基本
単位２、４、７、９の初期セクタを指している。各セク
タ・ポインタは、基本単位の絶対アドレスを格納するの
ではなく、以前指し示されていた基本単位から現在指し
示されている基本単位までのオフセット（セクタ数）を
格納する。前述の通り、第一の基本単位１５ｅの絶対ア
ドレスは各ディレクトリ項目のフィールド１７ｂに格納
されている。

【００２７】圧縮単位を５個の間隔１５ｄに区分しても
本発明を実施する際に制限とはならず、使用する間隔の
数をそれより増減することも可能であることに留意され
たい。

【００２８】データ圧縮処理によって４８Ｋバイトのト
ラック１５ｃ内の５個の間隔１５ｄがいずれも大幅に伸
張されないと想定すると、各セクタ・ポインタとしては
２ビット（０〜３の範囲）で十分である。その結果、デ
ィレクトリ１６ａの各項目１７ａに１バイト（２ビット
×４個のセクタ・ポインタ）を追加するだけで、フィー
ルド１７ｃを収容することができる。２個（または３個
以上）のセクタ・ポインタが指し示すセクタが同一の基
本単位１５ｅに存在する場合、第二（またはそれ以降）
のポインタのポインタ値がゼロに設定される。

【００２９】トラック１５ｃ内の間隔１５ｄのいずれか
１つ（または複数）が大幅に伸張する場合は、本方法に
より達成される待ち時間の短縮がいくらか低下するが、
本方法の動作は損なわれない。

【００３０】各ディレクトリ項目１７ａに追加される単
一のフィールド１７ｃに加え、未圧縮トラック内の事前
定義位置に相当するディスク内の特定の位置からのデー
タ転送を可能にするため、ディスク・セクタ・ポインタ
１５ｆというデータ構造がディスクに追加される。この
操作は、対応する未圧縮位置が不明な箇所からディスク
がデータ転送を開始する場合でも達成される。

【００３１】より具体的には、圧縮単位内の事前定義セ
クタの位置を指すディスク・セクタ・ポインタ１５ｆ
が、各基本単位１５ｅの初期セクタに対応するディスク
・セクタに追加される。このディスク・セクタ・ポイン
タ１５ｆは、基本単位１５ｅの先頭から圧縮単位内の間
隔１５ｄの１つの先頭までの距離を格納する。図２に示
す例によれば、ディスク・セクタ・ポインタ１５ｆは、
基本単位１５ｅの先頭からトラックの１／５、２／５、
３／５、４／５のいずれかの間隔の先頭までの距離を格
納している。これらの間隔のうちの複数が同一の基本単
位１５ｅ内にある場合は、ディスク・セクタ・ポインタ
１５ｆが最初の間隔を指し示す。１／５、２／５、３／
５、４／５の間隔のいずれも基本単位内に位置していな
い場合は、ディスク・セクタ・ポインタ１５ｆの値は未
定義なので使用されない。ディスク・セクタ・ポインタ
１５ｆに格納されている距離は未圧縮単位数（すなわ
ち、未圧縮のバイト数）で示される。

【００３２】ディスク・セクタ・ポインタ１５ｆは、０
〜９６００の範囲の値を表すのに２バイト程度を要す
る。このため、各トラックごとに、合計１２バイト（圧
縮比が２：１であると想定する）がディスク・セクタ・
ポインタ１５ｆの格納専用になり、ディスクの総データ
量はディレクトリのサイズと同程度になる。しかし、デ
ィスク・メモリはディレクトリ・メモリに比べ、相当低
価格である。

【００３３】本発明の方法をサポートする追加のデータ
構造は、トラックがディスク記憶システム１４に書き込
まれるときに初期設定される。書き込まれるトラック
は、トラック・バッファ２２とデータ圧縮装置／圧縮解
除装置２０を介してディスクに送られる。装置２０はデ
ータを複数の基本単位１５ｅに圧縮する。対応するディ
レクトリ項目１７ａのフィールド１７ｃに入っているセ
クタ・ポインタの１つによって指し示されるセクタが圧
縮装置／圧縮解除装置２０を介して転送される場合、圧
縮装置／圧縮解除装置２０によって生成される基本単位
１５ｅを指し示すように対応するセクタ・ポインタが設
定される。

【００３４】新しい基本単位１５ｅが生成されると、デ
ィスク・セクタ・ポインタ１５ｆは、基本単位１５ｅに
送られる最初のバイトと次に指し示されるはずのセクタ
（すなわち、トラック１５ｃの１／５、２／５、３／
５、４／５という所定の間隔）との間の距離（未圧縮単
位数）に必ず設定される。

【００３５】データ処理装置１２によって生成されるレ
コード読取り操作コマンドでは、特定のセクタ（レコー
ドの先頭）から別のセクタ（レコードの末尾）までのデ
ータをディスク記憶システム１４からトラック・バッフ
ァ２２に（圧縮解除を使用して）転送する必要がある。
以下、読み取るレコードの初期セクタを対象セクタ（Ｓ
ＯＩ）と呼ぶ。

【００３６】次に図３を参照して説明すると、レコード
読取り操作では以下のステップが実行される。

【００３７】Ａ．データ処理装置１２によってレコード
読取り操作が開始される。

【００３８】Ｂ．ＳＯＩに基づいて、ディスク・マネー
ジャ１６がディレクトリ１６ａを探索し、ＳＯＩが入っ
ているトラックに対応するディレクトリ項目１７ａがデ
ィレクトリ１６ａから取り出される。

【００３９】Ｃ．セクタ・ポインタの１つによって指し
示され、ＳＯＩの前にある最大未圧縮セクタが決定され
る。

【００４０】Ｄ．前記のステップで決定された未圧縮セ
クタを指すセクタ・ポインタ（フィールド１７ｃ）によ
って指し示されている基本単位１５ｅのアドレスがディ
レクトリ項目１７ａから取り出される。図２を参照して
例を挙げると、ＳＯＩがｊ＋１であれば、基本単位９の
アドレス（初期セクタ）が取り出される。

【００４１】Ｅ．前記のステップで取り出された基本単
位９の初期セクタにシークするように、ディスクに指示
が送られる。ディスクが基本単位９に達すると、圧縮装
置／圧縮解除装置２０が基本単位９の読取りを開始して
これを圧縮解除し、ディスク・セクタ・ポインタ１５ｆ
に格納されている値が求められる。ただし、ディスク・
セクタ・ポインタ１５ｆによって示されるバイト数が圧
縮解除されるまでは、圧縮解除されたデータはトラック
・バッファ２２に送られず、単に破棄されるだけであ
る。

【００４２】Ｆ．ディスク・セクタ・ポインタ１５ｆに
よって示されるバイト数が圧縮解除されると、基本単位
１５ｅ内に残っているデータのうち、間隔４の開始部分
に相当するデータが圧縮解除され、トラック・バッファ
２２に送られる。

【００４３】Ｇ．ＳＯＩがトラック・バッファ２２に格
納されると、レコード読取り操作は、トラック・バッフ
ァ２２に格納されている圧縮解除データの処理を続行す
ることができる。

【００４４】Ｈ．残りの基本単位１５ｅのうち、レコー
ド読取り操作が要求するレコードの一部が入っている基
本単位１５ｅがあれば、それが圧縮解除され、トラック
・バッファ２２に転送される。

【００４５】任意のトラックの１つのレコードが参照さ
れたときにそのトラック全体をトラック・バッファ２２
に転送する必要があるタイプのディスク・システム１４
の場合は、以下のステップが実行される。

【００４６】Ｉ．残りの基本単位のうち、ＳＯＩが入っ
ている基本単位以降のもので、ステップＨで転送されて
いないものが、トラック・バッファ２２に転送される。
図２では、基本単位１０および１１がこれに該当する。

【００４７】Ｊ．ＳＯＩが入っているトラック１５ｃに
属す最後の基本単位１５ｅ（基本単位１１）の転送後、
ＳＯＩが入っているトラック１５ｃに属す最初の基本単
位（基本単位０）にシークするようにディスクに指示が
送られる。

【００４８】Ｋ．ディスクが基本単位０に達すると、基
本単位１からＳＯＩが入っている基本単位９までのすべ
ての基本単位が圧縮解除され、トラック・バッファ２２
に転送される。

【００４９】Ｌ．トラック・バッファ２２が受け取った
圧縮解除バイト数が基本単位９のディスク・セクタ・ポ
インタ１５ｆによって示されるバイト数と等しくなるま
で、ＳＯＩを含む間隔の先頭が入っている基本単位９の
初期セクタからトラック・バッファ２２にデータが転送
される。このようにして、トラック全体がトラック・バ
ッファ２２に格納される。

【００５０】Ｍ．レコード読取り操作が終了する。

【００５１】前記の解決策の代わりに、小規模レコード
読取り操作の接続時間と応答時間の両方を同じ程度まで
短縮し、追加のディレクトリ項目を必要とするような解
決策を使用すると、ディレクトリ１６ａの６倍程度（圧
縮比が２：１であると想定する）の大きいディレクトリ
が必要になることに留意されたい。ディレクトリ１６ａ
の項目サイズが２バイトもあると想定すると、このよう
な代替解決策では、本発明の方法が必要とするディレク
トリ・サイズより１桁大きくなることを意味する。

【００５２】前述のレコード読取り操作の結果、データ
ベース操作で一般に発生するように、データ処理装置１
２がレコードの内容を改訂したり更新する場合がある。
しかし、ディスク記憶システム１４に書き戻す前に更新
済みレコードを圧縮すると、必要な記憶空間が元のレコ
ードより大きくなる可能性がある。このため、順次書き
込まれたレコードでは、改訂されたレコードを別の位置
に格納しなければならないという問題が発生し、それに
より、その後行われる順次レコードの読取り時にディス
クのパフォーマンスに悪影響を及ぼす。

【００５３】ディスク記憶システム１４の記憶域にまず
データベース・レコードが割り振られると、今後のレコ
ードの拡大に対応するためにそのレコードに未使用空間
が提供される。たとえば、レコードの未使用部分を１６
進のゼロで埋めてもよい。

【００５４】レコードの最初の更新を除けば、通常、圧
縮レコードのサイズの変動量は少ない。このため、本発
明の他の態様によれば、最初の更新のための予想圧縮サ
イズを上回る空間を元のレコードに割り振ると、更新済
みレコードをディスクの別の領域に再書込みせずに、レ
コードを所定の位置で更新できる確率が高くなる。

【００５５】この予測を行うには、最初に作成したレコ
ード内の「ブランク」文字で埋められる未使用空間を考
慮する必要がある。つまり、００_１６という埋込み文字
の圧縮比（たとえば、９６：１）は、「通常」データの
場合（たとえば、３．６：１）よりかなり高いのが一般
的である。このため、前述のランレングス・カウンタ２
０ａが使用されるのである。

【００５６】ランレングス・カウンタ２０ａは、圧縮単
位の圧縮完了時にその圧縮単位内の繰返しバイトの最長
ランの値（バイト数）を格納する２４ビットのカウンタ
である。たとえば、"ｘｘｘｙａａａａ"という文字列に
は以下のランが含まれている。ｘｘｘランレングス＝３ｙランレングス＝１ａａａａランレングス＝４

【００５７】文字列"ｘｘｘｙａａａａ"の圧縮後、ラン
レングス・カウンタ２０ａには、文字列"ａａａａ"に対
応する４という値が入っているはずである。このランレ
ングス・カウンタ２０ａの内容は、入出力操作によって
データ処理装置１２から読み取ることができる。また、
ランレングス・カウンタ２０ａの内容は、圧縮操作の完
了時にホスト装置（たとえば、データ処理装置１２）に
送られる圧縮終了（ＥＯＣ）信号に自動的に付加するこ
とができる。

【００５８】新しいレコードを含む圧縮単位の圧縮終了
時に、ランレングス・カウンタ２０ａの値は、そのレコ
ードに含まれる埋込み文字の数を反映している。これ
は、埋込み文字が同一文字の最長ランに含まれていると
いう想定による。このため、ランレングス・カウンタ２
０ａに格納されている値を使用して、そのレコードの実
際のデータ圧縮比を圧縮後のサイズを反映した値に調整
する。この圧縮後のサイズは、レコードが更新され、埋
込み文字が実際のデータで上書きされたときにレコード
が想定する。たとえば、レコードの２０％が埋込み文字
で構成されていることがランレングス・カウンタ２０ａ
から判定された場合、ならびに埋込み文字が９６：１な
どの圧縮比で圧縮されていることが分かっている場合に
は、２０％の埋込み文字部分が３．６：１などの圧縮比
で圧縮される実際のデータで置き換えられるという想定
に基づいて、予想圧縮比が調整される。レコードの調整
後、圧縮済み（調整済み）レコードのためにとっておく
必要があるディスク空間の第一の量が求められる。次
に、最初の更新が行われた後で所定の位置でレコードを
更新し、論理レコードの追加を行えるようにするため
に、追加の量のディスク空間（たとえば、５％）が追加
される。

【００５９】"The Design and Implementation of a Lo
g-Structured File System" という論文（ACM Transact
ions on Computer Systems, Vol.10, No.1, 1992年2月,
pp.26-52）において M. Rosenblum および John K. Ou
sterhout が記載しているタイプのログ構造ファイル・
システムとしてシステム１０を操作することが本発明の
範囲内であることに留意されたい。

【００６０】本発明の好ましい実施例に関連して具体的
に本発明を示し説明してきたが、当業者には、本発明の
範囲および精神を逸脱せずに形式および細部の変更が可
能であることが理解されるだろう。

【００６１】

【発明の効果】本発明の実施により、（１）より小規模
の圧縮単位を使用する場合に必要なものと比較して、ご
く少量の情報をディレクトリに追加するだけで、レコー
ド読取り操作時の接続時間を短縮する方法を提供し、
（２）制御情報の追加量を大幅に増加せずに、圧縮ディ
スク・トラックからの小規模読取り操作の実行時に発生
する接続時間と応答時間をともに短縮することができ
る。

【図面の簡単な説明】

【図１】本発明により構築および操作されるデータ処理
システムを示すブロック図である。

【図２】本発明による圧縮単位の区分を示す図である。

【図３】本発明の好ましい方法を示す論理流れ図であ
る。

【符号の説明】

１０データ処理システム１２データ処理装置１２ａキャッシュ１２ｂデータ経路１４ディスク・データ記憶システム１４ａ第一のディスク装置１４ｂ第二のディスク装置１５ａ第一のデータ記憶面１５ｂ第二のデータ記憶面１５ｃトラック１６ディスク・マネージャ１６ａディレクトリ１８ディスク・デバイス・ドライバ１８ａバス２０データ圧縮装置／圧縮解除装置２０ａランレングス・カウンタ２２トラック・バッファ

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジョー＝ミン・チェンアメリカ合衆国95111 カリフォルニア州サンノゼライラック・レーン 4935 (72)発明者オデド・コーンイスラエル32922 ハイファグート・レヴィン 20／４ (72)発明者ジェームズ・ダブリュー・エルドリッジアメリカ合衆国カリフォルニア州サンノゼスイス・ドライブ 559 (72)発明者ヨラム・ノヴィクイスラエル32922 ハイファゴット・レヴィン・ストリート 14 (72)発明者ノーマン・ケイ・オーウチアメリカ合衆国95120 カリフォルニア州サンノゼビュー・クレスト・コート 20248 (72)発明者ダニト・セゲヴイスラエル34751 ハイファワトソン・ストリート 12 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 3/06

Claims

(57)【特許請求の範囲】

【請求項１】少なくとも１個のディスクで構成されるデ
ータ記憶システムを操作する方法において、データ圧縮単位をｎ個（但し、ｎは２以上の正の整数）
の基本圧縮単位に区分するステップであって、各データ
圧縮単位が複数のディスク・セクタで構成され、ｎ個の
基本圧縮単位のそれぞれが異なる初期セクタから始まる
ステップと、データ圧縮単位をＸ個（但し、Ｘはｎ未満の正の整数）
の間隔に区分するステップであって、Ｘ個の間隔のそれ
ぞれが異なる初期セクタから始まり、しかもｎ個の基本
圧縮単位の１つの範囲内にあるステップと、１／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各間隔
が始まるｎ個の基本圧縮単位の１つの初期セクタをそれ
ぞれ指す複数の第一のポインタを前記少なくとも１個の
ディスクの外部に格納する第一の格納ステップと、１／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各間隔
が始まるｎ個の基本圧縮単位のそれぞれの各初期セクタ
内に、その基本圧縮単位内で始まる間隔の初期セクタを
指す第二のポインタを格納する第二の格納ステップと、Ｘ個の間隔の１つの範囲内に位置するセクタの１つから
始まる圧縮データ単位を読み取るためのディスク読取り
操作に応答して、第一のポインタの１つと第二のポイン
タの１つにより、当該圧縮データ単位の開始セクタにア
クセスするアクセス・ステップとを含む、前記方法。
【請求項２】データ圧縮単位が前記少なくとも１個のデ
ィスクの１つのトラックに対応することを特徴とする、
請求項１に記載の方法。
【請求項３】第一のポインタのそれぞれが、以前の第一
のポインタからのオフセット（セクタ数）として格納さ
れることを特徴とする、請求項１に記載の方法。
【請求項４】第二のポインタのそれぞれが、１つの間隔
が始まる基本圧縮単位の初期セクタの先頭から基本圧縮
単位内で始まる間隔の初期セクタまでのバイト数として
格納されることを特徴とする、請求項１に記載の方法。
【請求項５】前記第一の格納ステップが、圧縮単位の初
期セクタを指す第三のポインタを前記少なくとも１個の
ディスクの外部に格納することを特徴とする、請求項１
に記載の方法。
【請求項６】圧縮データ単位の開始セクタが対象セクタ
（ＳＯＩ）であり、前記アクセス・ステップが、ＳＯＩを含む間隔が始まる目標基本圧縮単位の初期セク
タを決定するために第一のポインタを使用するステップ
と、目標基本圧縮単位の初期セクタで前記少なくとも１個の
ディスクから圧縮データの読取りを開始するステップ
と、第二のポインタの値を求めるために読み取ったデータを
圧縮解除するステップと、ＳＯＩを含む間隔の初期セクタに達するまで圧縮解除デ
ータを破棄するステップとを含むことを特徴とする、請
求項１に記載の方法。
【請求項７】ＳＯＩと、圧縮データ単位を構成する他の
セクタとを読み取って圧縮解除するステップをさらに含
むことを特徴とする、請求項６に記載の方法。
【請求項８】ＳＯＩから圧縮単位の末尾までのすべての
セクタを読み取って圧縮解除するステップと、圧縮単位の初期セクタにシークするステップと、初期セクタからＳＯＩまでのすべてのセクタを読み取っ
て圧縮解除するステップとをさらに含むことを特徴とす
る、請求項７に記載の方法。
【請求項９】圧縮単位が複数のセクタで構成される少な
くとも１つの圧縮レコードを含み、所定のデータ圧縮比
に基づいてセクタの必要数を予測することで圧縮レコー
ドを格納するために複数のセクタを割り振るステップを
含み、この割振りステップが、レコードの実際の圧縮比
を求め、そのレコード内の同一文字の最長ランの値を求
め、同一文字の最長ランの値に基づいて実際の圧縮比を
調整するステップを含むことを特徴とする、請求項１に
記載の方法。
【請求項１０】前記割振りステップが、前記少なくとも
１個のディスクの別の領域に圧縮レコードを再書込みせ
ずに圧縮レコードを後で更新できるようにするため、予
測数に少なくとも１つの追加セクタを追加するステップ
を含むことを特徴とする、請求項９に記載の方法。
【請求項１１】少なくとも１個のディスクを有するデー
タ記憶システムにおいて、データ圧縮単位をｎ個（但し、ｎは２以上の正の整数）
の基本圧縮単位に区分するためのディスク・マネージャ
であって、各データ圧縮単位が複数のディスク・セクタ
で構成され、ｎ個の基本圧縮単位のそれぞれが異なる初
期セクタから始まり、前記ディスク・マネージャがデー
タ圧縮単位をＸ個（但し、Ｘはｎ未満の正の整数）の間
隔にさらに区分し、Ｘ個の間隔のそれぞれが異なる初期
セクタから始まり、しかもｎ個の基本圧縮単位の１つの
範囲内にあるディスク・マネージャと、１／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各間隔
が始まるｎ個の基本圧縮単位の１つの初期セクタをそれ
ぞれ指す複数の第一のポインタを前記少なくとも１個の
ディスクの外部に格納するための第一の格納手段と、１／Ｘ、２／Ｘ、・・・、（Ｘ−１）／Ｘという各間隔
が始まるｎ個の基本圧縮単位のそれぞれの各初期セクタ
内に、その基本圧縮単位内で始まる間隔の初期セクタを
指す第二のポインタを格納するための第二の格納手段と
を含み、前記ディスク・マネージャが、Ｘ個の間隔の１つの範囲
内に位置するセクタの１つから始まる圧縮データ単位を
読み取るためのディスク読取り操作に応答し、第一のポ
インタの１つと第二のポインタの１つにより、当該圧縮
データ単位の開始セクタにアクセスするためのアクセス
手段をさらに含む、前記データ記憶システム。
【請求項１２】データ圧縮単位が前記少なくとも１個の
ディスクの１つのトラックに対応することを特徴とす
る、請求項１１に記載のデータ記憶システム。
【請求項１３】第一のポインタのそれぞれが、以前の第
一のポインタからのオフセット（セクタ数）として格納
されることを特徴とする、請求項１１に記載のデータ記
憶システム。
【請求項１４】第二のポインタのそれぞれが、１つの間
隔が始まる基本圧縮単位の初期セクタの先頭から基本圧
縮単位内で始まる間隔の初期セクタまでのバイト数とし
て格納されることを特徴とする、請求項１１に記載のデ
ータ記憶システム。
【請求項１５】前記第一の格納手段が、圧縮単位の初期
セクタを指す第三のポインタを前記少なくとも１個のデ
ィスクの外部に格納することを特徴とする、請求項１１
に記載のデータ記憶システム。
【請求項１６】圧縮データ単位の開始セクタが対象セク
タ（ＳＯＩ）であり、前記アクセス手段が、ＳＯＩを含
む間隔が始まる目標基本圧縮単位の初期セクタを決定す
るために第一のポインタを使用して、目標基本圧縮単位
の初期セクタで前記少なくとも１個のディスクから圧縮
データの読取りを開始し、しかも第二のポインタの値を
求めるために読み取ったデータを圧縮解除して、ＳＯＩ
を含む間隔の初期セクタに達するまで圧縮解除データを
破棄し、ＳＯＩと、圧縮データ単位を構成する他のセク
タとを読み取って圧縮解除するための手段をさらに含む
ことを特徴とする、請求項１１に記載のデータ記憶シス
テム。
【請求項１７】前記アクセス手段が、さらにＳＯＩから
圧縮単位の末尾までのすべてのセクタを読み取って圧縮
解除し、しかも圧縮単位の初期セクタにシークし、初期
セクタからＳＯＩまでのすべてのセクタを読み取って圧
縮解除するための手段を含むことを特徴とする、請求項
１６に記載のデータ記憶システム。
【請求項１８】圧縮単位が複数のセクタで構成される少
なくとも１つの圧縮レコードを含み、前記ディスク・マ
ネージャが、所定のデータ圧縮比に基づいてセクタの必
要数を予測することで圧縮レコードを格納するために複
数のセクタを割り振るための割振り手段をさらに含み、
レコードの実際の圧縮比を求めるための手段と、そのレ
コード内の同一文字の最長ランの値を求めるための手段
と、同一文字の最長ランの値に基づいて実際の圧縮比を
調整するための手段とを含むことを特徴とする、請求項
１１に記載のデータ記憶システム。
【請求項１９】前記割振り手段が、前記少なくとも１個
のディスクの別の領域に圧縮レコードを再書込みせずに
圧縮レコードを後で更新できるようにするため、予測数
に少なくとも１つの追加セクタを追加するための手段を
さらに含むことを特徴とする、請求項１８に記載のデー
タ記憶システム。