Consistency level driven data storage in a dispersed storage network

• US 10,122,795 B2
• Filed: 05/31/2016
• Issued: 11/06/2018
• Est. Priority Date: 05/31/2016
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Khadiwala, Ravi V., Volvovski, Ilya
• Primary Examiner(s): Williams, Clayton R
• Application Number:
  US15/168,635
• Publication Number:
  US 20170346900A1
• Time in Patent Office: 889 Days
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• 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]

Abstract

A method begins by a processing module of a computing device, in response to sending a set of write requests regarding a set of encoded data slices sent to a set of storage units, receiving write response ballots from some storage units. The method continues with the processing module interpreting the write response ballots to determine whether the write requests have a consensus number of highest rankings. When the computing device has the consensus number of highest rankings, the method continues with the processing module interpreting the write response ballots to determine whether a write threshold number of encoded data slices is listed in lists of correctly stored new revision levels. When the write threshold number of encoded data slices is listed, the method continues with the processing module issuing a set of finalize commands to the set of storage units.

Claims

1. A method comprises:

in response to sending a set of write requests regarding a set of encoded data slices having a first revision level of a data segment of a data object to a set of storage units of a dispersed storage network (DSN), receiving, by a computing device of a plurality of computing devices of the DSN, at least a subset of write response ballots from at least a subset of storage units of the set of storage units, wherein a write response ballot of the at least the subset of write response ballots is received from a storage unit of the at least the subset of storage units regarding an encoded data slice of the set of encoded data slices, wherein the write response ballot includes a list of stored new revision levels of the encoded data slice of pending write requests regarding the new revision levels of the set of encoded data slices and a ranking list of the pending write requests, wherein the pending write requests include the set of write requests and one or more other sets of write requests regarding storage of one or more other sets of encoded data slices having one or more other revision levels of the data segment from one or more other computing devices of the plurality of computing devices of the DSN, wherein the ranking list of the pending write requests lists the pending write requests in order of timestamp of receipt by the storage unit, and wherein the at least the subset of write response ballots includes at least a subset of lists of stored new revision levels of encoded data slices of the data segment and at least a subset of ranking lists of the pending write requests;

interpreting, by the computing device, the at least the subset of write response ballots to determine whether write requests of the set of write requests has a consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests;

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpreting, by the computing device, the at least the subset of write response ballots to determine whether a write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issuing, by the computing device, a set of finalize commands to the set of storage units.

2. The method of claim 1 further comprises:

when the computing device does not have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpreting, by the computing device, the at least the subset of write response ballots to determine whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, wherein the other computing device is associated with one of the one or more other sets of write requests of the pending write requests regarding another set of encoded data slices having another revision level of the data segment;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpreting, by the computing device, the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issuing a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

3. The method of claim 2 further comprises:

when the write threshold number of encoded data slices of the other set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, interpreting, by the computing device, the at least the subset of write response ballots to determine whether write requests of the set of write requests has a second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpreting, by the computing device, the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issuing, by the computing device, the set of finalize commands to the set of storage units.

4. The method of claim 1 further comprises:

when the write threshold number of encoded data slices of the set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issuing a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

5. The method of claim 1, wherein the determining whether the computing device has the consensus number comprises:

determining, by the computing device, whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN also has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests; and

when the other computing device also has the consensus number of the highest rankings, implementing, by the computing device, a conflict avoidance protocol to establish that the computing device or the other computing device has the consensus number.

6. The method of claim 1 further comprises:

verifying, by the computing device, a current revision level of the encoded data slice of the set of encoded data slices, wherein the write response ballot includes a local current revision level of the encoded data slice of the set of encoded data slices of the storage unit.

7. A computing device of a plurality of computing devices of a dispersed storage network (DSN) comprising:

an interface;

memory; and

a processing module operably coupled to the interface and the memory, wherein the processing module is operable to;

in response to sending a set of write requests regarding a set of encoded data slices having a first revision level of a data segment of a data object to a set of storage units of the DSN, receive, via the interface, at least a subset of write response ballots from at least a subset of storage units of the set of storage units, wherein a write response ballot of the at least the subset of write response ballots is received from a storage unit of the at least the subset of storage units regarding an encoded data slice of the set of encoded data slices, wherein the write response ballot includes a list of stored new revision levels of the encoded data slice of pending write requests regarding the new revision levels of the set of encoded data slices and a ranking list of the pending write requests, wherein the pending write requests include the set of write requests and one or more other sets of write requests regarding storage of one or more other sets of encoded data slices having one or more other revision levels of the data segment from one or more other computing devices of the plurality of computing devices of the DSN, wherein the ranking list of the pending write requests lists the pending write requests in order of timestamp of receipt by the storage unit, and wherein the at least the subset of write response ballots includes at least a subset of lists of stored new revision levels of encoded data slices of the data segment and at least a subset of ranking lists of the pending write requests;

