United States Patent
`
`119
`
`Osterlund
`
`{11] Patent Number:
`[45] Date of Patent:
`
`5,034,914
`Jul, 23, 1991
`
`{54]
`
`OPTICAL DISK DATA STORAGE METHOD
`AND APPARATUS WITH BUFFERED
`INTERFACE
`
`[75]
`
`Inventor:
`
`Steven W. Osterlund, North
`Kingstown, R.I.
`
`{73]
`
`[21]
`
`{22]
`
`[63]
`
`[$1]
`[52]
`
`[58]
`
`[56]
`
`Assignee: Aquidneck Systems, International,
`Inc., North Kingstown, R.I.
`
`Appl. No.: 207,590
`Filed:
`Jun. 16, 1988
`
`Related U.S. Application Data
`Continuation-in-part 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. CLS cosescseesscecceeceees GO6F 13/00; G11B 7/013
`US. Che cecssccsssessccsssssseseseeenee 364/900; 364/952.31;
`364/939.3; 364/952.1; 360/72.2; 360/48;
`369/32; 369/59
`Field of Search 0... 364/200, 900 MSFile;
`369/116, 59, 60, 32, 272; 365/234; 360/72.2,48,
`71
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,562,577 12/1985 GIOVEE o.sseeecssecsecseeeerneee STI/3B
`we 369/32
`5/1986 Monen.......
`4,587,643
`
`
`. 364/200
`4,633,393 12/1986 Rundell ..
`7/1987 Ng .......+
`4,680,653
`360/722
`
`7/1987 Busby.........
`-
`ve 369/59
`4,682,318
`
`4,775,969 10/1988 Osterlund......
`369/59
`
`4,791,623 12/1988 Deiotte vacesssecessseccrsse
`
`OTHER PUBLICATIONS
`Jaworski, “Lasers Anticipate Mass (Storage) Appeal”,
`Hardcopy Magazine, Feb. 1986, pp. 43-49.
`Freeman, Jr., “Optical Recording Comes of Age”,
`Mini-Micro Systems, Apt. 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 numberofvariable-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 providinga list of addresses for
`the embedded directories. The embedded directories
`comprise up to a fixed maximum numberofentries each
`indicating the length in bytes ofa corresponding record.
`In a data retrieval or “read” operation, the high-level
`directoryis 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-
`ing-length records can beefficiently 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.
`
`
`9/1968 Anda0... cccsseee
`3,400,371
`9/1968 Beausoleil ..
`3,400,372
`
`3,629,860 12/197! Capozzi.....
`
`4,001,883
`1/1977 Strout ........
`
`4,089,027
`$/1978 Grigoletti......
`.
`.
`4,094,013
`6/1978 Hill et ab...
`cesses 365/234
`4,229,808 10/1980 Hui ...0.-ssssesseeeseseesneneeceneree
`sees 369/48
`
`.....
`w 364/200
`4,310,883
`1/1982 Clifton et al.
`
`3/1982 Tsuyuguchi 0... 360/72.2
`4,321,635
`
`8/1983 ANdersOm ceersererecsrescertreeceers 360/71
`4,398,227
`4,467,421 B/T9R4 WIte on ceeerssceenseneeneseanes 364/200
`4,486,870 12/1984 Pettigrew... 369/32
`4,490,747 12/1984 Yokoyama ......ccccee
`rece 358/296
`
`4,496,997 1/1985 Obtsukd «00...esesseeeseeseees 360/13
`4,531,166 7/1985 Anderson..
`ves
`360/73.04
`4,535,439
`8/1985 Satoh.....
`wee 369/275
`
`4,541,019 9/1985 Precourt«11.seseenesesees 360/15
`30 Claims, 9 Drawing Sheets
`4,545,044 10/1985 Satoh ......c.ce eeeeeneteeeeeeeeeys 369/32
`
`
`
`9
`|
`
`
` OPTICAL
`
`
`RAM
`
`DISK
`
`HOST
`BUFFER
`SYSTEM
`
`MEMORY
`COMPUTER
`
`
`0
`
`
`
`MICROPROCESSOR
`
`NetApp
`
`Exhibit1005
`
`Page 1
`
`NetApp Exhibit 1005 Page 1
`
`

`

