JPH08234921A - アドレス・スペースを管理するための方法及び記憶サブシステム - Google Patents

アドレス・スペースを管理するための方法及び記憶サブシステム

Info

Publication number
JPH08234921A
JPH08234921A JP7301784A JP30178495A JPH08234921A JP H08234921 A JPH08234921 A JP H08234921A JP 7301784 A JP7301784 A JP 7301784A JP 30178495 A JP30178495 A JP 30178495A JP H08234921 A JPH08234921 A JP H08234921A
Authority
JP
Japan
Prior art keywords
segment
segments
addressable
size
linear
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP7301784A
Other languages
English (en)
Inventor
Bruce Brody Robert
ロバート・ブルース・ブロディ
Min Chen Jwo
ジョー−ミン・チェン
John Garriby Lawrence
ローレンス・ジョン・ギャリバイ
Moosdes Menon Yaishankar
ヤイシャンカー・ムースデス・メノン
Iu Ngu Chan
チャン・イウ・ング
T Nyugen Trung
トラム・ティ・マイ・ニュイェン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH08234921A publication Critical patent/JPH08234921A/ja
Pending legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/0604—Improving or facilitating administration, e.g. storage management
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/0644—Management of space entities, e.g. partitions, extents, pools
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0683—Plurality of storage devices
    • G06F3/0689—Disk arrays, e.g. RAID, JBOD
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/40—Specific encoding of data in memory or cache
    • G06F2212/401—Compressed data

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Memory System (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

(57)【要約】 【課題】参照の局所性を維持するように一定のサイズの
記憶装置を管理する。 【解決手段】記憶装置は、圧縮記号ストリングに対する
線形アドレス可能なスペース及び各圧縮記号ストリング
のオーバフロー部分に対するリンク・リスト・アドレス
可能なスペースに区分けされ、オーバフローに対するト
ークンが線形アドレスに組み込まれる。線形スペース
は、現在使用している範囲内になるようその使用可能な
オーバフローの量を維持するために周期的に１つの方向
に再調整される。圧縮統計における変化の結果、内部の
断片化を最小にするために再調整することを必要とする
オーバフロー使用の変化が生じる。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、アドレス可能メモ
リ又は記憶サブシステムにおける圧縮記号ストリングの
管理に関するものであり、更に詳しく云えば、同じ圧縮
比を受けたストリング又は異なる圧縮比を受けたストリ
ングに対して前記メモリ又は記憶サブシステムにおける
参照の局所性を維持するためのアクセス方法及び手段に
関するものである。
【０００２】
【従来の技術】この項では、記憶サブシステムに適用さ
れるモデルを説明する。これは、直接アクセス記憶装置
（ＤＡＳＤ）のアレーに適用されたログ構造ファイル／
ログ構造アレー（ＬＳＦ／ＬＳＡ）を含む。問題は、同
じソースの或いは異質のソースの圧縮記号ストリングか
ら得られた圧縮ファイル、レコード、又はページ編成の
記号ストリングの参照の局所性における効果に影響す
る。
【０００３】Ａ．記憶装置及び記憶モデル 記憶サブシステムは、変更可能な記憶媒体、アクセス機
構、及びアドレシング・プロトコルを含む。そのような
サブシステムはホストＣＰＵに接続される。ホストＣＰ
Ｕにおけるオペレーティング・システム（ＯＳ）は、Ｃ
ＰＵが実行する１つ又は複数個のアプリケーションから
のアクセス・コマンドに応答する。アクセス・コマンド
は、媒体上のアドレスを定義する１つ又は複数個のアー
ギュメントを含む。ＯＳは、アドレシング・プロトコル
及びアクセス・コマンド・アーギュメントの関数とし
て、記憶媒体に関して機械的に又は電気的にそれ自身を
アクセス機構に位置付けさせる。しかる後、それは、記
憶媒体に或いは記憶媒体からそのアドレスされたロケー
ションにおける記号ストリングを転送する。
【０００４】階層的なシステムでは、参照システムより
も下位のサブシステムの予想される作用として、１つの
モデルが定義可能である。記憶装置モデルは、記憶サブ
システムに適用される時、ＣＰＵが優越していることか
らも明らかなように単なる記憶装置である。如何なる記
憶装置モデルも、論理的アドレスを交換可能媒体におけ
るロケーションに関連付けるための手段によって抽象的
空間又は論理的空間におけるアドレスをアクセス及びレ
イ・アウトする態様を定義するプロトコルを含んでい
る。しかし、そのモデルは、基礎となる物理的記憶装置
に対する如何なる必然的な類似性も持つ必要はない。こ
れは、論理的空間の内容が連続的アドレスから不連続の
実アドレス空間に１対１でマップ可能である仮想及び実
アドレス２分法によって示される。ＯＳ及び記憶サブシ
ステムは必要な変換を行う。又、論理的空間又は仮想空
間を構成するアドレスの数は、通常、実アドレス空間を
構成するアドレスの数よりも大きい。本願では、実アド
レスと絶対アドレスとの区別は全く行われない。
【０００５】Ｂ．ログ構造記憶装置モデル、キャッシュ
付きＤＡＳＤ記憶装置及びＤＡＳＤアレー 従来技術では、プロセッサ速度の増加は外部記憶装置に
おけるＩ／Ｏ要求を増加させた。ランダムな読取りオペ
レーションにおける補助記憶装置への反復的な参照はデ
ータを大型の中間的なキャッシュにステージングするこ
とによって減少可能であるという技術的対応策がとられ
ていた。又、すべての書込み更新パスは、それら更新を
バッファすること、そして直接アクセス記憶装置（ＤＡ
ＳＤ）上にそれらを非同期的にバッチ・レコードするこ
とによって改善可能であることがわかった。
【０００６】ＤＡＳＤ外部記憶装置への書込みパスは、
周期的にガーベジ・コレクト（ｇａｂａｇｅ ｃｏｌｌ
ｅｃｔｅｄ）される断片化された記憶内容を有する半無
限のテープとしてそれが管理される場合には最適化可能
であった。更新されたレコードは、種々のアフィニティ
（ａｆｆｉｎｉｔｙ）を保ちながらログ・ファイルの終
わりに圧縮形式で書き込まれたであろう。そのようなフ
ァイル管理は「ログ構造のファイル」と呼ばれた。
【０００７】Ｎ個のＤＡＳＤのアレーが同期的にアクセ
スされ、データがそこでストライプ化される場合、デー
タ速度はＮ＊ＤＡＳＤ速度に増加し、論理的トラック
は、ＤＡＳＤの物理的トラック等のサイズのＮ倍になる
ことがわかった。その関連では、ログ構造ファイルとし
て管理されるＤＡＳＤアレーは「ログ構造のアレー（Ｌ
ＳＡ）」と呼ばれる。
【０００８】Ｃ．ログ構造の記憶モデル及び圧縮 ＵＣバークレイＳＰＲＩＴＥログ構造ファイル（ＬＳ
Ｆ）は、データを見つけるための順次走査を最小にする
に十分なディレクトリでもって、シャドー書きされた準
無限テープとして記憶装置をモデル化することによって
書込み効率及び回復が最大にされたＵＮＩＸ記憶装置の
ホスト編成である。ＬＳＦでは、すべてのライブ・ファ
イル及び更新済みファイルは、ガーベジ・コレクション
後のログの終了時に書き直される。これは、複写及び短
縮と呼ばれる。
【０００９】ログ構造ファイル編成は、修正されたデー
タを書く効率を向上させる。しかし、誘起される不利益
は、（１）シーク・アフィニティを失うこと、（２）情
報の論理的ブロックの動的に変化する物理的ロケーショ
ンを追跡するディレクトリ構造を維持しなければならな
いこと、（３）修正されなかったブロックを同時に定期
的にガベージ・コレクトし、それらを新しいロケーショ
ンに移動させることを含む。後者は、ログからの大量の
修正されたブロックを書くための連続したクリーン・ス
ペースを残すために必要とされる。
【００１０】Ｄ．シーク・アフィニティを持った修正Ｌ
ＳＡ 任意の所与のワークロードを実行している間の平均的シ
ーク時間を、無作為なワークロードをアクセスする場合
の平均的シーク時間で割った比率が重要な意味を持つ。
シーク・アフィニティが小さければ小さいほど、パフォ
ーマンスは良い。
【００１１】この未決出願では、キャッシュからデステ
ージされた或いはＬＳＡから収集された書込み修正読取
りアクティブ・トラック及びクリーン読取りアクティブ
・トラックをすべて収集すること及びそれらを読取りア
クティブ・トラックの連続セグメントの領域へのセグメ
ントとしてＬＳＡに書き直すことによって、小さい値の
シーク・アフィニティを得ている。又、キャッシュから
デステージされた或いはＬＳＡから収集された書込み修
正読取りインアクティブ・トラック及びクリーン読取り
インアクティブ・トラックがすべて収集され、読取りア
クティブ・トラックの連続セグメントの領域へのセグメ
ントとしてＬＳＡに書き直される。ガーベジ・コレクシ
ョンは、１つの領域内の検出された自由空間が閾値以下
になる時に開始され、収集されたセグメントが第２閾値
を超えるまで継続する。
【００１２】Ｅ．ファジー・ログ構造ＤＡＳＤアレー 事前割り振りされた記憶装置をオーバフローした圧縮更
新トラックだけがログ構造ファイルとして書き出される
（シャドウ書込み）書込更新のための方法がある。これ
は、事前割り振りされた記憶装置におけるレコードに対
する参照の局所性を維持し、複雑さを回避するであろ
う。このプロトコルは、トラックが更新される場合、非
圧縮トラック＋圧縮トラック拡張のための５％パッドが
占めるトラック・スペースの少なくとも３０％を留保す
るためのものであった。圧縮アルゴリズム及び圧縮を受
けるストリングのゼロ桁統計が少なくとも３／１の比を
サポートするということがその仮定である。圧縮比が３
／１よりも小さい場合、元の長さのセグメント・サイズ
の３５％を超えるすべてのストリングがＬＳＦ／ＬＳＡ
ファイル等として第１の利用可能スペースに書き出され
るため、かなりの断片化が生じる。
【００１３】Ｆ．オペレーティング・システム・レベル
圧縮記憶装置 マイクロソフト社の「ＤｏｕｂｌｅＳｐａｃｅ」及びＳ
ＴＡＣエレクトロニクス社の「ＳＴＡＣＫＥＲ」のよう
な幾つかの商業的な製品は、基本ディスク・ベースの記
憶装置によって圧縮データ及びアクセスを提供する。こ
れらの製品は、一定のディスクが非圧縮領域又はボリュ
ームと、１つ又は複数個の圧縮領域又はボリュームとに
区分けされる必要がある。非圧縮領域は、幾つかのシス
テム・ファイル及び単一のファイルとしての圧縮ボリュ
ームを記憶する。圧縮データへのアクセスは、圧縮ボリ
ュームがそれら圧縮ボリュームに関連した圧縮ディレク
トリのみを通して搭載され又は導入されることを必要と
する。従って、圧縮ファイルは、圧縮ボリューム及びそ
れのディレクトリを最初に搭載することなくしては透明
にはアクセス可能でない。
【００１４】
【発明が解決しようとする課題】本発明の目的は、アド
レス可能な記憶スペースにおける可変長の圧縮記号スト
リングを、それらストリングが一定の圧縮比に従ってい
る場合に参照の局所性を維持しながら、透明にアクセス
するための方法及び手段を提供することにある。
【００１５】本発明の関連の目的は、それらストリング
が種々の圧縮比に従ったものを含む場合の方法及び手段
を提供することにある。
【００１６】本発明のもう１つの目的は、可変長の圧縮
記号ストリングを１対１（ＯＮＥ−ＴＯ−ＯＮＥ）及び
オンツー（ＯＮＴＯ）の両方で固定（一定）サイズの論
理的及び物理的アドレス・スペースにマップする方法及
び手段を提供することにあり、その場合、書込み可能な
記憶単位はＤＡＳＤトラック、固定長ブロック、ページ
等から成るセットから選択される。
【００１７】本発明のもう１つの目的は、高レベルのア
クセス方法及び手段に対して透明な方法及び手段を提供
することにある。
【００１８】第１の例では、上記の諸目的は、記号スト
リングが共通の所定圧縮比ｒに従っており且つ一定のア
ドレス可能な記憶スペースＳに書き込まれるという方法
及び手段によって達せられる。そのスペースＳは、Ｎ個
の等しいサイズのセグメントから成る線形アドレス範囲
及び名目的にはＮ／２個のセグメントから成るオーバフ
ロー範囲に区分けされる。その圧縮比ｒは、ガウス又は
ラプラス記号の全体的な確率分布の２シグマ又はそれ以
下の境界で生じる圧縮比である。その分布は部分的な順
序範囲の圧縮比に重畳される。各線形セグメントの初期
サイズは、平均的な非圧縮ＤＡＳＤトラック、固定長ブ
ロック、又はページ・サイズを比ｒで除したものとして
決定される。その比ｒは、任意のトラック、固定長ブロ
ック、ページ等を形成する記号ストリングの非圧縮長対
圧縮長の比であることに留意して欲しい。
【００１９】
【課題を解決するための手段】この方法では、線形アド
レス・セグメントのサイズを超えた圧縮記号ストリング
のすべての部分が、線形セグメント又は１次セグメント
に組み込まれたリンク又はポインタでもって対応のオー
バフロー・セグメントに過剰分を書き込まれる。オーバ
フロー範囲が飽和してしまい、線形範囲又は１次範囲が
飽和してない場合、線形アドレス範囲を減少させること
によって追加のオーバフローが得られる。同様に、線形
にアドレス可能な範囲が飽和してしまい、オーバフロー
範囲が疎らに占められる場合、オーバフロー領域のサイ
ズを減少させることによって、追加の線形にアドレス可
能なスペースが再生される。
【００２０】この固定サイズ・アドレス範囲全体を動的
に管理するためには、オーバフローが終了してしまった
か或いはそれの現サイズの百分率として十分に利用され
なかったかどうかの関数として周期的に又は便宜的に書
き直される。例えば、オーバフロー領域の５％以上が書
かれてしまった場合、線形アドレス可能な記憶装置にお
けるセグメントのサイズは小さすぎるものと考えられ
る。Ｎ個のアドレス及び増加した線形セグメント・サイ
ズに対して追加のスペースがオーバフロー領域から要求
されるであろう。オーバフローのうちの１％又は２％だ
けが使用される場合、線形アドレス可能な記憶装置のセ
グメント・サイズは減少し、オーバフローに対して追加
のアドレスが加えられるか或いは領域が要求されるであ
ろう。
【００２１】換言すれば、本発明の方法及び手段は、マ
ルコフ生成の記号ストリング「ＯＮＥ−ＴＯ−ＯＮＥ」
及び「ＯＮＴＯ」を対応の線形アドレス・スペースに圧
縮する。何れかのストリングのうちのすべての超過部分
が、すべてのホストＣＰＵベースの記憶マネージャにと
って透明な対応のリンクのオーバフロー・セグメントに
書き込まれる。オーバフロー・スペースは、一定の和を
維持するように線形スペースにより調節可能に使用され
る。線形アドレス範囲の相対的サイズ及びそれに含まれ
るセグメントは、ソース記号の確率（順序統計量）が時
間経過と共に変化する時に変化する。これは、圧縮スト
リングを、大きい又は小さいサイズの線形アドレス・セ
グメントに周期的に又は便宜的に書き直すことによって
実施される。そのサイズ決めは、現在利用可能なオーバ
フロー・アドレスの所定のパーセンテージ範囲（即ち、
１％乃至５％）になるようオーバフロー・アドレスの数
を維持するような方向である。これは、すべてのスピル
領域又はオーバフロー領域に対するポインタ・オーバ
（チェーン）によって同所更新（ｕｐｄａｔｅ−ｉｎ−
ｐｌａｓｅ）を可能にする。
【００２２】この方法の変形は、線形アドレス・スペー
スがそこにレコードされたストリングの圧縮比の関数と
して予約される場合に生じる。従って、本発明による固
定サイズ・スペースＳは、連続したセグメントのバンド
から形成された線形アドレス範囲又は１次領域及びオー
バフロー領域を含むことも可能である。バンドそのもの
は、固定サイズ・スペース内に種々に位置指定可能であ
る。同じ圧縮比を受けたストリングを記憶するために、
バンドが予約されるであろう。従って、２／１、１／
１、３／１、及び４／１の圧縮比を受けたストリングが
受信される場合、「４つのバンド＋オーバフロー」が予
約されるであろう。動作的には、前述のように、１つ又
は複数個のバンドがオーバフロー範囲と共に調節可能に
変化可能である。
【００２３】有利なことには、そのような方法及び手段
はセルフ・スケーリングであり、参照の局所性を維持す
る。ログ構造ファイルを「線形アドレシング＋オーバフ
ロー範囲」に書き直すようなバックグランド処理におい
てファイルをゆっくりと改変するために、バンディング
が使用可能である。ＤＡＳＤ記憶サブシステム・イメー
ジ全体をパックし直すことはそれらバンドの特異な扱い
を可能にする。例えば、時間の３／１圧縮９５％を受け
た完全なファイルは、オーバフローと線形アドレス・セ
グメントとの間の関係を、時間の２／１圧縮７５％を受
けた新たにフォーマットされたファイルの許容度とは相
異した許容度内で調整される。完全なファイルは、通常
は、読取りアクセスを受け、更新を頻繁には受けないこ
とを想起して欲しい。
【００２４】
【発明の実施の形態】本発明は、ＤＡＳＤ記憶サブシス
テムにおける幾つかのレベル又は階級のうちのどれか１
つにおいて、即ち、サブシステム制御装置レベル又は記
憶装置レベルにおいて実施可能である。次の数節におい
て、サブシステム及び装置環境の簡単な説明を行うこと
にする。
【００２５】図１を参照すると、ホスト・プロセッサ１
及び外部記憶装置を含むシステムが示される。後者は、
Ｎ＋１個のＤＡＳＤのアレー５及びそのプロセッサをそ
のアレーに結合するアレー制御装置３から形成される。
プロセッサ１は、アプリケーション・コード及びシステ
ム・コードを実行するために使用される少なくとも１つ
又は複数個のプロセッサと、アプリケーション・コー
ド、システム・コード、及びデータを保持するためのメ
モリと、実行中のアプリケーションからの読取り要求及
び書込み要求に応答して外部記憶装置からシステム・コ
ード（又は、ＭＶＳ、ＡＩＸ、ＣＩＣＳ等のようなオペ
レーティング・システムとも呼ばれる）を通して情報を
アクセスするための手段とを含むものが望ましい。
【００２６】一般的には、１９８０年６月１０日発行の
「複数ＣＰＵ及び共用装置アクセス・システムにおける
パス独立装置の予約及び再結合のための方法及び装置」
と題した米国特許第４,２０７,６０９号及びそれの参考
文献に開示されているように、データへのアクセス・パ
スを設定するためのアーキテクチャが示される。ホスト
・プロセッサ又はＣＰＵは、そのアクセス・パスによっ
て、付属のＤＡＳＤ記憶サブシステムから可変長レコー
ド又は固定長レコードを得る。
【００２７】このアーキテクチャの下で、ＣＰＵは、
「チャネル・コマンド・ワード」又はＣＣＷと呼ばれる
特別目的のＩ／Ｏ命令の連鎖を使用してアクセスしそし
て要求／応答インターフェースを介して付属のサブシス
テムにデータ・ストリームを転送するための専用の仮想
プロセッサを構成する。ＣＣＷは、高速呼出しのサポー
トでＣＰＵメイン・メモリの一部分に記憶される。アプ
リケーション・プログラムが外部記憶装置（通常は、付
属のＤＡＳＤ記憶装置）へのアクセスを要求する読取り
又は書込みを実行する時、ＣＰＵのＳ／３７０ＭＶＳオ
ペレーティング・システムは「ＳＴＡＲＴ Ｉ／Ｏ」コ
マンドでもってそのような参照を開始する。このコマン
ドは、ＣＰＵにその多重処理状態を中断させ、ＣＣＷ連
鎖に移らせ、そしてＣＣＷ連鎖の完了後にそれの前の状
態を設定させる。
【００２８】図１を再び参照すると、プロセッサ１はパ
ス７を介して記憶制御装置（ＳＣＵ）９に適切なＣＣＷ
連鎖を送る。ＳＣＵ９はそれらＣＣＷの各々を「解釈」
し、それに応答して、パス１５を介してディレクトリ・
メモリ１９に対応の制御信号及びアドレス信号を与えて
バッファ１７又はＤＡＳＤアレー５におけるデータのロ
ケーションを確認させる。データは、パス７、ＳＣＵ
９、アクセス回路２１、バッファ装置１７、アクセス回
路２３、及びパス２６を含むパスを介してホスト・プロ
セッサ１とアレー５との間で転送される。そのホスト・
プロセッサ１は、アレー制御装置３により保持された記
憶モデルを使用してデータをアクセスする。これは、バ
ッファ１７の内容をＤＡＳＤアレー（ＤＡＳＤ１乃至Ｄ
ＡＳＤｎ＋１）上に所定のパターン及び条件でデステー
ジする（書き込む）ことによって表される。
【００２９】ＳＣＵ９及びバッファ１７は、ＣＣＷを解
釈しそして一般的な記憶装置に従ってそのバッファ及び
ＤＡＳＤアレーを管理するための十分に関連付けられた
メモリを有する少なくとも１つ又は複数個のマイクロプ
ロセッサと、ディレクトリ・メモリ１９に配され論理的
データ・ブロックから物理的データ・ブロックへのマッ
ピングを示すディレクトリと、論理的アフィニティを有
する一群のブロックを形成しそしてパリティ又は他の冗
長コードを計算するための手段と、修正されたデータ・
ブロックを保持するためのバッファ手段１７と、任意の
ＤＡＳＤとバッファ手段１７との間でデータ及び制御信
号を移動させるためのパス１１及び２５とを含む。
【００３０】ＤＡＳＤアレー５は、前述の米国特許出願
０８／１９６,０４７号によって定義されたＲＡＩＤ３
アレー又はＲＡＩＤ５アレーのようにＳＣＵ９によって
管理可能である。ＤＡＳＤアレー５に対するＲＡＩＤ３
の実施例では、データ・ストリング・セグメント化或い
はストライピング、一群のブロックへのパリティ割当
て、対応ＤＡＳＤからのパリティ・グループ或いはブロ
ックの同期アクセス、及び耐障害モード及び低下モード
の両方におけるアレー・オペレーションは、１９９０年
４月３日発行の「ディスク・ドライブ・メモリ」と題し
た米国特許第４,９１４,６５６号で説明されている。
【００３１】図２を参照すると、ＤＡＳＤ装置３５の書
込みパスの論理的ブロック図が示される。装置３５は、
図１に示されたＤＡＳＤアレー５を形成する幾つかのＤ
ＡＳＤの１つである。更に詳しくいえば、装置３５は、
データ・パス２５及びアドレス及び制御パス１１を介し
てアレー制御装置３と相互作用する。アドレス及び制御
パス１１はマイクロプロセッサ４１において終端し、一
方、データ・パス２５は、データ圧縮装置４５及び非圧
縮データのためのバッファ４９において終端する。プロ
セッサ４１は、ＤＡＳＤ装置のソフトウエア・ドライバ
のすべて又は一部分を記憶したローカル制御メモリ４３
と相互作用する。又、プロセッサ４１はパス５９を介し
て圧縮装置４５からのバイト・カウント出力を受ける。
そのプロセッサは、パス６１、６９、５７、及び６６を
介してそれぞれ圧縮データ・バッファ４７、書込み／再
書込みバッファ５１、非圧縮データ・バッファ４９、及
びドライバ制御回路５３の出力おける制御を行う。ヘッ
ド／ディスク・アーム・アセンブリ（図示されてない）
の位置付けは制御回路５３によってパス７３を介して調
整され、書込みモードにおいてはディスク記録媒体５５
上の１つ又は複数個のアドレスに記号シーケンスをレコ
ードさせ、読取りモードにおいては選択されたアドレス
から読取りシーケンスをレコードさせる。
【００３２】本発明では、線形スペース及びオーバフロ
ー・スペースがサイズ変更される時、現在の線形スペー
スの内容及びオーバフロー・スペースの内容は、図１に
示されたパス２５及びアクセス回路２３を介してアレー
制御装置３のバッファ１７に読み込まれる。実際の再書
込み又はブロックのサイズ変更は図２における圧縮機構
を通してオン・ザ・フライで行われ、バッファ５１にお
いて部分的にブロック化され、そしてバッファ５１から
ディスク記憶媒体５５に書き出される。プロセッサ４１
は、各ストリングの圧縮コピー及び非圧縮コピーのバイ
ト・サイズが両方ともそれにとって利用可能であるとい
う事実によって拡大するというデータ・シーケンスのす
べての傾向を制御することに留意すべきである。小さい
ストリングの選択は、パス６７におけるバッファ５１へ
のバッファ４９の出力及びパス６５におけるバッファ４
７の出力を、制御パス５７及び６１を介して選択的に禁
止することによって行われる。
【００３３】図３を参照すると、英語のテキスト記号に
対する発生の全体的なゼロ桁ガウス又はラプラス確率分
布が示される。このような全体的な記号確率分布は、そ
れらの標準偏差の関数として歪ベル型特性曲線をとる。
この曲線は、下方尾部における平均値からの２又はそれ
以上の標準偏差で発生確率を有する記号が正の圧縮比ｒ
と一致するような圧縮比の部分的順序に重畳されてい
る。この一致に起因する比率ｒは、線形アドレス・セグ
メントの各々の最大圧縮サイズを最初に決定するために
使用される。即ち、圧縮セグメント・サイズ＝非圧縮サ
イズ／ｒである。ｒは下方境界であるので、高い圧縮を
受けた記号ストリングは、高い確率をもってセグメント
にマップ可能である。決定的なことは、下方尾部の確率
ポイントが低い圧縮比と一致して選択されることであ
る。
【００３４】本願明細書では、Ｎ個の等しいサイズのセ
グメントの用語「線形マップ・スペース」、「線形範
囲」及び「１次バンド又は領域」は、「オーバフロー・
スペース」、「オーバフロー範囲」、及び「２次バンド
又は領域」と同義的に使用される。
【００３５】図４を参照すると、線形アドレス・スペー
スにおける非圧縮記号ストリングの５つのトラック、即
ち、指定されたセグメント０−４が示される。これらの
ストリングは、対応の小さいサイズのセグメントへの圧
縮を通して同じ数の線形マップ・スペース（しかし、小
さいサイズの及び等しい長さの圧縮セグメント＋オーバ
フロー・セグメント）にマップされる。「Ｎ個の圧縮セ
グメント＋オーバフロー・セグメント」の結合したサイ
ズは、それらコンポーネントが周期的にサイズ変更され
ても一定のままである。
【００３６】圧縮は確率的プロセスであるため、圧縮ス
トリングの長さは変化する。図４の右側はそのシナリオ
の幾つかを示す。例えば、非圧縮セグメント０は線形セ
グメント１をオーバフローし、２つまでのオーバフロー
・セグメント・スペースを必要とする。これに関して、
線形セグメント及びオーバフロー・セグメントは、線形
セグメントに組み込まれる第１のオーバフロー・セグメ
ントに対するポインタ及びその第１のオーバフロー・セ
グメントに組み込まれる第２のオーバフロー・セグメン
トに対するポインタを有するリンク・リストとして結合
される。又、非圧縮セグメント１、３、及び４は変化す
るオーバフロー・サイズの圧縮セグメントにマップさ
れ、一方、非圧縮セグメント２はそれと関連するオーバ
フローを持たない。問題は、線形マップされた領域が大
きく又は小さくサイズ変更されるべきかどうかを周期的
に確認することである。サイズ変更は、オーバフローの
ために利用可能なスペースの減少時に線形マップされた
スペースにおけるＮ個の等しい長さの圧縮セグメントに
とって使用可能なスペースを増加させるか、又はその逆
である。この属性は、０又は１次圧縮比統計の変化及び
セグメントの更新書込みにおけるオーバフロー又はアン
ダーフローの変化に適応する。
【００３７】図５を参照すると、１次領域及び２次領域
に区分けされたディスク上に非圧縮記号シーケンスのデ
ィスク記憶セグメントをマップするという１つのタイプ
が示される。線形にアドレスされる圧縮セグメントの１
次領域はＮ個の外側トラックを占め、一方、Ｎ／２個の
トラックの２次領域は、最初は、オーバフロー拡張のた
めに予約される。図６は、非圧縮トラックを或る論理レ
ベルの線形にアドレス可能な記憶装置におけるＮ個の圧
縮１次セグメント対応にマップしたもの及びすべてのオ
ーバフローをＮ／２個の２次セグメント又はオーバフロ
ー・セグメントのうちのリンク・リスト・セグメントに
マップしたものを示す。１００メガバイトの非圧縮記憶
装置に対して、２.５／１という正規の圧縮比を仮定す
ると、これは、それの元のサイズの４０％のスペースに
マップされるであろう。元のスペースの１／２がオーバ
フローに割り当てられる場合、これは２.５／１の圧縮
の下では元のスペースの２０％にマップされるであろ
う。１次領域がフルであり且つオーバフロー領域がフル
でない場合、オーバフロー領域は十分に利用されない。
オーバフロー領域がフルであり且つ１次領域がフルでな
い場合、有効容量は減少する。
【００３８】図７及び図８を参照すると、本発明に従っ
て、ステップ状連続ベースでの、線形マップ領域及びオ
ーバフロー領域の動的なサイズ変更が示される。これら
の図は、サイズ変更が１次領域及びオーバフロー領域の
間のようなスペースを動的に再配分する方法を表す６つ
のステップを示す。理解を助けるものとして、スペース
利用は、図８の下部に見られる種々のクロス・ハッチン
グによってコード化される。
【００３９】図７のステップ１を参照すると、１次セグ
メント又はブロックは０乃至４の参照番号を付される。
ブロック１及び３はオーバフローしており、オーバフロ
ー領域におけるブロックを指している。ブロック０、
２、及び４は全体的にフルというのではない。オーバフ
ロー領域は、追加のスペースを必要とした１次ブロック
に２つのブロックを割り当てられる。矢印はこれらのオ
ーバフロー・ブロックを指している。
【００４０】ステップ１によれば、４つのオーバフロー
・ブロックをだけが１次領域による使用のために利用可
能である。
【００４１】オーバフローを処理する装置ドライバの部
分は、ディスク上のすべてのブロックを追跡するように
初期設定されるであろう。しかし、実際に１次領域に割
り当てられるブロックはその１次領域に事前割り振りさ
れるであろう。オーバフロー・ソフトウエア管理が「知
っている」範囲まで、トラックはすべてブロックをオー
バフロー領域に対して容易に自由にする。
【００４２】図７のステップ２を参照すると、ブロック
４が「サイズ変更」された。即ち、ブロック４は、如何
なるオーバフロー・ブロックも必要とすることなくサイ
ズ変更されるに十分なほど小さい。従って、１次領域に
よって使用されなかった１つの追加のブロックがオーバ
フロー領域に再割当て可能である。図７のステップ３で
は、ブロック３がサイズ変更された。ブロック３は、既
に、追加のオーバフロー・ブロックを必要とするに十分
なほど大きいので、そのオーバフロー・ブロックから他
のオーバフロー・ブロックを指す矢印が挿入される。ブ
ロック３のサイズ変更の後、オーバフロー領域は、未使
用の１次ブロックを自由にすることができる。
【００４３】図７のステップ４を参照すると、すべての
ブロックのサイズ変更が示される。ブロック１の最終的
なサイズ変更の結果、自由ブロックがオーバフロー領域
の真の「トップ」になることに留意して欲しい。それに
関連して、図８のステップ５では、ブロック１がオーバ
フロー領域の真のトップにおける自由ブロックまで移動
させられる。これは、オーバフロー領域に対して未使用
の１次ブロックを自由にする。最後に、図８のステップ
６はサイズ変更及び一次ブロックの移動の最終結果を示
す。依然として５つのブロックが存在するが、それらは
小さい連続した領域にある。１次ブロックは小さいの
で、オーバフローの高い可能性があり、追加のオーバフ
ロー・ブロックが１次ブロック又はオーバフロー・ブロ
ックによって使用可能である。
【００４４】Ｃ＋＋コメント付きコードで表されたクラ
イアント・サーバ装置ドライバの好適な実施例を以下で
説明する。
【００４５】動作的には、記憶サブシステムの管理が、
クライアント／サーバ相互作用をモデル化したソフトウ
エア・サブシステム及び装置ドライバの形で表される。
従って、本発明はアレー制御装置３又はＤＡＳＤ２７−
３５のレベルで実施可能である。何れの場合も、アレー
・コントローラ及びそれら装置の各々に存在するコード
はイニシャライザ、割込みハンドラ、モニタ、及びサー
バを含むであろう。本願明細書で後述されるイニシャラ
イザ機能、ハンドラ機能、モニタ機能、及びサーバ機能
はコメント付きＣ＋＋ソース・コードの形式のものであ
る。
【００４６】Ｃ＋＋は、Ｃ言語のスーパセットを形成す
るオブジェクト指向のプログラミング言語システムであ
る。オブジェクト、クラス、継承、多形性、過負荷、及
びそれの構文上の及び予約されたワード規約のようなそ
の言語のアトリビュートは、カリフォルニア州コルテ・
マデラにあるウェイト・グループ・プレス（Waite Grou
p Press）社による１９９２年の著作権のレイフォア（L
afore）著「マイクロソフトＣ＋＋におけるオブジェク
ト指向プログラミング（Object Oriented Programming
in Microsoft C++）」又はマジソン・ウェスリ出版社
（Addison-WesleyPub.Co.）による１９９４年の著作権
のＤ．マーク（Dave Mark）著「ＰＣにおけるＣ＋＋の
学習（Learn C++ The PC）」のような多くの文献におい
て開示されている。Ｃ＋＋においては、"/*---*/"及び"
//---"の両方がコメント・トークンとして作用する。
【００４７】幾つかの実行のソフトウエア・スレッドが
同時にサブシステム内に共存し得ることは明らかであ
る。単一のソフトウエア・スレッドという概念は、オペ
レーティング・システムからのサービス・リクエストに
応答するサーバのような１つ又は複数個のプロセスが要
求／応答関係にあることを意味する。独立したスレッド
は何れの他のスレッドに関しても、それが同時に呼び出
されても、必要な従属性を持たないスレッドである。本
発明では、線形マップ・スペースを評価及びサイズ変更
するためのモニタは、システム・クロックによって登録
された所定の時間及びインターバルのような何らかの事
象に基づいて、オペレーティング・システムによって呼
び出される。一方、サーバは連続的にスピンしながら、
ホストＣＰＵからサブシステムを送られたコマンドのア
クセスを待つ。
【００４８】ＤＡＳＤに存在するドライバは、Ｃ＋＋表
記において、次のような汎用の機能を含む。即ち、
【００４９】サーバは、ディスク全体におけるデータを
管理するディスク・オブジェクトを作成するであろう。
表２に示されたコード・シーケンスでは、ディスク・オ
ブジェクトは単一の１次バンド及び単一のオーバフロー
・バンドを作成する。オペレーティング・システムはモ
ニタと呼ばれる独立したスレッドを開始する。そのモニ
タ・スレッドは、オーバフローの数が大き過ぎないか又
は小さ過ぎないかどうかを周期的に評価するであろう。
しかる後、それは「サイズ変更」を呼び出すことによっ
て１次領域をサイズ変更するであろう。一方、「サイズ
変更」は１次バンドを調節するために、「ＭａｋｅＳｍ
ａｌｌｅｒ」又は「ＭａｋｅＬａｒｇｅｒ」を呼び出
す。これらの機能はバンド機能、サイズ変更、移動、パ
ック、及び予約メンバ機能を呼び出す。
【００５０】モニタ・スレッドが呼び出される時、それ
はサーバ・スレッドをサイズ変更期間の間中断させる。
サイズ変更はかなりの時間期間にわたって生じ得るた
め、アクセス・オペレーションに対する大きな中断を回
避するためには、それは便宜的に又は周期的にスケジュ
ール可能である。
【００５１】初期化後の装置レベルにおけるドライバの
主要スレッドのサーバ部分は、無限のＤＯ／ＷＨＩＬＥ
ループを実行する。これは、表１乃至表４において、コ
メント付きＣ＋＋ソース・コードで表される。
【００５２】なお、下記の表において、表１乃至表４及
び表５乃至表２１が、それぞれ、全体として１つの表を
構成するものである。
【表１】
【表２】
【表３】
【表４】
【表５】
【表６】
【表７】 /*--------------------------------------*/ /*事物のアレーを追跡するオブジェクトを定義する。*/ /*+各事物は割り振られるか或いは自由である。 */ /*--------------------------------------*/ class BitMap{ public: BitMap(int Size); int GetBlock(); //次のフリーブロックを得る int FreeBlock(int); //ブロックをフリーとして マークする BitMap *Split(int start); //ビットマップをス プリットする bool Reserve(int,int); //ブロックを留保する unsigned int *GetList(); //アレーをダンプす る準備をする void SetList(int,int*); //アレーを回復する int GetNumTaken(){return NumTaken;} private; int NumBits; //事物の数 int Numints; //アレーにおける整数の数 int NumFree; //自由な事物の数 int NumTaken; //取られた事物の数 unsigned int *FreeBlockList; 取られた事物を追 跡するためのアレー };
【表８】
【表９】
【表１０】
【表１１】
【表１２】
【表１３】
【表１４】
【表１５】
【表１６】
【表１７】
【表１８】
【表１９】
【表２０】
【表２１】
【００５３】本発明の方法及び装置は、内部の断片化を
小さくするように調節可能な任意の固定サイズ・アドレ
ス可能記憶スペースに拡張可能であり、このまま、線形
マッピングの質を維持するように更に遅いペースで、或
いはオフライン・オペレーションとして、その圧縮比を
１次領域における割振りに対して適応することも可能で
ある。
【００５４】本発明は、ホスト及び記憶サブシステムの
情報状態の整合性を確保するためにレイト・バインディ
ング（ｌａｔｅ−ｂｉｎｄｉｎｇ）を使用する固定サイ
ズ・アドレス可能記憶スペースの任意の圧縮バンドにも
拡張可能である。
【００５５】まとめとして、本発明の構成に関して以下
の事項を開示する。
【００５６】（１）有限のアドレス可能な記憶媒体にお
ける対応アドレスで固定長記号ストリングの圧縮イメー
ジの同所更新書込みを行うシステムにおいて、前記有限
の記憶媒体における前記ストリングの参照の局所性を維
持するアドレス・スペース管理方法であって、 （ａ）前記有限の記憶媒体を線形アドレス可能なスペー
スにおけるＮ１のセグメントに及びリンク・リスト・ア
ドレス可能なスペースにおけるＮ２のセグメントに区分
けするステップであって、Ｎ１における各セグメントは
非圧縮記号ストリングの見積平均長よりも小さい第１の
長さのものであり、Ｎ２における各セグメントは前記非
圧縮記号ストリングの見積平均長よりも小さい第２の長
さのものであるステップと、 （ｂ）前記固定長記号ストリングのうちの記号ストリン
グの圧縮イメージでもってＮ１におけるセグメントを１
対１及びオンツーで移植するステップと、 （ｃ）前記Ｎ１のセグメント相互間に記憶された記号ス
トリングの圧縮イメージのうちの圧縮イメージを同所更
新するステップあって、（ｃ１）Ｎ１におけるセグメン
トのサイズを超えるすべての圧縮記号ストリング・イメ
ージの部分を、Ｎ２における１つ又は複数個の対応セグ
メントに書き込むステップと、（ｃ２）Ｎ２におけるセ
グメントを指すトークンをＮ１における対応セグメント
に組み込むステップと、を含むステップと、 （ｄ）Ｎ２におけるセグメントの数がＮ２における現在
のセグメントの数の所定パーセンテージの範囲内にある
ようにＮ１におけるすべてのセグメントのサイズを１つ
方向に反復的に調節するステップと、を含む方法。 （２）前記ステップ（ｄ）は、便宜上の基準で又は周期
的にスケジュールされた基準で前記ステップ（ｂ）乃至
ステップ（ｄ）を反復するステップを含むことを特徴と
する上記（１）に記載の方法。 （３）複数個の動的なマルコフ記号ストリング・ソース
によって発生された固定長ストリング及び前記固定長ス
トリングの圧縮イメージを固定サイズの循環式記憶媒体
の対応アドレスに書き込むための手段に応答するシステ
ムにおいて、少なくとも所定の下方圧縮比境界を維持し
ながら前記圧縮イメージを同所更新して前記記憶媒体に
再書込みするアドレス・スペース管理方法であって、 （ａ）前記ストリング・ソースにわたって低い末尾を有
するガウス又はラプラス記号の全体的な確率分布を、圧
縮比の部分的順序範囲ｒ０，ｒ１，．．．，ｒ
ｍ，．．．上に重畳したものとして決定するステップ
と、 （ｂ）前記記憶媒体をＮ１の線形アドレス可能なセグメ
ント及びＮ２のリンク・リスト・アドレス可能なセグメ
ントに区分けするステップであって、前記Ｎ１のセグメ
ントの各々は一定のブロック、レコード、又はトラック
の記号のサイズを、前記確率分布の低い末尾における所
定の標準偏差において一致した圧縮比ｒによって除した
ものに近似するステップと、 （ｃ）前記固定長記号ストリングのうちの記号ストリン
グの圧縮イメージでもってＮ１における前記セグメント
を１対１及びオンツーで移植するステップと、 （ｄ）Ｎ１における前記セグメントのうちのセグメント
におけるストリングを同所更新するステップであって、
（ｄ１）前記セグメントのサイズを超えるすべての圧縮
イメージの部分をＮ２における１つ又は複数個の対応セ
グメントに書き込むステップと、（ｄ２）Ｎ２における
セグメントを指すトークンをＮ１における対応セグメン
トに組み込むステップと、を含むステップと、 （ｅ）Ｎ２におけるセグメントの数がＮ２における現在
のセグメントの数の所定パーセンテージ範囲内にあるよ
うにＮ１におけるすべてのセグメントのサイズを１つの
方向に反復的に調節するステップと、を含む方法。 （４）前記ステップ（ｅ）は、便宜上の基準で又は周期
的にスケジュールされた基準で前記ステップ（ｂ）乃至
ステップ（ｄ）を反復するステップを含むことを特徴と
する上記（３）に記載の方法。 （５）前記ステップ（ｅ）における前記所定パーセンテ
ージ範囲は１％及び５％の間にあることを特徴とする上
記（３）に記載の方法。 （６）前記ステップ（ｅ）は周期的なスケジュール又は
便宜的なスケジュールで実行され、更に、前記ステップ
（ｅ）は（１）Ｎ１におけるセグメント・サイズが増加
している場合、Ｎ２に割り当てられたセグメントからＮ
１において使用するためのセグメントを再生するステッ
プと、（２）Ｎ１におけるセグメント・サイズが減少し
ている場合、Ｎ１に割り当てられたセグメントからＮ２
において使用するためのセグメントを再生するステップ
と、から成るセットから選択されたステップの１つを含
むことを特徴とする上記（３）に記載の方法。 （７）有限のアドレス可能な記憶媒体における対応アド
レスにおいて固定長記号ストリングの圧縮イメージの同
所更新書込みを行うためのシステムにおいて、前記有限
の記憶媒体における前記ストリングの参照の局所性を維
持するアドレス・スペース管理方法であって、 （ａ）前記有限の記憶媒体を線形アドレス可能なスペー
スにおいてＮ１のセグメントに及びリンク・リスト・ア
ドレス可能なスペースにおけるＮ２のセグメントに区分
けするステップであって、Ｎ１における各セグメントは
「第１の長さ＜非圧縮記号ストリングの見積平均長」の
ものであること及びＮ２における各セグメントは「第２
の長さ＜非圧縮記号ストリングの見積平均長」のもので
あるステップと、 （ｂ）前記固定長記号ストリングのうちの記号ストリン
グの圧縮イメージでもってＮ１におけるセグメントを１
対１及びオンツーで移植するステップと、 （ｃ）前記Ｎ１のセグメント相互間に記憶された記号ス
トリングの圧縮イメージのうちの圧縮イメージを同所更
新するステップあって、（ｃ１）Ｎ１におけるセグメン
トのサイズを超えるすべての圧縮記号ストリング・イメ
ージの部分を、Ｎ２における１つ又は複数個の対応セグ
メントに書き込むステップと、（ｃ２）Ｎ２におけるセ
グメントを指すトークンをＮ１における対応セグメント
に組み込むステップと、を含むステップと、 （ｄ）Ｎ２におけるセグメントの数がＮ２における現在
のセグメントの数の所定パーセンテージの範囲内にある
ようにＮ１におけるすべてのセグメントのサイズを１つ
の方向に反復的に調節するステップと、を含み、前記サ
イズを反復的に調節するステップは、（１）Ｎ１におけ
るセグメント・サイズが増加している場合、Ｎ２に割り
当てられたセグメントからＮ１において使用するための
セグメントを再生するステップと、（２）Ｎ１における
セグメント・サイズが減少している場合、Ｎ１に割り当
てられたセグメントからＮ２において使用するためのセ
グメントを再生するステップと、を含むことを特徴とす
る方法。 （８）前記ステップ（ｄ）における前記所定パーセンテ
ージ範囲は１％及び５％の間にあること、及び前記ステ
ップ（ｄ）は前記ステップ（ｂ）乃至ステップ（ｄ）を
周期的スケジュールで又は便宜的スケジュールで実行す
るステップを含むことを特徴とする上記（７）に記載の
方法。 （９）複数個の循環記憶装置及び前記記憶装置を接続す
る制御装置を有し、コマンドに応答して前記制御装置及
び付属のＣＰＵの間で非圧縮データを移動させるための
記憶サブシステムにして、各記憶装置は記号ストリング
の各々が前記記憶装置上のアドレス可能なロケーション
にレコードされる時に前記記号ストリングを圧縮するた
めの手段及び前記記憶装置上のアドレス可能なロケーシ
ョンに記憶された前記記号ストリングから非圧縮イメー
ジを生成するための手段を有するものにおいて、前記記
憶装置上の一定サイズのアドレス・スペースを複数個の
線形アドレス可能セグメント及び複数個のリンク・リス
ト・アドレス可能セグメントに区分けするための手段で
あって、各線形アドレス可能セグメントのサイズは圧縮
記号ストリングの平均的見積長であるものと、前記記憶
装置上の前記線形アドレス可能セグメントを１対１及び
オンツーで移植する手段と、前記線形アドレス可能セグ
メントのうちの選択されたセグメントを同所更新し、前
記線形アドレス可能セグメントのサイズを超えるすべて
の圧縮記号ストリングを１つ又は複数個の対応するリン
ク・リスト・アドレス可能セグメントに書き込み、前記
リンク・リスト・アドレス可能セグメントを指すトーク
ンを対応する線形アドレス可能セグメントに組み込むた
めの各記憶装置における手段と、前記リンク・リスト・
アドレス可能セグメントの数が現在のリンク・リスト・
アドレス可能セグメントの数の所定のパーセンテージ範
囲内にあるようにすべての線形アドレス可能セグメント
のサイズを１つの方向に反復的に調節する手段と、を含
む記憶サブシステム。 （１０）前記調節する手段は、前記線形アドレス可能セ
グメントのサイズが増加している場合、線形アドレス可
能セグメントとして使用するためにリンク・リスト・ア
ドレス可能セグメントを再生する手段と、前記線形アド
レス可能セグメントのサイズが減少している場合、リン
ク・リスト・アドレス可能セグメントとして使用するた
めに線形アドレス可能セグメントを再生する手段と、を
含むことを特徴とする上記（９）に記載の記憶サブシス
テム。
【図面の簡単な説明】
【図１】本発明の線形アドレス・スペース及びオーバフ
ロー・スペースをサイズ変更を可能にする、データへの
主要アクセス・パスを表すＤＡＳＤアレー記憶サブシス
テムを示す。
【図２】圧縮及び再ブロック化バッファリングを通して
オン・ザ・フライによるサイズ変更に適応し得る、図１
に示されたＤＡＳＤの制御電子回路を介する書込みパス
を示す。
【図３】圧縮比の部分的順序範囲上に重畳された所定の
アルファベットから選択された記号の相対的な発生頻度
を示す。
【図４】本発明による、非圧縮データとそれの線形マッ
プ圧縮の対応体との間の概念上の関係を示す。
【図５】非圧縮ブロックを記憶する磁気ディスク及び線
形及びオーバフロー領域の１次バンド及び２次バンドに
区分けされた磁気ディスクを示す。
【図６】線形論理アドレス・スペースへの投影、即ち、
対応の圧縮領域及びオーバフロー領域へのＤＡＳＤトラ
ックの線形マッピングを示す。
【図７】本発明による線形マップ及びオーバフロー領域
の動的なサイズ変更をステップ状の連続的変化を示す。
【図８】本発明による線形マップ及びオーバフロー領域
の動的なサイズ変更をステップ状の連続的変化を示す。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ジョー−ミン・チェン アメリカ合衆国カリフォルニア州、カパー ティノ、ダナス・ドライブ 7472 (72)発明者 ローレンス・ジョン・ギャリバイ アメリカ合衆国カリフォルニア州、サン・ ノゼ、フィニー・ウェイ 7451 (72)発明者 ヤイシャンカー・ムースデス・メノン アメリカ合衆国カリフォルニア州、サン・ ノゼ、ステアリング・ゲート・ドライブ 1095 (72)発明者 チャン・イウ・ング アメリカ合衆国カリフォルニア州、サン・ ノゼ、タイル・レーン 21599 (72)発明者 トラム・ティ・マイ・ニュイェン アメリカ合衆国カリフォルニア州、サン・ ノゼ、キンダー・ヒル・ドライブ 7087

Claims (10)

    【特許請求の範囲】
  1. 【請求項１】有限のアドレス可能な記憶媒体における対
    応アドレスで固定長記号ストリングの圧縮イメージの同
    所更新書込みを行うシステムにおいて、前記有限の記憶
    媒体における前記ストリングの参照の局所性を維持する
    アドレス・スペース管理方法であって、 （ａ）前記有限の記憶媒体を線形アドレス可能なスペー
    スにおけるＮ１のセグメントに及びリンク・リスト・ア
    ドレス可能なスペースにおけるＮ２のセグメントに区分
    けするステップであって、Ｎ１における各セグメントは
    非圧縮記号ストリングの見積平均長よりも小さい第１の
    長さのものであり、Ｎ２における各セグメントは前記非
    圧縮記号ストリングの見積平均長よりも小さい第２の長
    さのものであるステップと、 （ｂ）前記固定長記号ストリングのうちの記号ストリン
    グの圧縮イメージでもってＮ１におけるセグメントを１
    対１及びオンツーで移植するステップと、 （ｃ）前記Ｎ１のセグメント相互間に記憶された記号ス
    トリングの圧縮イメージのうちの圧縮イメージを同所更
    新するステップあって、（ｃ１）Ｎ１におけるセグメン
    トのサイズを超えるすべての圧縮記号ストリング・イメ
    ージの部分を、Ｎ２における１つ又は複数個の対応セグ
    メントに書き込むステップと、（ｃ２）Ｎ２におけるセ
    グメントを指すトークンをＮ１における対応セグメント
    に組み込むステップと、を含むステップと、 （ｄ）Ｎ２におけるセグメントの数がＮ２における現在
    のセグメントの数の所定パーセンテージの範囲内にある
    ようにＮ１におけるすべてのセグメントのサイズを１つ
    方向に反復的に調節するステップと、 を含む方法。
  2. 【請求項２】前記ステップ（ｄ）は、便宜上の基準で又
    は周期的にスケジュールされた基準で前記ステップ
    （ｂ）乃至ステップ（ｄ）を反復するステップを含むこ
    とを特徴とする請求項１に記載の方法。
  3. 【請求項３】複数個の動的なマルコフ記号ストリング・
    ソースによって発生された固定長ストリング及び前記固
    定長ストリングの圧縮イメージを固定サイズの循環式記
    憶媒体の対応アドレスに書き込むための手段に応答する
    システムにおいて、少なくとも所定の下方圧縮比境界を
    維持しながら前記圧縮イメージを同所更新して前記記憶
    媒体に再書込みするアドレス・スペース管理方法であっ
    て、 （ａ）前記ストリング・ソースにわたって低い末尾を有
    するガウス又はラプラス記号の全体的な確率分布を、圧
    縮比の部分的順序範囲ｒ０，ｒ１，．．．，ｒ
    ｍ，．．．上に重畳したものとして決定するステップ
    と、 （ｂ）前記記憶媒体をＮ１の線形アドレス可能なセグメ
    ント及びＮ２のリンク・リスト・アドレス可能なセグメ
    ントに区分けするステップであって、前記Ｎ１のセグメ
    ントの各々は一定のブロック、レコード、又はトラック
    の記号のサイズを、前記確率分布の低い末尾における所
    定の標準偏差において一致した圧縮比ｒによって除した
    ものに近似するステップと、 （ｃ）前記固定長記号ストリングのうちの記号ストリン
    グの圧縮イメージでもってＮ１における前記セグメント
    を１対１及びオンツーで移植するステップと、 （ｄ）Ｎ１における前記セグメントのうちのセグメント
    におけるストリングを同所更新するステップであって、
    （ｄ１）前記セグメントのサイズを超えるすべての圧縮
    イメージの部分をＮ２における１つ又は複数個の対応セ
    グメントに書き込むステップと、（ｄ２）Ｎ２における
    セグメントを指すトークンをＮ１における対応セグメン
    トに組み込むステップと、 を含むステップと、 （ｅ）Ｎ２におけるセグメントの数がＮ２における現在
    のセグメントの数の所定パーセンテージ範囲内にあるよ
    うにＮ１におけるすべてのセグメントのサイズを１つの
    方向に反復的に調節するステップと、 を含む方法。
  4. 【請求項４】前記ステップ（ｅ）は、便宜上の基準で又
    は周期的にスケジュールされた基準で前記ステップ
    （ｂ）乃至ステップ（ｄ）を反復するステップを含むこ
    とを特徴とする請求項３に記載の方法。
  5. 【請求項５】前記ステップ（ｅ）における前記所定パー
    センテージ範囲は１％及び５％の間にあることを特徴と
    する請求項３に記載の方法。
  6. 【請求項６】前記ステップ（ｅ）は周期的なスケジュー
    ル又は便宜的なスケジュールで実行され、更に、前記ス
    テップ（ｅ）は （１）Ｎ１におけるセグメント・サイズが増加している
    場合、Ｎ２に割り当てられたセグメントからＮ１におい
    て使用するためのセグメントを再生するステップと、 （２）Ｎ１におけるセグメント・サイズが減少している
    場合、Ｎ１に割り当てられたセグメントからＮ２におい
    て使用するためのセグメントを再生するステップと、 から成るセットから選択されたステップの１つを含むこ
    とを特徴とする請求項３に記載の方法。
  7. 【請求項７】有限のアドレス可能な記憶媒体における対
    応アドレスにおいて固定長記号ストリングの圧縮イメー
    ジの同所更新書込みを行うためのシステムにおいて、前
    記有限の記憶媒体における前記ストリングの参照の局所
    性を維持するアドレス・スペース管理方法であって、 （ａ）前記有限の記憶媒体を線形アドレス可能なスペー
    スにおいてＮ１のセグメントに及びリンク・リスト・ア
    ドレス可能なスペースにおけるＮ２のセグメントに区分
    けするステップであって、Ｎ１における各セグメントは
    「第１の長さ＜非圧縮記号ストリングの見積平均長」の
    ものであること及びＮ２における各セグメントは「第２
    の長さ＜非圧縮記号ストリングの見積平均長」のもので
    あるステップと、 （ｂ）前記固定長記号ストリングのうちの記号ストリン
    グの圧縮イメージでもってＮ１におけるセグメントを１
    対１及びオンツーで移植するステップと、 （ｃ）前記Ｎ１のセグメント相互間に記憶された記号ス
    トリングの圧縮イメージのうちの圧縮イメージを同所更
    新するステップあって、（ｃ１）Ｎ１におけるセグメン
    トのサイズを超えるすべての圧縮記号ストリング・イメ
    ージの部分を、Ｎ２における１つ又は複数個の対応セグ
    メントに書き込むステップと、（ｃ２）Ｎ２におけるセ
    グメントを指すトークンをＮ１における対応セグメント
    に組み込むステップと、を含むステップと、 （ｄ）Ｎ２におけるセグメントの数がＮ２における現在
    のセグメントの数の所定パーセンテージの範囲内にある
    ようにＮ１におけるすべてのセグメントのサイズを１つ
    の方向に反復的に調節するステップと、を含み、前記サ
    イズを反復的に調節するステップは、（１）Ｎ１におけ
    るセグメント・サイズが増加している場合、Ｎ２に割り
    当てられたセグメントからＮ１において使用するための
    セグメントを再生するステップと、（２）Ｎ１における
    セグメント・サイズが減少している場合、Ｎ１に割り当
    てられたセグメントからＮ２において使用するためのセ
    グメントを再生するステップと、を含むことを特徴とす
    る方法。
  8. 【請求項８】前記ステップ（ｄ）における前記所定パー
    センテージ範囲は１％及び５％の間にあること、及び前
    記ステップ（ｄ）は前記ステップ（ｂ）乃至ステップ
    （ｄ）を周期的スケジュールで又は便宜的スケジュール
    で実行するステップを含むことを特徴とする請求項７に
    記載の方法。
  9. 【請求項９】複数個の循環記憶装置及び前記記憶装置を
    接続する制御装置を有し、コマンドに応答して前記制御
    装置及び付属のＣＰＵの間で非圧縮データを移動させる
    ための記憶サブシステムにして、各記憶装置は記号スト
    リングの各々が前記記憶装置上のアドレス可能なロケー
    ションにレコードされる時に前記記号ストリングを圧縮
    するための手段及び前記記憶装置上のアドレス可能なロ
    ケーションに記憶された前記記号ストリングから非圧縮
    イメージを生成するための手段を有するものにおいて、 前記記憶装置上の一定サイズのアドレス・スペースを複
    数個の線形アドレス可能セグメント及び複数個のリンク
    ・リスト・アドレス可能セグメントに区分けするための
    手段であって、各線形アドレス可能セグメントのサイズ
    は圧縮記号ストリングの平均的見積長であるものと、 前記記憶装置上の前記線形アドレス可能セグメントを１
    対１及びオンツーで移植する手段と、 前記線形アドレス可能セグメントのうちの選択されたセ
    グメントを同所更新し、前記線形アドレス可能セグメン
    トのサイズを超えるすべての圧縮記号ストリングを１つ
    又は複数個の対応するリンク・リスト・アドレス可能セ
    グメントに書き込み、前記リンク・リスト・アドレス可
    能セグメントを指すトークンを対応する線形アドレス可
    能セグメントに組み込むための各記憶装置における手段
    と、 前記リンク・リスト・アドレス可能セグメントの数が現
    在のリンク・リスト・アドレス可能セグメントの数の所
    定のパーセンテージ範囲内にあるようにすべての線形ア
    ドレス可能セグメントのサイズを１つの方向に反復的に
    調節する手段と、 を含む記憶サブシステム。
  10. 【請求項１０】前記調節する手段は、 前記線形アドレス可能セグメントのサイズが増加してい
    る場合、線形アドレス可能セグメントとして使用するた
    めにリンク・リスト・アドレス可能セグメントを再生す
    る手段と、 前記線形アドレス可能セグメントのサイズが減少してい
    る場合、リンク・リスト・アドレス可能セグメントとし
    て使用するために線形アドレス可能セグメントを再生す
    る手段と、 を含むことを特徴とする請求項９に記載の記憶サブシス
    テム。
JP7301784A 1994-11-22 1995-11-20 アドレス・スペースを管理するための方法及び記憶サブシステム Pending JPH08234921A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US343316 1994-11-22
US08/343,316 US5666114A (en) 1994-11-22 1994-11-22 Method and means for managing linear mapped address spaces storing compressed data at the storage subsystem control unit or device level

Publications (1)

Publication Number Publication Date
JPH08234921A true JPH08234921A (ja) 1996-09-13

Family

ID=23345590

Family Applications (1)

Application Number Title Priority Date Filing Date
JP7301784A Pending JPH08234921A (ja) 1994-11-22 1995-11-20 アドレス・スペースを管理するための方法及び記憶サブシステム

Country Status (2)

Country Link
US (1) US5666114A (ja)
JP (1) JPH08234921A (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015097739A1 (ja) * 2013-12-24 2015-07-02 株式会社日立製作所 ストレージ装置及びその制御方法
US10452614B2 (en) 2015-06-12 2019-10-22 International Business Machines Corporation Storage data reduction analysis and forecast

Families Citing this family (96)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6021408A (en) * 1996-09-12 2000-02-01 Veritas Software Corp. Methods for operating a log device
US5832515A (en) * 1996-09-12 1998-11-03 Veritas Software Log device layered transparently within a filesystem paradigm
US6067199A (en) * 1997-06-30 2000-05-23 Emc Corporation Method and apparatus for increasing disc drive performance
US6178489B1 (en) 1998-06-08 2001-01-23 International Business Machines Corporation Method and apparatus for managing linear address mapped storage under selective compression and regency of usage constraints
US6535949B1 (en) 1999-04-19 2003-03-18 Research In Motion Limited Portable electronic device having a log-structured file system in flash memory
US6463503B1 (en) * 1999-05-12 2002-10-08 International Business Machines Corporation Method and system for increasing concurrency during staging and destaging in a log structured array
US6804676B1 (en) * 1999-08-31 2004-10-12 International Business Machines Corporation System and method in a data processing system for generating compressed affinity records from data records
US6463513B1 (en) 1999-09-07 2002-10-08 International Business Machines Corporation Cache storage optimization in a data storage library of a redundant copy synchronization token tracking system
US6470345B1 (en) 2000-01-04 2002-10-22 International Business Machines Corporation Replacement of substrings in file/directory pathnames with numeric tokens
US6718434B2 (en) * 2001-05-31 2004-04-06 Hewlett-Packard Development Company, L.P. Method and apparatus for assigning raid levels
US7126500B2 (en) * 2002-06-26 2006-10-24 Microsoft Corporation Method and system for selecting grammar symbols for variable length data compressors
US7434214B2 (en) * 2004-01-21 2008-10-07 International Business Machines Corporation Method for determining a close approximate benefit of reducing memory footprint of a Java application
EP1939751A1 (en) * 2006-12-22 2008-07-02 Telefonaktiebolaget LM Ericsson (publ) Storing compressed data
WO2008138042A1 (en) * 2007-05-10 2008-11-20 Chrystall, Alexander, George, Mallick System and/or method for reducing disk space usage and improving input/output performance of computer systems
US7978516B2 (en) * 2007-12-27 2011-07-12 Pliant Technology, Inc. Flash memory controller having reduced pinout
US8365041B2 (en) 2010-03-17 2013-01-29 Sandisk Enterprise Ip Llc MLC self-raid flash data protection scheme
US8909982B2 (en) 2011-06-19 2014-12-09 Sandisk Enterprise Ip Llc System and method for detecting copyback programming problems
US8910020B2 (en) 2011-06-19 2014-12-09 Sandisk Enterprise Ip Llc Intelligent bit recovery for flash memory
US8527467B2 (en) * 2011-06-30 2013-09-03 International Business Machines Corporation Compression-aware data storage tiering
US8589543B2 (en) * 2011-07-01 2013-11-19 Cisco Technology, Inc. Virtual data center monitoring
US9058289B2 (en) 2011-11-07 2015-06-16 Sandisk Enterprise Ip Llc Soft information generation for memory systems
US8924815B2 (en) 2011-11-18 2014-12-30 Sandisk Enterprise Ip Llc Systems, methods and devices for decoding codewords having multiple parity segments
US8954822B2 (en) 2011-11-18 2015-02-10 Sandisk Enterprise Ip Llc Data encoder and decoder using memory-specific parity-check matrix
US9048876B2 (en) 2011-11-18 2015-06-02 Sandisk Enterprise Ip Llc Systems, methods and devices for multi-tiered error correction
US9699263B1 (en) 2012-08-17 2017-07-04 Sandisk Technologies Llc. Automatic read and write acceleration of data accessed by virtual machines
US9501398B2 (en) 2012-12-26 2016-11-22 Sandisk Technologies Llc Persistent storage device with NVRAM for staging writes
US9612948B2 (en) 2012-12-27 2017-04-04 Sandisk Technologies Llc Reads and writes between a contiguous data block and noncontiguous sets of logical address blocks in a persistent storage device
US9239751B1 (en) 2012-12-27 2016-01-19 Sandisk Enterprise Ip Llc Compressing data from multiple reads for error control management in memory systems
US9454420B1 (en) 2012-12-31 2016-09-27 Sandisk Technologies Llc Method and system of reading threshold voltage equalization
US9003264B1 (en) 2012-12-31 2015-04-07 Sandisk Enterprise Ip Llc Systems, methods, and devices for multi-dimensional flash RAID data protection
US8922414B2 (en) 2013-02-12 2014-12-30 Cortica, Ltd. Multi-layer system for symbol-space based compression of patterns
US9214965B2 (en) 2013-02-20 2015-12-15 Sandisk Enterprise Ip Llc Method and system for improving data integrity in non-volatile storage
US9329928B2 (en) 2013-02-20 2016-05-03 Sandisk Enterprise IP LLC. Bandwidth optimization in a non-volatile memory system
US9870830B1 (en) 2013-03-14 2018-01-16 Sandisk Technologies Llc Optimal multilevel sensing for reading data from a storage medium
US9236886B1 (en) 2013-03-15 2016-01-12 Sandisk Enterprise Ip Llc Universal and reconfigurable QC-LDPC encoder
US9367246B2 (en) 2013-03-15 2016-06-14 Sandisk Technologies Inc. Performance optimization of data transfer for soft information generation
US9092350B1 (en) 2013-03-15 2015-07-28 Sandisk Enterprise Ip Llc Detection and handling of unbalanced errors in interleaved codewords
US9136877B1 (en) 2013-03-15 2015-09-15 Sandisk Enterprise Ip Llc Syndrome layered decoding for LDPC codes
US9244763B1 (en) 2013-03-15 2016-01-26 Sandisk Enterprise Ip Llc System and method for updating a reading threshold voltage based on symbol transition information
US9009576B1 (en) 2013-03-15 2015-04-14 Sandisk Enterprise Ip Llc Adaptive LLR based on syndrome weight
US9170941B2 (en) 2013-04-05 2015-10-27 Sandisk Enterprises IP LLC Data hardening in a storage system
US10049037B2 (en) 2013-04-05 2018-08-14 Sandisk Enterprise Ip Llc Data management in a storage system
US9159437B2 (en) 2013-06-11 2015-10-13 Sandisk Enterprise IP LLC. Device and method for resolving an LM flag issue
US9043517B1 (en) 2013-07-25 2015-05-26 Sandisk Enterprise Ip Llc Multipass programming in buffers implemented in non-volatile data storage systems
US9384126B1 (en) 2013-07-25 2016-07-05 Sandisk Technologies Inc. Methods and systems to avoid false negative results in bloom filters implemented in non-volatile data storage systems
US9524235B1 (en) 2013-07-25 2016-12-20 Sandisk Technologies Llc Local hash value generation in non-volatile data storage systems
US9639463B1 (en) 2013-08-26 2017-05-02 Sandisk Technologies Llc Heuristic aware garbage collection scheme in storage systems
US9361221B1 (en) 2013-08-26 2016-06-07 Sandisk Technologies Inc. Write amplification reduction through reliable writes during garbage collection
US9442670B2 (en) 2013-09-03 2016-09-13 Sandisk Technologies Llc Method and system for rebalancing data stored in flash memory devices
US9519577B2 (en) 2013-09-03 2016-12-13 Sandisk Technologies Llc Method and system for migrating data between flash memory devices
US9158349B2 (en) 2013-10-04 2015-10-13 Sandisk Enterprise Ip Llc System and method for heat dissipation
US9323637B2 (en) 2013-10-07 2016-04-26 Sandisk Enterprise Ip Llc Power sequencing and data hardening architecture
US9442662B2 (en) 2013-10-18 2016-09-13 Sandisk Technologies Llc Device and method for managing die groups
US9298608B2 (en) 2013-10-18 2016-03-29 Sandisk Enterprise Ip Llc Biasing for wear leveling in storage systems
US9436831B2 (en) 2013-10-30 2016-09-06 Sandisk Technologies Llc Secure erase in a memory device
US9263156B2 (en) 2013-11-07 2016-02-16 Sandisk Enterprise Ip Llc System and method for adjusting trip points within a storage device
US9244785B2 (en) 2013-11-13 2016-01-26 Sandisk Enterprise Ip Llc Simulated power failure and data hardening
US9152555B2 (en) 2013-11-15 2015-10-06 Sandisk Enterprise IP LLC. Data management with modular erase in a data storage system
US9703816B2 (en) 2013-11-19 2017-07-11 Sandisk Technologies Llc Method and system for forward reference logging in a persistent datastore
US9520197B2 (en) 2013-11-22 2016-12-13 Sandisk Technologies Llc Adaptive erase of a storage device
US9520162B2 (en) 2013-11-27 2016-12-13 Sandisk Technologies Llc DIMM device controller supervisor
US9280429B2 (en) 2013-11-27 2016-03-08 Sandisk Enterprise Ip Llc Power fail latching based on monitoring multiple power supply voltages in a storage device
US9122636B2 (en) 2013-11-27 2015-09-01 Sandisk Enterprise Ip Llc Hard power fail architecture
US9582058B2 (en) 2013-11-29 2017-02-28 Sandisk Technologies Llc Power inrush management of storage devices
US9250676B2 (en) 2013-11-29 2016-02-02 Sandisk Enterprise Ip Llc Power failure architecture and verification
US9092370B2 (en) 2013-12-03 2015-07-28 Sandisk Enterprise Ip Llc Power failure tolerant cryptographic erase
US9235245B2 (en) 2013-12-04 2016-01-12 Sandisk Enterprise Ip Llc Startup performance and power isolation
US9129665B2 (en) 2013-12-17 2015-09-08 Sandisk Enterprise Ip Llc Dynamic brownout adjustment in a storage device
US9549457B2 (en) 2014-02-12 2017-01-17 Sandisk Technologies Llc System and method for redirecting airflow across an electronic assembly
US9497889B2 (en) 2014-02-27 2016-11-15 Sandisk Technologies Llc Heat dissipation for substrate assemblies
US9703636B2 (en) 2014-03-01 2017-07-11 Sandisk Technologies Llc Firmware reversion trigger and control
US9485851B2 (en) 2014-03-14 2016-11-01 Sandisk Technologies Llc Thermal tube assembly structures
US9348377B2 (en) 2014-03-14 2016-05-24 Sandisk Enterprise Ip Llc Thermal isolation techniques
US9519319B2 (en) 2014-03-14 2016-12-13 Sandisk Technologies Llc Self-supporting thermal tube structure for electronic assemblies
US9448876B2 (en) 2014-03-19 2016-09-20 Sandisk Technologies Llc Fault detection and prediction in storage devices
US9454448B2 (en) 2014-03-19 2016-09-27 Sandisk Technologies Llc Fault testing in storage devices
US9390814B2 (en) 2014-03-19 2016-07-12 Sandisk Technologies Llc Fault detection and prediction for data storage elements
US9390021B2 (en) 2014-03-31 2016-07-12 Sandisk Technologies Llc Efficient cache utilization in a tiered data structure
US9626400B2 (en) 2014-03-31 2017-04-18 Sandisk Technologies Llc Compaction of information in tiered data structure
US9626399B2 (en) 2014-03-31 2017-04-18 Sandisk Technologies Llc Conditional updates for reducing frequency of data modification operations
US9697267B2 (en) 2014-04-03 2017-07-04 Sandisk Technologies Llc Methods and systems for performing efficient snapshots in tiered data structures
US10114557B2 (en) 2014-05-30 2018-10-30 Sandisk Technologies Llc Identification of hot regions to enhance performance and endurance of a non-volatile storage device
US8891303B1 (en) 2014-05-30 2014-11-18 Sandisk Technologies Inc. Method and system for dynamic word line based configuration of a three-dimensional memory device
US10656842B2 (en) 2014-05-30 2020-05-19 Sandisk Technologies Llc Using history of I/O sizes and I/O sequences to trigger coalesced writes in a non-volatile storage device
US9703491B2 (en) 2014-05-30 2017-07-11 Sandisk Technologies Llc Using history of unaligned writes to cache data and avoid read-modify-writes in a non-volatile storage device
US9070481B1 (en) 2014-05-30 2015-06-30 Sandisk Technologies Inc. Internal current measurement for age measurements
US10146448B2 (en) 2014-05-30 2018-12-04 Sandisk Technologies Llc Using history of I/O sequences to trigger cached read ahead in a non-volatile storage device
US10372613B2 (en) 2014-05-30 2019-08-06 Sandisk Technologies Llc Using sub-region I/O history to cache repeatedly accessed sub-regions in a non-volatile storage device
US9093160B1 (en) 2014-05-30 2015-07-28 Sandisk Technologies Inc. Methods and systems for staggered memory operations
US10656840B2 (en) 2014-05-30 2020-05-19 Sandisk Technologies Llc Real-time I/O pattern recognition to enhance performance and endurance of a storage device
US9645749B2 (en) 2014-05-30 2017-05-09 Sandisk Technologies Llc Method and system for recharacterizing the storage density of a memory device or a portion thereof
US10162748B2 (en) 2014-05-30 2018-12-25 Sandisk Technologies Llc Prioritizing garbage collection and block allocation based on I/O history for logical address regions
US9652381B2 (en) 2014-06-19 2017-05-16 Sandisk Technologies Llc Sub-block garbage collection
US9443601B2 (en) 2014-09-08 2016-09-13 Sandisk Technologies Llc Holdup capacitor energy harvesting
US12135643B2 (en) 2020-11-12 2024-11-05 Intel Corporation Sequestered memory for selective storage of metadata corresponding to cached data
US12461685B2 (en) * 2022-04-07 2025-11-04 Micron Technology, Inc. Storage system with multiple data paths depending on data classifications

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4207609A (en) * 1978-05-08 1980-06-10 International Business Machines Corporation Method and means for path independent device reservation and reconnection in a multi-CPU and shared device access system
US4916605A (en) * 1984-03-27 1990-04-10 International Business Machines Corporation Fast write operations
US4947447A (en) * 1986-04-24 1990-08-07 Hitachi, Ltd. Method for data coding
US4914656A (en) * 1988-06-28 1990-04-03 Storage Technology Corporation Disk drive memory
US5237675A (en) * 1990-06-04 1993-08-17 Maxtor Corporation Apparatus and method for efficient organization of compressed data on a hard disk utilizing an estimated compression factor
US5247638A (en) * 1990-06-18 1993-09-21 Storage Technology Corporation Apparatus for compressing data in a dynamically mapped virtual data storage subsystem
US5237460A (en) * 1990-12-14 1993-08-17 Ceram, Inc. Storage of compressed data on random access storage devices
US5305295A (en) * 1992-06-29 1994-04-19 Apple Computer, Inc. Efficient method and apparatus for access and storage of compressed data

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2015097739A1 (ja) * 2013-12-24 2015-07-02 株式会社日立製作所 ストレージ装置及びその制御方法
US10452614B2 (en) 2015-06-12 2019-10-22 International Business Machines Corporation Storage data reduction analysis and forecast

Also Published As

Publication number Publication date
US5666114A (en) 1997-09-09

Similar Documents

Publication Publication Date Title
JPH08234921A (ja) アドレス・スペースを管理するための方法及び記憶サブシステム
JP3371044B2 (ja) ディスクアレイのための領域割り当て方法およびディスクアレイアクセス方法
US11048415B1 (en) Transaction-based storage system and method that uses variable sized objects to store data
US8131969B2 (en) Updating system configuration information
US7610434B2 (en) File recording apparatus
JP2846839B2 (ja) データ記憶システム及び関連する方法
US7120767B2 (en) Snapshot creating method and apparatus
US8131927B2 (en) Fast accessible compressed thin provisioning volume
JP5347061B2 (ja) フラッシュメモリデータストレージデバイスにデータを格納するための方法及び装置
JP7794381B2 (ja) データ圧縮方法及び装置
EP1265152B1 (en) Virtual file system for dynamically-generated web pages
US6205529B1 (en) Method and apparatus for defragmenting a storage device using a copy function in the device control logic
US7415653B1 (en) Method and apparatus for vectored block-level checksum for file system data integrity
KR100317691B1 (ko) 로그 구조화 목표 저장장치를 사전에 구성하여 볼륨을 효율적으로 복사하는 방법 및 장치
JPH06259197A (ja) アレイ型ディスクシステムの制御方式
US7584229B2 (en) Method and system for priority-based allocation in a storage pool
US11875051B2 (en) Contiguous data storage using group identifiers
US20060218347A1 (en) Memory card
US8209513B2 (en) Data processing system with application-controlled allocation of file storage space
CN1573747A (zh) 阴影分页
US7376758B2 (en) I/O dependency graphs
US7424574B1 (en) Method and apparatus for dynamic striping
US20070106865A1 (en) Method and system for using a block allocation policy
US20070106868A1 (en) Method and system for latency-directed block allocation
Hwang et al. {Z-LFS}: A Zoned Namespace-tailored Log-structured File System for Commodity Small-zone {ZNS}{SSDs}