basho/riak_dt — pull request #93 by russelldb (2014-05-14 13:14:58+00:00)
Title: Reset-remove semantic on Map

With a shared causal context for the map and the crdts it embeds, removing a field, and then re-adding it has the effect of removing all the additions to that field when merging with a concurrent update to the field. For example:

Add 'X' to set in field F at A
Merge with B
Add 'Y' to set in field F at B
remove field F at A
Add 'Z' to field F at A
merge A and B

The set contains only 'Y' and 'Z', since the remove of the field at A containing 'X' constitutes a remove of 'X'.

However, if the field was _not_ re-added by A the semantic was different, and the result would contain 'X, Y, Z'. This seemed counter-intuitive and confusing. These changes add a temporary tombstone to present fields, so that the removal of a field effects a removal of all dots seen by the field at removal time.

One intutuitive way to think of it as like an offline sync of a file system like Dropbox. With this semantic, removing a directory on one machine, and adding a file to that directory on another, merges to the directory being present, with only the added file in it.

There is some oddness with counters, though.

I added a new counter type, `riak_dt_emcntr` (see it's docs for more details) that stores a `dot` as latast event against each actors increments and decrements. This is so a field removal can reset the counter value. However, we don't store a dot per increment (that would be crazy ineffecient). Counters work will in this scenario

A increments counter at field F by 10
B merges A
A removes field F
B increments counter at field F by 5
A and B merge
Counter is at 5 (A's dot for the increment is dropped)

However there is an anomoly

A increments counter at field F by 10
B merges A
A increments counter by 5
B removes field F
A and B merge

Now, technically, A's first increment should be dropped and only the second stand, but that does not happen, as we don't keep a dot per increment. This, too, can be spun in the filesystem sense. If you updated a file and concurrently removed it, you wouldn't expect only the diff to survive, but the whole file.

Personally I'm happy enough with the semantic, to enable reset-remove on counters requires a dot per increment (a counter as set of increments) and that is not worth the overhead.