APPARATUS, SYSTEM, AND METHOD FOR ALLOCATING STORAGE

• US 20110060887A1
• Filed: 09/09/2010
• Published: 03/10/2011
• 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: Flynn, David, Thatcher, Jonathan
• Granted Patent: US 8,578,127 B2
• Time in Patent Office: Days
• US Class Current: 711/171
• 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 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;

referencing the index to determine whether a client request to allocate logical capacity in the logical address space can be satisfied; and

providing a response indicating whether the client request can be satisfied.

2. The method of claim 1, 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.

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

4. 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 requested logical capacity.

5. The method of claim 1, further comprising:

maintaining allocation entries to indicating 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 requested logical capacity to the unallocated logical capacity.

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

7. The method of claim 1, further comprising:

maintaining an unallocated index comprising unallocated LIDs in the logical address space,

wherein determining comprises identifying a LID in the unallocated index.

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

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

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

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

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

13. The method of claim 12, 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.

14. The method of claim 13, in response to satisfying the request

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

and

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

15. A method for managing physical capacity in a non-volatile storage, comprising:

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

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

responding to a client request for physical storage capacity by referencing the index to determine available physical storage capacity of the solid-state storage device.

16. The method of claim 15, wherein determining available physical storage capacity comprises identifying storage locations of the non-volatile storage device that are not assigned to LIDs in the logical address space.

17. The method of claim 15, further comprising:

maintaining an indicator of the available physical storage capacity of the non-volatile storage device responsive to performing storage operations on the non-volatile storage device.

20. The method of claim 15, further comprising:

maintaining reservations for physical storage capacity,

wherein determining available physical storage capacity further comprises accessing the reservations.

21. The method of claim 15, further comprising:

reserving physical storage capacity in response to satisfying the client request; and

maintaining sufficient physical storage capacity on the non-volatile storage device to satisfy the reservation.

22. The method of claim 15, wherein the client request pertains to data to be stored on the non-volatile storage device, the method further comprising one of:

storing the data referenced in the request on a storage location of the non-volatile storage device and associating the storage location with a LID in the index, in response to satisfying the client request; and

notifying the client when the request cannot be satisfied.

23. The method of claim 15, 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.

18. The method of clam 17, further comprising:

updating the indicator of the available physical storage capacity of the non-volatile storage request in response to a storage operation comprising one 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.

19. The method of clam 15, further comprising:

updating an association of a LID and a storage location on the non-volatile storage device in response to one 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. A method for allocating non-volatile storage, 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 for storage capacity;

selecting a LID in the logical address space to allocate to the client in response to the request;

reserving physical storage capacity on the non-volatile storage device for the allocated LID; and

providing the LID to the client.

25. 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;

selecting a LID in the logical address space to allocate to the client in response to the request;

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.

26. A method for allocating non-volatile storage a solid-state storage device, the method comprising:

maintaining an index pertaining to allocation operations performed on a solid-state storage device and to storage operations of the solid-state storage device;

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

accessing the index to manage a allocated logical capacity supported by the solid-state storage device.

27. The method of claim 26, wherein metadata pertaining to allocation operations and the metadata pertaining to storage operations are stored in a shared datastructure.

28. The method of claim 26, wherein allocation metadata comprises an allocation indicator identifying LIDS of the logical capacity that have been allocated, the method further comprising:

using the allocation indicators to respond to an allocation query.