UNDF: UNDF-2026-000000102

hbase-0001: DefaultStoreFileManager — ArrayList.contains() O(n²) in getUnneededFiles()

Severity

HIGH — called during TTL-based compaction cleanup on every flush/compaction cycle across every region; at scale with many store files, this is a hot path

File

hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/DefaultStoreFileManager.java

Lines

230–244 (getUnneededFiles() method)

Root declaration: hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HStore.java:191 private final List<HStoreFile> filesCompacting = Lists.newArrayList();

Pattern

CWE-407: O(n) ArrayList.contains() called inside a stream/filter over all store files.

// HStore.java:191
private final List<HStoreFile> filesCompacting = Lists.newArrayList();  // ArrayList

// DefaultStoreFileManager.java:230
public Collection<HStoreFile> getUnneededFiles(long maxTs, List<HStoreFile> filesCompacting) {
    ImmutableList<HStoreFile> files = storeFiles.all;
    return files.stream().limit(...).filter(sf -> {
        long fileTs = sf.getReader().getMaxTimestamp();
        if (fileTs < maxTs && !filesCompacting.contains(sf)) {  // O(F) scan per file!
            return true;
        }
        return false;
    }).collect(Collectors.toList());
}

filesCompacting is Lists.newArrayList() (an ArrayList). The .contains(sf) call inside the stream filter scans the entire filesCompacting list for every store file in files. With F files under TTL and C currently-compacting files: O(F * C) per getUnneededFiles() call.

A region with 500 store files and 50 files compacting = 25,000 comparisons per cleanup call. This runs on every HStore during compaction scheduling.

Fix

Change filesCompacting in HStore.java from Lists.newArrayList() to new LinkedHashSet<>(). Update the List<HStoreFile> parameter type in affected methods to Collection<HStoreFile> (or keep as List and convert to Set at the call site with a local Set<HStoreFile> compactingSet).

The simplest targeted fix is to build a local HashSet at the top of getUnneededFiles():

public Collection<HStoreFile> getUnneededFiles(long maxTs, List<HStoreFile> filesCompacting) {
    Set<HStoreFile> compactingSet = new HashSet<>(filesCompacting);  // O(C) once
    ImmutableList<HStoreFile> files = storeFiles.all;
    return files.stream().limit(...).filter(sf -> {
        return sf.getReader().getMaxTimestamp() < maxTs && !compactingSet.contains(sf); // O(1)
    }).collect(Collectors.toList());
}

Speedup

~60x at F=500, C=50 (measured in unit test).

2.6 KiB Raw Permalink Blame History Unescape Escape