Rebuild prioritization during a plurality of concurrent data object write operations

• US 10,042,709 B2
• Filed: 01/24/2017
• Issued: 08/07/2018
• Est. Priority Date: 06/06/2011
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Gladwin, S. Christopher, Resch, Jason K., Shirley, Jr., Thomas F.
• Primary Examiner(s): Thammavong, Prasith
• Application Number:
  US15/414,338
• Publication Number:
  US 20170132080A1
• Time in Patent Office: 560 Days
• Field of Search: None
• 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 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 2211/1035 Keeping track, i.e. keeping track of data and parity changes
• 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/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 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: H03M 13/1105 Decoding
• CPC Class Codes: H03M 13/1515 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
• CPC Class Codes: H04L 65/00 Network arrangements, protocols or services for supporting real-time applications in data packet communication real-time or near real-time messaging, e.g. instant messaging [IM] H04L51/04; selective video distribution H04N21/00
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/762 at the source reformatting of additional data in video distribution servers H04N21/2355
• 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: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W
• CPC Class Codes: H04N 21/2181 comprising remotely distributed storage units, e.g. when movies are replicated over a plurality of video servers distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: H04N 21/23109 : by placing content in organized collections, e.g. EPG data repository details of retrieval of video data and associated meta data in video databases G06F16/739
• CPC Class Codes: H04N 21/23116 : involving data replication, e.g. over plural servers synchronization of replicated data G06F11/1658; error detection or correction by means of data replication G06F11/2053; replication in distributed file systems G06F16/10; replication in distributed file systems G06F16/27; replication or mirroring of data in data networks H04L67/1095
• CPC Class Codes: H04N 21/2393 : involving handling client requests scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04N 21/8586 : by using a URL processing chained hypermedia data for information retrieval G06F16/94; information retrieval from the Internet by using URLs G06F16/955; URL in broadcast information H04H20/93; Web-based protocols H04L67/02

Abstract

A method includes receiving data objects at substantially the same time for storage. The method further includes determining priority levels for the data objects. The method further includes establishing write thresholds for encoding the data objects based on the priority levels. The method further includes dispersed storage error encoding the data objects to produce pluralities of sets of encoded data slices. The method further includes executing write operations to store the pluralities of sets of encoded data slices in storage units in accordance with the write thresholds. During execution of the write operations, the method further includes identifying encoded data slices that were not properly stored and determining rebuild priorities for them. The method further includes rebuilding at least some of the encoded data slices based on the rebuild priorities.

Claims

1. A method comprises:

receiving, by a computing device of a dispersed storage network (DSN), a plurality of data objects for storage in the DSN, the plurality of data objects received during a timeframe in which processing of the plurality of data objects would require concurrent use of one or more DSN resources;

determining, by the computing device, a priority level for each of at least some of the plurality of data objects to produce a plurality of priority levels;

based on the plurality of priority levels, establishing, by the computing device, a write threshold for encoding each of at least some of the plurality of data objects to produce a plurality of write thresholds;

dispersed storage error encoding, by the computing device, the plurality of data objects to produce pluralities of sets of encoded data slices, wherein a data object of the plurality of data objects is encoded into a plurality of sets of encoded data slices of the pluralities of sets of encoded data slices;

executing, by the computing device, a plurality of write operations to store the pluralities of sets of encoded data slices in storage units of the DSN in accordance with the plurality of write thresholds;

during the execution of the write operations, identifying, by a rebuilding detection module of the DSN, encoded data slices of the pluralities of sets of encoded data slices that were not properly stored;

determining, by the rebuilding detection module, rebuild priority of each of the encoded data slices based on a corresponding one of the plurality of priority levels and a level of write success of a corresponding set of encoded data slices of the pluralities of sets of encoded data slices to produce a plurality of rebuild priorities; and

rebuilding, by a rebuilding module of the DSN, at least some of the encoded data slices based on the plurality of rebuild priorities.

2. The method of claim 1, wherein determining the priority level comprises:

determining, for a first data object of the plurality of data objects, one or more of;

a length of data retention, a data type of the first data object, and an analysis protocol; and

based on the determination of the one or more of;

the length of data retention, the data type of the first data object, and the analysis protocol, determining, by the computing device, a first priority level for the first data object.

3. The method of claim 1, wherein the establishing the write threshold comprises:

ranking the plurality of priority levels;

determining estimated write operation costs to execute the plurality of write operations;

determining, for a first data object of the plurality of data objects, a rank order for a first priority level of the first data object; and

determining a first write threshold of the plurality of write thresholds for the first data object based on the rank order of the first priority level and the estimated write operation costs.

4. The method of claim 1, wherein the executing a write operation of the plurality of write operations comprises:

issuing, by the computing device, a set of write requests regarding a set of encoded data slices of the pluralities of sets of encoded data slices to a set of the storage units;

receiving, by the computing device, write responses from at least some storage units of the set of the storage units in response to the set of write requests;

when a corresponding write threshold of the plurality of write thresholds number of write responses have been received, issuing, by the computing device, a set of write commit requests to the at least some storage units;

receiving, by the computing device, write commit responses from the at least some storage units in response to the set of write commit requests; and

when the corresponding write threshold of write commit responses have been received, issuing, by the computing device, a set of write finalize requests to the at least some storage units.

5. The method of claim 4, wherein the identifying encoded data slices that were not properly stored comprises:

when a first storage unit of the set of the storage units does not provide a write response, identifying an encoded data slice to be stored by the first storage unit to include in the encoded data slices that were not properly stored; and

