Apparatus, system, and method for a storage layer

• US 9,122,579 B2
• Filed: 01/06/2011
• Issued: 09/01/2015
• Est. Priority Date: 01/06/2010
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Flynn, David, Thatcher, Jonathan
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US12/986,117
• Publication Number:
  US 20120011340A1
• Time in Patent Office: 1,699 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/023 Free address space management
• 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 12/0623 for memory modules
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2212/7209 Validity control, e.g. using flags, time stamps or sequence numbers

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.

Claims

1. A method comprising:

presenting a logical address space of a solid-state storage device to a storage client, wherein a logical capacity of the logical address space exceeds a total physical storage capacity of a full physical address space of the solid-state storage device;

performing persistent storage operations on storage entities addressable within the logical address space in response to storage requests from the storage client;

maintaining storage metadata that associates logical addresses for the storage entities in the logical address space with physical storage locations on the non-volatile storage device; and

associating an ordered sequence of write storage operations with the storage entities.

2. The method of claim 1, further comprising:

in response to a request to persist a storage entity from the storage client,

allocating at least one logical identifier in the logical address space to satisfy the request, and

returning the at least one logical identifier to the storage client.

3. The method of claim 1, further comprising:

in response to a request to persist a storage entity having a logical identifier provided by the storage client,

allocating the logical identifier in the logical address space to satisfy the request, in response to the logical identifier being unallocated in the logical address space, and

acknowledging to the storage client persistence of the storage entity having the logical identifier on the solid-state storage device.

4. The method of claim 1, further comprising:

in response to a request to persist a storage entity having a logical identifier provided by the storage client,

determining that the logical identifier provided by the storage client is allocated,

persisting the storage entity having the logical identifier using an alternate logical identifier in response to the logical identifier provided by the storage client being allocated in the logical address space, and

returning the alternate logical identifier to the storage client.

5. The method of claim 1, further comprising:

in response to an allocation query for a logical identifier provided by the storage client,

determining whether the logical identifier provided by the storage client is allocated, and

notifying the storage client whether the logical identifier is allocated.

6. The method of claim 1, further comprising:

determining a status of a 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 solid-state storage device in request to a query from the storage client.

7. The method of claim 1, further comprising:

in response to a request to persist a storage entity in association with a particular logical identifier in the logical address space,

notifying the storage client that a storage operation failed, in response to determining that the particular logical identifier is allocated, and

allocating the particular logical identifier for the storage client, and persisting the storage entity corresponding to the request using the particular logical identifier, in response to determining that the particular logical identifier is not allocated.

8. The method of claim 1, further comprising:

segmenting logical identifiers of the logical address space such that the logical identifiers comprise respective first portions and second portions;

referencing a storage entity using the first portion of a logical identifier; and

referencing an offset into a storage entity using the second portion of the logical identifier.

9. The method of claim 8, wherein the storage entity referenced by the first portion of the logical identifier is a file system object and,

wherein each first portion comprises high-order bits of a logical identifier of the logical address space and each second portion comprises low-order bits of a logical identifier,

wherein each successive first portion defines a contiguous range of blocks within the logical address space, and

wherein each block in the contiguous range is independently addressable by way of a respective logical identifier.

10. The method of claim 8, further comprising maintaining an index comprising entries configured to represent storage entities in the logical address space, the entries identified by respective first portions of the logical identifiers and comprising a range of addresses in the logical address space corresponding to the respective second portions of the logical identifiers, wherein the index is capable of representing 2Λ

32 unique storage entities, each comprising a contiguous range of 2Λ

32 addresses in the logical address space.

11. The method of claim 1, the method further comprising:

segmenting logical identifiers of the logical address space into respective first portions and second portions, the first portions of the logical identifiers representing storage entity identifiers and the second portions representing offsets;

maintaining a storage metadata index comprising entries to represent storage entities in the logical address space, the entries identified by a respective first portion of a logical identifier and comprising a contiguous range of addresses in the logical address space corresponding to the second portion of the logical identifier; and

in response to a request from the storage client to access storage entity data in the logical address space at a particular logical identifier,

identifying an entry in the storage metadata using the first portion of the particular logical identifier,

determining a physical storage location of the requested storage entity data on the solid-state storage device using the identified entry and the second portion of the particular logical identifier, and

returning data from the solid-state storage device at the determined physical storage location to the storage client.

12. The method of claim 1, further comprising:

storing data on the solid-state storage device in a sequential, log-based storage format;

reconstructing the storage metadata from sequential, log-based formatted data on the solid-state storage device; and

providing an interface through which the storage client accesses the reconstructed storage metadata.

13. The method of claim 12, wherein the storage client comprises a file system, and wherein the file system accesses file allocation information in the reconstructed storage metadata.

