Coherency of replicas for a distributed file sharing system

• US 7,500,020 B1
• Filed: 12/31/2003
• Issued: 03/03/2009
• Est. Priority Date: 12/31/2003
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Ranade, Dilip Madhusudan, Banerjee, Anindya, Gunda, Laxmikant Vithal, Kabra, Navin, Venkata, Sivaramakrishna Ramadugu, Nanda, BijayaLaxmi, Shelat, Radha
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): Mesfin; Yemane
• Application Number:
  US10/749,365
• Time in Patent Office: 1,889 Days
• Field of Search: 709/246, 709/248, 707/9, 707201-204
• US Class Current: 709/248
• CPC Class Codes: G06F 16/176 Support for shared access to files; File sharing support
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: G06F 16/1865 Transactional file systems
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A plurality of data objects may be replicated across a plurality of computing nodes coupled to a network. The network may include a first node operable to initiate an update operation to update a plurality of replicas of a first object. If one or more of the replicas are not reachable then the update operation may update a subset (e.g., a quorum) but not all of the replicas. For each node on which one of the replicas was updated in the update operation, the node may add the object to a list of incoherent objects. The list of incoherent objects may subsequently be used to bring the lagging replicas in sync with the replicas that were updated. In another embodiment, a plurality of replicas of an object may be stored on a plurality of nodes, similarly as described above. A first node that stores a replica of the object may store a first timestamp associated with the replica on the first node. The timestamp may be used to ensure that the replica on the first node is coherent with respect to one or more other replicas by periodically communicating with the one or more other replicas when a threshold amount of time has passed without the replica on the first node receiving an update.

Claims

1. A computer-readable storage medium storing program instructions executable to implement a method comprising:

storing a respective replica of an object on each respective node of a plurality of nodes;

a first node of the plurality of nodes initiating a first distributed transaction to attempt to synchronously update the replicas of the object stored on each of other nodes of the plurality of nodes, wherein each respective node of a first subset of the other nodes successfully commits the first distributed transaction to update the replica of the object stored on the respective node, and wherein each node of a second subset of the other nodes does not successfully commit the first distributed transaction; and

each respective node of the first subset of the other nodes adding an identification of the object to a respective list of incoherent objects stored on the respective node in response to determining that not all of the other nodes successfully committed the first distributed transaction;

wherein the first subset of the other nodes includes a second node of the plurality of nodes;

wherein the method implemented by the program instructions further comprises;

after the second node adds the identification of the object to the respective list of incoherent objects stored on the second node, the second node attempting to communicate with each of the plurality of nodes other than the second node; and

in response to successfully communicating with each of the plurality of nodes other than the second node, the second node initiating a second distributed transaction to synchronize the replicas stored on the second subset of the other nodes with the replicas stored on the first subset of the other nodes.

2. The computer-readable storage medium of claim 1, wherein the method implemented by the program instructions further comprises:

the first node updating the replica of the object stored on the first node; and

the first node adding an identification of the object to a respective list of incoherent objects stored on the first node in response to determining that not all of the other nodes successfully committed the first distributed transaction.

3. The computer-readable storage medium of claim 1,

wherein the first subset of the other nodes includes at least a quorum of the plurality of nodes.

4. The computer-readable storage medium of claim 1,

wherein the method implemented by the program instructions further comprises each respective node of the first subset of the other nodes removing the identification of the object from the respective list of incoherent objects stored on the respective node in response to said synchronizing the replicas stored on the second subset of the other nodes with the replicas stored on the first subset of the other nodes.

5. The computer-readable storage medium of claim 1,

wherein each respective node of the first subset of the other nodes updates the replica of the object stored on the respective node by applying a first change to the replica of the object stored on the respective node;

wherein synchronizing the replicas stored on the second subset of the other nodes with the replicas stored on the first subset of the other nodes comprises each respective node of the second subset of the other nodes applying the first change to the replica of the object stored on the respective node.

6. The computer-readable storage medium of claim 1,

wherein the object is a first object of a plurality of objects, wherein each object of the plurality of objects has a plurality of replicas stored on the plurality of nodes;

wherein the respective list of incoherent objects stored on the second node includes identifications of one or more additional objects of the plurality of objects in addition to the first object;

wherein the method implemented by the program instructions further comprises;

for each respective object of the one or more additional objects identified in the list of incoherent objects stored on the second node, the second node attempting to communicate with the plurality of replicas of the respective object to initiate a respective distributed transaction to synchronize the plurality of replicas of the respective object.

