System and method for the distribution of hierarchically structured data

• US 5,812,773 A
• Filed: 07/12/1996
• Issued: 09/22/1998
• Est. Priority Date: 07/12/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Norin, Scott
• Primary Examiner(s): Barry, Lance Leonard
• Assistant Examiner(s): PATRU, DANIEL
• Application Number:
  US08/679,209
• Time in Patent Office: 802 Days
• Field of Search: 395/200.31, 395/200.35, 395/200.34, 395/200.78
• US Class Current: 709/204
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/1886 with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9094 Arrangements for simultaneous transmit and receive, e.g. simultaneous reading/writing from/to the storage element

Abstract

A system and method for replicating hierarchical data is disclosed. The system and method preferably use one-way, unacknowledged communication messages to transfer data among various servers in a computer network. In many instances replicating hierarchically structured data requires processing the data in a hierarchical fashion even though the data is received in essentially random order. Hierarchically structured data is processed in the proper order by dynamically reconstructing the hierarchy as messages are received and processed. The invention first stores received replication packets in an incoming packet store. The data is processed by creating certain structures in memory for each corresponding replication packet and then processing all entries in the structures that can be processed. Global lists are kept for entries that remain unprocessed. If entries remain unprocessed because of hierarchical dependence on unprocessed data, the structures will remain in memory for a period of time in anticipation that the parent will soon be processed. When parent data is processed, the global lists are checked for child data that can then be processed.

Claims

1. In a replication enterprise comprising a plurality of replica nodes, each having a copy of a plurality of replica objects that have a hierarchical relationship, and each of which may make changes to the replica objects that affect the hierarchical relationship and each of which replicates changes to other replica nodes without enforcing any particular chronological order, a method of replicating changes made to the replica objects among the replica nodes so that the hierarchical relationship of the replica objects are properly preserved at each replica node independent of the chronological order in which the changes are received, the method comprising the steps of:

receiving, at a local node via networking neans, a plurality of one-way unacknowledged replication packets which together comprise a plurality of changes to at least one of the replica objects, at least one of said changes having a hierarchical dependence on at least one other change so that the changes must be processed in a designated hierarchical order independent of any received chronological order if the hierarchical relationship between the replica objects is to be properly preserved on said local node;

storing said received replication packets in an incoming packet store so the received replication packets will be available for processing;

selecting a replication packet from the incoming packet store for processing;

for each change in the elected replication packet, performing the steps of;

selecting a change to process based on a designated criteria that selects chances according to a plurality of change types;

if said selected change has a hierarchical dependence on another change that has not yet been processed, then deferring processing of the selected change and selecting another change to process;

if said selected change does not have a hierarchical dependence on another change that has not yet been processed, then (a) processing the change and then (b) processing any changes whose processing was deferred due to a dependence on the change just processed and then (c) selecting another change to process.

2. A method of replicating hierarchically structured data as recited in claim 1 wherein the replication packets in the incoming packet store are selected for processing based on a priority that is dependent on the type of replication packet.

3. A method of replicating hierarchically structured data as recited in claim 1 wherein received replication packets containing hierarchically dependent changes are assigned a timeout value and wherein the method further comprises the step of removing any replication packet whose timeout value has been exceeded before the replication packet is processed.

4. A method of replicating hierarchically structured data as recited in claim 1 wherein change identifiers are associated with the changes in said received replication packets that uniquely identify said changes and wherein the method further comprises the step of adding change identifiers associated with changes successfully processed to a change set comprising the change identifiers of all changes made locally or received via replication packets and successfully processed.

5. A method of replicating hierarchically structured data as recited in claim 1 wherein the changes contained in a replication packet comprise deletion of replica objects, creation of replica objects, or modification of replica objects and wherein the step of selecting a change to process selects any changes deleting replica objects for processing before selecting changes modifying or creating replica objects for processing.

6. A method of replicating hierarchically structured data as recited in claim 5 further comprising the step of processing a change that attempts to delete a parent replica object with at least one undeleted child replica object by first promoting said at least one child replica object to the same level as the parent replica object and then deleting the parent replica object.

