United States Patent
`
`[191
`
`[11] Patent Number:
`
`5,034,914
`
`[45} Date of Patent:
`Jul. 23, 1991
`Osterlund
`______________________..________—————————————-———
`
`4,562,577 12/1935 Glover 371/38
`4,587,643
`5/1986 Monea
`369/32
`4,633,393 12/1986 Rundell ..
`364/200
`4,680,653
`7/1987 Ng ........ ..
`..360/72.2
`4,682,318
`7/1987 Busby . . . . . .. ..
`. . . .. 369/59
`4,775,969 10/1988 Ostcrlund ......
`369/53
`4,791,623 12/1988 Deiotte
`369/59
`
`
`
`OTHER PUBLICATIONS
`
`Jaworski, “Lasers Anticipate Mass (Storage) Appeal",
`Hardcapy Magazine, Feb. I 986. pp. 43-49.
`Freeman, Jr., “Optical Recording Comes of Age",
`Mini-Micro Systems, Apr. 1985, pp. 65, 66 & 69.
`
`(List continues on next page.)
`
`Primary Examiner—Michael R. Fleming
`Assistant Examiner—Gopal C. Ray
`Attorney, Agent. or Firm—Pennie & Edmonds
`
`[57]
`
`ABSTRACT
`
`An optical disk data storage system and method are
`disclosed. In a data storage or “write” operation, up to
`a fixed number of variable-length records are written to
`the optical disk in close proximity to an embedded di»
`rectory, which stores record length information de-
`scribing the records associated therewith. A high-level
`directory is constructed providing a list of addresses for
`the embedded directories. The embedded directories
`comprise up to a fixed maximum number of entries each
`indicating the length in bytes of a corresponding record.
`In a data retrieval or “read” operation, the high-level
`directory is first accessed to determine the addresses for
`the embedded directories, with reference to positional
`information permanently written to the disk. Bytes of
`data are then counted in accordance with the record
`length stored by the embedded directory to access the
`record sought by the host computer. In this way, vary-
`ingdength records can be efficiently stored on an opti-
`cal disk divided into fixed-length data storage sectors.
`All data is buffered in random access memory during
`both read and write data transfer operations.
`
`30 Claims, 9 Drawing Sheets
`
`[54]
`
`OPTICAL DISK DATA STORAGE METHOD
`AND APPARATUS WITH BUFFERED
`INTERFACE
`
`[75]
`
`Inventor:
`
`Steven W. Osterlund, North
`Kingstown, R.I.
`
`[73]
`
`Assignee: Aquidneck Systems, International,
`Inc., North Kingstown, R.I.
`
`l2 1]
`
`Appl. No.: 207,590
`
`[22]
`
`Filed:
`
`Jun. 16, 1988
`
`Related US. Application Data
`
`Continuation-impart of Ser. No. 037,749, Apr. 13,
`1987. Pat. No. 4,775,969, which is a continuation-in-
`part of Ser. No. 863,564, May 15, 1986, abandoned.
`Int. c1.s ..................... .. G06F 13/00; G1 113 7/013
`11.5. C1. ............................. .. 364/900; 364/952.31;
`364/9393; 364/952.1; 360/722; 360/48;
`369/32; 369/59
`Field of Search .............. .. 364/200, 900 MS File;
`369/116, 59, 60, 32, 272; 365/234; 360/722, 48,71
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`
`
`364/200
`9/1968 Andahl ......................
`3,400,371
`.. 364/200
`9/1968 Beausoleil ..
`3,400,372
`364/200
`3,629,860 12/1971 Capozzi
`360/48
`4,001,883
`1/1977 Strout .............. .,
`.. 360/722
`4,089,027
`5/1978 Grigoletti .... ..
`. .. . .. 365/234
`4,094,013
`6/1978 Hill et al.
`.. . . . .
`369/48
`4,229,808 10/1980 Hui
`364/200
`4,310,883
`1/1982 Clifton et al.
`.. . . .. 360/722
`4,321,635
`3/1982 Tsuyuguchi . . . . ..
`....... .. 360/71
`4,398,227
`8/1983 Anderson
`....... 364/200
`4,467,421
`8/1984 White
`. . . . . . . .. 369/32
`4,486,870 12/1984 Pettigrew . . . . . .
`....... 358/296
`4,490,747 12/1984 Yokoyama
`. . . . . . ... 360/13
`4,496,997
`1/1985 Ohtsuki . . . . . . .. .
`360/7304
`4,531,166 7/1985 Anderson ..
`369/275
`4,535,439
`8/1985 Satoh
`360/15
`4,541,019 9/1985 Precourt
`10/1985 Satoh ................................... .. 369/32
`4,545,044
`
`[63]
`
`[51]
`[521
`
`[5 3]
`
`[56]
`
`22
`
`23
`
`|
`
`24
`
`
`
`OPTICAL
`01 SK
`SYSTEM
`
`
`
`
`RAM
`
`BUFFER
`
`MEMORY
`
`
`
`MICROPRUCESSOR
`
`NetApp
`
`Exhibit1005
`
`Page1
`
`NetApp Exhibit 1005 Page 1
`
`

`

`Page 2
`
`5,034,914
`
`Warren, “Optical Storage Shines on the Horizon", Min-
`ni-Micro Systems, Dec. 1985, pp. 68-70, 73, 74, 75, 76,
`79 & 80.
`
`Welch, “A New Stab At Data Storage", Venture, Feb.
`1986, pp. 66, 68 & 70.
`Meng, “Optical Disks Slip On Compatibility”, Digital
`Design. Jan. 1986, pp. 28, 29, 32, 34, 36 & 37.
`Tucker, “Mass Storage Goes Optical”, Advanced Imag-
`ing. Nov. 1986, pp. Al9—A24.
`Rathmann. "Dynamic Data Structures 0n Optical
`Disks”, Computer Science Department, Stanford Uni-
`versity, pp. 175-180.
`Fujitani, “Laser Optical Disk: The Coming Revolution
`
`In On-Line Storage", Communications of the ACM,
`Jun. 1984, pp. 546-554.
`Warren, “Software Tools, Utility Drive Optical Disks",
`Mini-Micro Systems, Dec. 1986, pp. 33, 34, 37, 40, 43 8t
`44.
`
`Rothchild, “Optical Storage Moves Closer To Main-
`frames", Computerworld. May 7, 1984.
`Rothchild,
`“CD—ROM and Write-Once Optical
`Storage-Right Nowl”, Optical Memory News. Jul—Aug.
`1985.
`M. J. Mitchell, Jr., “Diskette Load/Dump Control",
`IBM Technical Disclosure Bulletin, vol. 20, No. 4, Sep.
`1977, pp. 1359—1361.
`
`NetApp
`
`Exhibit1005
`
`Page2
`
`NetApp Exhibit 1005 Page 2
`
`

`

`
`
`US. Patent
`
`July 23, 1991
`
`Sheet 1 of 9
`
`5,034,914
`
`4<o_pmo
`
`gm.e
`
`Eupm»m
`
` mowmuoommozo_z
`
`
`pmoz
`
`zmp=mzoo
`
`
`
`NetApp
`
`Exhibit 1005
`
`Page 3
`
`NetApp Exhibit 1005 Page 3
`
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 2 of 9
`
`5,034,914
`
`HIGH LEVEL DIRECTORY GROW TOWARD
`THE INSIDE OF DISK. STARTS AT THE
`HIGHEST AODRESSED DISK BLOCK.
`
`OPTICAL DISK
`
`DATA, EMBEDDED DIRECTORY BLOCK AND
`FRAGMENTATION MAP GROW TOWARDS THE
`OUTSIDE OF THE DISK.
`
`24-1
`
`Fig. 2
`
`NetApp
`
`Exhibit1005
`
`Page4
`
`NetApp Exhibit 1005 Page 4
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 3 of 9
`
`5,034,914
`
`PHYSICAL LAYOUT OF MAPPING OF DATA, DIRECTORIES
`AND FRAGMENTAHON MAP 0N DISK
`
`PERIPHERY
`
`0F DISK
`
`HIGHEST DISK ._..
`BLOCK ADDRESS
`
`:}>LOGICAL(HIGH LEVEL) DIRECTORY
`
`. DISK TRACK(S)
`
`f
`
`DISK SPACE FOR ADDHIONAL
`
`DATA SEGMENTSIRECORDSI
`
`OF DATA SEGMENT 1
`
`BAD BLOCK FRAGMENTATION MAP
`
`EMBEDDED DIRECTORY ENTRY
`OF DATA SEGMENT I
`
`
`Mafiaflflhafi BAD
`
`
`7".V.‘.'.'.‘..‘.;."
`
`DATA SEGMENT I
`
`BLOCKISI
`
`
`
`EMBEDDED DIRECTORY
`or DATA SEGMENT D
`
`DATA SEGMENT O
`
`LOWEST msx BLOCK ADDRESS
`
`CENTER
`OF DISK
`
`‘
`
`Fig." 3
`
`NetApp
`
`Exhibit1005
`
`Page5
`
`NetApp Exhibit 1005 Page 5
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 4 of 9 '
`
`5,034,914
`
`EMBEDDED DIRECTORY
`
`IDENTIFIES THE RELATIVE POSITION OF
`THIS SEGMENT WITHIN THE TAPE IMAGE
`PUT OUT BY COMPUTER
`NUMBER OF RECORDS CONTAINED WITHIN
`TMIS DATA SEOMENT
`
`NUMBER OF TIMES TMIs SEOMENT WAS
`
`BROKEN BY BAD DATA BLOCK SECTIONS
`
`BYTE D OF RECORD O (8 DOS TO BYTE)
`STARTS AT THE BEGINNING OF THIS
`BLOCK ON THE DISK
`
`LENGTH OF EACH OF SOD RECORDS
`
`LOWEST ADDRESS-
`
`
`
`
`
`NUMBER OF
`ENTRIES
`
`NUMBER OF
`
`ERROEMENTETQION
`
` DIRECTORY
`
`
`
`
`
`
`
`STARTING DISK
`BLOCK ADDRESS
`OF DATA
`
`
`
`LENGTH
`ENTRY D
`
`LENGTH
`ENTRYI
`
`
`
`
`
`HIGHEST
`ADDRESS —_-
`
`LENGTH OF
`ENTRY 499
`
`Fig. 4
`
`NetApp
`
`Exhibit1005
`
`Page6
`
`NetApp Exhibit 1005 Page 6
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 5 of 9
`
`5,034,914
`
`FRAGMENTATION BLOCK
`(ONLY PRESENT IF NUMBER OF FRAGMENTATION ENTRIES FIELD
`IN PRECEDING EMBEDDED DIRECTORY IS NON-ZERO)
`
`
`
`COOO
`BLOCKS
`
`' BAD
`BLOCKS
`
`GOOD
`BLOCKS
`
`BAD
`BLOCKS
`
`
`
`RELATIVE TO START
`BLOCK OF DATA
`
`RELATIVE TO END OF PREVIOUS
`STRETCH 0F COOO BLOCKS
`
`RELATIVE TO END OF PREVIOUS
`STRETCH OF BAD BLOCKS
`
`RELATIVE TO END OF PREVIOUS
`STRETCH OF GOOD BLOCKS
`
`
`
`
`
`
`A BLOCK ON DISK EOUALS AT LEAST I024 BYTES
`OF 8 BITS EACH
`
`NOTE:
`
`SEOUENCES OF BLOCKS THAT ARE LONGER THAN FFFFHEX
`CAN BE EXPRESSED BY CONTINUING THE COUNT AN
`ADDITIONAL ENTRY AND PUTTING A ZERO IN THE
`COMPLEMENTARY FIELD OF THAT ENTRY
`
`IFTTigy'.
`
`.55
`
`NetApp
`
`Exhibit1005
`
`Page7
`
`NetApp Exhibit 1005 Page 7
`
`

`

