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

• US 8,046,500 B2
• Filed: 10/07/2010
• Issued: 10/25/2011
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Flynn, David, Thatcher, Jonathan, Zappe, Michael
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US12/900,336
• Publication Number:
  US 20110029496A1
• Time in Patent Office: 383 Days
• Field of Search: None
• US Class Current: 710/5
• 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. A method for coordinating storage requests, comprising:

generating a first append storage command in response to a first request to store first data on a storage device;

generating a second append storage command in response to a second request to store second data on the storage device, the second data overlapping at least a portion of the first data, the second request received after the first request; and

updating an index for the first append storage command and updating the index for the second append storage command, wherein the update for the first append storage command retains a reference to the second data in the index when the index is updated for the first append storage command after the index is updated for the second append storage command.

2. The method of claim 1, further comprising preventing access to a region of the index pertaining to the second append storage command while updating the index for the second append storage command.

3. The method of claim 1, wherein updating the index for the second append storage command further comprises:

preventing access to a first region of the index pertaining to the second append storage command while updating the index to reference a storage location of the second data on the storage device, such that other regions of the index are accessible while updating the first region of the index; and

allowing access to the first region of the index after updating the index for the second append storage command.

4. The method of claim 1, the index comprising a forward index comprising a plurality of nodes associating logical identifiers with storage locations on the storage device, wherein updating the index for the second append storage command comprises restructuring the forward index to include a node associating a logical identifier of the second request with a storage location of the second data on the storage device.

5. The method of claim 4, wherein the second data overlapping at least a portion of the first data comprises a first set of logical identifiers that identify a storage location of the second data, the first set of logical identifiers intersecting with a second set of logical identifiers that identify a storage location of the first data, and wherein updating the index comprises restructuring the forward index such that a single node identifies a set of logical identifiers comprising the intersection of the first set of logical identifiers and the second set of logical identifiers.

6. The method of claim 5, wherein restructuring the forward index comprises splitting one or more nodes of the forward index associating logical identifiers with the portion of the first data overlapping the second data into two or more nodes.

7. The method of claim 1, the index comprising a forward index comprising a plurality of nodes to associate logical identifiers with storage locations on the storage device, the forward index comprising a node associating a logical identifier with a storage location of the second data on the storage device, and wherein updating the index for the first append storage command comprises updating a node in the forward index to reference a storage location comprising the first data and retaining the node associating the logical identifier with the storage location of the second data.

8. The method of claim 1, wherein updating the index for the second append storage command comprises updating the index to mark the portion of the first data overlapped by the second data as invalid and updating the index to reference a storage location of the second data on the storage device.

9. The method of claim 8, wherein marking the portion of the first data overlapped by the second data as invalid comprises updating a reverse index associating storage locations of the storage device with logical identifiers to mark the portion of the first data overlapped by the second data as invalid.

10. The method of claim 9, wherein the reverse index is organized by storage division, the method further comprising selecting a storage division for recovery based at least in part on a proportion of data marked as invalid in a selected storage division of the reverse index.

11. The method of claim 1, wherein the second append storage command comprises a command to store the second data sequentially on the storage device to preserve an ordered sequence of storage operations performed on the storage device.

12. The method of claim 1, wherein the second request comprises a logical identifier of the second data, and wherein the second append storage command comprises a command to store the logical identifier with the second data on the storage device.

13. The method of claim 1, wherein the first request and the second request originate from different clients.

14. The method of claim 1, further comprising:

updating the index for the first append storage command by way of a first thread; and

updating the index for the second append storage command by way of a second thread operating concurrently with the first thread.

15. The method of claim 1, further comprising:

associating the first and the second append storage commands with respective sequence indicators, the sequence indicators indicating that the second append storage command is more recent than the first append storage command; and

using the sequence indicators to retain the reference to the second data in the index.

16. The method of claim 15, wherein the sequence indicators represent an order in which the first and the second requests were received.

17. The method of claim 15, wherein the first and the second requests comprise the sequence indicators.

18. The method of claim 15, wherein the sequence indicators represent an order in which the first and the second requests were transmitted.

19. The method of claim 1, further comprising delaying a request to read data pertaining to the second request until updating the index for the second append storage command.

20. A method for coordinating storage requests, comprising:

generating a first append storage command in response to a first request to store first data on a storage device;

generating a second append storage command in response to a second request to store second data on the storage device, the second data pertaining to a logical identifier range that overlaps at least a portion of a logical identifier range of the first data, wherein the second request is more recent than the first request;

updating an index associating logical identifiers with storage locations on the storage device for the first append storage command and updating the index for the second append storage command, the updating to retain an association between a storage location of the second data and the overlapping logical identifier range when the index is updated for the second append storage command before being updated for the first append storage command, wherein updating the index comprises invalidating a portion of the first data associated with the overlapping logical address range.

21. The method of claim 20 further comprising preventing access to a region of the index pertaining to the second append storage command while updating the index for the second append storage command.

22. The method of claim 20, wherein updating the index for the second append storage command further comprises:

preventing access to a first region of the index pertaining to the second append storage command while updating the first region of the index to associate a logical address range of the second data with a storage location of the second data on the storage device, such that other regions of the index are accessible while the first region is updated; and

allowing access to the first region after updating the index for the second append storage command.

23. The method of claim 20, wherein a first thread updates the index for the first append storage command, and a second thread updates the index for the second append storage command.

24. A computer program product comprising a computer readable storage medium comprising code executable to perform operations for coordinating storage requests, the operations comprising:

generating a first append storage command in response to a first request to store first data on a storage device;

generating a second append storage command in response to a second request to store second data on the storage device, the second data pertaining to a logical identifier range that overlaps at least a portion of a logical identifier range of the first data, wherein the second request is more recent than the first request;

updating an index associating logical identifiers with storage locations on the storage device for the first append storage command and updating the index for the second append storage command, the updating to retain an association between a storage location of the second data on the storage device and the overlapping logical identifier range when the index is updated for the second append storage command before the index is updated for the first append storage command; and

preventing access to a region of the index pertaining to the second append storage command while the index is updated for the second append storage command.