Granular control over the authority of replicated information via fencing and unfencing

• US 7,660,833 B2
• Filed: 12/10/2003
• Issued: 02/09/2010
• Est. Priority Date: 07/10/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bjorner, Nikolaj S., Teodosiu, Dan
• Primary Examiner(s): Ly; Cheyne D
• Application Number:
  US10/733,459
• Publication Number:
  US 20050015413A1
• Time in Patent Office: 2,253 Days
• Field of Search: 707/100, 707/203, 707/204, 707/201, 707/202, 709/220, 709/206, 709/217, 709/218, 709/219, 709/236, 709/237, 714/6, 714/7, 714/19, 714/24
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A method and system for controlling which content gets precedence and is replicated. A replica set is comprised of a set of resources. Each resource is associated with resource data and resource meta-data. For files-based systems, resource data includes file contents and attributes, while resource meta-data includes additional attributes that are relevant for negotiating synchronization during replication. An extra field called a “fence value” is added to the meta-data associated with each resource. During synchronization, first fence values are compared. The resource with the highest fence value includes the content that is controlling and replicated. If fence values are equal (and greater than a particular value), the controlling resource is determined based on other meta-data.

Claims

1. A computer storage media storing computer-executable instructions that when executed perform a method comprising:

receiving a first fence value and first meta-data of the first member of a replica set, wherein the first fence value is independent of any change made to content of the first member of the replica set and is used to resolve a conflict between information in the first member of the replica set and information in the second member of the replica set;

comparing the first fence value with a second fence value of a second member of the replica set;

determining whether the first fence value has precedence over the second fence value;

based on the determining, changing content of the second member to reflect content of the first member; and

changing second meta-data of the second member to indicate a change in the content of the second member and maintaining the second fence value unchanged, wherein the second fence value is independent of any change made to the content of the second member.

2. The computer storage media of claim 1, wherein the second fence value and the second meta-data is stored in a store separate from the content of the second member.

3. The computer storage media of claim 1, wherein changing content of the second member comprises determining one or more differences between content on the first member and the content of the second member.

4. The computer storage media of claim 1, wherein the content on the second machine comprises file data and file attributes.

5. The computer storage media of claim 1, wherein the first meta-data further comprises a first digest that summarizes the first resource and the second meta-data further comprises a second digest that summarizes the second resource.

6. The computer storage media of claim 5, further comprising comparing the first digest with the second digest and bypassing the changing the content of the second member if the first digest and the second digest are equivalent.

7. The computer storage media of claim 1, further comprising if the first fence value is equal to the second fence value, comparing the first meta-data with the second meta-data to determine whether the content on the second member should be changed.

8. The computer storage media of claim 1, wherein each of the first fence value and the second fence value is assigned to a portion of content on its respective member of the replica set.

9. A computer storage media storing computer-executable instructions that when executed perform a method comprising:

determining whether a first resource residing on a first machine should be used to update a second resource residing on a second machine, each resource associated with a fence value, meta-data, and content, each meta-data including one or more fields that are updated whenever the content of the associated resource is changed and, each fence value indicating whether its associated resource should be used to update a resource on another machine, the fence value having precedence over the meta-data, wherein each fence value is independent of any change made to content of its associated resource and is used to resolve a conflict between information on the first machine and information on the second machine;

preventing propagation from the second machine based on the fence value of the second resource indicating that the second resource should not be propagated; and

updating the second resource from the first resource based on the fence value of the first resource having precedence over the fence value of the second resource, and maintaining the fence value of the first resource and the fence value of the second resource unchanged.

10. The computer storage media of claim 9, further comprising if the fence values of the first and second resources are equivalent, determining which machine will be updated based on the meta-data.

11. The computer storage media of claim 10, wherein the meta-data comprises a logical clock indicating the last time the corresponding content was updated.

12. The computer storage media of claim 11, wherein a fence value indicates that its corresponding resource may be propagated to other machines until another resource with a higher fence value is located on another machine.

13. The computer storage media of claim 9, wherein the meta-data associated with the first resource is stored in a separate data structure from its corresponding resource.

14. The computer storage media of claim 13, wherein the data structure is corrupted or deleted, further comprising rebuilding the data structure and decrementing the fence value associated with the first resource.

15. The computer storage media of claim 14, further comprising rebuilding the data structure a plurality of times and decrementing the fence value associated with the first resource each time the data structure is rebuilt.

16. The computer storage media of claim 15, further comprising if the fence value of the second resource has precedence over the fence value of the first resource, updating the first resource from the second resource.

17. A system for replicating data, comprising:

a first machine having a first set of resources;

a second machine having a second set of resources, wherein each resource on each machine is associated with a fence value, meta-data, and content, each meta-data including one or more fields that are updated whenever the content of the associated resource is changed and, each fence value indicating whether its associated resource should be used to update a resource on another machine independently from other meta-data and each fence value being independent of any change made to content of its associated resource and being used to resolve a conflict between information on the first machine and information on the second machine, wherein the first and second machines are configured to;

communicate information regarding the resources contained by both machines; and

update each resource that is out-of-date according to the following precedence;

determining whether a fence value of a resource on one of the machines has precedence over the fence value of a corresponding resource on the other machine;

if a fence value of a resource on one of the machines has precedence over the fence value of a corresponding resource on the other machine, updating the other machine with the resource on the one machine;

otherwise

updating the resource on the machines based on data other than the fence values, wherein the fence values are maintained unchanged.

18. The system of claim 17, wherein the first set of resources is loaded from a backup and the fence values thereof are set to cause the first set of resources to have precedence over any other set of resources, such that any other set of resources on any other machine that corresponds to the set of resources are updated from the first set of resources.

19. The system of claim 17, wherein the fence values of the first set of resources are marked to have precedence over corresponding resources on other machines, such that the corresponding resources are updated from the first set of resources.

20. A computer implemented method of replicating data, the method comprising:

receiving a first fence value and first meta-data of a first member of a replica set, wherein the first fence value is independent of any change made to content of the first member of the replica set and is used to resolve a conflict between information on the first machine and information on the second machine;

comparing the first fence value with a second fence value of a second member of the replica set;

determining whether the first fence value has precedence over the second fence value;

based on the determining, changing content of the second member to reflect content of the first member; and

changing second meta-data of the second member of the replica set to indicate a change in the content of the second member and maintaining the second fence value unchanged, wherein the second fence value is independent of any change made to the content of the second member.

21. The method of claim 20, wherein the second meta data is stored in a store separate from the content of the second member.

22. The method of claim 20, wherein changing the content of the second member comprises determining one or more differences between content on the first member and the content of the second member.

23. The method of claim 22, wherein content on the first machine and the content on the second machine is the same.

24. The method of claim 20, wherein the content on the second machine comprises file data and file attributes.

25. The method of claim 20, wherein the first meta-data comprises a digest that summarizes the first resource and the second meta-data comprises a second digest that summarizes the second resource.

26. The method of claim 25, further comprising comparing the first digest and the second digest and bypassing the changing the content of the second member if the digests are equivalent.

27. The method of claim 20, further comprising if the first fence value is equal to the second fence value, comparing the first meta-data with the second other meta-data to determine whether the content on the second machine should be changed.

28. The method of claim 20, wherein each of the first fence value and the second fence value is assigned to a portion of its respective member of the replica set.