java-topology/defects/dragonfly/patch/dragonfly-0001-missing-migrations-hashset.md

UNDF: UNDF-2026-000000382

dragonfly-0001: GetMissingMigrations O(M²) std::find → O(M log M) set_difference

Classification

Field	Value
CWE	CWE-407 Inefficient Algorithmic Complexity
Severity	LOW-MEDIUM
Component	src/server/cluster/cluster_config.cc:394
Function	GetMissingMigrations (called × 4 per config update)
Hot path	Every SetConfig / cluster reconfiguration event
Status	PATCHED (unit test PASS)

Defect

GetMissingMigrations computes the set difference of two std::vector<MigrationInfo> using a nested loop + std::find:

// cluster_config.cc:394
static std::vector<MigrationInfo> GetMissingMigrations(
    const std::vector<MigrationInfo>& haystack,
    const std::vector<MigrationInfo>& needle) {
  std::vector<MigrationInfo> res;
  for (const auto& h : haystack) {                              // O(M)
    if (find(needle.begin(), needle.end(), h) == needle.end()) { // O(M × R)
      res.push_back(h);
    }
  }
  return res;
}

MigrationInfo::operator== compares node_info (string) + slot_ranges (vector comparison O(R)). Total: O(M² × R) per call × 4 call sites per config update.

Called by:

• GetNewOutgoingMigrations
• GetNewIncomingMigrations
• GetFinishedOutgoingMigrations
• GetFinishedIncomingMigrations

Note: Current deployments use M < 10, so practical impact is low. However the API is O(M²) by design and becomes a bottleneck if Dragonfly supports large-scale automated shard rebalancing (M = hundreds).

Fix

Sort both vectors on node_info.id (already has operator<), then use std::set_difference → O(M log M):

static std::vector<MigrationInfo> GetMissingMigrations(
    std::vector<MigrationInfo> haystack,   // by value — will sort
    std::vector<MigrationInfo> needle) {
  std::sort(haystack.begin(), haystack.end());
  std::sort(needle.begin(), needle.end());
  std::vector<MigrationInfo> res;
  std::set_difference(haystack.begin(), haystack.end(),
                       needle.begin(), needle.end(),
                       std::back_inserter(res));
  return res;
}

Or: build absl::flat_hash_set<string> keyed on node_info.id from needle, check in O(1) per haystack entry → O(M) total.