Apparatus, system, and method for coordinating storage requests in a multi-processor/multi-thread environment

• US 9,600,184 B2
• Filed: 09/25/2015
• Issued: 03/21/2017
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Flynn, David, Zappe, Michael, Thatcher, Jonathan
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US14/866,461
• Publication Number:
  US 20160018991A1
• Time in Patent Office: 543 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

An apparatus, system, and method are disclosed for coordinating storage requests in a multi-processor/multi-thread environment. An append/invalidate module generates a first append data storage command from a first storage request and a second append data storage command from a second storage request. The storage requests overwrite existing data with first and second data including where the first and second data have at least a portion of overlapping data. The second storage request is received after the first storage request. The append/invalidate module updates an index by marking data being overwritten as invalid. A restructure module updates the index based on the first data and updates the index based on the second data. The updated index is organized to indicate that the second data is more current than the first data regardless of processing order. The modules prevent access to the index until the modules have completed updating the index.

Claims

1. An apparatus comprising:

a controller configured to;

receive, at a first time, a first storage request to store data on a non-volatile storage medium;

receive, at a second time after the first time, a second storage request to store data on the non-volatile storage medium; and

update an index based on the second storage request before updating the index based on the first storage request, wherein the index is updated with information corresponding to the second storage request, the index comprises mappings between physical addresses and logical addresses, and the index is used to update one or more of a forward map and a reverse map.

2. The apparatus of claim 1, wherein updating the index based on the second storage request before updating the index based on the first storage request indicates that the second storage request is more current than the first storage request.

3. The apparatus of claim 1, wherein the controller is further configured to order the first and second storage requests to service the second storage request before the first storage request.

4. The apparatus of claim 1, wherein the controller is further configured to compress data corresponding to the first and second storage requests before servicing the first and second storage requests.

5. The apparatus of claim 1, wherein the controller is further configured to receive a read request prior to receiving the first storage request.

6. The apparatus of claim 5, wherein the read request is performed after servicing one or more of the first and second storage requests.

7. An apparatus comprising:

means for receiving, at a first time, a first storage command to store data on a non-volatile storage media;

means for receiving, at a second time after the first time, a second storage command to store data on the non-volatile storage media;

means for ordering the first and second storage commands to perform the second storage command before the first storage command; and

means for updating an index based on the second storage command before updating the index based on the first storage command, wherein the index is updated with information corresponding to the second storage command, the index comprises mappings between physical addresses and logical addresses, and the index is used to update one or more of a forward map and a reverse map.

8. The apparatus of claim 7, further comprising means for blocking performing at least a portion of the first storage command that overlaps with a portion of the second storage command.

9. The apparatus of claim 7, further comprising means for compressing data corresponding to the first and second storage commands before performing the first and second storage commands.

10. The apparatus of claim 7, further comprising means for receiving a read request after receiving the first storage command and prior to receiving the second storage command.

11. The apparatus of claim 10, wherein the read request is performed after performing both of the first and second storage commands.

12. A method comprising:

receiving, at a first time, a first storage request to store data on a non-volatile storage media;

receiving, at a second time after the first time, a second storage request to store data on the non-volatile storage media;

servicing the second storage request before servicing the first storage request; and

updating an index based on the second storage request before updating the index based on the first storage request, wherein the index is updated with information corresponding to the second storage request, the index comprises mappings between physical addresses and logical addresses, and the index is used to update one or more of a forward map and a reverse map.

13. The method of claim 12, comprising receiving a read request prior to receiving the first storage request.

14. The method of claim 13, wherein the read request is performed after servicing one or more of the first and second storage requests.

15. The method of claim 12, comprising receiving a read request after receiving the first storage request and prior to receiving the second storage request.

16. The method of claim 15, wherein the read request is performed after servicing both of the first and second storage requests.

17. The method of claim 12, wherein the at least one of the first and second storage requests is a request to store data comprising a data segment and a data header.

18. The method of claim 17, wherein the data header comprises source parameters.