Non-volatile memory storage and bilevel index structure for fast retrieval of modified records of a disk track

• US 5,269,019 A
• Filed: 04/08/1991
• Issued: 12/07/1993
• Est. Priority Date: 04/08/1991
• Status: Expired due to Term

• Current Assignee: Storage Technology Corp (Oracle Corporation)
• Original Assignee: Storage Technology Corp (Oracle Corporation)
• Inventors: Peterson, Gregory W., Kurzawa, Leonard J.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US07/681,753
• Time in Patent Office: 974 Days
• Field of Search: 364/200, 395/600, 395/275, 395/425
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06F 2212/225 Hybrid cache memory, e.g. having both volatile and non-volatile portions
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method is described for managing data records stored in non-volatile memory in a disk drive system with cache memory. A variable-length directory containing descriptors of disk records is used to locate a selected record non-volatile memory. A table, ordered sequentially by record number, is used to quickly locate a record in non-volatile memory without having to perform a time-consuming search. In order to efficiently utilize space in non-volatile memory, a list is kept of free space for storing record descriptors. After an initial nominal allocation, additional free space is allocated only when required, thus further increasing the efficiency of use of non-volatile memory.

Claims

1. In a disk drive system which stores data in a plurality of tracks contained therein, each of said tracks containing a plurality of data records, each of said data records having an associated record number, said disk drive system having an associated volatile memory subsystem and an associated non-volatile memory subsystem, both of which subsystems are external to said disk drive system, said non-volatile memory subsystem having random-access memory for storing a plurality of said data records and a plurality of record descriptors, each of said record descriptors comprising a pointer to one of said data records in said non-volatile memory subsystem, a method for managing said data records in said non-volatile memory subsystem, comprising the steps of:

(a) allocating, in response to a request for writing a data record to said disk drive system, space for said record descriptors from the list of free memory locations;

(b) writing, to said data buffer area, a copy of each said data record which has been modified in both said non-volatile memory subsystem and in said volatile memory subsystem after having been read into said volatile memory subsystem from said disk drive system;

(c) allocating a data buffer area in said non-volatile memory subsystem for storing said data records;

(d) tabulating, in said non-volatile memory subsystem, a list of free memory locations available for storing said record descriptors;

(e) compiling, in said non-volatile memory subsystem, a directory of each said data record which has been modified, each entry in said directory having indicia of location of a corresponding modified said data record in said non-volatile memory subsystem;

(f) compiling, in said non-volatile memory subsystem, a list for each of said tracks which has been read into said volatile memory subsystem from said disk drive system, each said list having entries, ordered sequentially by said record number, of the records in said non-volatile memory subsystem, each of said entries in said list having indicia of location of a corresponding said record descriptor in said directory of modified data records; and

(g) locating said selected data record in the non-volatile memory subsystem, by indexing to the record descriptor in said list in said non-volatile memory subsystem, using the record number as an offset from the beginning of the list, to find an entry in the list, and then using the value of the found entry as an offset into said directory of modified data records to fine the entry having indicia of location of the selected data record in said non-volatile memory subsystem.

2. The method of claim 1 wherein the step of compiling each said is performed in said volatile memory subsystem, exclusive of said non-volatile memory subsystem.

3. The method of claim 1 wherein:

the step of compiling said directory of said data records includes;

allocating a segment of said non-volatile memory equivalent to the size occupied by the sum of a pre-determined plurality of said record descriptors.

4. The method of claim 1 wherein space for the record descriptors is allocated in segments capable of containing between 16 and 64 descriptors per segment.

5. The method of claim 4 wherein said segments are allocated only when additional space is required for storing additional record descriptors.

6. In a disk drive system which stores data in a plurality of tracks each containing a plurality of data records, each of said data records having an associated record number, said disk drive system having an associated non-volatile memory subsystem external to said disk drive system and having random-access memory for storing a plurality of said data records, said non-volatile memory subsystem containing a plurality of record descriptors, each said record descriptor comprising a pointer to one of said data records in said non-volatile memory subsystem, a method for managing said data records in said non-volatile memory subsystem comprising the steps of:

(a) allocating space for a table of modified records in said non-volatile memory subsystem having n entries, each entry being of sufficient size to contain indicia of location of a memory location in said non-volatile memory subsystem, where n is equal to the number of said data records per said track;

(b) allocating a segment of space for a non-volatile memory directory, capable of containing v said record descriptors, where v is a variable integral number between one and the number of said data records per said track, said segment being allocated from said free list;

(c) maintaining a free list, in said non-volatile memory subsystem, of the unused memory locations in the directory which are available for storing said record descriptors;

(d) defining an area in said non-volatile memory subsystem as a non-volatile memory data buffer for storing said data records which are modified;

(e) writing said data records to the non-volatile memory data buffer;

(f) storing, for each of said data records which has been modified in said non-volatile memory system as a result of a request for writing said data record to said disk drive system, in the first available location in the free list, a record descriptor corresponding to said modified data record, and

in the mth location in the record descriptor list in the modified record table for the associated track, the integer corresponding to the offset, into the non-volatile memory directory, of the entry containing the record descriptor for said modified data record, where m is the record number of said modified record;

(g) compiling, in the table of modified records, for each said track, a list of said record descriptors for said records written to said non-volatile memory subsystem, said record descriptor list having entries sequentially ordered by record number, each said entry in said list having indicia of location of a record descriptor in said non-volatile memory directory, said record descriptor corresponding to one of said data records in said non-volatile memory data buffer; and

(h) locating said selected data record in said non-volatile memory subsystem, using the record number of said selected data record as an offset from the beginning of said record descriptor list to an entry in said list, then using the integer value of said entry in said list as the rank of position of an entry in said non-volatile memory directory, said non-volatile memory directory entry having indicia of location of said selected record in said non-volatile memory subsystem.

7. The method of claim 6 wherein the step of allocating a segment of space for the non-volatile memory directory occurs in response to a request for writing a data record to said disk drive system, when said request requires more space than currently allocated in the free list for the track associated with the record;

and v is an integer between 8 and 64.