Namespace consistency for a wide-area file system

• US 20040172421A1
• Filed: 12/01/2003
• Published: 09/02/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 8,311,980 B2
• Time in Patent Office: Days
• US Class Current: 707/200
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 16/184 implemented as replicated file system

Abstract

The invention is a system for and a method of maintaining namespace consistency in a wide-area file system. In one embodiment, a wide-area file system has a plurality of replicas for a file. Each replica of a file and parent directories for the file are at a node. An update to a replica of the file is propagated to other replicas of the file. In response to receiving a propagated update to a replica at a node, the replica for the file at the node is updated. A directory operation (e.g., rename, link or unlink) may affect a backpointer for a replica. When a backpointer for a replica at a node is not consistent with the parent directories for the replica at the node, the the parent directories are modified to be consistent with the backpointer. A modification may be performed at a node while an earlier inconsistent modification may be ignored. As a result, consistency is maintained among the replicas.

Claims

1. A method for a wide-area file system, including a plurality of replicas for a file, wherein each replica of the file and parent directories for the file are at each of a plurality of nodes, the method comprising:

propagating an update to a replica of the file to other replicas of the file; and

in response receiving a propagated update to a replica at a node, updating the replica for the file at the node.

2. The method according to claim 1, wherein each replica has a backpointer including an identification of a parent directory for the file and a name of the file in the parent directory.

3. The method according to claim 2, wherein the parent directories are modified when the backpointer for a replica at a node is not consistent with the parent directories for the replica at the node.

4. The method according to claim 3, wherein modifying the parent directories occurs only after a delay.

5. The method according to claim 3, wherein multiple modifications to the parent directories at the node are performed according to an order in which corresponding updates occur.

6. The method according to claim 3, wherein a modification is performed at the node and an earlier inconsistent modification is ignored.

7. The method according to claim 2, wherein a directory operation affects the backpointer for the file.

8. The method according to claim 7, wherein the directory operation is selected from a group consisting of rename, link and unlink.

9. The method according to claim 8, wherein when the backpointer for a replica at a node is not consistent with the parent directories for the replica at the node, further comprising modifying the parent directories to be consistent with the backpointer.

10. The method according to claim 1, wherein the replicas include replicas of a first type and of a second type wherein locations of replicas of the first type are registered in a parent directory for a file.

11. The method according to claim 1, wherein the replicas include replicas of a first type and of a second type and wherein in response to a user accessing a file at a node, the method further comprises steps of replicating the parent directory for the file at the node and forming of replica of the second type at the node.

12. The method according to claim 11, wherein a minimum number of replicas of the first type are maintained according to a minimum replication factor for the corresponding file.

13. The method according to claim 1, wherein a replica is deleted by marking the replica as invalid.

14. The method according to claim 13, wherein said marking the replica as invalid comprises removing the backpointer for the replica.

15. The method according to claim 13, further comprising periodically removing replicas marked as invalid.

16. A method for a wide-area file system, including a plurality of replicas for a file, and wherein upon access of the file by a user at a node, the method comprises steps of:

replicating parent directories for the file at the node; and

forming a replica of the file at the node wherein the replica includes a backpointer having an identification of a parent directory for the file and a name of the file within the parent directory.

17. The method according to claim 16, further comprising propagating an update to a replica of the file to other replicas of the file.

18. The method according to claim 17, wherein the update is forwarded according to a graph for the file.

19. The method according to claim 17, wherein in response receiving a propagated update to a replica at a node, the node updates parent directories for the file at the node.

20. The method according to claim 17, wherein when a backpointer for a replica at a node is not consistent with parent directories for the replica at the node, the method further comprises modifying the parent directories to be consistent with the backpointer.

21. The method according to claim 20, wherein said modifying is performed only after a delay.

22. The method according to claim 20, wherein multiple modifications to the parent directories at the node are performed according to an order in which corresponding updates occur.

23. The method according to claim 20, wherein a modification is performed at the node and an earlier inconsistent modification is ignored.

24. The method according to claim 17, wherein a directory operation affects the backpointer for the file.

25. The method according to claim 24, wherein the directory operation is selected from a group consisting of rename, link and unlink.

26. The method according to claim 24, wherein when the backpointer for a replica at a node is not consistent with parent directories for the replica at the node, the method further comprises modifying the parent directories to be consistent with the backpointer.

27. The method according to claim 16, wherein a minimum number of replicas for a file are maintained according to a minimum replication factor for the file.

28. The method according to claim 27, wherein links between replicas of a file form a graph for the file and wherein updates to the file are propagated along the graph.

29. The method according to claim 16, wherein a replica is deleted by marking the replica as invalid.