`5,034,914
`
`Page 2
`
`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. A19-A24.
`Rathmann, “Dynamic Data Structures On 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 &
`44
`Rothchild, “Optical Storage Moves Closer To Main-
`frames”, Computerworld, May 7, 1984.
`Rothchild,
`“CD-ROM and Write-Once Optical
`Storage-Right Now!”, OpticalMemory 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
`
`Page 2
`
`NetApp Exhibit 1005 Page 2
`
`

`

`Sheet 1 of 9
`
`July 23, 1991
`
`U.S. Patent YOSSIIOUdOYOIN
` WIISKS
`¥Si0ya44ngeon
`b2|622202|6
`WoLd0vy
`AYOWIN
`
`5,034,914
`
`NetApp
`
`Exhibit1005
`
`Page 3
`
`NetApp Exhibit 1005 Page 3
`
`
`

`

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

`

`U.S. Patent
`
`July 23, 1991
`
`Sheet 3 of 9
`
`5,034,914
`
`PHYSICAL LAYOUT OF MAPPING OF DATA, DIRECTORIES
`AND FRAGMENTATION MAP ON DISK
`
`PERIPHERY
`OF DISK
`
`HIGHEST DISK _
`
`BLOCK ADDRESS
`
`SP LOGICAL |HIGH LEVEL) DIRECTORY
`
`DISK TRACK(S
`
`DISK SPACE FOR ADDITIONAL
`DATA SEGMENTS (RECORDS)
`
`
`
`
`BAD BLOCK FRAGMENTATION MAP
`OF DATA SEGMENT 1
`
`EMBEDDED DIRECTORY ENTRY
`OF DATA SEGMENT 1
`
`DATA SEGMENT 1
`
`EMBEDDED DIRECTORY
`OF DATA SEGMENT @
`
`DATA SEGMENT @
`
`LOWEST DISK BLOCK ADDRESS
`
`KKK—WN BAD
`
`oF
`
`_
`exc
`
`| a C
`
`
`
`ENTER
`OF DISK
`
`BLOCK (S)
`
`Fig. 3
`
`NetApp
`
`Exhibit1005
`
`Page5
`
`NetApp Exhibit 1005 Page 5
`
`

`

`U.S. Patent
`
`July 23, 1991
`
`Sheet 4 of 9
`
`5,034,914
`
`EMBEDDED DIRECTORY
`
`LOWEST ADDRESS—
`
`DIRECTORY
`SEQUENCE
`NUMBER
`NUMBER OF
`ENTRIES
`NUMBER OF
`
`STARTING DISK
`BLOCK ADDRESS
`OF DATA
`
`LENGTH
`ENTRY @
`LENGTH
`ENTRY {
`
`IDENTIFIES THE RELATIVE POSITION OF
`THIS SEGMENT WITHIN THE TAPE IMAGE
`PUT QUT BY COMPUTER
`
`NUMBER OF RECORDS CONTAINED WITHIN
`THIS DATA SEGMENT
`
`NUMBER OF TIMES THIS SEGMENT WAS
`
`STARTS AT THE BEGINNING OF THIS
`BLOCK ON THE DISK
`
`
`
`
`BROKEN BY BAD DATA BLOCK SECTIONS
`RATEON
`
`
`
` BYTE @ OF RECORD @ (8 BITS TO BYTE)
`
` LENGTH OF EACH OF 500 RECORDS
`
`HIGHEST
`ADDRESS
`
`LENGTH OF
`ENTRY 499
`
`Fig.4
`
`NetApp
`
`Exhibit1005
`
`Page6é
`
`NetApp Exhibit 1005 Page 6
`
`

`

`U.S. 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 1S NON-ZERO)
`
`
`
`G00D
`BLOCKS
`
`~ BAD
`BLOCKS
`
`6000
`BLOCKS
`
`
`
`
`
`
`
`
`
`RELATIVE TO START
`BLOCK OF DATA
`RELATIVE TO END OF PREVIOUS
`STRETCH OF GOOD BLOCKS
`
`RELATIVE TO END OF PREVIOUS
`STRETCH OF BAD BLOCKS
`RELATIVE TO END OF PREVIOUS
`STRETCH OF GOOD BLOCKS
`
`BAD
`BLOCKS
`
`
`
`A BLOCK ON DISK EQUALS AT LEAST 1024 BYTES
`OF 8 BITS EACH
`
`NOTE:
`
`SEQUENCES 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
`
`Fiig.353
`
`NetApp
`
`Exhibit1005
`
`Page7
`
`NetApp Exhibit 1005 Page 7
`
`

`

