[ovs-dev] v22 arrived a bit early (was Re: [ovs-dev, v21, 2/8] Persist ovn flow tables)

[Ben Pfaff]

On Mon, Jul 04, 2016 at 05:20:38PM -0500, Ryan Moats wrote:
> Ben Pfaff <blp at ovn.org> wrote on 07/03/2016 11:51:17 PM:
> 
> > From: Ben Pfaff <blp at ovn.org>
> > To: Ryan Moats/Omaha/IBM at IBMUS
> > Cc: dev at openvswitch.org
> > Date: 07/03/2016 11:51 PM
> > Subject: Re: [ovs-dev,v21,2/8] Persist ovn flow tables
> >
> > On Sun, Jul 03, 2016 at 08:03:54PM -0500, Ryan Moats wrote:
> > > Ben Pfaff <blp at ovn.org> wrote on 07/03/2016 07:19:11 PM:
> > >
> > > > From: Ben Pfaff <blp at ovn.org>
> > > > To: Ryan Moats/Omaha/IBM at IBMUS
> > > > Cc: dev at openvswitch.org
> > > > Date: 07/03/2016 07:19 PM
> > > > Subject: Re: [ovs-dev,v21,2/8] Persist ovn flow tables
> > > >
> > > > On Sun, Jul 03, 2016 at 06:08:23PM -0500, Ryan Moats wrote:
> > > > > Ben Pfaff <blp at ovn.org> wrote on 07/03/2016 05:40:59 PM:
> > > > >
> > > > > > From: Ben Pfaff <blp at ovn.org>
> > > > > > To: Ryan Moats/Omaha/IBM at IBMUS
> > > > > > Cc: dev at openvswitch.org
> > > > > > Date: 07/03/2016 05:41 PM
> > > > > > Subject: Re: [ovs-dev,v21,2/8] Persist ovn flow tables
> > > > > >
> > > > > > On Sun, Jul 03, 2016 at 10:35:27AM -0500, Ryan Moats wrote:
> > > > > > > Ensure that ovn flow tables are persisted so that changes to
> > > > > > > them chan be applied incrementally - this is a prereq for
> > > > > > > making lflow_run and physical_run incremental.
> > > > > > >
> > > > > > > Signed-off-by: Ryan Moats <rmoats at us.ibm.com>
> > > > > >
> > > > > > This time I think I've figured out properly what I'm concerned
> about.
> > > > > > Before, I think I was distracted enough by 'is_new' and the
> remaining
> > > > > > patches that I hadn't formulated it correctly yet.
> > > > > >
> > > > > > ofctrl needs to support the following operations on physical
> flows:
> > > > > >
> > > > > >     1. Add flow.
> > > > > >     2. Update flow.
> > > > > >     3. Remove flow.
> > > > > >
> > > > > > lflow generates physical flows from logical flows in a
> one-to-many
> > > > > > fashion.  That is, a single logical flow can yield zero, one, or
> > > > > > multiple physical flows.  Other sources can yield physical flows
> too,
> > > > > > and ofctrl needs those sources to pretend that they are generated
> > > from
> > > > > > something similar enough to a logical flow that it can be
> uniquely
> > > > > > identified with a UUID.  All that makes sense.
> > > > > >
> > > > > > Case #1, "add flow", for physical flows is implemented via
> > > > > > ofctrl_add_flow() with is_new == true.  This is straightforward
> > > enough.
> > > > > > Add the new flow to the flow table, add it to the list of
> physical
> > > flows
> > > > > > associated with the UUID passed in, suppress duplicates.
> > > > > >
> > > > > > Case #3, "remove flow", for physical flows is implemented via
> > > > > > ofctrl_remove_flow().  This removes all the physical flows
> associated
> > > > > > with a UUID.  This is almost as straightforward.  The
> implementation
> > > > > > here does appear to mean that, if there is a bug in the logical
> flow
> > > > > > table such that two different logical flows generate physical
> flows
> > > with
> > > > > > the same match, then there is a behavioral change versus the
> previous
> > > > > > implementation: previously, one of the flows to be added in the
> main
> > > > > > loop would end up in the flow table, but after this change the
> > > removal
> > > > > > will not reveal an underlying flow but just delete it, at least
> until
> > > > > > something happens to fully refresh flows instead of just
> > > incrementally
> > > > > > adding and removing them.  That is an edge case; it might be
> > > necessary
> > > > > > to fix it but it is not the top priority.
> > > > >
> > > > > I'm going to pull your text for case 3 up here and let's deal with
> that
> > > > > first:
> > > > >
> > > > > > Now let's go back to the edge case concern I expressed about case
> #3.
> > > > > > Thinking harder, I don't think it's so much of an edge case, at
> least
> > > > > > not to the extent that exhibiting it requires a buggy logical
> flow
> > > > > > table.  Suppose that a single transaction from ovn-northd deletes
> a
> > > > > > Logical_Flow with uuid U1 and adds a new Logical_Flow with uuid
> U2.
> > > > > > This will yield a call to ofctrl_remove_flow(U1) and (except in
> > > > > > pathological cases) one or more calls to ofctrl_add_flow(U2).
> > > Suppose
> > > > > > that the sets of physical flows for U1 and U2 overlap in terms of
> > > their
> > > > > > key fields (table_id, pipeline, match, ...).  Then I believe that
> the
> > > > > > result will currently depend on the order of the calls to
> > > > > > ofctrl_remove_flow() and ofctrl_add_flow():
> > > > > >
> > > > > >         * If the removal precedes all the adds, all is well.
> > > > > >
> > > > > >         * If the removal follows any of the adds, the remove will
> > > > > >           falsely delete all the flows that should be added.
> > > > > >
> > > > > > Does any of this ring a bell?
> > > > >
> > > > > I see where your analysis is going, but I think the problem is on
> the
> > > > > add side :) : On the delete side, the code checks for U1 and so
> none
> > > > > of the U2 flows will be removed.  However, I see the problem on the
> add
> > > > > side: because if U2 creates a duplicate flow to what's in U1, then
> > > > > right now the U2 flow is discarded silently and after U1 is
> deleted,
> > > > > the flow incorrectly disappears.  The simplest thing that comes to
> > > > > mind is to make two passes through the changed flows: the first to
> > > > > handle deletes and the second to handle adding/modifying flows.
> > > >
> > > > That will only make the problem harder to trigger.  It will work if
> the
> > > > only way that overlaps can come up is from within Logical_Flow
> itself.
> > > > If ovn-controller has two independent pieces of code that can
> generate
> > > > overlapping flows, then the same problem can arise again.  That is
> > > > unlikely today, but it will be sitting in the code like a time bomb
> > > > waiting to surprise us months or years down the road with
> unpredictable
> > > > behavior.  With this approach, the cure would be to make two passes
> > > > through the entire pipeline of code in ovn-controller that can
> generate
> > > > flows, the first pass to remove and the second pass to add.  That
> would
> > > > be a pain.
> > > >
> > > > I suggest that we avoid going down that path by making ofctrl track
> > > > flows with duplicate keys, when those keys have different UUIDs.
> This
> > > > could be done within an hmap, if struct ovn_flow would add an
> ovs_list
> > > > of duplicates (probably preferred).  We'd want to use some kind of
> > > > deterministic method to determine which one actually gets installed,
> so
> > > > as to avoid oscillation; for example, it could be done based on UUID
> > > > ordering.  This will add a little bit of code now, but I think that
> it's
> > > > well worth it for predictability and for making code harder to screw
> up
> > > > in subtle ways by ordering things wrong.
> > > >
> > > > > > Case #2, "update flow", is implemented via ofctrl_add_flow() with
> > > is_new
> > > > > > == false.  This is the one that I'm worried about and where I do
> not
> > > > > > understand the strategy.  What I'd expect is that the client
> would be
> > > > > > able to say, one way or another, "Here is the new set of physical
> > > flows
> > > > > > F2 associated with uuid U."  If some of the flows in F2 coincide
> with
> > > > > > the set of physical flows F1 that had previously been associated
> with
> > > U,
> > > > > > then it would make sense that nothing actually changes in the
> > > physical
> > > > > > flow table.  But there are many more possibilities.  For example,
> if
> > > F1
> > > > > > contains more flows than F2, then there needs to be a way to
> indicate
> > > > > > that some of the physical flows associated with U should be
> removed.
> > > > > > There is code in ovn_flow_lookup_by_uuid() that tries to tolerate
> > > some
> > > > > > kind of changes to flow matches from F1 to F2 (match fields that
> > > appear
> > > > > > or disappear), but I don't know a reason to believe that only
> those
> > > > > > changes can happen from F1 to F2; even after explanation, they
> look
> > > like
> > > > > > magic to me.
> > > > > >
> > > > > > Maybe there is a belief here that a given Logical_Flow has some
> kind
> > > of
> > > > > > consistency, e.g. that its match and action, etc. do not change
> after
> > > > > > the logical flow is added.  That might be a useful assumption,
> and we
> > > > > > could enforce it if we made some (all?) Logical_Flow columns
> > > immutable.
> > > > > > But it is not currently guaranteed to be true: I can use
> ovn-sbctl
> > > (or
> > > > > > whatever) to modify all of the columns in a Logical_Flow row in
> > > > > > arbitrary ways.  This means that F1 and F2 might also have
> nothing in
> > > > > > common for a given Logical_Flow U.
> > > > >
> > > > > If that's not the case, then I think the simplest thing to do is to
> > > > > delete all the existing physical flows for the modified logical
> flow
> > > > > and then recreate them as if they were a new add. That sacrifices
> some
> > > > > performance, but it should be correct :)
> > > > >
> > > > > Now, the question that arises is how to handle the flows created in
> > > > > physical.c, but I think that should be relatively simple to handle.
> > > >
> > > > My thought is that the API should change to something like this,
> where
> > > > "key" is (table_id, priority, match) and "value" is actions.  These
> > > > "key" and "value" names wouldn't actually be used this way but I find
> it
> > > > a good conceptualization:
> > > >
> > > >     ofctrl_add_flow(uuid, key, value)
> > > >
> > > >         Add a flow that maps from key to value.  If there's a
> duplicate
> > > >         key with a different uuid, add the flow anyway but use a
> > > >         deterministic rule (e.g. based on UUID order) to determine
> which
> > > >         one will be in the real flow table.  If there's a duplicate
> key
> > > >         with the same uuid, do nothing and log a warning.
> > > >
> > > >     ofctrl_remove_flow(uuid)
> > > >
> > > >         Remove all the flows that have the given uuid.
> > > >
> > > > We could also add a shortcut for the case where a key maps to exactly
> > > > one value, e.g.:
> > > >
> > > >     ofctl_set_flow(uuid, key, value)
> > > >
> > > >         Equivalent to:
> > > >
> > > >             ofctrl_remove_flow(uuid);
> > > >             ofctrl_add_flow(uuid, key, value);
> > > >
> > > >         but easy to optimize for the case where nothing actually
> > > >         changes.
> > >
> > > I think we are converging, because I generally agree with the above
> APIs.
> > > (I'm not quite sure when ovn_set_flow would get used, but I can put it
> > > in).
> >
> > I think that there are a few cases where a UUID is associated with
> > exactly one physical flow; consider_neighbor_flow() might be an
> > example.  Maybe this is premature optimization, dunno.
> >
> > > I think we want the key to track both uuid/value pairs (you may be
> > > thinking that already, but it wasn't 100% clear to me from your
> > > text above). Given that we want a deterministic rule for picking
> > > which value based on uuid if the key maps to more than one uuid/value
> > > "pair", an hmap may be the answer, but I'll look around some more
> > > to see if another structure strikes me as being a better candidate.
> >
> > Here's a summary of the data structure model I have in mind.  It is
> > really not so far from what you've implemented already:
> >
> >         one-to-many map from uuid to ovn_flow
> >         one-to-many map from (table_id,priority,match) to ovn_flow
> >
> > where the latter map should ordinarily be one-to-one in steady state but
> > might have duplicates either intermittently while doing adds and removes
> > within a given iteration of the poll loop or more permanently if there's
> > a bug in, e.g., the logical flow table output by ovn-northd.
> >
> > > For now, I think UUID ordering is a fine rule for breaking ties
> > > between uuid/value "pairs".
> >
> > Seems fine to start.
> >
> > > Obviously, this will take a bit of recoding, but I like this direction,
> > > because I've had some of these items on my "how to address that in the
> > > next pass" list and now they will be addressed...
> >
> > Great.
> 
> Surprise!  It turned out to be simpler than I thought it would be, since
> (as you said) it wasn't really that far from what was already there.
> 
> Anyway, v22 is posted and I believe it does everything we discussed
> above...

Great, thanks!