Hi Karolos, You're right about the timing assumptions needed to make sync+read / writes linearizable. This is a tradeoff many systems make, the risk of violating linearizability due to this is usually considered minimal while the benefit of saving a quorum operation on reads is significant. Nevertheless, we do consider this a problem and there is an open jira. I believe Michael was looking at it recently.
Ignoring this issue for a second, Kfir Lev-Ari (together with me), tried to answer your question by defining a new consistency semantics that captures ZK: http://webee.technion.ac.il/people/idish/ftp/OSC-IPL17.pdf This was done in the context of this work: https://www.usenix.org/system/files/conference/atc16/atc16_paper-lev-ari.pdf Cheers, Alex On Sun, Aug 18, 2019 at 12:34 PM Jordan Zimmerman < jor...@jordanzimmerman.com> wrote: > Isn’t this a “no true Scotsman” argument? By this definition any > eventually consistent system can never be considered linearizable. Right? > > ==================== > Jordan Zimmerman > > > On Aug 18, 2019, at 1:47 PM, Karolos Antoniadis <karo...@gmail.com> > wrote: > > > > Hi Jordan, > > > > When Aphyr tested ZooKeeper, he did not seem to know that it is not > > linearizable. See here: https://github.com/jepsen-io/jepsen/issues/399, > where > > I pointed-out that even with *sync + read*, ZooKeeper might return stale > > data. > > > > ZooKeeper can only be considered linearizable if we assume that specific > > timing constraints apply. Naturally, in a real system, we cannot make > such > > assumptions if we want to be 100% safe. > > For instance, if the time(TCP timeout) > (syncLimit * tickTime), > ZooKeeper > > provides linearizable reads. However, if this does not hold (e..g, skewed > > clocks), then ZooKeeper might return stale data. > > To conclude, I do not think we can argue that ZooKeeper is linearizable. > > > > Cheers, > > Karolos > > > > > > On Sun, 18 Aug 2019 at 11:34, Jordan Zimmerman < > jor...@jordanzimmerman.com> > > wrote: > > > >> ZooKeeper _is_ linearizable. I’m pretty sure the ZAB paper talks about > it. > >> Aphyr does as well here: https://aphyr.com/posts/291-jepsen-zookeeper > >> > >> ==================== > >> Jordan Zimmerman > >> > >>> On Aug 18, 2019, at 1:23 PM, Karolos Antoniadis <karo...@gmail.com> > >> wrote: > >>> > >>> Hello everyone, > >>> > >>> I was wondering on the exact consistency guarantees that ZooKeeper > >> provides. > >>> It seems that ZooKeeper does not provide strong consistency (i.e., > >>> linearizability) since reads could potentially return arbitrarily old > >>> values. > >>> On the other hand, ZooKeeper provides sequential consistency, since the > >>> order of operations of a specific client is respected and all > operations > >>> appear to take place in some total order ( > >>> https://jepsen.io/consistency/models/sequential). > >>> However, ZooKeeper provides linearizable writes, and therefore it > >> provides > >>> something stronger than sequential consistency, but still not as strong > >> as > >>> linearizability. In other words, ZooKeeper guarantees are somewhere > >> between > >>> sequential consistency and linearizability. > >>> Is there a specific name for the specific consistency guarantees that > >>> ZooKeeper provides? > >>> What would the ZooKeeper community claim about the consistency > guarantees > >>> of ZooKeeper? > >>> > >>> Best Regards, > >>> Karolos > >> >
