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

• US 7,836,226 B2
• Filed: 04/06/2008
• Issued: 11/16/2010
• 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/098,435
• Publication Number:
  US 20090222596A1
• Time in Patent Office: 954 Days
• Field of Search: None
• US Class Current: 710/36
• 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. A 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 to coordinate storage requests, the apparatus comprising:

an append/invalidate module that generates a first append data storage command in response to receiving a first storage request, the first storage request comprising a request to overwrite existing data of a data segment stored on a data storage device with first data, and that generates a second append data storage command in response to receiving a second storage request, the second storage request comprising a request to overwrite existing data of the data segment with second data, the first and second data comprising at least a portion of overlapping data to be stored at a common offset within the data segment, the second storage request received after the first storage request, and that updates an index in response to the first storage request by marking data of the data segment as invalid, the data marked invalid comprising data being replaced by the first data, and that updates the index in response to the second storage request by marking data of the data segment as invalid, the data marked invalid comprising data being replaced by the second data; and

a restructure module that updates the index based on the first data and updates the index based on the second data, wherein the updated index is organized to indicate that the second data is more current than the first data when either the index is updated based on the first data before being updated based on the second data or the index is updated based on the second data before being updated based on the first data,

wherein the append/invalidate module prevents access to the index until the append/invalidate module has completed updating the index and wherein the restructure module prevents access to the index until the restructure module has completed updating the index.

2. The apparatus of claim 1, further comprising a data location update module that updates the index with a first physical location indicating where the data storage device stored the first data and updates the index with a second physical location indicating where the data storage device stored the second data, the physical locations where the data storage device stored the first data and the second data received from the data storage device, wherein the updated index is organized to indicate that the second physical location is more current than the first physical location when either the index is updated based on the first physical location before being updated based on the second physical location or the index is updated based on the second physical location before being updated based on the first physical location, and wherein the data location update module prevents access to the index until the data location module has completed updating the index.

3. The apparatus of claim 2, wherein processing a storage request by the append/invalidate module occurs before processing by the restructure module and processing of the storage request by the restructure module occurs before processing by the data location module.

4. The apparatus of claim 3, wherein processing of the first storage request by any of the append/invalidate module, the restructure module, and the data location update module occurs prior to or after processing of the second storage request by any of the append/invalidate module, the restructure module, and the data location update module.

5. The apparatus of claim 2, wherein an instance of each of the append/invalidate module, the restructure module, and the data location update module are executed in two or more threads and wherein each instance of the append/invalidate module, the restructure module, and the data location update module prevents access to the index until the append/invalidate module, the restructure module, or the data location update module has completed updating the index.

6. The apparatus of claim 2, wherein an instance of each of the append/invalidate module, the restructure module, and the data location update module are executed on two or more processors operating in parallel and wherein each instance of the append/invalidate module, the restructure module, and the data location update module prevents access to the index until the append/invalidate module, the restructure module, or the data location update module has completed updating the index.

7. The apparatus of claim 2, further comprising a read module that reads at least a portion of the data segment in response to a storage request comprising a read request and further comprising a read delay module that delays servicing the requested read until the first storage request is serviced by the append/invalidate module, the restructure module, and the data location update module.

8. The apparatus of claim 7, wherein the storage request to read at least a portion of the data segment is received by the apparatus after the first storage request and before the second storage request and wherein the read delay module delays servicing the read request until both the first and second storage requests are serviced by the append/invalidate module, the restructure module, and the data location update module.

9. The apparatus of claim 1, further comprising a sequence number module that associates a sequence number with a storage request, assigned sequence numbers representing an order that storage requests are received by the apparatus, and wherein the restructure module organizes the index to indicate that the second data is more current than the first data by using a sequence number assigned to each of the first storage request and the second storage request.

10. The apparatus of claim 1, wherein organizing the index to indicate that the second data is more current than the first data comprises updating a portion of the index mapped to the overlapping data with the second data and retaining the mapping to the second data if the restructure module updates the index based on the second data before updating the index based on the first data.

11. The apparatus of claim 1, wherein the append/invalidate module receives three or more storage requests to overwrite existing data of the data segment and the restructure module organizes the index with data of the storage requests based on an order of arrival of the storage requests regardless of an order that the restructure module uses data of the storage requests to update the index.

