Apparatus, system, and method for allocating storage

• US 8,578,127 B2
• Filed: 09/09/2010
• Issued: 11/05/2013
• Est. Priority Date: 09/09/2009
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Thatcher, Jonathan, Flynn, David
• Primary Examiner(s): SCHNEE, HAL W
• Application Number:
  US12/879,004
• Publication Number:
  US 20110060887A1
• Time in Patent Office: 1,153 Days
• Field of Search: 711/103, 711/171, 711/202, 711/E12.008, 711/E12.014
• US Class Current: 711/202
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• 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 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0626 Reducing size or complexity of storage systems
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0671 In-line storage system

Abstract

An apparatus, system, and method are disclosed for allocating non-volatile storage. The storage device may present a logical address, which may exceed a physical storage capacity of the device. The storage device may allocate logical capacity in the logical address space. An allocation request may be allowed when there is sufficient unassigned and/or unallocated logical capacity to satisfy the request. Data may be stored on the non-volatile storage device by requesting physical storage capacity. A physical storage request, such as a storage request or physical storage reservation, when there is sufficient available physical storage capacity to satisfy the request. The device may maintain an index to associate logical identifiers (LIDs) in the logical address space with storage locations on the storage device. This index may be used to make logical capacity allocations and/or to manage physical storage space.

Claims

1. A method for allocating non-volatile data storage, comprising:

presenting a logical address space to a storage client through a storage interface, the logical address space comprising a plurality of logical identifiers (LIDs);

maintaining an index associating LIDs in the logical address space with respective storage locations on the non-volatile storage device; and

referencing the index to determine whether a client request to allocate logical capacity in the logical address space can be satisfied based on allocations of the LIDs of the logical address space, wherein the client request identifies a set of LIDs in the logical address space, and wherein determining whether the client request can be satisfied comprises determining whether one or more LIDs of the identified set of LIDs are in the index.

2. The method of claim 1, wherein the client request identifies an ordered set of LIDs in the logical address space, and wherein determining whether the client request can be satisfied comprises determining whether one or more LIDS of the identified, ordered set of LIDs are in the index.

3. The method of claim 1, wherein determining whether the client request can be satisfied comprises,

determining an unassigned logical capacity of the logical address space;

and

comparing the unassigned logical capacity to the logical capacity of the client request.

4. The method of claim 1, further comprising:

maintaining allocation entries to indicate allocation of LIDs having no associated storage location; and

determining an unallocated logical capacity using the allocation index,

wherein determining whether the client request can be satisfied comprises comparing the logical capacity of the client request to the unallocated logical capacity.

5. The method of claim 4, wherein the allocation entries are maintained in the index.

6. The method of claim 1, further comprising:

maintaining an unallocated index comprising unallocated LIDs in the logical address space; and

determining that the client request to allocate logical capacity in the logical address space can be satisfied in response to identifying a LID in the unallocated index.

7. The method of claim 1, wherein providing a response comprises one of:

providing allocated LIDs satisfying the client request;

indicating that the request can be satisfied;

indicating that the request cannot be satisfied; and

indicating that LIDs satisfying the client request are allocated.

8. The method of claim 1, wherein the client request comprises a first LID to allocate, and wherein providing the response comprises providing a second, different LID in response to the first LID being allocated.

9. The method of claim 1, the client request pertaining to data to store on the non-volatile storage device, the method further comprises:

storing the data pertaining to the client request at a storage location of the non-volatile storage device; and

associating the storage location with a LID in the index.

10. The method of claim 1, wherein the index comprises one of:

a LID associated with a plurality of storage locations of the non-volatile storage device; and

a storage location associated with a plurality of LIDs.

11. The method of claim 1, wherein the logical address space exceeds a physical storage capacity of the non-volatile storage device.

12. The method of claim 11, further comprising:

receiving a request to allocate physical storage capacity for an allocated LID that is not assigned a storage location on the non-volatile storage device;

determining an available physical storage capacity of the non-volatile storage device;

providing a response indicating whether the available physical storage capacity satisfies the request.

13. The method of claim 12, further comprising, in response to satisfying the request to allocate physical storage capacity for the allocated LID:

storing data corresponding to the allocated LID on a storage location of the non-volatile storage device; and

assigning a physical address for the storage location to the allocated LID in the index.

14. A method for allocating non-volatile storage, comprising:

presenting a logical address space of a non-volatile storage device to a client, the logical address space comprising a plurality of logical identifiers (LIDs), the LIDs being independent of storage locations of the non-volatile storage device, wherein a physical capacity corresponding to the LIDs exceeds a physical storage capacity of the non-volatile storage device, wherein each LID is capable of being mapped to any of the storage locations of the non-volatile storage device;

