[ https://issues.apache.org/jira/browse/CASSANDRA-4482?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13434150#comment-13434150 ]
Jonathan Ellis commented on CASSANDRA-4482: ------------------------------------------- bq. The commutative properties of XOR make it possible to update the MT incrementally without having to read on write Hang on, let's flesh this out. I have an md5 hash (or part of one, see below) per row in a MerkleTree TreeRange. I xor all these together to get my initial state, S. To update row A to row A', I need to take S xor hash(A) xor hash(A'). So I still need to read-on-write to compute hash(A), I just don't have to rehash everything else in the same TreeRange. (I can imagine breaking this down into xoring individual columns, which would mean we would only need to read modified columns and not the entire row, but the principle is the same.) bq. For num_tokens=256, that's 1 KB per range on average I see, you mean vnode ranges. What I meant was MT TreeRanges... a MT can have 64k TR. Ideally you will have 16 bytes (md5 size) per TR. You can throw away some bytes at the cost of false negatives, i.e., with a single byte per TR, two replicas will think they have the same data even when they do not 1/256 of the time. But if you have 64k 1-byte treeranges, how do you fit that into 1KB? Do you reduce the TR granularity further? 64k already feels too low... although this is mitigated somewhat by vnodes. bq. do have to reload $num_tokens ByteBuffers when creating the ColumnFamilyStore And sync the BB saving with CF flushes so CL replay matches up, I imagine. > 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