12. The apparatus of claim 1, wherein the index is further divided into two or more regions and a storage request pertaining to a first region of the index is serviced while additional instances of the one or more of the append/invalidate module and the restructure module prevent access to a second region of the index while servicing a storage request pertaining to a second region.

13. The apparatus of claim 1, wherein the first storage request is transmitted from a first client and the second storage request is transmitted from a second client.

14. The apparatus of claim 1, wherein updating the index in response to the first storage request by marking the data of the data segment being replaced as invalid further comprises marking one or more bits of a bitmap, the bits in the bitmap corresponding to one or more locations in the data storage device where the data of the data segment being replaced by the first data and the second data resides.

15. The apparatus of claim 1, wherein updating the index in response to the first storage request by marking the data of the data segment being replaced as invalid further comprises temporarily marking the entire data segment invalid until the restructure module updates the index based on the first data and the second data and then updating the index to indicate that data of the data segment other than the data being replaced is valid.

16. The apparatus of claim 1, wherein updating the index in response to the first storage request by marking the data of the data segment being replaced as invalid further comprises generating a list indicating portions of the data segment being replaced by the first data and the second data are invalid and indicating that portions of the data segment not being replaced by the first data and the second data are valid.

17. The apparatus of claim 1, wherein one or more of the first storage request and the second storage request are received substantially without data.

18. The apparatus of claim 1, wherein one or more of the first append data storage command and the second append data storage command are transmitted to the data storage device substantially without data.

19. The apparatus of claim 1, wherein at least one of a storage request and an append data storage command initiates a direct memory access (“

DMA”

) process or a remote DMA (“

RDMA”

) process to transfer data of the data segment to the data storage device.

20. A system to coordinate storage requests, the system comprising:

a data storage device; and

a storage controller controlling the data storage device, the storage controller comprising

an append/invalidate module that generates a first append data storage command in response to receiving a first storage request to overwrite existing data of a data segment stored on the data storage device with first data and that generates a second append data storage command in response to receiving a second storage request to overwrite existing data of the data segment with second data, the first and second data comprising at least a portion of overlapping data to be stored at a common offset within the data segment, the second storage request received after the first storage request, and that updates an index in response to the first storage request by marking data of the data segment as invalid, the data marked invalid comprising data being replaced by the first data, and that updates the index in response to the second storage request by marking data of the data segment as invalid, the data marked invalid comprising data being replaced by the second data; and

a restructure module that updates the index based on the first data and updates the index based on the second data, wherein the updated index is organized to indicate that the second data is more current than the first data when either the index is updated based on the first data before being updated based on the second data or the index is updated based on the second data before being updated based on the first data,

wherein the append/invalidate module prevents access to the index until the append/invalidate module has completed updating the index and wherein the restructure module prevents access to the index until the restructure module has completed updating the index.

21. The system of claim 20, wherein the data storage device comprises a solid-state storage device.

22. The system of claim 20, wherein first storage request and the second storage request are received from separate requesting devices, wherein the separate requesting devices comprise one or more of a client and a server.

23. The system of claim 22, wherein at least one of the requesting devices comprises a client and the append/invalidate module and the restructure module operate independent of the client.

24. The system of claim 20, further comprising a server, wherein the storage controller is within the server.

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

generating a first append data storage command in response to receiving a first storage request to overwrite existing data of a data segment stored on a data storage device with first data;

generating a second append data storage command in response to receiving a second storage request to overwrite existing data of the data segment with second data, the first and second data comprising at least a portion of overlapping data to be stored at a common offset within the data segment, the second storage request received after the first storage request;

updating an index in response to the first storage request by marking data of the data segment as invalid, wherein the data marked invalid comprises data being replaced by the first data;

updating the index in response to the second storage request by marking data of the data segment as invalid, wherein the data marked invalid comprises data being replaced by the second data,

wherein access to the index is prevented until an append data storage command is generated for one of the first storage request and the second storage request and the index is updated by marking the data of the data segment invalid for one of the first storage request and the second storage request;

updating the index based on the first data; and

updating the index based on the second data, wherein the updated index is organized to indicate that the second data is more current than the first data when either the index is updated based on the first data before being updated based on the second data or the index is updated based on the second data before being updated based on the first data,

wherein access to the index is prevented until the index is updated based on one of the first data and the second data.