Why is Snapshot Isolation not enough?

I always liked Jim Gray's marbles example to demonstrate the problem with snapshot isolation, so much easy to understand:

https://techcommunity.microsoft.com/t5/sql-server-blog/seria...

The problem with all of these examples is that it’s using a model of Snapshot Isolation which guarantees writes don’t conflict, but doesn’t provide a similar guarantee for reads. What you really want is the pair of constraints:

- Anything I write hasn’t been concurrently written to by another transaction

- (added): Anything I read also hasn’t been concurrently written to by another transaction

Adding “conflicting reads” fixes every single example in this post. The linked list example can be fixed in any number of ways. The most efficient might be to “spread out” the set of conflicting keys to also include the next / prev pointers of the deleted items b and c. This makes the transactions conflict. Or maybe better - include all the next pointers of all items before the modified item. This adds an implicit guarantee that the visited / modified item must be in the list for the transaction to be successfully committed.

Now, adding reads to the conflict set might change SI into a different concurrency model. The blog post does use the same definition as Wikipedia. And that definition only mentions writes. But I think any SI system can be made to work this way by setting X = X for any value read during each transaction.

The “two threads” example becomes this:

    beginTxn();
      if (x == 0 && y == 0) x = 1;
      x = x; y = y; // implicit
    endTxn();
 
    beginTxn();
      if (x == 0 && y == 0) y = 1;
      x = x; y = y;
    endTxn();

And the two transactions will function correctly.

Having the database handle this for you is best because:

- Humans will forget

- If two transactions read some value but neither transaction writes to it, the two transactions don’t actually need to conflict. This is too strict.

Foundationdb in my opinion has the best API for this I’ve seen. Reads and writes within a transaction are tracked like this automatically, and you can manually add, remove or change the set of conflicting keys using an explicit api if you want to. But I’m sure it’s not alone.

There's a typo, clearly the second transaction is removing C and not D as stated.

> The first transaction modifies fields in records A and C, while the second transaction modifies fields in records B and D.

> Under Snapshot Isolation both transactions will commit, which means that the doubly linked list will be left in an inconsistent state

That's not how the DB we use works[1]. Both transactions will run, but as soon as either touches a row the other has already modified it will raise an "Update conflict on snapshot transaction" error. If the first transaction races the second, the second will be blocked on the row's write lock until the first is committed, and then raise the same error.

And yes, I verified this just now, and I verified the connections are running snapshot isolation.

So does SQLAnywhere not implement the standard way?

[1]: https://infocenter.sybase.com/help/index.jsp?topic=/com.syba... (old version but hasn't changed)

I really like to work with snapshot isolation and rarely have any problems with it, but you do have to be aware what guarantees it gives and does not give.

In the example given in the article, there would not be a problem if the links on the removed node would be reset (which is cleaner imho) as then an update conflict would be triggered.

When using snapshot isolation, I sometimes implement ‘dummy’ updates (using a version field for example) on ‘root’ objects to trigger update conflicts when concurrent updates must be prevented to data linked to that same ‘root’ object. (This is similar to implementing optimistic locking using a version field on a root object.)

Related: "A Critique of Snapshot Isolation" - https://news.ycombinator.com/item?id=40516582

It’s the ABA problem that also comes up with normal multithreading when trying to go lock free. Lock free data structures are hard. SI is giving you the same guarantees (your update is atomic, but things might have changed between when you read and when you write). If you can handle this extra complexity, all good, but it’s generally something that needs to be carefully abstracted. Nobody wants to be thinking this hard every time they have to interact with a DB.

This is so well explained. Cockroachdb implements serializable by default and it is a great experience being able to write sql with that in mind.

Amazon Redshift very recently has made this the default choice.

It’s enough, just make sure you’re not trying to fly an airplane or prevent the detonation of nuclear weapons using a database, it’s the wrong tool for the job.

If you’re storing doubly linked lists in a DB you’re doing it wrong.

Updating doubly linked lists can be done at about 200 million ops/sec, single threaded, not sure why you need multiple threads updating the list at the same time, exactly what are you doing that can't be solved by putting a ring buffer in front of a single thread that updates the values, doesn't need locks and is cache coherent.