On Tue, Jun 29, 2021 at 03:32:26PM -0700, Ben Pfaff wrote:
> On Mon, Jun 28, 2021 at 05:40:53PM +0200, Dumitru Ceara wrote:
> > On 5/20/21 5:50 PM, Ben Pfaff wrote:
> > > On Thu, May 20, 2021 at 05:06:26PM +0200, Dumitru Ceara wrote:
> > >> On 4/7/21 6:49 PM, Ben Pfaff wrote:
> > >>
> > >> [...]
> > >>
> > >>>>
> > >>>> Thanks! I can download them now. It's back on my to-do list.
> > >>>
> > >>> I can reproduce the problem now. I haven't fixed it yet, but I did fix
> > >>> a nasty performance problem in ovn-nbctl that became really apparent
> > >>> when working with your databases:
> > >>> https://mail.openvswitch.org/pipermail/ovs-dev/2021-April/381909.html
> > >>
> > >> I was wondering if you had a chance to look at this since.
> > >
> > > I haven't kept going. I consider my series that gives a 5x performance
> > > improvement a kind of checkpoint along the way. I assumed at first that
> > > it would get reviewed quickly so I could move on to other things, but no
> > > one has looked at it yet.
> > >
> >
> >
> > Hi Ben,
> >
> > Just a note, I've tried this again with ovn-northd-ddlog built from
> > current OVN master branch, running against the same DBs:
>
> I've identified the problem. It's because of the ReachableLogicalRouter
> relation, which holds all pairs of routers (A,B) such that a packet at
> router A can transit switches and rotuers to arrive at router B. This
> is inherently O(n**2) and in this example n is about 8,000.
>
> I'll fix it.
The following is pretty close, but I see three test failures I need to
investigate:
273: ovn.at:11253 ovn -- vlan traffic for external network with
distributed router gateway port -- ovn-northd-ddlog -- dp-groups=yes
641: ovn.at:26903 ovn -- proxy-arp: 1 HVs, 1 LSs, 1 lport/LS, 1 LR
-- ovn-northd-ddlog -- dp-groups=yes
proxy-arp
642: ovn.at:26903 ovn -- proxy-arp: 1 HVs, 1 LSs, 1 lport/LS, 1 LR
-- ovn-northd-ddlog -- dp-groups=no
proxy-arp
-8<--------------------------cut here-------------------------->8--
From: Ben Pfaff <[email protected]>
Date: Wed, 30 Jun 2021 11:57:46 -0700
Subject: [PATCH ovn] ovn-northd-ddlog: Avoid N**2 blowup for N connected
logical routers.
It's easy to implement "connected components" in raw DDlog, but it
takes N**2 time and space in the number of elements in a component.
This was a huge waste for a test case supplied by Dumitru Ceara that
had over 8000 logical routers. This commit solves the problem by using
the "graph" transformer built in DDlog, which efficiently implements
connected components.
Signed-off-by: Ben Pfaff <[email protected]>
Reported-by: Dumitru Ceara <[email protected]>
Reported-at:
https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html
---
northd/lrouter.dl | 38 ++++++++++++++++++++++----------------
northd/ovn_northd.dl | 4 +++-
2 files changed, 25 insertions(+), 17 deletions(-)
diff --git a/northd/lrouter.dl b/northd/lrouter.dl
index ff9dc9844ffc..85c07716bb12 100644
--- a/northd/lrouter.dl
+++ b/northd/lrouter.dl
@@ -14,6 +14,7 @@
import OVN_Northbound as nb
import OVN_Southbound as sb
+import graph as graph
import multicast
import ovsdb
import ovn
@@ -95,26 +96,31 @@ LogicalSwitchRouterPort(lsp, lsp_router_port, ls) :-
&nb::Logical_Switch_Port(._uuid = lsp, .__type = "router", .options =
options),
Some{var lsp_router_port} = options.get("router-port").
+/* Undirected edges connecting one router and another.
+ * This is a building block for ConnectedLogicalRouter. */
+relation LogicalRouterEdge(a: uuid, b: uuid)
+LogicalRouterEdge(a, b) :-
+ FirstHopLogicalRouter(a, ls),
+ FirstHopLogicalRouter(b, ls),
+ a <= b.
+LogicalRouterEdge(a, b) :- PeerLogicalRouter(a, b).
+function edge_from(e: LogicalRouterEdge): uuid = { e.a }
+function edge_to(e: LogicalRouterEdge): uuid = { e.b }
+
/*
- * Reachable routers.
+ * Sets of routers such that packets can transit directly or indirectly among
+ * any of the routers in a set. Any given router is in exactly one set.
*
- * Each row in the relation indicates that routers 'a' and 'b' can reach each
- * other directly or indirectly through any chain of logical routers and
- * switches.
+ * Each row (set, elem) identifes the membership of router with UUID 'elem' in
+ * set 'set', where 'set' is the minimum UUID across all its elements.
*
- * This relation is symmetric: if (a,b) then (b,a).
- * This relation is reflexive: (a,a) is always true.
+ * We implement this using the graph transformer because there is no
+ * way to implement "connected components" in raw DDlog that avoids O(n**2)
+ * blowup in the number of nodes in a component.
*/
-relation ReachableLogicalRouter(a: uuid, b: uuid)
-ReachableLogicalRouter(a, b), ReachableLogicalRouter(a, a),
ReachableLogicalRouter(b, b) :-
- PeerLogicalRouter(a, b).
-ReachableLogicalRouter(a, b), ReachableLogicalRouter(a, a),
ReachableLogicalRouter(b, b) :-
- FirstHopLogicalRouter(a, ls),
- FirstHopLogicalRouter(b, ls),
- a != b.
-ReachableLogicalRouter(a, b) :-
- ReachableLogicalRouter(a, c), a != c,
- ReachableLogicalRouter(c, b), b != c.
+relation ConnectedLogicalRouter[(uuid, uuid)]
+apply graph::ConnectedComponents(LogicalRouterEdge, edge_from, edge_to)
+ -> (ConnectedLogicalRouter)
// ha_chassis_group and gateway_chassis may not both be present.
Warning[message] :-
diff --git a/northd/ovn_northd.dl b/northd/ovn_northd.dl
index 52a6206a186c..61055c0c205d 100644
--- a/northd/ovn_northd.dl
+++ b/northd/ovn_northd.dl
@@ -498,7 +498,9 @@ sb::Out_Port_Binding(._uuid = pbinding._uuid,
* chassis. RefChassisSet has a row for every logical router. */
relation RefChassis(lr_uuid: uuid, chassis_uuid: uuid)
RefChassis(lr_uuid, chassis_uuid) :-
- ReachableLogicalRouter(lr_uuid, lr2_uuid),
+ LogicalRouterHAChassisGroup(lr_uuid, _),
+ ConnectedLogicalRouter[(lr_uuid, set_uuid)],
+ ConnectedLogicalRouter[(lr2_uuid, set_uuid)],
FirstHopLogicalRouter(lr2_uuid, ls_uuid),
LogicalSwitchPort(lsp_uuid, ls_uuid),
&nb::Logical_Switch_Port(._uuid = lsp_uuid, .name = lsp_name),
--
2.31.1
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
