Data replication based upon a non-destructive data model

• US 7,024,429 B2
• Filed: 01/31/2002
• Issued: 04/04/2006
• Est. Priority Date: 01/31/2002
• Status: Active Grant

• Current Assignee: Proofpoint Incorporated
• Original Assignee: NextPage, Inc. (Proofpoint Incorporated)
• Inventors: Ngo, J. Thomas, Barnett, Russell Clark
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Lu, Kuen S.
• Application Number:
  US10/059,233
• Publication Number:
  US 20030145020A1
• Time in Patent Office: 1,524 Days
• Field of Search: 707/201, 707/203, 707/204, 707/10, 711/165, 345/744, 705/8
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/184 implemented as replicated file system
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

In a data-replication system, multi-way synchronization of copies of the data at different devices is achieved by employing a non-destructive data model. In this model, each replicated data object is represented by a revision graph, and every operation that is performed on a data object, e.g. a revision of data content or deletion of the object, is represented by adding a node to a revision graph at the device where the change is made. Synchronization between multiple devices is achieved by applying a graph union operator. Since the union operator is commutative and associative, it avoids the limitations normally associated with the order in which updates occur. A synchronization enforcement mechanism restricts the situations in which the nodes of a graph can be deleted, to thereby ensure integrity of the data throughout its useful life cycle.

Claims

1. A method for replicating data at multiple devices, comprising the steps of:

representing the history of a data object at each of said devices by means of a graph of atoms in a store, where said graph includes at least one parent atom of a first type that contains information pertaining to an operation performed on the data object and at least two descendant atoms of said first type;

adding an atom of said first type to the atom graph in the store at a given device when an operation is performed on the data object at said given device;

updating the history of the data object at another device by transmitting to said other device at least one atom that is present in the store at said given device and absent from the store at said other device and forming the mathematical union of the atom graphs at said given device and said other device, such that said atom graph can contain at least one parent atom having at least two direct descendant atoms that represent different versions of said data object; and

at each of said devices, selectively designating either one of said different versions to be viewed as the representative version of said data object at that device.

2. The method of claim 1 wherein said atom graphs further include a second type of atom that contains information pertaining to an attribute of the data object.

3. The method of claim 2 wherein said attribute comprises access rights for the data object.

4. The method of claim 2 wherein said attribute is an approval marking for the data object.

5. The method of claim 4 wherein said approval marking is a digital signature for the data object.

6. The method of claim 1 wherein the operation on the data object comprises a change in the contents of the data object.

7. The method of claim 6 wherein the operation on the data object includes deletion of the data object.

8. The method of claim 7 wherein said atom graph is directed, acyclic and connected, such that each atom associated with an operation on the data object is connected to at least one atom associated with a version of the object that existed prior to said operation.

9. The method of claim 1 wherein the atom graph in the store at a given device has a cursor that identifies one atom in the graph that is associated with the designated version of the data object at that device.

10. The method of claim 9 wherein the cursor determines a view of the object that is presented by an application at said device.

11. The method of claim 10 wherein different views of the same object are presented by applications at different respective devices.

12. The method of claim 10 further including the step of generating metadata pertaining to a data object, and assigning said cursor to an atom by applying business rules to said metadata.

13. The method of claim 12, wherein said metadata is generated at a store when an atom is created at that store.

14. The method of claim 13, further including the step of transmitting the metadata created at a store to other stores during said updating step.

15. The method of claim 14, wherein a given store applies the business rules to metadata generated at that store and to metadata received from other stores.

16. The method of claim 12 wherein said metadata includes a time stamp for the creation of an atom, and said business rules assign the cursor on a time-related basis.

17. The method of claim 12 wherein said metadata includes an indication of a person who was responsible for the creation of an atom, and said business rules assign the cursor on a trust-related basis.

18. The method of claim 12 wherein said business rules assign the cursor on an application-specific basis.

19. The method of claim 1 wherein the atom graph in the store at a given device has plural cursors which identify at least two different respective atoms in the graph as a result of an update, and further including the step of presenting a view of each version of the data object represented by the respective identified atoms for conflict resolution.

20. The method of claim 1 further including the steps of generating metadata pertaining to a data object, and applying business rules to said metadata at a store to designate a view of the object that is presented by an application.

21. The method of claim 20, wherein said metadata is generated at a store when an atom is created at that store.

22. The method of claim 21, further including the step of transmitting the metadata created at a store to other stores during said updating step.

23. The method of claim 22, wherein a given store applies the business rules to metadata generated at that store and to metadata received from other stores.

24. The method of claim 20 wherein said metadata includes a time stamp for the creation of an atom, and said business rules determine the designated view on a time-related basis.

