Data Rebuild on Feedback from a Queue in a Non-Volatile Solid-State Storage

• US 20160041868A1
• Filed: 08/07/2014
• Published: 02/11/2016
• Est. Priority Date: 08/07/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Davis, John D., Hayes, John, Tan, Zhangxi, Kannan, Hari, Miladinovic, Nenad
• Granted Patent: US 9,483,346 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• 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/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1102 Codes on graphs and decoding on graphs, e.g. low-density parity check [LDPC] codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

A storage cluster is provided. The storage cluster includes a plurality of storage nodes, each of the plurality of storage nodes having nonvolatile solid-state memory and a plurality of operations queues coupled to the solid-state memory. The plurality of storage nodes is configured to distribute the user data and metadata throughout the plurality of storage nodes such that the plurality of storage nodes can access the user data with a failure of two of the plurality of storage nodes. Each of the plurality of storage nodes is configured to determine whether a read of 1 or more bits in the solid-state memory via a first path is within a latency budget. The plurality of storage nodes is configured to perform a read of user data or metadata via a second path, responsive to a determination that the read of the bit via the first path is not within the latency budget.

Claims

1. A method for accessing data in a plurality of storage nodes having nonvolatile solid-state memory, comprising:

distributing user data throughout the plurality of storage nodes through erasure coding such that in event of a determination by the plurality of storage nodes that two of the plurality of storage nodes are unreachable the user data is accessible via the erasure coding from a remainder of the plurality of storage nodes, wherein the plurality of storage nodes are coupled as a storage cluster;

receiving a request that directs a read of the non-volatile solid-state memory, wherein the read of the non-volatile solid-state memory is based at least in part on reading a first bit in the non-volatile solid-state memory via a first path, and wherein a plurality of operations queues is coupled to the first path;

determining, based on contents of the plurality of operations queues, whether the reading the first bit via the first path can be performed within a latency budget; and

determining a second path to achieve the read of the non-volatile solid-state memory, responsive to determining that the reading of the first bit via the first path cannot be performed within the latency budget, wherein a processor performs at least one method operation.

2. The method of claim 1, further comprising:

performing the read of the non-volatile solid-state memory via the second path, wherein the read of the non-volatile solid-state memory includes reading a data segment that includes the first bit, and wherein the second path includes reconstructing the first bit via application of the erasure coding.

3. The method of claim 1, further comprising:

performing the read of the non-volatile solid-state memory via the second path, wherein the read of the non-volatile solid-state memory includes reading metadata that includes the first bit, and wherein the second path includes reading a redundant copy of the first bit.

4. The method of claim 1, further comprising:

performing the read of the non-volatile solid-state memory via the second path, wherein the read of the non-volatile solid-state memory includes reading user data that includes the first bit, and wherein the second path includes reading a redundant copy of the first bit.

5. The method of claim 1, further comprising:

performing the read of the non-volatile solid-state memory via the second path, wherein the read of the non-volatile solid-state memory includes reading a data segment that includes the first bit, and wherein the second path includes rebuilding the data segment via application of the erasure coding.

6. The method of claim 1, wherein:

the second path bypasses the first path;

the first path includes a first channel bus coupled to a first flash die and to the plurality of operations queues; and

the second path includes a second channel bus coupled to a second flash die.

7. The method of claim 1, wherein the determining whether the reading the first bit via the first path can be performed within the latency budget includes at least one of:

determining whether one or more further data reads in the plurality of operations queues has higher priority or higher weighting than reading the first bit;

determining whether one or more data writes in the plurality of operations queues has higher priority or higher weighting than reading the first bit;

determining whether a write queue of the plurality of operations queues is close to overflowing; and

determining whether an erase operation in the plurality of operations queues has higher priority or higher weighting than reading the first bit.

8. A plurality of storage nodes, comprising:

the plurality of storage nodes configured to communicate together as a storage cluster, each of the plurality of storage nodes having non-volatile solid-state memory for user data storage, the plurality of storage nodes configured to distribute the user data and metadata associated with the user data throughout the plurality of storage nodes such that the plurality of storage nodes maintain ability to read the user data, using erasure coding, despite a loss of two of the plurality of storage nodes;

