[jira] [Commented] (CASSANDRA-11390) Too big MerkleTrees allocated during repair

["Marcus Olsson (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/CASSANDRA-11390?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15206074#comment-15206074 ] 

Marcus Olsson commented on CASSANDRA-11390:
-------------------------------------------

Sure! :) I've taken a glance at the patch and it looks good and should reduce the merkle tree memory usage in most cases. However I'm worried that we still might be able to get into a situation where we allocate too much memory for the merkle trees since we have a max depth of {{20}} which was used as max when there was only one merkle tree. Due to the fact that we have a variable number of concurrently repairing ranges it would probably be ineffective to simply lower the max depth since that would reduce the resolution of the merkle trees when we are repairing a fewer number of ranges. Instead we could calculate the max depth each time. The number of nodes in a merkle tree is roughly {{2^d}} where {{d}} is the depth of the tree and before CASSANDRA-5220 the max number of nodes were {{2^20 = 1048576}}. If we want {{2^20}} to be the max total number of nodes then {{ranges * 2^d}} would have to be less than {{2^20}} which we could calculate as:

{code}
2^20 >= ranges * 2^d
<=>
log2(2^20) >= log2(ranges * 2^d)
<=>
20 >= log2(ranges) + d
<=>
d <= 20 - log2(ranges)
{code}

In java:
{code}
int maxDepth = (int) Math.floor(20 - Math.log(validator.desc.ranges.size()) / Math.log(2));
// And then calculate the depth using:
int depth = numPartitions > 0 ? (int) Math.min(Math.floor(Math.log(numPartitions)), maxDepth) : 0;
{code}

---

Another thing that also could reduce the merkle tree sizes is if we are able to estimate how much overlap there is between sstables for each range, since that could be used to reduce the estimated number of partitions. The effectiveness of this would probably depend on the compaction strategy and how accurately we can calculate the range overlap though.

> Too big MerkleTrees allocated during repair
> -------------------------------------------
>
>                 Key: CASSANDRA-11390
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-11390
>             Project: Cassandra
>          Issue Type: Bug
>            Reporter: Marcus Eriksson
>            Assignee: Marcus Eriksson
>             Fix For: 3.0.x, 3.x
>
>
> Since CASSANDRA-5220 we create one merkle tree per range, but each of those trees is allocated to hold all the keys on the node, taking up too much memory



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)