25. The method of claim 20 wherein said metadata includes an indication of a person who was responsible for the creation of an atom, and said business rules determine the designated view on a trust-related basis.

26. The method of claim 20 wherein said business rules determine the designated view on an application-specific basis.

27. The method of claim 1 further including the step of assigning an atom in a store to a bundle for transmission to another device during an update step.

28. The method of claim 27 wherein plural atoms are assigned to a single bundle.

29. The method of claim 27 wherein the contents of an atom become fixed when it is assigned to a bundle, and subsequent operations on the data object result in the creation of a new atom.

30. The method of claim 27 wherein a bundle is automatically created in a store in advance of a transmission containing said bundle.

31. The method of claim 27 wherein a bundle is created in a store in response to a request for a transmission from another store.

32. The method of claim 27 wherein one store sends a list of its bundles to another store during said updating step.

33. The method of claim 32 wherein the bundles in said list are run-length encoded.

34. The method of claim 27 wherein a bundle is comprised of plural sheaves that form individual units for transmission.

35. The method of claim 34 wherein one store sends a list of its sheaves to another store during said updating step.

36. The method of claim 27 further including the steps of assigning different levels of volatility to stores at different respective devices and selectively deleting atoms in a bundle from a given store in accordance with its assigned level of volatility.

37. The method of claim 36 further including the steps of associating a volatility flag with each bundle, and setting the flag to identify the least volatile level of store in which a copy of the bundle is known to be stored.

38. The method of claim 37 wherein said volatility flag is separately set at each store, and further including the step of resetting the flag as appropriate in response to data received during said updating step.

39. The method of claim 37 wherein one of said assigned levels is classified as volatile and another assigned level is classified as non-volatile, and wherein a bundle is identified for deletion from a volatile store when its volatility flag indicates that it has been stored in a non-volatile store.

40. The method of claim 39 wherein an atom comprises a content component and an identity component, and wherein the content component of the atom is deleted from a volatile store after it has been identified for deletion while its identity component is retained in the store.

41. The method of claim 40 wherein a bundle includes a completeness flag, and further including the step of setting said completeness flag to indicate whether the atoms of a bundle include their content component.

42. The method of claim 39 wherein an atom comprises a content component and an identity component, and wherein both components are deleted from a volatile store after the atom has been identified for deletion.

43. The method of claim 39 wherein another assigned level is classified as final, to which an atom is transmitted during an end-of-life process.

44. The method of claim 43 wherein an atom comprises a content component and an identity component, and wherein both components are deleted from the volatile and non-volatile stores after the atom has been transmitted to a final store.

45. The method of claim 43 wherein an end-of-life process includes the steps of broadcasting the final store'"'"'s inventory and a notification that the end-of-life process is taking place.

46. The method of claim 45 wherein, in response to receipt of said broadcast, the stores other than said first store perform an updating operation with said final store.

47. The method of claim 46, further including the step of setting the volatility flags in said other stores to indicate that a bundle has been updated to the final store.

48. The method of claim 47 further including the step of deleting the bundles in said other stores whose volatility flags have been set to a final value.

49. The method of claim 37 wherein said updating step comprises the transmission of information pertaining to atoms from a sender store to a receiver store.

50. The method of claim 49 wherein said information is transmitted by means of a synchronous communications network.

51. The method of claim 49 wherein said information is transmitted by means of a file that is attached to an e-mail message.

52. The method of claim 49 wherein said information is transmitted by means of a file that is stored on a removable medium.

53. The method of claim 49 wherein said information is transmitted with the following steps:

the recipient store requests an update, and sends a first inventory of the bundles that it currently contains;

the recipient store sends a list of the volatility flags for its bundles;

the sender store sends a second inventory of the bundles that it has but the recipient does not have;

the sender sends a list of volatility flags for its bundles; and

the sender store transmits the bundles in said second inventory.

54. The method of claim 53 further including the step wherein the recipient store responds with a list that represents the bundles that are to be received from the sender, after the sender store sends an inventory of the bundles that it has but the recipient does not have.

55. The method of claim 53 further including the step wherein the recipient store responds with a list of the bundles that it received and added to its atom graphs.

56. The method of claim 49 wherein said information is transmitted with the following steps:

the sender store caches a copy of a recipient'"'"'s bundle inventory;

the sender store transmits a bundle inventory showing what it has and what it assumes the recipient store does not have, based upon its cached copy of the recipient'"'"'s bundle inventory;

the sender store transmits its bundle volatility list; and

the sender store transmits the bundles.

57. The method of claim 56 further including the step in which the sender store transmits an inventory of its bundles, for future reference.

