5 ms·

" A customer issues a transaction to machine A that decrements the inventory. After this transaction completes, a different transaction is issued to machine B t

" 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.

freels 8y 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.
- mav3rick 8y 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 ?
  - freels 8y ago
    Usually 2PC is used to run transactions across multiple shard which each have a subset of the total dataset. Though it doesn't provide you with any extra reliability. There's a tradeoff in sync vs async replication... a node which you synchronously replicate to won't serve stale reads, but then it becomes part of the critical write path. Conversely when reading from a async node it's very possible to get a stale read. (Alternatively, systems like Cassandra allow you to read from multiple nodes and return the latest result). Note, I don't believe it's necessary for _all_ transactions to be strictly serializable, but I would make the argument that all read-write transactions should be in order to prevent the anomaly in the article. In other circumstances it's reasonable to make the tradeoff and accept potentially stale data.
    - bdarnell 8y ago
      > Note, I don't believe it's necessary for _all_ transactions to be strictly serializable, but I would make the argument that all read-write transactions should be in order to prevent the anomaly in the article. In other circumstances it's reasonable to make the tradeoff and accept potentially stale data. How exactly does the "free checking" example work? Is it two transactions, where each transaction is responsible for checking the total balance across all accounts? Or is it three transactions, where a third read-only transaction verifies the sum of all accounts? If it's two transactions, I think the anomaly as described is prevented even by non-strict serializability, because the additional reads force the transactions to conflict. If it's three transactions, then what we're really concerned with is the read-only transaction. What does it mean to mix some strictly-serializable transactions and non-strictly-serializable ones?
      - freels 8y ago
        It is 3 transactions. Alice deposits money into her savings acount, then subsequently withdraws money from her checking account. In the meantime, some concurrent process transactionally reads the balances of both accounts. Since there is no internal causality tying transactions 1 and 2 together, transaction 3 is allowed to arbitrarily order them without violating serializability. I think the answer to your second question comes down to what anomalies you are trying to protect against. In order to prevent causal reverse, all read-write transactions must be strictly serializable, but it is safe to reorder read-only ones.
deleted 8y ago
[deleted]

freels 8y 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.

mav3rick 8y 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 ?
- freels 8y ago
  Usually 2PC is used to run transactions across multiple shard which each have a subset of the total dataset. Though it doesn't provide you with any extra reliability. There's a tradeoff in sync vs async replication... a node which you synchronously replicate to won't serve stale reads, but then it becomes part of the critical write path. Conversely when reading from a async node it's very possible to get a stale read. (Alternatively, systems like Cassandra allow you to read from multiple nodes and return the latest result). Note, I don't believe it's necessary for _all_ transactions to be strictly serializable, but I would make the argument that all read-write transactions should be in order to prevent the anomaly in the article. In other circumstances it's reasonable to make the tradeoff and accept potentially stale data.
  - bdarnell 8y ago
    > Note, I don't believe it's necessary for _all_ transactions to be strictly serializable, but I would make the argument that all read-write transactions should be in order to prevent the anomaly in the article. In other circumstances it's reasonable to make the tradeoff and accept potentially stale data. How exactly does the "free checking" example work? Is it two transactions, where each transaction is responsible for checking the total balance across all accounts? Or is it three transactions, where a third read-only transaction verifies the sum of all accounts? If it's two transactions, I think the anomaly as described is prevented even by non-strict serializability, because the additional reads force the transactions to conflict. If it's three transactions, then what we're really concerned with is the read-only transaction. What does it mean to mix some strictly-serializable transactions and non-strictly-serializable ones?
    - freels 8y ago
      It is 3 transactions. Alice deposits money into her savings acount, then subsequently withdraws money from her checking account. In the meantime, some concurrent process transactionally reads the balances of both accounts. Since there is no internal causality tying transactions 1 and 2 together, transaction 3 is allowed to arbitrarily order them without violating serializability. I think the answer to your second question comes down to what anomalies you are trying to protect against. In order to prevent causal reverse, all read-write transactions must be strictly serializable, but it is safe to reorder read-only ones.

deleted 8y ago

[deleted]