Apparatus, system, and method for a storage layer

Patent metadata

Field	Value
Publication number	US-9442844-B2
Application number	US-201514841323-A
Country	US
Kind code	B2
Filing date	Aug 31, 2015
Priority date	Sep 9, 2009
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

A storage layer for a non-volatile storage device presents a large, logical address space having a logical capacity that may exceed the storage capacity of the non-volatile storage device. The storage layer implements persistent storage operations within the logical address space; storage operations performed within the logical address space may be persisted on the non-volatile storage device. The storage layer maintains storage metadata to allocate ranges of the logical address space to storage entities. The storage layer provides for allocation of contiguous logical address ranges, which may be implemented by segmenting logical identifiers into a first portion referencing storage entities, and a second portion referencing storage entity offsets. The storage layer persists data on the non-volatile storage device in a sequential, log-based format. Accordingly, storage clients, such as file systems, databases, and other applications, may delegate logical allocations, physical storage bindings, and/or crash-recovery to the storage layer.

First claim

What is claimed is:

1. A method, comprising:
presenting a logical address space of a non-volatile storage device;
maintaining storage metadata that associates storage entities with respective sets of two or more logical identifiers of the logical address space, and associates respective logical identifiers with physical storage locations on the non-volatile storage device comprising stored data of respective storage entities; and
in response to a request to persist data of a particular storage entity to the non-volatile storage device,
selecting a logical identifier of the logical address space to associate with the data of the particular storage entity by use of the storage metadata,
persisting the data of the particular storage entity at a physical storage location of the non-volatile storage medium, and
updating the storage metadata such that the selected logical identifier is associated with the particular storage entity and with the physical storage location of the persisted data of the particular storage entity on the non-volatile storage medium.

2. The method of claim 1 , further comprising returning the selected logical identifier in response to the request.

3. The method of claim 1 , wherein the request to persist the data of the particular storage entity includes a logical identifier provided by a storage client, the method further comprising selecting the logical identifier included in the request to allocate to the particular storage entity.

4. The method of claim 1 ,
wherein the request to persist the particular storage entity references a logical identifier to allocate to the particular storage entity, the method further comprising:
selecting an alternative logical identifier to allocate to the particular storage entity in response to determining that the logical identifier referenced in the request is allocated, and
returning the alternate logical identifier in response to the request.

5. The method of claim 1 , further comprising:
in response to an allocation query for a specified logical identifier,
determining whether the specified logical identifier is allocated, and
responding to the allocation query with an indication of whether the specified logical identifier is allocated.

6. The method of claim 1 , further comprising:
in response to a query for a status of a particular logical identifier provided by a storage client,
determining a status of the particular logical identifier using the storage metadata, the status indicating one of whether the particular logical identifier is allocated and whether the particular logical identifier is bound to a physical storage location on the non-volatile storage device, and
notifying the storage client of the determined status of the particular logical identifier.

7. The method of claim 1 , wherein the request to persist the data of the particular storage entity comprises a request to allocate a specified logical identifier to a storage client, the method further comprising:
determining that the specified logical identifier is available to be allocated to the storage client based on the storage metadata,
allocating the specified logical identifier to the storage client, and
selecting the specified logical identifier to allocate for the data of the particular storage entity.

8. The method of claim 1 , wherein the request to persist the data of the particular storage entity comprises a request to modify the data of the particular storage entity, and wherein selecting the logical identifier to associate with the data of the particular storage entity comprises selecting a logical identifier allocated for the particular storage entity.

9. The method of claim 1 , the method further comprising:
determining whether the logical address space has sufficient logical capacity to persist the data of the particular storage entity,
determining whether the non-volatile storage device has sufficient physical storage capacity to persist the data of the particular storage entity, and
acknowledging persisting the particular storage entity in response to determining that the logical address space has sufficient logical capacity and the non-volatile storage device has sufficient storage capacity.

10. The method of claim 1 , further comprising:
segmenting logical identifiers of the logical address space into a first portion and a second portion, wherein the first portion of the logical identifiers comprise a plurality of unique identifiers, and wherein the second portion of the logical identifiers define respective ranges of logical identifiers corresponding to the respective unique identifiers; and
allocating a range of logical identifiers for the particular storage entity, wherein allocating the range of logical identifiers comprises allocating one of the plurality of unique identifiers defined by the first portion of the logical identifiers for the particular storage entity.

11. The method of claim 10 , wherein the first portion comprises high-order bits of the logical identifiers of the logical address space and the second portion comprises low-order bits of the logical identifiers,
the method further comprising determining a logical identifier corresponding to a specified offset within the particular storage entity, wherein high-order bits of the determined logical identifier correspond to the unique identifier allocated for the particular storage entity, and wherein low-order bits of the determined logical identifier correspond to the specified offset.

12. The method of claim 1 , the method further comprising:
segmenting logical identifiers of the logical address space into a first portion and a second portion, the first portion representing a storage entity identifier and the second portion representing offsets;
wherein maintaining the storage metadata comprises maintaining an index comprising entries to represent storage entities in the logical address space, wherein the entries of the index are identified by a respective first portion of a logical identifier.

13. The method of claim 1 , further comprising:
storing data on the non-volatile storage device in a sequential, log-based storage format;
reconstructing the storage metadata from sequential, log-based formatted data on the non-volatile storage device; and
providing an interface through which a storage client accesses the reconstructed storage metadata.

14. The method of claim 1 , wherein the storage metadata comprises entries representing contiguous allocated ranges within the logical address space, each entry further representing bindings between sub-ranges in the contiguous allocated range and physical storage locations on the non-volatile storage device.

15. The method of claim 1 , wherein the request to persist data of the particular storage entity comprises a request to modify data of the particular storage entity at a designated offset, wherein selecting the logical identifier comprises determining a logical identifier for the request by combining a unique identifier allocated for the particular storage entity with the designated offset.

16. A non-transitory computer-readable storage medium comprising instructions to cause a computing device to perform operations comprising:
presenting a logical address space of a non-volatile storage device to storage clients through a storage driver;
segmenting the logical address space into logical identifiers comprising a first portion and a second portion, the first portion referencing respective storage entities, and the second portion referencing storage entity offsets;
persisting storage entities addressa

Assignees

• Longitude Entpr Flash S A R L
• Sandisk Technologies Llc

Inventors

• Flynn David
• Thatcher Jonathan

Classifications

• G06F12/0292

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

• G06F17/30067

  Physics · mapped topic

• G06F12/0623

  for memory modules · CPC title

• G06F2212/7201

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

• G06F12/023

  Free address space management · CPC title