zookeeper-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Alexander Shraer <shra...@gmail.com>
Subject Re: Consistency Guarantees
Date Sun, 18 Aug 2019 22:56:15 GMT
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 <
jordan@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 <karolos@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 <
> jordan@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 <karolos@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
> >>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message