Systems and methods for providing a quiescing protocol
View Patent ↗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.
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 physical 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 by at least one node of the first subset:
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 by at least one node of the second subset:
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 at least one physical processor; and
one or more executable coordinator processes, each coordinator process configured to, when executed by one or more of the plurality of nodes:
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 by determining whether any of the plurality of nodes have received any new messages that change a state of the distributed system; and
when it is determined that any of the plurality of nodes received a new message that changes a state of the distributed system, sending and receiving additional messages until it is determined from one or more received messages that none of the plurality of nodes have received any new messages that change a state of the distributed system.
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. A distributed system configured to quiesce a set of messages, the distributed system comprising:
a plurality of nodes, each node comprising at least one physical 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 by the at least one physical processor:
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;
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;
determine whether the distributed system has been quiesced at least in part by determining whether any of the plurality of nodes have received any new messages that change a state of the distributed system; and
when it is determined that any of the plurality of nodes received a new message that changes a state of the distributed system, sending and receiving additional messages until it is determined that none of the plurality of nodes have received any new messages that change a state of the distributed system.
15. The distributed system of claim 14 , 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.
16. The distributed system of claim 14 , 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.
17. The distributed system of claim 14 , 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.
18. The distributed system of claim 14 , wherein the received-message information comprises a Boolean value.