SYSTEMS AND METHODS FOR STORAGE ALLOCATION

• US 20130227236A1
• Filed: 04/17/2013
• Published: 08/29/2013
• Est. Priority Date: 03/18/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Piggin, Nick, Talagala, Nisha
• Granted Patent: US 9,563,555 B2
• Time in Patent Office: Days
• US Class Current: 711/165
• 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. A method, comprising:

a computing device providing an address space of a storage device, the address space configured such that at least two or more addresses of the address space are associated with a different physical storage capacity; and

allocating one of the at least two or more addresses to a storage client in response to a storage request.

2. The method of claim 1, wherein the allocation granularity pertains to allocation of logical addresses within the address space.

3. The method of claim 1, wherein the allocation granularity pertains to data segment size corresponding to one or more logical address of the address space.

4. The method of claim 1, further comprising allocating a logical identifier within a first section of the address space corresponding to a first sector size on the storage device and allocating a logical identifier within a different section of the address space corresponding to a different sector size on the storage device.

5. The method of claim 1, further comprising:

allocating storage resources within a selected section of the address space in response to a request from a storage client; and

selecting the section based on one or more of;

a size of data associated with the request, a size of a data structure associated with the request, a size of a storage entity associated with the request, a file associated with the request, an application associated with the request, a parameter of the request, a storage client associated with the request, an input/output (I/O) control parameter, an fadvise parameter, and availability of unallocated logical addresses within the sections.

6. The method of claim 1, wherein dividing the address space comprises partitioning logical addresses within the address space into an identifier portion and an offset portion, wherein relative sizes of the identifier portions to the offset portions vary between the sections.

7. The method of claim 6, further comprising:

moving data stored on the storage device to a different section of the address space, wherein moving the data comprises associating the data with a different logical address than a logical address stored with the data on the storage device.

8. The method of claim 7, further comprising updating persistent metadata of the data to reference the different logical address in response to relocating the data on the storage device.

9. An apparatus, comprising:

a translation module configured to manage a logical address space of a storage device;

a partitioning module configured to segment the logical address space into a plurality of different regions, the individual regions having a different respective allocation granularity; and

an allocation module configured to allocate logical identifiers within the regions in accordance with the allocation granularities of the regions.

10. The apparatus of claim 9, further comprising an interface module 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.

11. The apparatus of claim 9, further comprising an interface module configured to provide information pertaining to the allocation granularities of one or more of the regions to a storage client.

12. The apparatus of claim 9, wherein the different respective allocation granularities of the regions pertain to one or more of:

a logical identifier block size for allocation operations performed within the respective regions and a data sector size associated with the logical identifiers of the respective regions.

13. The apparatus of claim 9, wherein the allocation module is configured to associate logical identifiers within the logical address space with one of a plurality of data sector sizes.

14. The apparatus of claim 13, further comprising a data read module configured to read a data segment associated with a logical identifier on the storage device, wherein a size of the data segment corresponds to a data sector size associated with the logical identifier.

15. The apparatus of claim 9, further comprising a reallocation module configured to reallocate a set of logical identifiers corresponding to data stored on the storage device to a different set of logical identifiers.

16. The apparatus of claim 10, wherein the reallocation module is configured to modify a size of a block of logical identifiers associated with the data, and wherein the reallocation module is configured to move one or more of the logical identifiers to another region of the logical address space.

17. The apparatus of claim 10, wherein each region comprises one or more blocks of logical identifiers within the logical address space, and wherein the reallocation module is configured to combine a plurality of blocks allocated within a first region of the logical address space into a single, larger block of logical identifiers within a different region of the logical address space.

18. The apparatus of claim 10, wherein each region comprises one or more blocks of logical identifiers within the logical address space, and wherein the reallocation module 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.

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

20. The apparatus of claim 19, 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.

21. The apparatus of claim 20, 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.

22. A computer program product comprising a computer readable storage medium storing computer usable program code executable to perform operations, the operations comprising:

associating logical addresses of an address space with respective sector sizes, wherein the sector size associated with a logical address corresponds to a physical storage capacity on a storage device corresponding to the logical address;

determining a sector size of one of the logical addresses in response to a request; and

performing a storage operation on the storage device in accordance with the determined sector size.

23. The computer program product of claim 22, the operations further comprising selecting a sector size for the logical address based on one or more of a file associated with the logical address, an application associated with the logical address, the storage client associated with the logical address, an input/output (I/O) control parameter, and an fadvise parameter.

24. The computer program product of claim 22, the operations further comprising determining an available physical storage capacity of the storage device based on sector sizes of logical addresses of the address space that are associated with valid data on the storage device.

25. The computer program product of claim 22, the operations further comprising assigning a different respective sector size to each of a plurality of segments of the address space, wherein determining the sector size of the logical address comprises associating the logical address with one of the segments.