SYSTEMS AND METHODS FOR PROVIDING A QUIESCING PROTOCOL

• US 20110044209A1
• Filed: 11/01/2010
• Published: 02/24/2011
• Est. Priority Date: 02/17/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Fachan, Neal T.
• Granted Patent: US 8,625,464 B2
• Time in Patent Office: Days
• US Class Current: 370/255
• CPC Class Codes: H04L 41/30 Decision processes by autonomous network management units using voting and bidding
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests

Abstract

The systems and methods of the present invention provide a quiescing protocol. In one embodiment, nodes of a system utilize the protocol to complete processing until they reach a consistent state. In one embodiment, a coordinator initiates the quiescing process and the nodes communicate with each other to determine whether their messages have been processed and communicate with the coordinator to determine when all of the messages have been processed.

Claims

1. A distributed system configured to quiesce a set of messages, the distributed system comprising:

a plurality of nodes, each node comprising one or more processors;

a first subset of two or more of the plurality of nodes, each node of the first subset further comprising a participant process;

a second subset of one or more of the plurality of nodes, each node of the second subset further comprising a coordinator process; and

a set of messages sent and received by the plurality of nodes, the set of messages comprising;

a relevant message which changes a state of the distributed system;

a probe message which requests a probe-response message;

the probe-response message which indicates that the sender has processed all received relevant messages from the recipient;

a checkpoint message which indicates that the sender has received a probe-response message from each of the plurality of nodes;

a continue message requesting a continue-response message; and

the continue-response message which indicates whether the sender has received a relevant message from one or more of the plurality of nodes;

wherein each participant process is configured to, when executed;

suspend generation of relevant messages;

maintain received-message information which indicates whether a relevant message has been received from the plurality of nodes;

send probe messages to each of the plurality of nodes;

receive probe-response messages from each of the plurality of nodes;

receive probe messages from each of the plurality of nodes; and

for each probe message received, send the probe-response message to the node which sent the probe message; and

wherein each coordinator process is configured to, when executed;

receive checkpoint messages from each of the plurality of nodes;

send continue messages to each of the plurality of nodes;

receive continue-response messages from each of the plurality of nodes; and

based on the received continue-response messages, determine whether the distributed system has been quiesced.

2. The distributed system of claim 1, wherein the first subset and the second subset are the same.

3. The distributed system of claim 2, wherein both the first subset and the second subset comprise all of the plurality of nodes.

4. The distributed system of claim 2, wherein the participant process and the coordinator process are implemented as a single module.

5. The distributed system of claim 1, wherein the first subset and the second subset are different.

6. The distributed system of claim 1, wherein the first subset comprises all of the plurality of nodes.

7. A distributed system configured to quiesce a set of messages, the distributed system comprising:

a plurality of nodes, each node comprising a processor; and

one or more executable coordinator processes, each coordinator process configured to, when executed;

receive one or more first messages from one or more of the plurality of nodes, each first message indicating that the node, which has sent that first message, has sent a second message to each of the plurality of nodes and has received a third message from each of the plurality of nodes, wherein the second message is a message requesting the third message, and wherein the third message indicates that all messages that change a state of the distributed system previously received by the node, which has received that second message, from the node, which has sent that second message, have been processed;

in response to receiving the one or more first messages, send fourth messages to the plurality of nodes, wherein each fourth message is a message requesting a fifth message;

receive one or more fifth messages from one or more of the plurality of nodes in response to the fourth messages, each fifth message indicating whether the node, which has sent that fifth message, has received a message that changes a state of the distributed system; and

based on one or more received fifth messages, determine whether the distributed system has been quiesced.

8. The distributed system of claim 7, wherein each of the plurality of nodes further comprises one of the one or more executable coordinator processes.

9. The distributed system of claim 7, wherein the plurality of nodes includes at least one coordinator node, the coordinator node further comprising one of the one or more executable coordinator processes.

10. The distributed system of claim 9, wherein sending the fourth messages includes sending a remote message to at least one of the plurality of nodes, and receiving the one or more first messages and fifth messages includes receiving a remote message from at least one of the plurality of nodes.

11. The distributed system of claim 10, wherein sending the fourth messages further includes sending a local message to the coordinator node, and receiving the one or more first messages and fifth messages further includes receiving a local message from the coordinator node.

12. The distributed system of claim 7, wherein the fifth message comprises information about the number of messages that change a state of the distributed system which have been received by the node which has sent the fifth message.

13. The distributed system of claim 7, wherein the fifth message comprises a Boolean value.

14. The distributed system of claim 7, wherein each coordinator process is configured to determine that the distributed system has been quiesced when the one or more received fifth messages indicate that the plurality of nodes have not received a message that changes a state of the distributed system.

15. A distributed system configured to quiesce a set of messages, the distributed system comprising:

a plurality of nodes, each node comprising a processor and at least one executable software module;

wherein the at least one executable software module of each of the plurality of nodes is configured to, when executed;

suspend generation of new messages that change a state of the distributed system;

maintain received-message information which indicates whether a message that changes a state of the distributed system has been received from the plurality of nodes;

send first messages to the plurality of nodes, each first message requesting a response;

receive one or more second messages from one or more of the plurality of nodes, each second message indicating that all messages which change a state of the distributed system sent by the node, which received the second message, to the node, which sent the second message, have been processed;

receive one or more third messages from one or more of the plurality of nodes, each third message requesting a response; and

for each third message received, send a fourth message to the node, which sent the third message, each fourth message indicating that all messages which change a state of the distributed system sent by the node, which sent the third message, to the node, which received the third message, have been processed.

16. The distributed system of claim 15, wherein sending the first message and fourth messages includes sending a remote message to at least one of the plurality of nodes, and receiving the one or more second messages and third messages includes receiving a remote message from at least one of the plurality of nodes.

17. The distributed system of claim 15, wherein sending the first messages and fourth message includes sending a local message to the node which is sending the first messages and fourth message, and receiving the one or more second messages and third messages includes receiving a local message from the node which is receiving the one or more second messages and third messages.

18. The distributed system of claim 15, wherein the received-message information comprises the number of messages that change a state of the distributed system which have been received from the plurality of nodes.

19. The distributed system of claim 15, wherein the received-message information comprises a Boolean value.

20. A distributed system comprising:

a plurality of three or more nodes, each node comprising a processor and configured to act as a coordinator node and a participant node in a quiescing protocol;

wherein, during operation of the quiescing protocol, the plurality of three or more nodes comprises at least one coordinator node and a plurality of two or more participant nodes;

wherein the at least one coordinator node is configured to send and receive messages to and from each of the plurality of participant nodes to collect information about messages which the plurality of participant nodes have received; and

wherein each participant node is configured to;

send and receive messages to and from the plurality of participant nodes to determine whether messages which the participant sent to the plurality of participant nodes and which change a state of the distributed system have been processed; and

send a message to the at least one coordinator node to communicate whether a message that changes a state of the distributed system has been received from one or more of the plurality of participant nodes during operation of the quiescing protocol.

21. The distributed system of claim 20, wherein the coordinator node is one of the plurality of two or more participant nodes.

22. The distributed system of claim 20, wherein the coordinator node is not one of the plurality of two or more participant nodes.