"Best Match" Conflict Manager

[Nascif Abousalh-Neto <Na...@sas.com>]

 
Hi,

In my company we are investigating how to use conflict managers and
eviction strategies in a large enterprise - and by large I mean hundreds
of modules and independent development teams.

The main problem we are facing is how to deal with multiple versions for
the same artifact selected over different paths in the dependency graph.
It seems that the maintenance problem could quickly scale out of
control. Imagine the following graph:


A->B
A->C
B->D
C->D

B and C can evolve their dependencies on D independently; but A has the
problem of choosing the versions of B and C, taking into consideration a
possible conflict when selecting version D.

Let's say that in the repository, we have the following configurations:
B v1.2 -> D v1.2
B v1.1 -> D v1.1

C v1.1 -> D v1.1
C v1.0 -> D v1.0

A can use static versions fo B and C. But as the size of the dependency
graph becomes larger, this becomes more and more of a problem as you
have to choose dependency versions based not only on its own merits, but
also on how compatible their entire dependency subgraph is with your
other dependencies. Imagine that instead of two you have ten
dependencies, each one with ten or so dependencies, and that the version
conflict is five levels removed from your level.

If A uses "latest" for his dependencies, we can either end up with
untested configurations (if we use the latest-revision strategy) or
build failures (if we use strict, which assumes that Ivy-474 is fixed). 

None of those two approaches is desirable; untested configurations (in
our example, C v1.1 using D v1.2) could lead to hard-to-debug errors at
runtime, even more so as the graph grows.

Build failures are better - fail early always is - but that moves us
back to the original scenario where A has the burden of experimenting
with dependency versions until it can find one that won't break.

One possible solution would be a conflict manager that automate the
manual process of finding the latest configuration that won't have
version conflicts. It could work by implementing a depth-first analysis
with backtrack capabilities (Prolog, anyone?) where the latest version
of a dependency would be selected by default, but if later a conflict
was detected with one of the dependencies it introduced, the conflict
manager would undo that selectio, pick the next one, and try again.

Or perhaps it could be solved with a breadth-search strategy, which
would probably be able to detect collisions earlier. But it would have
to hold a lot of state in memory (all the versions of all the modes)
which could become quite expensive.

Anyway, my questions are:
* Has anybody looked into this solution, or has a better idea of how to
deal with the problem I described?
* If I was to implement this conflict manager, could it be done based on
one of the two basic conflict managers (latest-cm and regexp-cm) or
would I have to create one from scratch? My guess is the second option,
but perhaps they can be tweaked to hold enough information to make the
decisions I described.

Thanks,
  Nascif

Re: "Best Match" Conflict Manager

[Xavier Hanin <xa...@gmail.com>]

On 8/31/07, Nascif Abousalh-Neto <Na...@sas.com> wrote:
>
>
> Hi,
>
> In my company we are investigating how to use conflict managers and
> eviction strategies in a large enterprise - and by large I mean hundreds
> of modules and independent development teams.
>
> The main problem we are facing is how to deal with multiple versions for
> the same artifact selected over different paths in the dependency graph.
> It seems that the maintenance problem could quickly scale out of
> control. Imagine the following graph:
>
>
> A->B
> A->C
> B->D
> C->D
>
> B and C can evolve their dependencies on D independently; but A has the
> problem of choosing the versions of B and C, taking into consideration a
> possible conflict when selecting version D.
>
> Let's say that in the repository, we have the following configurations:
> B v1.2 -> D v1.2
> B v1.1 -> D v1.1
>
> C v1.1 -> D v1.1
> C v1.0 -> D v1.0
>
> A can use static versions fo B and C. But as the size of the dependency
> graph becomes larger, this becomes more and more of a problem as you
> have to choose dependency versions based not only on its own merits, but
> also on how compatible their entire dependency subgraph is with your
> other dependencies. Imagine that instead of two you have ten
> dependencies, each one with ten or so dependencies, and that the version
> conflict is five levels removed from your level.
>
> If A uses "latest" for his dependencies, we can either end up with
> untested configurations (if we use the latest-revision strategy) or
> build failures (if we use strict, which assumes that Ivy-474 is fixed).
>
> None of those two approaches is desirable; untested configurations (in
> our example, C v1.1 using D v1.2) could lead to hard-to-debug errors at
> runtime, even more so as the graph grows.
>
> Build failures are better - fail early always is - but that moves us
> back to the original scenario where A has the burden of experimenting
> with dependency versions until it can find one that won't break.
>
> One possible solution would be a conflict manager that automate the
> manual process of finding the latest configuration that won't have
> version conflicts. It could work by implementing a depth-first analysis
> with backtrack capabilities (Prolog, anyone?) where the latest version
> of a dependency would be selected by default, but if later a conflict
> was detected with one of the dependencies it introduced, the conflict
> manager would undo that selectio, pick the next one, and try again.
>
> Or perhaps it could be solved with a breadth-search strategy, which
> would probably be able to detect collisions earlier. But it would have
> to hold a lot of state in memory (all the versions of all the modes)
> which could become quite expensive.
>
> Anyway, my questions are:
> * Has anybody looked into this solution, or has a better idea of how to
> deal with the problem I described?


The solution you describe seems to be very interesting and powerful, it's
not easy to implement though, and it may sometime be difficult to fix by
developers when they come into a situation where there is no possible match
(thus leading to a build failure if you apply the fail early strategy).

OTOH, using only tested configurations is too strict IMHO, unless you setup
tools to make compatibility tests automatically. This is something I've
already thought about, and Gilles also created an issue about making Ivy
help to test a set of dependencies versions depending on the ranges
expressed. From my experience, using versions which have not yet been tested
to be compatible with each other is ok at build time, because the
compatibility test is done in the module in which the dependencies versions
are selected. I agree bugs linked to incompatible versions may be difficult
to find at this time, and having a full description of compatible and
incompatible versions would be better, but it's not easy to get one, and it
may still contain problems.  Implementing a best match conflict manager
could still help to narrow down the number of possible incompatibility
cases, and thus would be interesting when leveraged by a high number of
users as in your case.

* If I was to implement this conflict manager, could it be done based on
> one of the two basic conflict managers (latest-cm and regexp-cm) or
> would I have to create one from scratch? My guess is the second option,
> but perhaps they can be tweaked to hold enough information to make the
> decisions I described.


Indeed, I don't think one of those will really help. Looking at their code
may help though, it will give you insights about what you need to develop.
Keep us informed of your progress about this if you can share more about it,
I think it could be something very interesting for the community.

Xavier


Thanks,
>   Nascif
>



-- 
Xavier Hanin - Independent Java Consultant
http://xhab.blogspot.com/
http://incubator.apache.org/ivy/
http://www.xoocode.org/