Allocation strategies for storage device sets

• US 8,793,463 B2
• Filed: 09/12/2011
• Issued: 07/29/2014
• Est. Priority Date: 09/12/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Moss, Darren, Mehra, Karan, Paleologu, Emanuel
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US13/230,505
• Publication Number:
  US 20130067187A1
• Time in Patent Office: 1,051 Days
• Field of Search: 711/170, 711/112, 711/114, 711/156
• US Class Current: 711/170
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A storage device set may allocate capacity for spaces (e.g., logical volumes) according to an allocation strategy, e.g., allocating capacity from the storage device having the greatest available capacity, or maximizing the distribution of allocated capacity across the storage devices. However, such allocation strategies may be inefficient (e.g., limiting the capability of the storage device set to satisfy subsequent requests with constraints such as a minimum distribution of capacity across several storage devices). The techniques presented herein achieve efficient allocation by first allocating capacity on storage devices having ample available capacity using a round-robin technique, and if such storage devices do not satisfy the capacity request, allocating capacity on storage devices having limited available capacity. Additionally, the techniques presented herein facilitate thin provisioning through capacity reservations, wherein storage devices withhold unallocated storage for particular spaces that may be utilized as a reserve if unreserved capacity is exhausted.

Claims

1. A method of allocating capacity for spaces on a storage device set comprising at least two storage devices accessible to a device having a processor, the method comprising:

executing on the processor instructions configured to, upon receiving a request to allocate capacity for a space;

among the storage devices, identify a spacious storage device subset comprising storage devices having available capacity above an available capacity minimum threshold;

allocate capacity for the space on the storage devices of the spacious storage device subset; and

if the spacious storage device subset does not satisfy the request;

among remaining storage devices, identify a limited storage device subset comprising storage devices having available capacity below the available capacity minimum threshold; and

allocate capacity for the space on the storage devices of the limited storage device subset.

2. The method of claim 1, allocating capacity on the storage devices of a storage device subset comprising:

identifying a sequence of storage devices of the storage device subset according to a round-robin selection;

for respective storage devices and according to the sequence;

allocating an extent on the storage device, and

associating the extent with the space,

until a total capacity of the extents associated with the space satisfies the request.

3. The method of claim 2:

the storage devices of a storage device subset having a storage device order; and

the round-robin selection comprising;

for a second request following a first request;

identifying a last storage device on which capacity was allocated for the first request;

identifying a next storage device following the last storage device according to the storage device order; and

allocating capacity on the storage devices according to the storage device order and beginning with the next storage device.

4. The method of claim 1, allocating capacity on the storage devices of a storage device subset comprising:

among the storage devices of the storage device subset, identify a sequence descendingly ordering the storage devices by available capacity; and

allocating capacity on the storage devices according to the sequence.

5. The method of claim 1, allocating capacity on the storage devices of a storage device subset comprising:

among the storage devices of the storage device subset, identify a sequence ascendingly ordering the storage devices by access rate; and

allocating capacity on the storage devices according to the sequence.

6. The method of claim 5:

the instructions configured to track the access rates of the storage devices as an access rate history; and

identifying the sequence comprising;

upon receiving the request to allocate capacity for the space, sorting the storage devices according to the access rate history.

7. The method of claim 1, the request specifying a storage device distribution constraint selected from a storage device distribution constraint set comprising:

a number of different storage devices;

for storage devices having a storage device type, a number of different storage device types; and

for storage devices located in different locations, a number of different locations of the storage devices.

8. The method of claim 1:

respective spaces created with a provisioned capacity;

respective spaces bound to extents respectively having an extent capacity;

the request comprising a request to access a location in the space that is not bound to an extent; and

allocating capacity for the space on a storage device comprising;

binding an extent allocated on the storage device to a logical address range of the space including the location.

9. The method of claim 1:

before the access, the storage device comprising at least one unbound extent allocated for the space and not bound to a logical address range of the space; and

binding the extent comprising;

binding an unbound extent to the logical address range of the space including the location.

10. The method of claim 9, the provisioned capacities of the spaces exceeding the capacity of the storage devices of the storage device set.

11. The method of claim 10, the instructions configured to, for at least one space:

identify a capacity reservation; and

for respective storage devices;

calculate a capacity reservation size comprising a lesser of;

a remaining provisioned capacity of the space, and

a capacity reservation portion of the capacity reservation for the space on the storage device; and

reduce the available capacity of the storage device by the capacity reservation size.

12. The method of claim 11, allocating the capacity reservation for a space comprising:

upon receiving a request to create a space having a provisioned capacity and a capacity reservation size;

create the space with the provisioned capacity; and

