[ovs-git] [ovn-org/ovn] cd0642: ovn-northd-ddlog: Upgrade to ddlog 0.38.

Leonid Ryzhyk noreply at github.com
Fri May 21 05:23:04 UTC 2021


  Branch: refs/heads/master
  Home:   https://github.com/ovn-org/ovn
  Commit: cd064285214ef1b6b0a640ec84bb80c026a56a94
      https://github.com/ovn-org/ovn/commit/cd064285214ef1b6b0a640ec84bb80c026a56a94
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M NEWS
    M northd/lrouter.dl
    M northd/ovn-northd-ddlog.c

  Log Message:
  -----------
  ovn-northd-ddlog: Upgrade to ddlog 0.38.

Upcoming commits will use a new --intern-table option of ovsdb2ddlog,
so we need to upgrade to the version of ddlog that has that feature.

To do so, we need to adapt the code to language changes in ddlog.  This
commit does that for a change in 0.37 in which, when iterating over a
`Group` in a for-loop, the iterator returns `(value, weight)` tuples.

This also adapts ovn-northd-ddlog.c to a slightly updated C API.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 5c3b987b571e7aa41018888d7a35048caf09e2f9
      https://github.com/ovn-org/ovn/commit/5c3b987b571e7aa41018888d7a35048caf09e2f9
  Author: Ben Pfaff <blp at ovn.org>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Preserve NB_Global more carefully.

Dumitru reported in #openvswitch that ovn-northd-ddlog can discard the
setting of NB_Global.options:use_logical_dp_groups at startup.  I think
that this must be because it seems possible that at startup some of the
relations in the Out_NB_Global rule aren't populated yet, and yet
there is still a row in nb::NB_Global, so that neither rule for
Out_NB_Global matches and therefore ovn-northd-ddlog deletes the row.

This commit changes the structure of how ovn-northd-ddlog generates
Out_NB_Global to ensure that, if there's an input row, it always
generates exactly one output row.  This should be more robust than the
previous version regardless of whether it fixes the exact problem
that Dumitru observed (which I did not try to reproduce).

Reported-by: Dumitru Ceara <dceara at redhat.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 3f21890bff378c4cd5bd7570d003cfc1e28eb5d2
      https://github.com/ovn-org/ovn/commit/3f21890bff378c4cd5bd7570d003cfc1e28eb5d2
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lrouter.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Remove `lr` field from `Router`.

`relation Router` stores the internal representation of a logical
router, consisting of values from the `nb::Logical_Router` table
augmented with some additional fields.  We used to do this by
copying the entire `Logical_Router` record inside `Router`.  This
proved highly inefficient in scenarios where the set of router ports
changes frequently.  Every such change modifies the `ports` array
inside `Logical_Router`, which triggers an update of the `Router`
object, which can cause a bunch of rules to update their outputs.  This
recomputation is unnecessary as none of these rules look at the `ports`
field (`ports` is a slightly backwards way to maintain the relationship
between ports and routers by storing the array of ports in the router
instead of having each port point to the router).

As a workaround, we no longer store the entire `Logical_Router` object
in the `Router` table, and instead only copy its relevant fields.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: fa50861017d53928947bd6a6fdb52f9878607a4a
      https://github.com/ovn-org/ovn/commit/fa50861017d53928947bd6a6fdb52f9878607a4a
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lrouter.dl
    M northd/multicast.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern the `Router` table.

This is the first in a series of commits that will replace the use of
the DDlog's `Ref<>` type with `Intern<>` throughout the OVN code base.
`Ref` and `Intern` are the two forms of smart pointers supported by
DDlog at the moment.  `Ref` is a reference counted pointer.  Copying
a `Ref<>` simply increments its reference count.  `Intern<>` is an
interned object reference.  It guarantees that there exists exactly
one copy of each unique interned value.  Interned objects are slightly
more expensive to create, but they have several important advantages:
(1) they save memory by deduplicating identical values, (2) they allow
by-pointer comparisons, and (3) they avoid unnecessary recomputations
in some scenarios. See DDlog docs [1], [2] for more detail.

In this commit we change the type of records in the `Router` table from
`Ref<Router>` to `Intern<Router>`.  This reduces the amount of churn
and speeds up northd significantly in scenarios where the set of router
ports changes frequently, which triggers updates to
`nb::Logical_Router`, which in turn updates corresponding records
in the `Router` table.  Interning guarantees that these updates are
no-ops and do not trigger any other rules.

