cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Peter Schuller (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-3952) avoid quadratic startup time in LeveledManifest
Date Tue, 06 Mar 2012 08:20:58 GMT

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

Peter Schuller commented on CASSANDRA-3952:
-------------------------------------------

I think this might happen whenever there is exactly one sstable in L0 that is large enough
for the score for L0 to be > 1, *and* if L1 is full (so that skipLevels doesn't promote).

It's possible the sstables I had lying around from sized-tiered compaction combined with my
write load conspired to trigger this case.

I'll go over the patch once again and try to be sure we are never accidentally not adding
the level information somewhere. If it looks good I'll file this problem in a separate ticket.
                
> avoid quadratic startup time in LeveledManifest
> -----------------------------------------------
>
>                 Key: CASSANDRA-3952
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-3952
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Jonathan Ellis
>            Assignee: Dave Brosius
>            Priority: Minor
>              Labels: lhf
>             Fix For: 1.1.1
>
>         Attachments: speed_up_level_of.diff
>
>
> Checking that each sstable is in the manifest on startup is O(N**2) in the number of
sstables:
> {code}
> .       // ensure all SSTables are in the manifest
>         for (SSTableReader ssTableReader : cfs.getSSTables())
>         {
>             if (manifest.levelOf(ssTableReader) < 0)
>                 manifest.add(ssTableReader);
>         }
> {code}
> {code}
> private int levelOf(SSTableReader sstable)
> {
>     for (int level = 0; level < generations.length; level++)
>     {
>         if (generations[level].contains(sstable))
>             return level;
>     }
>     return -1;
> }
> {code}
> Note that the contains call is a linear List.contains.
> We need to switch to a sorted list and bsearch, or a tree, to support TB-levels of data
in LeveledCompactionStrategy.

--
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

        

Mime
View raw message