7. In a replication enterprise comprising a plurality of replica nodes, each having a copy of a plurality of replica objects flat have a hierarchical relationship, and each of which may make changes to the replica objects that affect the hierarchical relationship and each of which replicates changes to other replica nodes without enforcing any particular chronological order, a method of replicating changes made to the replica objects among the replica nodes so that the hierarchical relationship of the replica objects are properly preserved at each replica node independent of the chronological order in which the changes are received, the method comprising the steps of:

receiving, at a local node via networking means, a plurality of one-way unacknowledged replication packets which together comprise a plurality of changes to at least one of the replica objects, at least one of said changes having a hierarchical dependence on at least one other change so that the changes must be processed in a designated hierarchical order independent of any received chronological order if the hierarchical relationship between the replica objects is to be properly preserved on said local node;

storing received replication packets in an incoming packet store so the received replication packets will be available for processing;

selecting a replication packet from the incoming packet store for processing;

creating an information object associated with said selected replication packet, said information object comprising an entry corresponding to each change in said selected replication packet so that processing each entry in said information object will result in processing each change of said selected replication packet; and

for each entry in the information object performing the steps of;

selecting an entry for processing based on the type of change that corresponds to said entry;

attempting to process the entry in the information object; and

if the entry could not be processed due to a hierarchical dependence on unprocessed changes, then deferring processing of the change corresponding to the entry in the information object.

8. A method of replicating hierarchically structured data as recited in claim 7 further comprising the step of retaining the information object if any entries remain unprocessed due to a hierarchical dependence on unprocessed information.

9. A method of replicating hierarchically structured data as recited in claim 8 further comprising the step of selecting another replication packet for processing and creating an associated information object when no more entries remain in existing information objects that can be processed.

10. A method of replicating hierarchically structured data as recited in claim 9 further comprising the step of processing any entries whose processing had been previously deferred due to a hierarchical dependence on unprocessed changes once the information object causing the hierarchical dependence on unprocessed changes has been successfully processed.

11. A method of replicating hierarchically structured data as recited in claim 10 further comprising the steps of assigning a timeout value to said information object and removing said information objects when the timeout value is exceeded.

12. A method of replicating hierarchically structured data as recited in claim 11 wherein the step of removing said information object when the timeout value is exceeded also removes the replication packet associated with said timed out information object.

13. A method of replicating hierarchically structured data as recited in claim 11 further comprising the step of not removing an information object whose timeout value has been exceeded if entries in the information object are currently being processed.

14. A method of replicating hierarchically structured data as recited in claim 13 further comprising the step of not removing any other information object whose timeout value has been exceeded if said any other information object has entries that have a hierarchical relationship to entries of the information object whose entries are being processed.

15. A method of replicating hierarchically structured data as recited in claim 14 further comprising the step of adding a unique change identifier for each successfully processed change, to a locally stored change set comprising changes made locally and changes that have been successfully processed and that were received via replication packets.

16. A method of replicating hierarchically structured data as recited in claim 15 wherein replication packets containing changes to replica objects that have a hierarchical dependence on other replica objects are processed before changes to replica objects that have no such hierarchical dependence.

17. A method of replicating hierarchically structured data as recited in claim 7 further comprising the step of processing entries in said information object that correspond to deletion of hierarchically structured replica objects before processing entries in said information object that correspond to creation or modification of hierarchically structured replica objects.

18. A method of replicating hierarchically structured data as recited in claim 17 wherein the step of deferring processing of entries only defers processing if such entries correspond to creation or modification of hierarchically structured replica objects.

19. A method of replicating hierarchically structured data as recited in claim 18 further comprising the step of processing entries that attempt to delete a parent replica object having at least one undeleted child replica object by promoting said at least one undeleted child replica object to the level of the parent replica object and then deleting the parent replica object.

20. A method of replicating hierarchically structured data as recited in claim 19 further comprising the step of processing each deleted replica object by adding a replica object ID that uniquely identifies the deleted replica object and a change identifier that uniquely identifies the change that caused deletion of the deleted replica object to a local tombstone set comprising replica object IDs and change identifiers for all deleted replica objects.

