I've always been a little confused about this framing of WSI. The observation that detecting read-write conflicts is sufficient for serializability dates back to at least Kung and Robinson in '83 (IIRC). It is true, though, and the observation that it's a minor change to an already MVCC database's commit logic is theoretically correct.
It's not really practically correct, though. Writes kinda have to be resolved to updated keys, so detecting w-w conflicts is very easy. In a SQL database, though, reads can be predicates, or aggregations, or even indicate a lack of data (gaps). This makes practically implementing this scheme on real world workloads pretty tricky, both correctness-wise and performance-wise. Clearly possible, but quickly devolves into a bunch of optimizations around edge cases. Granted, it is easier in databases that don't need full SQL semantics.
We actually started here early in the design of Aurora DSQL, but changed our minds and picked SI based on data about what isolation levels people actually choose (vs what they say they choose), the difficulty that optimizing schemas and queries for good performance under serializability presents to application programmers (you have to be very very careful to read only what you need), and the general large size of read sets compared to write sets in relational workloads. We might end up doing serializability down the line, but the demand isn't there once people see the real world tradeoffs.
Amusing aside (not about the article linked here). It's super common to see people try refute the performance cost of serializability using TPC-C. That's funny because TPC-C is serializable at SI, and never experiences write skew due to the structure of it's workload.
Relatedly, another thing I found amusing/perplexing about SSI is that they already go to the effort of dealing with read-write dependencies in order to detect "dangerous structure" patterns (e.g. Sec 5.2 of [1]), and yet end up in a scheme that is somehow more complex (conceptually) than either plain snapshot isolation or basic WSI-style serializability.
It always seemed to me that, if you were already going to have to deal with the subtleties of read-write conflict detection (e.g. predicate reads, etc.), why not just default back to the simpler WSI-style approach. It is maybe an odd historical artifact that these algorithms ended up being layered in this way.
I agree about the practical difficulties of implementing WSI. However, what’s not clear to me is how to reason about SI as an application programmer. Whenever you write data within a transaction that depends on data read within that transaction, you can’t exclude the possibility that the data you read is stale and hence that what you write will create inconsistencies. In principle, you have to read everything with SELECT FOR UPDATE in a read-write transaction. But if you do that, isn’t the performance impact similar as it would be for WSI, in that all rows that are read have to be tagged until the transaction completes?
FoundationDB used this (detection of read-write conflicts in optimistic transactions) as its default isolation level since we started building it around 2009. Doing it at the kv store level has the advantage of providing serializability even for predicate and range reads (sometimes at the cost of unnecessary conflicts, so it offers granular control of read conflict ranges also).
Good read.
I've always been a little confused about this framing of WSI. The observation that detecting read-write conflicts is sufficient for serializability dates back to at least Kung and Robinson in '83 (IIRC). It is true, though, and the observation that it's a minor change to an already MVCC database's commit logic is theoretically correct.
It's not really practically correct, though. Writes kinda have to be resolved to updated keys, so detecting w-w conflicts is very easy. In a SQL database, though, reads can be predicates, or aggregations, or even indicate a lack of data (gaps). This makes practically implementing this scheme on real world workloads pretty tricky, both correctness-wise and performance-wise. Clearly possible, but quickly devolves into a bunch of optimizations around edge cases. Granted, it is easier in databases that don't need full SQL semantics.
We actually started here early in the design of Aurora DSQL, but changed our minds and picked SI based on data about what isolation levels people actually choose (vs what they say they choose), the difficulty that optimizing schemas and queries for good performance under serializability presents to application programmers (you have to be very very careful to read only what you need), and the general large size of read sets compared to write sets in relational workloads. We might end up doing serializability down the line, but the demand isn't there once people see the real world tradeoffs.
Amusing aside (not about the article linked here). It's super common to see people try refute the performance cost of serializability using TPC-C. That's funny because TPC-C is serializable at SI, and never experiences write skew due to the structure of it's workload.
Relatedly, another thing I found amusing/perplexing about SSI is that they already go to the effort of dealing with read-write dependencies in order to detect "dangerous structure" patterns (e.g. Sec 5.2 of [1]), and yet end up in a scheme that is somehow more complex (conceptually) than either plain snapshot isolation or basic WSI-style serializability.
It always seemed to me that, if you were already going to have to deal with the subtleties of read-write conflict detection (e.g. predicate reads, etc.), why not just default back to the simpler WSI-style approach. It is maybe an odd historical artifact that these algorithms ended up being layered in this way.
[1] https://www.eecs.umich.edu/courses/cse584/archive/fall2023/s...
I agree about the practical difficulties of implementing WSI. However, what’s not clear to me is how to reason about SI as an application programmer. Whenever you write data within a transaction that depends on data read within that transaction, you can’t exclude the possibility that the data you read is stale and hence that what you write will create inconsistencies. In principle, you have to read everything with SELECT FOR UPDATE in a read-write transaction. But if you do that, isn’t the performance impact similar as it would be for WSI, in that all rows that are read have to be tagged until the transaction completes?
FoundationDB used this (detection of read-write conflicts in optimistic transactions) as its default isolation level since we started building it around 2009. Doing it at the kv store level has the advantage of providing serializability even for predicate and range reads (sometimes at the cost of unnecessary conflicts, so it offers granular control of read conflict ranges also).