Implement parallel DAG walking

[bschaatsbergen]

Resource reconciliation currently happens sequentially, which creates a bottleneck for complex graphs. Many resources are independent of each other, yet they are processed one by one because the existing walker enforces sequential execution. This limits throughput and increases processing times unnecessarily.

A simpler approach could be to rely on levelled topological execution and push all resources at the same level into an apply set. Each apply set would contain only the nodes that are ready to be processed in parallel, while still respecting all dependency guarantees. This avoids introducing a fully separate concurrent DAG walker, but still allows independent resources to be applied concurrently within each level.

Before moving forward, it would be useful to discuss how people typically write RGDs and wire up dependencies. This will help us understand patterns and ensure that applying resources in parallel preserves expected behavior.

[bschaatsbergen]

I'm actively working on a prototype and KREP for this.

[jakobmoellerdev]

I seriously think this will require something like a levelled concurrency algorithm that does not introduce a walking state. I dont want to reinvent the wheel here and there are estbalished algorithms for doing this.

PTAL at the Coffman–Graham algorithm and Kahn's algorithm.

Assuming

    A
   / \
  B   C
   \ /
    D
    |
    E

You can layer them as

L4: [E]
L3: [D]
L2: [B]
L1: [A C]

so that

         E     | L4
         |     |
         D     | L3
        / \
       /   \
      B     C | L2
       \   /
        \ /
         A    | L1

[jakobmoellerdev]

/assign @bschaatsbergen

thanks for taking a look!

[tjamet]

I agree, applying resources in parallel is something we should be doing.
We though need to take into consideration that users may expect the current sequential order as I interpret #744
We should probably issue a "deprecation notification" ahead of time with suggested actions to properly configure the dependency DAG