Replication and replica management in a wide area file system

• US 7,739,240 B2
• Filed: 12/09/2002
• Issued: 06/15/2010
• Est. Priority Date: 12/09/2002
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Saito, Yasushi, Karamanolis, Christos
• Primary Examiner(s): Le; Miranda
• Application Number:
  US10/315,582
• Publication Number:
  US 20040111390A1
• Time in Patent Office: 2,745 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-205, 707/634, 707/827, 707/999.204, 709/203, 709217-231, 709/248
• US Class Current: 707/634
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

An embodiment of the invention provides a method and apparatus for constructing and maintaining a consistent hierarchical namespace in a wide-area distributed file system, where individual files and directories are replicated in the system. An embodiment of the invention provides a method and apparatus for achieving eventual data (file contents) and metadata (directory contents) consistency in a wide-area distributed file system.

Claims

1. A method of managing replicated files for a wide-area distributed file system, the method comprising:

storing at least three replicas of a file, each replica being located at a corresponding one of a plurality of computer nodes connected by a graph and each replica having an indication of its location in the file system;

accessing one of the replicas for performing a write operation thereby making an update to the replica; and

after the update is made, propagating the update to the other replicas in two phases by sending a harbinger for the update along the graph to the other computer nodes that store the replicas in a first phase, the harbinger being other than the update, and, in response to the harbinger, receiving a request for the update from one or more of the other computer nodes in a second phase,

wherein the indication for each replica comprises a directory identifier and file name for the replica,

wherein the update comprises a delta that describes a change to a portion of the file, and

wherein the harbinger includes a timestamp corresponding to the update.

2. The method according to claim 1, wherein the timestamp is a first timestamp that represents the state of the replica just before the change in the replica, and the harbinger further includes a second timestamp that represents the state of the replica after the change in the replica.

3. The method according to claim 2, wherein a computer node applies the update only if a timestamp for the replica at the computer node matches the first timestamp and, otherwise, the node requests a full file transfer.

4. The method according to claim 1, wherein in response to receiving a harbinger, a computer node of the plurality forwards the harbinger to other nodes along the graph.

5. The method according to claim 4 wherein each computer node requests the update from a node from which it received the harbinger.

6. The method according to claim 1, wherein the update comprises a merger of two or more changes to the file.

7. The method according to claim 1, wherein the computer nodes connected by the graph are subset of a set of computer nodes connected by a network.

8. The method according to claim 7, further comprising:

adding a replica to a computer node of the network when a user attempts to access the replica from the computer node and the computer node does not already have the replica; and

connecting the computer node by the graph.

9. The method according to claim 1, wherein the harbinger is sent only if the update is smaller than a predetermined threshold.

10. The method according to claim 1, wherein a computer node of the plurality delays sending the harbinger by an amount related to the speed of an edge of the graph over which the harbinger is to be sent.

11. The method according to claim 1, further comprising using a combination of version vectors and a last-writer-wins rule for conflict resolution.

12. The method according to claim 1, further comprising providing a user with confirmation of update delivery.

13. The method according to claim 1, wherein when a response to a harbinger is not received from a computer node to which the harbinger was sent, the computer node is indicated as unavailable.

14. The method according to claim 1, wherein the harbinger for the update is flooded to the other computer nodes that store the replicas such that at least one of the computer nodes that store the replicas receives the harbinger for the update and a duplicate of the harbinger.

15. The method according to claim 14, wherein when the duplicate of the harbinger is received by one of the computer nodes that store the replicas after having received the update, it does not thereafter request the update.

16. The method according to claim 14, wherein when one of the computer nodes that store the replicas receives the duplicate of the harbinger before having received the update, it sends a request to the sender of the duplicate harbinger to try again later.

17. The method according to claim 14, wherein when each of the computer nodes that store replicas receives the harbinger the receiving computer node forwards the harbinger to another one of the computer nodes and sends the request for the update to the sender of the harbinger.

