System and method for topology manager employing finite state automata for dynamic cluster formation

• US 20030204273A1
• Filed: 04/29/2002
• Published: 10/30/2003
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Kannan, Mahesh, Dinker, Darpan, Gopinath, Pramod
• Granted Patent: US 7,024,483 B2
• Time in Patent Office: Days
• US Class Current: 700/48
• CPC Class Codes: G06F 2209/505 Clust
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A distributed system provides for separate management of dynamic cluster membership and distributed data. Nodes of the distributed system may include a state manager and a topology manager. A state manager handles data access from the cluster. A topology manager handles changes to the dynamic cluster topology. The topology manager enables operation of the state manager by handling topology changes, such as new nodes to join the cluster and node members to exit the cluster. A topology manager may follow a static topology description when handling cluster topology changes. Data replication and recovery functions may be implemented, for example to provide high availability.

Claims

1. A method, comprising:

a node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node, wherein the plurality of cluster nodes are connected together to form a distributed data cluster having a topology order;

upon connecting to its next node, the node transitioning to a joining state and sending a connect request message to its next node;

the node waiting in the joining state to receive a connect complete message; and

upon receiving the connect complete message from one of a plurality of cluster nodes connecting to the node as its previous node, the node transitioning to a joined state as a member of the distributed data cluster;

wherein in the joined state the node is a member of the distributed data cluster in the topology order between its previous node and its next node.

2. The method as recited in claim 1, further comprising the node initially starting up in the connecting state before the node is a member of the distributed data cluster.

3. The method as recited in claim 1, wherein the node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node comprises the node attempting to connect to other nodes according to a predefined order, wherein the node attempts to connect to successive nodes from its position in the predefined order until a successful connection is established.

4. The method as recited in claim 1, wherein the node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node comprises the node opening a TCP/IP socket to its next node.

5. The method as recited in claim 1, wherein when the node is in the joining state, the node ignores any connection attempts by other nodes not already a member of the distributed data cluster.

6. The method as recited in claim 1, further comprising, after receiving the connect complete message from its previous node, the node sending the connect complete message to its next node to indicate that the node has successful joined the distributed data cluster.

7. The method as recited in claim 1, wherein the connect complete message received by the node includes a topology table indicating a current cluster membership, the method further comprising the node storing the topology table.

8. The method as recited in claim 1, wherein the transitions between the connecting, joining and joined states are managed by a topology manager of the node, wherein the node further comprises a distributed data manager for replicating data to one or more other nodes of the distributed data cluster.

9. The method as recited in claim 8, further comprising, upon transitioning to the joined state, the node'"'"'s topology manager sending an event notification to the node'"'"'s distributed data manager indicating that the node has joined the distributed data cluster.

10. The method as recited in claim 9, further comprising, after receiving the event notification indicating that the node has joined the distributed data cluster, the node'"'"'s distributed data manager replicating data stored by the node to at least one of the node'"'"'s next node and previous node.

11. A method, comprising:

a node in a joined state receiving a connect request message from a new node attempting to join a distributed data cluster, wherein the node in the joined state is a member of the distributed data cluster having a plurality of cluster nodes, wherein the node in the joined state is connected to one of the cluster nodes as its next node according to a cluster topology order;

after receiving the connect request message, the node transitioning to a transient state and sending a node joined message to its next node indicating that the new node is joining the distributed data cluster;

the node waiting in the transient state to receive a connect complete message from the new node; and

upon receiving the connect complete message from the new node, the node transitioning back to the joined state wherein the node is connected to the new node as its previous node in the cluster topology order.

12. The method as recited in claim 11, wherein the node in a joined state receiving a connect request message from a new node comprises the node verifying that the new node is connecting to it in a correct order as its previous node according to a predefined order, wherein if the new node is not connecting in the correct order, the node sending a connect reject message to the new node.

13. The method as recited in claim 12, wherein the connect reject message includes an indication of a correct one of the cluster nodes for the new node to connect to.

14. The method as recited in claim 11, further comprising, while in the transient state, the node refusing any connect request messages from other nodes by replying with a connect reject message.

15. The method as recited in claim 11, further comprising the node ignoring any connect request messages from other nodes while the node is in the transient state.

16. The method as recited in claim 11, wherein the node joined message sent by the node to its next node includes an indication that the new node is now the node'"'"'s previous node.

17. The method as recited in claim 11, further comprising, upon receiving the connect complete message from the new node, the node dropping its connection to one of the cluster nodes that was its former previous node.

18. A method, comprising:

