[
https://issues.apache.org/jira/browse/CASSANDRA-4482?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13434048#comment-13434048
]
Nicolas Favre-Felix commented on CASSANDRA-4482:
------------------------------------------------
Jonathan,
I wrote the blog post linked in this ticket; the incremental repair process
we've implemented is not doing any random I/O on insert as you suggest.
Instead, we maintain a Merkle Tree (MT) in memory and update it with every
single column insert in ColumnFamilyStore.apply(). We use
column.updateDigest(digest) on all the changes in order to create a hash per
column update and then XOR this hash with the existing one in the Merkle Tree
bucket for the corresponding row.
This Merkle Tree is created with the column family (one per range), initialized
with zeros, and persisted to disk with regular snapshots.
The commutative properties of XOR make it possible to update the MT
incrementally without having to read on write.
When an incremental repair session starts, the CFS swap out their existing MTs
for new empty ones that will receive subsequent updates.
There are a few downsides to this approach:
* It is possible for the incremental MTs to miss a few inserts that happen when
the replicas involved swap out their MTs for new ones. An insert will be in the
previous MT for node "A" but in the fresh one for node "B", for instance. This
leads to either a very small amount of extra streaming or some unrepaired
changes. For this reason, we still recommend that users run either a full
repair or a "tombstone-only repair" at least once every GCGraceSeconds.
* There is some overhead to keeping these MTs in memory. We actually maintain
only the leaves as a single ByteBuffer instead of creating all the intermediate
nodes like the MerkleTree class does. To avoid using too much RAM, we allocate
a fixed amount of memory per CF and divide it into a number of smaller buffers
(one per range) in order to give the same guarantees regardless of the number
of ranges per CF.
* There is a small cost in insert, about half of which is due to the hash
function (MD5).
We are looking into making our patch available to the community and would
welcome suggestions to solve or improve on these limitations.
> In-memory merkle trees for repair
> ---------------------------------
>
> Key: CASSANDRA-4482
> URL: https://issues.apache.org/jira/browse/CASSANDRA-4482
> Project: Cassandra
> Issue Type: New Feature
> Reporter: Marcus Eriksson
>
> this sounds cool, we should reimplement it in the open source cassandra;
> http://www.acunu.com/2/post/2012/07/incremental-repair.html
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
