Replication and replica management in a wide area file system

• US 20040111390A1
• Filed: 12/09/2002
• Published: 06/10/2004
• 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
• Granted Patent: US 7,739,240 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• 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 a wide-area distributed file system, the method comprising:

constructing and maintaining a consistent hierarchical namespace in a wide-area distributed file system, where individual files and directories are replicated in the system.

2. The method of claim 1, further comprising:

using a combination of version vectors and a last-writer-wins rule for conflict resolution.

3. The method of claim 1, further comprising:

acknowledging, by a replica, a harbinger after all graph neighbors have timed out or have acknowledge the harbinger from the replica.

4. The method of claim 3, wherein an update is propagated along an edge of the graph.

5. An apparatus for managing a wide-area distributed file system, the apparatus comprising:

a node configured to construct and maintain a consistent hierarchical namespace in a wide-area distributed file system, where individual files and directories are replicated in the system.

6. The apparatus of claim 5, wherein the node is configured to use a combination of version vectors and a last-writer-wins rule for conflict resolution.

7. The apparatus of claim 5, wherein a replica is configured to acknowledge a harbinger after all graph neighbors have timed out or have acknowledge the harbinger from the replica.

8. The apparatus of claim 7, wherein an update is propagated along an edge of the graph.

9. A method of updating replicas in a wide-area distributed file system, the method comprising:

propagating an update along an edge of the graph.

10. The method of claim 9, further comprising:

propagating an update to a replica; and

propagating the update to neighboring replicas of the replica.

11. The method of claim 10, further comprising:

whenever a portion of a file is changed, propagating a delta that indicates the change in the portion of the file.

12. The method of claim 11, wherein a delta carries an old timestamp that represents the state of the replica just before a change in the replica and a new timestamp that shows the state of the replica after the change in the replica.

13. The method of claim 11, further comprising:

using a two-phase protocol to propagate an update that exceeds a certain size, wherein the first phase comprises flooding a harbinger along graph edges and the second phase comprises sending the update when the update is requested by another node.

14. The method of claim 11, further comprising:

before sending a harbinger over a graph edge, dynamically building a spanning tree with a shape closely matching a physical network topology; and

sending an update along edges of the spanning tree of the physical network topology.

15. An apparatus for updating replicas in a wide-area distributed file system, the apparatus comprising:

a node configured to propagate an update along an edge of the graph.

16. The apparatus of claim 15, wherein a node in the file system is configured to propagate an update to a replica and propagate the update to neighboring replicas of the replica.

17. The apparatus of claim 15, wherein a node in the file system is configured to propagate a delta that indicates the change in the portion of a file whenever a portion of the file is changed.

18. The apparatus of claim 17, wherein a delta carries an old timestamp that represents the state of the replica just before a change in the replica and a new timestamp that shows the state of the replica after the change in the replica.

19. The apparatus of claim 15, wherein a node in the file system is configured to use a two-phase protocol to propagate an update that exceeds a certain size, wherein the first phase comprises flooding a harbinger along graph edges and the second phase comprises sending the update when the update is requested by another node.

20. The apparatus of claim 15, wherein a node in the file system is configured for the following:

before sending a harbinger over a graph edge, dynamically building a spanning tree with a shape closely matching a physical network topology; and

sending an update along edges of the spanning tree of the physical network topology.

21. A method for managing a wide-area distributed file system, the method comprising:

achieving eventual data and metadata consistency in a wide-area distributed file system, in a fast and efficient way.

22. The method of claim 21, wherein the data comprises file contents.

23. The method of claim 21, wherein the metadata comprises directory contents.

24. An apparatus for managing a wide-area distributed file system, the apparatus comprising:

a node capable of achieving eventual data and metadata consistency in a wide-area distributed file system, in a fast and efficient way.

25. The apparatus of claim 24, wherein the data comprises file contents.

26. The apparatus of claim 24, wherein the metadata comprises directory contents.

27. A method of failure recovery in a wide-area distributed file system, the method comprising:

in response to a temporary failure by a node, resending logged updates upon reboot of the node or after detection of a recovery of the node; and

in response to a permanent failure by a node, cleaning all data structures associated with the failed node so that the system runs as if the node had not existed and creating a replica on a live node.

28. An apparatus for failure recovery in a wide-area distributed file system, the apparatus comprising:

a node configured to resend logged updates upon reboot of the node or after detection of a recovery of the node, in response to a temporary failure by the node; and

the node configured to clean all data structures associated with the failed node so that the system runs as if the node had not existed and to create a replica on a live node, in response to a permanent failure by a node.

29. An article of manufacture, comprising:

a machine-readable medium having stored thereon instructions to;

construct and maintain a consistent hierarchical namespace in a wide-area distributed file system, where individual files and directories are replicated in the system.

30. An article of manufacture, comprising:

a machine-readable medium having stored thereon instructions to;

propagate an update along an edge of the graph.

31. An article of manufacture, comprising:

a machine-readable medium having stored thereon instructions to;

achieve eventual data and metadata consistency in a wide-area distributed file system.

32. An article of manufacture, comprising:

a machine-readable medium having stored thereon instructions to;

in response to a temporary failure by a node, resend logged updates upon reboot of the node or after detection of a recovery of the node; and

in response to a permanent failure by a node, clean all data structures associated with the failed node so that the system runs as if the node had not existed and creating a replica on a live node.