+Kfir Lev-Ari <kfirlev...@gmail.com> On Sun, Aug 18, 2019 at 3:56 PM Alexander Shraer <shra...@gmail.com> wrote:
> 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 >> >> >> >