[1] https://github.com/vmware/differential-datalog/blob/master/doc/tutorial/tutorial.md#reference-type-ref
[2] https://github.com/vmware/differential-datalog/blob/master/doc/tutorial/tutorial.md#interned-values-intern-istring

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: a5549aaec8486143e5ed2745bdde31e2df99640a
      https://github.com/ovn-org/ovn/commit/a5549aaec8486143e5ed2745bdde31e2df99640a
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Workaround for slow group_by.

This patch is a workaround for a performance issue in the DDlog
compiler.  The issue will hopefully be resolved in a future version of
DDlog, but for now we need this and possibly a few other similar fixes.

Here is one affected rule:

```
sb::Out_Port_Group(._uuid = hash128(sb_name), .name = sb_name, .ports = port_names) :-
    nb::Port_Group(._uuid = _uuid, .name = nb_name, .ports = pg_ports),
    var port_uuid = FlatMap(pg_ports),
    &SwitchPort(.lsp = lsp at nb::Logical_Switch_Port{._uuid = port_uuid,
                                                   .name = port_name},
                .sw = &Switch{.ls = nb::Logical_Switch{._uuid = ls_uuid}}),
    TunKeyAllocation(.datapath = ls_uuid, .tunkey = tunkey),
    var sb_name = "${tunkey}_${nb_name}",
    var port_names = port_name.group_by((_uuid, sb_name)).to_set().
```

The first literal in the body of the rule binds variable `pg_ports` to
the array of ports in the port group.  This is a potentially large
array that immediately gets flattened by the `FlatMap` operator.
Since the `pg_ports` variable is not used in the remainder of the rule,
DDlog normally would not propagate it through the rest of the rule.
Unfortunately, due to a subtle semantic quirk, the behavior is different
when there is a `group_by` operator further down in the rule, in which
case unused variables are still propagated through the rule, which
involves expensive copies.

The workaround I implemented factors the first two terms in the
rule into a separate `PortGroupPort` relation, so that the ports array
no longer occurs in the new version of the rule:

```
sb::Out_Port_Group(._uuid = hash128(sb_name), .name = sb_name, .ports = port_names) :-
    PortGroupPort(.pg_uuid = _uuid, .pg_name = nb_name, .port = port_uuid),
    &SwitchPort(.lsp = lsp at nb::Logical_Switch_Port{._uuid = port_uuid,
                                                   .name = port_name},
                .sw = &Switch{.ls = nb::Logical_Switch{._uuid = ls_uuid}}),
    TunKeyAllocation(.datapath = ls_uuid, .tunkey = tunkey),
    var sb_name = "${tunkey}_${nb_name}",
    var port_names = port_name.group_by((_uuid, sb_name)).to_set().
```

Again, benchmarking is likely to reveal more instances of this.  A
proper fix will require a change to the DDlog compiler.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 12fe31f101bb3dad43f040223d84d79a53c22110
      https://github.com/ovn-org/ovn/commit/12fe31f101bb3dad43f040223d84d79a53c22110
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lswitch.dl
    M northd/multicast.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern the Switch table.

Change the type of record in the `Switch` table from `Ref<Switch>` to
`Intern<Switch>`.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 053a8385237001185ea8bb6d0769e57aa5225254
      https://github.com/ovn-org/ovn/commit/053a8385237001185ea8bb6d0769e57aa5225254
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/ipam.dl
    M northd/lswitch.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Remove `ls` field from `Switch`.

This commit is analogous to 076749c99, but switches instead of routers.

`relation Switch` stores the internal representation of a logical
switch, consisting of values from the `nb::Logical_Switch` table
augmented with some additional fields.  We used to do this by
copying the entire `Logical_Switch` record inside `Switch`.  This
proved highly inefficient in scenarios where some of the entities that
`Logical_Switch` references (logicl switch ports, ACLs, or QoS rules)
change frequently.  Every such change modifies the `Logical_Switch`
record, which triggers an update of the `Switch` object, which can cause
a bunch of rules to update their outputs.

As a workaround, we no longer store the entire `Logical_Switch` object
in the `Switch` table, and instead only copy its relevant fields.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 9aaa08d74ed95e9fb6f50ca9c63c6ccb018b32a4
      https://github.com/ovn-org/ovn/commit/9aaa08d74ed95e9fb6f50ca9c63c6ccb018b32a4
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/ipam.dl
    M northd/lswitch.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern the SwitchPort table.

