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

• US 9,170,754 B2
• Filed: 04/25/2012
• Issued: 10/27/2015
• Est. Priority Date: 12/06/2007
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Intelligent Intellectual Property Holdings LLC
• Inventors: Flynn, David, Zappe, Michael, Thatcher, Jonathan
• Primary Examiner(s): CHEN, ALAN S
• Application Number:
  US13/456,119
• Publication Number:
  US 20120210021A1
• Time in Patent Office: 1,280 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 storage request receiver module configured to receive a storage request to store data at a logical address specified by the storage request;

a translation module configured to;

determine whether to generate a single append storage command or a plurality of append storage commands based on a length of the data and a storage capacity of a physical storage location on the non-volatile storage medium; and

based on the determination, generate one or more append storage commands in response to the received storage request, wherein each of the one or more append storage commands is executable to store a portion of the data at one or more respective physical addresses corresponding to one or more append point locations;

an append module configured to execute the one or more append storage commands by storing the portions of the data on a non-volatile storage medium, wherein one or more of the storage request receiver module, translation module, and append module include hardware;

a mapping module configured to translate, in accordance with a map data structure, the logical address to one or more corresponding physical addresses;

a check point module configured to periodically store the map data structure to the non-volatile storage medium, wherein the append module is configured to further store metadata of the map data structure with the portions of the data; and

a map rebuild module configured to rebuild a current version of the map data structure by sequentially reading the metadata stored since a last storage of the map data structure, wherein the mapping module, check point module, and map rebuild module are hardware.

2. The apparatus of claim 1, wherein the append module is configured to:

execute a first of the one or more append storage commands by storing a portion of the data at one or more physical addresses corresponding to a first append point location on the non-volatile storage medium; and

execute a second of the one or more append storage commands by storing a portion of the data at one or more physical addresses corresponding to a second append point location on the non-volatile storage medium.

3. The apparatus of claim 2, wherein the first and second append point locations correspond to physical addresses located within different erase blocks of the non-volatile storage medium.

4. The apparatus of claim 1, wherein the logical address is a logical block address, and wherein the storage request further specifies a length of the data.

5. The apparatus of claim 1, wherein the apparatus is configured to process storage requests received in parallel.

6. A method, comprising:

receiving a request to store data on a non-volatile storage medium;

analyzing a length of the data and an available amount of storage capacity for a physical storage location in the non-volatile storage medium;

based on the analyzing, issuing a plurality of storage commands to the non-volatile storage medium, wherein each of the plurality of storage commands is executable to store a portion of the data within a respective data packet on the non-volatile storage medium; and

compressing the portions of data prior to storing the data on the non-volatile storage medium.

7. The method of claim 6, wherein the analyzing includes:

determining that the length of the data is greater than the available amount of storage capacity; and

splitting the data into a plurality of portions prior to storing the data.

8. The method of claim 6, wherein the plurality of storage commands include a first storage command and a second storage command, wherein the first storage command is executable to store a portion of the data at a first append point location that is advanced sequentially through the non-volatile storage medium, and wherein the second storage command is executable to store a portion of the data at a second append point location that is advanced sequentially through the non-volatile storage medium.

9. The method of claim 6, wherein the available amount of storage capacity is a remaining amount of storage capacity for a page within the non-volatile storage medium.

10. The method of claim 6, wherein the length of the data is specified in the received request.

11. The method of claim 6, further comprising:

receiving storage requests to store data having different respective lengths.

12. An apparatus, comprising:

solid-state storage media; and

a storage controller configured to;

receive a storage request to store data to the solid-state storage media, wherein the storage request specifies a size of the data;

determine, based on the size, a number of append instructions to issue to the solid-state media, wherein each append instruction is executable by the solid-state storage media to store a respective portion of the data;

cause the solid-state storage media to store metadata of a map data structure usable by the storage controller to translate logical addresses specified in storage requests to corresponding physical addresses of the solid-state storage media; and

recover the map data structure to a current state by replaying packets stored since a checkpoint of the map data structure, wherein the replayed packets include metadata of the map data structure.

13. The apparatus of claim 12, wherein the storage controller is configured to determine the number of append instructions by comparing the size with an available mount of space within a page of the solid-state storage media.

14. The apparatus of claim 12, wherein the storage controller is configured to issue append instructions that are executable by the solid-state storage media to store portions of the data at different append point locations advanced sequentially through the solid-state storage media.

15. The apparatus of claim 12, wherein the storage controller is configured to direct the append instructions to different erase blocks of the solid-state storage media.

16. An apparatus, comprising:

solid-state storage media; and

a storage controller configured to;

receive a storage request to store data to the solid-state storage media, wherein the storage request specifies a size of the data; and

determine, based on the size, a number of append instructions to issue to the solid-state media, wherein each append instruction is executable by the solid-state storage media to store a respective portion of the data, wherein the solid-state storage media is configured to execute the append instructions in a different order than an order of issuance of the append instructions.