| Message ID | 1454538023-15669-1-git-send-email-rmoats@us.ibm.com |
|---|---|
| State | RFC |
| Headers | show |
On Wed, Feb 03, 2016 at 04:20:23PM -0600, RYAN D. MOATS wrote: > Add incremental processing of lflows in ovn-controller by > taking the simple approach of marking each lflow dirty when > touched and have lflow_run only process dirty flows. > > This needs unit test code before the RFC tag comes off. > > Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> I was envisioning something that would incrementally determine on a per-flow basis whether anything needed to be recalculated. Starting with a per-logical-datapath approach, as this patch does, is a nice place to start because it is presumably easier, so I think it's a good idea. I don't understand how this particular patch is going to make a difference, though, since ldp_run() appears to always dirty every logical datapath. I don't know why this deletes a comment that seems to be orthogonal to the purpose of the patch. Please use "bool", "true", and "false" for Boolean values, instead of uint8_t, 1, and 0. Thanks, Ben.
Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 01:01:56 PM: > From: Ben Pfaff <blp@ovn.org> > To: Ryan Moats/Omaha/IBM@IBMUS > Cc: dev@openvswitch.org > Date: 02/05/2016 01:02 PM > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > lflow incremental processing > > On Wed, Feb 03, 2016 at 04:20:23PM -0600, RYAN D. MOATS wrote: > > Add incremental processing of lflows in ovn-controller by > > taking the simple approach of marking each lflow dirty when > > touched and have lflow_run only process dirty flows. > > > > This needs unit test code before the RFC tag comes off. > > > > Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> > > I was envisioning something that would incrementally determine on a > per-flow basis whether anything needed to be recalculated. Starting > with a per-logical-datapath approach, as this patch does, is a nice > place to start because it is presumably easier, so I think it's a good > idea. I suspect we'll get to that point eventually, but I figured this would be easier to start with... > I don't understand how this particular patch is going to make a > difference, though, since ldp_run() appears to always dirty every > logical datapath. Well, when I ran the test that I used on Russell's now merged patch that improved things 15%, I was still seeing that each lflow_run call would process 36020 logical datapaths, 40012 matches and take a little more than half a second to complete Running that same test on this patch resulted in (after completion) only 2797 of the 36020 logical datapaths being processed - these generated 2934 matches being reprogrammed and a lflow_run call would complete in less than 50 msec. > > I don't know why this deletes a comment that seems to be orthogonal to > the purpose of the patch. Honestly, that's my mistake and I'll fix it when I fix the below... > Please use "bool", "true", and "false" for Boolean values, instead of > uint8_t, 1, and 0. Ack. Ryan
On Fri, Feb 05, 2016 at 03:41:24PM -0600, Ryan Moats wrote: > Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 01:01:56 PM: > > > From: Ben Pfaff <blp@ovn.org> > > To: Ryan Moats/Omaha/IBM@IBMUS > > Cc: dev@openvswitch.org > > Date: 02/05/2016 01:02 PM > > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > > lflow incremental processing > > > > On Wed, Feb 03, 2016 at 04:20:23PM -0600, RYAN D. MOATS wrote: > > > Add incremental processing of lflows in ovn-controller by > > > taking the simple approach of marking each lflow dirty when > > > touched and have lflow_run only process dirty flows. > > > > > > This needs unit test code before the RFC tag comes off. > > > > > > Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> > > > > I was envisioning something that would incrementally determine on a > > per-flow basis whether anything needed to be recalculated. Starting > > with a per-logical-datapath approach, as this patch does, is a nice > > place to start because it is presumably easier, so I think it's a good > > idea. > > I suspect we'll get to that point eventually, but I figured this would be > easier to start with... > > > I don't understand how this particular patch is going to make a > > difference, though, since ldp_run() appears to always dirty every > > logical datapath. > > Well, when I ran the test that I used on Russell's now merged patch that > improved things 15%, I was still seeing that each lflow_run call would > process > 36020 logical datapaths, 40012 matches and take a little more than half a > second to complete > > Running that same test on this patch resulted in (after completion) > only 2797 of the 36020 logical datapaths being processed - these generated > 2934 matches being reprogrammed and a lflow_run call would complete in less > than 50 msec. I think this is because lflow_run() marks a logical datapath "clean" after processing any one logical flow in the datapath. I don't know why it does that, but on the face of it it seems wrong.
Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 04:20:04 PM: > From: Ben Pfaff <blp@ovn.org> > To: Ryan Moats/Omaha/IBM@IBMUS > Cc: dev@openvswitch.org > Date: 02/05/2016 04:20 PM > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > lflow incremental processing > > On Fri, Feb 05, 2016 at 03:41:24PM -0600, Ryan Moats wrote: > > Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 01:01:56 PM: > > > > > From: Ben Pfaff <blp@ovn.org> > > > To: Ryan Moats/Omaha/IBM@IBMUS > > > Cc: dev@openvswitch.org > > > Date: 02/05/2016 01:02 PM > > > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > > > lflow incremental processing > > > > > > On Wed, Feb 03, 2016 at 04:20:23PM -0600, RYAN D. MOATS wrote: > > > > Add incremental processing of lflows in ovn-controller by > > > > taking the simple approach of marking each lflow dirty when > > > > touched and have lflow_run only process dirty flows. > > > > > > > > This needs unit test code before the RFC tag comes off. > > > > > > > > Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> > > > > > > I was envisioning something that would incrementally determine on a > > > per-flow basis whether anything needed to be recalculated. Starting > > > with a per-logical-datapath approach, as this patch does, is a nice > > > place to start because it is presumably easier, so I think it's a good > > > idea. > > > > I suspect we'll get to that point eventually, but I figured this would be > > easier to start with... > > > > > I don't understand how this particular patch is going to make a > > > difference, though, since ldp_run() appears to always dirty every > > > logical datapath. > > > > Well, when I ran the test that I used on Russell's now merged patch that > > improved things 15%, I was still seeing that each lflow_run call would > > process > > 36020 logical datapaths, 40012 matches and take a little more than half a > > second to complete > > > > Running that same test on this patch resulted in (after completion) > > only 2797 of the 36020 logical datapaths being processed - these generated > > 2934 matches being reprogrammed and a lflow_run call would complete in less > > than 50 msec. > > I think this is because lflow_run() marks a logical datapath "clean" > after processing any one logical flow in the datapath. I don't know why > it does that, but on the face of it it seems wrong. > I'll definitely revisit that as that was *not* the intent... Ryan
"dev" <dev-bounces@openvswitch.org> wrote on 02/05/2016 05:09:44 PM: > From: Ryan Moats/Omaha/IBM@IBMUS > To: Ben Pfaff <blp@ovn.org> > Cc: dev@openvswitch.org > Date: 02/05/2016 05:10 PM > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > lflow incremental processing > Sent by: "dev" <dev-bounces@openvswitch.org> > > Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 04:20:04 PM: > > > From: Ben Pfaff <blp@ovn.org> > > To: Ryan Moats/Omaha/IBM@IBMUS > > Cc: dev@openvswitch.org > > Date: 02/05/2016 04:20 PM > > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > > lflow incremental processing > > > > On Fri, Feb 05, 2016 at 03:41:24PM -0600, Ryan Moats wrote: > > > Ben Pfaff <blp@ovn.org> wrote on 02/05/2016 01:01:56 PM: > > > > > > > From: Ben Pfaff <blp@ovn.org> > > > > To: Ryan Moats/Omaha/IBM@IBMUS > > > > Cc: dev@openvswitch.org > > > > Date: 02/05/2016 01:02 PM > > > > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > > > > lflow incremental processing > > > > > > > > On Wed, Feb 03, 2016 at 04:20:23PM -0600, RYAN D. MOATS wrote: > > > > > Add incremental processing of lflows in ovn-controller by > > > > > taking the simple approach of marking each lflow dirty when > > > > > touched and have lflow_run only process dirty flows. > > > > > > > > > > This needs unit test code before the RFC tag comes off. > > > > > > > > > > Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> > > > > > > > > I was envisioning something that would incrementally determine on a > > > > per-flow basis whether anything needed to be recalculated. Starting > > > > with a per-logical-datapath approach, as this patch does, is a nice > > > > place to start because it is presumably easier, so I think it's a > good > > > > idea. > > > > > > I suspect we'll get to that point eventually, but I figured this would > be > > > easier to start with... > > > > > > > I don't understand how this particular patch is going to make a > > > > difference, though, since ldp_run() appears to always dirty every > > > > logical datapath. > > > > > > Well, when I ran the test that I used on Russell's now merged patch > that > > > improved things 15%, I was still seeing that each lflow_run call would > > > process > > > 36020 logical datapaths, 40012 matches and take a little more than half > a > > > second to complete > > > > > > Running that same test on this patch resulted in (after completion) > > > only 2797 of the 36020 logical datapaths being processed - these > generated > > > 2934 matches being reprogrammed and a lflow_run call would complete in > less > > > than 50 msec. > > > > I think this is because lflow_run() marks a logical datapath "clean" > > after processing any one logical flow in the datapath. I don't know why > > it does that, but on the face of it it seems wrong. > > > > I'll definitely revisit that as that was *not* the intent... > > Ryan Yes, that is a definite mistake and the more I look at this, the more I think it just isn't going to work correctly the way I've tried to code it. Trying to mark logical flows as dirty either means changing how the IDL code is generated (which doesn't strike me as a good idea) or adding a "dirty" column to the Logical_Flows table, which then means I'm looking at modifying the ovsdb_idl_txn_write__ code to touch this column appropriately and then adding code into lflow_run() method to clear this column (which can be done, but still feels a little crufty). Ben, does this analysis look right to you or am I missing a third path? Ryan
On Mon, Feb 08, 2016 at 10:34:05AM -0600, Ryan Moats wrote: > > > I think this is because lflow_run() marks a logical datapath "clean" > > > after processing any one logical flow in the datapath. I don't know > why > > > it does that, but on the face of it it seems wrong. > > > > > > > I'll definitely revisit that as that was *not* the intent... > > Yes, that is a definite mistake and the more I look at this, the more I > think > it just isn't going to work correctly the way I've tried to code it. > > Trying to mark logical flows as dirty either means changing how the IDL > code > is generated (which doesn't strike me as a good idea) or adding a "dirty" > column to the Logical_Flows table, which then means I'm looking at > modifying > the ovsdb_idl_txn_write__ code to touch this column appropriately and then > adding code into lflow_run() method to clear this column (which can be > done, > but still feels a little crufty). > > Ben, does this analysis look right to you or am I missing a third path? I'd consider making use of the ovsdb-idl support for change tracking. See this commit: From 932104f483ef4384d15dec1d26661da8da58de8d Mon Sep 17 00:00:00 2001 From: Shad Ansari <shad.ansari@hp.com> Date: Tue, 27 Oct 2015 13:55:35 -0700 Subject: [PATCH] ovsdb-idl: Add support for change tracking. Ovsdb-idl notifies a client that something changed; it does not track which table, row changed in what way (insert, modify or delete). As a result, a client has to scan or reconfigure the entire idl after ovsdb_idl_run(). This is presumably fine for typical ovs schemas where tables are relatively small. In use-cases where ovsdb is used with schemas that can have very large tables, the current ovsdb-idl notification mechanism does not appear to scale - clients need to do a lot of processing to determine the exact change delta. This change adds support for: - Table and row based change sequence numbers to record the most recent IDL change sequence numbers associated with insert, modify or delete update on that table or row. - Change tracking of specific columns. This ensures that changed rows (inserted, modified, deleted) that have tracked columns, are tracked by IDL. The client can directly access the changed rows with get_first, get_next operations without the need to scan the entire table. The tracking functionality is not enabled by default and needs to be turned on per-column by the client after ovsdb_idl_create() and before ovsdb_idl_run(). /* Example Usage */ idl = ovsdb_idl_create(...); /* Track specific columns */ ovsdb_idl_track_add_column(idl, column); /* Or, track all columns */ ovsdb_idl_track_add_all(idl); for (;;) { ovsdb_idl_run(idl); seqno = ovsdb_idl_get_seqno(idl); /* Process only the changed rows in Table FOO */ FOO_FOR_EACH_TRACKED(row, idl) { /* Determine the type of change from the row seqnos */ if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_DELETE) >= seqno)) { printf("row deleted\n"); } else if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_MODIFY) >= seqno)) printf("row modified\n"); } else if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_INSERT) >= seqno)) printf("row inserted\n"); } } /* All changes processed - clear the change track */ ovsdb_idl_track_clear(idl); } Signed-off-by: Shad Ansari <shad.ansari@hp.com> Signed-off-by: Ben Pfaff <blp@ovn.org>
Aha! that makes a lot more sense, but unfortunately, I don't think I'm grokking the code yet: 1. When using the baseling of SBREC_LOGICAL_FLOW_FOR_EACH, at startup, each lflow_run pass handles 12 flows and 12 matches... 2. When I tried using ovsdb_idl_track_add_all and SBREC_LOGICAL_FLOW_FOR_EACH_TRACKED, then at startup each lflow_run pass handles 13 flows and spits out warnings about unparsable match strings, which worries me mightily, but honestly, the column I care about is "match", which leads to... 3. Looking through the code I can't quite see how to translate from an ovsdb_idl structure to a column that I can use in ovsdb_idl_track_add_column - it looks like I have to reparse the ovs schema file and look up the table and column via that - is that really the case or am I just missing something obvious (again)? Thanks in advance, Ryan Ben Pfaff <blp@ovn.org> wrote on 02/08/2016 11:27:12 AM: > From: Ben Pfaff <blp@ovn.org> > To: Ryan Moats/Omaha/IBM@IBMUS > Cc: dev@openvswitch.org > Date: 02/08/2016 11:27 AM > Subject: Re: [ovs-dev] [PATCH] [ovn-controller] [RFC] Poor man's > lflow incremental processing > > On Mon, Feb 08, 2016 at 10:34:05AM -0600, Ryan Moats wrote: > > > > I think this is because lflow_run() marks a logical datapath "clean" > > > > after processing any one logical flow in the datapath. I don't know > > why > > > > it does that, but on the face of it it seems wrong. > > > > > > > > > > I'll definitely revisit that as that was *not* the intent... > > > > Yes, that is a definite mistake and the more I look at this, the more I > > think > > it just isn't going to work correctly the way I've tried to code it. > > > > Trying to mark logical flows as dirty either means changing how the IDL > > code > > is generated (which doesn't strike me as a good idea) or adding a "dirty" > > column to the Logical_Flows table, which then means I'm looking at > > modifying > > the ovsdb_idl_txn_write__ code to touch this column appropriately and then > > adding code into lflow_run() method to clear this column (which can be > > done, > > but still feels a little crufty). > > > > Ben, does this analysis look right to you or am I missing a third path? > > I'd consider making use of the ovsdb-idl support for change tracking. > See this commit: > > From 932104f483ef4384d15dec1d26661da8da58de8d Mon Sep 17 00:00:00 2001 > From: Shad Ansari <shad.ansari@hp.com> > Date: Tue, 27 Oct 2015 13:55:35 -0700 > Subject: [PATCH] ovsdb-idl: Add support for change tracking. > > Ovsdb-idl notifies a client that something changed; it does not track > which table, row changed in what way (insert, modify or delete). > As a result, a client has to scan or reconfigure the entire idl after > ovsdb_idl_run(). This is presumably fine for typical ovs schemas where > tables are relatively small. In use-cases where ovsdb is used with > schemas that can have very large tables, the current ovsdb-idl > notification mechanism does not appear to scale - clients need to do a > lot of processing to determine the exact change delta. > > This change adds support for: > - Table and row based change sequence numbers to record the > most recent IDL change sequence numbers associated with insert, > modify or delete update on that table or row. > - Change tracking of specific columns. This ensures that changed > rows (inserted, modified, deleted) that have tracked columns, are > tracked by IDL. The client can directly access the changed rows > with get_first, get_next operations without the need to scan the > entire table. > The tracking functionality is not enabled by default and needs to > be turned on per-column by the client after ovsdb_idl_create() > and before ovsdb_idl_run(). > > /* Example Usage */ > > idl = ovsdb_idl_create(...); > > /* Track specific columns */ > ovsdb_idl_track_add_column(idl, column); > /* Or, track all columns */ > ovsdb_idl_track_add_all(idl); > > for (;;) { > ovsdb_idl_run(idl); > seqno = ovsdb_idl_get_seqno(idl); > > /* Process only the changed rows in Table FOO */ > FOO_FOR_EACH_TRACKED(row, idl) { > /* Determine the type of change from the row seqnos */ > if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_DELETE) > >= seqno)) { > printf("row deleted\n"); > } else if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_MODIFY) > >= seqno)) > printf("row modified\n"); > } else if (foo_row_get_seqno(row, OVSDB_IDL_CHANGE_INSERT) > >= seqno)) > printf("row inserted\n"); > } > } > > /* All changes processed - clear the change track */ > ovsdb_idl_track_clear(idl); > } > > Signed-off-by: Shad Ansari <shad.ansari@hp.com> > Signed-off-by: Ben Pfaff <blp@ovn.org> > > -- > 2.1.3 >
diff --git a/ovn/controller/lflow.c b/ovn/controller/lflow.c index e586365..b5a0ebb 100644 --- a/ovn/controller/lflow.c +++ b/ovn/controller/lflow.c @@ -172,6 +172,7 @@ struct logical_datapath { uint32_t tunnel_key; /* 'tunnel_key' from Datapath_Binding row. */ struct simap ports; /* Logical port name to port number. */ enum ldp_type type; /* Type of logical datapath */ + uint8_t dirty; /* Does this path need to be reprogrammed? */ }; /* Contains "struct logical_datapath"s. */ @@ -205,6 +206,7 @@ ldp_create(const struct sbrec_datapath_binding *binding) ldp->tunnel_key = binding->tunnel_key; const char *ls = smap_get(&binding->external_ids, "logical-switch"); ldp->type = ls ? LDP_TYPE_SWITCH : LDP_TYPE_ROUTER; + ldp->dirty = 1; simap_init(&ldp->ports); return ldp; } @@ -233,6 +235,7 @@ ldp_run(struct controller_ctx *ctx) struct logical_datapath *ldp; HMAP_FOR_EACH (ldp, hmap_node, &logical_datapaths) { simap_clear(&ldp->ports); + ldp->dirty = 1; } const struct sbrec_port_binding *binding; @@ -240,12 +243,14 @@ ldp_run(struct controller_ctx *ctx) struct logical_datapath *ldp = ldp_lookup_or_create(binding->datapath); simap_put(&ldp->ports, binding->logical_port, binding->tunnel_key); + ldp->dirty = 1; } const struct sbrec_multicast_group *mc; SBREC_MULTICAST_GROUP_FOR_EACH (mc, ctx->ovnsb_idl) { struct logical_datapath *ldp = ldp_lookup_or_create(mc->datapath); simap_put(&ldp->ports, mc->name, mc->tunnel_key); + ldp->dirty = 1; } struct logical_datapath *next_ldp; @@ -291,7 +296,7 @@ lflow_run(struct controller_ctx *ctx, struct hmap *flow_table, * point in maintaining any flows for it anyway, so skip it. */ const struct logical_datapath *ldp; ldp = ldp_lookup(lflow->logical_datapath); - if (!ldp) { + if (!ldp || !ldp->dirty) { continue; } @@ -308,15 +313,6 @@ lflow_run(struct controller_ctx *ctx, struct hmap *flow_table, * after a packet leaves a logical router. Further optimization * is possible, but not based on what we know with local_datapaths * right now. - * - * A better approach would be a kind of "flood fill" algorithm: - * - * 1. Initialize set S to the logical datapaths that have a port - * located on the hypervisor. - * - * 2. For each patch port P in a logical datapath in S, add the - * logical datapath of the remote end of P to S. Iterate - * until S reaches a fixed point. */ struct hmap_node *ld; @@ -424,6 +420,7 @@ lflow_run(struct controller_ctx *ctx, struct hmap *flow_table, expr_matches_destroy(&matches); ofpbuf_uninit(&ofpacts); conj_id_ofs += n_conjs; + ldp->dirty = 0; } }
Add incremental processing of lflows in ovn-controller by taking the simple approach of marking each lflow dirty when touched and have lflow_run only process dirty flows. This needs unit test code before the RFC tag comes off. Signed-off-by: RYAN D. MOATS <rmoats@us.ibm.com> --- ovn/controller/lflow.c | 17 +++++++---------- 1 files changed, 7 insertions(+), 10 deletions(-)