MOVE-IN/MOVE-OUT NOTIFICATION FOR PARTIAL REPLICA SYNCHRONIZATION

• US 20090006495A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rodeheffer, Thomas L., Terry, Douglas B., Wobber, Edward P., Ramasubramanian, Venugopalan Saraswati
• Granted Patent: US 7,685,185 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• 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

Abstract

A system is disclosed for synchronizing partially-replicated collections using the concept of item-set knowledge and move-out notifications. Move-out notifications are provided to allow removal of changed items from replicas when the change in the item takes that item outside of the interest set of the replicas.

Claims

1. A computer implemented method of synchronizing a plurality of replicas having a collection of items, the plurality of replicas including a target replica having a first interest set of items, and the plurality of replicas including a source replica having a second interest set of items, the method comprising the steps of:

(a) storing representations of items that are known to the target replica in the target replica;

(b) receiving a sync request from the target replica at the source replica, said request indicating versions of items known to the target replica;

(c) transmitting from the source replica to the target replica versions of items which are not known to the target replica; and

(d) transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met, the item falling within the first interest set of the target replica prior to the change in the item, and the item not falling within the first interest set of the target replica after the change in the item.

2. A computer implemented method as recited in claim 1, wherein said step (d) of transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met comprises the step of transmitting the notification if:

(i) the source replica stores the item,

(ii) the source replica'"'"'s version of the item is more recent than the target replica'"'"'s version of this item, and

(iii) the source replica'"'"'s version of the item is outside of the first interest set of the target replica.

3. A computer implemented method as recited in claim 1, wherein said step (d) of transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met comprises the step of transmitting the notification if:

(i) the source replica does not store the item,

(ii) a filter in the source replica defining the second item set is no more restrictive than a filter in the target replica defining the first item set, and

(iii) the source replica'"'"'s last known version of the item is more recent than the target replica'"'"'s version of the item.

4. A computer implemented method as recited in claim 1, wherein the method of synchronization employs transmitting item-set knowledge.

5. A computer implemented method as recited in claim 1, wherein the method of synchronization employs one of per-item version vectors, operation logs, multicast and two-way synchronization.

6. A computer implemented method as recited in claim 1, said step (d) of transmitting a notification of a changed item comprising the step of transmitting a unique identifier of the item that has changed and the version in which the item was changed.

7. A computer implemented method as recited in claim 1, further comprising the step (e) of removing the changed item from a database of stored items in the target replica upon receipt of the notification transmitted in said step (d).

8. A computer implemented method as recited in claim 1, wherein the items that are known to the target replica in step (a) include items stored in the target replica.

9. A computer implemented method as recited in claim 1, wherein the items that are known to the target replica in step (a) include items not stored in the target replica but known to the target replica as not being within the first interest set of the target replica.

10. A computer implemented method of synchronizing a plurality of replicas having a collection of items, the plurality of replicas including a target replica having a first interest set of items, and the plurality of replicas including a source replica having a second interest set of items, the method comprising the steps of:

(a) storing in the target replica one or more knowledge fragments representing versions of items within the first interest set of items in the target replica;

(b) storing in the target replica one or more knowledge fragments representing versions of items not within the first interest set of items in the target replica;

(c) receiving a sync request from the target replica at the source replica, said request containing a plurality of item-set knowledge fragments, said plurality of item-set knowledge fragments indicating versions of items of which the target replica is aware and which are within the first interest set of items, and said plurality of item-set knowledge fragments indicating versions of items not within the first interest set of items stored in said step (b);

(d) transmitting from the source replica to the target replica versions of items which are not known to the target replica and which are not represented by the one or more knowledge fragments stored in said step (a) or (b);

(e) transmitting from the source replica to the target replica a plurality of item-set knowledge fragments, said plurality of item-set knowledge fragments indicating versions of items learned by the target replica; and

(f) transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met, the item falling within the first interest set of the target replica prior to the change in the item, the item not falling within the first interest set of the target replica after the change in the item, and the changed version of the item not being known to the target replica.

11. A computer implemented method as recited in claim 10, wherein said step (f) of transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met comprises the step of transmitting the notification if:

(i) the source replica stores the item,

(ii) the source replica'"'"'s knowledge of the item dominates the target replica'"'"'s knowledge, and

(iv) the source replica'"'"'s version of the item is outside of the first interest set of the target replica.

12. A computer implemented method as recited in claim 10, wherein said step (f) of transmitting from the source replica to the target replica a notification of a changed item if a set of predetermined conditions are met comprises the step of transmitting the notification if:

(i) the source replica does not store the item,

(ii) a filter in the source replica defining the second item set is no more restrictive than a filter in the target replica defining the first item set, and

(iii) the source replica'"'"'s knowledge of the item dominates the target replica'"'"'s knowledge of the item.

13. A computer implemented method as recited in claim 10, further comprising the step (g) of removing the changed item from a database of stored items in the target replica upon receipt of the notification transmitted in said step (f).

14. A computer implemented method as recited in claim 10, further comprising the step (h) of transmitting from the target replica to the source replica as part of the sync request an explicit list of identifiers for the items that are currently stored at the target replica so that the source replica can avoid returning notifications for items that are not stored at the target replica.

15. A computer implemented method of synchronizing a plurality of replicas having a collection of items, the plurality of replicas including a target replica having a first interest set of items, and the plurality of replicas including a source replica having a second interest set of items, the method comprising the steps of:

(a) storing in the target replica one or more knowledge fragments representing both versions of items within the first interest set of items in the target replica and versions of items not within the first interest set of items in the target replica;

(b) receiving a sync request from the target replica at the source replica, said request containing a plurality of item-set knowledge fragments, said plurality of item-set knowledge fragments indicating versions of items of which the target replica is aware and which are within the first interest set of items, and said plurality of item-set knowledge fragments indicating versions of items not within the first interest set of items stored in said step (a);

(c) transmitting from the source replica to the target replica versions of items which are not known to the target replica and which are not represented by the one or more knowledge fragments stored in said step (a);

(d) transmitting from the source replica to the target replica a plurality of item-set knowledge fragments indicating versions of items learned by the target replica and within the first interest set of the target replica and versions of items learned by the target replica and not within the first interest set of the target replica.

16. A computer implemented method as recited in claim 15, wherein the plurality of item-set knowledge fragments transmitted in said step (d) are added to the one or more knowledge fragments stored in said step (a).

17. A computer implemented method as recited in claim 15, further comprising the step (e) of transmitting from the source replica to the target replica a notification of a changed item, the item falling within the first interest set of the target replica prior to the change in the item, and the item not falling within the first interest set of the target replica after the change in the item.

18. A computer implemented method as recited in claim 17, further comprising the step (f) of removing the changed item from a database of stored items in the target replica upon receipt of the notification transmitted in said step (e).

19. A computer implemented method as recited in claim 18, further comprising the step of transmitting from the target replica to the source replica as part of the sync request an explicit list of identifiers for the items that are currently stored at the target replica so that the source replica can avoid returning notifications for items that are not stored at the target replica.

20. A computer implemented method as recited in claim 19 where the list of identifiers for the items that are currently stored at the target replica is sent in compressed form, such as using a Bloom filter.