Database Reference
In-Depth Information
the value is returned to the client. On the other hand, if there is a mismatch, full data is re-
trieved and reconciliation is done and the client is sent the reconciled value. After this, in
the background, all the replicas are updated with the reconciled value to have a consistent
view of data on each node. The following figure shows this process:
• Client queries for data X, from a node C (coordinator)
• C gets data from replicas R1, R2, and R3 reconciles
• Sends reconciled data to client
• If there is a mismatch across replicas, a repair is invoked
The following figure shows the read repair dynamics:
So, we have got a consistent view on read. What about the data that is inserted, but never
read? Hinted handoff is there, but we do not rely on hinted handoff for consistency. What
if the node containing hinted handoff data dies, and the data that contains the hint is never
read? Is there a way to fix them without read? This brings us to the anti-entropy architec-
ture of Cassandra (borrowed from Dynamo).
Anti-entropy compares all the replicas of a column family and updates the replicas to the
latest version. This happens during major compaction. It uses Merkle trees to determine
discrepancies among the replicas and fixes them.
Merkle tree
Merkle tree is a hash tree where leaves of the tree hashes hold actual data in column fam-
ily and non-leaf nodes hold hashes of their children. For more information, refer to
A di-
gital signature Based On A Conventional Encryption Function
by Merkle, R. (1988),
available at
http://link.springer.com/chapter/10.1007%2F3-540-48184-2_32
.
The unique
advantage of a Merkle tree is that a whole subtree can be validated just by looking at the
value of the parent node. So, if nodes on two replica servers have the same hash values,
then the underlying data is consistent and there is no need to synchronize. If one node
passes the whole Merkle tree of a column family to another node, it can determine all the
inconsistencies.
