[PATCH] circular dependency check speedup

[Glenn Herteg]

Nagios has historically used a very inefficient algorithm to check
for circular host and service dependencies, with respect to both
execution and notification dependencies.  This area has been the
subject of previous patches to improve performance.  For example,
in early 2008, a depth-first-search algorithm was proposed for
part of this checking, and it was eventually incorporated into
the standard code base.  However, that only affected part of the
circular-dependency-check algorithm, and performance against tens
of thousands of dependencies has still been extremely slow (taking
tens of minutes for a very large configuration).

GroundWork Open Source has looked at this problem with an eye
toward full optimization, and hereby provides a patch to fix
the remaining sources of poor performance.  The changes here are
not just theoretical; they have been tested against a very large
customer configuration, both with and without seeding a number of
actual circular dependencies, to demonstrate that the same errors
are caught as with the original code.  The replacement algorithm in
this patch provides a speedup of around 20,000x for that portion of
a pre-flight or reload operation, for a configuration with a very
large number of host or service dependencies.  This translates to
an overall speedup of about 275x with our large test dataset, for
a complete preflight operation.  In simpler terms, many minutes of
computation dissolve away into just a few seconds.

Given the timing improvements just noted, it is GroundWork's belief
that application of this patch will completely obsolete the nagios
-x and --dont-verify-paths ("Don't check for circular object paths")
options.

The replacement algorithm works in three ways:  by using substitute
data structures which can be operated on much more efficiently, by
sidestepping huge amounts of pointless work, and by optimizing the
placement of fields within certain existing data structures so that
more efficient assembly code is generated for the most commonly used
field accesses.  All of the modifications have been carefully tested
using actual measurements to show that they do improve execution
time, so the field-placement changes (for instance) are not based
on capricious guesswork.

To avoid impacting the rest of the Nagios code outside of the
circular dependency checks, the original dependency list structures
are restored after the replacement algorithm has done its checking.
We have not investigated whether keeping the replacement data
structures around for later use instead of the original dependency
lists might afford additional operating speedup, though that is
perhaps a possibility.

As provided, the attached patch file is suitable for direct
application to the Nagios 3.2.3 source code.

Glenn

-------------- next part --------------
A non-text attachment was scrubbed...
Name: nagios-3.2.3-circular-dependency-analysis.patch
Type: text/x-patch
Size: 18624 bytes
Desc: not available
URL: <https://www.monitoring-lists.org/archive/developers/attachments/20101215/e1594edb/attachment.bin>
-------------- next part --------------
------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
-------------- next part --------------
_______________________________________________
Nagios-devel mailing list
Nagios-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/nagios-devel