Data replication based upon a non-destructive data model
First Claim
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
119 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105)
-
-
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. - View Dependent Claims (107, 108, 109)
-
-
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. - View Dependent Claims (111, 112, 113, 114, 115, 116, 117, 118, 119)
-
Specification