30. The method according to claim 29, wherein said marking the replica as invalid comprises removing the backpointer for the replica.

31. The method according to claim 29, further comprising periodically removing replicas marked as invalid.

32. The method according to claim 16, further comprising locating a parent directory of the file.

33. The method according to claim 32, wherein said replicating the parent directories comprises copying contents of the parent directory located by said locating.

34. The method according to claim 33, wherein said locating and copying are performed recursively, thereby traversing a pathname for the file.

35. The method according to claim 33, wherein said forming the replica of the file comprises a copying contents of a replica of the file located by said locating.

36. A method for a wide-area file system including a first type of file replica and a second type of file replica wherein locations of replicas of the first type are registered in a parent directory for a file, and wherein upon access of a file by a user at a node, the method comprises steps of:

replicating the parent directory for the file at the node; and

forming a replica of the second type at the node wherein the replica of the second type includes a backpointer having an identification of the parent directory for the file and a name of the file within the parent directory.

37. The method according to claim 36, further comprising propagating an update to a replica of the file to other replicas of the file.

38. The method according to claim 37, wherein the update is forwarded according to a graph for the file.

39. The method according to claim 37, wherein in response receiving a propagated update to a replica at a node, the node updates parent directories for the file at the node.

40. The method according to claim 37, wherein when a backpointer for a replica at a node is not consistent with parent directories for the replica at the node, the method further comprises modifying the parent directories to be consistent with the backpointer.

41. The method according to claim 40, wherein said modifying is performed only after a delay.

42. The method according to claim 40, wherein multiple modifications to the parent directories at the node are performed according to an order in which corresponding updates occur.

43. The method according to claim 40, wherein a modification is performed at the node and an earlier inconsistent modification is ignored.

44. The method according to claim 37, wherein a directory operation is performed on the backpointer for the file.

45. The method according to claim 44, wherein the directory operation is selected from the group consisting of rename, link and unlink.

46. The method according to claim 44, wherein when the backpointer for a replica at a node is not consistent with parent directories for the replica at the node, the method further comprises modifying the parent directories to be consistent with the backpointer.

47. The method according to claim 36, wherein a minimum number of replicas of the first type are maintained according to a minimum replication factor for the corresponding file.

48. The method according to claim 47, wherein links between replicas of a file form a graph for the file and wherein updates to the file are propagated along the graph.

49. The method according to claim 36, wherein a replica is deleted by marking the replica as invalid.

50. The method according to claim 49, wherein said marking the replica as invalid comprises removing the backpointer for the replica.

51. The method according to claim 49, further comprising periodically removing replicas marked as invalid.

52. The method according to claim 36, further comprising locating a parent directory of the file.

53. The method according to claim 52, wherein said replicating the parent directories comprises copying contents of the parent directory located by said locating.

54. The method according to claim 53, wherein said locating and copying are performed recursively, thereby traversing a pathname for the file.

55. The method according to claim 53, wherein said forming the replica of the file comprises a copying contents of a replica of the file located by said locating.

56. A system including a plurality of nodes for storing replicas of files wherein for each replica at a node, the node stores parent directories for the file and a backpointer having an identification of a parent directory for the file and wherein updates to replicas of the file are propagated to other replicas of the file.

57. The system according to claim 56, wherein in response to receiving a propagated update to a replica at a node, the node updates the parent directories for the file at the node.

58. The system according to claim 56, wherein when a backpointer for a replica at a node is not consistent with the parent directories for the replica at the node, the node modifies the parent directories to be consistent with the backpointer.

59. The system according to claim 58, wherein the node modifies the parent directories to be consistent with the backpointer only after a delay.

60. The method according to claim 58, wherein multiple modifications to the parent directories at the node are performed according to an order in which corresponding updates occur.

61. The method according to claim 58, wherein a modification is performed at the node and an earlier inconsistent modification is ignored.

62. The method according to claim 56, wherein a directory operation is affects the backpointer for the file.

63. The method according to claim 62, wherein the directory operation is selected from a group consisting of rename, link and unlink.

64. The method according to claim 62, wherein when a backpointer for a replica at a node is not consistent with the parent directories for the replica at the node, the node modifies the parent directories to be consistent with the backpointer.

65. The system according to claim 56, wherein the replicas include replicas of a first type and of a second type wherein locations of replicas of the first type are registered in a parent directory for a file.

66. The system according to claim 56, wherein in response to a user accessing a file at a node, a replica of the file is formed at the node.

67. The method according to claim 56, wherein a replica is deleted by marking the replica as invalid.

68. The method according to claim 67, wherein said marking the replica as invalid comprises removing the backpointer for the replica.

69. The method according to claim 67, further comprising periodically removing replicas marked as invalid.