Implicit leader election in a distributed storage network

• US 10,372,381 B2
• Filed: 06/05/2017
• Issued: 08/06/2019
• Est. Priority Date: 06/05/2017
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Khadiwala, Ravi V., Resch, Jason K.
• Primary Examiner(s): Tsui, Daniel D
• Application Number:
  US15/613,531
• Publication Number:
  US 20180349039A1
• Time in Patent Office: 792 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method begins by a processing module receiving a request to store a data object in distributed storage (DS) units. The processing module generates and transmits a proposal message that includes a source name, a value for the source name, and a proposal attempt identifier. The processing module then receives a threshold number of proposal message responses from the plurality of DS units, and when the proposal message responses indicate that no other proposal messages have been received by the DS units, uses the value for the source name included within the proposal message as a persistent value for the source name, and the method continues with the processing module notifying the requesting computing device. When the proposal message responses indicate that at least one other proposal message has been received by the DS unit of the plurality of DS units, the method continues with the processing module employing a third value for the source name as the persistent value for the source name.

Claims

1. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions;

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

receive, from a requesting computing device and via the DSN, a request to store a data object within a plurality of distributed storage (DS) units;

generate a proposal message that includes a source name associated with the data object, a first value for the source name, and a proposal attempt identifier;

transmit the proposal message to the plurality of DS units;

receive, in response to the proposal message, a threshold number of proposal message responses from the plurality of DS units, wherein a proposal message response of the threshold number of proposal message responses is received from a DS unit of the plurality of DS units and corresponds to a second value for the source name that is most recently accepted by the DS unit and further indicates whether the DS unit of the plurality of DS units has received any other proposal message;

when the proposal message response of the threshold number of proposal message responses that is received from the DS unit of the plurality of DS units indicates that no other proposal messages has been received by the DS unit of the plurality of DS units, employ the first value for the source name included within the proposal message as a persistent value for the source name and notify the requesting computing device of the persistent value for the source name; and

when the proposal message response of the threshold number of proposal message responses that is received from the DS unit of the plurality of DS units indicates that at least one other proposal message has been received by the DS unit of the plurality of DS units, employ a third value for the source name based on the threshold number of proposal message responses from the plurality of DS units as the persistent value for the source name and notify the requesting computing device of the persistent value for the source name.

2. The computing device of claim 1, wherein the persistent value is determined based on execution of a deterministic function by the processing module.

3. The computing device of claim 1, wherein the third value for the source name is equal to the second value for the source name.

4. The computing device of claim 2, wherein the deterministic function is further executed by other processing units receiving proposal message responses for the source name and further wherein executing the deterministic function results in the third value for the source name.

5. The computing device of claim 1, wherein the persistent value is determined based on a balloting process executed by the processing module.

6. The computing device of claim 5, wherein the balloting process includes choosing a ballot value based on a timestamp associated with the proposal message.

7. The computing device of claim 5, wherein the balloting process results in two potential persistent values, and the persistent value is chosen from the two potential persistent values after a second processing module and a third processing modules associated with the two potential persistent values, respectively, re-transmit proposal messages transmitted after the processing module receives the threshold number of proposal messages.

8. The computing device of claim 1, wherein a select other processing module is associated with the third value and the third value is determined after the select other processing module transmits a proposal message associated with the third value after the processing module receives the threshold number of proposal messages.

9. The computing device of claim 8, wherein the transmitting a proposal message associated with the third value after the processing module receives the threshold number of proposal messages by the select other processing module is based on the select other processing module determining that the proposal message associated with the third value includes a preferred candidate value for the persistent value.

10. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

receiving, from a requesting computing device and via the DSN, a request to store a data object within a plurality of distributed storage (DS) units;

generating a proposal message that includes a source name associated with the data object, a first value for the source name, and a proposal attempt identifier;

transmitting the proposal message to the plurality of DS units;

receiving, in response to the proposal message, a threshold number of proposal message responses from the plurality of DS units, wherein a proposal message response of the threshold number of proposal message responses is received from a DS unit of the plurality of DS units and corresponds to a second value for the source name that is most recently accepted by the DS unit and further indicates whether the DS unit of the plurality of DS units has received any other proposal message;

when the proposal message response of the threshold number of proposal message responses that is received from the DS unit of the plurality of DS units indicates that no other proposal messages has been received by the DS unit of the plurality of DS units, employing the first value for the source name included within the proposal message as a persistent value for the source name and notifying the requesting computing device of the persistent value for the source name; and

when the proposal message response of the threshold number of proposal message responses that is received from the DS unit of the plurality of DS units indicates that at least one other proposal message has been received by the DS unit of the plurality of DS units, employing a third value for the source name based on the threshold number of proposal message responses from the plurality of DS units as the persistent value for the source name and notifying the requesting computing device of the persistent value for the source name.

11. The method of claim 10, wherein the persistent value is determined based on execution of a deterministic function by the processing module.

12. The method of claim 10, wherein the third value for the source name is equal to the second value for the source name.

13. The method of claim 11, wherein the deterministic function is further executed by other processing units receiving proposal message responses for the source name and further wherein executing the deterministic function results in the third value for the source name.

14. The method of claim 10, wherein the persistent value is determined based on a balloting process executed by the processing module.

15. The method of claim 14, wherein the balloting process includes choosing a ballot value based on a timestamp associated with the proposal message.

16. The method of claim 14, wherein the balloting process results in two potential persistent values, and the persistent value is chosen from the two potential persistent values after a second processing module and a third processing modules associated with the two potential persistent values, respectively, re-transmit proposal messages transmitted after the processing module receives the threshold number of proposal messages.

17. The method of claim 10, wherein a select other processing module is associated with the third value and the third value is determined after the select other processing module transmits a proposal message associated with the third value after the processing module receives the threshold number of proposal messages.

18. The method of claim 17, wherein the transmitting a proposal message associated with the third value after the processing module receives the threshold number of proposal messages by the select other processing module is based on the select other processing module determining that the proposal message associated with the third value includes a preferred candidate value for the persistent value.

19. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

receiving, by a computing device, an access request intended for a threshold number of storage units of a dispersed storage network (DSN), wherein the access request is for a value associated with a source name, and further wherein the computing device has received one or more proposal message responses from at least some of the threshold number of storage units;

determining whether the value associated with the source name is a persistent value for the source name, wherein the determining is based on the computing device having received a threshold number of proposal message responses from the threshold number of storage units, and further wherein the determining is also based on whether threshold proposal message responses indicate that a consensus value has been determined for the value associated with the source name; and

when the value associated with the source name is the persistent value for the source name, transmitting the value associated with the source name to the requesting computing device.

20. The method of claim 19, further comprises:

when the value associated with the source name is not a persistent value for the source name, determining that a persistent value cannot be determined and selecting a previously stored value for the value associated with the source name and transmitting the previously stored value to the requesting computing device.