java-topology/docs/tickets/linkerd2-0001-federated-service-remote-discovery-quadratic-dedup.md

linkerd2-0001: federatedService.update() slices.Contains O(n) inside loop → O(n²) dedup

Target: linkerd/linkerd2 Severity: MEDIUM CWE: CWE-407 (Inefficient Algorithmic Complexity) File: controller/api/destination/federated_service_watcher.go Status: PATCHED

Description

federatedService.update() computes the diff between the old and new remoteDiscovery slices by calling slices.Contains inside two separate for range loops. Each slices.Contains call is O(N) where N = number of remote discovery IDs. With N IDs in both old and new slices, the diff is O(N²).

This function is called on every Service update event. In multi-cluster Linkerd deployments with many federated services, each annotation update triggers a full O(N²) scan.

Location	Pattern
federated_service_watcher.go:231	slices.Contains(fs.remoteDiscovery, id) inside for _, id := range newRemoteDiscovery
federated_service_watcher.go:238	slices.Contains(newRemoteDiscovery, id) inside for _, id := range fs.remoteDiscovery
federated_service_watcher.go:46	remoteDiscovery []remoteDiscoveryID — stored as slice

Root cause

// federated_service_watcher.go:229
func (fs *federatedService) update(service *corev1.Service) {
    newRemoteDiscovery := remoteDiscoveryIDs(service, fs.log)

    // O(N²): for each new ID, scan old slice
    for _, id := range newRemoteDiscovery {
        if !slices.Contains(fs.remoteDiscovery, id) {
            ...subscribe...
        }
    }
    // O(N²): for each old ID, scan new slice
    for _, id := range fs.remoteDiscovery {
        if !slices.Contains(newRemoteDiscovery, id) {
            ...unsubscribe...
        }
    }
    fs.remoteDiscovery = newRemoteDiscovery
}

With N=1000 remote discovery IDs, each update event costs ~1,000,000 struct comparisons. In active multi-cluster deployments this runs on every Service reconcile.

Fix

Convert remoteDiscovery to a map[remoteDiscoveryID]struct{} or use sets.Set[remoteDiscoveryID]. Diff becomes O(N).

// After fix: O(N) diff using map set
func (fs *federatedService) update(service *corev1.Service) {
    newSet := make(map[remoteDiscoveryID]struct{})
    for _, id := range remoteDiscoveryIDs(service, fs.log) {
        newSet[id] = struct{}{}
    }
    oldSet := fs.remoteDiscoverySet

    // O(N) adds
    for id := range newSet {
        if _, exists := oldSet[id]; !exists {
            for i := range fs.subscribers { fs.remoteDiscoverySubscribe(...) }
        }
    }
    // O(N) removes
    for id := range oldSet {
        if _, exists := newSet[id]; !exists {
            for i := range fs.subscribers { fs.remoteDiscoveryUnsubscribe(...) }
        }
    }
    fs.remoteDiscoverySet = newSet
}

Ops/ns numbers (Java benchmark)

See defects/linkerd2/unit/Linkerd2Test.java. At N=1000 IDs: slow ~1,000,000 ops, fast ~2,000 ops → >100× speedup.