`U.S. Patent
`
`July 23, 1991
`
`Sheet 6 of 9
`
`5,034,914
`
`
`CSTART) EMBEDDED DIRECTORY
`INTERFACE20
`CONSTRUCTION FLOWCHART
`
`APPEND RECORD DATA
`TQ DATA ALREADY IN
`BUFFER MEMORY
`
`MARK END OF BUFFER
`NO
`ROOM LEFT IN
`AT EVEN MULTIPLE OF
`BUFFER FOR MAXIMUM
`DISK BLOCK LENGTH
`RECORD LENGTH?
`
`
` TRANSFER REMAINDER
`
`DATA TO BEGINNING
`OF BUFFER MEMORY
`
`NIMUM OPTICAL
`K WRITE LENGTH\YES
`5
`OF DATA IN BUFFER
`MEMORY
`
`WRITE ONE WRITE
`LENGTH OF DATA
`TO DISK
`
`ENGTH
`BEDDED
`RY
`
`RECORD LENGTHS IN
`TEMPORARY EMBEDDED
`DIRECTORY ENTRY OR
`OPERATOR CONTROLLED
`DISMOUNT ?
`
`
`WRITE EMBEDDED DIRECTORY
`ENTRY TO BLOCK IMMEDIATELY
`
`
` MAXIMUM NUMBER OF
`WRITE REMAINING DATA
`IN BUFFER TO DISK
`
`FOLLOWING DATA
`
`
`
`ADD ADDRESS OF EMBEDDED
`DIRECTORY TO HIGH LEVEL
`
`DIRECTORY IN BUFFER
`
`
`
`
`BAD BLOCK
`FRAGMENTATION
`MAP REQUIRED
`
`YES
`
`
`WRITE BAD BLOCK FRAGMENTATION
`MAP TO BLOCK FOLLOWING
`EMBEDDED DIRECTORY ENTRY
`
`
`
`
`(END)
`
`Fig.6
`
`NetApp
`
`Exhibit1005
`
`Page 8
`
`NetApp Exhibit 1005 Page 8
`
`

`

