Scheduling policy for queues in a non-volatile solid-state storage

• US 8,874,836 B1
• Filed: 07/03/2014
• Issued: 10/28/2014
• Est. Priority Date: 07/03/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Hayes, John, Gupta, Shantanu, Davis, John, Gold, Brian, Tan, Zhangxi
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US14/323,707
• Time in Patent Office: 117 Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 13/1626 by reordering requests
• CPC Class Codes: G06F 2206/1014 One time programmable [OTP] memory, e.g. PROM, WORM
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0623 in relation to content
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• 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]
• 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: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial

Abstract

A method of applying scheduling policies is provided. The method includes distributing user data throughout a plurality of storage nodes through erasure coding, wherein the plurality of storage nodes are housed within a single chassis coupling the storage nodes as a cluster. The method includes receiving operations relating to a non-volatile memory of one of the plurality of storage nodes into a plurality of operation queues. The method includes evaluating each of the operations in the plurality of operation queues as to benefit to the non-volatile solid-state storage according to a plurality of policies. For each channel of a plurality of channels coupling the operation queues to the non-volatile memory, the method includes iterating a selection and an execution of a next operation from the plurality of operation queues, with each next operation having a greater benefit than at least a subset of operations remaining in the operation queues.

Claims

1. A method of applying scheduling policies to a non-volatile solid-state storage, comprising:

distributing user data throughout a plurality of storage nodes through erasure coding, wherein the plurality of storage nodes are housed within a single chassis that couples the storage nodes as a cluster;

receiving operations relating to a non-volatile memory of a non-volatile solid-state storage of one of the plurality of storage nodes into a plurality of operation queues;

evaluating each of the operations in the plurality of operation queues as to benefit to the non-volatile solid-state storage according to a plurality of policies;

for each channel of a plurality of channels coupling the operation queues to the non-volatile memory, iterating a selection and an execution of a next operation from the plurality of operation queues, with each next operation having a greater benefit than at least a subset of operations remaining in the operation queues; and

assigning sequential addresses, within a bounded address space, to newly arriving data write operations, wherein a first data write resulting from a garbage collection is accorded a lower benefit than a second data write of the newly arriving data write operations as a result of the first data write referencing a lower address than the second data write, wherein at least one method operation is performed by a processor.

2. The method of claim 1, wherein the operations include reading from the non-volatile memory, writing to the non-volatile memory, and erasing a portion of the non-volatile memory, and wherein the method comprises:

repeating the receiving for additional storage nodes; and

evaluating operations across the additional storage nodes as to the benefit.

3. The method of claim 1, further comprising:

reevaluating the operations remaining in the operation queues as to the benefit, wherein the reevaluating takes into account an aging of the operations remaining in the operation queues.

4. The method of claim 1, wherein the selection of the next operation from the plurality of operation queues includes one of selecting an operation from among operations at heads of the plurality of operation queues, or selecting an operation from anywhere in operation queues coupled to the each channel.

5. The method of claim 1, wherein:

at least one of the operations relating to the non-volatile memory includes a tag;

the tag indicates one of an inode identifier (ID) is being accessed, a medium address is being accessed, or a priority is attached by a filesystem to the at least one of the operations; and

the evaluating assigns the benefit based on the tag.

6. The method of claim 1, further comprising:

pausing an interruptible operation having a first benefit according to the plurality of policies, wherein the interruptible operation is one of an interruptible write or an interruptible erase;

executing an operation having a second benefit, according to the plurality of policies, greater than the first benefit; and

resuming the interruptible operation, responsive to completing the write or erase operation having the second benefit.

7. A storage cluster, comprising:

a plurality of storage nodes within a single chassis;

each of the plurality of storage nodes having nonvolatile solid-state memory for storage of user data, the nonvolatile solid-state memory comprising;

a plurality of operation queues;

a plurality of channel busses, configured to couple the plurality of operation queues to a non-volatile memory, each of the plurality of channel busses having a channel;

a processor, configured to perform repeating actions including;

