basho/riak_kv — pull request #421 by jtuple (2012-11-02 12:12:52+00:00)
Title: Active Anti-Entropy

Had trouble merging and rebasing, so I ended up squashing into a single commit. So, here's AAE in all it's a glory, as a single super commit. Given how much this has been rewritten/reorganized, the old commit history doesn't help much anyway.

I'm extending/polishing my riak_tests some more, but will have thoses pushed soon and linked to this pull-request.

Hopefully all documentation and included -specs make this straightforward to review, despite being a massive pull-request. Also, everything from my AAE screencast that I previously distributed is still valid:
http://coffee.jtuple.com/video/AAE.html

I'm assuming @rzezeski and @Vagabond will be the two reviewing this, but others can jump on as well. However, we should have at least 2 reviewers on this one.

(cabal: basho/cabal#1)

---

Active anti-entropy is a process through which multiple replicas periodically sync with each other and automatically repair any keys that are missing or have divergent data. For example, a user could delete all data from a node and Riak would automatically regenerate the data from the other replicas.

This implementation uses hash trees / Merkle trees to perform lightweight key exchange, with work proportional to the number of divergent keys rather than the size of the overall keyspace.

This implementation meets several design goals:

1. The underlying hash trees are on-disk structures, and can scale to billions+ keys. This is in contrast to in-memory trees that require significant RAM to support massive keyspaces.

2. The underlying hash trees are persistent. Riak nodes can be restarted without fear of hash tree data being lost and needing to be rebuilt.

3. As new data is written to Riak, the hash trees associated with the various partitions are kept up-to-date. Each write in Riak triggers an asynchronous write to one or more hash trees. Combined with 2, this enables trees to be built once through a scan over existing data, and then maintained in real-time. In reality, trees are expired over time and rebuilt to ensure the hash tree and backend data stay in sync, and also to identify bit rot / disk failure.

4. The entire implementation is designed to be non-blocking. For example, a snapshot of a hash tree is generated before performing an exchange with other replicas, therefore allowing concurrent inserts of new key/hash pairs as new writes occur.

The current implementation triggers read repair for each key difference identified through the hash exchange. This is a reasonable approach as read repair is stable, production-tested mechanism in Riak. However, the read repair approach leads to slower replica repair in cases where there are a large number of key differences. This is an area for future improvement.