basho/riak_kv — pull request #710 by jtuple (2013-10-24 22:20:45+00:00)
Title: Support for strongly consistent Riak

This is the `riak_kv` related pull-request for on-going work to add strong consistency to Riak.

Primarily, this pull-request integrates with [riak_ensemble](http://github.com/basho/riak_ensemble) that provides most of the heavy lifting.

This pull-request is provides a `riak_ensemble_backend` implementation that integrates with K/V vnodes, registers ensembles (consensus groups) for each distinct replica set (preflist/n-val) in Riak, and maps the existing client API onto `riak_ensemble_client` against these new K/V ensembles.

---

Objects written under a bucket type with property `consistent = true` are consistent objects and use the consistent code path, everything else uses the normal Riak code path.

Consistent operations are conditional single key atomic updates:

* If you write a key, the next successful read is guaranteed to show that write (or the result of a future write that saw the write).

* If you get/modify/put an object, Riak ensures that the object didn't change since you read it. In other words, the request will fail if a concurrent write occurred and changed the object.

* In general, timeouts are indistinguishable from partial writes in a distributed system. Thus, consistent Riak resolves partial write ambiguity at read time. If you try to write a value, and that write times out, the current state of the key is unknown -- it could be the prior value or the attempted to write value. However, the next successful read of the key tells you which occurred and ensures that decision does not change in the future.

* For example, if you partially write to 1 replica which then becomes partitioned/goes offline. Subsequently, perform a successful read that shows the old value. It's guaranteed the old value wins. The partitioned failed--to-write value is essentially rolled back. Even once that replica comes back online and propagates the failed-to-write value, the old value still wins.

Internally, `riak_ensemble` supports three types of writes: `put_once`, `modify`, and `overwrite`.

* A `put_once` operation only succeeds if the key doesn't already exist.

* A `modify` operation is used as the `put` in a get/modify/put sequence. A `modify` operation fails the write if the object no longer matches the base object returned in the `get` part of the sequence.

* A `overwrite` operation is a fast, unsafe, unchecked operation. `overwrite` operations overwrite the key without regard to it's existing value. This is useful when bulk loading data.

For Riak, the existing K/V API is mapped to a subset of these operations. Client puts that are missing a vector clock are mapped to `put_once` operations, while those that provide a vector clock are mapped to `modify`. There is currently no mapping to `overwrite`.

A previous version of this code mapped operations w/o vector clocks to `overwrite`, and puts with `if_none_matched` to `put_once`, but it is too easy for a client to accidentally not send vector clock data and mapping that to `overwrite` made it too easy for users to clobber data. Hence the safer mapping above.

Delete operations are similar. Riak client deletes map to a unchecked (similar to overwrite) ensemble delete. Whereas client delete_vclock operations map to safe deletes that are similar to `modify`. Specifically, the safe variant is used in the sequence: `Obj = get(), delete(Obj)` where Riak fails the delete if the object has changed the get.

Note: All mentions of "vector clock" above are slightly different than normal Riak. Consider them opaque contexts passed back/forth to the client. In general, vector clocks for consistent data aren't really the same as with normal Riak operations. We don't main normal vector clocks at all. The consistent subsystem maintains it's own logical clock per ensemble (eg. per preflist) which is used for all consistent operations. However, for compatibility this value is converted into a "vector clock" thus the object and client requests formats stays the same.

---

Known limitations/issues (TODO: file issues)

* Consistent data does not currently support secondary indexes.

* Consistent data does not currently support object mutators.

* Consistent operations do not yet fire any stats-related events, nor keep any stats of their own.

* Consistent operations currently bypass the overload protection system and need their own overload protection to be added.

* Deleting consistent data leaves around tombstones that are not currently harvested.

* Consistent reads currently do not use read repair, nor does normal AAE currently heal missing consistent data.

* The consensus subsystem (riak_ensemble) requires implementing modules to provide a `sync` behavior that heals potentially diverted/corrupted replicas. The plan is to use AAE for this in `riak_kv`. However, this currently is not done and will be done in a future pull-request.