Differences between Strict Serializable and External Consistency

Question

I follow this great blog. In this blog, the author has drawn a complete picture of all types of isolation and consistency and the relationship between them.

But based on the Google's blog, there is another type of consistency named External Consistency which is provided by Google's Spanner database. As I understood:

External consistency = Strongly Consistency + Strict Serializable

After some research, the definition of external consistency might be:

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

I still don't see the differences between External consistency and Strict Serializability. Please give me an example that it satisfies Strict Serializability but not External Consistency.

Thanks

Gunner

Answer 1

Serializability requires that transactions appear to occur sequentially. Serializability does not require any particular ordering on the serial schedule to which the transaction executions be equivalent to.

Strict serializability requires serializability, but also imposes a condition on the order of the serial schedule to which the transaction execution is equivalent to: a transaction that commits before a different transaction starts must appear to happen first. Suppose A commits before B starts--A must appear to take effect before B. With a single node system this comes for free with serializability, and no one really discusses it in this context. In a distributed system it's very hard. See https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf.

External consistency is a little different. External consistency requires that a transaction that commits before a different transaction commits must appear to happen first. Suppose A commits before B commits--A must appear to take effect first. See here for a definition of external consistency.

The subtle distinction here is that strict serializability imposes no order on concurrent transactions, whereas external consistency imposes a total order on all transactions. External consistency is therefore a stronger condition in the sense that any externally consistent system is also strictly serializable.

Broome

From the original paper of In David Gifford in 1981, it says: "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." It sounds like the seiral schedule in external consistency respects the time "transactions complete". But from the paper "Spanner, TrueTime & The CAP" by Eric Brewer says the schedule order is "T2 starts after T1 commits" – Gautama

I guess David accidentally used the word "complete" which might be inaccurate or mis-understanding. From other papers related to Spanner who claims to be external consistent, the order means: T2 starts after T1 finishes commit. And there is no order for overlapped parallel transactions, you can re-order parallel transactions anyway you want, if only all processes see the same global order. – Gautama

So, I think strict serializability is external consistency. – Gautama

The paper "Spanner, TrueTime & The CAP" references Liskov's paper dl.acm.org/doi/pdf/10.1145/112600.112601 which references Gifford's paper. I agree the spanner paper's definition of external consinstency contradicts Gifford's definition. But I think Spanner should in fact provide guarantees on the serial schedule consistent with Gifford's definition. – Broome

I can't find any definition of External Consistency that comes before Gifford's definition. I also think it's confusing to have two synonymous phrases. So I prefer the interpretation that I gave (rather than interpreting Gifford's paper as having an error). – Broome

I found this blog helps me a lot. bailis.org/blog/linearizability-versus-serializability – Haemolysis

Answer 2

You are right, strict serializability and external consistency are pretty much the same. As far as I understand, the one guarantee with external consistency that is not obvious from strict serializability is that a strong snapshot read will follow strict serializability and will observe all previously committed transactions, even though it does not take a lock.

Technicality

Answer 3

Strict serializability says that transaction behavior is equivalent to some serial execution, and the serial order of transactions corresponds to real time (i.e. a transaction started after another one finished will be ordered after it). Note that strict serializability (like linearizability) still doesn’t say anything about the relative ordering of concurrent transactions (but, of course, those transaction still need to appear to be “isolated” from each other).

For my understanding, Google's Spanner uses the term external consistency instead of strict serializability because it emphasizes the difference between a system that provides consistency for transactions known to the database to be causally related and systems that don’t try to infer causality and offer stronger guarantees.

Roger

Answer 4

I would actually venture to say strict serializability is not very particular in what kind of real-time ordering it demands, as long as there is some real-time (partial) order [warn: needs citation]. Most databases will give you strict serializability with a rather simple notion of real-time ordering which is if A commits before B starts, then A appears before B in the serial order. Erm...doh but regular serializability doesn't even enforce this.

Now if you see the spanner docs, it has a stronger definition of real-time order: if one transaction completes before another transaction starts to commit i.e if A commits before B commits, then A will appear before B in the serial order. This they call "external consistency".

TLDR: Strict serializability is different from external consistency in the way it is commonly defined by database vendors. Spanner has a stronger serializability in this sense.

Articular

Answer 5

I'm an engineer who works at Google on Spanner. From serializability theory, a concurrent execution of a set of transactions is considered serializable if it is equivalent to some serial execution of the same set of transactions. It also introduces some additional desirable properties that are more restrictive:

• Recoverable (RC). A concurrent execution of transactions is recoverable if whenever a transaction B reads x written by transaction A, A commits before B.
• Avoids Cascading Aborts (ACA). A concurrent execution of transactions avoids cascading aborts if whenever a transaction B reads x written by transaction A, A commits before B reads x.
• Strict (ST). A concurrent execution of transactions is strict if whenever a transaction B reads or writes x written by transaction A, A commits or aborts before B reads or writes x.

Given a set of transactions, each of the above scheduler properties defines a subset of all possible transaction operation interleavings and are increasingly restrictive (i.e. ST ⊂ ACA ⊂ RC). For a complete treatment of serializability theory, see chapter two of the freely downloadable textbook Concurrency Control and Recovery in Database Systems by P.A. Bertnstein et al.

External consistency is a term somewhat synonymous with strict serializability that was introduced to describe a similar property as it relates to the more challenging case of a decentralized storage system. It emphasizes the requirement that actual (wall clock) time order in which transactions complete must match their commit order. This requirement is the fundamental challenge in a decentralized database system that does distributed transaciton processing, which is why we chose to use this term for Spanner. In terms of serializabilty theory, externally consistent transactions are both "serializable" and "recoverable" but don't necessarily uphold the "avoids cascading aborts" and "strict" properties. Though the definition doesn’t include these additional properties, if a database system doesn’t allow reading or overwriting uncommitted data and provides external consistency, it will automatically guarantee strict serializability. For the formal definition of external consistency, see page 35 of Information Storage in a Decentralized Computer System by David K. Gifford.

For a more detailed explanation of these terms as they relate to Spanner, see Spanner under the hood: Understanding strict serializability and external consistency.

Encephalography