| Message ID | 20240226174449.3426220-1-i.maximets@ovn.org |
|---|---|
| State | Accepted |
| Headers | show |
| Series | [ovs-dev] controller: ofctrl: Use index for meter lookups. | expand |
| Context | Check | Description |
|---|---|---|
| ovsrobot/apply-robot | success | apply and check: success |
| ovsrobot/github-robot-_ovn-kubernetes | success | github build: passed |
| ovsrobot/github-robot-_Build_and_Test | fail | github build: failed |
| ovsrobot/github-robot-_Build_and_Test | success | github build: passed |
| ovsrobot/github-robot-_ovn-kubernetes | success | github build: passed |
On 2/26/24 18:44, Ilya Maximets wrote: > Currently, ovn-controller attempts to sync all the meters on each > ofctrl_put() call. And the complexity of this logic is quadratic > because for each desired meter we perform a full scan of all the > rows in the Southbound Meter table in order to lookup a matching > meter. This is very inefficient. In a setup with 25K meters this > operation takes anywhere from 30 to 60 seconds to perform. All > that time ovn-controller is blocked and doesn't process any updates. > So, addition of new ports in such a setup becomes very slow. > > The meter lookup is performed by name and we have an index for it > in the database schema. Might as well use it. > > Using the index for lookup reduces complexity to O(n * log n). > And the time to process port addition on the same setup drops down > to just 100 - 300 ms. > > We are still iterating over all the desired meters while they can > probably be processed incrementally instead. But using an index > is a simpler fix for now. > > Fixes: 885655e16e63 ("controller: reconfigure ovs meters for ovn meters") > Fixes: 999e1adfb572 ("ovn: Support configuring meters through SB Meter table.") > Reported-at: https://issues.redhat.com/browse/FDP-399 > Signed-off-by: Ilya Maximets <i.maximets@ovn.org> > --- > > This is a "performance bug", so the decision to backport this or not > is on maintainers. But it is severe enough, IMO. > > controller/ofctrl.c | 37 ++++++++++++++++++++++--------------- > controller/ofctrl.h | 2 +- > controller/ovn-controller.c | 4 +++- > 3 files changed, 26 insertions(+), 17 deletions(-) Recheck-request: github-robot-_Build_and_Test
On Mon, Feb 26, 2024 at 9:44 AM Ilya Maximets <i.maximets@ovn.org> wrote: > > Currently, ovn-controller attempts to sync all the meters on each > ofctrl_put() call. And the complexity of this logic is quadratic > because for each desired meter we perform a full scan of all the > rows in the Southbound Meter table in order to lookup a matching > meter. This is very inefficient. In a setup with 25K meters this > operation takes anywhere from 30 to 60 seconds to perform. All > that time ovn-controller is blocked and doesn't process any updates. > So, addition of new ports in such a setup becomes very slow. > > The meter lookup is performed by name and we have an index for it > in the database schema. Might as well use it. > > Using the index for lookup reduces complexity to O(n * log n). > And the time to process port addition on the same setup drops down > to just 100 - 300 ms. > > We are still iterating over all the desired meters while they can > probably be processed incrementally instead. But using an index > is a simpler fix for now. > > Fixes: 885655e16e63 ("controller: reconfigure ovs meters for ovn meters") > Fixes: 999e1adfb572 ("ovn: Support configuring meters through SB Meter table.") > Reported-at: https://issues.redhat.com/browse/FDP-399 > Signed-off-by: Ilya Maximets <i.maximets@ovn.org> > --- > > This is a "performance bug", so the decision to backport this or not > is on maintainers. But it is severe enough, IMO. > Thanks Ilya. The fix looks good to me. And I think it is ok to backport, since the change is simple enough. Acked-by: Han Zhou <hzhou@ovn.org> Just curious, how would the OVS perform with this large number of meters? Thanks, Han > controller/ofctrl.c | 37 ++++++++++++++++++++++--------------- > controller/ofctrl.h | 2 +- > controller/ovn-controller.c | 4 +++- > 3 files changed, 26 insertions(+), 17 deletions(-) > > diff --git a/controller/ofctrl.c b/controller/ofctrl.c > index cb460a2a4..f14cd79a8 100644 > --- a/controller/ofctrl.c > +++ b/controller/ofctrl.c > @@ -2257,18 +2257,29 @@ ofctrl_meter_bands_erase(struct ovn_extend_table_info *entry, > } > } > > +static const struct sbrec_meter * > +sb_meter_lookup_by_name(struct ovsdb_idl_index *sbrec_meter_by_name, > + const char *name) > +{ > + const struct sbrec_meter *sb_meter; > + struct sbrec_meter *index_row; > + > + index_row = sbrec_meter_index_init_row(sbrec_meter_by_name); > + sbrec_meter_index_set_name(index_row, name); > + sb_meter = sbrec_meter_index_find(sbrec_meter_by_name, index_row); > + sbrec_meter_index_destroy_row(index_row); > + > + return sb_meter; > +} > + > static void > ofctrl_meter_bands_sync(struct ovn_extend_table_info *m_existing, > - const struct sbrec_meter_table *meter_table, > + struct ovsdb_idl_index *sbrec_meter_by_name, > struct ovs_list *msgs) > { > const struct sbrec_meter *sb_meter; > - SBREC_METER_TABLE_FOR_EACH (sb_meter, meter_table) { > - if (!strcmp(m_existing->name, sb_meter->name)) { > - break; > - } > - } > > + sb_meter = sb_meter_lookup_by_name(sbrec_meter_by_name, m_existing->name); > if (sb_meter) { > /* OFPMC13_ADD or OFPMC13_MODIFY */ > ofctrl_meter_bands_update(sb_meter, m_existing, msgs); > @@ -2280,16 +2291,12 @@ ofctrl_meter_bands_sync(struct ovn_extend_table_info *m_existing, > > static void > add_meter(struct ovn_extend_table_info *m_desired, > - const struct sbrec_meter_table *meter_table, > + struct ovsdb_idl_index *sbrec_meter_by_name, > struct ovs_list *msgs) > { > const struct sbrec_meter *sb_meter; > - SBREC_METER_TABLE_FOR_EACH (sb_meter, meter_table) { > - if (!strcmp(m_desired->name, sb_meter->name)) { > - break; > - } > - } > > + sb_meter = sb_meter_lookup_by_name(sbrec_meter_by_name, m_desired->name); > if (!sb_meter) { > static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1); > VLOG_ERR_RL(&rl, "could not find meter named \"%s\"", m_desired->name); > @@ -2656,7 +2663,7 @@ ofctrl_put(struct ovn_desired_flow_table *lflow_table, > struct ovn_desired_flow_table *pflow_table, > struct shash *pending_ct_zones, > struct hmap *pending_lb_tuples, > - const struct sbrec_meter_table *meter_table, > + struct ovsdb_idl_index *sbrec_meter_by_name, > uint64_t req_cfg, > bool lflows_changed, > bool pflows_changed) > @@ -2733,10 +2740,10 @@ ofctrl_put(struct ovn_desired_flow_table *lflow_table, > * describes the meter itself. */ > add_meter_string(m_desired, &msgs); > } else { > - add_meter(m_desired, meter_table, &msgs); > + add_meter(m_desired, sbrec_meter_by_name, &msgs); > } > } else { > - ofctrl_meter_bands_sync(m_existing, meter_table, &msgs); > + ofctrl_meter_bands_sync(m_existing, sbrec_meter_by_name, &msgs); > } > } > > diff --git a/controller/ofctrl.h b/controller/ofctrl.h > index 46bfccd85..502c73da6 100644 > --- a/controller/ofctrl.h > +++ b/controller/ofctrl.h > @@ -58,7 +58,7 @@ void ofctrl_put(struct ovn_desired_flow_table *lflow_table, > struct ovn_desired_flow_table *pflow_table, > struct shash *pending_ct_zones, > struct hmap *pending_lb_tuples, > - const struct sbrec_meter_table *, > + struct ovsdb_idl_index *sbrec_meter_by_name, > uint64_t nb_cfg, > bool lflow_changed, > bool pflow_changed); > diff --git a/controller/ovn-controller.c b/controller/ovn-controller.c > index 7e7bc71b3..1c9960c70 100644 > --- a/controller/ovn-controller.c > +++ b/controller/ovn-controller.c > @@ -5129,6 +5129,8 @@ main(int argc, char *argv[]) > = chassis_private_index_create(ovnsb_idl_loop.idl); > struct ovsdb_idl_index *sbrec_multicast_group_by_name_datapath > = mcast_group_index_create(ovnsb_idl_loop.idl); > + struct ovsdb_idl_index *sbrec_meter_by_name > + = ovsdb_idl_index_create1(ovnsb_idl_loop.idl, &sbrec_meter_col_name); > struct ovsdb_idl_index *sbrec_logical_flow_by_logical_datapath > = ovsdb_idl_index_create1(ovnsb_idl_loop.idl, > &sbrec_logical_flow_col_logical_datapath); > @@ -5942,7 +5944,7 @@ main(int argc, char *argv[]) > &pflow_output_data->flow_table, > &ct_zones_data->pending, > &lb_data->removed_tuples, > - sbrec_meter_table_get(ovnsb_idl_loop.idl), > + sbrec_meter_by_name, > ofctrl_seqno_get_req_cfg(), > engine_node_changed(&en_lflow_output), > engine_node_changed(&en_pflow_output)); > -- > 2.43.0 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > https://mail.openvswitch.org/mailman/listinfo/ovs-dev
On 2/27/24 07:51, Han Zhou wrote: > > > On Mon, Feb 26, 2024 at 9:44 AM Ilya Maximets <i.maximets@ovn.org <mailto:i.maximets@ovn.org>> wrote: >> >> Currently, ovn-controller attempts to sync all the meters on each >> ofctrl_put() call. And the complexity of this logic is quadratic >> because for each desired meter we perform a full scan of all the >> rows in the Southbound Meter table in order to lookup a matching >> meter. This is very inefficient. In a setup with 25K meters this >> operation takes anywhere from 30 to 60 seconds to perform. All >> that time ovn-controller is blocked and doesn't process any updates. >> So, addition of new ports in such a setup becomes very slow. >> >> The meter lookup is performed by name and we have an index for it >> in the database schema. Might as well use it. >> >> Using the index for lookup reduces complexity to O(n * log n). >> And the time to process port addition on the same setup drops down >> to just 100 - 300 ms. >> >> We are still iterating over all the desired meters while they can >> probably be processed incrementally instead. But using an index >> is a simpler fix for now. >> >> Fixes: 885655e16e63 ("controller: reconfigure ovs meters for ovn meters") >> Fixes: 999e1adfb572 ("ovn: Support configuring meters through SB Meter table.") >> Reported-at: https://issues.redhat.com/browse/FDP-399 <https://issues.redhat.com/browse/FDP-399> >> Signed-off-by: Ilya Maximets <i.maximets@ovn.org <mailto:i.maximets@ovn.org>> >> --- >> >> This is a "performance bug", so the decision to backport this or not >> is on maintainers. But it is severe enough, IMO. >> > > Thanks Ilya. The fix looks good to me. And I think it is ok to backport, since the change is simple enough. > > Acked-by: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>> > > Just curious, how would the OVS perform with this large number of meters? Hi. Thanks for review! I don't think 25K would cause any noticeable issues on OVS side, but I agree that if we scale further we may overload the classifier at some point. I don't have hard evidence to back this up, but based on my prior experience with flow explosion with negative matches, I think, we need about 200K rules in order for it to start becoming a problem. But also ACL rules are not normally conjunctive, i.e. should be easier for classifier to process, so we may probably handle more. Needs some testing. Best regards, Ilya Maximets.
On 2/27/24 05:32, Ilya Maximets wrote: > On 2/27/24 07:51, Han Zhou wrote: >> >> >> On Mon, Feb 26, 2024 at 9:44 AM Ilya Maximets <i.maximets@ovn.org <mailto:i.maximets@ovn.org>> wrote: >>> >>> Currently, ovn-controller attempts to sync all the meters on each >>> ofctrl_put() call. And the complexity of this logic is quadratic >>> because for each desired meter we perform a full scan of all the >>> rows in the Southbound Meter table in order to lookup a matching >>> meter. This is very inefficient. In a setup with 25K meters this >>> operation takes anywhere from 30 to 60 seconds to perform. All >>> that time ovn-controller is blocked and doesn't process any updates. >>> So, addition of new ports in such a setup becomes very slow. >>> >>> The meter lookup is performed by name and we have an index for it >>> in the database schema. Might as well use it. >>> >>> Using the index for lookup reduces complexity to O(n * log n). >>> And the time to process port addition on the same setup drops down >>> to just 100 - 300 ms. >>> >>> We are still iterating over all the desired meters while they can >>> probably be processed incrementally instead. But using an index >>> is a simpler fix for now. >>> >>> Fixes: 885655e16e63 ("controller: reconfigure ovs meters for ovn meters") >>> Fixes: 999e1adfb572 ("ovn: Support configuring meters through SB Meter table.") >>> Reported-at: https://issues.redhat.com/browse/FDP-399 <https://issues.redhat.com/browse/FDP-399> >>> Signed-off-by: Ilya Maximets <i.maximets@ovn.org <mailto:i.maximets@ovn.org>> >>> --- >>> >>> This is a "performance bug", so the decision to backport this or not >>> is on maintainers. But it is severe enough, IMO. >>> >> >> Thanks Ilya. The fix looks good to me. And I think it is ok to backport, since the change is simple enough. >> >> Acked-by: Han Zhou <hzhou@ovn.org <mailto:hzhou@ovn.org>> >> >> Just curious, how would the OVS perform with this large number of meters? > > Hi. Thanks for review! > > I don't think 25K would cause any noticeable issues on OVS side, > but I agree that if we scale further we may overload the classifier > at some point. I don't have hard evidence to back this up, but > based on my prior experience with flow explosion with negative > matches, I think, we need about 200K rules in order for it to start > becoming a problem. But also ACL rules are not normally conjunctive, > i.e. should be easier for classifier to process, so we may probably > handle more. Needs some testing. > > Best regards, Ilya Maximets. Thank you Han and Ilya. I pushed this change to main and all branches back to 23.03.
diff --git a/controller/ofctrl.c b/controller/ofctrl.c index cb460a2a4..f14cd79a8 100644 --- a/controller/ofctrl.c +++ b/controller/ofctrl.c @@ -2257,18 +2257,29 @@ ofctrl_meter_bands_erase(struct ovn_extend_table_info *entry, } } +static const struct sbrec_meter * +sb_meter_lookup_by_name(struct ovsdb_idl_index *sbrec_meter_by_name, + const char *name) +{ + const struct sbrec_meter *sb_meter; + struct sbrec_meter *index_row; + + index_row = sbrec_meter_index_init_row(sbrec_meter_by_name); + sbrec_meter_index_set_name(index_row, name); + sb_meter = sbrec_meter_index_find(sbrec_meter_by_name, index_row); + sbrec_meter_index_destroy_row(index_row); + + return sb_meter; +} + static void ofctrl_meter_bands_sync(struct ovn_extend_table_info *m_existing, - const struct sbrec_meter_table *meter_table, + struct ovsdb_idl_index *sbrec_meter_by_name, struct ovs_list *msgs) { const struct sbrec_meter *sb_meter; - SBREC_METER_TABLE_FOR_EACH (sb_meter, meter_table) { - if (!strcmp(m_existing->name, sb_meter->name)) { - break; - } - } + sb_meter = sb_meter_lookup_by_name(sbrec_meter_by_name, m_existing->name); if (sb_meter) { /* OFPMC13_ADD or OFPMC13_MODIFY */ ofctrl_meter_bands_update(sb_meter, m_existing, msgs); @@ -2280,16 +2291,12 @@ ofctrl_meter_bands_sync(struct ovn_extend_table_info *m_existing, static void add_meter(struct ovn_extend_table_info *m_desired, - const struct sbrec_meter_table *meter_table, + struct ovsdb_idl_index *sbrec_meter_by_name, struct ovs_list *msgs) { const struct sbrec_meter *sb_meter; - SBREC_METER_TABLE_FOR_EACH (sb_meter, meter_table) { - if (!strcmp(m_desired->name, sb_meter->name)) { - break; - } - } + sb_meter = sb_meter_lookup_by_name(sbrec_meter_by_name, m_desired->name); if (!sb_meter) { static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1); VLOG_ERR_RL(&rl, "could not find meter named \"%s\"", m_desired->name); @@ -2656,7 +2663,7 @@ ofctrl_put(struct ovn_desired_flow_table *lflow_table, struct ovn_desired_flow_table *pflow_table, struct shash *pending_ct_zones, struct hmap *pending_lb_tuples, - const struct sbrec_meter_table *meter_table, + struct ovsdb_idl_index *sbrec_meter_by_name, uint64_t req_cfg, bool lflows_changed, bool pflows_changed) @@ -2733,10 +2740,10 @@ ofctrl_put(struct ovn_desired_flow_table *lflow_table, * describes the meter itself. */ add_meter_string(m_desired, &msgs); } else { - add_meter(m_desired, meter_table, &msgs); + add_meter(m_desired, sbrec_meter_by_name, &msgs); } } else { - ofctrl_meter_bands_sync(m_existing, meter_table, &msgs); + ofctrl_meter_bands_sync(m_existing, sbrec_meter_by_name, &msgs); } } diff --git a/controller/ofctrl.h b/controller/ofctrl.h index 46bfccd85..502c73da6 100644 --- a/controller/ofctrl.h +++ b/controller/ofctrl.h @@ -58,7 +58,7 @@ void ofctrl_put(struct ovn_desired_flow_table *lflow_table, struct ovn_desired_flow_table *pflow_table, struct shash *pending_ct_zones, struct hmap *pending_lb_tuples, - const struct sbrec_meter_table *, + struct ovsdb_idl_index *sbrec_meter_by_name, uint64_t nb_cfg, bool lflow_changed, bool pflow_changed); diff --git a/controller/ovn-controller.c b/controller/ovn-controller.c index 7e7bc71b3..1c9960c70 100644 --- a/controller/ovn-controller.c +++ b/controller/ovn-controller.c @@ -5129,6 +5129,8 @@ main(int argc, char *argv[]) = chassis_private_index_create(ovnsb_idl_loop.idl); struct ovsdb_idl_index *sbrec_multicast_group_by_name_datapath = mcast_group_index_create(ovnsb_idl_loop.idl); + struct ovsdb_idl_index *sbrec_meter_by_name + = ovsdb_idl_index_create1(ovnsb_idl_loop.idl, &sbrec_meter_col_name); struct ovsdb_idl_index *sbrec_logical_flow_by_logical_datapath = ovsdb_idl_index_create1(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_logical_datapath); @@ -5942,7 +5944,7 @@ main(int argc, char *argv[]) &pflow_output_data->flow_table, &ct_zones_data->pending, &lb_data->removed_tuples, - sbrec_meter_table_get(ovnsb_idl_loop.idl), + sbrec_meter_by_name, ofctrl_seqno_get_req_cfg(), engine_node_changed(&en_lflow_output), engine_node_changed(&en_pflow_output));
Currently, ovn-controller attempts to sync all the meters on each ofctrl_put() call. And the complexity of this logic is quadratic because for each desired meter we perform a full scan of all the rows in the Southbound Meter table in order to lookup a matching meter. This is very inefficient. In a setup with 25K meters this operation takes anywhere from 30 to 60 seconds to perform. All that time ovn-controller is blocked and doesn't process any updates. So, addition of new ports in such a setup becomes very slow. The meter lookup is performed by name and we have an index for it in the database schema. Might as well use it. Using the index for lookup reduces complexity to O(n * log n). And the time to process port addition on the same setup drops down to just 100 - 300 ms. We are still iterating over all the desired meters while they can probably be processed incrementally instead. But using an index is a simpler fix for now. Fixes: 885655e16e63 ("controller: reconfigure ovs meters for ovn meters") Fixes: 999e1adfb572 ("ovn: Support configuring meters through SB Meter table.") Reported-at: https://issues.redhat.com/browse/FDP-399 Signed-off-by: Ilya Maximets <i.maximets@ovn.org> --- This is a "performance bug", so the decision to backport this or not is on maintainers. But it is severe enough, IMO. controller/ofctrl.c | 37 ++++++++++++++++++++++--------------- controller/ofctrl.h | 2 +- controller/ovn-controller.c | 4 +++- 3 files changed, 26 insertions(+), 17 deletions(-)