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

[Scott Marlow]

On 11/27/2012 11:22 AM, David M. Lloyd wrote:
> 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.

I understand what you said in this email about (1) but I'm not 100% sure 
I'm in sync with you about (2).  Are you proposing a MCS change to solve 
(2) module dependency resolution?

Also, I'm not sure if you meant "from" like you said in the (2) case. 
Should that be where a dependency has an export on another module?

>
> 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.
>