18. A system for managing replicated files for a wide-area distributed file system, the system comprising a plurality of computer nodes connected by a graph for storing at least three replicas of a file, each replica being located at a corresponding one of the computer nodes and each replica having an indication of its location in the file system, wherein in response to one of the replicas at a first one of the computer nodes is being accessed for performing a write operation thereby making an update to the replica and, the first one of the computer nodes is configured to after the update is made, propagate the update to the other replicas in two phases by sending a harbinger for the update along the graph to the other computer nodes that store the replicas in a first phase, the harbinger being other than the update, and, in response to the harbinger, the first one or the computer nodes is configured to receive a request for the update from one or more of the other computer nodes in a second phase,

wherein the indication for each replica comprises a directory identifier and file name for the replica,

wherein the update comprises a delta that describes a change to a portion of the file, and

wherein the harbinger includes a timestamp corresponding to the update.

19. The system according to claim 18, wherein the timestamp is a first timestamp that represents the state of the replica just before the change in the replica, and the harbinger further includes a second timestamp that represents the state of the replica after the change in the replica.

20. The system according to claim 19, wherein a computer node is configured to apply the update only if a timestamp for the replica at the computer node matches the first timestamp and, otherwise, the computer node is configured to request a full file transfer.

21. The system according to claim 18, wherein in response to receiving a harbinger, a computer node of the plurality is configured to forward the harbinger to other computer nodes along the graph.

22. The system according to claim 21, wherein each computer node is configured to request the update from a computer node from which it received the harbinger.

23. The system according to claim 18, wherein the update comprises a merger of two or more changes to the file.

24. The system according to claim 18, wherein the computer nodes connected by the graph are subset of a set of nodes connected by a network.

25. The system according to claim 24, wherein when a user attempts to access the replica from the computer node of the network that does not already have a replica, the replica is added to the computer node and the computer node is connected by the graph.

26. The system according to claim 18, wherein the harbinger is sent only if the update is smaller than a predetermined threshold.

27. The system according to claim 18, wherein a computer node of the plurality is configured to delay sending the harbinger by an amount related to the speed of an edge of the graph over which the harbinger is to be sent.

28. The system according to claim 18, wherein a combination of version vectors and a last-writer-wins rule is used for conflict resolution.

29. The method according to claim 18, wherein a user is provided with confirmation of update delivery.

30. The method according to claim 18, wherein when a response to a harbinger is not received from a computer node to which the harbinger was sent, the computer node is indicated as unavailable.

31. The system according to claim 18, wherein the harbinger for the update is flooded to the other computer nodes that store the replicas such that at least one of the computer nodes that store the replicas receives the harbinger for the update and a duplicate of the harbinger.

32. The system according to claim 31, wherein when the duplicate of the harbinger is received by one of the computer nodes that store the replicas after having received the update, it does not thereafter request the update.

33. The system according to claim 31, wherein when one of the computer nodes that store the replicas receives the duplicate of the harbinger before having received the update, it sends a request to the sender of the duplicate harbinger to try again later.

34. The system according to claim 31, wherein when each of the computer nodes that store replicas receives the harbinger the receiving computer node forwards the harbinger to another one of the computer nodes and sends the request for the update to the sender of the harbinger.

35. An article of manufacture comprising a machine-readable medium having stored thereon instructions for implementing a method of managing replicated files for a wide-area distributed file system, the method comprising:

storing at least three replicas of a file, each replica being located at a corresponding one of a plurality of computer nodes connected by a graph and each replica having an indication of its location in the file system;

accessing one of the replicas for performing a write operation thereby making an update to the replica; and

after the update is made, propagating the update to the other replicas in two phases by sending a harbinger for the update along the graph to the other computer nodes that store the replicas in a first phase, the harbinger being other than the update, and, in response to the harbinger, receiving a request for the update from one or more of the other computer nodes in a second phase,

wherein the indication for each replica comprises a directory identifier and file name for the replica,

wherein the update comprises a delta that describes a change to a portion of the file, and

wherein the harbinger includes a timestamp corresponding to the update.