each of the plurality of storage nodes having a plurality of queues configured to hold a plurality of operations relating to the non-volatile solid-state memory;

each of the plurality of storage nodes configured to determine whether a read of a bit in the non-volatile solid-state memory is achievable within a delay budget, based on operations present in the plurality of queues; and

the plurality of storage nodes configured to determine an alternate path for performing a read of user data or metadata responsive to a determination that the read of the bit in the non-volatile solid-state memory is not achievable within the delay budget, the alternate path bypassing the read of the bit.

9. The plurality of storage nodes of claim 8, wherein:

the non-volatile solid-state memory includes flash memory for user data storage;

the plurality of queues is coupled to the flash memory; and

the alternate path includes a differing one of the plurality of storage nodes than one of the plurality of storage nodes having the bit in the non-volatile solid-state memory.

10. The plurality of storage nodes of claim 8, further comprising:

the plurality of storage nodes configured to apply the alternate path in performing the read of the user data or the metadata, wherein the alternate path includes one of;

a redundant copy of a portion of the user data, a redundant copy of a portion of the metadata, or application of the erasure coding.

11. The plurality of storage nodes of claim 8, wherein the delay budget is based on a targeted read latency for reading the user data.

12. The plurality of storage nodes of claim 8, further comprising:

the plurality of queues configured to provide information regarding the operations present in the plurality of queues, wherein based on operations present in the plurality of queues includes at least one of;

based on priorities of the operations present in the plurality of queues, based on weightings of the operations present in the plurality of queues, based on quantity of the operations present in the plurality of queues, or based on types of the operations present in the plurality of queues.

13. The plurality of storage nodes of claim 8, further comprising:

the plurality of storage nodes having a plurality of channels, each channel coupling a portion of the non-volatile solid-state memory to a subset of the plurality of queues, wherein the alternate path includes a differing channel from a channel involved in the read of the bit in the non-volatile solid-state memory.

14. The plurality of storage nodes of claim 8, wherein:

the erasure coding includes at least one of a redundant copy of at least a portion of the user data, or error correction coding of at least a portion of the user data; and

the alternate path includes one of a path to the redundant copy of the at least a portion of the user data, or a path with application of the error correction coding to the at least a portion of the user data.

15. A storage cluster, comprising:

a plurality of storage nodes, each of the plurality of storage nodes having nonvolatile solid-state memory for storage of user data, each of the plurality of storage nodes having a plurality of operations queues coupled to the non-volatile solid-state memory;

the plurality of storage nodes configured to distribute the user data and metadata associated with the user data throughout the plurality of storage nodes such that the plurality of storage nodes can access the user data, via erasure coding, with a failure of two of the plurality of storage nodes;

each of the plurality of storage nodes configured to determine whether a read of a bit in the non-volatile solid-state memory via a first path is within a latency budget, based on feedback from the plurality of operations queues; and

the plurality of storage nodes configured to perform a read of the user data or the metadata via a second path, responsive to a determination that the read of the bit via the first path is not within the latency budget.

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

each of the plurality of storage nodes includes a non-volatile solid-state storage having flash memory, wherein the non-volatile solid-state memory includes the flash memory;

each non-volatile solid-state storage includes a plurality of channel busses coupled to the flash memory; and

each of the plurality of channel busses is coupled to a subset of the plurality of operations queues.

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

the plurality of operations queues configured to provide, as the feedback, information regarding at least one of;

fullness of each of the plurality of operations queues, weighting of operations in the plurality of operations queues, priorities of operations in the plurality of operations queues, quantity of operations in the plurality of operations queues, or contents of the plurality of operations queues.

18. The storage cluster of claim 15, wherein the second path includes one of:

a path to a redundant data shard, a path to a redundant metadata bit, or a path to a plurality of data shards from which a corrected data segment can be constructed.

19. The storage cluster of claim 15, further comprising:

the plurality of operations queues including a plurality of read queues, a plurality of write queues, a plurality of erase queues, and a plurality of status queues.

20. The storage cluster of claim 15, wherein:

the first path includes a first subset of the plurality of operations queues, a first channel bus, and a first flash die; and

the second path includes a second subset of the plurality of operations queues, a second channel bus, and a second flash die.