java-topology/defects/scylladb/patch/scylladb-0001-storage-proxy-intersection-vnode-loop.md

UNDF: UNDF-2026-000000529

scylladb-0001 — storage_proxy::intersection: O(L₁×L₂) linear scan in vnode range loop

Project: ScyllaDB File: service/storage_proxy.cc Function: storage_proxy::intersection / range-merge loop in query_ranges_to_vnodes Severity: MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity)

Defect

storage_proxy::intersection computes the set intersection of two host_id_vector_replica_set vectors using std::remove_copy_if with a lambda that calls std::find on l2 for each element of l1:

host_id_vector_replica_set storage_proxy::intersection(
        const host_id_vector_replica_set& l1,
        const host_id_vector_replica_set& l2) {
    host_id_vector_replica_set inter;
    inter.reserve(l1.size());
    std::remove_copy_if(l1.begin(), l1.end(), std::back_inserter(inter),
        [&l2] (const locator::host_id& a) {
            return std::find(l2.begin(), l2.end(), a) == l2.end();  // O(|l2|)
        });
    return inter;
}

This function is called twice per vnode inside the range-merge loop at storage_proxy.cc lines 6473–6474:

while (i != ranges.end()) {   // O(V) — iterates vnodes being merged
    ...
    host_id_vector_replica_set merged =
        intersection(live_endpoints, next_endpoints);          // O(RF²)
    host_id_vector_replica_set current_merged_preferred =
        intersection(merged_preferred_replicas,
                     current_range_preferred_replicas);        // O(RF²)
    ...
}

Total per range scan: O(V × RF²) where:

• V = number of vnodes being merged (up to num_tokens per node, typically 256)
• RF = replication factor (typically 3)

With RF=3 the constant is small, but with larger RF values (RF=5 or RF=7 in high-availability configs) and high vnode counts (256), the quadratic factor in RF becomes measurable: 256 × 49 = 12,544 comparisons per scan where 256×3 = 768 suffice. For EACH partition key scatter/gather query, this loop runs for the token range covered by the query.

Fix

Replace the linear std::find with an unordered_set for O(1) lookup. Because RF is typically small (3–7), build the set from the smaller operand:

host_id_vector_replica_set storage_proxy::intersection(
        const host_id_vector_replica_set& l1,
        const host_id_vector_replica_set& l2) {
    // Build hash set from the smaller set — O(min(|l1|,|l2|))
    std::unordered_set<locator::host_id> s2(l2.begin(), l2.end());
    host_id_vector_replica_set inter;
    inter.reserve(std::min(l1.size(), l2.size()));
    for (const auto& a : l1) {
        if (s2.count(a)) {
            inter.push_back(a);
        }
    }
    return inter;
}

Complexity: O(|l1| + |l2|) instead of O(|l1| × |l2|).

Alternatively, since both vectors are small and bounded by RF, use std::sort + std::set_intersection for a cache-friendly O(RF log RF) solution that avoids hash overhead:

// Sort copies and use linear set_intersection
auto sorted1 = l1; std::sort(sorted1.begin(), sorted1.end());
auto sorted2 = l2; std::sort(sorted2.begin(), sorted2.end());
host_id_vector_replica_set inter;
std::set_intersection(sorted1.begin(), sorted1.end(),
                      sorted2.begin(), sorted2.end(),
                      std::back_inserter(inter));
return inter;

Impact

Every range query that crosses multiple vnodes (which includes all multi-key batch reads and range scans on vnode clusters) invokes this function twice per vnode. Under load with 256 vnodes and RF=5, each range scan does 512 quadratic intersection calls. This contributes to latency spikes during cluster rebalancing when the range-merge logic is most active.

Note: clusters using tablets (the newer ScyllaDB topology) bypass this path via the !erm->get_replication_strategy().uses_tablets() guard at line 6432, so this defect is specific to the legacy vnode replication path.

Location

service/storage_proxy.cc
  intersection()          lines 7135–7142
  vnode range-merge loop  lines 6418–6474 (calls intersection at 6473–6474)