Is watch linearizable?

[mladedav]

Sorry if the question has been answered before, but I have been unable to find an authoritative answer. The documentation seems to me to have conflicting information. I have found this issue, but the last question has been left unanswered. There are also lately a few issues and PRs about linearizability tests for watch which could imply that it is in fact linearizable.

The documentation lists these guarantees considering watch:
Watches make three guarantees about events:

• Ordered - events are ordered by revision; an event will never appear on a watch if it precedes an event in time that has already been posted.
• Reliable - a sequence of events will never drop any subsequence of events; if there are events ordered in time as a < b < c, then if the watch receives events a and c, it is guaranteed to receive b.
• Atomic - a list of events is guaranteed to encompass complete revisions; updates in the same revision over multiple keys will not be split over several lists of events.

The Ordered property would seem to imply linearizability.

However, elsewhere in the documentation it is explicitly stated that watch is not linearizable:

etcd does not ensure linearizability for watch operations. Users are expected to verify the revision of watch responses to ensure correct ordering.

This seems to me to be clashing with the previous guarantee. So now I am unsure what to believe. Or is ordering guaranteed and the issue is that the events may be received late and thus do not satisfy linearizability guarantees regarding wall-clock? I guess that would mean the last sentence to mean that a user should check the revision against latest revision it got from the server some other way but I would not expect that to be the case.

[serathius]

The Ordered property would seem to imply linearizability.

That's not correct. Linearizability implies order, but order doesn't imply linearizability. Watch is serializable, which implies that responses are ordered. However as watch is eventually consistent we cannot guarantee linearizability. In simple terms watch returns a history of changes done in etcd, but events in watch might be delayed by unspecified time from when they really happened.

is ordering guaranteed and the issue is that the events may be received late and thus do not satisfy linearizability guarantees regarding wall-clock?

Yes.

[mladedav]

Thanks for the reply. Just to be 100 % percent sure, this sentence: Users are expected to verify the revision of watch responses to ensure correct ordering. then really means that users should check the revision against revisions obtained from other calls that are actually linearizable?

In an extreme case where I use watch in vacuum, I do not have to check anything as long as I don't tie the result to wall clock time or other responses?

[serathius]

Yes, for example if you want to know latest values of a key, you should never depend on watch alone. It's response could be delayed by unspecified amount. You need to execute any linearizable request and use the revision you received to confirm. Linearizable request you send could be totally unrelated to keys you watch, but the revision it returns will be the latest revision which can be correlated with watch events. If you have the watch event with the same revision, you know latest state of the key.

[mladedav]

Thanks a lot. I'll go ahead and make a PR to the docs to hopefully clear that up for others like me.