spawn on demand / event driven graph

[oliver-sanders]

Replace the iterative task pool with an event-driven graph solution.

Just realised that despite all the discussion we don't actually have an issue open for this (let me know if I've simply missed it).

For a longer (and much more rambling) read see https://github.com/cylc/cylc-flow/wiki/Possible-Cylc-Futures#event-driven-scheduler.

Quick overview

• Translate an iterative problem into a lookup problem.
  • O(N) => O(1)
  • Messages come into the system,
  • a lookup associates them with nodes in the graph,
  • these events propagate through the graph,
  • so there is no need to loop over the task pool to determine consequences.
• Implement cycling "drivers" to provide a simple abstract interface for things a graph could cycle over.

Benefits

• Better scaling to number of:
  • active tasks (close #1689);
  • recurrences (close #1751);
  • prerequisites (close #1894).
• Improved responsiveness (from one task succeeding to the next submitting should be fast).
• Removes the need to keep around inactive TaskProxy objects (closes #987, #1689).
• Understands graph structure so can make informed decisions when it changes (closes #773, #774)
• Obsoletes/removes suicide triggering with branched workflows (closes #3226)
• Clean up the TaskProxy/TaskState/Prerequisite/Depdency/Output interaction (closes #2329)

Further desired benefits

• Supports subgraphs (closes #3226, #2668).
• Supports cycling within subgraphs (closes #2241).
• Abstracts cycling "drivers" allowing the following to be used as cycling "drivers":
  • Suite parameters.
  • External events (closes #3188).
  • RRULE datetime recurrences (closes #2398, #2382).
  • Dynamic collections (e.g. a suite parameter which can be changed whilst the suite is running e.g. via broadcast).
  • (Would need to close #2452 on route)

[hjoliver]

Another benefit:

• should be much easier for users to understand (currently the task pool model has to be understood to explain some aspects of workflow evolution and response to commands).

[matthewrmshin]

(Should we mark some of the issues mentioned above as superseded and close them down?)

[matthewrmshin]

(Can probably supersede #2329 as well.)

[oliver-sanders]

(Should we mark some of the issues mentioned above as superseded and close them down?)

I guess, maybe some of the ones in the first section?

(Can probably supersede #2329 as well.)

Good point, added.

[matthewrmshin]

993 was the original version of this issue!

[hjoliver]

update post merge of task-proxy based spawn on demand

With merge of #3515 Cylc now has "spawn on demand" but by a different method than suggested here, which required less extensive refactoring: task proxies simply record (during graph parsing) who depends on their outputs, and spawn them as outputs are completed. So there is still no explicit use of the graph at run time.

We should probably close this issue and replace it with several others:

• consider converting to the method suggest here on the Cylc 9 timescale?
• other enhancements suggested here - e.g. see "further desired benefits" above.