| Message ID | 20210702005640.1627098-1-blp@ovn.org |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] ovn-northd-ddlog: Avoid N**2 blowup for N connected logical routers. | expand |
| Context | Check | Description |
|---|---|---|
| ovsrobot/apply-robot | success | apply and check: success |
| ovsrobot/github-robot | success | github build: passed |
On 7/2/21 2:56 AM, Ben Pfaff wrote: > 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 <blp@ovn.org> > Reported-by: Dumitru Ceara <dceara@redhat.com> > Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html > --- > All the tests pass with this for me now, as long as > https://patchwork.ozlabs.org/project/ovn/patch/20210701124521.2095748-1-numans@ovn.org/ > and > https://patchwork.ozlabs.org/project/ovn/patch/20210702005509.1626937-2-blp@ovn.org/ > are applied to fix pre-existing issues. > This is very neat! And it seems to work fine: Acked-by: Dumitru Ceara <dceara@redhat.com> Thanks, Dumitru
On Fri, Jul 02, 2021 at 04:30:52PM +0200, Dumitru Ceara wrote: > On 7/2/21 2:56 AM, Ben Pfaff wrote: > > 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 <blp@ovn.org> > > Reported-by: Dumitru Ceara <dceara@redhat.com> > > Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html > > --- > > All the tests pass with this for me now, as long as > > https://patchwork.ozlabs.org/project/ovn/patch/20210701124521.2095748-1-numans@ovn.org/ > > and > > https://patchwork.ozlabs.org/project/ovn/patch/20210702005509.1626937-2-blp@ovn.org/ > > are applied to fix pre-existing issues. > > > > This is very neat! And it seems to work fine: > > Acked-by: Dumitru Ceara <dceara@redhat.com> Thanks! I applied this to master. I decided to translate your "seems to work fine" into Tested-by, by the way.
On 7/2/21 7:24 PM, Ben Pfaff wrote: > On Fri, Jul 02, 2021 at 04:30:52PM +0200, Dumitru Ceara wrote: >> On 7/2/21 2:56 AM, Ben Pfaff wrote: >>> 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 <blp@ovn.org> >>> Reported-by: Dumitru Ceara <dceara@redhat.com> >>> Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html >>> --- >>> All the tests pass with this for me now, as long as >>> https://patchwork.ozlabs.org/project/ovn/patch/20210701124521.2095748-1-numans@ovn.org/ >>> and >>> https://patchwork.ozlabs.org/project/ovn/patch/20210702005509.1626937-2-blp@ovn.org/ >>> are applied to fix pre-existing issues. >>> >> >> This is very neat! And it seems to work fine: >> >> Acked-by: Dumitru Ceara <dceara@redhat.com> > > Thanks! I applied this to master. I decided to translate your "seems > to work fine" into Tested-by, by the way. > Sure, that's what I meant, I tested it with the DB I used in the report. :)
diff --git a/northd/lrouter.dl b/northd/lrouter.dl index 6c25b1ca9a93..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,27 +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) :- - PeerLogicalRouter(a, c), - ReachableLogicalRouter(c, b). -ReachableLogicalRouter(a, b) :- - FirstHopLogicalRouter(a, ls), - FirstHopLogicalRouter(b, ls). -ReachableLogicalRouter(a, b) :- - ReachableLogicalRouter(a, c), - ReachableLogicalRouter(c, b). -ReachableLogicalRouter(a, a) :- ReachableLogicalRouter(a, _). +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 9f18ace1c8b5..bd3c7f891f2e 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),
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 <blp@ovn.org> Reported-by: Dumitru Ceara <dceara@redhat.com> Reported-at: https://mail.openvswitch.org/pipermail/ovs-dev/2021-June/384519.html --- All the tests pass with this for me now, as long as https://patchwork.ozlabs.org/project/ovn/patch/20210701124521.2095748-1-numans@ovn.org/ and https://patchwork.ozlabs.org/project/ovn/patch/20210702005509.1626937-2-blp@ovn.org/ are applied to fix pre-existing issues. northd/lrouter.dl | 39 ++++++++++++++++++++++----------------- northd/ovn_northd.dl | 4 +++- 2 files changed, 25 insertions(+), 18 deletions(-)