Yuming Wang created SPARK-58137:
-----------------------------------
Summary: Optimize hasAttemptOnHost from O(m) linear scan to O(1)
HashSet lookup to avoid taskSetLock timeout
Key: SPARK-58137
URL: https://issues.apache.org/jira/browse/SPARK-58137
Project: Spark
Issue Type: Improvement
Components: Spark Core
Affects Versions: 4.3.0
Reporter: Yuming Wang
When speculation is enabled, dequeueTaskFromList iterates through the entire
pending speculative task list and calls hasAttemptOnHost for each entry — all
while holding the taskSetLock. The current implementation does an O(m) linear
scan:
{code}taskAttempts(taskIndex).exists(_.host == host){code}
With 100K+ speculatable tasks and many attempts per task (due to failures or
prior speculation), the lock hold time grows to tens of seconds, blocking all
other make-offer threads and causing:
{noformat}WARN [make-offer-thread-pool-4294] cluster.YarnScheduler:72 : Unable
to lock taskSet TaskSet_178603.1 after 5000ms, details:
org.apache.spark.scheduler.TaskSetLock@1a6daa67[Locked by thread
make-offer-thread-pool-4295]
at scala.collection.LinearSeqOptimized.exists 94
at scala.collection.LinearSeqOptimized.exists$ 92
at scala.collection.immutable.List.exists 91
at org.apache.spark.scheduler.TaskSetManager.hasAttemptOnHost 376
at org.apache.spark.scheduler.TaskSetManager.dequeueTaskFromList
357{noformat}
*Proposed fix:*
Add a lazily-allocated HashSet[String] per task index (taskAttemptHosts) to
track which hosts have attempted each task, enabling O(1) lookup instead of
O(m) linear scan. The set is lazily allocated per task to avoid upfront memory
for stages with 100K+ tasks.
*Benchmark results* (100K tasks, 1000 offers, while holding lock):
||Attempts/Task||Linear Scan (ms/offer)||HashSet (ms/offer)||Speedup||
|1|352|466|0.8X|
|10|2,655|2,246|1.2X|
|50|17,114|3,455|5.0X|
|100|30,640|3,758|8.2X|
At 100 attempts/task, lock hold time drops from ~30.6s to ~3.8s.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
