Systems and methods for persistent address space management

• US 10,133,663 B2
• Filed: 10/03/2013
• Issued: 11/20/2018
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Longitude Enterprise Flash S.à r.l. (Vector Capital Corporation)
• Inventors: Atkisson, David, Nellans, David, Flynn, David, Axboe, Jens, Zappe, Michael
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Chang, Tian-Pong
• Application Number:
  US14/045,605
• Publication Number:
  US 20150012689A1
• Time in Patent Office: 1,874 Days
• 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/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 2213/0038 System on Chip

Abstract

Data is stored on a non-volatile storage media in a sequential, log-based format. The formatted data defines an ordered sequence of storage operations performed on the non-volatile storage media. A storage layer maintains volatile metadata, which may include a forward index associating logical identifiers with respective physical storage units on the non-volatile storage media. The volatile metadata may be reconstructed from the ordered sequence of storage operations. Persistent notes may be used to maintain consistency between the volatile metadata and the contents of the non-volatile storage media. Persistent notes may identify data that does not need to be retained on the non-volatile storage media and/or is no longer valid.

Claims

1. A method for managing storage operations on a non-volatile storage medium, the method comprising:

a storage client issuing a message to a storage layer, the message specifying a logical identifier that is no longer in use by the storage client to reference data stored on the non-volatile storage medium;

responsive to receiving the message from the storage client, the storage layer storing a persistent note, wherein the persistent note comprises the specified logical identifier and indicates that the specified logical identifier does not correspond to valid data stored on the non-volatile storage medium;

the storage layer providing an interface configured to indicate whether identified logical identifiers correspond to valid data stored on the non-volatile storage medium, wherein the interface is independent of a read interface for accessing data corresponding to the identified logical identifiers stored on the non-volatile storage medium; and

responsive to receiving a request from the storage client, the storage layer determining whether a logical identifier corresponds to valid data stored on the non-volatile storage medium based on whether an entry corresponding to the logical identifier exists in an index maintained by the storage layer and comprising entries corresponding to assignments between logical identifiers and physical storage locations of the non-volatile storage medium;

wherein at least one of the storage layer and the storage client is embodied as non-transitory instructions stored on a non-volatile storage medium.

2. The method of claim 1, further comprising the storage layer returning, to the storage client, an indication that a particular logical identifier does not correspond to valid data 3tored on the non-volatile storage medium in response to determining that the particular logical identifier is not in the index.

3. The method of claim 2, wherein the indication that the particular logical identifier does not correspond to valid data stored on the non-volatile storage medium is returned while data corresponding to the particular logical identifier is stored on the non-volatile storage medium.

4. The method of claim 1, further comprising the storage layer reconstructing assignments between logical identifiers and storage locations of the non-volatile storage medium by use of metadata stored on the non-volatile storage medium, wherein reconstructing the assignments further comprises invalidating an assignment between a particular logical identifier and a storage location in response to identifying a persistent note stored on the non-volatile storage medium pertaining to one or more of the particular logical identifier and the storage location.

5. The method of claim 4, wherein data is stored on the non-volatile storage medium in a packet format, the packet format comprising a data segment and a header that identifies a logical identifier of the data segment.

6. The method of claim 4, wherein the identified persistent note comprises a physical address.

7. The method of claim 1, further comprising the storage layer returning, to the storage client, an indication that a particular logical identifier corresponds to valid data stored on the non-volatile storage medium in response to determining that the particular logical identifier exists in the index.

8. The method of claim 1, wherein the index comprises entries configured to map logical identifiers of the logical address space to storage units of the non-volatile storage medium, the method further comprising the storage layer removing an entry from the index in response to a message comprising a logical identifier that is no longer in use to reference data stored on the non-volatile storage medium.

9. A storage system comprising:

a non-volatile storage device;

a storage client configured to issue an invalidation directive, the invalidation directive designating a logical identifier that is no longer in use by the storage client to reference data stored on the non-volatile storage device;

a storage layer configured to maintain a forward map comprising assignments between logical identifiers of a logical address space and respective storage units of the non-volatile storage device, the respective storage units of the non-volatile storage device comprising data assigned to the logical identifiers;