a node in a joined state receiving a node joined message indicating a new node is attempting to join a distributed data cluster, wherein the node in the joined state is a member of the distributed data cluster having a plurality of cluster nodes, wherein the node in the joined state receives the node joined message from one of the cluster nodes connected to it as its previous node according to a cluster topology order, and wherein the node is connected to another cluster node as its current next node according to the topology order;

if the node joined message indicates that the new node is to be the node'"'"'s new next node, the node connecting to the new node and sending the new node a connect complete message; and

if the node joined message does not indicate that the new node is to be the node'"'"'s new next node, the node sending the node joined message to its current next node.

19. The method as recited in claim 18, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node dropping its connection to its current next node.

20. The method as recited in claim 18, wherein the node connecting to the new node comprises the node opening a TCP/IP socket to the new node.

21. The method as recited in claim 18, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node updating a topology table to indicate that the new node is now its next node.

22. The method as recited in claim 18, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node appending its node identifier to a topology table included with the received node joined message so that the topology table indicates that the new node is now the node'"'"'s next node in the cluster topology order.

23. The method as recited in claim 22, wherein the connect complete message sent by the node to the new node includes the topology table appended with the node'"'"'s node identifier and indicating that the new node is now the node'"'"'s next node in the cluster topology order.

24. The method as recited in claim 18, further comprising, if the received node joined message does not indicate that the new node is to be the node'"'"'s new next node, the node appending its node identifier to a topology table included with the node joined message so that the topology table indicates the node'"'"'s position in the cluster topology order.

25. The method as recited in claim 24, wherein the node joined message sent by the node to its current next node includes the topology table appended with the node'"'"'s node identifier.

48. The computer system as recited in claim 22, wherein the connect complete 25 message sent by the node to the new node includes the topology table appended with the node'"'"'s node identifier and indicating that the new node is now the node'"'"'s next node in the cluster topology order.

49. The computer system as recited in claim 48, further comprising, if the received node joined message does not indicate that the new node is to be the node'"'"'s new next node, the node appending its node identifier to a topology table included with the node joined message so that the topology table indicates the node'"'"'s position in the cluster topology order.

50. The computer system as recited in claim 49, wherein the node joined message sent by the node to its current next node includes the topology table appended with the node'"'"'s node identifier.

26. A computer system comprising a processor and memory including instructions executable by the processor for:

a node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node, wherein the plurality of cluster nodes are connected together to form a distributed data cluster having a topology order;

upon connecting to its next node, the node transitioning to a joining state and sending a connect request message to its next node;

the node waiting in the joining state to receive a connect complete message; and

upon receiving the connect complete message from one of a plurality of cluster nodes connecting to the node as its previous node, the node transitioning to a joined state as a member of the distributed data cluster;

wherein in the joined state the node is a member of the distributed data cluster in the topology order between its previous node and its next node.

27. The computer system as recited in claim 26, further comprising the node initially starting up in the connecting state before the node is a member of the distributed data cluster.

28. The computer system as recited in claim 26, wherein the node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node comprises the node attempting to connect to other nodes according to a predefined order, wherein the node attempts to connect to successive nodes from its position in the predefined order until a successful connection is established.

29. The computer system as recited in claim 26, wherein the node in a connecting state attempting to connect to one of a plurality of cluster nodes as its next node comprises the node opening a TCP/IP socket to its next node.

30. The computer system as recited in claim 26, wherein when the node is in the joining state, the node ignores any connection attempts by other nodes not already a member of the distributed data cluster.

31. The computer system as recited in claim 26, further comprising, after receiving the connect complete message from its previous node, the node sending the connect complete message to its next node to indicate that the node has successfully joined the distributed data cluster.

32. The computer system as recited in claim 26, wherein the connect complete message received by the node includes a topology table indicating a current cluster membership, the method further comprising the node storing the topology table.

33. The computer system as recited in claim 26, wherein the transitions between the connecting, joining and joined states are managed by a topology manager of the node, wherein the node further comprises a distributed data manager for replicating data to one or more other nodes of the distributed data cluster.

34. The computer system as recited in claim 33, further comprising, upon transitioning to the joined state, the node'"'"'s topology manager sending an event notification to the node'"'"'s distributed data manager indicating that the node has joined the distributed data cluster.

35. The computer system as recited in claim 34, further comprising, after receiving the event notification indicating that the node has joined the distributed data cluster, the node'"'"'s distributed data manager replicating data stored by the node to at least one of the node'"'"'s next node and previous node.

36. A computer system comprising a processor and memory including instructions executable by the processor for:

a node in a joined state receiving a connect request message from a new node attempting to join a distributed data cluster, wherein the node in the joined state is a member of the distributed data cluster having a plurality of cluster nodes, wherein the node in the joined state is connected to one of the cluster nodes as its next node according to a cluster topology order;