`
`
` WRITE
`
`U.S. Patent
`
`July 23, 1991
`
`Sheet 7 of 9
`
`5,034,914
`
`BAD BLOCK FRAGMENTATION
`MAP CONSTRUCTION
`FLOWCHART
`
`INSTRUCTION FROM
`OPTICAL DISK SYSTEM
`DRIVE 24
`
`PREVIOUS
`WRITE
`SUCCESSFUL ?
`
`SUCCESSFUL ?
`
`
`INCREMENT
`TES
`POINTER TO GOOD
`
`BLOCK FIELD OF
`NEXT ENTRY
`
`
`
`
`
`
`INCREMENT
`PREVIOUS
`{WRITE
`
`
`POINTER TO BAD
`BLOCK FIELD OF
`BAD?
`CURRENT ENTRY
`
`
`
`
`
`INCREMENT
`
`OEREy
`POINTER 10
`
`
`vent
`SAME FIELD OF
`NEXT ENTRY
`
`
`
`
`ADD BLOCKS
`
`USED 10 CURRENT
`
`FIELD OF ENTRY
`
`
`
`
`
`
`
`
`NOTE:
`POINTER IN MEMORY 1S TO
`KEEP TRACK OF POSITION
`IN THE FRAGMENTATION MAP
`
`PLACE
`OVERFLOW
`IN NEW FIELD.
`
`Fig.7
`
`NetApp
`
`Exhibit1005
`
`Page9
`
`NetApp Exhibit 1005 Page 9
`
`

`

`U.S. Patent
`
`July 23, 1991
`
`Sheet 8 of 9
`
`5,034,914
`
`READ OPERATIONS
`FLOWCHART
`
`(START)INSTRUCTION FROM
`HOST INTERFACE 20
`
`
`
`CALCULATE PORTIONS OF
`DESIRED RECORD\.ng
`DATA SEGMENT THAT
`DATA IN BUFFER
`INCLUDES DESIRED
`
`
`MEMORY ?
`RECORD DATA
`
`
`
`
`,
`
`RETRIEVE RECORD
`LENGTH FROM
`CURRENT EMBEDDED
`DIRECTORY ENTRY|-
`
`BLOCK ENTRIES
`IN CURRENT DATA
`
`
` NUMBER OF BAD
`SEGMENT NOT
`
`
`
`
`
`
`YES
`
`CALCULATE BUFFER
`ADDRESS OF
`RECORD DATA
`
`
`
`FILL BUFFER MEMORY
`FILL BUFFER MEMORY
`
`
`WITH PORTION OF DATA
`
`
`WITH PORTION OF
`SEGMENT USING BAD
`DATA SEGMENT
`
`BLOCK MAP INFORMATION
`
`BOX A
`
`TRANSFER RECORD
`DATA T0 HOST
`COMPUTER 19
`
`CENDY
`
`F'g-8
`
`NetApp
`
`Exhibit1005
`
`Page 10
`
`NetApp Exhibit 1005 Page 10
`
`

`

`U.S. 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 10 STARTING
`
`BLOCK ADDRESS
`
`
`
`
`600D
`BLOCK FIELD
`EQUALS § ?
`
`
` INCREMENT POINTER
`TO NEXT GOOD/BAD
`
`
`BLOCK ENTRY
`
`
`READ
`
`CONSECUTIVE
`
`GOOD BLOCKS
`
`FIELD TO STARTING
`BLOCK ADDRESS
`
`
`
`
` ADD GOOD BLOCK
` DESIRED NUMBER
`Fig.9
`
`OF BLOCKS READ
`TO FILL MEMORY?
`
`
`
`
`
`NetApp
`
`Exhibit1005
`
`Page 11
`
`NetApp Exhibit 1005 Page 11
`
`

`

`1
`
`5,034,914
`
`OPTICAL DISK DATA STORAGE METHOD AND
`APPARATUS WITH BUFFERED INTERFACE
`
`10
`
`PRIOR APPLICATIONS
`This is a continuation-in-part of U.S. 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.
`BACKGROUNDOF THE INVENTION
`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 madeto the followingarticles:
`(1) May 7, 1984 edition, Computerworld, 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”
`Oneobject ofthis inventionis to efficiently solve 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 andto the data organiza-
`tion practices which have become customary in tape
`storage applications.
`Moreparticularly, as conventionally implemented, a
`single reel of magnetic tape is commonly usedto store a
`single “file” of data, that is, an entire data set pertaining
`to a particular subject, e.g., a payrollfile, an employee
`file or the like. Within eachfile, the data is typically
`divided into “records”, the length of whichis notfixed.
`For example, each record may relate to a particular
`employee. Normally each record in thefile 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
`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 ofa 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,
`thatis, so that the single file typically found on eachreel
`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 correspondingto 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” |
`
`35
`
`40
`
`45
`
`50
`
`60
`
`65
`
`2
`instructions must be forwarded from the host to the tape
`drive and executed. Obviously, this 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 computerto direct that a so called
`“file mark”, consisting of a predetermined sequence of
`bits, be written to the tape from time to time,thatis, at
`unspecified intervals between records. If the host de-
`sires to skip over a portion ofthe 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 uniquefile
`mark sequence. If the host “knows”that the record of
`interest is between the second andthird file marks, for
`example, it can direct that the tape advancetothefirst
`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
`processis 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;
`thatis, 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 respondto all of
`the commands which are conventionally directed to
`tape drives, as outlined above, and in order to beattrac-
`tive to users must provide 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 aroundthe disk and divide
`the spiral track into “sectors”. Typically 1,024 bytes per
`sector may be stored on each track. The opticaldriveis
`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 numberof“sector locations” equal to the number of
`the hard sectors on the disk (on the order of 32) umes
`the numberofthe essentially concentric rings (on the
`order of 32,000) madebythe spiral track.
`One wayof 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 beusefully ap-
`plied to optical disk storage. However, this actually’ is
`not the case due to the varying characteristics of mag-
`
`NetApp
`
`Exhibit1005
`
`Page 12
`
`NetApp Exhibit 1005 Page 12
`
`

`

