Thanks for the e-mail, Ben. I'm 100% behind this effort. The performance
benefits and the potential drop in CPU usage of OVN components is
absolutely worth it. I have some questions inline below with regards to
specific points you've brought up.
On 11/02/2018 01:44 PM, Ben Pfaff wrote:
I was asked in an OVN meeting to send out an email talking about what
we're working on to make ovn-northd and ovn-controller faster. Here's
my summary.
OVN is essentially a stack of compilers. At the top, the CMS dumps
some configuration into the northbound database (NDBB). Then:
1. ovn-northd centrally translates the high-level NBDB description
into logical flows in the southbound database (SBDB).
2. ovn-controller, on each HV, translates the SBDB logical flows
into "physical" (OpenFlow) flows for the local hypervisor and
passes them to ovs-vswitchd.
3. ovs-vswitchd translates OpenFlow flows into datapath flows on
demand as traffic appears.
Currently, OVN implements steps 1 and 2 with code that translates all
input to output in one go. When any of the input changes, it
re-translates all of it. This is fine for small deployments, but it
scales poorly beyond about 1000 hypervisors, at which point each
translation step begins to take multiple seconds. Larger deployments
call for incremental computation, in which a small change in the input
requires only a small amount of computation to yield a small change in
the output.
It is difficult to implement incremental computation in C. For
ovn-controller, two attempts have been made already. The first attempt,
in 2016, increased code complexity without similar benefit
(https://mail.openvswitch.org/pipermail/ovs-dev/2016-August/078272.html).
A recent approach, by Han Zhou shows a much bigger improvement, but it
also increases complexity greatly and definitely makes maintenance more
difficult.
Justin and I are proposing a new approach, based on an incremental
computation engine called Differential Datalog, or DDlog for short
(https://github.com/ryzhyk/differential-datalog). DDlog is open source
software developed at the VMware Research Group in Palo Alto by Leonid
Ryzhyk, Mihai Budiu, and others. It uses an underlying engine developed
by Frank McSherry at Microsoft Research, called Differential Dataflow
(https://github.com/frankmcsherry/differential-dataflow). Here's a talk
that Leonid gave on DDlog earlier this earlier:
https://ovsorbit.org/#e58
DDlog appears suitable for steps 1 and 2, that is, for both ovn-northd
and ovn-controller. Justin and I are starting with ovn-northd, because
it is a simpler case, and once we've arrived at some minimum amount of
success, Han is going to apply what we've learned to ovn-controller as
well. Leonid and Mihai have been working very closely with us (we have
literally been writing DDlog code in conference rooms in 90 minute
sessions with everyone clustered around laptops) and none of it could
happen without them.
Here's the process we'll need to follow to get DDlog to work with
ovn-northd:
* DDlog needs to be able to talk to OVSDB for input (reading data from
the northbound database) and output (writing data to the southbound
database). Therefore, we need to write OVSDB adapters for DDlog.
Leonid has already done an important part of this work. There is
more work to do plumbing the adapter into ovn-northd's database
connections.
Is this work in one of the repos you previously linked? If not, is there
somewhere we can find the WIP?
* We need to translate the C flow generation code in ovn-northd into
DDlog's domain specific language. There are some tricky parts to
this but we expect the bulk of it to be straightforward and probably
easier to read in DDlog than in C. We've started with the tricky
parts, which you can find at
https://github.com/ryzhyk/differential-datalog/blob/northd/test/ovn/ovn_northd.dl
Please don't take the code there as illustrative of what one would
typically see for flow generation, because as I said, these are the
hard parts.
Thanks for the code examples. Seeing sample DDlog is very nice, even if
it's not necessarily illustrative of what the final product will be.
For those of us doing work right now to add new features to OVN, how
should we approach the conversion to DDlog? As an example, I have some
multicast work in progress that will add some new northbound data. It
also introduces ovn-northd changes to generate logical flows and
southbound data.
My assumption is that I should focus 100% on the C implementation for
now. When should I consider adding the analogous DDlog changes?
Is there some sort of plan for how to keep DDlog up to date in the face
of new C development? For instance, would we implement a policy that
states that C changes will not be accepted without equivalent DDlog
changes? For this initial conversion, would we declare a C feature
freeze date that states that no new ovn-northd C changes may be added
after that date in order to give a stable feature set for DDlog conversion?
* The OVN build system will need some changes:
- The DDlog compiler, which translates .dl files into Rust, is
written in Haskell, so Haskell becomes an OVN build requirement
but not a runtime requirement. (If that's a problem, then we can
arrange to distribute the Rust output as well as the .dl input,
for situations where Haskell is not available.)
- OVN will require a Rust compiler at build time. Whatever
libraries Rust needs becomes runtime requirements.
- ovn-northd (and eventually ovn-controller) will link against the
Rust object files and call into DDlog through its external API.
* Initially, we plan to make DDlog optional. If Haskell and Rust are
available at configure and build time, ovn-northd will build in
support for DDlog. At ovn-northd runtime, command-line options will
control which implementation is used; we hope to make it possible to
run both in parallel to check for differences in behavior. After
the DDlog implementation is proven in practice, we hope to delete
the C implementation entirely.
It's a bit of a loaded question, but by what measure do we consider the
DDlog implementation to be proven in practice?
Until the C implementation is erased, should we expect to develop
features for both C and DDlog? Or should we expect to target new
features only for DDlog?
Happy to hear comments.
Ben
_______________________________________________
discuss mailing list
disc...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-discuss
_______________________________________________
discuss mailing list
disc...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-discuss
