Expand and clarify consitency/durability docs in store.wit

[dicej]

The existing docs are somewhat vague about how the "read your writes" consistency model works in practice, so I've tried to make them more explicit. Also, they don't mention durability at all, so I've added a section dedicated to that.

Note that I've generally erred on the side of maximum portability across host implementations at the expense of strong guarantees for the guest. Based on previous conversations, my understanding is that we do want to support implementations backed by eventually consistent distributed systems, and that means portable guest code cannot assume a stronger consistency model than what such systems can deliver. Concretely, we must consider the scenario where a host has a pool of connections to multiple replicas in such a system such that a single component instance which opens the same bucket multiple times might get a different replica (each with its own view of the state) each time.

If we feel the guarantees described in these docs are too weak, we can certainly strengthen them at the expense of host implementation flexibility. Alternatively, we could add new APIs for querying and/or controlling the durability and consistency models provided by the implementation -- or even allow the guest to statically declare that it requires some specific consistency model by importing a specific interface corresponding to that model, analogous to what we did with the atomics interface.

Regardless of what set of (non-)guarantees and features we settle on, my main priority is to be as clear as possible about them so that application developers are not caught by surprise.

[rylev]

@dicej this is getting closer. There's a few places where I'd still like to clarify what is a MAY vs. SHOULD vs. MUST, but I think once those are taken care of, I'd be happy with the wording.

For the record, I'm not sure I'm fully on board with the semantics described here (vs. having it so that writes MUST be eventually reflected), but I do think the changes here at least make it much clearer what the semantics as written actually are.

[dicej]

@dicej this is getting closer. There's a few places where I'd still like to clarify what is a MAY vs. SHOULD vs. MUST, but I think once those are taken care of, I'd be happy with the wording.

Thanks; I just pushed an update; please let me know if I missed anything.

For the record, I'm not sure I'm fully on board with the semantics described here (vs. having it so that writes MUST be eventually reflected), but I do think the changes here at least make it much clearer what the semantics as written actually are.

I hear you. To me this boils down to whether we try to support BASE-style DBMSes such as Cassandra and CouchDB in this interface or not. Those systems are designed with a different set of tradeoffs in mind, favoring partition tolerance, low-latency and availability over consistency (i.e. in extreme circumstances they prioritize the former over the latter, and this can lead to lost writes in the case of unrecoverable replica failures). We could either:

• Support them by way of the SHOULD terminology I've used here
• Choose not to support them
• Support them, but in a separate interface (e.g. async-store?)

This PR represents the first option as a conservative default, but we can always change the SHOULDs to MUSTs later if we decide to pursue the second or third options.

[lukewagner]

Great to see the work here fleshing out consistency and durability and adding examples!

One request: perhaps surprisingly, even though Read Your Writes seems like it should be so basic that is comes "for free" (and indeed, on many single-node implementations, it does), in a highly-distributed key-value store, Read Your Writes does add some overhead. This is the case for Fastly's edge key-value store today, but I think the same laws of physics would apply to other low-latency geo-distributed kv stores where writes may take a different physical path than (cached) reads. Thus, if we're already designing wasi:keyvalue/store to be rather-weak and implementable in terms of many diverse kv stores impls anyways, I suggest we don't add the Read Your Writes consistency guarantee.

Also, Read Your Writes is just one of a lattice of rather-weak consistency models, so it'd be a bit arbitrary (at least without more of a broad survey of use cases) to pick "Read Your Writes" and not, say, Causal. Maybe one day we add more wasi:keyvalue/* interfaces that cover all these consistency models (we already have wasi:keyvalue/atomics which hits Sequential and could be expanded with more operations). But starting with wasi:keyvalue/store being just "eventually consistent" seems to make sense as a starting point.

Btw, another consistency(ish) guarantee I think we could include beyond "eventual consistency" is "there are no out-of-thin-air values" (i.e., if a read returns a value v, it's because some other write was made with that value v). No-thin-air-values is famously hard to rule out in weak formal theoretical models, but easy enough to hand-wave at and maybe useful as a complement to "eventual consistency" to illustrate the baseline.

[Mossaka]

Great to see the work here fleshing out consistency and durability and adding examples!

One request: perhaps surprisingly, even though Read Your Writes seems like it should be so basic that is comes "for free" (and indeed, on many single-node implementations, it does), in a highly-distributed key-value store, Read Your Writes does add some overhead. This is the case for Fastly's edge key-value store today, but I think the same laws of physics would apply to other low-latency geo-distributed kv stores where writes may take a different physical path than (cached) reads. Thus, if we're already designing wasi:keyvalue/store to be rather-weak and implementable in terms of many diverse kv stores impls anyways, I suggest we don't add the Read Your Writes consistency guarantee.

Also, Read Your Writes is just one of a lattice of rather-weak consistency models, so it'd be a bit arbitrary (at least without more of a broad survey of use cases) to pick "Read Your Writes" and not, say, Causal. Maybe one day we add more wasi:keyvalue/* interfaces that cover all these consistency models (we already have wasi:keyvalue/atomics which hits Sequential and could be expanded with more operations). But starting with wasi:keyvalue/store being just "eventually consistent" seems to make sense as a starting point.

Btw, another consistency(ish) guarantee I think we could include beyond "eventual consistency" is "there are no out-of-thin-air values" (i.e., if a read returns a value v, it's because some other write was made with that value v). No-thin-air-values is famously hard to rule out in weak formal theoretical models, but easy enough to hand-wave at and maybe useful as a complement to "eventual consistency" to illustrate the baseline.

Thanks for sharing this detailed perspective on the consistency models! You made a great point about read-your-write consistency potentially adding overhead in highly distributed systems. I agre that if we are designing wasi:keyvalue/store to be implementable across diverse KV store, starting with true "eventual consistency" as our baseline makes sense.

Would you be open to filing this as a separate issue? I think the current PR has good shape overall, and I'd prefer not to block its progress while we reconsider the consistency model. We could then have a focused discussion about the appropriate baseline guarantees for wasi:keyvalue/store and potentially plan for additional interfaces that address the consistency models in the future.

[Mossaka]

I am happy to merge this one as is - if there are no other active work you are doing @dicej

[dicej]

Would you be open to filing this as a separate issue? I think the current PR has good shape overall, and I'd prefer not to block its progress while we reconsider the consistency model.

I chatted with @lukewagner about this today, and he was concerned about pushing a PR to main that guarantees read-your-writes, only to yank that out soon after. I'll do another pass over this either on Friday or next week and aim to remove the read-your-writes parts, then we can do one final round of review and get this merged.

[dicej]

I just pushed an update that removes the "read-your-writes" guarantee and updates the pseudocode example to match.