when a second storage unit of the set of the storage units does not provide a write commit response, identifying an encoded data slice to be stored by the second storage unit to include in the encoded data slices that were not properly stored.

6. The method of claim 1, wherein the determining rebuild priority comprises:

for a first encoded data slice of the encoded data slices that were not properly stored;

determining a first priority level of the plurality of priority levels of a first data object of the plurality of data objects, wherein the first data object is dispersed storage error encoded into a first plurality of sets of encoded data slices, wherein the first encoded data slice is from a first set of encoded data slices of the first plurality of sets of encoded data slices;

determining whether the encoded data slices that were not properly stored includes one or more other encoded data slices of the first set of encoded data slices;

establishing a first level of write success for the first set of encoded data slices based on the first encoded data slice and whether the encoded data slices that were not properly stored includes one or more other encoded data slices of the first set of encoded data slices; and

establishing a first rebuild priority for the first encoded data slice based on the first priority level and the first level of write success.

7. A non-transitory computer readable memory comprises:

a first memory section that stores operational instructions that, when executed by a computing device of a dispersed storage network (DSN), causes the computing device to;

receive a plurality of data objects for storage in the DSN, the plurality of data objects received during a timeframe in which processing of the plurality of data objects would require concurrent use of one or more DSN resources;

determine a priority level for each of at least some of the plurality of data objects to produce a plurality of priority levels;

based on the plurality of priority levels, establish a write threshold for encoding each of at least some of the plurality of data objects to produce a plurality of write thresholds;

dispersed storage error encode the plurality of data objects to produce pluralities of sets of encoded data slices, wherein a data object of the plurality of data objects is encoded into a plurality of sets of encoded data slices of the pluralities of sets of encoded data slices; and

execute a plurality of write operations to store the pluralities of sets of encoded data slices in storage units of the DSN in accordance with the plurality of write thresholds;

a second memory section that stores operational instructions that, when executed by a rebuilding detection module of the DSN, causes the rebuilding detection module to;

during the execution of the write operations, identify encoded data slices of the pluralities of sets of encoded data slices that were not properly stored; and

determine rebuild priority of each of the encoded data slices based on a corresponding one of the plurality of priority levels and a level of write success of a corresponding set of encoded data slices of the pluralities of sets of encoded data slices to produce a plurality of rebuild priorities; and

a third memory section that stores operational instructions that, when executed by a rebuilding module of the DSN, causes the rebuilding module to;

rebuild at least some of the encoded data slices based on the plurality of rebuild priorities.

8. The non-transitory computer readable memory of claim 7, wherein the first memory section further stores operational instructions that, when executed by the computing device, causes the computing device to determine the priority level by:

determining, for a first data object of the plurality of data objects, one or more of;

a length of data retention, a data type of the first data object, and an analysis protocol; and

based on the determination of the one or more of;

the length of data retention, the data type of the first data object, and the analysis protocol, determining, by the computing device, a first priority level for the first data object.

9. The non-transitory computer readable memory of claim 7, wherein the first memory section further stores operational instructions that, when executed by the computing device, causes the computing device to establish the write threshold by:

ranking the plurality of priority levels;

determining estimated write operation costs to execute the plurality of write operations;

determining, for a first data object of the plurality of data objects, a rank order for a first priority level of the first data object; and

determining a first write threshold of the plurality of write thresholds for the first data object based on the rank order of the first priority level and the estimated write operation costs.

10. The non-transitory computer readable memory of claim 7, wherein the first memory section further stores operational instructions that, when executed by the computing device, causes the computing device to execute a write operation of the plurality of write operations by:

issuing a set of write requests regarding a set of encoded data slices of the pluralities of sets of encoded data slices to a set of the storage units;

receiving write responses from at least some storage units of the set of the storage units in response to the set of write requests;

when a corresponding write threshold of the plurality of write thresholds number of write responses have been received, issuing a set of write commit requests to the at least some storage units;

receiving write commit responses from the at least some storage units in response to the set of write commit requests; and

when the corresponding write threshold of write commit responses have been received, issuing a set of write finalize requests to the at least some storage units.

11. The non-transitory computer readable memory of claim 10, wherein the second memory section further stores operational instructions that, when executed by the rebuilding detection module, causes the rebuilding detection module to identify the encoded data slices that were not properly stored by:

when a first storage unit of the set of the storage units does not provide a write response, identifying an encoded data slice to be stored by the first storage unit to include in the encoded data slices that were not properly stored; and

when a second storage unit of the set of the storage units does not provide a write commit response, identifying an encoded data slice to be stored by the second storage unit to include in the encoded data slices that were not properly stored.

12. The non-transitory computer readable memory of claim 7, wherein the second memory section further stores operational instructions that, when executed by the rebuilding detection module, causes the rebuilding detection module to determine the rebuild priority by:

for a first encoded data slice of the encoded data slices that were not properly stored;

determining a first priority level of the plurality of priority levels of a first data object of the plurality of data objects, wherein the first data object is dispersed storage error encoded into a first plurality of sets of encoded data slices, wherein the first encoded data slice is from a first set of encoded data slices of the first plurality of sets of encoded data slices;

determining whether the encoded data slices that were not properly stored includes one or more other encoded data slices of the first set of encoded data slices;

establishing a first level of write success for the first set of encoded data slices based on the first encoded data slice and whether the encoded data slices that were not properly stored includes one or more other encoded data slices of the first set of encoded data slices; and

establishing a first rebuild priority for the first encoded data slice based on the first priority level and the first level of write success.