SYSTEMS, METHODS, AND INTERFACES FOR VECTOR INPUT/OUTPUT OPERATIONS

• US 20130166855A1
• Filed: 12/21/2012
• Published: 06/27/2013
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Peterson, James G., Talagala, Nisha, Piggin, Nick, Zappe, Michael, Batwara, Ashish
• Granted Patent: US 9,274,937 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/1734 Details of monitoring file system events, e.g. by the use of hooks, filter drivers, logs
• CPC Class Codes: G06F 16/907 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Data of a vector storage request pertaining to one or more disjoint, non-adjacent, and/or non-contiguous logical identifier ranges are stored contiguously within a log on a non-volatile storage medium. A request consolidation module modifies one or more sub-requests of the vector storage request in response to other, cached storage requests. Data of an atomic vector storage request may comprise persistent indicators, such as persistent metadata flags, to identify data pertaining to incomplete atomic storage requests. A restart recovery module identifies and excludes data of incomplete atomic operations.

Claims

1. An apparatus, comprising:

a non-volatile storage medium;

a request consolidation module configured to modify a storage request of a vector storage request in response to another pending storage request; and

a storage fulfillment module configured to service storage requests including the one or more modified storage requests.

2. The apparatus of claim 1, wherein the storage request is modified in response to another storage request of the vector storage request.

3. The apparatus of claim 1, wherein the storage request is modified in response to a storage request that is independent of the vector storage request.

4. The apparatus of claim 1, wherein modifying the storage request comprises combining two or more storage requests, wherein the two or more storage requests include a storage request of the vector storage request.

5. The apparatus of claim 4, wherein the two or more storage requests comprise logical identifiers that reference one of adjacent and overlapping logical identifiers.

6. The apparatus of claim 4, wherein the two or more storage requests comprise trim storage requests that pertain to one of adjacent and overlapping logical identifier ranges.

7. The apparatus of claim 1, wherein modifying the storage request comprises removing the storage request in response to determining that the storage request is obviated by one or more of the pending storage requests.

8. The apparatus of claim 7, wherein the request consolidation module is configured to remove the storage request in response to determining that the storage request comprises a trim request that pertains to one or more logical identifiers to be written by other pending storage requests.

9. The apparatus of claim 1, wherein the vector storage request comprises an atomic vector storage request, the apparatus further comprising:

a log storage module configured to append data pertaining to the atomic vector storage request contiguously within a log on the non-volatile storage medium; and

an atomic storage module configured to include a first persistent indicator on the non-volatile storage medium, wherein the first persistent indicator is configured to indicate that the data pertains to an atomic storage operation.

10. The apparatus of claim 9, wherein the atomic storage module is configured to include a second persistent indicator on the non-volatile storage medium to indicate that the atomic vector storage request is complete.

11. The apparatus of claim 9, wherein the atomic storage module is configured to append one or more data packets pertaining to the atomic vector storage request contiguously within the log, and wherein a last data packet of the atomic storage operation within the log comprises a persistent metadata flag configured to indicate completion of the atomic storage operation.

12. An apparatus, comprising:

a non-volatile storage medium;

a log storage module configured to append data pertaining to an atomic vector storage request in a contiguous log format on the non-volatile storage medium; and

an atomic storage module configured to include respective persistent metadata in data within a log on the non-volatile storage medium to indicate that the data corresponds to an atomic operation.

13. The apparatus of claim 12, wherein two or more vectors of the atomic vector storage request pertain to non-adjacent ranges of logical identifiers.

14. The apparatus of claim 12, wherein the atomic storage module is configured to append persistent metadata to the log to indicate that the atomic operation is complete.

15. The apparatus of claim 12, wherein a final data packet of the atomic storage operation within the log comprises a persistent metadata flag to indicate that the atomic operation is complete.

16. The apparatus of claim 12, wherein the data is organized in a packet format, and wherein a set of one or more data packets pertaining to the atomic operation comprise a persistent metadata flag configured to indicate that the set of data packets pertain to an atomic storage operation that is in process, and wherein a final data packet of the atomic operation comprises a persistent metadata flag configured to indicate that the atomic operation is complete.

17. The apparatus of claim 12, wherein the log storage module is configured to append the one or more data packets to non-contiguous physical storage locations within a physical address space of the non-volatile storage medium.

