Elliptics network is now able to work in a network split setup and system will merge different history logs when node rejoins.
There are 5 different strategies (described from joining node's point of view):
DNET_MERGE_PREFER_NETWORK (0) - discard local changes and prefer version which exists in the network
DNET_MERGE_PREFER_LOCAL (1) - send local transaction history into the network pretending it to be valid one, all changes in the history log, which is stored in the network will be discarded
DNET_MERGE_REMOTE_PLUS_LOCAL_UPDATES(2) - apply all local changes made after the common ancestor commit after full remote log
DNET_MERGE_LOCAL_PLUS_REMOTE_UPDATES (3) - apply all remote changes made after the common ancestor commit after full local log
DNET_MERGE_FAIL (4) - fail if transaction logs do not match
The first two are obvious - we discard either remote or local history in favour of the selected version. All uptadates stored in the discarded log will be lost. The next two versions are also quite simple - we find a common ancestor and then apply the rest of the selected history log on top of the base one. In this case the first part of the merged log will contain either full remote or local history (depending on the selected strategy) and the second part will contain the rest of the other history.
Here is an example. That's how original history looks on both servers:
$ ./example/dnet_hparser -f /tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history
/tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history:
objects: 5, range: 0-0, counting from the most recent (nanoseconds resolution).
2009-06-19 17:57:43.470096000: 32ea6116: flags: 00000000, offset: 2048, size: 2048: -
2009-06-19 17:57:40.814129000: af24ab16: flags: 00000000, offset: 8192, size: 4096: -
2009-06-19 17:57:40.656900000: 0054b454: flags: 00000000, offset: 4096, size: 4096: -
2009-06-19 17:57:40.503311000: 6cdd3cb9: flags: 00000000, offset: 0, size: 4096: -
2009-06-19 17:57:40.540129000: 6cdd3cb9: flags: 00000000, offset: 0, size: 12288: -
$ ./example/dnet_hparser -f /tmp/elliptics-test/root0/ff/ff00000000000000000000000000000000000000.history
/tmp/elliptics-test/root0/ff/ff00000000000000000000000000000000000000.history:
objects: 5, range: 0-0, counting from the most recent (nanoseconds resolution).
2009-06-19 17:57:42.163033000: 51b89998: flags: 00000000, offset: 1024, size: 3072: -
2009-06-19 17:57:40.814129000: af24ab16: flags: 00000000, offset: 8192, size: 4096: -
2009-06-19 17:57:40.656900000: 0054b454: flags: 00000000, offset: 4096, size: 4096: -
2009-06-19 17:57:40.503311000: 6cdd3cb9: flags: 00000000, offset: 0, size: 4096: -
2009-06-19 17:57:40.540129000: 6cdd3cb9: flags: 00000000, offset: 0, size: 12288: -
Notice that coloured lines (also italic) are different and should be merged. That's how this will look after one of the merge strategies applied:
$ ./example/dnet_hparser -f /tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history
/tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history:
objects: 6, range: 0-0, counting from the most recent (nanoseconds resolution).
2009-06-19 17:57:43.470096000: 32ea6116: flags: 00000000, offset: 2048, size: 2048: -
2009-06-19 17:57:42.163033000: 51b89998: flags: 00000000, offset: 1024, size: 3072: -
2009-06-19 17:57:40.814129000: af24ab16: flags: 00000000, offset: 8192, size: 4096: -
2009-06-19 17:57:40.656900000: 0054b454: flags: 00000000, offset: 4096, size: 4096: -
2009-06-19 17:57:40.503311000: 6cdd3cb9: flags: 00000000, offset: 0, size: 4096: -
2009-06-19 17:57:40.540129000: 6cdd3cb9: flags: 00000000, offset: 0, size: 12288: -
or
$ ./example/dnet_hparser -f /tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history
/tmp/elliptics-test/root1/ff/ff00000000000000000000000000000000000000.history:
objects: 6, range: 0-0, counting from the most recent (nanoseconds resolution).
2009-06-19 17:57:42.163033000: 51b89998: flags: 00000000, offset: 1024, size: 3072: -
2009-06-19 17:57:43.470096000: 32ea6116: flags: 00000000, offset: 2048, size: 2048: -
2009-06-19 17:57:40.814129000: af24ab16: flags: 00000000, offset: 8192, size: 4096: -
2009-06-19 17:57:40.656900000: 0054b454: flags: 00000000, offset: 4096, size: 4096: -
2009-06-19 17:57:40.503311000: 6cdd3cb9: flags: 00000000, offset: 0, size: 4096: -
2009-06-19 17:57:40.540129000: 6cdd3cb9: flags: 00000000, offset: 0, size: 12288: -
The same history will be placed both on local and remote nodes.
The last merge strategy - DNET_MERGE_FAIL (4) will fail with the following lines in the log:
2009-06-19 18:03:27.354246 2: ff000000: histories do not match and fail strategy was selected.
2009-06-19 18:03:27.354485 8: ff000000: failed to merge histories, err: -22.
Automatic test for this functionality (written in bash) is comparable in size with the feature itself.
There are only two issues left to implement in the elliptics network to be considered complete.
One of them is a known problem when joining node does not advertise objects it stores which are outside of the specified range, while it should merge them into the network. Although solution exists, it was not yet tested in this particular case - it is exactly the same as syncing failed range to the neighbour node.
Second problem is unlink support - objects have to maintain reference counter for the finer-grained deletion. Since transaction with the same content ends up in the same object thus performing automatic data deduplication, we can not simply delete it if it is referenced by two or more objects outside. Reference counting allows to remove object only when it is not referenced by any other object. Given that each low-level transaction (i.e. that one which contains some data and not a history update) has a history of the objects it is referenced from, deletion should not be a major problem.
After those tasks are finished I consider project as completed and it will be moved into bug fixing mode. To date I do not see any other features needed to be implemented in the core library (but I do remember about PAXOS-based locking for the backed up histories).
So plan to have a small rest after it and work on regext state machine implementation, LR grammatics and knowledge extraction. A small and rather simple AI bot should be developed for some mail lists this year, and I expect a lot of fun working with it.
In a week or so I will start porting POHMELFS to the elliptics network.
Recent comments
12 hours 49 min ago
1 day 21 hours ago
1 day 22 hours ago
1 day 22 hours ago
1 day 22 hours ago
1 day 23 hours ago
1 day 23 hours ago
1 day 23 hours ago
2 days 15 hours ago
2 days 16 hours ago