Utilization of erasure codes in a storage system

• US 10,671,480 B2
• Filed: 03/30/2018
• Issued: 06/02/2020
• Est. Priority Date: 06/04/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Hayes, John, Colgrove, John, Davis, John D.
• Primary Examiner(s): Lamarre, Guy J
• Assistant Examiner(s): Alshack, Osman M
• Application Number:
  US15/941,580
• Publication Number:
  US 20180225174A1
• Time in Patent Office: 795 Days
• Field of Search: 714763, 714764, 714755, 714770, 714773
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2201/845 Systems in which the redundancy can be transformed in increased performance
• CPC Class Codes: G06F 2212/7206 Reconfiguration of flash memory system
• CPC Class Codes: G06F 2212/7207 management of metadata or control data
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0607 by facilitating the process of upgrading existing storage systems, e.g. for improving compatibility between host and storage device
• 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/0632 by initialisation or re-initialisation of storage systems
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• 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: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial

Abstract

A plurality of storage nodes in a single chassis is provided. The plurality of storage nodes in the single chassis is configured to communicate together as a storage cluster. Each of the plurality of storage nodes includes nonvolatile solid-state memory for user data storage. The plurality of storage nodes is 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 the ability to read the user data, using erasure coding, despite a loss of two of the plurality of storage nodes. A plurality of compute nodes is included in the single chassis, each of the plurality of compute nodes is configured to communicate with the plurality of storage nodes. A method for accessing user data in a plurality of storage nodes having nonvolatile solid-state memory is also provided.

Claims

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

distributing the user data throughout the plurality of storage nodes using one or more of a set of erasure codes, the one or more erasure codes determined by a plurality of authorities, each authority of the plurality of authorities having ownership for a corresponding range of the user data;

in response to determining that one of the plurality of storage nodes is unreachable;

reading the user data across a remainder of the plurality of storage nodes, using a first subset of erasure codes from the set of erasure codes;

writing the user data across the remainder of the plurality of storage nodes, using a second subset of erasure codes from the set of erasure codes; and

accessing the user data, via one or more of the set of erasure codes as determined by at least one of the plurality of authorities, from the remainder of the plurality of storage nodes.

2. The method of claim 1, wherein the set of erasure codes includes two or more differing erasure codes coexisting in the plurality of storage nodes.

3. The method of claim 1, wherein determining that one of the plurality of storage nodes is unreachable is based on one of lack of a heartbeat, lack of a response to a query, or a timeout.

4. The method of claim 1, wherein the plurality of storage nodes are distributed throughout multiple chassis.

5. The method of claim 1, wherein the at least one authority is located on a differing storage node from the one of the plurality of storage nodes determined to be unreachable.

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

distributing user data throughout a plurality of storage nodes using one or more of a set of erasure codes, the one or more erasure codes determined by a plurality of authorities, each authority of the plurality of authorities having ownership for a corresponding range of the user data;

in response to determining that one of the plurality of storage nodes is unreachable;

reading the user data across a remainder of the plurality of storage nodes, using a first subset of erasure codes from the set of erasure codes;

writing the user data across the remainder of the plurality of storage nodes, using a second subset of erasure codes from the set of erasure codes; and

accessing the user data, via one or more of the set of erasure codes as determined by at least one of the plurality of authorities, from the remainder of the plurality of storage nodes.

7. The computer readable media of claim 6, wherein the set of erasure codes include two or more differing erasure codes coexisting in the plurality of storage nodes.

8. The computer readable media of claim 6, wherein determining that one of the plurality of storage nodes is unreachable is based on one of lack of a heartbeat, lack of a response to a query, or a timeout.

9. The computer readable media of claim 6, wherein the plurality of storage nodes are distributed throughout multiple chassis.

10. The computer readable media of claim 6, wherein the at least one authority is located on a differing storage node from the one of the plurality of storage nodes determined to be unreachable.

11. A storage cluster, comprising:

solid-state storage memory;

a processor, configurable to execute instructions causing the processor to;

distribute user data throughout a plurality of storage nodes using one or more of a set of erasure codes, the one or more erasure codes determined by a plurality of authorities, each authority of the plurality of authorities having ownership for a corresponding range of the user data;

in response to determining that one of the plurality of storage nodes is unreachable;

reading the user data across a remainder of the plurality of storage nodes, using a first subset of erasure codes from the set of erasure codes;

writing the user data across the remainder of the plurality of storage nodes, using a second subset of erasure codes from the set of erasure codes; and

accessing the user data, via one or more of the set of erasure codes as determined by at least one of the plurality of authorities, from the remainder of the plurality of storage nodes.

12. The storage cluster of claim 11, wherein the erasure codes include two or more differing erasure codes coexisting in the plurality of storage nodes.

13. The storage cluster of claim 11, wherein determining that one of the plurality of storage nodes is unreachable is based on one of lack of a heartbeat, lack of a response to a query, or a timeout.

14. The storage cluster of claim 11, wherein the plurality of storage nodes are distributed throughout multiple chassis.