| Message ID | 20180213135740.9341-1-jkbs@redhat.com |
|---|---|
| State | RFC |
| Headers | show |
| Series | [ovs-dev,RFC] ovn-northd: Store computed logical flow hash in SBDB. | expand |
Nice! Acked-by: Mark Michelson <mmichels@redhat.com> On 02/13/2018 07:57 AM, Jakub Sitnicki wrote: > Each time ovn-northd processes the NBDB contents it has to compute the > hash of every logical flow stored in the SBDB in order to identify ones > that need adding to or deleting from SBDB (build_lflows()). > > Avoid it by storing the logical flow hash together with its fields the > moment we first add it to SBDB. This saves us the hash computations > afterwards, every time ovn-northd processes the logical flows to find > candidates for removal/addition. > > In a simple micro-benchmark that adds 15 logical switches with 100 > logical ports each, perf tool shows a drop of 7% in CPU cycles > ('cycles:ppp' event) spent in ovn_lflow_find() where we compute the hash > of each logical flow found in SBDB: > > Children Self Command Shared Object Symbol > before: 10.61% 0.17% ovn-northd ovn-northd [.] ovn_lflow_find > after: 2.82% 0.19% ovn-northd ovn-northd [.] ovn_lflow_find > > Signed-off-by: Jakub Sitnicki <jkbs@redhat.com> > --- > ovn/northd/ovn-northd.c | 9 +++++---- > ovn/ovn-sb.ovsschema | 7 +++++-- > ovn/ovn-sb.xml | 5 +++++ > 3 files changed, 15 insertions(+), 6 deletions(-) > > diff --git a/ovn/northd/ovn-northd.c b/ovn/northd/ovn-northd.c > index 4d95a3d9d..dcb9939d9 100644 > --- a/ovn/northd/ovn-northd.c > +++ b/ovn/northd/ovn-northd.c > @@ -2331,7 +2331,7 @@ ovn_lflow_add_at(struct hmap *lflow_map, struct ovn_datapath *od, > static struct ovn_lflow * > ovn_lflow_find(struct hmap *lflows, struct ovn_datapath *od, > enum ovn_stage stage, uint16_t priority, > - const char *match, const char *actions) > + const char *match, const char *actions, uint32_t hash) > { > struct ovn_lflow target; > ovn_lflow_init(&target, od, stage, priority, > @@ -2339,8 +2339,7 @@ ovn_lflow_find(struct hmap *lflows, struct ovn_datapath *od, > NULL, NULL); > > struct ovn_lflow *lflow; > - HMAP_FOR_EACH_WITH_HASH (lflow, hmap_node, ovn_lflow_hash(&target), > - lflows) { > + HMAP_FOR_EACH_WITH_HASH (lflow, hmap_node, hash, lflows) { > if (ovn_lflow_equal(lflow, &target)) { > return lflow; > } > @@ -6014,7 +6013,7 @@ build_lflows(struct northd_context *ctx, struct hmap *datapaths, > = !strcmp(sbflow->pipeline, "ingress") ? P_IN : P_OUT; > struct ovn_lflow *lflow = ovn_lflow_find( > &lflows, od, ovn_stage_build(dp_type, pipeline, sbflow->table_id), > - sbflow->priority, sbflow->match, sbflow->actions); > + sbflow->priority, sbflow->match, sbflow->actions, sbflow->hash); > if (lflow) { > ovn_lflow_destroy(&lflows, lflow); > } else { > @@ -6034,6 +6033,7 @@ build_lflows(struct northd_context *ctx, struct hmap *datapaths, > sbrec_logical_flow_set_priority(sbflow, lflow->priority); > sbrec_logical_flow_set_match(sbflow, lflow->match); > sbrec_logical_flow_set_actions(sbflow, lflow->actions); > + sbrec_logical_flow_set_hash(sbflow, lflow->hmap_node.hash); > > /* Trim the source locator lflow->where, which looks something like > * "ovn/northd/ovn-northd.c:1234", down to just the part following the > @@ -6782,6 +6782,7 @@ main(int argc, char *argv[]) > add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_priority); > add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_match); > add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_actions); > + add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_hash); > > ovsdb_idl_add_table(ovnsb_idl_loop.idl, &sbrec_table_multicast_group); > add_column_noalert(ovnsb_idl_loop.idl, > diff --git a/ovn/ovn-sb.ovsschema b/ovn/ovn-sb.ovsschema > index 2abcc6b70..b6a145431 100644 > --- a/ovn/ovn-sb.ovsschema > +++ b/ovn/ovn-sb.ovsschema > @@ -1,7 +1,7 @@ > { > "name": "OVN_Southbound", > - "version": "1.15.0", > - "cksum": "70426956 13327", > + "version": "1.16.0", > + "cksum": "340822255 13518", > "tables": { > "SB_Global": { > "columns": { > @@ -70,6 +70,9 @@ > "maxInteger": 65535}}}, > "match": {"type": "string"}, > "actions": {"type": "string"}, > + "hash": {"type": {"key": {"type": "integer", > + "minInteger": 0, > + "maxInteger": 4294967295}}}, > "external_ids": { > "type": {"key": "string", "value": "string", > "min": 0, "max": "unlimited"}}}, > diff --git a/ovn/ovn-sb.xml b/ovn/ovn-sb.xml > index f000b166c..073a4c11d 100644 > --- a/ovn/ovn-sb.xml > +++ b/ovn/ovn-sb.xml > @@ -1767,6 +1767,11 @@ tcp.flags = RST; > </dl> > </column> > > + <column name="hash"> > + Cached value of a hash computed over selected fields of this logical flow > + by <code>ovn-northd</code>. > + </column> > + > <column name="external_ids" key="stage-name"> > Human-readable name for this flow's stage in the pipeline. > </column> >
On Tue, Feb 13, 2018 at 02:57:40PM +0100, Jakub Sitnicki wrote: > Each time ovn-northd processes the NBDB contents it has to compute the > hash of every logical flow stored in the SBDB in order to identify ones > that need adding to or deleting from SBDB (build_lflows()). > > Avoid it by storing the logical flow hash together with its fields the > moment we first add it to SBDB. This saves us the hash computations > afterwards, every time ovn-northd processes the logical flows to find > candidates for removal/addition. > > In a simple micro-benchmark that adds 15 logical switches with 100 > logical ports each, perf tool shows a drop of 7% in CPU cycles > ('cycles:ppp' event) spent in ovn_lflow_find() where we compute the hash > of each logical flow found in SBDB: > > Children Self Command Shared Object Symbol > before: 10.61% 0.17% ovn-northd ovn-northd [.] ovn_lflow_find > after: 2.82% 0.19% ovn-northd ovn-northd [.] ovn_lflow_find This is good work, thanks for figuring this out. I think that it is better if this kind of thing is not actually stored in the database. It adds a risk that the hash could get out of sync with the rest of a row, and there is no guarantee that the hash function is the same from one version of OVS to the next or between little and big endian architectures on the same version of OVS. However, we can still do better by calculating the hash only a single time on the client and only recalculating it if the row otherwise changes. I had a branch a while back that implemented something more ambitious than this, so I cut it down and polished it up and this is what I came up with: https://patchwork.ozlabs.org/project/openvswitch/list/?series=28651 Would you mind testing it to see whether its performance benefit is similar to what you observed? Thanks, Ben.
On Wed, 14 Feb 2018 13:58:16 -0800 Ben Pfaff <blp@ovn.org> wrote: > On Tue, Feb 13, 2018 at 02:57:40PM +0100, Jakub Sitnicki wrote: > > Each time ovn-northd processes the NBDB contents it has to compute the > > hash of every logical flow stored in the SBDB in order to identify ones > > that need adding to or deleting from SBDB (build_lflows()). > > > > Avoid it by storing the logical flow hash together with its fields the > > moment we first add it to SBDB. This saves us the hash computations > > afterwards, every time ovn-northd processes the logical flows to find > > candidates for removal/addition. > > > > In a simple micro-benchmark that adds 15 logical switches with 100 > > logical ports each, perf tool shows a drop of 7% in CPU cycles > > ('cycles:ppp' event) spent in ovn_lflow_find() where we compute the hash > > of each logical flow found in SBDB: > > > > Children Self Command Shared Object Symbol > > before: 10.61% 0.17% ovn-northd ovn-northd [.] ovn_lflow_find > > after: 2.82% 0.19% ovn-northd ovn-northd [.] ovn_lflow_find > > This is good work, thanks for figuring this out. > > I think that it is better if this kind of thing is not actually stored > in the database. It adds a risk that the hash could get out of sync > with the rest of a row, and there is no guarantee that the hash function > is the same from one version of OVS to the next or between little and > big endian architectures on the same version of OVS. > > However, we can still do better by calculating the hash only a single > time on the client and only recalculating it if the row otherwise > changes. I had a branch a while back that implemented something more > ambitious than this, so I cut it down and polished it up and this is > what I came up with: > https://patchwork.ozlabs.org/project/openvswitch/list/?series=28651 > > Would you mind testing it to see whether its performance benefit is > similar to what you observed? Ben, I agree, storing the hash in the database can be a source of problems. Your synthetic column solution is much cleaner. I will profile it and report back. Thanks, Jakub
diff --git a/ovn/northd/ovn-northd.c b/ovn/northd/ovn-northd.c index 4d95a3d9d..dcb9939d9 100644 --- a/ovn/northd/ovn-northd.c +++ b/ovn/northd/ovn-northd.c @@ -2331,7 +2331,7 @@ ovn_lflow_add_at(struct hmap *lflow_map, struct ovn_datapath *od, static struct ovn_lflow * ovn_lflow_find(struct hmap *lflows, struct ovn_datapath *od, enum ovn_stage stage, uint16_t priority, - const char *match, const char *actions) + const char *match, const char *actions, uint32_t hash) { struct ovn_lflow target; ovn_lflow_init(&target, od, stage, priority, @@ -2339,8 +2339,7 @@ ovn_lflow_find(struct hmap *lflows, struct ovn_datapath *od, NULL, NULL); struct ovn_lflow *lflow; - HMAP_FOR_EACH_WITH_HASH (lflow, hmap_node, ovn_lflow_hash(&target), - lflows) { + HMAP_FOR_EACH_WITH_HASH (lflow, hmap_node, hash, lflows) { if (ovn_lflow_equal(lflow, &target)) { return lflow; } @@ -6014,7 +6013,7 @@ build_lflows(struct northd_context *ctx, struct hmap *datapaths, = !strcmp(sbflow->pipeline, "ingress") ? P_IN : P_OUT; struct ovn_lflow *lflow = ovn_lflow_find( &lflows, od, ovn_stage_build(dp_type, pipeline, sbflow->table_id), - sbflow->priority, sbflow->match, sbflow->actions); + sbflow->priority, sbflow->match, sbflow->actions, sbflow->hash); if (lflow) { ovn_lflow_destroy(&lflows, lflow); } else { @@ -6034,6 +6033,7 @@ build_lflows(struct northd_context *ctx, struct hmap *datapaths, sbrec_logical_flow_set_priority(sbflow, lflow->priority); sbrec_logical_flow_set_match(sbflow, lflow->match); sbrec_logical_flow_set_actions(sbflow, lflow->actions); + sbrec_logical_flow_set_hash(sbflow, lflow->hmap_node.hash); /* Trim the source locator lflow->where, which looks something like * "ovn/northd/ovn-northd.c:1234", down to just the part following the @@ -6782,6 +6782,7 @@ main(int argc, char *argv[]) add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_priority); add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_match); add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_actions); + add_column_noalert(ovnsb_idl_loop.idl, &sbrec_logical_flow_col_hash); ovsdb_idl_add_table(ovnsb_idl_loop.idl, &sbrec_table_multicast_group); add_column_noalert(ovnsb_idl_loop.idl, diff --git a/ovn/ovn-sb.ovsschema b/ovn/ovn-sb.ovsschema index 2abcc6b70..b6a145431 100644 --- a/ovn/ovn-sb.ovsschema +++ b/ovn/ovn-sb.ovsschema @@ -1,7 +1,7 @@ { "name": "OVN_Southbound", - "version": "1.15.0", - "cksum": "70426956 13327", + "version": "1.16.0", + "cksum": "340822255 13518", "tables": { "SB_Global": { "columns": { @@ -70,6 +70,9 @@ "maxInteger": 65535}}}, "match": {"type": "string"}, "actions": {"type": "string"}, + "hash": {"type": {"key": {"type": "integer", + "minInteger": 0, + "maxInteger": 4294967295}}}, "external_ids": { "type": {"key": "string", "value": "string", "min": 0, "max": "unlimited"}}}, diff --git a/ovn/ovn-sb.xml b/ovn/ovn-sb.xml index f000b166c..073a4c11d 100644 --- a/ovn/ovn-sb.xml +++ b/ovn/ovn-sb.xml @@ -1767,6 +1767,11 @@ tcp.flags = RST; </dl> </column> + <column name="hash"> + Cached value of a hash computed over selected fields of this logical flow + by <code>ovn-northd</code>. + </column> + <column name="external_ids" key="stage-name"> Human-readable name for this flow's stage in the pipeline. </column>
Each time ovn-northd processes the NBDB contents it has to compute the hash of every logical flow stored in the SBDB in order to identify ones that need adding to or deleting from SBDB (build_lflows()). Avoid it by storing the logical flow hash together with its fields the moment we first add it to SBDB. This saves us the hash computations afterwards, every time ovn-northd processes the logical flows to find candidates for removal/addition. In a simple micro-benchmark that adds 15 logical switches with 100 logical ports each, perf tool shows a drop of 7% in CPU cycles ('cycles:ppp' event) spent in ovn_lflow_find() where we compute the hash of each logical flow found in SBDB: Children Self Command Shared Object Symbol before: 10.61% 0.17% ovn-northd ovn-northd [.] ovn_lflow_find after: 2.82% 0.19% ovn-northd ovn-northd [.] ovn_lflow_find Signed-off-by: Jakub Sitnicki <jkbs@redhat.com> --- ovn/northd/ovn-northd.c | 9 +++++---- ovn/ovn-sb.ovsschema | 7 +++++-- ovn/ovn-sb.xml | 5 +++++ 3 files changed, 15 insertions(+), 6 deletions(-)