Method and apparatus for allocating erasure coded data to disk storage

• US 8,713,405 B2
• Filed: 11/22/2011
• Issued: 04/29/2014
• 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: Healey, Michael W. Jr., Cordella, David, Beaverson, Arthur J., Bagby, Steven
• Primary Examiner(s): BRITT, CYNTHIA H
• Application Number:
  US13/302,510
• Publication Number:
  US 20130132800A1
• Time in Patent Office: 889 Days
• Field of Search: 714/763, 714/769, 714/770, 711/170, 711/173
• US Class Current: 714/763
• 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. A computer-implemented method comprising:

allocating encoded data objects for storage in a pool of disk storage devices comprising multiple disk drives;

at least some of the encoded objects being generated by different error correction algorithms and allocation is not restricted to a group of drives based on the algorithm utilized to generate the encoded object;

each disk drive is divided into multiple logical storage units, each defined as a partition;

a logical storage unit group (LSU group) comprising a group of partitions extending across a group of disk drives, wherein the partitions of the LSU group are each of the same size and cannot be on the same drive;

the allocating of each encoded data object being performed utilizing a single allocation bitmap that extends across the LSU group to identify available locations for storage of the object, wherein the object is allocated to one available location defined by contiguous bits of the bitmap, or to multiple locations aligned along a common partition boundary allowing a gap of non-contiguous allocation between the two locations.

2. The method of claim 1, wherein:

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

3. The method of claim 2, wherein:

the allocating step includes allocating encoded objects encoded by different error correction algorithms.

4. The method of claim 1, wherein:

the method includes encoding data by different error correction algorithms to generate the encoded objects and maintaining an index which maps the encoded object to its respective error correction algorithm.

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 bitmap to request allocation units aligned with a common partition 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 error correction algorithms.

11. The method of claim 1, including:

providing an index of the encoded data objects which maps each encoded data object to its respective error correction algorithm.

12. The method of claim 1, wherein:

the allocating step includes using an allocation bitmap assigning multiple allocation bits per chunk group of the respective error correction algorithm.

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 12, wherein the allocating step uses a boundary bitmap marking the allocation unit for an initial chunk of the encoded object.

16. The method of claim 1, wherein:

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

17. The method of claim 16, wherein:

the index record includes multiple pointers to the encoded object.

18. A non-transitory 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 error correction algorithm component operable to select, for different incoming data objects, different error correction algorithms for generating encoded data objects; and

a disk storage allocation component for allocating the encoded data objects for storage in a pool of disk storage devices comprising multiple disk drives, at least some of the encoded objects generated by different error correction algorithms being allocated to the same or a different group of drives that is not based on the algorithm utilized to generate the encoded object;

wherein each disk drive is divided into multiple logical storage units, each defined as a partition;

a logical storage unit group (LSU group) comprising a group of partitions extending across a group of disk drives wherein the partitions of the LSU group are of each of the same size and cannot be on the same drive;

the allocation component utilizing a single allocation bitmap that extends across the LSU group to identify available locations for storage of the object, wherein the object is allocated to one available location defined by contiguous bits of the bitmap, or to multiple locations aligned along a common partition boundary allowing a gap of non-contiguous allocation between the two locations.

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

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

22. The storage system of claim 20, wherein:

the allocation bitmap assigns multiple bits per chunk group of the respective error correction algorithm.

23. The storage system of claim 20, including:

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

24. In a computing environment for locating data storage, a data structure comprising an allocation bitmap, stored on a non-transitory computer-readable medium, to request available allocation units for storing encoded data objects in a pool of disk storage devices comprising multiple disk drives;

at least some of the encoded objects being generated by different error correction algorithms and allocation is not restricted to a group of drives based on the algorithm utilized to generate the encoded object;

each disk drive is divided into multiple logical storage units, each defined as a partition;

a logical storage unit group (LSU group) comprising a group of partitions extending across a group of disk drives, wherein partitions of the LSU group are each of the same size and cannot be on the same drive;

the single allocation bitmap extends across the LSU group to identify available locations for storage of the object, the bitmap including multiple available locations aligned along a common boundary allowing a gap of non-contiguous allocation between the two locations.