CONSISTENCY LEVEL DRIVEN DATA STORAGE IN A DISPERSED STORAGE NETWORK

• US 20170346900A1
• Filed: 05/31/2016
• Published: 11/30/2017
• 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
• Granted Patent: US 10,122,795 B2
• Time in Patent Office: 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 to a set of storage units of a dispersed storage network (DSN), receiving, by a computing device, 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 correctly 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 and wherein the at least the subset of write response ballots includes at least a subset of lists of correctly stored new revision levels and at least a subset of ranking lists;

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;

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; and

when the write threshold number of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, 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, interpreting, by the computing device, the at least the subset of write response ballots to determine whether another computing device has the consensus number of the highest rankings in the at least the subset of ranking lists, wherein the other computing device is associated with one of the pending write requests;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists, 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 another set of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, wherein the other computing device issued another set of write requests for the another set of encoded data slices, wherein the another set of encoded data slices has a first revision level regarding a data segment of a data object and the set of encoded data slices has a second revision level regarding the data segment; and

when the write threshold number of encoded data slices of another set of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, 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 another set of encoded data slices is not listed in the at least the subset of lists of correctly stored new revision levels, 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;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; and

when the write threshold number of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, 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 correctly stored new revision levels, 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 also has the consensus number of the highest rankings in the at least the subset of ranking lists; 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:

determining the highest ranking within the ranking list based on a timestamp of when write requests of the pending write requests were received by the storage unit.

7. The method of claim 1 further comprises:

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

8. A computing device 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 to a set of storage units of a dispersed storage network (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 correctly 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 and wherein the at least the subset of write response ballots includes at least a subset of lists of correctly stored new revision levels and at least a subset of ranking lists;

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;

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; and

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

9. The computing device of claim 8, 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, interpret the at least the subset of write response ballots to determine whether another computing device has the consensus number of the highest rankings in the at least the subset of ranking lists, wherein the other computing device is associated with one of the pending write requests;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists, interpret the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of another set of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, wherein the other computing device issued another set of write requests for the another set of encoded data slices, wherein the another set of encoded data slices has a first revision level regarding a data segment of a data object and the set of encoded data slices has a second revision level regarding the data segment; and

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

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

when the write threshold number of encoded data slices of another set of encoded data slices is not listed in the at least the subset of lists of correctly stored new revision levels, 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;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; and

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

11. 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 set of encoded data slices is not listed in the at least the subset of lists of correctly stored new revision levels, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

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

determining whether another computing device also has the consensus number of the highest rankings in the at least the subset of ranking lists; 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.

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

determine the highest ranking within the ranking list based on a timestamp of when write requests of the pending write requests were received by the storage unit.

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

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

15. A computer readable memory device comprises:

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

in response to sending a set of write requests regarding a set of encoded data slices sent to a set of storage units of a dispersed storage network (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 correctly 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 and wherein the at least the subset of write response ballots includes at least a subset of lists of correctly stored new revision levels and at least a subset of ranking lists;

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; and

when the computing device has the consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; 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 correctly stored new revision levels, issue a set of finalize commands to the set of storage units.

16. The computer readable memory device of claim 15 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, interpret the at least the subset of write response ballots to determine whether another computing device has the consensus number of the highest rankings in the at least the subset of ranking lists, wherein the other computing device is associated with one of the pending write requests;

when the other computing device does have the consensus number of the highest rankings in the at least the subset of ranking lists, interpret the at least the subset of write response ballots to determine whether the write threshold number of encoded data slices of another set of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, wherein the other computing device issued another set of write requests for the another set of encoded data slices, wherein the another set of encoded data slices has a first revision level regarding a data segment of a data object and the set of encoded data slices has a second revision level regarding the data segment; and

when the write threshold number of encoded data slices of another set of encoded data slices is listed in the at least the subset of lists of correctly stored new revision levels, 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 16 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 another set of encoded data slices is not listed in the at least the subset of lists of correctly stored new revision levels, 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;

when the computing device has the second highest consensus number of highest rankings in the at least the subset of ranking lists, 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 correctly stored new revision levels; and

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

18. The computer readable memory device of claim 15 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 correctly stored new revision levels, issue, via the interface, a set of withdraw commands to the set of storage units regarding the set of encoded data slices.

19. The computer readable memory device of claim 15 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 also has the consensus number of the highest rankings in the at least the subset of ranking lists; 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.

20. The computer readable memory device of claim 15 wherein the second memory section further stores operational instructions that, when executed by the computing device, causes the computing device to determine the highest ranking within the ranking list based on a timestamp of when write requests of the pending write requests were received by the storage unit.

21. The computer readable memory device of claim 15 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, wherein the write response ballot includes a local current revision level of the encoded data slice of the storage unit.