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 <[email protected] >>> <mailto:[email protected]>> 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. > > Best regards, Ilya Maximets. _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
