On Fri, Mar 24, 2023 at 7:22 AM Ilya Maximets <i.maxim...@ovn.org> wrote: > > On 3/24/23 14:33, Ilya Maximets wrote: > > On 3/21/23 13:24, Ilya Maximets wrote: > >> On 3/20/23 23:31, Han Zhou wrote: > >>> > >>> > >>> On Mon, Mar 20, 2023 at 3:37 AM Ilya Maximets <i.maxim...@ovn.org <mailto:i.maxim...@ovn.org>> wrote: > >>>> > >>>> This patch set covers removal of expressions which are subsets of other > >>>> wider expressions and aggregation of a few granular expressions into > >>>> wider expressions that cover all of them at once. This allows to avoid > >>>> flow explosion in case of negative matches and reduce the total number > >>>> of flows required for address sets. More details are in commit messages. > >>>> > >>>> Version 2: > >>>> * Became a patch set. > >>>> * Added tests and missing bitmap.h include. > >>>> * Code switched to work with bitwise maskable fields only (ORDINAL). > >>>> * Added a new patch to combine smaller expressions into wider ones. > >>>> * Added a patch to fix a crash uncovered with expression aggregation. > >>>> > >>>> Ilya Maximets (3): > >>>> expr: Remove supersets from OR expressions. > >>>> expr: Avoid crash if all sub-expressions crushed down to 'true'. > >>>> expr: Combine OR sub-expressions into supersets. > >>>> > >>>> controller/lflow.c | 5 +- > >>>> lib/expr.c | 188 +++++++++++++------ > >>>> tests/ovn-controller.at <http://ovn-controller.at> | 399 ++++++++++++++++++++-------------------- > >>>> tests/ovn.at <http://ovn.at> | 210 +++++++++++---------- > >>>> 4 files changed, 443 insertions(+), 359 deletions(-) > >>>> > >>>> -- > >>>> 2.39.2 > >>>> > >>> > >>> Thanks Ilya for working on this. The same problem was also reported and discussed briefly in the past: [0], which may be mentioned in reported-by as well. > >> > >> That one was more about memory issue on the OVS side, but sure. > >> > >>> > >>> I reviewed and tested this series. It definitely works great for the flow explosion problem caused by negations in expressions. With 5 subnets in != {} form, which would have generated hundreds of thousands of flows without the patch, now ended up with almost nothing. > >> > >> Nice! > >> > >>> > >>> However, I also see scale problems introduced by this change for more normal use cases. The loop that tries to combine expressions to supersets is O(n^2), n = size of an address set. In large scale environments, it is easy to have more than 10k IPs in an address set - such as when there is a network policy allowing access from all pods of a big tenant/application. I reused my scripts for testing my earlier address set I-P patch [1] to test the performance with this series. As mentioned in the commit message, the old result was: > >>> > >>> Before: ~400ms > >>> After: 11-12ms > >>> > >>> Now with this series, it takes 70 seconds for the same test! > >>> As we can see, even before address-set I-P, it took just 400ms. In a large scale environment, since pods come and go very frequently, even 400ms for each change would make ovn-controller too busy, and that's why we came up with address-set I-P, which made it O(1) and much faster. Now with this change, for each IP change it would take 70s, almost 200 times slower when recomputing the lflow, not to mention comparing with address-set I-P. > >>> > >>> So, I would suggest that the patch 1 should add some logic to restrict the handling for combining expressions generated by negation (!=) only, and keep the current logic unchanged for regular non-negative matches. I think it is possible to add a field in the expr structure to indicate that information while parsing the != operator. > > > > Han, do you see the performance degradation with just the first > > patch applied? > > > > I mean, it shouldn't block the I-P, unless users are manually > > adding supersets of the same IP match into the address set. > > It's not that different from removing duplicates that we do today. > > > > If that's the case, maybe the first two patches can be accepted > > as is? Patch #3 definitely needs more work though, I agree. > > > > What do you think? > > Nevermind. :) > Even if it doesn't affect I-P, it may affect full recompute time, > which is also not great. I'll do some testing and restrict the > use to cross-product sets. > Right, and it doesn't only affect full recompute, but also affect lflow level recompute, which may be triggered by e.g. creating a new ACL, or a local port-group update for an existing ACL.
Here is my test script for your reference: https://github.com/hzhou8/ovn-test-script The example in the readme is what I used (skip step 5 because ovn-controller is not the focus here) for this benchmark test. You may use ovn-heater, or something that simply creates a big address set for the same purpose. Thanks, Han > > > > Best regards, Ilya Maximets. > _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