7. The computer-readable storage medium of claim 1,

wherein the method implemented by the program instructions further comprises:

the second node periodically attempting to communicate with each of the nodes of the plurality of nodes other than the second node;

in response to determining that a particular amount of time has passed without successfully communicating with each of the nodes of the plurality of nodes other than the second node, the second node initiating an operation to create one or more new replicas of the object.

8. The computer-readable storage medium of claim 1,

wherein the list of incoherent objects stored on the second node is stored in persistent storage of the second node;

wherein the second node adding the identification of the object to the respective list of incoherent objects stored on the second node comprises;

the second node storing information indicating addition of the identification of the object without modifying the list of incoherent objects stored in the persistent storage of the second node;

after storing the information indicating the addition of the identification of the object, the second node updating the list of incoherent objects stored in the persistent storage of the second node to reflect the addition of the identification of the object.

9. The computer-readable storage medium of claim 1,

wherein each respective node updating the replica of the object stored on the respective node comprises each respective node applying a change to the replica of the object stored on the respective node.

10. The computer-readable storage medium of claim 1,

wherein the replicas of the object stored on the plurality of nodes include a plurality of persistent replicas of the object.

11. The computer-readable storage medium of claim 1,

wherein the object is a file;

wherein each replica of the object is a replica of the file.

12. The computer-readable storage medium of claim 1,

wherein the method implemented by the program instructions further comprises the first node receiving an update message;

wherein the first node initiates the first distributed transaction in response to the update message to attempt to synchronously update the replicas of the object stored on the other nodes.

13. A system comprising:

a plurality of nodes;

wherein the plurality of nodes includes memory storing program instructions executable to implement a method comprising;

storing a respective replica of an object on each respective node of the plurality of nodes;

a first node of the plurality of nodes initiating a first distributed transaction to attempt to synchronously update the replicas of the object stored on each of other nodes of the plurality of nodes, wherein each respective node of a first subset of the other nodes successfully commits the first distributed transaction to update the replica of the object stored on the respective node, and wherein each node of a second subset of the other nodes does not successfully commit the first distributed transaction; and

each respective node of the first subset of the other nodes adding an identification of the object to a respective list of incoherent objects stored on the respective node in response to determining that not all of the other nodes successfully committed the first distributed transaction;

wherein the first subset of the other nodes includes a second node of the plurality of nodes;

wherein the method implemented by the program instructions further comprises;

the second node adds the identification of the object to the respective list of incoherent objects stored on the second node, the second node attempting to communicate with each of the plurality of nodes other than the second node; and

in response to successfully communicating with each of the plurality of nodes other than the second node, the second node initiating a second distributed transaction to synchronize the replicas stored on the second subset of the other nodes with the replicas stored on the first subset of the other nodes.

14. The system of claim 13, wherein the method implemented by the program instructions further comprises:

the first node updating the replica of the object stored on the first node; and

the first node adding an identification of the object to a respective list of incoherent objects stored on the first node in response determining that not all of the other nodes successfully committed the first distributed transaction.

15. A method comprising:

storing a respective replica of an object on each respective node of a plurality of nodes;

a first node of the plurality of nodes initiating a first distributed transaction to attempt to synchronously update the replicas of the object stored on each of other nodes of the plurality of nodes, wherein each respective node of a first subset of the other nodes successfully commits the first distributed transaction to update the replica of the object stored on the respective node, and wherein each node of a second subset of the other nodes does not successfully commit the first distributed transaction; and

each respective node of the first subset of the other nodes adding an identification of the object to a respective list of incoherent objects stored on the respective node in response to determining that not all of the other nodes successfully committed the first distributed transaction;

wherein the first subset of the other nodes includes a second node of the plurality of nodes;

wherein the method further comprises;

after the second node adds the identification of the object to the respective list of incoherent objects stored on the second node, the second node attempting to communicate with each of the plurality of nodes other than the second node; and

in response to successfully communicating with each of the plurality of nodes other than the second node, the second node initiating a second distributed transaction to synchronize the replicas stored on the second subset of the other nodes with the replicas stored on the first subset of the other nodes.

16. The method of claim 15, further comprising:

the first node updating the replica of the object stored on the first node; and

the first node adding an identification of the object to a respective list of incoherent objects stored on the first node in response to determining that not all of the other nodes successfully committed the first distributed transaction.