Ben Pfaff <b...@ovn.org> wrote on 07/03/2016 11:51:17 PM: > From: Ben Pfaff <b...@ovn.org> > To: Ryan Moats/Omaha/IBM@IBMUS > Cc: dev@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 <b...@ovn.org> wrote on 07/03/2016 07:19:11 PM: > > > > > From: Ben Pfaff <b...@ovn.org> > > > To: Ryan Moats/Omaha/IBM@IBMUS > > > Cc: dev@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 <b...@ovn.org> wrote on 07/03/2016 05:40:59 PM: > > > > > > > > > From: Ben Pfaff <b...@ovn.org> > > > > > To: Ryan Moats/Omaha/IBM@IBMUS > > > > > Cc: dev@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 <rmo...@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... Safe travels, Ryan _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev