Apparatus, System, and Method for a Virtual Storage Layer

• US 20120011340A1
• Filed: 01/06/2011
• Published: 01/12/2012
• Est. Priority Date: 01/06/2010
• 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 9,122,579 B2
• Time in Patent Office: Days
• US Class Current: 711/171
• 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 virtual storage layer (VSL) 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 VSL 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 VSL maintains storage metadata to allocate ranges of the logical address space to storage entities. The VSL 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 VSL 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 VSL.

Claims

1. A method for providing a virtual storage layer for a storage client, comprising:

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

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

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

in response to performing the persistent storage operations, the storage metadata further associating an ordered sequence of the storage operations with each storage entity.

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 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 a 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 on the non-volatile 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 a storage client,

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

persisting the storage entity 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 a 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:

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

7. The method of claim 1, further comprising:

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

when the particular logical identifier is allocated, notifying the storage client that the storage operation failed, and

when the particular logical identifier is not allocated, allocating the particular logical identifier for the storage client, and persisting the storage entity using the particular logical identifier.

8. The method of claim 1, further comprising:

in response to a request to modify data of a storage entity at a logical identifier allocated to a storage client,

persisting the modified data of the storage entity on a physical storage location of the non-volatile storage device, and

updating the storage metadata to bind the logical identifier for the modified data allocated to the storage client with the physical storage location.

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

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

determining whether the logical address space has sufficient logical capacity to persist the storage entity,

determining whether the non-volatile storage device has sufficient physical storage capacity to persist the storage entity, and

acknowledging persisting the storage entity when 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;

referencing a storage entity using the first portion; and

referencing an offset into a storage entity using the second portion;

11. The method of claim 10, wherein the storage entity is a file.

12. The method of claim 10, wherein the storage entity is a file system object and the first portion comprises high-order bits of logical identifiers of the logical address space and the second portion comprises low-order bits of the logical identifiers,

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

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

13. The method of claim 10, wherein the storage entity is an I-node.

14. The method of claim 10, wherein the logical identifiers are segmented into the first portion and the second portion in response to a configuration request from a storage client, and wherein a length of one or more of the first portion and the second portion of the logical identifier is specified in the configuration request.

15. The method of claim 10, wherein the first portion of the logical identifier comprises 32 bits and the second portion of the logical identifier comprises 32 bits.

16. The method of claim 15, further comprising 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 range of addresses in the logical address space corresponding to the second portion of the logical identifier, 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.

17. 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 an offset;

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 a 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 non-volatile storage device using the identified entry and the second portion of the particular logical identifier, and

returning data from the non-volatile storage device at the determined physical storage location to the storage client.

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

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

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

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

22. 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 a logical identifier,

marking a physical storage location on the non-volatile storage device as comprising invalid data, and

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

23. The method of claim 1, further comprising:

determining a remaining physical storage capacity of the non-volatile storage device using the storage metadata; and

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

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

25. A non-transitory computer-readable storage medium comprising instructions to cause a computing device to perform a method for a virtual storage layer, 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;

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 addressable within the logical address space in response to requests from the storage clients;

maintaining storage metadata entries, each representing a storage entity using a respective 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 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 second portion of the specified logical identifier.

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

a non-volatile storage device;

a virtual storage layer comprising an interface to present to storage clients,

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 first portion referencing storage entities, and a second portion referencing storage entity offsets,

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