`US. Patent
`
`July 23, 1991 .
`
`Sheet 6 of 9
`
`5,034,914
`
`W}
`
`APPEND RECORD DATA
`TO DATA ALREADY IN
`BUFFER MEMORY
`
`EMBEDDED DIRECTORY
`CONSTRUCTION FLOWCHART
`
`ROOM LEFT IN
`BUFFER FOR MAXIMUM
`RECORD LENGTH?
`
`NO
`
`
`
`MARK END OF BUFFER
`AT EVEN MULTIPLE OF
`DISK' BLOCK LENGTH
`
` TRANSFER REMAINDER
`
`DATA TO BEGINNING
`OF BUFFER MEMORY
`
`MINIMUM OPTICAL
`DISK WRITE LENGTH
`OF DATA IN BUFFER
`MEMORY
`
`YES
`
`WRITE ONE WRITE
`LENGTH OF DATA
`TO DISK
`
`
`WRITE REMAINING DATA
` MAXIMUM NUMBER OF
`
`IN BUFFER TO DISK
`RECORD LENGTHS IN
`
`TEMPORARY EMBEDDED
`DIRECTORY ENTRY OR
`
`
`WRITE EMBEDDED DIRECTORY
`OPERATOR CONTROLLED
`
`DISMOUNT?
`ENTRY TO BLOCK IMMEDIATELY
`FOLLOWING DATA
`
`ADD ADDRESS OF EMBEDDED
`DIRECTORY TO HIGH LEVEL
`DIRECTORY IN BUFFER
`
`
`
`BAO BLOCK
`FRAGMENTATION
`MAP REQUIRED
`
`YES
`WRITE BAD BLOCK FRAGMENTATION
`
`MAP TO BLOCK FOLLOWING
`EMBEDDED DIRECTORY ENTRY
`
`
`
`‘
`
`Fig. 6'
`
`NetApp
`
`Exhibit1005
`
`Page8
`
`NetApp Exhibit 1005 Page 8
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 7 of 9
`
`5,034,914
`
`INSTRUCHDN FROM
`OPTICAL DISK SYSTEM
`DRIVE 24
`
`
`
`BAD BLOCK FRAGMENTATION
`MAP CONSTRUCTION
`FLOWCHART
`
` PREVIOUS
`
`WRRE
`SUCCESSFUL?
`
`
`WRHE
`SUCCESSFUL?
`
`
`
`
`INCREMENT
`INCREMENT
`PREVIOUS
`POINTER TO COOD
`POINTER TO BAD
`WRITE
`BLOCK FIELD OF
`BAD?
`BLOCK HELD OF
`
`
`NEXT ENTRY
`
`CURRENT ENTRY
`
`
`
`
`
`
`
`
`
`
`ADD BLOCKS
`USED TO CURRENT
`FIELD OF ENTRY
`
`
`
`
`
`
`NOTE:
`
`
`INCREMENT
`
`
`
`EULQPI3§
`POINTER To
`L?
`SAME HELD 0E
`
`FIELD.
`NEXT ENTRY
`
`
`
`
`
`
` PLACE
`DVERFLOW
`
`INNEW HELD.
`
`
`POINTERIN MEMORYIS TO
`KEEP TRACK OF POSHION
`
`IN THE FRAGMENTATION MAP
`
`NetApp
`
`Exhibit1005
`
`Page9
`
`NetApp Exhibit 1005 Page 9
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 8 of 9
`
`5,034,914
`
`READ OPERATIONS
`FLOWCHART
`
`m INSTRUCTION FROM
`HOST INTERFACE _ZQ
`
`DESIRED RECORD
`DATA IN BUFFER
`MEMORY?
`
`*
`
`
`
`CALCULATE PORTIONS OF
`N0
`DATA SECMENT TMAT
`
`INCLUDES DESIRED
`RECORD DATA
`
`
`
`
`
`NUMBER OF BAD
`BLOCK ENTRIES
`YES
`
`IN CURRENT DATA
`SECMENT MDT
`
`EDUAL fl ?
`
`‘ RETRIEVE RECDRD
`LENCTH FROM
`CURRENT EMBEDDED
`DIRECTORY ENTRY
`
`
`
`
`
`
`
`‘
`
`CALCULATE BUFFER
`ADDRESS OF
`mmmDMA
`
`TRANSFER RECORD
`DATA TO HOST
`COMPUTER I9
`
`
`
`
`
`
`FILL BUFFER MEMORY
`WITH PORTION OF
`DATA SEGMENT
`
`
`
`
`
`
`
`
`
`
`BOX A
`
`FILL BUFFER MEMORY
`WITH PORTION OF DATA
`SEGMENT USING BAD
`BLOCK MAP INFORMATION
`
`NetApp
`
`Exhibit 1005
`
`Page 10
`
`NetApp Exhibit 1005 Page 10
`
`