21. A method of replicating hierarchically structured data as recited in claim 20 further comprising the step of processing entries attempting to delete a replica object that does not exist locally by adding a replica object ID and a change identifier associated with said nonexistent replica object to said local tombstone set.

22. In a replication enterprise comprising a plurality of replica nodes, each having a copy of a plurality of replica objects that have a hierarchical relationship, and each of which may make changes to the replica objects that affect the hierarchical relationship and each of which replicates changes to other replica nodes without enforcing any particular chronological order, a method of replicating changes made to the replica objects among the replica nodes so that the hierarchical relationship of the replica objects are properly preserved at each replica node independent of the chronological order in which the changes are received, the method comprising the steps of:

receiving, at a local node via networking means, a plurality of one-way unacknowledged replication rackets which together comprise a plurality of changes to at least one of the replica objects, at least one of said changes having a hierarchical dependence on at least one other change so that the changes must be processed in a designated hierarchical order independent of any received chronological order if the hierarchical relationship between the replica objects is to be properly preserved on said local node;

storing received replication packets in an incoming packet store so the received replication packets will be available for processing;

selecting a replication packet from the incoming packet store for processing;

creating an information object associated with said selected replication packet, said information object comprising an entry corresponding to each change in said selected replication packet so that processing each entry in said information object will result in processing each change of said selected replication packet;

associating a timeout value with said information object so that when said timeout value is exceeded, the information object can be removed;

processing entries in the information object corresponding to deletion of replica objects by performing the following steps;

processing all entries that delete replica objects that have no undeleted child replica objects; and

processing all entries that delete parent replica objects that have undeleted child replica objects by first promoting undeleted child replica objects to the level of their parent replica object and then deleting the parent replica object;

processing entries in the information object corresponding to creation or modification of replica objects by performing the following steps;

attempting to process the entry in the information object;

if the entry could not be processed due to a hierarchical dependence on unprocessed changes, then deferring processing of the change corresponding to the entry in the information object; and

if the entry is successfully processed, then processing any entries whose processing was previously deferred and that have a hierarchical dependence on the entry successfully processed;

when no processible entries remain in the information object, selecting another replication packet for processing and creating another information object associated with said another replication packet.

23. In a computer system defining a location in a replication enterprise where replica objects are replicated among a plurality of such computer systems connected together by networking means without enforcing any particular chronological order so that changes made to one copy of a replica object on one system are reflected in other copies of the replica object on other systems through the replication, receipt, and processing of such changes, an article of manufacture comprising:

program storage means for storing program code means, said program storage means adapted for access by a local computer system so that said program code means can be provided to a CPU of said local computer system, said program code means comprising;

replication packet store means for storing incoming replication packets until said incoming replication packets can be processed;

means for selecting a replication packet from the replication packet store means for processing;

means for selecting a change to process according to a plurality of change types so that changes of one type are processed before changes of another type;

means for processing changes in said selected replication packet that correspond to creation of hierarchically structured replica objects, said means for processing comprising;

means for deferring processing of changes that cannot be processed due to a hierarchical dependence on unprocessed changes and for retaining such unprocessible changes until a future time when they may be processed because the changes on which they depend have been processed; and

means for reprocessing changes whose processing has been previously deferred due to a hierarchical dependence on unprocessed changes, and whenever a change is successfully processed, said means for reprocessing changes operating to locate previously deferred changes that have a hierarchical dependence on said successfully processed change and to place such previously deferred changes in condition for processing.

24. An article of manufacture as recited in claim 23 wherein the means for selecting a replication packet for processing comprises means for prioritizing the replication packets so they are selected based on a predetermined priority scheme.

25. An article of manufacture as recited in claim 23 further comprising means for assigning a timeout value to the changes in the received replication packets.

26. An article of manufacture as recited in claim 25 further comprising means for removing replication packets whose timeout values have been exceeded.

27. An article of manufacture as recited in claim 23 further comprising means for creating at least one information object associated with each received replication packet, said at least one information object comprising an entry for each change in its associated replication packet so that processing each entry in said at least one information object will result in processing each change of said associated replication packet.

