Cache for optical storage device and method for implementing same

• US 5,588,129 A
• Filed: 01/16/1996
• Issued: 12/24/1996
• Est. Priority Date: 02/09/1994
• Status: Expired due to Term

• Current Assignee: eAcceleration Corporation
• Original Assignee: Acceleration Software International Corporation
• Inventors: Ballard, Clinton L.
• Primary Examiner(s): Chan, Eddie P.
• Assistant Examiner(s): Nguyen, Hiep T.
• Application Number:
  US08/585,808
• Time in Patent Office: 343 Days
• Field of Search: 395/440, 395/441, 395/445, 395/488, 395/449, 395/182.13, 395/182.17, 395/182.19, 395/182.2
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/311 In host system
• CPC Class Codes: G06F 2212/312 In storage controller

Abstract

A cache for improving access to optical media includes a primary cache comprising RAM and a secondary cache comprising a portion of hard disk memory. Multiple aspects of the invention are defined: (1) Cache data discrimination: Discrimination methodology is implemented for determining when data should not be cached. Under certain conditions, caching of data is less likely to improve access time. (e.g., when the transfer rate is already exceeding a critical sustained throughput rate; when an estimated time to complete a CD-ROM data request is within a specific percentage of the estimated time to complete a hard drive disk request). (2) Secondary cache fragmentation avoidance: To keep the access time to secondary cache faster than the access time to the optical media, fragmentation of the secondary cache (i.e., hard disk) is minimized. To do so, constraints are imposed: (i) an entire CD-ROM request is stored in contiguous sectors on the hard drive; (ii) sequential CD-ROM requests to adjacent sectors of CD-ROM are concatenated on the hard drive; (iii) data redundancy is permitted); and (iv) first-in first-out criteria is used for overwriting data. (3) Alternative update methodologies: Cache updates are performed in sequence or in parallel to primary and secondary cache depending upon the embodiment. (4) Data integrity: Integrity of data stored in non-volatile secondary cache is maintained for a substantial portion of secondary cache through power failures, shutdowns and media swaps.

Claims

1. A cache apparatus for storing data for a plurality of optical disk storage media alternatively loadable into a common optical disk drive, the apparatus comprising:

volatile memory and non-volatile memory for storing disk data read from the plurality of optical disk storage media, the volatile memory serving as a primary cache and the non-volatile memory serving as a secondary cache, the secondary cache comprising a portion of a

a plurality to a respective optical disk identification codes stored in non-volatile memory and corresponding to a plurality of optical disk storage media alternatively loadable into the common optical disk drive, each identification code unique to a corresponding optical disk storage media;

an index stored in non-volatile memory pointing among said plurality of identification codes to a currently accessible optical disk storage media;

a first data structure stored in non-volatile memory for mapping at least a portion of said disk data stored in the non-volatile memory to corresponding address locations on an associated optical disk storage media, said first data structure comprising a first tag associated with first disk data read from a first optical disk storage media and a second tag associated with second disk data read from a second optical disk storage media; and

a digital processing means allocating the nonvolatile memory no comprise;

a second data structure for storing disk data, the stored disk data in the second data structure being organized into a plurality of groups of disk data, and wherein only one group of the plurality of groups of disk data is active at one time, each one group being a physically contiguous sector area within the non-volatile memory;

a third data structure for storing a plurality of markers and a corresponding plurality of optical disk sector addresses, each marker of said plurality of markers corresponding to a group of

said plurality of grouses of cached data; and

the digital processing means allocating the volatile memory to comprise a fourth data structure for storing a portion of the disk data stored in the second data structure of the nonvolatile memory;

the digital processing means processing a request to read disk data from an optical disk storage media fin a and comprising.

(i) means for defining the index pointing among said plurality of identification codes which corresponds to a current optical disk storage media;

(ii) means for accessing the first data structure to identify whether disk data is stored in non-volatile memory; and

(iii) means for retrieving first disk data from said non volatile memory without first re-storing said first disk data from said first optical disk storage media into the non-volatile memory following changes in the current optical disk storage media away from the first optical disk storage media and back to the first optical disk storage media, when said disk data is stored in said non-volatile memory; and

said digital processing means executing a first computer program for covering stored disk data after a restoration of power, and further comprising;

(iv) means for determining one marker of the plurality of markers as being invalid and each other marker of the plurality of markers as being valid by scanning among the plurality of markers to identify a last valid marker before said one invalid marker;

(v) means for defining a next marker unique to all valid markers in said third data structure, wherein said next marker is an increment of said last valid marker;

(vi) means for deriving a next location in the second data structure corresponding to said next marker for storing disk data.

2. A method for storing data in non-volatile cache memory received from a plurality of optical disks, comprising the steps of:

defining data-control structures, comprising;

a first data structure for storing a plurality of respective optical disk identification codes corresponding to a plurality of optical disks, each identification code unique to a corresponding optical disk and derived from information stored on the corresponding optical disk;

an index pointing into said first data structure to identify a current optical disk;

an optical disk sector address for disk data specified in a current data request associated with said current optical disk; and

a second data structure for mapping disk data stored in said non-volatile cache memory to a location on an associated optical disk;

defining a third data structure in the nonvolatile cache memory for storing disk data read from an optical disk, the third data structure organized into a plurality of groups of disk data, and wherein only one group of the plurality of groups of disk data is active at one time, each one group being a physically contiguous sector area within the nonvolatile memory;

defining a fourth data structure for storing a plurality of markers and a corresponding plurality of optical disk sector addresses, each marker of said plurality of markers corresponding to a group of said plurality of groups of disk data;

maintaining the index to identify the current optical disk;

determining the optical disk sector address from a current data request;

storing first disk data for the current data request in the third data structure;

updating said second data structure to enable the stored first disk data to be later accessed directly from the third data structure;

retrieving the first disk data from said third data structure without first re-storing said first disk data from said first optical disk back into said third data structure following a change in the current optical disk away from the first optical disk back to the first optical disk, when said first disk is stored in said third data structure;

in response to a power recovery determining one marker of the plurality of markers as being invalid and each other marker among the plurality of markers as being by scanning among the plurality of markers to identify a last valid marker before said one invalid marker

after the step of determining an invalid marker, defining a next marker unique to all valid markers in said fourth data structure, wherein said next marker is an increment of said last valid marker;

deriving a next location in the third data structure corresponding to said next marker for storing disk request data.