[jira] [Issue Comment Edited] (CASSANDRA-3952) avoid quadratic startup time in LeveledManifest

["Peter Schuller (Issue Comment Edited) (JIRA)" <ji...@apache.org>]

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

Peter Schuller edited comment on CASSANDRA-3952 at 3/6/12 8:41 AM:
-------------------------------------------------------------------

Committed with an additional assertion and the map renamed to {{sstableGenerations}}, and including 1.1.0. It was marked for 1.1.1 but frankly if this *does* introduce some kind of bug, it feels more dangerous to have that crop up in an upgrade to 1.1.1 than to have it in the initial release.
                
      was (Author: scode):
    Committed, including 1.1.0. It was marked for 1.1.1 but frankly if this *does* introduce some kind of bug, it feels more dangerous to have that crop up in an upgrade to 1.1.1 than to have it in the initial release.
                  
> 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.0
>
>         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