System and method for disk mapping and data retrieval

• US 6,185,653 B1
• Filed: 05/04/1999
• Issued: 02/06/2001
• Est. Priority Date: 09/24/1990
• Status: Expired due to Term

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Vishlitzky, Natan, Alterescu, Bruno, Yanai, Moshe, Castel, Daniel
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US09/305,127
• Time in Patent Office: 644 Days
• Field of Search: 711/4, 711/202, 711/156, 710/68, 707/101
• US Class Current: 711/4
• CPC Class Codes: G06F 11/2066 Optimisation of the communication load
• CPC Class Codes: G06F 11/2071 using a plurality of controllers
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 11/2079 Bidirectional techniques
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 2003/0697 device management, e.g. handlers, drivers, I/O schedulers
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11B 20/1217 on discs
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 69/26 Special purpose or proprietary protocols or architectures network applications for proprietary or special purpose networking environments H04L67/12
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An apparatus and method for disk mapping and data retrieval includes a data storage medium on which has been stored a plurality of data records. Each record includes at least a record identification portion, for uniquely identifying each record from among the plurality of data records. The apparatus builds a record locator table in high speed semiconductor memory which comprises the unique record identifiers for the records on the storage medium as well as a record locator index generated by the apparatus, which indicates the address of the data record on the storage medium. Data retrieval is facilitated by first searching the record locator table in high speed semiconductor memory for a requested data record. Utilizing the record locator index associated with the requested data record, the system directly accesses the requested data record on the storage medium thereby minimizing storage medium search time. Also disclosed is an apparatus and method for converting CKD formatted data records to FBA formatted disk drives and for building and compressing the “count” portion of the CKD data formatted record into a record locator table.

Claims

1. A method for storing data records onto one or more disk drives, said method comprising:

receiving a plurality of the data records, each of the plurality of data records including at least a record identification portion and a data portion; and

storing, to one or more of the disk drives, data of said plurality of data records, and maintaining an index of record locator information specifying locations on said one or more disk drives where said data of said plurality of data records are stored, wherein said index is accessible for obtaining record locator information of a specified data record for access to data of the specified data record on said one or more disk drives;

wherein the maintaining of the index of record locator information includes transforming and encoding the record identification portions of at least some of said plurality of data records, and storing the transformed and encoded record identification portions of said at least some of said plurality of data records in said index in association with record locator information of said at least some of said plurality of data records,

wherein the record identification portions of said at least some of said plurality of data records are transformed and encoded by comparing each record identification portion to an expected value for said each record identification portion, and storing in said index a record modifier for said each record identification portion when the comparing of said each record identification portion to the expected value for said each record identification portion determines that said each record identification portion differs from the expected value for said each record identification portion.

2. The method as claimed in claim 1, which includes accessing said index for obtaining record locator information of a specified data record, and using said record locator information of said specified data record for access to data of the specified data record on said one or more disk drives.

3. The method as claimed in claim 2, which includes maintaining said index in semiconductor memory, and accessing said index in the semiconductor memory for obtaining the record locator information of the specified data record for access to data of the specified data record on said one or more disk drives.

4. The method as claimed in claim 1, which includes compressing the index.

5. The method as claimed in claim 4, wherein the index is compressed by scanning the index to find repetitive patterns having a relatively high frequency of occurrence in the index, and replacing each repetitive pattern having a relatively high frequency of occurrence in the index with a respective new pattern having a length shorter than said each repetitive pattern.

6. The method as claimed in claim 1, wherein said maintaining of said index includes storing the transformed and encoded record identification portions of said at least some of said plurality of data records and said record locator information of said at least some of said plurality of data records in a table that comprises said index.

7. A method for storing data records onto one or more disk drives, said method comprising:

receiving a plurality of the data records, each of the plurality of data records including at least a record identification portion and a data portion; and

storing, to one or more of the disk drives, data of said plurality of data records, and maintaining an index of record locator information specifying locations on said one or more disk drives where said data of said plurality of data records are stored, wherein said index is accessible for obtaining record locator information of a specified data record for access to data of the specified data record on said one or more disk drives;

wherein the maintaining of the index of record locator information includes transforming and encoding the record identification portions of at least some of said plurality of data records, and storing the transformed and encoded record identification portions of said at least some of said plurality of data records in said index in association with record locator information of said at least some of said plurality of data records,

wherein said maintaining of said index includes storing the transformed and encoded record identification portions of said at least some of said plurality of data records and said record locator information of said at least some of said plurality of data records in a table that comprises said index, and

wherein the method includes storing in the table record flags and record modifiers.

8. The method as claimed in claim 7 which includes storing the record flags at one end of a body portion of the table and storing the record modifiers at an opposite end of the body portion of the table.

9. The method as claimed in claim 7, which includes selecting a compression algorithm for each of said at least some of said plurality of data records, and setting at least one of the record flags for each of said at least some of said plurality of data records for indicating the selected compression algorithm for said each of said at least some of said plurality of data records.

10. A method of transforming and encoding a sequence of record identifiers, said method comprising:

(a) comparing each record identifier to an expected value for said each record identifier; and

(b) producing a series of modifiers, said series of modifiers including a respective modifier for said each record identifier when the comparing of said each record identifier to the expected value for said each record identifier determines that said each record identifier differs from the expected value for said each record identifier, wherein said each record identifier can be reconstructed from the modifier for said each record identifier and the expected value for said each record identifier.

11. The method as claimed in claim 10, which further includes compressing the series of modifiers by scanning the series of record modifiers to find repetitive patterns having a relatively high frequency of occurrence in the series of modifiers, and replacing each repetitive pattern having a relatively high frequency of occurrence in the series of modifiers with a respective new pattern having a length shorter than said each repetitive pattern.

12. The method as claimed in claim 10, wherein the comparing of said each record identifier to the expected value for said each record identifier produces a respective flag, and wherein the method further includes storing the flags in one end of a region of memory, and storing the modifiers in an opposite end of the region of memory.

13. An apparatus for transforming and encoding a sequence of record identifiers, said apparatus comprising:

means for comparing each record identifier to an expected value for said each record identifier to determine whether or not said each record identifier differs from the expected value for said each record identifier; and

means for producing a series of modifiers, said series of modifiers including a respective modifier for said each record identifier when the means for comparing determines that said each record identifier differs from the expected value for said each record identifier, wherein said each record identifier can be reconstructed from the modifier for said each record identifier and the expected value for said each record identifier.

14. The apparatus as claimed in claim 13, which further includes means for compressing the series of modifiers by scanning the series of record modifiers to find repetitive patterns having a relatively high frequency of occurrence in the series of modifiers, and replacing each repetitive pattern having a relatively high frequency of occurrence in the series of modifiers with a respective new pattern having a length shorter than said each repetitive pattern.