EFFICIENT ENFORCEMENT OF COMMAND EXECUTION ORDER IN SOLID STATE DRIVES

• US 20140059270A1
• Filed: 08/23/2012
• Published: 02/27/2014
• Est. Priority Date: 08/23/2012
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Zaltsman, Etai, Golov, Oren, Stern, Ori Moshe, Ojalvo, Shai
• Granted Patent: US 9,122,401 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0623 in relation to content
• 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]

Abstract

A method in a storage device includes receiving from a host storage commands for execution in a non-volatile memory of the storage device. At least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received. The received storage commands are executed in the non-volatile memory in accordance with internal scheduling criteria of the storage device, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.

Claims

1. A method, comprising:

in a storage device, receiving from a host storage commands for execution in a non-volatile memory of the storage device, wherein at least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received; and

executing the received storage commands in the non-volatile memory in accordance with internal scheduling criteria of the storage device, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.

2. The method according to claim 1, wherein executing the storage commands comprises permitting unblocked execution of the storage commands other than the subset concurrently with execution of the storage commands in the subset.

3. The method according to claim 1, wherein the non-volatile memory comprises multiple memory devices, and wherein executing the storage commands in accordance with the internal scheduling criteria comprises scheduling the storage commands for execution across the multiple memory devices.

4. The method according to claim 1, wherein receiving the storage commands comprises receiving from the host an indication that distinguishes the storage commands in the subset from the storage commands other than the subset.

5. The method according to claim 4, wherein receiving the storage commands comprises reading the storage commands from multiple queues defined between the host and the storage device, and wherein receiving the indication comprises reading the commands in the subset from one of the queues that is predefined as an in-order queue whose storage commands are to be executed in accordance with the order-of-arrival.

6. The method according to claim 1, wherein receiving the storage commands comprises receiving from the host respective sequence numbers, which mark the storage commands in the subset in accordance with the order-of-arrival.

7. The method according to claim 1, wherein executing the storage commands comprises performing the storage commands in the non-volatile memory in accordance with the internal scheduling policy, but acknowledging a given storage command to the host and recording the execution of the given storage command only upon successful completion of all the storage commands that precede the given storage command in the order-of-arrival.

8. The method according to claim 1, wherein executing the storage commands comprises storing data items provided in the storage commands in the non-volatile memory, storing in the non-volatile memory respective sequence numbers that are assigned to the data items in accordance with the order-of-arrival, and, upon recovery from a disruption in the storage device, identifying a gap in the stored sequence numbers and disqualifying the storage commands whose sequence numbers follow the gap.

9. The method according to claim 1, wherein receiving the storage commands comprises reading the storage commands from multiple queues defined between the host and the storage device, including reading a barrier command that is duplicated by the host across the multiple queues, halting each queue upon identifying the barrier command in the queue, and releasing the multiple queues upon reaching the barrier command in all the queues.

10. Apparatus, comprising:

an interface, which is configured to receive from a host storage commands for execution in a non-volatile memory, wherein at least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received; and

a processor, which is configured to execute the received storage commands in the non-volatile memory in accordance with internal scheduling criteria of the apparatus, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.

11. The apparatus according to claim 10, wherein the processor is configured to permit unblocked execution of the storage commands other than the subset concurrently with execution of the storage commands in the subset.

12. The apparatus according to claim 10, wherein the non-volatile memory comprises multiple memory devices, and wherein the processor is configured to execute the storage commands in accordance with the internal scheduling criteria by scheduling the storage commands for execution across the multiple memory devices.

13. The apparatus according to claim 10, wherein the processor is configured to receive from the host an indication that distinguishes the storage commands in the subset from the storage commands other than the subset.

14. The apparatus according to claim 13, wherein the processor is configured to read the storage commands from multiple queues defined between the host and the apparatus, and to receive the indication by reading the commands in the subset from one of the queues that is predefined as an in-order queue whose storage commands are to be executed in accordance with the order-of-arrival.

15. The apparatus according to claim 10, wherein the processor is configured to receive from the host respective sequence numbers, which mark the storage commands in the subset in accordance with the order-of-arrival.

16. The apparatus according to claim 10, wherein the processor is configured to execute the storage commands in the non-volatile memory in accordance with the internal scheduling policy, but to acknowledge a given storage command to the host and record the execution of the given storage command only upon successful completion of all the storage commands that precede the given storage command in the order-of-arrival.

17. The apparatus according to claim 10, wherein the processor is configured to store data items provided in the storage commands in the non-volatile memory, to store in the non-volatile memory respective sequence numbers that are assigned to the data items in accordance with the order-of-arrival, and, upon recovery from a disruption in the apparatus, to identify a gap in the stored sequence numbers and to disqualify the storage commands whose sequence numbers follow the gap.

18. The apparatus according to claim 10, wherein the processor is configured to read the storage commands from multiple queues defined between the host and the apparatus, including reading a barrier command that is duplicated by the host across the multiple queues, to halt each queue upon identifying the barrier command in the queue, and to release the multiple queues upon reaching the barrier command in all the queues.

19. Apparatus, comprising:

a non-volatile memory; and

a memory controller, which is configured to receive from a host storage commands for execution in the non-volatile memory, wherein at least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received, and to execute the received storage commands in the non-volatile memory in accordance with internal scheduling criteria of the apparatus, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.

20. A system, comprising:

a host, which is configured to issue storage commands; and

a storage device, which comprises a non-volatile memory and which is configured to receive the storage commands from the host for execution in the non-volatile memory, wherein at least a subset of the storage commands are to be executed in accordance with an order-of-arrival in which the storage commands in the subset are received, and to execute the received storage commands in the non-volatile memory in accordance with internal scheduling criteria of the storage device, which permit deviations from the order-of-arrival, but such that execution of the storage commands in the subset reflects the order-of-arrival to the host.