UNDF: UNDF-2026-000000533

solr-003: SplitShardCmd O(n²) subSlices.contains in loop over all collection slices

Classification

CWE: CWE-407 (Inefficient Algorithmic Complexity)
Severity: MEDIUM
Path: Shard split rollback cleanup — SplitShardCmd.cleanupAfterFailedSplit()

Location

solr/core/src/java/org/apache/solr/cloud/api/collections/SplitShardCmd.java:985

Defect

List<String> subSlices = new ArrayList<>();
// subSlices is populated with the newly created sub-shard names (at most MAX_NUM_SUB_SHARDS = 8)

// In cleanupAfterFailedSplit() — called during shard split failure/rollback:
for (Slice s : coll.getSlices()) {         // O(S) — all slices in collection
    if (!subSlices.contains(s.getName())) { // O(n) — linear scan each time
        continue;
    }
    propMap.put(s.getName(), Slice.State.CONSTRUCTION.toString());
    sendUpdateState = true;
}

Total complexity: O(S × n) where S = total slices in the collection, n = subSlices count.

For a large SolrCloud collection with many shards (S = 1000+), each cleanup scan costs O(S × 8) comparisons rather than O(S). While subSlices is capped at 8, the outer loop is not. In a large collection during a failed split this runs at O(8,000) comparisons vs O(1,008) with a Set.

Fix

Convert to HashSet<String> before the loop:

Set<String> subSliceSet = new HashSet<>(subSlices);

for (Slice s : coll.getSlices()) {
    if (!subSliceSet.contains(s.getName())) {   // O(1)
        continue;
    }
    propMap.put(s.getName(), Slice.State.CONSTRUCTION.toString());
    sendUpdateState = true;
}

Result: O(S) — single pass with O(1) lookup.

Severity Rationale

The cleanupAfterFailedSplit path is not called on every request, but it is invoked during split operations which can be triggered frequently in large automated cluster management pipelines. The larger the collection, the more expensive the cleanup.

1.9 KiB Raw Permalink Blame History Unescape Escape