System and method for disk mapping and data retrieval

• US 6,587,919 B2
• Filed: 03/19/2002
• Issued: 07/01/2003
• 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: Castel, Daniel, Vishlitzky, Natan, Alterescu, Bruno, Yanai, Moshe
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US10/100,760
• Publication Number:
  US 20020147886A1
• Time in Patent Office: 469 Days
• Field of Search: 711/112, 710/68
• US Class Current: 711/112
• 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

A data storage system includes data storage and a record locator data structure in random access memory. The record locator data structure includes entries having different lengths. For locating variable-length data records in the data storage, for example, at least some but not all of the entries have a data-length portion indicating data length of a respective data record of the entry when the data length of the respective data record fails to match an expected data length. Each entry, for example, has a fixed length portion including an indication of whether or not the entry has a data-length portion, the fixed length portions are stored sequentially in a first region of address locations of the random access memory, and the data-length portions are stored sequentially in a second region of address locations of the random access memory.

Claims

1. A data storage system comprising data storage, random-access memory, and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data records of the logical track including variable-length data records, the data processor being programmed to access a record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing respective entries for data records having data stored in the data storage, at least some but not all of the entries having a data-length portion indicating data length of the data record of the entry when the data length of the record of the entry fails to match an expected data length.

2. The data storage system of claim 1, wherein the data length of the data record of the entry becomes the expected data length for a next data record of the logical track.

3. The data storage system of claim 1, wherein the processor is programmed to compress the entries by searching for a frequently replicated data-length portion, and upon finding a frequently replicated data-length portion, replacing the frequently replicated data-length portion by setting a value in each entry having the frequently replicated data-length portion, the value being representative of the frequently replicated data-length portion, so as to eliminate the frequently replicated data-length portion.

4. A data storage system comprising data storage, random-access memory, and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one count-key-data (CKD) record of a logical track of CKD records, the data processor being programmed to access a record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the CKD record, the record locator data structure containing entries for the CKD records having data stored in the data storage, at least some but not all of the entries having a respective record modifier portion when the count of the CKD record of the entry fails to match an expected count.

5. The data storage system of claim 4, wherein the count of the CKD record of each entry determines the expected count for a next CKD record of the logical track.

6. The data storage system of claim 4, wherein the processor is programmed to compress the entries by searching for a frequently replicated record modifier portion, and upon finding a frequently replicated record modifier portion, replacing the frequently replicated record modifier portion by setting a value in each entry having the frequently replicated record modifier portion, the value being representative of the frequently replicated record modifier portion, so as to eliminate the frequently replicated record modifier portion.

7. A data storage system comprising data storage, random-access memory, and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data processor being programmed to access a record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing entries for data records having data stored in the data storage, each entry including a fixed-length portion, and at least some but not all of the entries having respective variable-length portions, wherein the fixed-length portion of each entry includes an indication of whether or not the entry includes a variable-length portion.

8. The data storage system of claim 7, wherein the processor is programmed to compress the entries by searching for a frequently replicated variable-length portion, and upon finding a frequently replicated variable-length portion, replacing the frequently replicated variable-length portion by setting a value in the fixed-length portion of each entry having the frequently replicated variable-length portion, the value being representative of the frequently replicated variable-length portion, so as to eliminate the frequently replicated variable-length portion.

9. The data storage system of claim 7, wherein the data records include variable-length data records, and each entry has a variable-length portion indicating data length of the data record of the entry when the data length of the data record of said each entry fails to match an expected data length.

10. The data storage system of claim 9, wherein the data length of the data record of said each entry becomes the expected data length for a next data record of the logical track.

11. The data storage system of claim 7, wherein the data records are count-key-data (CKD) records, and each entry has a variable-length portion indicating the count of the data record of said each entry when the count of the data record of said each entry fails to match an expected count.

12. The data storage system of claim 11, wherein the count of the data record of said each entry determines the expected count for a next data record of the track.

13. A data storage system comprising data storage, random-access memory, and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data processor being programmed to access a record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing respective entries for data records having data stored in the data storage, each entry including a fixed-length portion, and at least some but not all of the entries having respective variable-length portions, the fixed-length portions being stored sequentially in a first region of address locations of the random-access memory, and the variable-length portions being stored sequentially in a second region of address locations of the random-access memory.