18. The apparatus of claim 12, wherein the log storage module is configured to append data packets comprising data of the atomic vector storage request sequentially from an append point within a physical address space of the non-volatile storage medium and to associate the data packets with respective sequence indicators, and wherein the sequential order and the sequence indicators of the data packets define a log order of the data packets.

19. The apparatus of claim 12, wherein the atomic vector storage request comprises a plurality of sub-requests, each sub-request comprising an operation pertaining to a respective set of one or more logical identifiers, and wherein the atomic storage module is configured to defer updating a forward index comprising any-to-any mappings between logical identifiers and physical storage locations until each of the sub-requests of the atomic vector storage operation are complete.

20. The apparatus of claim 19, wherein two or more of the sub-requests of the atomic vector storage request comprise different types of storage operations.

21. The apparatus of claim 12, wherein the atomic vector storage request comprises a plurality of vectors, and wherein each vector comprises a respective subcommand, the apparatus further comprising an ordered queue configured to complete the subcommands and one or more other storage requests in the ordered queue according to an order in which the subcommands and the one or more other storage requests were received at the ordered queue.

22. The apparatus of claim 21, further comprising a request consolidation module configured to modify one of the subcommands based on one or more other subcommands of the atomic vector storage request.

23. The apparatus of claim 22, wherein the vector storage module is configured to delete a subcommand in response to determining that the subcommand is overridden by another subcommand of the atomic vector storage request.

24. The apparatus of claim 22, wherein the vector storage module is configured to combine two or more of the subcommands.

25. An apparatus, comprising:

a request buffer configured to store one or more storage requests;

a request consolidation module configured to modify one or more of the storage requests in the request buffer based on one or more other storage requests in the request buffer; and

a storage request execution module configured to service storage requests in the request buffer.

26. The apparatus of claim 25, wherein the request consolidation module is configured to delete a storage request from the request buffer in response to one or more other storage requests in the request buffer.

27. The apparatus of claim 25, wherein the request consolidation module is configured to omit a trim storage request from the request buffer in response a storage request to store data to a set of logical identifiers that overlaps a set of logical identifiers of the trim storage request.

28. The apparatus of claim 25, wherein the request consolidation module is configured to consolidate two or more trim storage requests that overlap and/or are contiguous in a logical address space.

29. A computer-readable storage medium comprising instructions configured to cause a computing device to perform a method, comprising:

buffering a plurality of storage requests;

modifying one of the plurality of storage requests based on a logical identifier range of the storage request and respective logical identifier ranges of others of the plurality of storage requests; and

executing the buffered storage requests, wherein execution of one of the buffered storage requests comprises storing one or more data packets to a solid-state storage medium.

30. The computer-readable storage medium of claim 29, wherein modifying the storage request comprises one or more of:

deleting the storage request in response to identifying one or more storage requests that pertain to logical identifiers that overlap the logical identifier range of the storage request; and

combining the storage request with another storage request in response to one or more of the storage requests comprising logical identifier ranges that overlap in a logical address space and the storage requests comprising logical identifier ranges that are adjacent in the logical address space.

31. The computer-readable storage medium of claim 29, wherein modifying the storage request comprises one or more of:

removing a trim storage request in response to a subsequent storage request to store data in association with a range of logical identifiers that overlaps the logical identifier range of the trim storage request; and

consolidating the storage request with another storage request having a logical identifier range that overlaps with and/or is contiguous with the logical identifier range of the storage request within a logical address space.

32. An apparatus, comprising:

a log storage module configured to store data of an atomic storage request on a non-volatile storage medium;

an atomic storage module configured to associate persistent metadata indicating completion of the atomic storage request with a portion of the data of the atomic storage request on the non-volatile storage medium; and

a storage management layer configured to mark the portion of data associated with the persistent metadata invalid, and to preserve the persistent metadata indicating completion of the atomic storage request associated with the invalidated portion of data.

33. The apparatus of claim 32, wherein the storage management layer is configured to invalidate the portion of data of the atomic storage request in response to one or more of a request to trim the portion, a request to erase the portion, a request to delete the portion, a request to modify the portion, and a request to overwrite the portion.

34. The apparatus of claim 32, wherein the log storage module is configured to store persistent metadata on the non-volatile storage medium to invalidate the portion of data associated with the persistent metadata indicating completion of the atomic storage request.

35. The apparatus of claim 34, further comprising a restart recovery module configured to exclude the invalidated portion of data and to apply the persistent metadata indicating completion of the atomic storage request.