Accumulating star knowledge in replicated data protocol
A distributed system includes full and partial replicas of a set of data items that may be inserted, modified, or deleted by any replica. Replicas may occasionally synchronize with other arbitrarily chosen replicas to learn about updates. A replica's knowledge includes one or more knowledge fragments, where each fragment indicates a set of items. A type of knowledge fragment, called a star knowledge fragment, contains versions associated with all items in the system. Star knowledge fragments are compact because the set of items stored at a replica need not be explicitly listed. Once all replicas know of all updates in the system, partial and full replicas will have the same compact star knowledge fragment.
1. A method of synchronizing replicas in a system in which a collection of items are replicated fully or partially at two or more replicas, comprising:
arranging the replicas into a tree having a predefined synchronization hierarchy among the replicas;
recording item-set knowledge of which each replica is aware at each replica;
maintaining hierarchical information at each replica in the predefined synchronization hierarchy, wherein the hierarchical information maintained by at least one replica identifies a parent replica and a child replica of the at least one replica;
sending the item-set knowledge from a target replica to a source replica;
receiving, at the target replica, items that are previously unknown by the target replica and learned knowledge from the source replica, wherein the items that are previously unknown include items that are outside of an interest set of the source replica, and wherein the interest set comprises items that satisfy a filter;
assuming authority for the items that are outside of the interest set of the source replica by the target replica;
discarding the items that are outside of the interest set by the source replica after the target replica assumes authority for the items;
adding the items that are unknown by the target replica, and the learned knowledge to the target replica's item-set knowledge;
informing the target replica of versions of items for which the source replica is authoritative;
constructing star knowledge at the target replica from authoritative information from the source replica, wherein the star knowledge is a knowledge fragment that refers to a set of all items in the system;
combining star knowledge from source replicas into a star knowledge fragment with a knowledge vector containing an entry for all replicas;
reducing the overall size of the target replica's knowledge by discarding knowledge fragments that are covered by the star knowledge fragment;
creating a full replica at a root of the tree by providing the star knowledge fragment at the root of the tree in accordance with the hierarchical information; and
propagating the full replica to the predefined synchronization hierarchy in accordance with the hierarchical information maintained at each replica.
2. The method of claim 1 , further comprising:
a replica being authoritative for the versions that it creates.
3. The method of claim 1 , further comprising:
maintaining metadata at each replica to record a set of versions for which a replica is authoritative.
4. The method of claim 3 , further comprising:
maintaining the authoritative metadata as explicit version sets, an update history, star knowledge, or a version range.
5. The method of claim 1 , further comprising:
reducing the target replica's knowledge to a single star knowledge fragment.
6. The method of claim 1 , further comprising:
assuming authority for the versions at a parent replica for child replicas of the parent replica.
7. The method of claim 6 , further comprising:
relinquishing authority at child replicas for the versions passed to the parent replica.
8. The method of claim 7 , further comprising:
passing star knowledge from the parent replica to the child replicas during synchronization.
9. The method of claim 8 , further comprising:
maintaining version ranges at the child replicas containing versions of items produced by the child replicas or their descendants; and
clearing an update history when the child replicas synchronize with the parent replica.
10. The method of claim 1 , further comprising:
synchronizing the replicas in an ad-hoc fashion where no hierarchical relationship is established between the target replica and the source replica.