UNDF: UNDF-2026-000000291

spark-0003: Spark Standalone Master — completedApps ArrayBuffer.contains() O(n²) on worker failure

Severity

MEDIUM — called on each worker failure; O(A × C) where A = running apps, C = completed apps; materializes in long-running clusters where C grows to spark.deploy.retainedApplications (default 200)

File

core/src/main/scala/org/apache/spark/deploy/master/Master.scala

Lines

83 (completedApps field declaration), 1114 (apps.filterNot(completedApps.contains(_)))

Pattern

CWE-407: O(n) ArrayBuffer.contains() used as predicate in filterNot over all running apps.

// DEFECTIVE (line 83)
private val completedApps = new ArrayBuffer[ApplicationInfo]

// DEFECTIVE (line 1114) — inside workerRemoved(worker), called for every worker failure
apps.filterNot(completedApps.contains(_)).foreach { app =>
    ...  // notify app of lost worker
}

completedApps is a mutable.ArrayBuffer. filterNot(completedApps.contains(_)) iterates every element of apps (HashSet[ApplicationInfo]) and calls completedApps.contains(app) — O(completedApps.size) per app. Total: O(|apps| × |completedApps|).

By default, Spark retains 200 completed applications (spark.deploy.retainedApplications). Each worker failure call becomes O(200 × A) where A is the current number of running apps. In a large Spark cluster with 100 running apps and 200 completed: 20,000 comparisons instead of 100.

Fix

Pre-build a HashSet before the filter, or use toSet:

// FIXED — option 1: convert at call site
val completedAppsSet = completedApps.toSet
apps.filterNot(completedAppsSet.contains(_)).foreach { app =>

// FIXED — option 2: maintain as HashSet
private val completedApps = new mutable.HashSet[ApplicationInfo]

Option 2 is preferred as completedApps is only ever tested for membership or iterated; changing to HashSet gives O(1) contains with no behavior change.

Complexity

Before: O(A × C) per worker failure event
After: O(A) per worker failure event

Impact

Worker failures trigger master-level app notification. In a cluster under stress (many worker failures), this compounds — each failure event is more expensive just as cluster load peaks. With 200 completed apps, this is a 200x overhead per failure event.

2.3 KiB Raw Permalink Blame History Unescape Escape