opencoweb/coweb — Issue #149: OT support for maintaining the state of a complex data object represented by an ordered N-ry tree 
Author: vinomaster
Created: 2011-12-15 12:44:24+00:00
State: open
Labels: Docs, Feature, Java, JavaScript, Performance

Operation Transforms can be complex and are the subject of a lot of on going research in academia. Here we have an interesting problem of maintaining the state of an N-ry tree where the order of the child nodes is important.

The key to this is maintaining 2 data structures. This is done in order to preserve order. Assuming the following basic JSON object to represent our example complex data object:

Person : {
"uid" : 1,
"firstname" : "Happy",
"lastname" : "Slappy",
"Address" : [{
"uid" , 2,
"city", "",
"state, "",
"zip", "",
"geo" : {
"uid" : 3,
"long" : ""
}
}, {
"uid" , 4,
"city", "",
"state, "",
"zip", "",
"geo" : {
"uid" : 5,
"long" : "",
"lat" : ""
}
}]
}

Data Structure 1 is responsible for maintaining an objects properties / leaf nodes. Notice how this is a flat structure and does not contain any children.

structure : [
"1" : {
firstname : "Happy"
lastname " "Slappy"
},
"2" : {
"city" : "",
"state: "",
"zip": ""
},
"3" : {
"long" : "",
"lat" : ""
},
"4": {
"city" :"",
"state" : "",
"zip" : ""
}
"5":{
"long" : "",
"lat": ""
}
]

Data Structure 2 is responsible for the structure of the tree. We need to represent the root node explicitly so we know where to begin our tree traversal. They key is the UID of the node and it's value is an object containing a reference to it's parent node and an array of it's child nodes.

structure : [
root: [1],
"1" : {parent : root, [2, 4]},
"2" : {parent : 1, [3]},
"3" : {parent : 2, []},
"4" : {parent : 1, [5]},
"5" : {parent: 4, []}
]

For OT, each UID has a topic. The topics are NOT hierarchal. Inserts and deletes are performed on the parent node topic utilizing position to maintain order. For example, let's insert a new address on person 1.

Insert: topic=change.1-structure, position: 2, value = {new address}

We specified position 2 which would be the end of the address list, So we create a new UID for the address object, "6", and insert the object into our first structure. We then add "6" to position 2 of 1's child list in the second structure.

Updates are done on the actual node itself and are only performed on the properties. For example, let's change the city for address 2.

Update: topic=change.2-update, position: 0, value = {city: "Foo"}

Here we only need to update the value of city in our first structure as the structure of the tree does not change with updates.

We have to distinguish inserting / deleting a child node from updating the values of a parent, therefore inserts and deletes will have "structure" tagged to the end of the topic name. Updates will have "update" tagged to the end of the topic name. For example if an insert is performed on change.nodeA at the same time an update is occuring on a property of nodeA (change.nodeA) then the op engine will treat these as a collision. We don't want this to happen as updating an objects property should have no effect on inserting or deleting one of it's children.