14. The method of claim 12, wherein the storage client comprises a database, and wherein the database delegates logical identifier allocation for data structures of the database to a storage layer.

15. The method of claim 12, the method further comprising providing crash recovery for storage operations performed within the logical address space using the sequential, log-based storage format.

16. The method of claim 1, further comprising:

providing an interface to deallocate a logical identifier in the logical address space; and

in response to a request to deallocate the logical identifier,

marking a physical storage location on the solid-state storage device as comprising invalid data, and

returning a pre-determined value in response to a subsequent request to access the deallocated logical identifier.

17. The method of claim 1, further comprising:

determining a remaining portion of the total physical storage capacity of the solid-state storage device using the storage metadata; and

providing an interface through which the storage client accesses the remaining storage capacity.

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

19. A non-transitory computer-readable storage medium comprising instructions to cause a computing device to perform a method, the method comprising:

presenting a logical address space of a non-volatile storage device to storage clients,

wherein a logical capacity of the logical address space exceeds a physical storage capacity of the non-volatile storage device;

dividing logical identifiers of the logical address space into respective high-order portions and low-order portions, the first high-order portions referencing respective storage entities, and the low-order portions referencing storage entity offsets;

persisting storage entities addressable within the logical address space in response to requests from the storage clients;

maintaining storage metadata entries, each entry representing a storage entity using a respective high-order first portion of a logical identifier in the logical address space; and

in response to persisting a storage entity at a specified logical identifier in the logical address space,

identifying a storage metadata entry corresponding to the first high-order portion of the specified logical identifier, and

binding an offset in the identified storage metadata entry to a physical storage location on the non-volatile storage device comprising the persisted storage entity using the low-order portion of the specified logical identifier.

20. A storage system implemented at least in part by a computing device, comprising:

a non-volatile storage device;

a storage layer comprising,

an interface configured to present a logical address space of the non-volatile storage device, the logical address space comprising a logical capacity that exceeds a physical storage capacity of the non-volatile storage device, wherein logical identifiers in the logical address space are segmented into a respective first portion configured to reference storage entities, and a second portion configured to reference offsets within storage entities, and

an interface for persisting storage entities in association with identifiers of the logical address space, wherein in response to a request from a storage client to persist a designated storage entity at a specified logical identifier, the storage layer is configured to bind logical identifiers in a contiguous range of logical identifiers allocated to the designated storage entity to an ordered, log-based sequence of storage operations on the non-volatile storage device comprising the designated storage entity to be persisted.

21. An apparatus, comprising:

an interface configured to present a logical address space of a solid-state storage medium, wherein a size of the logical address space presented by the interface exceeds a total storage capacity corresponding to a full physical address space of the solid-state storage medium;

a storage controller configured to store data within respective storage locations of the solid-state storage medium in association with identifiers of the logical address space; and

a storage layer configured to associate the identifiers of the logical address space with the respective storage locations of the solid-state storage medium, wherein the storage controller comprises one or more hardware and machine-readable instructions stored on a non-transitory storage medium.

22. The apparatus of claim 21, further comprising an allocation module configured to allocate an identifier within the logical address space in response to a request to store a data segment on the solid-state storage medium, wherein the storage controller is configured to store the data segment in association with the allocated identifier on the solid-state storage medium.

23. The apparatus of claim 22, wherein the request to store the data segment specifies an identifier for the data segment that is unavailable, and wherein the allocation module is configured to allocate the identifier in response to determining that the specified identifier is unavailable.

24. The apparatus of claim 21, further comprising an allocation module configured to split the identifiers of the logical address space, such that the identifiers comprise respective unique identifier portions and respective offset portions, and wherein the allocation module is configured to allocate ranges of identifiers in accordance with a size of the offset portions of the identifiers.

25. The apparatus of claim 24 wherein the allocation module is configured to determine whether a particular identifier of the logical address space is allocated by use of the unique identifier portion of the particular identifier.

26. An apparatus, comprising:

a storage layer configured to present a logical address space corresponding to a non-volatile storage medium, wherein a size of the logical address space presented by the storage layer exceeds a storage capacity of the non-volatile storage medium;

a storage module configured to store data at respective physical addresses of the non-volatile storage medium in association with identifiers of the logical address space, wherein the storage layer is configured to associate the identifiers of the logical address space with the respective physical addresses of the non-volatile storage medium; and

an allocation module configured to divide the identifiers of the logical address space, such that the identifiers comprise respective unique identifier portions and respective offset portions, and wherein the allocation module is configured to allocate ranges of identifiers in accordance with a size of the offset portions of the identifiers, wherein the storage controller comprises one or more of a circuit and machine-executable instructions recorded on a non-transitory storage medium.