after receiving the connect request message, the node transitioning to a transient state and sending a node joined message to its next node indicating that the new node is joining the distributed data cluster;

the node waiting in the transient state to receive a connect complete message from the new node; and

upon receiving the connect complete message from the new node, the node transitioning back to the joined state wherein the node is connected to the new node as its previous node in the cluster topology order.

37. The computer system as recited in claim 36, wherein the node in a joined state receiving a connect request message from a new node comprises the node verifying that the new node is connecting to it in a correct order as its previous node according to a predefined order, wherein if the new node is not connecting in the correct order, the node sending a connect reject message to the new node.

38. The computer system as recited in claim 37, wherein the connect reject message includes an indication of a correct one of the cluster nodes for the new node to connect to.

39. The computer system as recited in claim 36, further comprising, while in the transient state, the node refusing any connect request messages from other nodes by replying with a connect reject message.

40. The computer system as recited in claim 36, further comprising the node ignoring any connect request messages from other nodes while the node is in the transient state.

41. The computer system as recited in claim 36, wherein the node joined message sent by the node to its next node includes an indication that the new node is now the node'"'"'s previous node.

42. The computer system as recited in claim 36, further comprising, upon receiving the connect complete message from the new node, the node dropping its connection to one of the cluster nodes that was its former previous node.

43. A computer system comprising a processor and memory including instructions executable by the processor for:

a node in a joined state receiving a node joined message indicating a new node is attempting to join a distributed data cluster, wherein the node in the joined state is a member of the distributed data cluster having a plurality of cluster nodes, wherein the node in the joined state receives the node joined message from one of the cluster nodes connected to it as its previous node according to a cluster topology order, and wherein the node is connected to another cluster node as its current next node according to the topology order;

if the node joined message indicates that the new node is to be the node'"'"'s new next node, the node connecting to the new node and sending the new node a connect complete message; and

if the node joined message does not indicate that the new node is to be the node'"'"'s new next node, the node sending the node joined message to its current next node.

44. The computer system as recited in claim 43, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node dropping its connection to its current next node.

45. The computer system as recited in claim 43, wherein the node connecting to the new node comprises the node opening a TCP/IP socket to the new node.

46. The computer system as recited in claim 43, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node updating a topology table to indicate that the new node is now its next node.

47. The computer system as recited in claim 43, further comprising, if the received node joined message indicates that the new node is to be the node'"'"'s new next node, the node appending its node identifier to a topology table included with the received node joined message so that the topology table indicates that the new node is now the node'"'"'s next node in the cluster topology order.

51. A method for managing cluster membership in a distributed data system according to a finite state automata, comprising:

a first node in a connecting state attempting to connect to a second node of a plurality of cluster nodes as its next node, wherein the plurality of cluster nodes are connected together to form a distributed data cluster having a topology order;

upon connecting to the second node, the first node transitioning to a joining state and sending a connect request message to the second node;

the first node waiting in the joining state to receive a connect complete message;

the second node in a joined state receiving the connect request message from the first node, wherein the second node is connected to a third node of the cluster nodes as the third node'"'"'s next node according to a cluster topology order;

after receiving the connect request message, the second node transitioning to a transient state and sending a node joined message to its next node indicating that the first node is joining the distributed data cluster;

the second node waiting in the transient state to receive a connect complete message from the first node;

the third node in a joined state receiving the node joined message indicating the first node is attempting to join the distributed data cluster as the third node'"'"'s new next node, wherein the third node receives the node joined message from one of the cluster nodes connected to it as its previous node according to a cluster topology order;

in response to the node joined message indicating that the first node is to be the third node'"'"'s new next node, the third node connecting to the first node and sending the first node a connect complete message;

upon receiving the connect complete message from the third node, the first node connecting to the third node as its previous node, sending a connect complete message to the second node, and transitioning to a joined state as a member of the distributed data cluster; and

upon receiving the connect complete message from the first node, the second node transitioning to the joined state wherein the second node is connected to the first node as the first node'"'"'s previous node in the cluster topology order;

wherein in the joined state the first node is a member of the distributed data cluster in the topology order between its previous node and its next node.

52. The method as recited in claim 51, further comprising the first node initially starting up in the connecting state before the node is a member of the distributed data cluster.

53. The method as recited in claim 51, wherein the second node receiving a connect request message from a first node comprises the second node verifying that the first node is connecting to it in a correct order as its previous node according to a predefined order, wherein if the first node is not connecting in the correct order, the second node sending a connect reject message to the first node.