basho/riak_kv — pull request #746 by russelldb (2013-12-04 21:15:44+00:00)
Title: Use a DVV like approach to stop sibling explosion

As has been witnessed by our customers, and demonstrated by Baquero et al, sibling explosion occurs when we keep values as concurrent when they're not really.

Our vnode vclocks are not fine grained enough to describe which of a set of siblings should be overwritten by a PUT, so we keep all siblings. It is trivially easy to create a scenario where interleaving writes create an explosion of sibling values, even without failure, or concurrency (see riak_test#383.)

This PR introduces a more fine grained approach to causality tracking, without going all the way and using DVV or DVVSets.

The general mechanism is to store the event (`{actor, {count, ts}}`) that a value is created at as metadata with the value. When a PUT is received, any siblings whose events are dominated by the PUT vclock are removed. Only siblings that the writer has not seen are genuinely concurrent.

In order not to drop ALL the values during other merge types, when any two merging objects both have the same event, that sibling stays.

Nothing is for free, so there is some extra complexity around `riak_object:merge`.

This PR requires the riak_core#463 and can be tested with riak_test#383.