Serializability vs. Strict Serializability: The Dirty Secret of Isolation Levels

https://fauna.com/blog/serializability-vs-strict-serializability-the-dirty-secret-of-database-isolation-levels

by evanweaver • 7 years ago

87 33 7 years ago

DelightOne3• 7 years ago

Does Postgresql offer strict serializability?

With synchronous replication it should, since it waits till all replicas are in the same state(as far as I know), which makes it strict?

freels5• 7 years ago

Yes, I believe so. Since in Postgres, snapshot isolation (on top of which its serializable implementation is built) provides a stable view of the system at a point in time, and also doesn't allow stale reads, transactions _can be_ strictly serializable.

However, if multiple synchronous standby replicas are configured, then this means that stale reads are possible, since Postgres by default does not necessarily wait for all replicas to ack the write. It depends on the replication configuration and where reads are directed.

DelightOne3• 7 years ago

However, if multiple synchronous standby replicas are configured, then this means that stale reads are possible, since Postgres by default does not necessarily wait for all replicas to ack the write. It depends on the replication configuration and where reads are directed.

It seems synchronous replication still refers to durability of a commit. Once it‘s stored on the replica persistently it doesn‘t block anymore, so no strict serializability. Macdice‘s comment and the link hold lots of info on this.

joevandyk• 7 years ago

What about mysql?

evanweaver• 7 years ago

MySQL’s default repeatable-read is a complex mix, but it is definitely not strictly serializable: https://blog.pythian.com/understanding-mysql-isolation-level...

It’s very unclear what level of serializability MySQL’s “serializable” level actually provides; it is seldom used in practice because the performance cost is extreme (essentially table locks everywhere for both reads and writes).

I would be surprised if either isolation level is correctly enforced across distributed replicas, even with semi-synchronous row-based replication. My MySQL operational experience was strongly characterized by fighting replication divergence.

zAy0LfpBZLC8mAC• 7 years ago

On a single machine, it most likely does (it wouldn't really make sense to implement something else), but across replicas it doesn't even offer non-strict serializability as SIREAD locks are not coordinated between replicas.

macdice2• 7 years ago

Edit: TL;DR: No, not with replication in the picture.

As for whether replication shows fresh data, it sort of can, but not in a very practical way. synchronous_commit = on, when synchronous_standbys has been configured, does indeed make COMMIT wait until some number of standbys has flusheùd the transaction to disk, but not until the transaction is visible to new transactions/snapshots on the replicas. In other words, it's just about making sure your transaction is durably stored on N servers before you tell your client about the transaction; a new transaction on the replica server after that might still not see the transaction (if the startup process hasn't got around to applying it yet). As a small step towards what you want, we added synchronous_commit = remote_apply, which makes COMMIT wait until the configured number of standbys has also applied the WAL for that transaction, so then it will be visible to new transactions. The trouble is, you either have to configure it in such a way that a dying/unreachable replica can stop all transactions on the primary (blocking the whole system), or so that it only needs some subset of replicas to apply, but then read queries don't know which replicas have fresh data.

I have a proposal to improve that situation: https://commitfest.postgresql.org/22/1589/ Feel free to test it and provide feedback; it's touch and go whether it might still make it into PostgreSQL 12. It's based on a system of read leases, so that replicas only have a limited ability to hold up future write transactions, before they get kicked out of the synchronous replica set, a bit like the way failing disks get kicked out of RAID arrays. Most of the patch is concerned with edge conditions around the transitions (new replicas joining, leases being revoked). The ideas are directly from another open source RDBMS called Comdb2. In a much more general sense, read leases can be found in systems like Spanner, but this is just a Fisher-Price version since it's not multi-master.

As for whether that gets you strict serializability, well no, because PostgreSQL doesn't even support SERIALIZABLE on read-only replicas yet, and although REPEATABLE READ (which for PostgreSQL means snapshot isolation) gets you close, anomalies are possible even with read-only transactions (see famous paper by A Fekete, search for that name in the PostgreSQL isolation tests, for an example). Some early work has been done to try to get SERIALIZABLE (actually SERIALIZABLE READ ONLY DEFERRABLE) working on read-only replicas. https://commitfest.postgresql.org/22/1799/ but some subproblems remain unsolved.

Maybe with all of that work we'll get close to the place you want. It's complicated, and we aren't even talking about multi-master.

DelightOne3• 7 years ago

doesn't even support SERIALIZABLE on read-only replicas yet

What are the anomalies here? Could a replica diverge or succeed where master failed or sth? I never asked these questions before.

It‘s complicated, and we aren‘t even talking about multi-master.

Hah, a dream. Very interesting read, thank you!

benmmurphy2• 7 years ago

You can reproduce the problem in postgresql with the following:

    create table counters(counter int);

    insert into counters(counter) values(1);

    BEGIN TRANSACTION ISOLATION LEVEL serializable; 
    select sum(counter) from counters; /* this will return 1 */
    /* insert sum into counters. wait until committing next transaction before executing the insert */
    insert into counters(counter) values(1);
    COMMIT;

    /* this transaction should commit before doing the insert in the above transaction and after the above transaction has calculated the sum */
    BEGIN TRANSACTION ISOLATION LEVEL serializable; 
    insert into counters(counter) values(10);
    COMMIT;

both transactions commit and the final table looks like: 1, 10, 1

which is possible if the first transaction committed first, and then the second transaction committed which is different from the order the transactions committed in by the wall clock. so it is possible for another client to see the table as:

    [1] (the initial state)
    [1, 10] (after the second transaction committed)
    [1, 1, 10] (after the first transaction committed)

which is a sequence of states which should not be possible. if you see [1], [1, 10] then you should see [1, 10, 11] as the last state. hence it violates external consistency.

