[jboss-as7-dev] A strategy for mapping a directed dependency graph with transitives and cycles onto a DAG

[David M. Lloyd]

The problem: MSC services must form a DAG.  However, in several cases, 
the dependency information we are given is potentially cyclic and may 
also include transitive dependency information.

Currently we deal with cyclic dependencies by using a two-phase 
resolution strategy, however this strategy can only ever encompass one 
level of dependencies and cannot accommodate transitive dependencies at all.

This problem has come up in the following contexts:

1) EJB JNDI resolution where EJB A injects EJB B, but B in turn depends 
on EJB C: A does not receive a dependency on C though it should have.

2) Module dependency resolution where a dependency has an export from 
another module.  In this case the transitive dependency is also lost.

The Two-Phase Solution
----------------------
The two-phase solution works like this:

   +---------+   +---------+
   | Item A  |   | Item B  |
   | (Create)|   | (Create)|
   |         |   |         |
   +---------+   +-+-------+
       ^           ^   ^
       |  +--------+   |
       |  |            |
   +---+--+--+   +-----+---+
   | Item A  |   | Item B  |
   | (Start) |   | (Start) |
   |         |   |         |
   +---------+   +---------+

In this example A has a dependency on B.  In the create phase, we 
ascertain what the dependencies are for a given item.  In the start 
phase we establish dependencies on all of the create-phase services of 
our dependencies.

The problem with this solution has been outlined above.

The Three-Phase Solution
------------------------
Superficially, it would seem that the problems associated with the 
two-phase solution can be resolved by the use of three phases.  The 
initial phase would encapsulate the list of dependencies; the second 
phase would depend on the immediate dependencies and would encapsulate 
the set of immediate dependencies plus their immediate dependencies; and 
the third phase would come up only when all these dependencies are up.

For cases where there is no concept of transitivity, this may suffice. 
However it is the case in AS now where both the modules/class-path use 
case and the JNDI @Resource case do indeed include the concept of 
transitivity.

The N-Phase Solution
--------------------
The only way to ensure that some arbitrary set of transitive 
dependencies is available is by using a self-configuring N-phase 
mechanism.  The way this works is as follows.

1. We create a Create-phase service as today, which encodes as part of 
its value the set of immediate dependencies.  This would include the 
following behavior (pseudo-code):

    void start() {
       dependencies = immediate declared deps of this service
       if (dependencies is not empty) {
          create child service "resolver1";
          for each (d in dependencies) {
             add create phase of d to "resolver1" as dependency
          }
       } else {
          create child service "start";
       }
    }

2. Each resolver service has the following behavior:

    void start() {
       dependencies = set of all injected create-phase services
       if (dependencies is not empty) {
          create child service "resolver" + (n + 1);
          for each (d in dependencies) {
             for each (t in d.dependencies) {
                add create phase of t to "resolver" + (n + 1);
             }
          }
       } else {
          create child service "start";
       }
    }

This way, we retain the exact service structure we have today.  From an 
outside perspective the *create/*start services act just as they always 
have, except they accommodate transitive dependencies correctly by way 
of the "private" resolver dependencies.

This solution also has the advantage that it only creates as many 
services as necessary to resolve all transitive dependencies.

Optimization
------------
Because the transitive closure of services can be pretty hefty *and* may 
contain cycles, a good optimization would be to maintain a set of 
create-phase services that we've already depended on which we pass from 
resolver to resolver to ensure that we don't bother with redundant or 
cyclic dependencies.

Not Solved
----------
This solution does not address the problem where a dependency actually 
fails to start.  Assuming there is no @DependsOn to establish a direct 
acyclic dependency, the service will still start, but any attempt to use 
a failed dependency will in turn result in a failure just like today.

-- 
- DML