wherein the storage layer is configured such that, responsive to receiving the invalidation directive from the storage client, the storage layer writes persistent metadata on the non-volatile storage device, wherein the persistent metadata comprises the designated logical identifier and indicates that the designated logical identifier does not correspond to valid data stored on the non-volatile storage device; and

wherein the storage layer is configured to return an indication that the designated logical identifier does not correspond to data stored on the non-volatile storage device in response to a query pertaining to the designated logical identifier and while data corresponding to the designated logical identifier remains on the non-volatile storage device, the query being independent of a read command;

wherein at least one of the storage layer and the storage client is embodied as non-transitory instructions stored on a non-volatile storage medium.

10. The storage system of claim 9, further comprising a reconstruction module configured to reconstruct the forward map by use of data stored on the non-volatile storage device, wherein the reconstruction module is configured to determine that a storage unit comprising data assigned to the designated logical identifier comprises invalid data by use of the persistent metadata stored on the non-volatile storage device.

11. The storage system of claim 9, wherein, in response to the invalidation directive, the storage layer is configured to remove an assignment between the designated logical identifier and a storage unit comprising data assigned to the designated logical identifier from the forward map while the data assigned to the designated logical identifier remains on the storage unit.

12. The storage system of claim 11, wherein the storage layer is configured to return an indication that a particular logical identifier corresponds to valid data stored on the non-volatile storage device in response to determining that the particular logical identifier exists in the forward map.

13. The storage system of claim 11, wherein the storage layer is configured to identify logical identifiers that exist in the forward map in response to requests pertaining to the logical identifiers.

14. The storage system of claim 9, wherein the storage layer is further configured to mark a storage unit comprising data assigned to the designated logical identifier as invalid in a validity bitmap, wherein a groomer is configured to recover a storage division comprising the storage unit by relocating valid data stored on the storage division, and erasing the storage division, and wherein the groomer is configured to determine that the storage unit corresponding to the designated logical identifier does not comprise valid data by use of the validity bitmap.

15. A non-transitory computer-readable storage medium comprising program code configured for execution by a computing device to cause the computing device to perform operations, comprising:

mapping identifiers of a logical address space to respective storage addresses of a non-volatile storage device in response to storing data segments corresponding to the identifiers at the respective storage addresses;

in response to a discard request comprising a particular identifier of the logical address space;

invalidating a mapping between the particular identifier and the respective storage address of the non-volatile storage device, and

storing invalidation metadata on the non-volatile storage device, wherein the invalidation metadata comprises the particular logical identifier and is configured to indicate that the particular logical identifier does not correspond to valid data stored on the non-volatile storage device; and

indicating whether specified identifiers of the logical address space correspond to valid data stored on the non-volatile storage device in response to queries pertaining to the specified identifiers based on whether mappings exist between the specified identifiers and respective storage addresses of the non-volatile storage device, the queries being independent of a read command.

16. The non-transitory computer-readable storage medium of claim 15, the operations further comprising responding to a query pertaining to the particular identifier with an indication that the particular identifier does not correspond to valid data stored on the non-volatile storage device while a data segment corresponding to the particular identifier remains on the non-volatile storage device.

17. The non-transitory computer-readable storage medium of claim 15, the operations further comprising:

storing the data segments with persistent metadata on the non-volatile storage device, the persistent metadata configured to indicate identifiers of the logical address space associated with the respective data segments; and

reconstructing mappings between identifiers of the logical address space and respective storage addresses of the data segments by use of the persistent metadata stored on the non-volatile storage device.

18. The non-transitory computer-readable storage medium of claim 17, wherein reconstructing the mappings between the identifiers of the logical address space and the respective storage addresses of the data segments comprises one or more of:

invalidating a mapping between an identifier and a data segment stored on the non-volatile storage device in response to invalidation metadata comprising the identifier; and

omitting a mapping between an identifier and a stored data segment based on invalidation metadata comprising the identifier.

19. The non-transitory computer-readable storage medium of claim 17, wherein reconstructing the mappings comprises accessing data segments stored on the non-volatile storage device according to a log order of the data segments stored on the non-volatile storage device.