Dear Wiki user, You have subscribed to a wiki page or wiki category on "Cassandra Wiki" for change notification.
The "AntiEntropy" page has been changed by JonathanEllis. The comment on this change is: link AAE. http://wiki.apache.org/cassandra/AntiEntropy?action=diff&rev1=1&rev2=2 -------------------------------------------------- - Quoting from [[http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html|Amazon's Dynamo]] section 4.7, + Cassandra's implementation is modeled on Dynamo's, with [[ArchitectureAntiEntropy|modifications to support the richer data model]]. Quoting from [[http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html|Amazon's Dynamo]] section 4.7, . To detect the inconsistencies between replicas faster and to minimize the amount of transferred data, Dynamo uses Merkle trees [13]. A Merkle tree is a hash tree where leaves are hashes of the values of individual keys. Parent nodes higher in the tree are hashes of their respective children. The principal advantage of Merkle tree is that each branch of the tree can be checked independently without requiring nodes to download the entire tree or the entire data set. Moreover, Merkle trees help in reducing the amount of data that needs to be transferred while checking for inconsistencies among replicas. For instance, if the hash values of the root of two trees are equal, then the values of the leaf nodes in the tree are equal and the nodes require no synchronization. If not, it implies that the values of some replicas are different. In such cases, the nodes may exchange the hash values of children and the process continues until it reaches the leaves of the trees, at which point the hosts can identify the keys that are “out of sync”. Merkle trees minimize the amount of data that needs to be transferred for synchronization and reduce the number of disk reads performed during the anti-entropy process.