Change the type of record in the `SwitchPort` table from
`Ref<SwitchPort>` to `Intern<SwitchPort>`.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: e516877c9dcdb18c977be3a986f459de3eae09aa
      https://github.com/ovn-org/ovn/commit/e516877c9dcdb18c977be3a986f459de3eae09aa
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lrouter.dl
    M northd/lswitch.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern the RouterPort table.

Change the type of record in the `RouterPort` table from
`Ref<RouterPort>` to `Intern<RouterPort>`.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 9c62a72d76ceb992dec5b608906253e9c86ac0d3
      https://github.com/ovn-org/ovn/commit/9c62a72d76ceb992dec5b608906253e9c86ac0d3
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lswitch.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Remove unused function.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 4a48effe0db0ba86026bd29e105cd6dbf12596b0
      https://github.com/ovn-org/ovn/commit/4a48effe0db0ba86026bd29e105cd6dbf12596b0
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/helpers.dl
    M northd/lrouter.dl
    M northd/lswitch.dl
    M northd/multicast.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Eliminate remaining Ref's.

Change all remaining occurrences of `Ref<T>` to `Intern<T>` throughout
the DDlog code base.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 7b93dfc5a9f980c646f166ab1b21c985695d1d40
      https://github.com/ovn-org/ovn/commit/7b93dfc5a9f980c646f166ab1b21c985695d1d40
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/ipam.dl
    M northd/multicast.dl
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Eliminate redundant dereferences.

We eliminate an anti-pattern in the use of smart pointers that occurred
throughout the DDlog code.

Consider relation `A` that contains field `x` wrapped in a DDlog smart
pointer (`Intern<>` or `Ref<>`):

```
relation A(x: Intern<T>, ...)
```

Here `T` might be a complex type with dynamically allocated fields like
vectors and maps, etc.  Here is how _not_ to use this relation in a
rule:

```
Rel(...) :- A(.x = &v),
            B(v.field1),
            C(v.field2).
```

The `&v` syntax here extracts the inner value that the smart pointer
points to and binds it to variable `v`.  Thus, the type of `v` is `T`
and we thread the value of `T` through the entire rule, which requires
creating two more copies of it (types not wrapped in smart pointers are
copied by value).  This is a waste of memory and CPU and is completely
unnecessary, as we can instead bind `v` to the value of the smart
pointer, so it can be copied efficiently:

```
Rel(...) :- A(.x = v),  // type of `v` is `Intern<T>`.
            B(v.field1),
            C(v.field2).
```

The inefficient usage if a leftover from the days when DDlog had some
awkward restrictions on the use of smart pointers.

Note that `&` is still useful and does not incur any overhead when used
to deconstruct an object wrapped in a smart pointer and refer to its
fields, e.g.:

```
Rel(...) :- // Bind `f1` and `f2` to `x.field1` and `x.field2`;
            // filter out records where `field3` is `false`.
            A(.x = &T{.field1 = f1, .field2 = f2, .field3 = true}),
            B(f1),
            C(f2).
```

On top of this, the `@` operator can be used to simultaneously bind the
entire value stored in `x` and its individual fields.

```
Rel(...) :- // Bind `v` to the value of field `x` (`v: Intern<T>`);
            // bind `f2` to `x.field2`; filter on the value of `field3`.
            A(.x = v @ &T{.field2 = f2, .field3 = true}),
            B(v.field1),
            C(f2).
```

The `&` in this rule is used to deconstruct the value inside the smart
pointer; however since the binding operator `@` preceeds `&`, we bind
`v` to the value of the smart pointer and not the type that it wraps.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: e56c27cb67c5539a372222a57fc708aac15987de
      https://github.com/ovn-org/ovn/commit/e56c27cb67c5539a372222a57fc708aac15987de
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/helpers.dl
    M northd/lrouter.dl
    M northd/lswitch.dl
    M northd/ovn-nb.dlopts
    M northd/ovn-sb.dlopts
    M northd/ovn_northd.dl
    M northd/ovsdb2ddlog2c

  Log Message:
  -----------
  ovn-northd-ddlog: Intern selected input relations.

DDlog 0.38.0 adds the `--intern-table` CLI flag to the `ovsdb2ddlog`
compiler to declare input tables coming from OVSDB as `Intern<...>`.
This is useful for tables whose records are copied around as a whole and
can therefore benefit from interning performance- and memory-wise.  In
the past we had to create separate tables in `helpers.dl` and copy
records from the original input table to them while wrapping them in
`Intern<>`.  With this change, we avoid the extra copy and intern
records as we ingest them for selected tables.