28. An article of manufacture as recited in claim 23 further comprising means for storing a change set comprising a list of changes that have been successfully processed.

29. An article of manufacture as recited in claim 23 wherein the means for processing changes in said selected replication packet that correspond to creation of hierarchically structured replica objects also processes changes in said selected replication packet that correspond to modification of hierarchically structured replica objects.

30. An article of manufacture as recited in claim 23 further comprising means for processing changes relating to deletion of replica objects comprising:

means for deleting a parent replica object without undeleted child replica objects, that first deletes said parent replica object and then enters a unique replica object identifier and a unique change identifier, each associated with said deleted parent replica object, into a tombstone set comprising replica object identifiers and change identifiers for all deleted replica objects; and

means for deleting a parent replica object with at least one undeleted child replica object, that first promotes said at least one child replica object and then deletes said parent replica object and enters a unique replica object identifier and a unique change identifier, each associated with said deleted parent replica object, into a tombstone set comprising replica object identifiers and change identifiers for all deleted replica objects.

31. In a computer system defining a location in a replication enterprise where replica objects are replicated among a plurality of such computer systems connected together by networking means without enforcing any particular chronological order so that changes made to one copy of a replica object on one system are reflected in other copies of the replica object on other systems through the replication, receipt, and processing of such changes, an article of manufacture comprising:

program storage means for storing program code means, said program storage means adapted for access by a local computer system so that said program code means can be provided to a CPU of said local computer system, said program code means comprising;

replication packet store means for storing incoming replication packets until said incoming replication packets can be processed;

means for selecting a replication packet from the replication packet store means for processing;

means for creating at least one information object associated with said selected replication packet, said at least one information object comprising an entry for each change in said selected replication packet so that processing each entry in said at least one information object will result in processing each change of said selected replication packet;

means for selecting an entry in said at least one information object to process according to a plurality of change types so that entries that correspond to changes of one type are processed before entries that correspond to changes of another type;

means for processing entries in said at least one information object that correspond to creation of hierarchically structured replica objects, said means for processing comprising;

means for deferring processing of entries in said at least one information object that cannot be processed due to a hierarchical dependence on unprocessed changes and for retaining such unprocessible entries until a future time when they may be processed because the changes on which they depend have been processed; and

means for reprocessing entries in said at least one information object whose processing had been previously deferred due to a hierarchical dependence on unprocessed changes, and whenever an entry in an information object is successfully processed, said means for reprocessing entries operating to locate previously deferred entries that have a hierarchical dependence on said successfully processed entries and to place such previously deferred entries in condition for processing.

32. An article of manufacture as recited in claim 31 wherein the means for processing entries in said at least one information object that correspond to creation of hierarchically structured replica objects, also processes entries in said at least one information object that correspond to modification of hierarchically structured replica objects.

33. An article of manufacture as recited in claim 31 further comprising means for associating a timeout value with said at least one information object.

34. An article of manufacture as recited in claim 33 further comprising means for removing said at least one information object and its associated replication packet when said timeout value has been exceeded.

35. An article of manufacture as recited in claim 34 further comprising means for preventing the timeout and removal of information objects with entries that are being processed.

36. An article of manufacture as recited in claim 35 wherein such means for preventing the timeout and removal of information objects with entries that are being processed will prevent the timeout and removal of any hierarchically related information objects if one such hierarchically related information object has entries that are being processed.

37. An article of manufacture as recited in claim 36 further comprising means for processing entries in said at least one information object relating to deletion of replica objects comprising:

means for deleting a parent replica object without undeleted child replica objects, that first deletes said parent replica object and then enters a unique replica object identifier and a unique change identifier, each associated with said deleted parent replica object, into a tombstone set comprising replica object identifiers and change identifiers for all deleted replica objects; and

means for deleting a parent replica object with at least one undeleted child replica object, that first promotes said at least one child replica object and then deletes said parent replica object and enters a unique replica object identifier and a unique change identifier, each associated with said deleted parent replica object, into a tombstone set comprising replica object identifiers and change identifiers for all deleted replica objects.