58. The method of claim 56 further including the step in which a recipient store broadcasts an inventory of its bundles prior to said steps performed by the sender store.

59. The method of claim 36, wherein at least one store does not have an assigned level of volatility.

60. The method of claim 59 wherein said one store is capable of receiving data objects from other stores, but is inhibited from replicating data objects to stores that have assigned levels of volatility.

61. The method of claim 27 wherein said updating step comprises the transmission of information pertaining to atoms from a sender store to a receiver store.

62. The method of claim 61 wherein said information is transmitted with the following steps:

the recipient store requests an update, and sends a first inventory of the bundles that it currently contains;

the sender store sends a second inventory of the bundles that it has but the recipient does not have; and

the sender store transmits the bundles in said second inventory.

63. The method of claim 62 further including the step wherein the recipient store responds with a list that represents the bundles that are to be received from the sender, after the sender store sends an inventory of the bundles that it has but the recipient does not have.

64. The method of claim 62 further including the step wherein the recipient store responds with a list of the bundles that it received and added to its atom graphs.

65. The method of claim 61 wherein said information is transmitted with the following steps:

the sender store caches a copy of a recipient'"'"'s bundle inventory;

the sender store transmits a bundle inventory showing what it has and what it assumes the recipient store does not have, based upon its cached copy of the recipient'"'"'s bundle inventory; and

the sender store transmits the bundles.

66. The method of claim 65 further including the step in which the sender store transmits an inventory of its bundles, for future reference.

67. The method of claim 65 further including the step in which a recipient store broadcasts an inventory of its bundles prior to said steps performed by the sender store.

68. The method of claim 1 wherein said updating step comprises the transmission of information pertaining to atoms from a sender store to a receiver store.

69. The method of claim 68 wherein said information is transmitted by means of a synchronous communications network.

70. The method of claim 68 wherein said information is transmitted by means of a file that is attached to an e-mail message.

71. The method of claim 68 wherein said information is transmitted by means of a file that is stored on a removable medium.

72. The method of claim 68 wherein said information is transmitted with the following steps:

the recipient store requests an update, and sends a first inventory of the atoms that it currently contains;

the sender store sends a second inventory of the atoms that it has but the recipient does not have; and

the sender store transmits the atoms in said second inventory.

73. The method of claim 72 further including the step wherein the recipient store responds with a list that represents the atoms that are to be received from the sender, after the sender store sends an inventory of the atoms that it has but the recipient does not have.

74. The method of claim 72 further including the step wherein the recipient store responds with a list of the atoms that it received and added to its atom graphs.

75. The method of claim 68 wherein said information is transmitted with the following steps:

the sender store caches a copy of a recipient'"'"'s atom inventory;

the sender store transmits an atom inventory showing what it has and what it assumes the recipient store does not have, based upon its cached copy of the recipient'"'"'s atom inventory; and

the sender store transmits the atoms.

76. The method of claim 75 further including the step in which the sender store transmits an inventory of its atoms, for future reference.

77. The method of claim 75 further including the step in which a recipient store broadcasts an inventory of its atoms prior to said steps performed by the sender store.

78. The method of claim 1 further including the step of encrypting information pertaining to an atom using a public-private key pair.

79. The method of claim 78 wherein said information is encrypted on a per-atom basis.

80. The method of claim 78 wherein the private key of said pair is held by only one person.

81. The method of claim 78 wherein the private key of said pair is held by a plurality of people.

82. The method of claim 78, further including the steps of storing the public key in the store in association with the atom graph, and providing said public key to said other device during said update step.

83. The method of claim 78 wherein said atom graph includes a validation atom that validates a revision to the public key and is digitally signed with a private key.

84. The method of claim 78 wherein said atom graph includes a revocation atom that revokes the public key and is digitally signed with a private key.

85. The method of claim 1 wherein each of said stores is associated with a space that pertains to a set of information, and different ones of said stores are respectively associated with different spaces.

86. The method of claim 85 wherein a data object is a member of plural spaces.

87. The method of claim 86 further including the step of detecting the addition of an atom to the atom graph for said data object, and designating said added atom for transmission to stores associated with all of the spaces of which said data object is a member.

88. The method of claim 1 wherein one store is associated with a hub device, and said updating step is carried out unidirectionally from the store at said hub device to all of the other stores.

89. The method of claim 88 further including the step of assigning a cursor to an atom in the graph at each store to identify a current version of the data object.

90. The method of claim 89 wherein the cursor is assigned at said hub device, and said assignment is transmitted to said other stores from the hub device during said updating step.