14. The data storage system as claimed in claim 13, wherein the fixed-length portion of each entry includes record flags, and one of the record flags indicates whether or not said each entry includes a variable-length portion.

15. The data storage system of claim 13, wherein the first region of memory addresses and the second region of memory addresses are within a block of memory addresses allocated for storing the entries of the records of the logical track, the first region of memory addresses is aligned at one end of the block, and the second region of memory addresses is aligned at another end of the block, so that as entries for records of the track are stored in the block, the first region of memory addresses and the second region of memory addresses each expand toward each other and may eventually collide within the block.

16. The data storage system of claim 15, wherein the processor is programmed to compress the entries when the first region of memory addresses and the second region of memory addresses collide within the block.

17. The data storage system of claim 13, wherein the processor is programmed to compress the entries by searching for a frequently replicated variable-length portion, and upon finding a frequently replicated variable-length portion, replacing the frequently replicated variable-length portion by setting a value in the fixed-length portion of each entry having the frequently replicated variable-length portion, the value being representative of the frequently replicated variable-length portion, so as to eliminate the frequently replicated variable-length portion.

18. The data storage system of claim 13, wherein the data records include variable-length data records, and each entry has a variable-length portion indicating data length of the data record of the entry when the data length of the data record of said each entry fails to match an expected data length.

19. The data storage system of claim 18, wherein the data length of the data record of said each entry becomes the expected data length for a next data record of the logical track.

20. The data storage system of claim 13, wherein the data records are count-key-data (CKD) records, and each entry has a variable-length portion indicating the count of the data record of said each entry when the count of the data record of said each entry fails to match an expected count.

21. The data storage system of claim 20, wherein the count of the data record of said each entry determines the expected count for a next data record of the track.

22. A method of maintaining a record locator data structure in random access memory of a data storage system also having data storage and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data records of the logical track including variable-length data records, the data processor being programmed to access the record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing respective entries for data records having data stored in the data storage, at least some but not all of the entries having a data-length portion indicating data length of the data record of the entry, the method including updating the record locator data structure to include a new entry for a new data record by:

(a) establishing an expected data length for the new data record;

(b) comparing the data length of the new data record to the expected data length for the new data record, and

(i) if the data length of the new data record does not match the expected data length of the new data record, storing a data-length portion indicating the data length of the new data record of the new entry; and

(ii) if the data length of the new data record matches the expected data length of the new data record, not storing a data-length portion indicating the data length of the new data record of the new entry.

23. The method of claim 22, wherein the data length of the data record of the entry becomes the expected data length for a next data record of the logical track.

24. The method of claim 22, which further includes compressing the entries by searching for a frequently replicated data-length portion, and upon finding a frequently replicated data-length portion, replacing the frequently replicated data-length portion by setting a value in each entry having the frequently replicated data-length portion, the value being representative of the frequently replicated data-length portion, so as to eliminate the frequently replicated data-length portion.

25. A method of maintaining a record locator data structure in random access memory of a data storage system also having data storage and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one count-key-data (CKD) record of a logical track of CKD records, the data processor being programmed to access the record locator data structure in the random-access memory for locating a data storage area in the data storage allocated for storing data of the CKD record, the record locator data structure containing entries for the CKD records having data stored in the data storage, at least some but not all of the entries having a respective record modifier portion, the method including updating the record locator data structure to include a new entry for a new CKD record by:

(a) establishing an expected count for the new CKD record;

(b) comparing the count of the new CKD record to the expected count for the new CKD record, and

(i) if the count of the new CKD record does not match the expected count of the new CKD record, storing a record modifier portion indicating the count of the new CKD record of the new entry; and

(ii) if the count of the new CKD record matches the expected count of the new CKD record, not storing a record modifier portion indicating the count of the new CKD record of the new entry.

26. The method of claim 25, which includes determining the expected count for a next CKD record of the logical track from the count of the CKD record of said each entry by incrementing an “

R”

byte of the count of the CKD record of said each entry.

27. The method of claim 25, which further includes compressing the entries by searching for a frequently replicated record modifier portion, and upon finding a frequently replicated record modifier portion, replacing the frequently replicated record modifier portion by setting a value in each entry having the frequently replicated record modifier portion, the value being representative of the frequently replicated record modifier portion, so as to eliminate the frequently replicated record modifier portion.

