Distributed processing system with replicated management information base

• US 6,411,967 B1
• Filed: 06/18/1999
• Issued: 06/25/2002
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Reliable Network Solutions
• Original Assignee: Reliable Network Solutions
• Inventors: Van Renesse, Robbert
• Primary Examiner(s): Coulter, Kenneth R.
• Application Number:
  US09/335,955
• Time in Patent Office: 1,103 Days
• Field of Search: 707/201, 709/223, 709/200
• US Class Current: 707/625
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A replicated management information base (RMIB), or replicated spreadsheet, is maintained at nodes to share information among the nodes. The RMIB includes columns, or categories, of the information to be shared and rows for the respective “member” nodes. Each member node is responsible for the contents of its own row. When the node updates its row, the node sends out an update message to the other members. As the update message propagates through the membership, each member updates the row in its copy, or view, of the RMIB. The nodes may include version numbers in the update messages, so that the receiving node ignores older messages or applies the messages in order. The member nodes may gossip among themselves, to ensure that each node receives the most recent updates. Also, the nodes may monitor their respective network interfaces and send as updates any changes to the status of the interfaces. The nodes may also include the interface status information in the gossip messages, such that the receiving nodes send update information to active interfaces. The nodes may select nodes on each sub-network and send the update messages to the selected nodes. The selected nodes then broadcast the update messages to the members on their respective sub-networks.

Claims

1. A system for communicating information among nodes of a network, the system including:

A. a replicated management information data base with columns containing information to be shared among nodes and a row for each node that is to share the information, the nodes sharing the information being members and each member node maintaining a view of the data base;

B. row updating means changing a row of the data base, the updating means allowing each member node to make changes to the corresponding row and associating a row version number with the changes made to the row by the member node;

C. update messaging means for providing, when changes are made by the member node to the corresponding row in the data base, a message that contains the changes and identifies the row to which the changes were made; and

D. updating means for updating the views, the updating means including in a given view the changes made to the row and the associated row version number by the corresponding member node.

2. The system of claim 1 wherein the updating means includes in a given view the changes associated with a version number that is larger than the version number associated with the corresponding row in the view.

3. The system of claim 2 further including gossip messaging means for

i. providing to the members gossip messages that include information which identifies the last change to each row of the view at a gossiping node,

ii. providing to the gossiping node changes that are included in the view of the data base at the given member node but are not included in the view at the gossiping node.

4. The system of claim 1 further including a means for monitoring the interfaces of a given node, the means providing to the view of the data base at the given node the status of each of the interfaces.

5. The system of claim 4 wherein the update messaging means sends information to the respective member nodes over interfaces that are listed in the associated view of the data base as having active statuses.

6. The system of claim 5 further including gossip messaging means for

i. providing to the members gossip messages that include information which identifies the last change made to each row of the view of the data base at a gossiping node, and

ii. providing to the gossiping node changes that are included in the view of the data base at the given member node but are not included in the view at the gossiping node.

7. The system of claim 6 wherein the gossip messaging means provides gossip messages to any interface listed in the applicable view of the data base.

8. The system of claim 1 wherein the row updating means associates with each change two row version numbers, namely, a first row version number that indicates the new row version number and a second row version number that indicates the row version to which the changes were made.

9. The system of claim 8 wherein

i. the update messaging means sends update messages that include the information that was changed in a given row and the two row version numbers, and

ii. the updating means alters the corresponding row in a given view of the data base if the second row version number is the same as the row version number associated with the row in the view.

10. The system of claim 9 wherein the updating means further holds the update messages in a list that is ordered by the second version number in the messages and updates the row by applying the listed update messages to the version of the row contained in the given view of the data base.

11. The system of claim 10 wherein the updating means combines overlapping update messages into a composite message and applies the composite message to the version of the row contained in the given view of the data base.

12. A system for communicating information among nodes of a network, the system including:

A. a replicated management information data base with columns containing information to be shared among nodes and a row for each node that is to share the information, the nodes sharing the information being members and each member node maintaining a view of the data base;

B. row updating means for changing a row of the data base, the updating means allowing each member node to make changes to the corresponding row;

C. update messaging means for providing, when changes are made by the member node to the corresponding row in the data base, a message that contains the changes and identifies the row to which the changes were made;

D. updating means for updating the views, the updating means including in a given view the changes made to the row by the corresponding member node; and

E. means for sending ping messages between associated members, said means sending to the updating means a list of associated members that have not sent ping messages within a predetermined time period.

13. The system of claim 12 wherein the row updating means removes from a given view the rows associated with the members that have not sent the ping messages.

14. A system for communicating information among nodes of a network, the system including:

