System and method for data structure synchronization
A system and method for data structure synchronization includes a control unit and a memory coupled to the control unit. The memory stores a first base data structure and a first digest data structure. The control unit maintains the first digest data structure based on the first base data structure and determines whether the first base data structure is in synchronization with a second base data structure. When the first and second base data structures are not in synchronization, the control unit receives a second digest data structure based on the second base data structure, attempts to synchronize the first base data structure to the second base data structure based on differences between the first and second digest data structures, and receives the second base data structure from the second computing device and replaces the first base data structure with the second base data structure when the attempt is not successful.
1. A computing device comprising:
a control unit; and
a memory coupled to the control unit, the memory storing a first base data structure and a first digest data structure;
wherein the control unit is configured to:
maintain the first digest data structure based on entries stored in the first base data structure;
determine whether the first base data structure is in synchronization with a second base data structure stored in a second computing device;
wherein when the first base data structure is not in synchronization with the second base data structure, the control unit is further configured to:
receive a second digest data structure based on the second base data structure from the second computing device;
determine a third digest data structure based on differences between the first digest data structure and the second digest data structure;
attempt to synchronize the first base data structure to the second base data structure based on the third digest data structure; and
when the attempt is not successful, receive the second base data structure from the second computing device and replace the first base data structure with the second base data structure.
2. The computing device of claim 1 , wherein the first base data structure is selected from a group consisting of a virtual LAN table, a link aggregation group table, a layer 2 next hop table, a layer 3 routing table, a layer 3 forwarding information base, and a flow table.
3. The computing device of claim 1 , wherein the computing device is a network switching device selected from a group consisting of a router, a switch, a hub, and a bridge.
4. The computing device of claim 1 , wherein the first digest data structure is an invertible bloom filter.
5. The computing device of claim 1 , wherein the control unit is further configured to:
receive a first checksum for the second base data structure from the second computing device; and
determine whether the first base data structure is in synchronization with the second base data structure based on whether the first checksum matches a second checksum for the first base data structure.
6. The computing device of claim 1 , wherein the control unit is further configured to:
receive a first entry count for the second base data structure from the second computing device; and
attempt to synchronize the first base data structure to the second base data structure when a difference between the first entry count and a second entry count for the first base data structure is lower than a threshold.
7. The computing device of claim 6 , wherein the threshold is based on one or more selected from a group consisting of a number of buckets in the first digest data structure, the first entry count, and the second entry count.
8. The computing device of claim 1 , wherein to attempt to synchronize the first base data structure to the second base data structure, the control unit is further configured to:
identify a pure bucket in the third digest data structure; and
add a first entry to or remove a second entry from the first base data structure is based on the pure bucket in the third digest data structure.
9. A method of synchronizing base data structures, the method comprising:
maintaining a first digest data structure based on entries stored in a first base data structure, the first base data structure being stored in a first computing device;
receiving a second digest data structure based on a second base data structure from a second computing device;
determining a third digest data structure based on differences between the first digest data structure and the second digest data structure;
identifying a first entry in the first digest data structure that is not in the second digest data structure or a second entry in the second digest data structure that is not in the first digest data structure based on the third digest data structure; and
adding the second entry to the first base data structure or removing the first entry from the first base data structure in response to identifying the first entry or second entry.
10. The method of claim 9 , wherein the first digest data structure is an invertible bloom filter.
11. The method of claim 9 , further comprising:
receiving a first checksum for the second base data structure from the second computing device; and
determining whether the first base data structure is in synchronization with the second base data structure based on whether the first checksum matches a second checksum for the first base data structure.
12. The method of claim 9 , further comprising:
receiving a first entry count for the second base data structure from the second computing device; and
attempting to synchronize the first base data structure to the second base data structure when a difference between the first entry count and a second entry count for the first base data structure is lower than a threshold.
13. The method of claim 12 , wherein the threshold is based on one or more selected from a group consisting of a number of buckets in the first digest data structure, the first entry count, and the second entry count.
14. The method of claim 9 , wherein attempting to synchronize the first base data structure to the second base data structure comprises
identifying a pure bucket in the third digest data structure; and
wherein adding the second entry or removing the first entry from the first base data structure is based on the pure bucket in the third digest data structure.
15. A computing device, comprising:
a control unit; and
a memory coupled to the control unit, the memory storing a first base data structure and a first digest data structure;
wherein the control unit is configured to:
maintain the first digest data structure based on entries stored in the first base data structure;
receive a second digest data structure based on a second base data structure from a second computing device;
determine a third digest data structure based on differences between the first digest data structure and the second digest data structure;
identify a first entry in the first digest data structure that is not in the second digest data structure or a second entry in the second digest data structure that is not in the first digest data structure based on the third digest data structure;
transmit, to the second computing device, an entry add request to add the first entry to the second base data structure or an entry remove request to remove the second entry from the second base data structure; and
when the third digest data structure cannot be used to bring the second base data structure into synchronization with the first base data structure, transmit the first base data structure to the second computing device.
16. The computing device of claim 15 , wherein the first digest data structure is an invertible bloom filter.
17. The computing device of claim 15 , wherein the control unit is further configured to:
receive a first entry count for the second base data structure from the second computing device; and
determine the third digest data structure when a difference between the first entry count and a second entry count for the first base data structure is lower than a threshold;
wherein the threshold is based on one or more selected from a group consisting of a number of buckets in the first digest data structure, the first entry count, and the second entry count.
18. An information handling system, comprising:
a network switching device comprising:
a control unit; and
a memory coupled to the control unit, the memory storing a first base data structure and a first digest data structure;
wherein the control unit is configured to:
maintain the first digest data structure based on entries stored in the first base data structure;
receive a second digest data structure based on a second base data structure from a second network switching device;
determine a third digest data structure based on differences between the first digest data structure and the second digest data structure;
identify a first entry in the first digest data structure that is not in the second digest data structure or a second entry in the second digest data structure that is not in the first digest data structure based on the third digest data structure;
identify a pure bucket in the third digest data structure; and
add the second entry to the first base data structure or remove the first entry from the first base data structure in response to identifying the first entry or second entry.
19. The information handling system of claim 18 , wherein the first base data structure is selected from a group consisting of a virtual LAN table, a link aggregation group table, a layer 2 next hop table, a layer 3 routing table, a layer 3 forwarding information base, and a flow table.
20. The information handling system of claim 18 , wherein the control unit is further configured to:
receive a first entry count for the second base data structure from the second network switching device; and
determine the third digest data structure when a difference between the first entry count and a second entry count for the first base data structure is lower than a threshold;
wherein the threshold is based on one or more selected from a group consisting of a number of buckets in the first digest data structure, the first entry count, and the second entry count.