Apparatus, system, and method for allocating storage

Patent metadata

Field	Value
Publication number	US-9606914-B2
Application number	US-201414533779-A
Country	US
Kind code	B2
Filing date	Nov 5, 2014
Priority date	Sep 9, 2009
Publication date	Mar 28, 2017
Grant date	Mar 28, 2017

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.

First claim

What is claimed is:

1. A method, comprising:
storing data units on a non-volatile storage device, the data units associated with logical identifiers of a logical address space, wherein storing the data units on the non-volatile storage device comprises,
writing data corresponding to the data units on storage locations of the non-volatile storage device, and
recording entries in an index, the entries configured to associate the logical identifiers of the data units with storage locations of data corresponding to the data units stored on the non-volatile storage device;

determining whether a client request comprising a request to allocate one or more logical identifiers of the logical address space can be satisfied based on the index; and
providing a response indicating whether the client request can be satisfied.

2. The method of claim 1 , wherein the client request comprises a request to allocate a particular logical identifier of the logical address space, and wherein determining whether the client request can be satisfied comprises determining whether the index comprises an entry corresponding to the particular logical identifier.

3. The method of claim 1 , wherein recording the entries comprises recording an entry configured to associate a particular logical identifier with a particular storage location, and wherein recording the entry comprises one or more of:
creating the entry in the index;
storing the entry in volatile memory of a computing device;
storing the entry in a portion of the index maintained in the volatile memory of the computing device;
storing the entry on the non-volatile storage device;
including the entry in a header of a packet stored within the particular storage location, the header configured to associate the particular logical identifier with a data segment of the packet; and
writing persistent metadata configured to associate the particular logical identifier with the particular storage location on the non-volatile storage device.

4. The method of claim 1 , further comprising recording allocation entries in the index, each allocation entry representing a contiguous range of one or more logical identifiers of the logical address space that are available for allocation, wherein the client request comprises a request to allocate a specified number of logical identifiers of the logical address space, and wherein determining whether the client request can be satisfied comprises identifying an allocation entry that represents a contiguous range of logical identifiers having a size that is greater than or equal to the specified number.

5. The method of claim 1 , further comprising recording entries in the index representing logical identifiers that are allocated but are not associated with valid data stored on the non-volatile storage device, wherein the client request comprises a request to allocate a particular logical identifier, and wherein determining whether the client request can be satisfied comprises determining whether the index comprises an entry corresponding to the particular logical identifier.

6. The method of claim 5 , further comprising allocating a set of logical identifiers in response to the client request, wherein allocating the set of logical identifiers comprises one or more of:
creating one or more entries in the index configured to indicate that the set of logical identifiers are allocated; and
updating one or more entries of the index to indicate that the set of logical identifiers are allocated.

7. The method of claim 1 , further comprising:
determining an amount of available physical storage capacity on the non-volatile storage device based on an amount of physical storage capacity referenced by the entries recorded in the index,
wherein the client request comprises a request to allocate a particular amount of physical storage capacity of the non-volatile storage device, and wherein determining whether the client request can be satisfied comprises comparing the particular amount of physical storage capacity to the determined amount of available physical storage capacity on the non-volatile storage device.

8. The method of claim 1 , further comprising:
determining an amount of available physical storage capacity on the non-volatile storage device based on associations between logical identifiers and storage locations recorded in the index; and
recording the determined amount of available physical storage capacity in storage metadata pertaining to the non-volatile storage device in response to one or more of one:
creating an association between a logical identifier and a storage location of the non-volatile storage device in the index, and
invalidating an existing association between a particular logical identifier and a storage location recorded in the index, wherein the existing association is invalidated in response to one or more of deallocation of the particular logical identifier, a TRIM message pertaining to the particular logical identifier, and deletion of the particular logical identifier.

9. The method of claim 1 , wherein the client request comprises a request to write a data unit on the non-volatile storage device, and wherein providing the response to the request comprises one or more of:
allocating a logical identifier of the logical address space;
storing data corresponding to the data unit of the client request on a particular storage location of the non-volatile storage device; and
recording an association between the allocated logical identifier and the particular storage location in an entry of the index.

10. The method of claim 1 , wherein the client request comprises a request to write one or more data units on the non-volatile storage device, the one or more data units corresponding to a particular amount of physical storage capacity, wherein determining whether the client request can be satisfied comprises:
determining an amount of available physical storage capacity on the non-volatile storage device; and
comparing the determined amount of available physical storage capacity to the particular amount of physical storage capacity.

11. The method of claim 10 , wherein determining the amount of available physical storage capacity on the non-volatile storage device comprises:
determining an amount of physical storage capacity that is currently in use to store valid data based on associations between logical identifiers and storage locations of the non-volatile storage device recorded in the index; and
subtracting the determined amount of physical storage capacity that is currently in use to store valid data from a storage capacity threshold.

12. A non-transitory storage medium comprising instructions configured to cause a computing device to perform operations, the operations comprising:
maintaining storage metadata pertaining to a logical address space comprising a plurality of logical identifiers, wherein maintaining the storage metadata comprises,
recording translation metadata configured to associate logical identifiers of the logical address space with data stored on a storage device, and
recording allocation metadata configured to identify logical identifiers of the logical address space that are unavailable for allocation;

receiving a request to allocate one or more logical identifiers of the logical address space;
determining whether the request can be satisfied based on whether the one or more logical identifiers are associated with data stored on the storage device by the translation metadata and/or are identified as unavailable for allocation by the allocation metadata; and
providing a response indicating whether the request can be satisfied.

Assignees

• Sandisk Technologies Llc

Inventors

• Thatcher Jonathan
• Flynn David

Classifications

• G06F12/0292

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

• G06F3/0626

  Reducing size or complexity of storage systems · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06F2212/7201

  Logical to physical mapping or translation of blocks or pages · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title