Jul
11

Active Anti-Entropy

By kellabyte  //  Databases, Distributed Systems  //  3 Comments

Distributed systems that have relaxed consistency guarantees between replicas need ways to eventually converge on the same state. Doing this with a large set of data can be a real challenge. Processing and comparing full sets of data is expensive. If two replicas aren’t consistent you want to find out what pieces of data aren’t the same as efficiently as possible so that you can repair the inconsistent data.

Several eventually consistent databases such as Cassandra, Riak and Voldemort implement ideas introduced in the Amazon Dynamo paper. The Dynamo paper included the idea of using Merkle Tree’s (hash tree) for comparing data efficiently. Bit Torrent uses merkle tree’s as well.

Merkle Tree

The leaves in a merkle tree are hashes of data. Nodes further up in the tree are the hashes of their respective children. This allows you to compare in a top-down fashion until you find a mismatch. If the top level hash is the same, both nodes are consistent without having to check any further.

Anti-entropy

Anti-entropy is the process of detecting inconsistencies and repairing these inconsistencies. Sometimes this is simply describes as a “repair” that you may issue manually. In Riak there is support for what’s called active anti-entropy. Active anti-entropy takes a more automated  approach by continuously in the background comparing merkle tree’s between replicas and repairing inconsistencies.

In my opinion the choice whether active anti-entropy makes sense depends on a lot of factors about your system and the workload characteristics.

Joseph Blomstedt has an excellent video describing how active anti-entropy works in Riak. The video is also a really great example of how merkle tree’s work so I suggest anyone using Cassandra or Riak or just interested in distributed systems to give it a watch. Or four.

  • Graham

    Sounds similar to the way git is implemented…

  • Bryon

    I can’t get the ‘excellent video’ to run. The link takes me to the player, but clicking play results in spinning dots. :( I want to see it.

  • Marcus Granström

    Thanks for the tip.

    Great video.