28. A method of maintaining a record locator data structure in random access memory of a data storage system also having data storage and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data processor being programmed to access the record locator data structure for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing entries for data records having data stored in the data storage, each entry including a fixed-length portion, and at least some but not all of the entries having respective variable-length portions, the method including updating the record locator data structure to include a new entry for a new data record by:

(a) determining whether or not to include a variable length portion in the new entry for the new data record, and

(b) setting a value in the fixed-length portion of the new entry indicating whether or not the new entry includes a variable-length portion.

29. The method of claim 28, which further includes compressing the entries by searching for a frequently replicated variable-length portion, and upon finding a frequently replicated variable-length portion, replacing the frequently replicated variable-length portion by setting a value in the fixed-length portion of each entry having the frequently replicated variable-length portion, the value being representative of the frequently replicated variable-length portion, so as to eliminate the frequently replicated variable-length portion.

30. The method of claim 28, wherein the data records include variable-length data records, and each entry has a variable-length portion indicating data length of the record of the entry when the data length of the record of said each entry fails to match an expected data length.

31. The method of claim 30, wherein the data length of the data record of said each entry becomes the expected data length for a next data record of the logical track.

32. The method of claim 28, wherein the data records are count-key-data (CKD) records, and each entry has a variable-length portion indicating the count of the data record of said each entry when the count of the data record of said each entry fails to match an expected count.

33. The method of claim 32, which includes determining the expected count for a next CKD record of the logical track from the count of the CKD record of said each entry by incrementing an “

R”

byte of the count of the CKD record of said each entry.

34. A method of maintaining a record locator data structure in random access memory of a data storage system also having data storage and at least one processor responsive to data storage access requests for access to data stored in the data storage, each data storage access request specifying at least one data record of a logical track of data records, the data processor being programmed to access the record locator data structure for locating a data storage area in the data storage allocated for storing data of the data record, the record locator data structure containing respective entries for data records having data stored in the data storage, each entry including a fixed-length portion, and at least some but not all of the entries having respective variable-length portions, the method including updating the record locator data structure to include a new entry for a new data record by:

(a) determining whether or not the new entry is to have a variable-length portion, and

(b) storing a fixed-length portion for the new data record in a next address location in a first region of address locations of the random-access memory, and if the new entry is to have a variable-length portion, storing the variable-length portion of the new entry in a next address location in a second region of address locations of the random-access memory.

35. The method as claimed in claim 34, which includes setting record flags in the fixed-length portion of the new entry, wherein one of the record flags indicates whether or not the new entry includes a variable-length portion.

36. The method as claimed in claim 34, wherein the first region of memory addresses and the second region of memory addresses are within a block of memory addresses allocated for storing the entries of the records of the logical track, the first region of memory addresses is aligned at one end of the block, and the second region of memory addresses is aligned at another end of the block, and the method includes storing entries for records of the track in the block so that the first region of memory addresses and the second region of memory addresses each expand toward each other and eventually collide within the block.

37. The method as claimed in claim 36, which further includes compressing the entries when the first region of memory addresses and the second region of memory addresses collide within the block.

38. The method as claimed in claim 34, which includes compressing the entries by searching for a frequently replicated variable-length portion, and upon finding a frequently replicated variable-length portion, replacing the frequently replicated variable-length portion by setting a value in the fixed-length portion of each entry having the frequently replicated variable-length portion, the value being representative of the frequently replicated variable-length portion, so as to eliminate the frequently replicated variable-length portion.

39. The method of claim 34, wherein the data records include variable-length data records, and the method includes storing in each entry a variable-length portion indicating data length of the data record of the entry when the data length of the data record of said each entry fails to match an expected data length.

40. The method of claim 39, wherein the data length of the data record of said each entry becomes the expected data length for a next data record of the logical track.

41. The method of claim 34, wherein the data records are count-key-data (CKD) records, and the method includes storing in each entry a variable-length portion indicating the count of the data record of said each entry when the count of the data record of said each entry fails to match an expected count.

42. The method of claim 41, which includes determining the expected count for a next CKD record of the logical track from the count of the CKD record of said each entry by incrementing an “

R”

byte of the count of the CKD record of said each entry.