91. The method of claim 89 further including the step of notifying users at devices other than said hub device that a revision has been made to a data object, and enabling said users to assign the cursor at said other devices.

92. The method of claim 88 wherein said updating step is performed by pushing information pertaining to said atoms from said hub device to said other stores.

93. The method of claim 88 wherein said updating step is initiated by sending a request from said other stores to said hub device.

94. The method of claim 88 wherein a first updating step is performed unidirectionally from said hub device to a first set of intermediate stores, and a second updating step is performed unidirectionally from said intermediate stores to other stores.

95. The method of claim 1 wherein one store is associated with a hub device, and said updating step is carried out bidirectionally between the store at said hub device and all of the other stores.

96. The method of claim 95 wherein the atom graph at each store has a cursor that identifies an atom pertaining to a current version of the data object.

97. The method of claim 96 wherein the atom identified by the cursor can only be changed at said hub device, and said change is transmitted to said other stores from the hub device during an updating step.

98. The method of claim 1 wherein stores are present at a multiplicity of devices, and a store at any device is capable of performing said updating step with a store at any other device.

99. The method of claim 98 wherein the performance of said updating step between a first store and a second stores results in a conflict, and further including the steps of:

a) performing an update between a third store and one of said first and second stores;

b) detecting and resolving said conflict at said third store; and

c) performing an update between said third store and each of said first and second stores, to thereby resolve said conflict at said first and second stores.

100. The method of claim 99 wherein the update of step (c) is carried out directly between said third store and at least one of said first and second stores.

101. The method of claim 99 wherein the update of step (c) between said third store and at least one of said first and second stores is carried out indirectly by way of an intermediary store.

102. The method of claim 1 wherein each of said parent atom and said descendant atoms contains a complete set of data for the version of the data object to which the atom pertains.

103. The method of claim 1 wherein a parent atom contains a complete set of data for the version of the data object to which the atom pertains, and descendant atoms contain information regarding differences between said complete set and the respective versions of the data object to which they pertain.

104. The method of claim 1 wherein a descendant atom contains a complete set of data for the version of the data object to which the atom pertains, and a parent atom contains information regarding differences between said complete set and the version of the data object to which said parent atom pertains.

105. The method of claim 1, wherein said data object is a document.

106. A method for replicating data at multiple devices, comprising the steps of:

representing the history of a data object at each of first and second devices by means of a graph of atoms, where said atoms contain information pertaining to changes in the content of the data object, and said graph contains at least one parent atom having at least two descendant atoms;

adding an atom to the atom graph at said first device when a change is made to the data object at said first device;

updating the history of the data object at a second device by forming a new graph at said second device that is a strict superset of the of the atom graph that existed at said second device prior to said updating step, and a non-strict subset of the union of the atom graphs that existed at said first and second devices prior to said updating step, such that said atom graph can contain at least one parent atom having at least two direct descendant atoms that represent different versions of said data object; and

at each of said devices, selectively designating either one of said different versions to be viewed as the representative version of said data object at that device.

107. The method of claim 106 wherein said updating step comprises forming the mathematical union of the atom graphs that existed at said first and second devices prior to said updating step.

108. The method of claim 106 wherein said two descendant atoms contain information that pertains to different respective versions of said data object.

109. The method of claim 106, wherein said data object is a document.

110. A system for replicating data at multiple devices, comprising:

a store at each of said devices, each of said stores containing replicas of a data object;

a manager associated with each store that detects and records operations performed on the data object in the form of a graph of atoms containing at least one parent atom having at least two descendant atoms, and that updates the history of the data object by receiving atoms that are contained in a graph at one store and adding said atoms to the graph in another store by forming the mathematical union of the atom graphs at said two stores, such that said atom graph can contain at least one parent atom having at least two direct descendant atoms that represent different versions of said data object; and

means for selectively designating either one of said different versions at a given store to be viewed as the representative version of said data object at the device associated with that store.

111. The system of claim 110 wherein the manager associated with one store communicates with a manager associated with another store to perform said updates.

112. The system of claim 111 wherein said communications take place via a synchronous network.

113. The system of claim 111 wherein said communications occur asynchronously.

114. The system of claim 111 wherein said communications occur via e-mail.

115. The system of claim 111 wherein said communication occur via files on a removable medium.

116. The system of claim 111 wherein said managers assigns an atom in a store to a bundle for transmission to another store.

117. The system of claim 116 wherein said manager assigns plural atoms to a single bundle.

118. The system of claim 116 wherein said manager can modify the contents of an atom before it is assigned to bundle, and thereafter creates a new atom when an operation is performed on the data object.

119. The system of claim 110, wherein said data object is a document.