Advanced merge conflict resolver in the elliptics network
I’ve almost recovered from being a weekend mosquito dinner so returned back to the interesting problem in the elliptics network: merge conflict resolve.
In the existing systems with the global index (like git) this problem is rather simple – index is always different, so system can find a common parent transaction and merge subsequent updates. There may be conflicts of course, but those conflicts can not be resolved generally without human intervention.
In the elliptics network there is no global index, instead each object has own history, which only contained applied transaction IDs, so it was possible that log will contain the same entries (like when updating the same block with the same data multiple times). Because of performance reasons each update does not end up generating a checksum of the whole object (which is not the case for git, where files are on the local machine and should not be fetched from the bunch of remote nodes, when some of them may be unaccessible). Since elliptics network does not have a global index with the always unique entries it is not possible to find a common parent for the two logs or this can be done with errors.
For example we can find two possible merge solutions for the diagram below:
1 2 3 4 5 1 2 3 1 2 3 4 5 and 1 2 3 4 5 1 2 3 1 2 3 4 5 -----------------------------------> t
Where horizontal axis is a time and numbers are transaction IDs. To solve this merge conflict we need to know exactly how to differentiate transactions when their IDs are the same, and thus to find which path to take on the above diagram.
To solve this problem, I introduced a transction timestamp, which says when given data was sent into the network. It does not require a precise clocks on all machines in the network, since timestamp is only needed to be a unique number in pair with the given transaction ID, system does not use it to merge transactions based on its generation time.
I selected time since it is quite monotonically increasing number, while it could be a random cookie. Another useful usage of the timestamp is log truncation. Well, truncation is not a good definition though, since we cut off the log from the beginning dropping some old transactions. This is not implemented yet, while 5 different merge algorithms are:
- prefer network log and drop all local changes in favor of the version stored on the remote node
- prefer local log and overwrite the one stored in the network discarding all changes there
- apply local changes after common ancestor on top of remote log
- apply remote changes after common ancestor on top of local log
- do nothing and return error when remote and local transaction logs do not match
The first two are rather simple cases, while the third and the fourth (although being quite the same) are a bit more complex. They can destroy data consistency since transactions are applied on top of existing local or remote logs potentially overwriting data written there by another client. Although it is always possible to recreate object some time in its past, the latest version may be changed the way users do not expect.
Since it is potentially not a text file, usuall offset/size check (like in
diff) is not enough (consider some binary tree updates). So there is the last case when nothing is done and it is up to administrator to decide which version is correct.
There should be a fair amount of testing of this functionality before new release will see the light, as well as other tasty features implemented, but core functionality is already there.