[Solved] Replying to queries on disjoint keys

[p-avital]

We've recently put up for debate whether queryables should be able to reply on Key Expressions (KE) that are disjoint from the query's KE. This discussion's goal is to act as a way for the members of the team to express their opinions with higher fidelity before a final debate.

[p-avital]

For context, the current behaviour is that a queryable may reply with any KE to any query. The query's KE thus selects the queryables that get a chance to reply, but doesn't restrict their set of possible replies in any way.

We currently have software in the zenoh ecosystem that relies on this "feature", and know of use-cases that could benefit from it.

However, this goes against the intuition that "I queried for X, I should get data for X", and breaks an assertion that can be made on subscribers that you'll only get data relevant to what you asked for in your KE.

Note that this is distributed runtime behaviour: we should be very careful about breaking changes around this behaviour.

My personal stance is that we should restrict replies to intersect with the queried KE by default, but provide some form of escape hatch for users that would rather work without this restriction, which can be somewhat strong.

[Mallets]

To keep things symmetrical, I would add allow_disjoint_replies on get and reply.

[sreeja]

In this case, a query will get a different key expression only when allow_disjoint_replies is set at both queryable side and querier side.
Why don't we allow to set it only on get? That way, the queryable receiving the get can see that intersection is required and hence drop disjoint samples there itself. With a single flag per get, we can filter on both queryable and querier sides.

[p-avital]

This would require telling the queryable about the get's disjoint reply tolerance. While I think we'd do so eventually (allowing network filtering, and possibly switching the queryable API presentation from "I want to reply disjoint keys" to "does that query also accept disjoint keys?"), this would currently be a protocol break

[JEnoch]

It wouldn't break the protocol if this option is passed as a query parameter (with _ prefix as zenoh specific).
E.g.: get("a/b?_allow_disjoint_replies")

BTW, an alternative name maybe more explicit for users: _accept_unmatching_replies

[p-avital]

That's a lot of bytes for a boolean... how about _adr, with the unstable API as the only advertised way to construct it?
Still, I'd rather not send it like that to avoid future incompatibility issues. Being explicit on both sides for now allows us to contain breakage more easily.

[Mallets]

My 2 cents.

For safety and consistency reasons, I believe the default behaviour of a query should be the following:

• a get to a/* should reach all queryable matching a/*
• only replies matching a/* are returned to the issuer of the get

I feel this is a natural expected behaviour that can be found in other technologies like SQL, find command line tool, etc.

This kind of default behaviour provides the guarantee the all key_expr contained in the replies actually match the same structure of the key_expr being queried. This allows, e.g. to issue a query on a/*/c/*/e and to be sure that all key_expr in the replies will have exactly 5 chunks. User code can then safely parse the key_expr to extract e.g. the content of the 2nd and 4th chunk.

If such guarantee is not provided, then user code should explicitly check first that key_expr has the expected form and then to parse it. I fear that these kind of checks will not be done by users in actual code since it is a bit counter-intuitive to expect to receive key_expr not matching the key_expr being queried. In practice, the user should handle all the reply key_exprs in the same way as he had queried ** instead of a/*.

In case of subscribers and queryables, key_exprs delivered to the subscribers' and queryables' callback are guaranteed to match the key_expr (e.g. a/*) used in the declare_subscriber and declare_queryable. Therefore, user code can safely parse the received the key_expr. It would hence desirable to have the same level of guarantee by default also for replies, making Zenoh's expected behaviour consistent across subscriber, publisher, queryable, and queries.

Then, thinking about embedded world, providing default filtering would enable early dropping of unwanted replies. Such behaviour would allow bandwidth savings in the network, especially in the last hop which could operated over a constrained/sensor network.

Finally, as mentioned by @p-avital , not filtering replies matching the get key_expr may be useful in special use cases where we would like to enable it. However, these are special use cases and shouldn't be the default behaviour expected in the most common use cases. So, I echo @p-avital and also my stance is that we should restrict replies to intersect with the queried key_expr by default, but provide some form of escape hatch for users that would rather work without this restriction.

[cguimaraes]

I echo the rationale already exposed by @p-avital and @Mallets .

• As a user, whenever I do a query I expect no more or no less than what I asked for. Allowing other things to go through means that as a user I always need to check what I received. That breaks the concept of layering and hurdles the simplicity for the user.
• if as a user, I need other things to go through, then it means that my information model is wrong under the Zenoh vision. Zenoh provides ways to express any with either * or **, so a Zenoh application must make use of them or fail to be compliant with Zenoh concept. Workarounds can still be done at user code, but it is up to the user to implement the non-compliant behavior.
• the more time we allow such behavior, the more users might exploit it....to the point that it would be too late to change without having a big regression on the runtime behavior.

Summing up, I would prefer to see it not allowed or, if we allowed it for this release, to make it explicitly that the user MUST not do it.

[Mallets]

If that's the specific scenario, and you are aware of what is being done. Then, fine. We should provide a way to do it by simply enabling the option on the get and reply (or any other place). My argument is that it shouldn't be the default behaviour, which addresses a very specific use case while removing safety guards for most common use cases.

[sreeja]

I agree with having it as the default behaviour. I am only against making it the "only" behaviour.

[Mallets]

Ok, but as suggested, it wouldn't be the only behaviour. The idea is still to allow the "non-filtered" behaviour by explicitly setting it. By doing so, the user is fully aware of the expected behaviour of the query.

[cguimaraes]

@kydos , I answered below with something I can see as a compromise from both opinion sides.
@sreeja , the problem is when the system is dynamic and/or has many different participants. That could make the assumptions on what is expected void.

[kydos]

The real question is when would a Queryable reply with something that does not match its key. I think that the answer is when this makes sense for the application... Or if there is a bug.

No assume there is a bug, of all a sudden the queryable reply are dropped and I cannot figure out why I don't receive any data... Now I am a very confused user...

[kydos]

As we've discussed there are simple examples that show the need for either expanding our query syntax or allowing the flexibility to respond with a key that matches the queryable expression but does not necessarily matches the query expression.

Here is a rather simple example, imagine we want to have a queryable that answers with dragon quotes. The key expression for the queryable could be something like zenoh/quotes/*. This queryable should be able to:

• Return all the quotes when queried with zenoh/quotes/*
• Return the nth quote when being queried with zenoh/quotes/n or empty strings if such a quote does not exist
• Return a random quote when being queried with zenoh/quotes/any
• Return the number of available quotes when being queried with `zenoh/quotes/howmany

Now when implementing this queryable the question becomes what should we answer for the query on zenoh/quotes/any, suppose that the 18th quote was selected, then we could answer:

• (zenoh/quotes/any, "An adventure isn't worth telling if there aren’t any dragons in it"), or
• (zenoh/quotes/18, "An adventure isn't worth telling if there aren’t any dragons in it")

Answering with zenoh/quotes/any it is not strictly correct as the actual name of this resource is zenoh/quotes/18. At the same time answering with zenoh/quotes/18 returns a key that does not match the query -- but matches the queryable declaration.

This is a simple example that shows how it is handy at times to be able to return something that does not match the key of the query.

The specific problem could be resolved differently if we would allow to get any-n when matching a wildcard, in other terms, we could have a syntax like zenoh/quote/*[n] (assuming we could use [] in this position) to have at most n elements out of all the matching.

In this case, instead of using zenoh/quotes/any, one could use zenoh/quotes/*[1] and everything would be in order. But we don't have this now and we should consider adding it.

I think that constraining a Queryable to answer with keys that match the query can be overly limiting in some use cases. If we introduce enforcing of some kind I think we'd need three levels:

• None
• Match Queryable Key Expression
• Match Query Key Expression

[kydos]

• None
• Match Queryable Key Expression
• Match Query Key Expression

One could argue that a reply should match both, but I don't think matching the queryable's KE is useful, in the sense that the person who declared the queryable is in control of the replies it constructs.

@p-avital, not sure I understand your remark above since (1) you have a clear example outlined above for which it makes sense to comply only with the Queryable key-exr and (2) the implementor of the queryable is always in control to what it answers... Thus if you take this argument to the end it leads to the fact that NONE is all we need ;-)

For one to construct a queryable on a KE and UNintentionally reply on different keys would be a goof, but I don't think it's common enough that it needs checking.

The problem is not whether you think or I think it is common enough. I think we have even internally some key use cases that require this. Thus it is a valid use case and BTW in line with the idea that zenoh routes queries does not route answers. I think this is perhaps the source of the confusion. When publishing data what we route is the key of the data, thus it is normal that the data reaches the subscribers that have a matching subscription. When we route a query we route the key-expr of the query and this is why the queryable that match receive the data. The rest, should not be our business.

BTW for me the default should be NONE, the reason being that filtering can also lead to unexpected behaviour to the user that are even more surprising.

I strongly disagree. Optional safety is basically the same as no safety, especially if the API is unstable as we plan for it to be at first. Exactly one sentence is required on declare_queryable's (and .reply just to be safe) documentation: "by default, attempting to reply on a KE that does not intersect with the queried one will error out, you can disable this check through ".

It is not a question of safety, it is a question of invariants. The real questions is about the invariants that we guarantee. That is it.

On top of that, for those that don't read docs, the surprise wouldn't be "I tried to do X and nothing happened", but "I tried to do X and it returned an error". Extremely short feedback cycle, compared to "our infrastructure always worked, for months, but ever since Tom deployed something, it keeps panicking on some queries because of parsing errors".

Again this is a matter of invariants and who checks the invariants. Having minimal invariants enforced by the infrastructure keeps it simple and efficient and allows application to have more freedom on how to leverage the infrastructure. This is the contract that should be clear.

Some users ARE going to assume this check is in place, and get bitten strongly and very late if that isn't true.

Sure, but this is one of the potential issues that they may face. We can help mitigating it, but that is the cost in terms of CPU cycles, additional code and API complexity? Especially compared to a simple filter on the receiving side? This is what we should put on the two side of the balance.

[Mallets]

The most predictable a system is, the shorter the feedback cycle is, the better to me. Having filtering on by default also provides more guarantees out of the box.

Let me expand, if a Queryable answers with something that does not match the query or the queryable key, either is a bug or is intended as a consequence of the application semantics.

That's exactly my point. If it is a bug, it can be quickly caught. If it's application semantics, then let the application explicitly disable the check and react accordingly. No hidden/counter-intuitive behaviours for the newcomers and additional guarantees on KE structure on replies.

Regarding safety, I agree with @p-avital that Optional safety is basically the same as no safety. Like in Rust, safe by default, unsafe on purpose when needed. Therefore, to me the default behaviour should be enforcing the query's KE matching. This aligns with the semantic that can be found in other key-value storages, thus it wouldn't surprise many users.

When we route a query we route the key-expr of the query and this is why the queryable that match receive the data. The rest, should not be our business.

I disagree. The user most of the time would query something like a/*/c/* and it would expect to retrieve the value of the 2nd and 4th chunk. We are having already internal use cases that do that. Since no guarantees are provided on the structure of the KE in the reply, the user would ALWAYS need to do the following to SAFELY extract the 2nd and 4th chunk:

• Manually validate that KE has the right number of chunks
• Manually validate that 1st and 3rd chunk actually match what he asked for
• Extract the 2nd and 4th chunk

I'm not expecting users to do this kind of checks every time, by default they will assume that what they receive is what they asked for. After already few decades, NULL pointers are not always checked in C (see https://hackernoon.com/null-the-billion-dollar-mistake-8t5z32d6). The users not checking the structure of the KE would most certainly lead to an index out of bound and a segfault. So, I see a stronger guarantee highly beneficial for the user and the safety of system.

If the user wants the behaviour to explicitly accept any KE in the reply, they are free to explicitly enable it and they are aware the guarantee on KE is removed, so it's up to them to parse the KEs in the replies accordingly. Regarding the actual mechanism to configure/disable the matching, it has been suggested by @sreeja to allow the user to set it when performing a .get(). In that respect, we can think about a reserved parameter for that. E.g. _disjoint_replies or any other name.

[p-avital]

Just to make it clear, because I feel like we're getting strawman'd here with the "but this restricts what the user can do": Forbidding dijoint replies entirely is NO ONE's position.

I consider invariant enforcement a safety critical: if my system crashes because someone somewhere (remember this is a distributed system) made a queryable that doesn't respect an emergent invariant (no one in the existing ever replied on disjoint keys, so this case was never tested for, but assumed), what good was memory safety if the crash causes the same kind of issues ? What if the system that assumed that invariant is no longer maintained, and the invariant breaker comes after ? Invariants WILL be assumed, and distributed systems are intrinsically more complex than average. We have a chance to help remove a bug-category at extremely low cost, and without actually restricting what can be done, why skip that chance?

Keep in mind that this check's cost is basically null (one KE intersection per reply, as opposed to the potential hundreds that are done for every single put). Checking on queryable side IS an optimisation, as sending data over the network that shouldn't be there is orders of magnitudes more costly. It also helps users detect why the reply hasn't reached the querier while experimenting, whereas a querier would just ignore non-compliant replies.

[p-avital]

Also, if we don't check by default, but offer an API to check, people are just gonna do their own (possibly less efficient) checks, rather than use an optional (and possibly unstable) API.

[kydos]

Just to make it clear, because I feel like we're getting strawman'd here with the "but this restricts what the user can do": Forbidding dijoint replies entirely is NO ONE's position.

@p-avital not sure why you think I was hinting that. I think that there are really two areas of debate (1) How many options we should have and (2) what should be the default.

I consider invariant enforcement a safety critical: if my system crashes because someone somewhere (remember this is a distributed system) made a queryable that doesn't respect an emergent invariant (no one in the existing ever replied on disjoint keys, so this case was never tested for, but assumed), what good was memory safety if the crash causes the same kind of issues ? What if the system that assumed that invariant is no longer maintained, and the invariant breaker comes after ? Invariants WILL be assumed, and distributed systems are intrinsically more complex than average. We have a chance to help remove a bug-category at extremely low cost, and without actually restricting what can be done, why skip that chance?

Again the question is not about checking invariants. The question is who should check the invariants and what are the invariants that make sense for my application.

Keep in mind that this check's cost is basically null (one KE intersection per reply, as opposed to the potential hundreds that are done for every single put). Checking on queryable side IS an optimisation, as sending data over the network that shouldn't be there is orders of magnitudes more costly. It also helps users detect why the reply hasn't reached the querier while experimenting, whereas a querier would just ignore non-compliant replies.

To be useful the invariant should be decided by the querier and checked on the Queryable. It is not just a matter of optimisation, it is a matter of catching the error at the right place and avoid silent drops as discussed above.

[Mallets]

After some additional discussion, the conclusion is:

• The default behaviour guarantees that only replies with a key expression matching the query key expression are delivered to user code
• The following unstable constructor will be added to the get builder:

enum ReplyKeyExpr {
	Any,
	MatchingQuery,
}

fn accept_replies(self, ReplyKeyExpr) -> Self;

• The following unstable function will be added to the Query type:

fn accepts_replies(&self) -> ReplyKeyExpr;