config: enhance ZoneConfig expressiveness

[petermattis]

From a comment on #4866:

Instead of shorthand at the CLI level, we should consider reworking the protobuf completely. In addition to making it awkward to express the basic constraint of the number of target replicas, it is completely unable to express negative constraints (any store but hdd) or diversity constraints (in a deployment with more datacenters than the replication factor, we don't want two in the same DC, but we can't get that today without pinning the specific datacenters).

I'd be in favor of introducing a num_replicas field which would be used in place of len(attrs). If attrs are present they would be used to constrain the replica selection in the way that they are today, otherwise it is as if there are num_replicas empty attr entries. No need to actually address the issues around negative or diversity constraints at this point.

[d4l3k]

For diversity constraints we could use something like https://github.com/Knetic/govaluate which would let people specify arbitrary math/boolean logic strings. It would let us do things like us_east && !hdd.

Also would allow for even more flexible queries by passing numerical values about the state of the node. For example: avg_ping < 100 || store_replica_count < 100 || free_disk > 1000000000.

It also has regular expression support region =~ "europe_*".

@bdarnell

[petermattis]

I'm not sure how govaluate would allow us to model diversity constraints. In particular, how would you model 3 replicas with no 2 replicas on the same rack unless there are less than 3 racks? For diversity constraints, the locations of the other replicas are matter.

I see how general expressions would allow us to model negative constraints, but I'm not sure that generality is warranted and it feels like a big gun to be handing users. I worry that users would set up configs that would vastly limit the candidate stores leading to poor performance and/or confusing/surprising behavior.

Lastly, we should pay a small bit of attention to efficient implementation. Currently, on every allocation we loop over all of the stores and generate a list of candidates and then randomly select from that list. For a given zone config, the candidate list changes slowly and it currently looks possible that we could cache it. I'm not seeing anything about general expressions that would prohibit that, but want to make sure this is something you're considering as well.

[d4l3k]

For that specific example, you could have something like num_racks < 3 || num_replicas_on_rack < 2. It would definitely require more than just govaluate though.

That's true. Just found that library and thought it would be a neat thing to use. Might not warrant it however.

As for performance https://github.com/Knetic/govaluate#benchmarks seems to indicate that it's reasonably quick. Parsing and running are two different steps but it looks like parsing takes most of the time.

[d4l3k]

Could also make pseudo functions with stuff like [count:"rack_.*"] < 3 || [replicas_with:\[first:"rack_.*"\]] < 3.

https://gist.github.com/d4l3k/53ab3e333299ed9b93f0a1c1065a18b9

[bdarnell]

We already have an expression language: SQL. I'm not sure how far down the path of arbitrary expressions we should go, but we should aim for a subset of SQL syntax instead of a subset of Go (so AND and OR instead of && and ||). We might even be able to come up with a clever usage of aggregate functions and GROUP BY to express diversity constraints, although I think it's probably better to make diversity constraints an explicit feature instead of overgeneralizing.

[petermattis]

@d4l3k Yes, evaluation of the individual expressions is fast, but I'm pretty sure it is going to be a problem for allocation to be evaluating the zone config expression on every store for every allocation. Your example of smashing diversity constraints into general expressions isn't terribly compelling. I agree with Ben that we should make diversity constraints an explicit feature. For example, instead of a single expression we could imagine there are a series of expressions. diversity(us-.*), require(hdd), prohibit(eu-.*) would provide diversity across nodes containing an attribute matching us-.*, require nodes to have the attribute hdd and prohibit nodes from containing the attribute eu-.*. To make this more terse we could provide short-hand operators: ~us-.*, +hdd, !eu.*. We'd want some rule about how to drop constraints when they can't be achieved.

Just brainstorming here. I haven't fully thought this through.

[d4l3k]

I agree that it's overly cumbersome. Shorthand notation was one of the
first things I thought of but figured it wasn't complex enough. I thought
we needed logic operations to do things like "us-east or eur-uk".

For the use case of "3 replicas with no 2 replicas on the same rack unless
there are less than 3 racks," did you imagine those numbers to be
configurable or just a special flag you could put on a zone?

SQL with GROUP BY feels really odd to me, but SQL could work if we define
custom functions for diversity(us-.*), require(hdd), prohibit(eu-.*).
That would address the require("us-east") OR require("eur-uk") problem.

[d4l3k]

I just added a WIP RFC for this. #7660

[spencerkimball]

Closed by #12165.