A. a replicated management information data base with columns containing information to be shared among nodes and a row for each node that is to share the information, the nodes sharing the information being members and each member node maintaining a view of the data base;

B. row updating means for changing a row of the data base, the updating means allowing each member node to make changes to the corresponding row;

C. update messaging means for providing, when changes are made by the member node to the corresponding row in the data base, a message that contains the changes and identifies the row to which the changes were made, the updating means

selecting as recipients of the messages a set of members that includes a members that connect respectively to each associated sub-network,

sending the messages to each of the members in the set, and

broadcasting the messages from the members in the set to the members in the respective sub-networks, and

D. updating means for updating the views, the updating means including in a given view the changes made to the row by the corresponding member node.

15. A method for communicating information among nodes of a network, the method including:

A. maintaining at each node a view of replicated management information data base with columns containing information to be shared among nodes and a row for each node that is a member and shares the information;

B. updating a row of the data base by the member associated with the row;

C. updating a version number when a member updates the associated row of the data base;

D. sending update information about the row from the associated member to one or more of the remaining members and including the version number in the update information, and

E. updating the respective rows in the view of each member that receives the update information if the corresponding version number included in the update information is larger than the version number associated with the row in the view.

16. The method of claim 15 further includes the steps of

i. providing to the members gossip messages that include information which identifies the last change to each row of the view at a gossiping node, and

ii. providing to the gossiping node changes that are included in the view at a receiving member but are not included in the view at the gossiping member.

17. The method of claim 15 wherein the step of updating a version number with each change to a given row further includes associating with the change a second version number that indicates the row version to which the changes were made.

18. The method of claim 17 wherein

a. the step of sending update information includes the step of including the two row version numbers in the update information, and

b. the step of updating a given view alters the corresponding row in the given view if the second row version number in the update message is the same as the row version number associated with the row in the view.

19. The method of claim 18 wherein the step of updating further includes the steps of

i. holding the update information in a list that is ordered by the second associated version numbers, and

ii. updating the row by applying the listed update messages to the version of the row contained in the given view of the data base.

20. The method of claim 19 wherein the step of updating further combines overlapping update messages into a composite message and applies the composite message to the version of the row contained in the given view of the data base.

21. The method of claim 17 further including the steps of

i. providing to the members gossip messages that include information which identifies the last change to each row of the view at a gossiping node, and

ii. providing to the gossiping node changes that are included in the view at a receiving member but are not included in the view at the gossiping member.

22. A method for communicating information among nodes of a network, the method including:

A. maintaining at each node a view of replicated management information data base with columns containing information to be shared among nodes and a row for each node that is a member and shares the information;

B. monitoring network interfaces of a given node;

C. including in the data base the status of each of the network interfaces;

D. updating a row of the data base by the member associated with the row;

E. sending update information about the row from the associated member to one or more of the remaining members;

F. updating the rows in the view of each member that receives the update information.

23. The method of claim 22 further including in the step of sending the update information sending the update information to selected ones of the interfaces that are listed as having active statuses.

24. A method for communicating information among nodes of a network, the method including:

A. maintaining at each node a view of replicated management information data base with columns containing information to be shared among nodes and a row for each node that is a member and shares the information;

B. updating a row of the data base by the member associated with the row;

C. sending ping messages between associated members;

D. listing as failed those associated members that have not sent ping messages for a predetermined time;

E. sending update information about the row from the associated member to one or more of the remaining members and including in the update information a list of the associated members that have failed since the last update information was sent;

F. updating the rows in the view of each member that receives the update information.

25. The method of claim 24 further including the steps of

d. incrementing an associated counter when a gossip message is received from a given member,

e. listing a given node as failed if the counter is not incremented within a predetermined interval,

f. removing the node from the data base if the associated counter is not incremented within an additional predetermined interval.

26. The method of claim 25 wherein the step of incrementing the counter includes incrementing the counters associated with the respective members listed in the gossip message if the counts included in the gossip message are larger than the associated counts at the receiving member.

27. The method of claim 26 further includes the step of adding to a view a row associated with a member that has a count in the gossip message but no row in the view.

28. A method for communicating information among nodes of a network, the method including:

A. maintaining at each node a view of replicated management information data base with columns containing information to be shared among nodes and a row for each node that is a member and shares the information;

B. updating a row of the data base by the member associated with the row;

C. selecting as recipients of update information a set of members that includes a node that connects respectively to each associated sub-network;

D. sending the update information to each of the members in the set;

E. broadcasting the update information from the members in the set to the members in the respective sub-networks; and

F. updating the rows in the view of each member that receives the update information.