Systems and methods for storage allocation

Patent metadata

Field	Value
Publication number	US-9563555-B2
Application number	US-201313865153-A
Country	US
Kind code	B2
Filing date	Apr 17, 2013
Priority date	Mar 18, 2011
Publication date	Feb 7, 2017
Grant date	Feb 7, 2017

Abstract

Resources of an address space are managed in dynamically sized ranges, extents, sets, and/or blocks. The address space may be divided into regions, each corresponding to a different, respective allocation granularity. Allocating a block within a first region of the address space may comprise allocating a particular number of logical addresses (e.g., a particular range, set, and/or block of addresses), and allocating a block within a different region may comprise allocating a different number of logical addresses. The regions may be configured to reduce the metadata overhead needed to identify free address blocks (and/or maintain address block allocations), while facilitating efficient use of the address space for differently sized data structures.

First claim

We claim:

1. An apparatus, comprising:
a storage controller configured to manage a logical address space of a storage device, and to translate logical identifiers of the logical address space to data stored on the storage device,
wherein the storage controller is configured to segment the logical address space into a plurality of different regions, the regions having different respective allocation granularities that determine a capacity of storage resource allocations within the respective regions, and
wherein the storage controller is further configured to allocate storage resources within the regions of the logical address space in accordance with the respective allocation granularities of the regions, such that the storage controller allocates resource units of a first capacity responsive to allocation operations within a first region of the logical address space and allocates resource units of a second, different capacity responsive to allocation operations within a second region of the logical address space.

2. The apparatus of claim 1 , further comprising an interface of the storage controller configured to provide for specifying a region of the logical address space in which to perform one or more of an allocation operation and a storage operation.

3. The apparatus of claim 1 , further comprising an interface of the storage controller configured to provide information pertaining to the allocation granularities of the regions of the logical address space to a storage client.

4. The apparatus of claim 1 , wherein the different respective allocation granularities of the regions pertain to a data sector size associated with the logical identifiers of the respective regions.

5. The apparatus of claim 1 , wherein the logical identifiers within the respective regions of the logical address space correspond to different respective amounts of physical storage capacity, such that a logical identifier within the first region corresponds to a first amount of physical storage capacity, and a logical identifier within the second region corresponds to a second, different amount of storage capacity.

6. The apparatus of claim 5 , wherein the storage controller is configured to read a data segment associated with a logical identifier stored on the storage device, wherein a size of the data segment corresponds to an amount of physical storage capacity represented by the logical identifier.

7. The apparatus of claim 1 , wherein the storage controller is configured to reallocate a set of logical identifiers corresponding to data stored on the storage device to a different set of logical identifiers.

8. The apparatus of claim 7 , wherein the different set of logical identifiers are within a different region of the logical address space from the set of logical identifiers.

9. The apparatus of claim 7 , wherein each region comprises one or more blocks of logical identifiers, and wherein the storage controller is configured to combine a plurality of blocks allocated within the first region of the logical address space into a single, larger block of logical identifiers within the second region of the logical address space.

10. The apparatus of claim 7 , wherein each region comprises one or more blocks of logical identifiers within the logical address space, and wherein the storage controller is configured to reallocate a block of logical identifiers within a first region of the logical address space as one or more smaller blocks of logical identifiers within a different region of the logical address space.

11. The apparatus of claim 7 , further comprising a log storage module configured to store data on the storage device in association with respective logical identifiers corresponding to the data.

12. The apparatus of claim 11 , wherein the reallocation module is configured to modify the logical identifier associated with a data segment such that the logical identifier associated with the data segment on the storage device is inconsistent with the modified logical identifier, the apparatus further comprising a translation module configured to reference the data segment associated with the inconsistent logical identifier on the storage device by use of the modified logical identifier.

13. The apparatus of claim 12 , wherein the log storage module is configured to store the data segment in association with the modified logical identifier on the storage device in response to grooming a storage division comprising the data segment.

14. A computer program product comprising a non-transitory computer readable storage medium storing computer usable program code executable to perform operations, the operations comprising:
translating logical identifiers of a logical address space to storage addresses of data corresponding to the logical identifiers stored on a non-volatile storage device; and
allocating storage resources within respective allocation regions of the logical address space, each allocation region having a respective granularity that determines a capacity for storage resource allocations within the region, such that
allocating a storage resource within a first allocation region of the logical address space comprises allocating a first capacity of storage resources, and
allocating a storage resource within a second allocation region of the logical address space comprises allocating a second capacity of storage resources, different from the first capacity of storage resources.

15. The computer program product of claim 14 , the operations further comprising:
in response to receiving a request to allocate a storage resource,
selecting an allocation region for the received request, and
allocating a capacity of storage resources corresponding to an allocation granularity of the selected allocation region,
wherein selecting the allocation region comprises one or more of: selecting an allocation region specified in the received request, selecting an allocation region corresponding to an amount of storage resources requested by the received request, selecting an allocation region corresponding to a storage entity associated with the received request, and selecting an allocation region corresponding to a file associated with the received request.

16. The computer program product of claim 14 , further comprising:
allocating a first set of logical identifiers within the first logical allocation region for a storage entity;
translating logical identifiers of the first set of logical identifiers to respective storage addresses of the non-volatile storage device in response to storing data of the storage entity on the non-volatile storage device, such that the first set of logical identifiers reference stored data of the storage entity on the non-volatile storage device; and
moving the storage entity to the second allocation region, by
allocating a second set of logical identifiers within the second allocation region, the second set of logical identifiers different from the first set of logical identifiers, and
translating logical identifiers of the second set to storage addresses storing data of the storage entity on the non-volatile storage device, such that the second set of logical identifiers reference stored data of the storage entity on the non-volatile storage device.

17. The computer program product of claim 16 , wherein the storage entity is moved to the second allocation region based on one or more of: an amount of valid data of the storage entity that is stored on the non-volatile storage device, and a number of logical identifiers allocated to reference stored data of the storage en

Assignees

• Fusion-Io Inc
• Sandisk Technologies Llc

Inventors

• Flynn David
• Piggin Nick
• Talagala Nisha

Classifications

• G06F16/13

  File access structures, e.g. distributed indices (arrangements of input from, or output to, record carriers G06F3/06) · CPC title

• G06F16/188

  Virtual file systems · CPC title

• G06F3/0643

  Management of files · CPC title

• G11C16/349

  Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles · CPC title

• G06F12/0292 Primary

  using tables or multilevel address translation means (G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10) · CPC title