`

`US. Patent
`
`July 23, 1991
`
`Sheet 9 of 9
`
`5,034,914
`
`BAD BLOCK FRAGMENTATION MAP INTERPRETATION
`DURING DISK READOUT
`
`FLOW CHART
`
`
`
`
`
`ADD BAD BLOCK
`FIELD TO STARTING
`BLOCK ADDRESS
`
`
`
`
`
`GOOD
`BLOCK FIELD
`EOUALS O?
`
`
`
`INCREMENT POINTER
`TO NEXT GOOD/BAD
`
`BLOCK ENTRY
`
`
`
`READ
`CONSECUTIVE
`GOOD BLOCKS
`
`
`
`
`
`
`ADD GOOD BLOCK
`FIELD TD STARTING
`
`BLOCK ADDRESS
`
`
` DESIRED NUMBER
`
`
`
`OF BLOCKS READ
`TO FILL MEMORY?
`
`
`NetApp
`
`Exhibit 1005
`
`Page 11
`
`NetApp Exhibit 1005 Page 11
`
`

`

`1
`
`5,034,914
`
`OPTICAL DISK DATA STORAGE METHOD AND
`APPARATUS WITH BUFFERED INTERFACE
`
`PRIOR APPLICATIONS
`
`This is a continuation-in-part of US. Pat. Application
`Ser. No. 37,749, filed Apr. 13, 1987, now U. S. Pat. No.
`4,775,969, which was a continuation~in-part of Ser. No.
`863,564, filed May 15, 1986, and now abandoned.
`
`IO
`
`BACKGROUND OF THE INVENTION
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`This invention is directed to optical disk storage sys-
`tems and is more particularly directed to a new and
`improved embedded directory technique for storing
`data on an optical disk to permit rapid access thereto.
`For general information concerning the field of opti-
`cal data storage and the associated hardware, reference
`may be made to the following articles:
`(I) May 7, 1984 edition, Computerwarld, article enti-
`tled “Optical Storage Moves Closer to Mainframes";
`(2) April, 1985 edition, Mini Micro Systems, article
`entitled “Optical Recording Comes of Age"; and
`(3) December, 1985 edition. Mini Micro Systems, arti-
`cle entitled “Optical Storage Shines on the Horizon”
`One object of this invention is to efficiently soive the
`specific problems associated with using an optical disk
`storage system to emulate a magnetic tape storage sys-
`tem in a “plug-compatible" manner. Numerous prob-
`lems are encountered in such an effort. due both to the
`differing natures of the media and to the data organiza-
`tion practices which have become customary in tape
`storage applications.
`More particularly, as conventionally implemented, a
`single reel of magnetic tape is commonly used to store a
`single “file” of data, that is, an entire data set pertaining
`to a particular subject, e.g., a payroll file, an employee
`file or the like. Within each file, the data is typically
`divided into "records", the length of which is not fixed.
`For example, each record may relate to a particular
`employee. Normally each record in the file is set off on
`the tape by “preamble” and “postamble” indicators of
`specified format; successive records are separated by
`“inter-record" gaps.
`In some cases, a single reel of tape may store several
`files, that is, several data sets accessed separately by an 45
`application program running on a host computer. If
`plural files are stored on a single tape, they may be
`divided by “file marks", as discussed below; however,
`the presence of a file mark does not indicate the end of
`a file per se. For the purposes of the present invention,
`it is immaterial whether one or several files are stored
`on a single reel of tape.
`Typically, data is written to the tape record-by-
`record under direct control of a host computer. When
`the host subsequently desires to retrieve one of the
`records, it first directs that a particular tape be mounted,
`that is. so that the single file typically found on each reel
`of tape can be accessed. The host then directs the tape
`drive to obtain access to the “next” record. In response
`to such a command, the tape drive will typically read
`the next record into a random-access memory or other
`buffer for subsequently supplying it to the host; less
`sophisticated drives may simply advance the tape to a
`point corresponding to the beginning of the next record.
`If the host is not interested in a particular record, it
`directs instead that the next record be accessed, and so
`on. Thus, if the host in fact needs access to the two
`hundredth record on the tape, 200 such "next record” I
`
`50
`
`55
`
`65
`
`2
`instructions must be forwarded from the host to the tape
`drive and executed. Obviously, ihis is very time con-
`suming. Normally, of course.
`the intrinsic sequential
`nature of tape storage is turned to advantage by use of
`tape in connection with programs (e.g. payroll process-
`ing) in which the records can conveniently be accessed
`in sequence, one by one.
`In order to partially alleviate this problem, it is con-
`ventional for the host computer to direct that a so cailed
`“file mark", consisting of 'a predetermined sequence of
`bits, be written to the tape from time to time, that is, at
`unspecified intervals between records. If the host de-
`sires to skip over a portion of the tape, it can then direct
`that the tape be advanced to the next file mark. The
`drive can advance the tape until it detects the unique file
`mark sequence. If the host "knows" that the record of
`interest is between the second and third file marks, for
`example, it can direct that the tape advance to the first
`file mark, and when this has been done, to the second
`file mark; the host can then direct that the tape succes-
`sively read individual records, as above. Again,
`this
`process is relatively cumbersome and time consuming.
`.As indicated above, one object of this invention is the
`emulation of a tape drive using optical disk storage
`media. It is important that the optical disk according to
`the invention be “plug-compatible” with a tape drive;
`that is, the optical drive according to the invention must
`be connected to a host computer precisely as is a con-
`ventional tape drive. In this way, the optical disk can be
`employed without requiring any modification to the
`host operation or, application software. Clearly,
`in
`order to do so the optical drive must respond to all of
`the commands which are conventionally directed to
`tape drives, as outlined above, and in order to be attrac-
`tive to users must pr0vide a substantial performance
`advantage.
`At present, all optical disk media of which the present
`inventor is aware define a single spiral "track", al-
`though concentric tracks could also be employed. Radi-
`ally-extending “hard sectors", provided at manufacture,
`are spaced circumferentially around the disk and divide
`the spiral track into “sectors”. Typically 1,024 bytes per
`sector may be stored on each track. The optical drive is
`provided with a controller operable so that its read/-
`write head can access the disk at the beginning of any
`sector; hence reading and writing operations can begin
`at a number of “sector locations" equal to the number of
`the hard sectors on the disk (on the order of 32) times
`the number of the essentially concentric rings (on the
`order of 32,000) made by the Spiral track.
`One way of writing varying-length tape-type records
`to an optical disk would be to start each individual
`record at a sector location. In that way, whenever the
`host directed that the next record be accessed, the opti-
`cal disk could simply begin reading at the subsequent
`sector. However, many tape record entries are very
`short, e.g., a single byte may be written as a record. In
`such cases, essentially the entire storage capacity repre-
`sented by the sector would be wasted.
`It will be recognized, of course, that magnetic disk
`storage is also extremely popular. Magnetic disks are
`also typically divided into sectors, but use concentric
`rather then spiral tracks. It might be considered that
`magnetic disk storage techniques could be usefully ap-
`plied to optical disk storage. However, this actually is
`not the case due to the varying characteristics of mag-
`
`NetApp
`
`Exhibit1005
`
`Page12
`
`NetApp Exhibit 1005 Page 12
`
`

`

`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`5
`
`3
`netic and optical storage systems, for the following
`reasons.
`Conventionally, for a disk of given size, an optical
`disk can store up to ten times as much data as can a
`magnetic disk. However, a magnetic disk can be repeti~
`tively erased and rerecorded, such that if the contents of
`a given file change overtime, the obsolete data is simply
`erased and rewritten. This cannot be done with present-
`day commercially-available optical disk media and stor-
`age systems, which do not allow erasure.
`is
`Erasing of obsolete blocks of data,
`incidentally,
`typically not practiced on tape, although erasing itself is
`readily accomplished. Instead, the new data is simply
`written to the end of the tape and a record is maintained
`(e.g. by the application program) indicating which data
`blocks are current and which are obsolete, such that
`those which are obsolete are simply ignored. This is
`preferred because the time consumed in rewinding the
`tape to the location of the obsolete record, record-by-
`record, as discussed - is more costly than simply using a
`new section of tape. An exception to this practice is
`discussed below.
`Another important distinction between optical and
`magnetic disk storage is that the average “head seek"
`time required by state of the art magnetic read/write
`heads to move radially in order to access various por-
`tions of the disk is much shorter than that of the compa-
`rable optical disk read/write head units. This is simply
`because the magnetic read/write head assembly of a
`magnetic disk is typically less massive than the laser
`read/write head assembly associated with an optical
`disk. The magnetic head assembly can therefore be
`moved much more quickly to a given area of the disk
`for a read/write operation than can an optical head»
`assembly. Accordingly, it is desired to provide a mem-
`ory structure and organization for an optical disk in
`which head seeks are minimized insofar as possible.
`The fact that magnetic disks allow repeated erasure
`of and rapid access to varying points of the disk has
`caused disk memory organization practices to develop
`substantially differently from those employed in con-
`nection with tape storage. As indicated above, on a
`given tape a single file comprising a number of individ-
`ual “records” is normally stored, and a host computer
`accesses the file record-by-record, that is, sequentially.
`On a magnetic disk, by comparison, data is typically
`accessed only file-by-file. For example, the entire pay-
`roll file might be read from a disk into a host computer
`for processing in a single operation. Where a particular
`file extends beyond a particular sector (the beginning
`points of the sectors again being the only points at
`which the magnetic disk can accurately be addressed a
`directory also stored on the magnetic disk provides a
`"map" according to which the read/write head can
`then "jump" from the end of that sector to the begin-
`ning of the sector at which the next portion of the file is
`stored. Typically, this can be accomplished sufficiently
`quickly that the host does'not experience a delay in
`accessing all of the file. Accordingly, even if an applica-
`tion program does not require all of the data contained
`in an entire file stored on a magnetic disk, but only a
`portion thereof, which might or might not correspond
`to a “recor " as stored on tape, it simply accesses the
`entire file from the disk and then selects the individual
`portion required therefrom when the data 'has been
`stored in the host.
`The above discussion serves to illustrate why the
`storage organization arrangements used for magnetic
`
`4
`tape and disk storage cannot appropriately be applied to
`optical disk storage, even where a particular sequential-
`ly-organized data set to be stored on the optical disk
`might otherwise have been suitable for storage on tape.
`Notably, the fact that tape records are conventionally
`accessed record-by-record means that it would be inap-
`propriate to assign an entire sector on the optical disk to
`each record; if the record were relatively short, most if
`not substantially all of the sector would be wasted. The
`variable-length tape records would rarely correspond
`to the fixed length of the sectors, such that incomplete
`usage would be very common.
`More specifically, note that data is stored on tape
`record-by-record because there is no alternative to
`doing so; on tape, there are no permanently-written
`equivalents of the hard sectors on the disk which can be
`used to provide indexing to a particular record, for
`example. File marks can be written, as described above,
`but as presently employed this is done only in response
`to specific host commands. Accordingly tape records
`must be delimited by preamble and postamble informa-
`tion, so that they can be reliably counted.
`Writing data to tape record-by-record does permit
`flexibility of record length. Media organized into blocks
`of fixed length, such as magnetic or optical disks, do not
`have this flexibility. Accordingly,
`to store tape-type
`records on media divided into fixed-length blocks (i.e.,
`either optical or magnetic disks) is complex.
`It
`is understood that at least in some tape systems
`variable-length records are also divided into fixed-
`length blocks for convenience in storage; see U.S. Pat.
`Nos. 4,398,227 and 4,531,166 to Anderson. However, if
`plug compatibility is to be retained, the blocks must be
`“transparent” to the host computer, and the random
`record length characteristic preserved. Hence this does
`not solve the problem noted above.
`U. S. Pat. No. 4,467,421 to White discloses one ap-
`proach to the storage of sequential, tape-type records
`on magnetic disks. However,
`this involves extensive
`reprogramming of the host computer, and is thus not
`appropriate in the plug-compatible environment pri-
`marily addressed by the present invention. Moreover,
`the White approach is directed principally to very large
`mainframe host computers.
`0n the other hand, to organize an optical disk in the
`way in which magnetic disks are normally organized
`would be highly inappropriate. Data stored on mag-
`netic disks is accessed file-by-file, with numerous “head
`seeks” between portions of the file stored in various
`sectors, as indicated. Such a scheme would be ineffi-
`cient in an optical disk system due to the relatively slow
`motion of current optical read/write head assemblies.
`In effect, in such case the sequential nature of the spiral
`track on an optical disk would not be employed gain-
`fully. Moreover, if an optical disk were to be configured
`to be functionally-compatible as well as plug-compati—
`ble with a magnetic disk, the fact that data stored on
`magnetic disks is frequently erased and overwritten
`would mean that numerous obsolete copies of large
`volumes of data would be stored on the optical disk,
`since no erasure is possible. This would rapidly fill up
`even the high capacity optical disk systems now avail-
`able. Further,
`to emulate a magnetic disk to a host
`would involve numerous difficulties with respect
`to
`plug-compatibility.
`'
`It would of course be possible to provide an interface
`scheme for mating a computer with an optical disk
`drive in. a manner designed to take advantage of the
`
`5,034,914
`
`45
`
`50
`
`55
`
`65
`
`NetApp
`
`Exhibit 1005
`
`Page 13
`
`NetApp Exhibit 1005 Page 13
`
`

`

`5,034,914
`
`5
`
`characteristics of the optical media. However, to do so
`in a manner such that the device was not plug-compati-
`ble with a class of existing storage devices would pre-
`vent the optical disk system from being useful with
`preexisting computer systems, limiting the market for
`the optical disk.
`Accordingly, it can be seen that a new way of record-
`ing data efficiently on an optical disk, while retaining
`plug-compatibility with a conventional magnetic data
`storage device, such as a tape drive, is needed.
`
`10
`
`BRIEF DESCRIPTION OF THIS INVENTION
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`This invention is directed to a new and improved
`method and apparatus for storing user or “customer”
`data, typically organized as a sequence of data records,
`and record structure data, that is, data describing the
`user data records, (all of which is hereinafter sometimes
`referred to as information) on an optical disk. Optical
`disks as constructed today comprise concentric tracks
`or a spiral track in which physical changes, e.g., bubbles
`are formed by a laser writing head to record informa-
`tion. The information is read out for example by mea-
`suring reflected light from the tracks.
`In the method and apparatus for storing data accord-
`ing to the invention, record structure data is generated
`based on the data records to be stored and is distributed
`on the disk so that it is in close physical proximity to the
`optical disk read/write head when it is needed.
`With this system and method. the optical disk is able
`to effectively emulate magnetic tape storage. The
`method of the invention also enables the optical disk to
`be used efficiently for storage of data not particularly
`directed to magnetic storage devices.
`According to the present invention, a high-level di-
`rectory is begun during initial writing of data to an
`optical disk. The high-level directory relates a file to a
`number of “embedded directories“ interspersed with
`the data on the disk, and written to the disk substantially
`simultaneously with the data. The “embedded directo-
`ries" each provide an index to a number of associated
`data records, all part of a single corresponding file. The
`fact that the embedded directories are interspersed with
`the data reduces the number of long “head seeks” re-
`quired to access a particular record. Preferably,
`the
`embedded directories are written to the disk immedi-
`ately following the data records to which they corre-
`spond. The hi gh—level directory is written to a predeter-
`mined location on the disk, so that it can be located
`reliably; entries are added to the high-level directory as
`data is written to the disk.
`In order to allow emulation by the optical disk of the
`record-by-record response of a tape drive to typical
`host commands, the embedded directories each contain
`a sequence of record length identifiers. Each record
`length identifier simply consists of a number equal to
`the number of bytes of a corresponding record having
`been written to the optical disk by the host. The records
`themselves are written contiguously; that is, the pream-
`ble and postam’ble and inter-record gaps found on tape
`are eliminated, such that very high density of data stor-
`age on the disk is achieved.
`In an exemplary embodiment each sector contains
`1,024 bytes of data. Each embedded directory occupies
`one sector; header and other information required to
`identify each embedded directory takes the first 24
`bytes of the sector. The remainder of the sector contain-
`ing the embedded directory consists of record length
`data. Each record length data item is assigned two bytes
`
`6
`in the embedded directory, such that each embedded
`directory is capable of containing 500 record length
`identifiers corresponding to 500 stored records.
`The sector address of each of the embedded directo-
`ries is stored in the high-level directory, and an identifi-
`cation of the file to which the records corresponding to
`each of the embedded directories belong is stored there-
`with. When a host subsequently requires access to a
`particular file, the optical disk storage control system
`accesses the high-level directory to determine the start-
`ing address of the first embedded directory correspond-
`ing to that file. When the host subsequently desires to
`read a particular record, the optical disk control system
`accesses the corresponding embedded directory—-
`which follows the data to which it corresponds-to
`determine the number of bytes of data preceding the
`particular record sought, starting from the sector after
`the preceding embedded directory, and the number of
`bytes of the particular record sought. The starting point
`of the particular record sought can then be located
`simply by counting out a number of bytes of data corre-
`sponding to the total length of the preceding records.
`The specific record sought can then be supplied by
`counting out a number of bytes of the copied data equal
`to the length of the record sought.
`In the preferred embodiment, the system of the inven-
`tion includes a random-access memory (RAM) buffer in
`which all data is stored during its transfer from the host
`to the optical disk, and vice versa. During a write oper-
`ation, while the records to be stored on the optical disk
`are stored in the RAM buffer, the embedded directory
`corresponding to a particular group of records is con-
`structed. When the embedded directory correSponding
`to the group of records has been constructed. it is stored
`on the optical disk following the corresponding re-
`cords. Similarly, during a read operation directed at a
`particular record, the embedded directory is first con—
`sulted to determine the number of bytes preceding the
`record sought. The bytes preceding a particular record
`sought by the host then are counted to locate the re-
`cord, after up to the entire group of records corre-
`Sponding to the embedded directory has been copied
`from the optical disk to the RAM buffer.
`As mentioned above,
`the host computer may also
`direct that file marks be written to the tape from time to
`time. According to the invention, file marks are written
`as zero-length records in the corresponding embedded
`directory. As noted,
`the locations of the embedded
`directories are stored in the high-level directory. When
`the host directs the tape to skip ahead to the next file
`mark, the entries in the embedded directories are re-
`viewed. The zero-length entries in the embedded direc-
`tory then indicate the location of the file marks.
`A defective area on an optical disk is sometimes en-
`countered. If this occurs, a “fragmentation map" is
`constructed which is stored in the sector immediately
`following the embedded directory. The map contains
`the lengths of the “good” and “bad” portions of the
`disk. This information is taken into account when
`counting data during the reading of the data back to the
`host, such that the existence of the bad data blocks need
`not be communicated to the host.
`The use of the embedded directories containing the
`length of each record thus allows a particular record to
`be accessed simply by counting bytes of data on the disk
`as they are read. The data need not be examined, e.g.. to
`determine whether a particular byte is preamble or
`postamble information or the like. The ultimate result is
`
`45
`
`50
`
`55
`
`65
`
`NetApp
`
`Exhibit1005
`
`Page14
`
`NetApp Exhibit 1005 Page 14
`
`

`

`5,034,914
`
`l0
`
`‘
`15
`
`20
`
`25
`
`30
`
`7
`that data "segments", consisting in the presently-
`preferred embodiment of up to 500 records of any
`length desired, are stored in sequence, each associated
`with a single embedded directory. [In the exemplary
`embodiment, the maximum record length is 64 k by-
`tes—l. to conform to the largest record length value
`which can be stored as two bytes in the embedded
`directory.]The data is stored contiguoust without
`wastage of space due to preamble or postamble require-
`ments or to inter-record gaps. The only space wasted is
`that which may exist in a single sector between the last
`record corresponding to a particular embedded d