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.0, 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