determining a relative benefit of each of a plurality of operations in the plurality of operation queues, based on a plurality of policies, the plurality of policies including assigning sequential addresses, within a bounded address space, to newly arriving data write operations, wherein a first data write resulting from a garbage collection is accorded a lower benefit than a second data write of the newly arriving data write operations as a result of the first data write referencing a lower address than the second data write;

determining for each channel one of the plurality of operations in the plurality of operation queues having a greater relative benefit than others of the plurality of operations in the plurality of operation queues; and

performing, for each channel, the determined one of the plurality of operations.

8. The storage cluster of claim 7, wherein each of the channel busses has, among the plurality of operation queues, at least one read queue, at least one write queue, and at least one erase queue.

9. The storage cluster of claim 7, wherein the plurality of policies includes operations on user data per client request having higher benefit than operations resulting from garbage collection.

10. The storage cluster of claim 7, wherein determining the relative benefit is based at least in part on aging of the operations in the plurality of operation queues.

11. The storage cluster of claim 7, wherein the actions further include interrupting one of an interruptible write or an interruptible erase in order to execute an operation having a greater relative benefit than the interruptible write or the interruptible erase.

12. The storage cluster of claim 7, wherein the processor determines the relative benefit based in part on addresses associated with operations.

13. A storage cluster comprising:

a plurality of storage nodes within a single chassis;

each of the plurality of storage nodes having nonvolatile solid-state memory for storage of user data, the nonvolatile solid-state memory comprising;

a non-volatile memory;

a controller, coupled to the non-volatile memory;

a plurality of queues, coupled to or included in the controller, the plurality of queues coupled to the non-volatile memory by a plurality of channels, each of the plurality of queues configured to hold therein a plurality of operations relating to the non-volatile memory; and

the controller configured to perform actions including;

weighting each operation in each of the plurality of queues, according to a plurality of policies, the plurality of policies including assigning sequential addresses, within a bounded address space, to newly arriving data write operations, wherein a first data write resulting from a garbage collection is accorded a lower benefit than a second data write of the newly arriving data write operations as a result of the first data write referencing a lower address than the second data write;

selecting, for each of the plurality of channels, a next operation from the plurality of queues, according to the weighting; and

executing, for each of the plurality of channels, the next operation.

14. The storage cluster of claim 13, further comprising:

the non-volatile memory includes a plurality of non-volatile dies; and

a plurality of channel busses, wherein each of the plurality of channels is coupled to a subset of the plurality of non-volatile dies by a one of the plurality of channel busses.

15. The storage cluster of claim 13, wherein the plurality of queues includes at least one of a read queue, a write queue, an erase queue, or queues according to traffic classes.

16. The storage cluster of claim 13, further comprising:

the non-volatile memory includes a plurality of non-volatile dies, wherein the plurality of queues coupled to the non-volatile memory by the plurality of channels includes each channel coupling to a subset of the plurality of queues and to a subset of the plurality of dies according to addresses of the subset of the plurality of dies.

17. The storage cluster of claim 13, further comprising:

each of the plurality of queues configured to associate a weighting parameter with each of the plurality of operations therein, wherein the weighting parameter includes at least one of a tag relating to an address space, a result of the weighting according to the plurality of policies, or an aging parameter relating to length of time each of the plurality of operations is present in each of the plurality of queues.

18. The storage cluster of claim 13, wherein the plurality of policies is selected from a group consisting of:

writing user data per client request has higher benefit than a data write resulting from garbage collection;

reading user data per client request has higher benefit than a data read resulting from garbage collection;

reading user data has higher benefit than erasing;

writing user data has higher benefit than erasing;

data reads or writes on an indicated client critical path have higher benefit than data reads or writes not on an indicated client critical path;

a data write operation that has been in a queue for a longer time has greater benefit than a data write operation that has been in a queue for a shorter time; and

a data read operation that has been in a queue for a longer time has greater benefit than a data read operation that has been in a queue for a shorter time.

19. The storage cluster of claim 13, wherein the plurality of policies comprises:

erasing has highest benefit if the erasing prevents having insufficient storage capacity for new writes;

data writes having shorter latency have higher benefit than data writes having longer latency; and

data reads having shorter latency have higher benefit than data reads having longer latency.