basho/riak_dt — pull request #82 by russelldb (2014-03-07 19:06:47+00:00)
Title: Fix bugs in Map, Set, and OD Flag

Dear Reviewer,

Let me know if you want me to break this into separate PRs for Map, Set, Flag.

The common theme here is that the merge functions on all three of these types were broken in a similar way. The Set had implementation bugs around common dots. The Flag and Map were broken by design (though the broken design's impl had the same bugs as the Set.)

-------

The Set changes are all about stopping the following bug (or variations on it):

add x to a
add x to b
rep a to c
rem x from a
rep b to a
rem x from b
merge (b,merge(a,c))

'x' should not be in the set, but the logic used to hold that is 'X' was on both sides of the merge it was in the set. Clearly a value can be on both sides of a merge, but actually be removed, the patch fixes that.

-----

The Flag was broken by design. You need more than a vector to track the current value. The result is a lot like the faulty assumption with the set (if both sides are 'true' then the result is 'true') The test that shows this is incorrect is called `disable_test`. The re-write of the Flag is pretty self-explanatory: if there are no `dots` left in the OD Flag's value, it is a `false`, otherwise it is a `true`.

-----

The Map problem is rather more complex. As well has having the other bugs above, there is an issue with merging CRDTs during the merge. Looking at the model we used for testing, it only merges CRDTs to a new value on update. It creates a new event that supersedes past events. The problem with our merge function on the Map was that it created this new value, without an event to provoke it. It mixed seen and unseen changes together. Then, when a remove occurred, the values to be removed where bound up with other values and associativity of the merge was broken. Depending on merge order a value could either be in, or out if it got merged in with some data that _was_ concurrent with a remove. The downside to requiring an update event to merge divergent fields, is that you store the field siblings _until_ such an event. So larger maps. I'm yet to quantify exactly how much larger, since the compressed to/from binary seems to take care of _all_ the deduplication. I ran the eqc binary round trip test, hacking it to compare size of the old and new maps, and the new map was usually a little smaller. Go figure. We need to do more testing and benchmarking around this.

I guess I should write a lot more about the new Map design. One thing is for sure, the merge function is a damn sight simpler. And there are still no tombstones.

------

I wrote new EQCs for the Map and Set. They caught a bunch of bugs that old statem test did not. We need to re-write all the CRDTs to use this smaller-state-space style of test. We also need to factor out the commonality between theses tests. I think at this point just raising issues is enough.

Let me know if you need more information. This is last minute, big change stuff, so tread carefully. But be aware, the Map as it is in develop is unshippable, so we need either this design, or something new.

Good luck

Love

RDB