UNDF: UNDF-2026-000000472

nifi-0001: Controller Service topological sort O(S²) → O(S)

Location

Primary: nifi-framework-bundle/nifi-framework/nifi-framework-components/src/main/java/org/apache/nifi/controller/service/StandardControllerServiceProvider.java Lines 431–465 (determineEnablingOrder)

Duplicate: nifi-framework-bundle/nifi-framework/nifi-web/nifi-web-api/src/main/java/org/apache/nifi/web/util/LocalComponentLifecycle.java Lines 410–438 (same function, copy-pasted)

Severity

HIGH — triggered every time controller services are enabled (startup, flow deployment, restart)

Description

determineEnablingOrder performs a depth-first topological sort of controller service dependencies. The orderedNodes accumulator is a List<ControllerServiceNode>, and every node addition is guarded by orderedNodes.contains(node) — an O(N) scan.

The public method iterates over all S services, calling the recursive private method for each. In the worst case (a chain of S services), the list grows to S entries and each contains() check scans the whole list → O(S²) total.

Root Cause

// StandardControllerServiceProvider.java line 431–441
static List<List<ControllerServiceNode>> determineEnablingOrder(
        final Map<String, ControllerServiceNode> serviceNodeMap) {
    final List<List<ControllerServiceNode>> orderedNodeLists = new ArrayList<>();
    for (final ControllerServiceNode node : serviceNodeMap.values()) {  // O(S) outer
        final List<ControllerServiceNode> branch = new ArrayList<>();
        determineEnablingOrder(serviceNodeMap, node, branch, new HashSet<>());
        orderedNodeLists.add(branch);
    }
    return orderedNodeLists;
}

private static void determineEnablingOrder(...,
        final List<ControllerServiceNode> orderedNodes,   // ← List, not Set
        final Set<ControllerServiceNode> visited) {
    ...
    for (final Map.Entry<PropertyDescriptor, String> entry : ...) {  // O(P) props
        ...
        if (!orderedNodes.contains(referencedNode)) {  // O(N) scan → O(S×P×N) total
            ...
            determineEnablingOrder(...);
        }
    }
    if (!orderedNodes.contains(contextNode)) {          // O(N) scan again
        orderedNodes.add(contextNode);
    }
}

Fix

Track membership in a companion Set<ControllerServiceNode> alongside the ordered list:

private static void determineEnablingOrder(
        final Map<String, ControllerServiceNode> serviceNodeMap,
        final ControllerServiceNode contextNode,
        final List<ControllerServiceNode> orderedNodes,
        final Set<ControllerServiceNode> orderedSet,   // ← new parameter
        final Set<ControllerServiceNode> visited) {

    if (visited.contains(contextNode)) return;

    for (final Map.Entry<PropertyDescriptor, String> entry : ...) {
        if (entry.getKey().getControllerServiceDefinition() != null) {
            final String referencedServiceId = entry.getValue();
            if (referencedServiceId != null) {
                final ControllerServiceNode referencedNode = serviceNodeMap.get(referencedServiceId);
                if (!orderedSet.contains(referencedNode)) {      // O(1)
                    visited.add(contextNode);
                    determineEnablingOrder(serviceNodeMap, referencedNode, orderedNodes, orderedSet, visited);
                }
            }
        }
    }

    if (!orderedSet.contains(contextNode)) {                     // O(1)
        orderedNodes.add(contextNode);
        orderedSet.add(contextNode);
    }
}

Apply the same fix to LocalComponentLifecycle.java.

Complexity

	Before	After
determineEnablingOrder	O(S²×P)	O(S×P)

Where S=services, P=properties per service. At S=200 services, P=10 props: 400,000 ops → 2,000 ops (200x improvement).

Note

This is structurally identical to the Airflow (airflow-0001) and Maven topological sort defects found in previous waves. The fix pattern is the same: companion HashSet for O(1) membership, ordered List for sequence.

4 KiB Raw Permalink Blame History Unescape Escape