`10
`
`5
`
`35
`
`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 notallow erasure.
`Erasing of obsolete blocks of data,
`incidentally,
`is
`typically not practiced on tape, although erasingitself is
`readily accomplished. Instead, the new data is simply
`written to the end ofthe 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 moveradially 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 numberof 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 ofthe sector at whichthe next portionofthefile is
`stored. Typically, this can be accomplished sufficiently
`quickly that the host does not experience a delay in
`accessingall of the file. Accordingly, even if an applica-
`tion program does notrequire 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 “record” 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
`
`5,034,914
`4
`tape and disk storage cannot appropriately be applied to
`optical disk storage, even wherea particular sequential-
`ly-organized data set to be stored on the optical disk
`might otherwise have beensuitable for storage on tape.
`Notably, the fact that tape records are conventionally
`accessed record-by-record meansthatit would be inap-
`propriate to assign an entire sector on the optical disk to
`each record;if the record wererelatively 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 bereliably 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 conveniencein 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 approachis directed principally to very large
`mainframe host computers.
`On 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 ofthe 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 wouldofcourse 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
`
`40
`
`45
`
`60
`
`65
`
`NetApp
`
`Exhibit1005
`
`Page 13
`
`NetApp Exhibit 1005 Page 13
`
`

`

`5
`characteristics of the optical media. However, to do so
`in a manner suchthat 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 anew 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.
`BRIEF DESCRIPTION OF THIS INVENTION
`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,¢.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 apparatusfor storing data accord-
`ing to the invention, record structure data is generated
`based on the data recordsto be stored andis distributed
`on the disk so thatit is in close physical proximity to the
`optical disk read/write head when it is needed.
`Withthis system and method. the optical disk is able
`to effectively emulate magnetic tape storage. The
`methodof 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 embeddeddirectories 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 high-level directoryis 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 bythe optical disk of the
`record-by-record response of a tape drive to typical
`host commands, the embeddeddirectories each contain
`a sequence of record length identifiers. Each record
`length identifier simply consists of a number equal to
`the numberof 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 postamble 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 remainderof the sector contain-
`ing the embedded directory consists of record length
`data. Each record length data item is assigned two bytes
`
`20
`
`25
`
`40
`
`45
`
`6
`in the embedded directory, such that each embedded
`directory is capable of containing 500 record length
`identifiers corresponding to 500 stored records.
`Thesector address of each of the embedded directo-
`ries is stored in the high-level directory, and an identifi-
`cation ofthe 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 ofthe 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 sectorafter
`the preceding embedded directory, and the number of
`bytes of the particular record sought. Thestarting 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 numberof 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 duringits 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 ofrecords 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., [0
`determine whether a particular byte is preamble or
`postamble information orthelike. The ultimate result is
`
`5,034,914
`
`50
`
`60
`
`65
`
`NetApp
`
`Exhibit1005
`
`Page 14
`
`NetApp Exhibit 1005 Page 14
`
`

`

`’
`15
`
`20
`
`25
`
`5,034,914
`8
`tions are then written by the microprocessorto the disk
`adjacent to the location ofthe last high-level directory
`entry written to the disk.
`All of the data which had been directed to tape by the
`host for storage is treated as a single file in the high-
`level directory structure. The high-level directory,
`comprising a table of embedded directory addresses,
`can be used to locate any segment ofrecords within the
`file. This serves as a convenient way to locate the em-
`bedded directory blocks; however,
`if this entry be-
`comes damaged,the data records can still be recovered
`using pointers in the embedded directories. File marks
`can be used to divide a file as thus defined into ““sub-
`files” if needed by an application program.
`Numerous advantages of this arrangement will be
`apparentto thoseofskill in the art. For example, in one
`preferred embodimentof the invention, in w