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

• US 10,185,506 B2
• Filed: 11/21/2016
• Issued: 01/22/2019
• 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
• Application Number:
  US15/357,243
• Publication Number:
  US 20170068476A1
• Time in Patent Office: 792 Days
• 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 for queues in a non-volatile solid-state storage, performed by a storage system, comprising:

receiving a request for a write operation into one of a plurality of operation queues of a non-volatile solid-state storage;

assigning a sequential address to data of the write operation, according to a progression of sequential addresses assigned to data for write operations; and

selecting, from the plurality of operation queues, the write operation for execution, based on a benefit to the non-volatile solid-state storage, with the write operation for execution having a greater benefit than a further write operation for garbage collection, based on the sequential address of the data of the write operation and an address of data of the further write operation for garbage collection, the sequential address and the address in accordance with the progression.

2. The method of claim 1, wherein the sequential address is in a sequential nonrepeating address space associated with a medium address space, a segment address space, or a virtual allocation unit address space.

3. The method of claim 1, further comprising:

persisting a message that includes the request for the write operation, through redundant copies of the message, across the storage system.

4. The method of claim 1, further comprising:

recording a message that includes the request for the write operation in non-volatile random-access memory (NVRAM); and

writing the message that includes the request for the write operation from the NVRAM to flash memory, responsive to a power failure.

5. The method of claim 1, wherein the assigning comprises:

assigning the sequential address as a segment address of the data of the write operation, by an authority for the data of the write operation, the authority being one of a plurality of authorities in the storage system.

6. The method of claim 1, further comprising:

forwarding the request for the write operation from a first one of a plurality of storage nodes of the storage system to a second one of the plurality of storage nodes of the storage system having an authority for the data of the write operation, the authority being one of a plurality of authorities in the storage system.

7. The method of claim 1, further comprising:

generating one or more addresses in medium address space, based on an inode identification for a file;

generating a plurality of addresses in segment address space, based on the one or more addresses in the medium address space, wherein the sequential address is associated with the medium address space or the segment address space; and

translating the plurality of addresses in the segment address space to a plurality of physical flash memory locations.

8. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a processor, cause the processor to perform a method comprising:

placing a write operation into one of a plurality of operation queues of a non-volatile solid-state storage;

assigning an address to data of the write operation, the address from a sequential, nonrepeating address space and according to a progression of sequential addresses assigned to other data for write operations in the non-volatile solid-state storage; and

executing the write operation from one of the plurality of operation queues, based on a benefit to the non-volatile solid-state storage, with the write operation for execution having a greater benefit than a further write operation for garbage collection, based on the sequential address of the data of the write operation and an address of data of a further write operation for garbage collection, the sequential address and the address in accordance with the progression.

9. The computer-readable media of claim 8, wherein the method further comprises:

storing redundant copies of a message that includes the request for the write operation, in a plurality of storage nodes of the storage system.

10. The computer-readable media of claim 8, wherein the method further comprises:

writing a message that includes the request for the write operation, to a first memory in the storage system; and

writing the message from the first memory to flash memory in the storage system, responsive to a power failure, wherein the writing is supported by an energy reserve.

11. The computer-readable media of claim 8, wherein the assigning comprises:

assigning, by an authority for the data of the write operation, the address from the sequential, nonrepeating address space to a data segment as a segment address, wherein a storage cluster that includes the non-volatile solid-state storage and the plurality of operation queues has a plurality of such authorities.

12. The computer-readable media of claim 8, wherein the method further comprises:

receiving a request including the write operation at one of a plurality of storage nodes of a storage cluster;

determining which of a plurality of authorities in the plurality of storage nodes is associated with data for the request; and

forwarding the request to a further one of the plurality of storage nodes having the one of the plurality of authorities determined to be associated with the data for the request.

13. The computer-readable media of claim 8, wherein the method further comprises:

translating an inode identification for a file to one or more addresses in a medium address space;

translating the one or more addresses in the medium address space to a plurality of data segment addresses in segment address space, wherein the address from the sequential, nonrepeating address space is one of the one or more addresses in the medium address space or one of the plurality of data segment addresses in the segment address space; and

translating the plurality of data segment addresses to a plurality of physical flash memory locations.

14. A storage system, comprising;

non-volatile solid-state storage memory;

a plurality of operation queues coupled to the non-volatile solid-state storage memory; and

one or more processors configured to place a first write operation into one of the plurality of operation queues of the storage system, configured to assign an address to data of the first write operation, the address being from a sequential nonrepeating address space according to a progression of sequential addresses assigned to other data for write operations in the non-volatile solid-state storage, and configured to select and execute the first write operation from the one of the plurality of operation queues as having greater benefit for the storage system than a second write operation for garbage collection, based on the address assigned to the data of the first write operation and an address of data of the second write operation, the address assigned to the first write operation and the address of the data of the second write operation in accordance with the progression.

15. The storage system of claim 14, further comprising:

a plurality of storage nodes, coupled as a storage cluster; and

a plurality of storage units, with a first storage unit having the plurality of operation queues and the non-volatile solid-state storage memory and each further storage unit having a further plurality of operation queues and further non-volatile solid-state storage memory.

16. The storage system of claim 14, wherein the one or more processors are further configured to distribute over a communication path of the storage system a plurality of copies of a message that includes a request for the write operation, for persisting the message throughout the storage system.

17. The storage system of claim 14, further comprising:

a first memory;

a second memory;

an energy reserve coupled to the first memory and the second memory;

the one or more processors further configured to write a message that includes the request for the write operation, to the first memory; and

the one or more processors further configured to write the message from the first memory to the second memory, supported by the energy reserve, responsive to a power failure.

18. The storage system of claim 14, further comprising:

the storage system having a plurality of authorities; and

the one or more processors configured to determine which one of the plurality of authorities is associated with the data of the first write operation, wherein the one or more processors configured to assign the address to the data of the first write operation includes the one of the plurality of authorities configured to assign a data segment address to the data of the first write operation.

19. The storage system of claim 14, further comprising:

a plurality of storage nodes, coupled as a storage cluster;

the plurality of storage nodes having a plurality of authorities for data in the storage cluster; and

the one or more processors further configured to forward a request for the first write operation from a first one of the plurality of storage nodes to a second one of the plurality of storage nodes that has an authority for the data of the first write operation.

20. The storage system of claim 14, further comprising:

the one or more processors further configured to translate an inode identification for a file to one or more addresses in a medium address space, translate the one or more addresses in the medium address space to a plurality of data segment addresses in segment address space, and translate the plurality of data segment addresses in the segment address space to a plurality of physical memory locations in the non-volatile solid-state storage memory, wherein the address from the sequential nonrepeating address space is one of the one or more addresses in the medium address space or one of the plurality of data segment addresses in the segment address space.