Apparatus, system, and method for managing commands of solid-state storage using bank interleave

• US 9,575,902 B2
• Filed: 12/06/2007
• Issued: 02/21/2017
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Longitude Enterprise Flash S.à r.l. (Vector Capital Corporation)
• Inventors: Flynn, David, Lagerstedt, Bert, Strasser, John, Thatcher, Jonathan, Zappe, Michael
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): DARE, RYAN A
• Application Number:
  US11/952,095
• Publication Number:
  US 20080229079A1
• Time in Patent Office: 3,365 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 1/183 Internal mounting support structures, e.g. for printed circuit boards, internal connecting means for buses G06F13/409
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• 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 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 13/426 using an embedded synchronisation, e.g. Firewire bus, Fibre Channel bus, SSA bus
• CPC Class Codes: G06F 2211/002 Bus
• CPC Class Codes: G06F 2211/103 Hybrid, i.e. RAID systems with parity comprising a mix of RAID types
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/222 Non-volatile memory
• CPC Class Codes: G06F 2212/70 Details relating to dynamic memory management
• CPC Class Codes: G06F 2212/7203 Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 : Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 : Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0608 : Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 : in relation to throughput
• CPC Class Codes: G06F 3/0619 : in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0643 : Management of files
• CPC Class Codes: G06F 3/065 : Replication mechanisms
• CPC Class Codes: G06F 3/0652 : Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0656 : Data buffering arrangements
• 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]
• CPC Class Codes: G06F 3/0685 : Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0688 : Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 9/52 : Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/54 : Interprogram communication
• CPC Class Codes: H04L 67/02 : based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/1097 : for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 : Complex or three-dimensional-arrangements; Stepped or dual mother boards
• CPC Class Codes: H05K 7/1487 : Blade assemblies, e.g. blade cases or inner arrangements within a blade
• CPC Class Codes: Y02D 10/00 : Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

An apparatus, system, and method are disclosed for efficiently managing commands in a solid-state storage device that includes a solid-state storage arranged in two or more banks. Each bank is separately accessible and includes two or more solid-state storage elements accessed in parallel by a storage input/output bus. The solid-state storage includes solid-state, non-volatile memory. The solid-state storage device includes a bank interleave that directs one or more commands to two or more queues, where the one or more commands are separated by command type into the queues. Each bank includes a set of queues in the bank interleave controller. Each set of queues includes a queue for each command type. The bank interleave controller coordinates among the banks execution of the commands stored in the queues, where a command of a first type executes on one bank while a command of a second type executes on a second bank.

Claims

1. A method comprising:

receiving storage commands at respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device, wherein the storage commands include storage commands of a first type received in an order at a first command queue associated with a first one of the banks and storage commands of a second, different type, received in an order at a second command queue associated with a second one of the banks;

issuing commands from the first and second command queues such that execution of a first command of the first type overlaps in time with execution of a second command of the second type,

wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command; and

issuing commands from the first command queue in an order different than the order in which the commands were received at the first command queue.

2. The method of claim 1, wherein the command queues include one or more first-in-first-out (FIFO) queues.

3. The method of claim 1, wherein the first command queue is an erase queue configured to receive erase commands, and wherein the second command queue is a read queue configured to receive read commands.

4. The method of claim 1, further comprising

creating subcommands from commands in the command queues;

and

issuing the subcommands for execution such that a subcommand of a first type executes on the first bank concurrent with execution of a subcommand of a second type on the second bank.

5. The method of claim 1, further comprising issuing write commands in the command queues for execution, wherein the write commands are executable to write data sequentially at an append point that is advanced through the two or more banks.

6. The method of claim 1, wherein the issuing of commands from the first and second command queues includes selecting the first and second commands for execution based on their execution durations.

7. A method, comprising:

directing storage commands to respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device, wherein the storage commands include storage commands of a first type directed in an order to a first command queue associated with a first one of the banks and storage commands of a second, different type, directed in an order to a second command queue associated with a second one of the banks;

sequencing execution of two or more commands in the command queues such that execution of a first command of the first type overlaps in time with execution of a second command of the second type; and

executing one or more write commands in the command queues such that data is written sequentially at an append point that is advanced through the two or more banks, wherein commands are issued from the first command queue in an order different than the order in which the commands are directed to the first command queue,

wherein an execution duration of the command of the first type and an execution duration of the command of the second type differ by at least an order of magnitude.

8. The method of claim 7, further comprising:

mapping a logical address associated with a read command in one of the command queues to a corresponding physical address where data was written within one of the two or more banks.

