[ovs-dev,RFC] ovn-northd: Store computed logical flow hash in SBDB.

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.
Related show

Commit Message

Jakub Sitnicki Feb. 13, 2018, 1:57 p.m.
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(-)

Comments

Mark Michelson Feb. 13, 2018, 2:57 p.m. | #1
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>
>
Ben Pfaff Feb. 14, 2018, 9:58 p.m. | #2
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.
Jakub Sitnicki Feb. 15, 2018, 10:18 a.m. | #3
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

Patch

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>