You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Jonathan Ellis (Updated) (JIRA)" <ji...@apache.org> on 2012/02/23 19:16:48 UTC
[jira] [Updated] (CASSANDRA-3952) avoid quadratic startup time in
LeveledManifest
[ https://issues.apache.org/jira/browse/CASSANDRA-3952?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-3952:
--------------------------------------
Fix Version/s: (was: 1.1.0)
> 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: Jonathan Ellis
> Priority: Minor
> Fix For: 1.1.1
>
>
> 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