Metadata for a grid based data storage system

• US 7,594,075 B2
• Filed: 10/20/2004
• Issued: 09/22/2009
• Est. Priority Date: 10/20/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 Edward
• Primary Examiner(s): Nguyen; Than
• Application Number:
  US10/969,580
• Publication Number:
  US 20060085594A1
• Time in Patent Office: 1,798 Days
• Field of Search: None
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Metadata architecture and associated methodology for a data storage system employing a grid-based storage capacity wherein each grid defines a storage unit in terms of a plurality of storage domains along one axis against one or more rows of a plurality of storage stripes along another axis, and wherein a grid grouping of two or more grids defines a sheet of data storage capacity. The metadata comprises identification information stored in a memory space characterizing an allocation status of the sheets in the storage capacity. A method is provided for allocating memory for the grid-based storage capacity comprising determining whether the allocation is associated with an existing logical device. If the determining step is associated with an existing logical device, then a logical device allocation map and a sheet allocation table are accessed to allocate a selected storage unit. Otherwise, a sheet allocation descriptor and a sheet allocation map are accessed to allocate a selected storage unit. A method is provided for transferring data for the grid-based storage capacity comprising accessing a logical device allocation map and a drive organization table to transfer data to or from a selected storage unit.

Claims

1. An apparatus comprising:

a grouping of stripes of storage capacity across a plurality of storage domains, wherein same-size groupings define respective sheets of data storage capacity; and

a data structure, stored in a computer readable medium, that includes a table of values indexed by a sheet identifier, the data structure reflecting data transaction activity by identifying whether each of the respective sheets is allocated.

2. The apparatus of claim 1 wherein the data structure comprises a sheet allocation map characterized by a bit array indicating whether each of the sheets is allocatable.

3. The apparatus of claim 2 wherein the data structure comprises a sheet allocation descriptor indicating the number of allocatable sheets.

4. The apparatus of claim 3 wherein the sheets are arranged into a plurality of zones, and wherein the sheet allocation descriptor indicates the number of allocatable sheets per zone.

5. The apparatus of claim 1 wherein the data structure comprises a storage unit descriptor identifying a reference logical block address for a selected grouping.

6. The apparatus of claim 5 wherein the storage unit descriptor comprises a book identification that identifies storage domains for a selected grouping.

7. The apparatus of claim 6 wherein the storage unit descriptor comprises a unique storage unit number for each grouping in a selected book.

8. The apparatus of claim 5 wherein the storage unit descriptor comprises fault tolerance information.

9. The apparatus of claim 8 wherein the fault tolerance information comprises a drive organization indicator defining an ordered scheme of implementing spare storage domains.

10. The apparatus of claim 9 wherein a sheet version defines which storage domains are designated as spares, and wherein the data structure comprises a drive organization table characterized as an array of all permutations of book identifications, drive organizations, and sheet versions.

11. The apparatus of claim 8 wherein the fault tolerance information comprises a redundant array of independent drives (RAID) level.

12. The apparatus of claim 5 wherein the data structure comprises a logical device allocation map characterized by an array of storage unit descriptors for each logical device in the array.

13. The apparatus of claim 12 wherein the data structure comprises a storage unit allocation descriptor characterized by an array of logical device indices indicating the number of sheets allocated to each of the logical devices.

14. The apparatus of claim 13 wherein the storage unit allocation descriptor indicates the number of groupings allocated to each of the logical devices.

15. The apparatus of claim 12 wherein the data structure comprises a sheet allocation table characterized by an array of sheet indices indicating the logical device to which each sheet is allocated.

16. The apparatus of claim 15 wherein the sheet allocation table comprises fault tolerance information.

17. A data structure stored in a computer readable medium for a data storage system employing a grid-based storage capacity defining a storage unit in terms of a plurality of storage domains against one or more rows of a plurality of storage stripes, and groupings of two or more storage units defining respective sheets of data storage capacity arranged in a plurality of zones, the data structure comprising a sheet allocation map, characterized as a bit array associated with whether each of the sheets is allocatable, and a sheet allocation descriptor summarizing the sheet allocation map in terms of a number of allocatable sheets and a number of allocatable sheets per zone.

18. A data structure stored in a computer readable medium for a data storage system employing a grid-based storage capacity defining a storage unit in terms of a plurality of storage domains against one or more rows of a plurality of storage stripes, and groupings of two or more storage units defining respective sheets of data storage capacity, the data structure comprising indicia that identify whether each of the respective sheets of storage capacity are allocated in its entirety, and a storage unit descriptor that, for a selected storage unit, identifies:

(a) a reference logical block address, (b) a book identification defining contributing storage domains of the plurality, (c) a unique storage unit number with respect to storage units in the same book, and (d) a redundant array of independent drives (RAID) level.

19. A data structure stored in a computer readable medium for a data storage system employing a grid-based storage capacity defining a storage unit in terms of a plurality of storage domains against one or more rows of a plurality of storage stripes, and groupings of two or more storage units defining respective sheets of data storage capacity, the data structure comprising:

indicia that identify whether each of the respective sheets of storage capacity are allocated in its entirety;

a storage unit descriptor that, for a selected storage unit, identifies;

(a) a reference logical block address, (b) a book identification defining contributing storage domains of the plurality, (c) a unique storage unit number with respect to storage units in the same book, and (d) a drive organization defining an ordered scheme of implementing spare storage domains; and

a drive organization table characterized by all permutations of book identifications, drive organizations, and sheet versions defining which storage domains are designated as spares.

20. A method comprising:

receiving an allocation request in a grid-based storage system in which a storage unit is defined by rows of a plurality of stripes of storage capacity across a plurality of storage domains, wherein groupings of same-size storage units define respective sheets of data storage capacity; and

indexing a data structure, stored in memory, according to a sheet identifier to determine an allocation status of the respective sheet.