Storage media data structure system and method

• US 7,237,062 B2
• Filed: 04/02/2004
• Issued: 06/26/2007
• Est. Priority Date: 04/02/2004
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Inventors: Roberson, Randy L., Lubbers, Clark E.
• Primary Examiner(s): Verbrugge; Kevin
• Application Number:
  US10/817,264
• Publication Number:
  US 20050223156A1
• Time in Patent Office: 1,180 Days
• Field of Search: None
• US Class Current: 711/114
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0683 Plurality of storage devices

Abstract

Disclosed is a data storage architecture employing a plurality of data grids each comprising an array of equal capacity data storage blocks organized into a plurality of rows and a plurality of columns such that each column corresponds to a storage domain in a data storage system and each row of the plurality of rows corresponds to a plurality of data storage blocks, one data storage block from each column of the plurality of columns at the same physical address, with the plurality of rows each having a plurality of contiguous data storage blocks in each domain. Capacity grids are produce by applying one of a plurality of sparing versions that designate at least one data storage block in each row of the grid is designated as spare, Defined within each capacity grid are one or more data storage units. Each data storage unit reflects a storage format, such as a RAID level, and defines data storage blocks, mirror data blocks, and parity data blocks depending upon storage the format and can provide fault tolerance in the event of a domain failure. User data is stored exclusively in a first portion of the grid and parity data, if any, is exclusively stored in a second portion of the grid, providing optimized performance. Data access employs metadata that may comprise grid and storage unit descriptors, data storage unit format, and a sparing table.

Claims

1. A method of storing data in a grid-based data storage system comprising:

defining an array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains fewer than a total available number of storage domains; and

allocating each of the data storage units for storing either user data entirely or fault tolerance data entirely.

2. The method of claim 1 further comprising aligning a base address of each data storage unit allocated for storing user data with an address defined by a multiple of a size of the storage blocks.

3. The method of claim 1 further comprising defining a pointer that identifies a selected data storage unit.

4. The method of claim 1 wherein the fault tolerance data is characterized as either mirror data or parity data.

5. The method of claim 1 further comprising defining a sparing table that designates at least one data block in each row of said array as a spare data block.

6. The method of claim 5 further comprising defining said sparing table to contain a plurality of sparing versions that each specify a different storage domain as containing said at least one spare data block in each row.

7. The method of claim 1 further comprising creating a metadata entry that identifies each data storage unit and the respective array of a plurality of arrays in which each data storage unit exists.

8. The method of claim 7 wherein said metadata entry further comprises an entry indicating a storage format of each data storage unit.

9. A grid-based data storage system comprising an array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains fewer than a total available number of storage domains, wherein each data storage unit is individually allocated for storing either user data entirely or fault tolerance data entirely.

10. The data storage system of claim 9 further comprising a plurality of spare storage blocks that are allocatable for storing data in the respective data storage units.

16. The data storage system of claim 9 wherein the data storage blocks are of equal capacity.

17. The data storage system of claim 9 wherein within a particular row, a data storage block in a first domain has the same logical address as a data storage block in a second domain.

18. The data storage system of claim 9 wherein the array is adapted for storing data in the data storage blocks in a selected storage format by predetermined arrangements of user data, mirror data, and parity data associated with each of a plurality of selectable storage formats.

19. The data storage system of claim 18 wherein the predetermined arrangement defines at least one row in the array that contains no mirror or parity data in the data storage blocks.

20. The data storage system of claim 19 wherein the array is adapted for storing data in a RAID 5 or RAID 6 storage format.

21. The data storage system of claim 9 further comprising metadata defining a pointer for identifying a selected data storage unit.

22. The data storage system of claim 9 wherein a base address of each data storage unit allocated for storing user data is aligned with an address defined by a multiple of a size of the storage blocks.

23. The data storage system of claim 9 wherein the fault tolerance data comprises either mirror data or parity data.

11. A method of storing data in a grid-based data storage system comprising:

defining an array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains fewer than a total available number of storage domains;

allocating each of the data storage units for storing either user data entirely or fault tolerance data entirely in accordance with a selected first storage format; and

reallocating the data storage units for storing either user data entirely or fault tolerance data entirely in accordance with a selected second storage format if the number of data storage units in the first storage format is less than or equal to the number of data storage units in the second storage format.

12. The method of claim 11 further comprising:

defining a second array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains; and

allocating additional data storage units in the second array if the number of data storage units in the first storage format is greater than the number of data storage units in the second storage format.

13. The method of claim 11 comprising:

determining the data storage format of said array;

identifying an inaccessible storage domain accessing a sparing table that specifies at least one spare data block in each row of said array;

accessing metadata corresponding to said data storage format that specifies the location and content of each data block in said array; and

regenerating or copying data corresponding to each non-accessible data storage block to the respective spare data block.

14. A data structure stored on a storage medium having an array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains fewer than a total available number of storage domains, the data structure comprising a pointer that when multiplied by a storage capacity of said data storage blocks and by the number of rows of data storage units allocated for storing user data, and to which an offset, if any, is added, produces a base address in each storage domain.

15. A method of accessing data in a data storage system comprising:

defining an array of equal capacity data storage units, each data storage unit defined as a grouped plurality of data storage blocks from separate storage domains fewer than a total available number of storage domains;

determining a domain and a physical address for at least one data storage block by applying an array pointer value to determine a base address of said array, applying a data storage unit pointer value to determine at least one domain to be accessed and to determine a row such that the row number minus one is multiplied by a capacity of said storage blocks and added to a base address to produce a physical address; and

issuing an access command to said at least one domain that includes said physical address.