[CASSANDRA-3952] avoid quadratic startup time in LeveledManifest

• Type: Improvement
• Status: Resolved
• Priority: Low
• Resolution: Fixed
• Fix Version/s: 1.1.0
• Labels: lcs lhf
• Assignee: David Brosius
• Reporter: Jonathan Ellis

Authors

David Brosius

Reviewers

Peter Schuller

• Created: 23/Feb/12 18:13
• Updated: 16/Apr/19 09:32
• Resolved: 06/Mar/12 08:40

Description

Checking that each sstable is in the manifest on startup is O(N**2) in the number of sstables:

.       // ensure all SSTables are in the manifest
        for (SSTableReader ssTableReader : cfs.getSSTables())
        {
            if (manifest.levelOf(ssTableReader) < 0)
                manifest.add(ssTableReader);
        }

private int levelOf(SSTableReader sstable)
{
    for (int level = 0; level < generations.length; level++)
    {
        if (generations[level].contains(sstable))
            return level;
    }
    return -1;
}

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.