reserve a capacity reservation of the capacity reservation size for the space on at least one storage device.

13. The method of claim 11, allocating an extent on a storage device for a space comprising:

upon allocating an extent for the space, reduce the capacity reservation portion of the reservation capacity for the space on the storage device.

14. The method of claim 13, reducing the capacity reservation portion comprising:

reducing the capacity reservation portion of the reservation capacity for the space on the storage device if;

the remaining provisioned capacity of the space exceeds the capacity reservation portion on the storage device;

or

the storage device has no available capacity.

15. The method of claim 10, comprising:

upon reducing the available capacity of the storage devices of the storage device set below an available capacity minimum threshold, notify an administrator of the available capacity of the storage device set.

16. The method of claim 1, the instructions configured to adjust the available capacity minimum threshold according to the available capacities of the storage devices of the storage device set.

17. The method of claim 1:

the storage device set including at least one unavailable storage device; and

the instructions configured to exclude the unavailable storage device from storage device subsets.

18. The method of claim 1:

the storage device set configured to store data redundantly across at least two storage devices;

the storage device set configured to satisfy accesses to data on an unavailable storage device by accessing redundantly stored data on other storage devices of the storage device set;

the storage device set including at least one unavailable storage device; and

allocating capacity for a space on an unavailable storage device comprising;

allocating the capacity on the unavailable storage device; and

satisfying accesses to the data within the capacity of the unavailable storage device by accessing redundantly stored data on other storage devices of the storage device set.

19. A method of allocating capacity for spaces on a storage device set comprising at least two storage devices accessible to a device having a processor, the method comprising:

sending to the device instructions that, when executed by the processor, cause the device to;

upon receiving a request to create a space with a provisioned capacity and a capacity reservation;

create the space, and

for respective storage devices, reserve a capacity reservation portion for the space; and

upon receiving a request to allocate capacity for the space;

among the storage devices, identify a spacious storage device subset comprising storage devices having available capacity above an available capacity minimum threshold;

for respective storage devices of the spacious storage device subset, allocate at least one extent for the space on the storage devices of the spacious storage device subset;

adjust the capacity reservation portion of the capacity reservation for the space; and

if the spacious storage device subset does not satisfy the request;

among remaining storage devices, identify a limited storage device subset comprising storage devices having available capacity below the available capacity minimum threshold; and

allocate capacity for the space across the limited storage device subset; and

adjust the capacity reservation portion of the capacity reservation for the space.

20. A computer-readable storage medium comprising instructions that, when executed on a processor of a device having access to a storage device set comprising at least two storage devices, allocates storage for respective spaces by:

upon receiving a request to create a space with a provisioned capacity and a capacity reservation;

creating the space;

for respective storage devices, calculating capacity reservation size comprising a lesser of;

a remaining provisioned capacity of the space, and

a capacity reservation portion of the capacity reservation for the space on the storage device; and

reducing the available capacity of the storage device by the capacity reservation size;

upon receiving a request to allocate capacity for a space, the provisioned capacities of the spaces exceeding the capacity of the storage devices of the storage device set, and the request specifying a storage device distribution constraint selected from a storage device distribution constraint set comprising;

a number of different storage devices;

for storage devices having a storage device type, a number of different storage device types; and

for storage devices located in different locations, a number of different locations of the storage devices, allocating capacity by;

among the storage devices, identifying a spacious storage device subset comprising storage devices having available capacity above an available capacity minimum threshold;

allocating capacity for the space on the storage devices of the spacious storage device subset; and

if the spacious storage device subset does not satisfy the request;

among remaining storage devices, identifying a limited storage device subset comprising storage devices having available capacity below the available capacity minimum threshold; and

allocating capacity for the space across the limited storage device subset;

wherein allocating at least one extent on a storage device subset comprises;

identifying a sequence of storage devices of the storage device subset according to a round-robin selection, comprising, for a second request following a first request;

identifying a last storage device on which capacity was allocated for the first request; and

identifying a next storage device following the last storage device according to the storage device order; and

for respective storage devices and according to the sequence beginning with the next storage device;

allocating an extent on the storage device,

associating the extent with the space,

binding the extent to a logical address range of the space, and

if the remaining provisioned capacity of the space exceeds the capacity reservation portion on the storage device and the storage device has no available capacity, reducing the capacity reservation portion of the reservation capacity for the space on the storage device,

until a total capacity of the extents associated with the space satisfies the request;

adjusting an available capacity minimum threshold according to the available capacities of the storage devices of the storage device set; and

upon reducing the available capacity of the storage devices of the storage device set below the available capacity minimum threshold, notify an administrator of the available capacity of the storage device set.