interpret the at least the subset of write response ballots to determine whether write requests of the set of write requests has a consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests;

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether a write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, a set of finalize commands to the set of storage units.

8. The computing device of claim 7, wherein the processing module is further operable to:

when the computing device does not have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, wherein the other computing device is associated with one of the one or more other sets of write requests of the pending write requests regarding another set of encoded data slices having another revision level of the data segment;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

9. The computing device of claim 8, wherein the processing module is further operable to:

when the write threshold number of encoded data slices of the other set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, interpret the at least the subset of write response ballots to determine whether write requests of the set of write requests has a second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether the write threshold n umber of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, the set of finalize commands to the set of storage units.

10. The computing device of claim 7, wherein the processing module is further operable to:

when the write threshold number of encoded data slices of the set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

11. The computing device of claim 7, wherein the processing module is further operable to determine whether the computing device has the consensus number by:

determining whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN also has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests; and

when the other computing device also has the consensus number of the highest rankings, implement a conflict avoidance protocol to establish that the computing device or the other computing device has the consensus number.

12. The computing device of claim 7, wherein the processing module is further operable to:

verify a current revision level of the encoded data slice of the set of encoded data slices, wherein the write response ballot includes a local current revision level of the encoded data slice of the set of encoded data slices of the storage unit.

13. A computer readable memory device comprises:

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

in response to sending a set of write requests regarding a set of encoded data slices having a first revision level of a data segment of a data object to a set of storage units of the DSN, receive at least a subset of write response ballots from at least a subset of storage units of the set of storage units, wherein a write response ballot of the at least the subset of write response ballots is received from a storage unit of the at least the subset of storage units regarding an encoded data slice of the set of encoded data slices, wherein the write response ballot includes a list of stored new revision levels of the encoded data slice of pending write requests regarding the new revision levels of the set of encoded data slices and a ranking list of the pending write requests, wherein the pending write requests include the set of write requests and one or more other sets of write requests regarding storage of one or more other sets of encoded data slices having one or more other revision levels of the data segment from one or more other computing devices of the plurality of computing devices of the DSN, wherein the ranking list of the pending write requests lists the pending write requests in order of timestamp of receipt by the storage unit, and wherein the at least the subset of write response ballots includes at least a subset of lists of stored new revision levels of encoded data slices of the data segment and at least a subset of ranking lists of the pending write requests;

a second memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

interpret the at least the subset of write response ballots to determine whether write requests of the set of write requests has a consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests; and

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether a write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

a third memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

when the write threshold number of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue a set of finalize commands to the set of storage units.

14. The computer readable memory device of claim 13 further comprises:

a fourth memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

when the computing device does not have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, wherein the other computing device is associated with one of the one or more other sets of write requests of the pending write requests regarding another set of encoded data slices having another revision level of the data segment;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the other set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

15. The computer readable memory device of claim 14 further comprises:

the fourth memory section further stores operational instructions that, when executed by the computing device, causes the computing device to;

when the write threshold number of encoded data slices of the other set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, interpret the at least the subset of write response ballots to determine whether write requests of the set of write requests has a second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists of the pending write requests, interpret the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment; and

when the write threshold number of encoded data slices of the set of encoded data slices is listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, the set of finalize commands to the set of storage units.

16. The computer readable memory device of claim 13 further comprises:

a fourth memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

when the write threshold number of encoded data slices of the set of encoded data slices is not listed in the at least the subset of lists of stored new revision levels of encoded data slices of the data segment, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

17. The computer readable memory device of claim 13 wherein the second memory section further stores operational instructions that, when executed by the computing device, causes the computing device to determine whether the computing device has the consensus number by:

determining whether another computing device of the one or more other computing devices of the plurality of computing devices of the DSN also has the consensus number of the highest rankings in the at least the subset of ranking lists of the pending write requests; and

when the other computing device also has the consensus number of the highest rankings, implement a conflict avoidance protocol to establish that the computing device or the other computing device has the consensus number.

18. The computer readable memory device of claim 13 further comprises:

a fourth memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

verify a current revision level of the encoded data slice of the set of encoded data slices, wherein the write response ballot includes a local current revision level of the encoded data slice of the set of encoded data slices of the storage unit.