[ovs-dev] ovn-controller CPU use and incremental processing dependencies

Ben Pfaff blp at ovn.org
Thu Jun 7 18:15:23 UTC 2018

To review the problem we're trying to solve, ovn-controller uses too
much CPU in many circumstances because it recomputes everything on every
iteration on the main loop.  That includes when it wakes up for any
reason, e.g. in response to a timer, or to an "ovs-appctl" command, or
to respond to an "echo request" probing whether an OpenFlow or OVSDB
connection is still up.  In even a medium-sized network, this is a lot
of work and can easily lead to ovn-controller using 100% of a CPU
without doing significant valuable work.

The solution, as you and others have noticed, is to recompute only when
an input has changed.  This can be done on at least three different

1. Whole system.  Recompute everything if any input changed.

2. Coarsely granular.  Recompute intermediate data and output data, coarsely
   defined, if their respective inputs changed.

3. Finely granular.  Recompute individual rows (etc.) of intermediate or output
   data if their individual inputs changed.

The 2016 patches from Ryan Moats were mostly #1 with some #2, and, Han,
as I see it your patch series is mostly #2 with some #3.

Ryan Moats' series was eventually reverted because it was not correct and could
not be confidently fixed or maintained.  In turn, this was because it was too
difficult to figure out each calculation's actual dependencies.  This was in
fact difficult even for #1, let alone #2.

Your new patch series uses a much more systematic approach to
dependencies, since it uses a formal incremental processing engine to
propagate changes through a DAG of computations.  However, assuming that
it is correct as is, I am concerned that it will eventually suffer from
the same problem.

The way I see it, the incremental computation systems that have been proposed
so far are analogous to a Makefile that explicitly lists all of the .h files
that each .c file includes (directly or indirectly).  If you've ever maintained
a Makefile that works this way, you know that it's difficult to get it right at
the start and that it is essentially impossible to keep it correct as a project
evolves.  That's why every modern build system computes header file
dependencies automatically as a side effect of compilation.  Similarly, I don't
see a realistic way that we can keep these dependencies correct as
ovn-controller evolves.

So, I've been spending some time thinking about how we can come up with the
ovn--controller equivalent of automatic dependency computation.  My current
thinking is that we need to adopt a more functional programming attitude here.
That is, any given part of the ovn-controller computation should only be passed
as input the data that it actually needs, and as output the data structures
that it produces.  This will give us the opportunity to make sure that the
input and the dependencies are in sync.  Ideally, we'd be able to tie those
together in the code, so that passing a piece of data into a computation
function automatically makes that a dependency from the engine's perspective.

Currently, we're pretty far from being able to do this.  Most of the state
computation functions in ovn-controller receive pointers to the OVSDB and OVNSB
IDLs (via struct controller_ctx), which means that they can read and write
anything in any part of those databases, and even if they don't now it's easy
to carelessly add new ones.  To pass only a function's actual dependencies into
it, we will need to pass, at a minimum, individual tables into a function
rather than entire databases.  This is more difficult than it sounds, because
the OVSDB IDL doesn't have a way to pass around a table.  Thus, some steps to
take here, starting from the easiest:

1. Add some ability for the IDL to pass around tables.  Exact mechanism not
   obvious yet.

2. Add some ability for the IDL to pass just part of a table, e.g. specific
   columns, to make dependencies more specific.  This would also make it
   possible to control dependencies related to hopping from one table to
   another via pointers in the table's columns.

(Not every input comes from an OVSDB instance.  Other input sources tend to be
easier to deal with.  I don't know of specific problems there yet.)

There's another issue related to OVSDB.  Currently ovn-controller only composes
OVSDB transactions when there is not already a transaction in flight.  This
causes trouble for the interaction between some parts of ovn-controller that
only do their work when they can compose a transaction and parts that need to
keep track of individual changes in tables ("change tracking") because change
tracking only keeps the changes for a single main loop iteration.  Thus, change
tracking changes can be missed if there's a transaction outstanding.  It seems
like there should be a way to solve this problem by always allowing a
transaction to be composed (and probably just discarding the transaction in
some cases).

I'm currently working on step #1 above, to make dependencies easier to track by
passing individual tables into functions.  At that point, I think that the
incremental processing engine makes a lot of sense.

More information about the dev mailing list