karmakaze2• 7 years ago

The query results [1, 1, 10] and [1, 10, 1] are equivalent and any perception of difference irrelevant.

mav3rick3• 7 years ago

" A customer issues a transaction to machine A that decrements the inventory. After this transaction completes, a different transaction is issued to machine B that reads the current inventory. On a single machine, the second transaction would certainly read the write of the first transaction. But now that they are running on separate machines, if the system does not guarantee consistent reads across machines, it is very much possible that the second transaction would return a stale value (e.g. this could happen if replication was asynchronous and the write from the first transaction has not yet been replicated from A to B). This stale read would not be a violation of serializability. It is equivalent to a serial order of the second transaction prior to the first. But since the second transaction was submitted after the first one completed, it is certainly a violation of strict serializability."

Isn't this a problem on all DBs that don't have strict serializability and can't it be solved by 2 Phase Commit ? In the vote phase, the coordinator can also get the final balance from each replica, in that case if any balance differes it knows one of the replica isn't synced and aborts the transaction (user retries).

Another idea maybe (doesn't scale) -

Mark replicas as read only and the writes only go through one or a set of master nodes which guarantee that the state is up to date ?

Would love for an expert to chime in.

freels5• 7 years ago

Yes, it potentially is, but it entirely depends on the implementation details of the system. It's certainly allowed behavior by the definition of serializability.

mav3rick3• 7 years ago

Edited my comment to include 2 Phase Commits. Wouldn't 2PC always get you synchronous replication ? Async Replication probably helps you scale but the tradeoff is consistency and errors like the one they mentioned. Is that correct ?

foobiekr• 7 years ago

I really enjoy the Faunadb blogs and technical writeups. They hit the right level of depth and readability, so kudos to the author.

northstar702• 7 years ago

Thanks, we appreciate the shoutout.

karmakaze2• 7 years ago

I'd always known this as wall-clock serializability. Not a technical sounding term but very descriptive.

I'm not sure I know of any traditional RDBMSes that run in Serializable but not Strict Serializable mode. It's only the horizontally distributed ones that squeeze more performance that seem to choose the trade-off for performance. CockroachDB (-is-)was the notable one that used SNAPSHOT isolation permitting write skew. "As of CockroachDB 2.1, SNAPSHOT isolation is no longer supported, and SERIALIZABLE SNAPSHOT is now simply known as SERIALIZABLE." Good to know.

daxfohl2• 7 years ago

Same as linearizability?

grogers• 7 years ago

Linearizability is a property of accesses of a single key. Strict serializability is the analogous property for accesses on a multi-key system. Basically, strict serializability implies linearizability, but not the other way around.

A database with just serializable operations but with single key operations being linearizable is still useful. You could imagine this being implemented as a partitioned database with operations in a single partition being strictly serializable, but without a global clock to preserve real time ordering of transactions on different partitions.

daxfohl2• 7 years ago

What do you mean by "key" here? In my world a "key" is a half of a key-value-pair, and would correspond to only one record. But then you talk about strict serializability of entire partitions and that seems like something different.

slaymaker19072• 7 years ago

Their banking example is impossible under any system which guarantees serializability.

To guarantee serializability, the database system cannot assume anything about how some value is derived (unless it is something like a single stored procedure).

If I am playing the evil demon to show why their example is not valid under serializability, let us make a small modification to their example. Instead of just paying the babysitter, assume that our customer simply execute the following procedure twice as two separate transactions.

  begin transaction;
  money = select money from bank where id=42;
  if money % 2 == 0:
    update bank set money=money-1 where id=42;
  else:
    update bank set money=money+2 where id=42;
  commit;

If money = 10 initially, there is precisely one valid end state for money, money = 11. However, using the logic from the article, it is supposedly valid for the second execution to read the old value for money. Therefore, both transactions end up writing money=9 which is clearly not possible under serializability, strict or not!

The key part of this is that the database has no idea what logic we are using to compute the new value of money.

The only time I could see strict serializability potentially being stronger than normal serializability is with cases where the client is executing a stored procedure and therefore the database can know exactly what logic the client is running.

ascar• 7 years ago

Their banking example is impossible under any system which guarantees serializability. > To guarantee serializability, the database system cannot assume anything about how some value is derived

Their example is very well possible with a system that just guarantees serializability. Especially if it's distributed. The database is not assuming anything in their example, but you are changing the database design and assume it's in a way serializability works. Serializability works in many scenarios, especially on single machine databases, that's why it was usually sufficient (they even mention exactly that). So it's very easy to come up with an example for serializability working. Actually your example is equivalent to their first example (with inventory), where they point out how serializability works.

But the data in their second example is not in a single value "money", but it's disjoint values "savings_balance" and "checkings_balance". Reads/writes to these are from a database point of view non-conflicting operations, so they might be reordered. The article explains the transactions access disjoint data (checking balance vs savings balance) if the disjoint data are located on different machines in a distributed system.

So the two transactions T1 (add money to saving) and T2 (remove money from checkings), may be executed T1 -> T2 and T2 -> T1, because they are non-conflicting reads/writes. In the T2 -> T1 case of their example, the balance dropped below $5000 dollar, because the addition came later.

tirumaraiselvan2• 7 years ago

Except in that case, the user already received confirmation that T1 was success before T2 was even executed. So not sure how that is even possible.

moring• 7 years ago

Doesn't strict serializability solve only part of the problem? If X finishes before Y starts, then X must come before Y in serial order. But if there is some overlap between X and Y in the first place, then again some serial order is picked (serializability already guarantees that), but strict serializability still does not define which of the two possible orders gets picked. So at least query-level replication would suffer from the same problems as before.

Serializability vs. Strict Serializability: The Dirty Secret of Isolation Levels

Related Stories