We use the `--intern-table` flag to eliminate all intermediate tables in
`helpers.dl`.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: cd84d5ee57d3da810d1b226c492840e82b44204b
      https://github.com/ovn-org/ovn/commit/cd84d5ee57d3da810d1b226c492840e82b44204b
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/helpers.dl
    M northd/lrouter.dl
    M northd/lswitch.dl
    M northd/multicast.dl
    M northd/ovn-nb.dlopts
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern nb::Logical_Router_Port.

Use the `--intern-table` switch to intern `Logical_Router_Port` records,
so that they can be copied and compared efficiently by pointer.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: 46427eecfea9f7447644c9ce6d1d50360a49936a
      https://github.com/ovn-org/ovn/commit/46427eecfea9f7447644c9ce6d1d50360a49936a
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/helpers.dl
    M northd/lrouter.dl
    M northd/lswitch.dl
    M northd/multicast.dl
    M northd/ovn-nb.dlopts
    M northd/ovn_northd.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Intern nb::Logical_Switch_Port.

Use the `--intern-table` switch to intern `Logical_Switch_Port` records,
so that they can be copied and compared efficiently by pointer.

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


  Commit: dd333dceca36b0f9bbfb7c1e8eedb59ea8e53db8
      https://github.com/ovn-org/ovn/commit/dd333dceca36b0f9bbfb7c1e8eedb59ea8e53db8
  Author: Leonid Ryzhyk <lryzhyk at vmware.com>
  Date:   2021-05-20 (Thu, 20 May 2021)

  Changed paths:
    M northd/lrouter.dl

  Log Message:
  -----------
  ovn-northd-ddlog: Remove Router.static_routes.

This is another instance of a performance bug when a change to a
router object forces a cascade of changes to relations that reference
the object.  This time around the problem was caused by the
`Router.static_routes` field, which is copied from
`nb::Logical_Router`.  Luckily, this field was only used in one rule
and was easy to remove.

Here is how we diagnosed the issue (this may be useful for posterity):

- We started with a benchmark that executed several hundreds of similar
  transactions (in this case, these transactions were adding new router
  ports).  We recorded execution of the benchmark in a DDlog command
  file (replay.txt) and added `timestamp;` commands after each
  transaction in the file.

- Run `make NORTHD_CLI=1` to generate the ovn_northd_cli executable and
  use it to execute the command file:
  ```
  ./ovn_northd_ddlog/target/release/ovn_northd_cli -w 1  < replay.txt > replay.dump
  ```

- Extract only the timestamps from replay.dump and plot differences
  between successive timestamps (i.e., individual transaction times).
  I use gnumeric.  It would be nice to have some automation for this
  in the future.  We observe that one of the transactions in the
  benchmark loop slows down linearly as the size of the network
  topology grows:
  https://gist.github.com/ryzhyk/16a5607b280ed9cd09b176d6816cb4f0
  Clearly some of the rules in the program are getting more expensive
  as the number of ports goes up.  Another interesting observation is
  that the size of the delta output at each iteration of the benchmark
  remains constant (the delta mostly consists of new network flows).
  This suggests that whatever extra work DDlog is doing at each
  iteration might be redundant.

- To identify where the wasted work happens, we re-compile the program
  passing the `--output-internal-relations` flag to DDlog, which tells it
  to dump changes to all intermediate relations, not just output
  relation.  We replay the trace again.  We locate the expensive
  transaction in the log and compare its output from one of the first
  iterations vs one from the end of the log.  We now see a whole bunch of
  intermediate relations that only had a few modified records in the
  first transaction versus hundreds in the second one.  We further
  observe that all of these changes simply update the `static_routes`
  field (as explained above).

- After removing the field, we observe that changes to intermediate
  relations no longer grow with the topology, and transaction timing
  increases much more slowly:
  https://gist.github.com/ryzhyk/d02784b9088d82f8549ea1b2ebdf095e

Signed-off-by: Leonid Ryzhyk <lryzhyk at vmware.com>
Signed-off-by: Ben Pfaff <blp at ovn.org>
Acked-by: Mark Michelson <mmichelson at redhat.com>


Compare: https://github.com/ovn-org/ovn/compare/849ef6ae2a30...dd333dceca36


More information about the git mailing list