METHOD AND APPARATUS FOR ALLOCATING ERASURE CODED DATA TO DISK STORAGE

• US 20130132800A1
• Filed: 11/22/2011
• Published: 05/23/2013
• Est. Priority Date: 11/22/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: SimpliVity Corporation (Hewlett-Packard Enterprise Company)
• Inventors: Cordella, David, Beaverson, Arthur J., Bagby, Steven, HEALEY, Michael W. Jr.
• Granted Patent: US 8,713,405 B2
• Time in Patent Office: Days
• US Class Current: 714/769
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• 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/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Allocation process that allows erasure coded data to be stored on any of a plurality of disk drives, in a pool of drives, so that the allocation is not tied to a fixed group of drives. Still further, the encoded data can be generated by any of multiple different erasure coding algorithms, where again storage of the encoded data is not restricted to a single group of drives based on the erasure algorithm being utilized to encode the data. In another embodiment, the encoded data can be “stacked” (aligned) on select drives to reduce the number of head seeks required to access the data. As a result of these improvements, the system can dynamically determine which one of multiple erasure coding algorithms to utilize for a given incoming data block, without being tied to one particular algorithm and one particular group of storage devices as in the prior art.

Claims

1. Computer-implemented method for locating data on storage comprising computer-executable acts of:

allocating for storage on the same or different devices in a pool of disk storage devices, a plurality of encoded data objects encoded by the same or different erasure codes;

for each encoded object to be stored on multiple logical storage units, utilizing an allocation bitmask as a single request for available allocation units to store the respective encoded object on the multiple logical storage units, wherein the allocation bitmask spans the multiple logical storage units and includes a gap aligned with a starting partition boundary for the encoded object being stored.

2. The method of claim 1, wherein:

the allocating step includes allocating the encoded objects on different devices.

3. The method of claim 2, wherein:

the allocating step includes allocating encoded objects encoded by different erasure codes.

4. The method of claim 1, wherein:

the allocating step includes allocating encoded objects encoded by different erasure codes.

5. The method of claim 1, wherein:

the allocating step includes allocating multiple encoded objects on the same logical storage unit.

6. The method of claim 1, wherein:

the allocating step includes allocating multiple encoded objects on the same logical storage unit group.

7. The method of claim 1, including:

using the allocation bitmask to request allocation units aligned with a logical storage unit boundary.

8. The method of claim 1, wherein:

the object size of the data being encoded is fixed.

9. The method of claim 1, wherein:

the object size of the data being encoded is variable.

10. The method of claim 1, wherein:

the data objects are encoded by different categories of erasure codes.

11. The method of claim 1, including:

providing an index of the encoded data objects which maps each encoded data object to its respective erasure code.

12. The method of claim 1, wherein:

the allocating step includes using an allocation bitmap marking the available allocation units.

13. The method of claim 12, wherein:

the allocation bitmap maps to a logical address space.

14. The method of claim 13, wherein:

a logical object number (LON) defines a pointer to the encoded object.

15. The method of claim 1, wherein:

a pointer to the encoded object is stored in an index record.

16. The method of claim 15, wherein:

the index record includes multiple pointers to the encoded object.

17. The method of claim 12, wherein the allocating step uses a boundary bitmap marking the allocation unit for an initial chunk of the encoded object.

18. A computer-readable medium having stored thereon instructions which perform, when loaded into a computer, the method steps according to claim 1.

19. A programmable logic configured to implement the method steps according to claim 1.

20. A data storage system comprising:

an erasure coding algorithm selection component operable to select, for different incoming data objects, different erasure coding algorithms for generating encoded data objects; and

a disk storage allocation component for allocating the encoded data objects encoded by the different algorithms to any available allocation units on the same or different devices in a pool of disk storage devices.

21. The storage system of claim 20, further comprising:

the pool of disk storage devices for storing the encoded data.

22. The storage system of claim 20, wherein:

the disk storage allocation component utilizes an allocation bitmask to request, for each encoded data object, available storage units for storing the encoded object across one or multiple logical storage units of a logical storage unit group that spans multiple devices in the pool, and wherein the bitmask includes a gap allowing the encoded object to be stored on multiple logical storage units on at least one device in the pool.

23. The storage system of claim 20, including:

an index of the encoded data objects which maps each encoded data object to its respective erasure coding algorithm.

24. In a computing environment for locating data storage, a data structure comprising an allocation bitmask to request available allocation units for storing encoded objects across one or multiple logical storage units, the encoded data objects being encoded in different erasure codes, the allocation bitmask spanning multiple logical storage units across a plurality of disk drives, and the bitmask including a gap aligned with a starting partition boundary for the encoded object being stored where the available allocation units are requested across multiple logical storage units.