Systems and methods for storage allocation

• US 9,563,555 B2
• Filed: 04/17/2013
• Issued: 02/07/2017
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Flynn, David, Piggin, Nick, Talagala, Nisha
• Primary Examiner(s): YU, JAE UN
• Application Number:
  US13/865,153
• Publication Number:
  US 20130227236A1
• Time in Patent Office: 1,392 Days
• Field of Search: 711/103
• US Class Current: 1/1
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0292 using tables or multilevel address translation means G06F12/023 takes precedence; address translation in virtual memory systems G06F12/10
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/188 Virtual file systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/06 Auxiliary circuits, e.g. for writing into memory
• CPC Class Codes: G11C 16/26 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles

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.

Claims

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 entity.

18. The computer program product of claim 16, wherein data of the storage entity is appended to a log on the non-volatile storage device, and wherein moving the storage entity to the second region further comprises appending a persistent note to the storage log to associate logical identifiers of the second set with the data of the storage entity appended to the log.

19. The computer program product of claim 18, wherein the data of the storage entity is appended to the log together with persistent translation metadata that associates the appended data with logical identifiers of the first set, and wherein the persistent note appended to the log is configured to replace the persistent translation metadata appended with the data of the storage entity.

20. The computer program product of claim 16, further comprising maintaining a forward map comprising translations between logical identifiers and data stored on the non-volatile storage device, wherein moving the storage entity to the second region comprises modifying the forward map to replace translations between storage addresses of the stored data of the storage entity and logical identifiers of the first set with translations to logical identifiers of the second set.

21. The computer program product of claim 16, the operations further comprising:

storing data on the non-volatile storage medium together with persistent metadata configured to associate the stored data with respective logical identifiers, wherein data of the storage entity is stored with persistent metadata configured to associate the stored data of the storage entity with logical identifiers of the first set;

writing a persistent metadata note on the non-volatile storage device in response to moving the storage entity to the second region, the persistent metadata note configured to associate the stored data of the storage entity with logical identifiers of the second set; and

rebuilding translations between logical identifiers and data stored on the non-volatile storage device by use of the persistent metadata stored with the data on the non-volatile storage device, wherein rebuilding the forward map comprises associating the stored data of the storage entity with logical identifiers of the second set based on the persistent metadata note written to the non-volatile storage medium.

22. A method, comprising:

translating logical identifiers of a logical address space to respective storage locations of a non-volatile storage device by use of a forward map, the respective storage locations being used to store data associated with the logical identifiers; and

allocating storage resources for objects to be stored on the non-volatile storage device, wherein allocating storage resources for an object comprises;

selecting one of a plurality of allocation regions within the logical address space for the object, each allocation region having a respective granularity, such that a capacity of a storage resource allocation within a first one of the plurality of allocation regions differs from a capacity of a storage resource allocation within a second one of the plurality of allocation regions, and

allocating storage resources for the object within the selected allocation region of the logical address space, wherein allocating the storage resources comprises allocating a first logical identifier within the selected allocation region of the logical address space, and translating the first logical identifier to a storage location of stored data of the object on the non-volatile storage device.

23. The method of claim 22, wherein the allocation region is selected based on one or more of:

an allocation request pertaining to the object, a physical storage capacity required to store data of the object, a logical capacity required to reference data of the object, and a block size for the object.

24. The method of claim 22, wherein logical identifiers of the first allocation region correspond to a first amount of physical storage capacity on the non-volatile storage device, and wherein logical identifiers of the second allocation region correspond to a second amount of physical storage capacity on the non-volatile storage device, different from the first amount.

25. The method of claim 22, wherein data of the object is stored within a segment of a log on the non-volatile storage device, the segment comprising persistent metadata configured to associate the segment with the first logical identifier, the method further comprising moving the storage entity to the second allocation region of the logical address space, by

allocating a second logical identifier within the second region of the logical address space for the storage entity;

modifying the forward map to translate the second logical identifier to a storage location of the segment on the non-volatile storage device; and

appending a persistent note to the storage log to record the translation between the second logical identifier and the storage location of the storage segment.