# 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`:

```cpp
// 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):

```cpp
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.