9. The method of claim 7, wherein execution of the two or more commands is sequenced to optimize performance of the banks.

10. The method of claim 7, wherein sequencing execution of the two or more commands includes issuing commands from a command queue in an order different than an order in which the commands were received at the command queue.

11. The method of claim 7, wherein sequencing execution of the two or more commands includes selecting the command of the first type and the command of the second type for execution based on their execution durations.

12. A method, comprising:

storing storage commands in respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device; and

selecting two or more commands in the command queues for execution such that execution of a first command of a first execution duration on a first one of the banks overlaps in time with execution of a second command of a second, different execution duration on a second one of the banks, wherein the selecting of the first and second commands for execution is based on the first and second execution durations,

wherein the first command is of a first type, wherein the second command is of a second type, and wherein the first and second execution durations differ by at least an order of magnitude.

13. The method of claim 12, wherein the selecting is performed by an arbiter circuit within the non-volatile solid-state storage device.

14. The method of claim 12, wherein the selecting is performed to minimize bus idle time.

15. The method of claim 12, further comprising:

issuing commands from a command queue in an order different than an order in which the commands were stored in the command queue.

16. The method of claim 12, wherein the selecting includes selecting write commands in the command queues for execution, wherein the write commands are executable to write data sequentially at an append point that is advanced through the two or more banks.

17. A method, comprising:

directing storage commands to respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device; and

sequencing execution of two or more commands in the command queues such that execution of a first command of a first type on a first one of the banks overlaps with execution of a second command of a second, different type on a second one of the banks, wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command.

18. The method of claim 17, wherein the command queues of a bank include a read queue configured to store read commands, a write queue configured to store write commands, and an erase queue configured to store erase commands.

19. The method of claim 17, further comprising:

sequencing execution of one or more commands that were not stored within the command queues.

20. The method of claim 17, wherein sequencing execution of the two or more commands includes issuing commands from one of the command queues in an order different than an order in which the commands were received at the command queue.

21. The method of claim 17, further comprising:

sequencing execution of write commands in the command queues, wherein the write commands are executable by the two or more banks to write data sequentially at an append point that is advanced through the two or more banks.

22. The method of claim 17, wherein sequencing execution of the two or more commands includes selecting the first command and the second command for execution based on the execution duration of the first command and the execution duration of the second command.

23. An FPGA solid-state storage controller for controlling execution of storage commands on non-volatile solid state storage, the storage controller comprising circuitry configured to:

receive storage commands at respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device, wherein the storage commands include storage commands of a first type received in an order at a first command queue associated with a first one of the banks and storage commands of a second, different type, received in an order at a second command queue associated with a second one of the banks;

issue commands from the first and second command queues such that execution of a first command of the first type overlaps in time with execution of a second command of the second type, wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command; and

issue commands from the first command queue in an order different than the order in which the commands were received at the first command queue.

24. An FPGA solid-state storage controller for controlling execution of storage commands on non-volatile solid state storage, the storage controller comprising circuitry configured to:

direct storage commands to respective command queues, each command queue associated with one of two or more banks of a non-volatile solid-state storage device, wherein the storage commands include storage commands of a first type directed in an order to a first command queue associated with a first one of the banks and storage commands of a second, different type, directed in an order to a second command queue associated with a second one of the banks;

sequence execution of two or more commands in the command queues such that execution of a first command of the first type overlaps in time with execution of a second command of the second type; and

execute one or more write commands in the command queues such that data is written sequentially at an append point that is advanced through the two or more banks, wherein commands are issued from the first command queue in an order different than the order in which the commands are directed to the first command queue,

wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command.

25. A non-volatile solid-state storage device comprising:

non-volatile solid-state storage arranged in two or more banks each bank configured to operate independently; and

a bank interleave controller configured to;

store storage commands in respective command queues, each command queue associated with one of the two or more banks; and

select two or more commands in the command queues for execution such that execution of a first command of a first execution duration on a first one of the banks overlaps in time with execution of a second command of a second, different execution duration, on a second one of the banks, wherein the selecting of the first and second commands for execution is based on the first and second execution durations,

wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command.

26. A non-volatile solid-state storage device comprising:

non-volatile solid-state storage arranged in two or more banks each bank configured to operate independently; and

a bank interleave controller configured to;

direct storage commands to respective command queues, each command queue associated with one of the two or more banks; and

sequence execution of two or more commands in the command queues such that execution of a first command of a first type on a first one of the banks overlaps with execution of a second command of a second, different type on a second one of the banks, wherein an execution duration of the first command is at least an order of magnitude greater than an execution duration of the second command.