[ovs-dev] [PATCH v2 14/26] ovn-northd-ddlog: Workaround for slow group_by.

Ben Pfaff blp at ovn.org
Thu Apr 1 23:20:56 UTC 2021


From: Leonid Ryzhyk <lryzhyk at vmware.com>

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>
---
 northd/ovn_northd.dl | 19 +++++++++++++------
 1 file changed, 13 insertions(+), 6 deletions(-)

diff --git a/northd/ovn_northd.dl b/northd/ovn_northd.dl
index 80d8598bd7dc..5a7a11295964 100644
--- a/northd/ovn_northd.dl
+++ b/northd/ovn_northd.dl
@@ -712,11 +712,10 @@ sb::Out_Address_Set(._uuid = hash128("svc_monitor_mac"),
     SvcMonitorMac(svc_monitor_mac).
 
 sb::Out_Address_Set(hash128(as_name), as_name, pg_ip4addrs.union()) :-
-    nb::Port_Group(.ports = pg_ports, .name = pg_name),
+    PortGroupPort(.pg_name = pg_name, .port = port_uuid),
     var as_name = pg_name ++ "_ip4",
     // avoid name collisions with user-defined Address_Sets
     not nb::Address_Set(.name = as_name),
-    var port_uuid = FlatMap(pg_ports),
     PortStaticAddresses(.lsport = port_uuid, .ip4addrs = stat),
     SwitchPortNewDynamicAddress(&SwitchPort{.lsp = nb::Logical_Switch_Port{._uuid = port_uuid}},
                                 dyn_addr),
@@ -738,11 +737,10 @@ sb::Out_Address_Set(hash128(as_name), as_name, set_empty()) :-
     not nb::Address_Set(.name = as_name).
 
 sb::Out_Address_Set(hash128(as_name), as_name, pg_ip6addrs.union()) :-
-    nb::Port_Group(.ports = pg_ports, .name = pg_name),
+    PortGroupPort(.pg_name = pg_name, .port = port_uuid),
     var as_name = pg_name ++ "_ip6",
     // avoid name collisions with user-defined Address_Sets
     not nb::Address_Set(.name = as_name),
-    var port_uuid = FlatMap(pg_ports),
     PortStaticAddresses(.lsport = port_uuid, .ip6addrs = stat),
     SwitchPortNewDynamicAddress(&SwitchPort{.lsp = nb::Logical_Switch_Port{._uuid = port_uuid}},
                                 dyn_addr),
@@ -771,9 +769,18 @@ sb::Out_Address_Set(hash128(as_name), as_name, set_empty()) :-
  * SB Port_Group.name uniqueness constraint, ovn-northd populates the field
  * with the value: <SB.Logical_Datapath.tunnel_key>_<NB.Port_Group.name>.
  */
+
+relation PortGroupPort(
+    pg_uuid: uuid,
+    pg_name: string,
+    port: uuid)
+
+PortGroupPort(pg_uuid, pg_name, port) :-
+    nb::Port_Group(._uuid = pg_uuid, .name = pg_name, .ports = pg_ports),
+    var port = FlatMap(pg_ports).
+
 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),
+    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}}),
-- 
2.29.2



More information about the dev mailing list