13
$\begingroup$

In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:

One subtle thing about Spanner is that it gets serializability from locks, but it gets external consistency (similar to linearizability) from TrueTime [emphasis added].

What is the definition of external consistency, and how does it differ from linearizability?

$\endgroup$
1
  • $\begingroup$ This is a great question, and I wish Eric would have elaborated a bit here. Is it linearizable or not? :) $\endgroup$
    – BMiner
    Jul 16 '20 at 2:43
12
$\begingroup$

External consistency doesn't have a fixed meaning. In this context, it has the meaning appearing in the very next sentence in the document:

For any two transactions, $T_1$ and $T_2$ (even if on opposite sides of the globe): if $T_2$ starts to commit after $T_1$ finishes committing, then the timestamp for $T_2$ is greater than the timestamp for $T_1$.

$\endgroup$
3
  • $\begingroup$ The more I think about it, this sounds a whole awful lot like linearizability to me because all transactions are ordered. Sadly, sometimes these terms are subtle... Anyone disagree? I mean, the transactions are serializable, and they are totally ordered based on commit time. Perhaps the subtlety lies in how 2PC is implemented in Spanner? $\endgroup$
    – BMiner
    Jul 16 '20 at 2:39
  • $\begingroup$ @Bminer Linearizability is a consistency models that only applies to single objects, where transactions can involve multiple objects. $\endgroup$ Jul 16 '20 at 3:32
  • 2
    $\begingroup$ @LorinHochstein - Ha! That smells like mincing words. The whole point of the terminology is to help real people conceptualize what guarantees they get, especially with regard to transactions. Linearizability + serializability is the strongest guarantee, and I think that's what the Spanner docs are referring to with the term "external consistency." But, it begs the question: does anyone really know what "external consistency" means? :) $\endgroup$
    – BMiner
    Oct 12 '20 at 14:10
2
$\begingroup$

There is a distinction between external consistency and strict serializability. I wrote a comment on it here https://stackoverflow.com/questions/60365103/differences-between-strict-serializable-and-external-consistency/65853495#65853495.

The difference is that strict serializability imposes no order on concurrent transactions, whereas external consistency does (the order in which they commit).

$\endgroup$
1
$\begingroup$

You can think about external consistency from transactions (Tx) isolation and order point of view. In Tx isolation speak the external consistency is equivalent to the strict serializable isolation, where 'strict' is the real-time constraint part (as in linearizability).

That again all means that to a system client observable Tx side effects are equivalent to a system, where all Tx take place in isolation without any concurrency and where their real-time ordering, as seen by the client, is preserved. More importantly this same ordering is seen by any other unrelated client.

Read more about the distinction at this blog.

$\endgroup$
0
$\begingroup$

When mentioning "external consistency", Brewer references B. Liskov. Practical Uses of Synchronized Clocks in Distributed Systems. ACM Principles of Distributed Computing (PODC). Montreal, Canada, August 1991.

Liskov, in term, references Gifford D.K. Information Storage in a Decentralized Computer System. Technical Report CSL-81-8, Xerox Corporation, March, 1983

Here's how Gifford defines external consistency:

External consistency guarantees that a transaction will always receive current information. Using the concepts we have just introduced, we can provide a formal definition of external consistency. The actual time order in which transactions complete defines a unique serial schedule. This serial schedule is called the external schedule. A system is said to provide external consistency if it guarantees that the schedule it will use to process a set of transactions is equivalent to its external schedule.

As @Oleg mentions, this sounds like strict serializability.

$\endgroup$
1
  • $\begingroup$ Is it just me or does that definition of external consistency make very little sense? It's saying "A system is said to provide external consistency if it guarantees that the schedule it will use to process a set of transactions is equivalent to the actual time order in which transactions complete." $\endgroup$ Aug 8 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.