I was reading https://cloud.google.com/blog/products/databases/strict-serializability-and-external-consistency-in-spanner and it says below "While this consistency guarantee says nothing about the order of transactions that overlap in time, it is considered “perfect” for practical purposes." Can someone please explain what this means? From whatever I read, external consistency is to ensure that if there are two transactions T1 and T2, and T2 starts after T1 has committed, T2 sees the data committed by T1 irrespective if how the data is sharded or on which replica transaction execution happened.
However, the linked article talks about an example A write(x) → B write(x) → A commit → B commit and calls is externally serializable. It looks to me that this example is talking about transactions where times overlap. In this example, B has definitely not seen the writes done by A and has overwritten A's change (I understand that using snapshots, we can retrieve value written by A which I don't think is important for current discussion).
As a programmer, do I get any advantage from external consistency where transactions times overlap or do I still have to rely on my own locking mechanisms? I understand there could be two cases here
- There is some data overlap and there is at least one common scheduler that can serialize transactions. But what order? The transaction that first acquires locks?
- In cases of causally dependent transactions that are external to database. Article talks about this case, but not when the transaction times overlap.
Some wording in that blog post is not “perfect for practical purposes”. This blog post firstly refers to Gifford’s definition of external consistency (Information Storage in a Decentralized Computer System, p. 24) and tries to reformulate it in terms of Spanner timestamps. The original Gifford’s definition says that under external consistency a) a result of any transactions execution should be equal to execution of those transactions in some serial order; b) this order corresponds to transaction completion (commit) time. Thus, formally this definition actually defines the order of transaction overlapped in time as well. E.g. in Spanner if transaction A starts before transaction B starts and commits while B is running, transaction B can see the effects of transaction A.
However, the most important thing to understand here about the word “external” is that there is a difference between a time when an external client application observes an event related to a transaction and a time when the database executes a task corresponding to that event. E.g. if a client application issues a read request to the database in one read-only transaction and then without getting result back issues a write with auto-commit in another transaction, the read request may be delivered by the underlying network infrastructure only after the write request. The same way, the responses for these requests can be delivered to the client out-of-order. Thus, the database cannot provide any external guarantees on the order of execution of in-flight requests. This gives the database service a right to do different types of transaction reordering before it actually sends the response back to the client. And some databases actively use this opportunity by batching transactions and reordering them in order to increase concurrency/throughput.
Due to it's internal nature, this Gifford's definition is hard for a client application to reason about directly, since it deals with a completion time observed by a database and not externally by client. However, it’s possible to use it to infer a guarantee that can be applicable on the client as well. It should sound very familiar: if a transaction A starts after transaction B succeeds, transaction A should be able to observe all effects of the transaction B or later transaction. This model of definition (relying on start and commit time) is more easy to reason about and was used in the original Spanner paper to define external consistency.
Another thing is that there are other definitions of external consistency and strict serializability (e.g. see here, here or here). Some of them actually diverge in some subtleties. You can also notice that external consistency and strict serializability sometimes used interchangeably. It’s hard to cover all aspects with a succinct definition. For myself, I just prefer to explain Spanner consistency/isolation guarantees using the following 4 rules:
External consistency also implies serializability. And you absolutely benefit from serializability during concurrent transaction execution, since it’s a transaction isolation level that prevents read skew and write skew (and other read phenomena, btw). Serializability ensures that the result of your transaction execution will be equivalent to some serial order. Thus the final state of your data will be like if you took a global exclusive lock at the beginning of each transaction and released it at the end. So, you may not need locks unless you need to synchronize objects outside of Spanner or have a workflow that spans multiple transactions.
As we discussed, in general, it’s not something that a database would guarantee; it will depend on implementation and transaction type. E.g, check the wound-wait deadlock prevention mechanism mentioned in the original Spanner paper.
Let me give you an example that shows how Spanner differentiates from CockroachDB – as you may know CockroachDB is not externally consistent, since it fails to provide global linearizability in some cases. This example involves concurrent execution of transactions:
So, you can see here that transaction T2 and T3 overlapped with T1. In CockroachDB it’s possible that T1 will get the following result: { K1=V0, K2=V2 }. This is a violation of the global serial order (database scope linearizability), since T2 completed before T3 and thus, if T1 sees V2 it should see V1 as well.
Spanner will not allow that. In Spanner, T1 will be allowed to only return one of the following results: { K1=V0, K2=V0} or { K1=V1, K2=V0 } or { K1=V1, K2=V2 }.