System and method for the distribution of hierarchically structured data

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.

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.

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.

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.