receiving from the client a request for storage capacity, wherein the request comprises a first LID to allocate; and

providing a second, different LID in the logical address space to the client in response to determining that the first LID is allocated.

15. A non-transitory storage medium comprising machine-readable instructions configured to cause a machine to perform a method for allocating non-volatile storage, the method comprising:

presenting by a non-volatile storage device, a logical address space comprising a plurality of logical identifiers (LIDs) to a client, the LIDs being independent of storage locations of the non-volatile storage device and exceeding a physical storage capacity of the non-volatile storage device;

receiving from the client a request to store data on the non-volatile storage device, the request specifying a LID to allocate to the client;

selecting a different LID in the logical address space to allocate to the client in response to determining that the specified LID is allocated;

storing data of the request on a storage location of the non-volatile storage device; and

associating the LID allocated to the client with the storage location comprising the data of the request.

16. A method for allocating non-volatile storage, the method comprising:

maintaining an index pertaining to allocation operations within a logical address space of a solid-state storage device and to storage operations of the solid-state storage device, wherein the allocation operations within the logical address space pertain to allocating logical identifiers of the logical address space to respective storage clients;

accessing the index to manage storage operations of the solid-state storage device; and

accessing the index to manage an allocated logical capacity supported by the solid-state storage device, wherein a logical identifier included in a client request to allocate logical capacity is determined to be allocated in response to determining that the logical identifier is in the index.

17. The method of claim 16, wherein the index pertaining to allocation operations is stored in a shared datastructure with metadata pertaining to storage operations performed on the solid-state storage device.

18. The method of claim 16, wherein the index pertaining to allocation operations comprises an allocation indicator identifying logical identifiers of the logical capacity that have been allocated, the method further comprising:

using the allocation indicators to respond to an allocation query.

19. An apparatus, comprising:

a logical space management module configured to present a logical address space of a non-volatile storage device that exceeds a physical storage capacity of the non-volatile storage device, the logical address space comprising a plurality of logical identifiers (LIDs) that exceed a physical storage capacity of the non-volatile storage device;

a mapping module configured to maintain an index configured to map LIDs in the logical address space to storage locations of the non-volatile storage device; and

an allocation module configured to respond to a client request for physical storage capacity by referencing the index to determine available physical storage capacity of the non-volatile storage device, wherein the client request comprises one or more logical identifiers, and wherein the allocation module is further configured to determine whether the client request can be satisfied by determining whether the one or more logical identifiers are allocated.

20. The apparatus of claim 19, wherein the allocation module is configured to determine available physical storage capacity by identifying storage locations of the non-volatile storage device that are not assigned to LIDs in the index.

21. The apparatus of claim 19, further comprising a physical capacity allocation module configured to maintain an indicator of available physical storage capacity of the non-volatile storage device responsive to storage operations performed on the non-volatile storage device.

22. The apparatus of claim 21, wherein the physical capacity allocation module is configured to update the indicator of available physical storage capacity in response to a storage operation comprising one or more of:

a storage operation storing data associated with a physical storage capacity reservation, wherein the storing does not require a portion of the associated physical storage capacity reservation;

a storage operation canceling a physical storage capacity reservation; and

a storage operation canceling a portion of a physical storage capacity reservation.

23. The apparatus of claim 19, wherein the mapping module is configured to update an association between a LID and a storage location in response to one or more of:

moving data stored at the storage location to a different storage location of the non-volatile storage device;

the data stored at the storage location being identical to data stored at a second storage location, the updating comprising associating the LID with the second storage location; and

one or more storage locations associated to one or more LIDs are remapped to one or more different LIDs.

24. The apparatus of claim 19, further comprising a physical space reservation module configured to maintain reservations for physical storage capacity, wherein determining available physical storage capacity further comprises accessing the reservations.

25. The apparatus of claim 19, further comprising a physical space reservation module configured to reserve available physical storage capacity of the non-volatile storage device in response to satisfying the client request and to maintain sufficient available physical storage capacity on the non-volatile storage device to satisfy the reservation.

26. The apparatus of claim 19, wherein the client request pertains to data to be stored on the non-volatile storage device, the apparatus further comprising a storage controller configured to store data referenced in the client request on a storage location of the non-volatile storage device, wherein the mapping module is configured to map the storage location to a LID in the index.

27. The apparatus of claim 19, wherein the client request comprises one of:

an amount of logical capacity in the logical address space used to derive the requested physical storage capacity;

one or more LIDs in the logical address space used to derive the requested physical storage capacity;

a request to store data, from which the requested physical storage capacity is derived;

a request to reserve the physical storage capacity; and

a request to reserve the physical storage capacity and to allocate a corresponding logical capacity in the logical address space.