Does anybody know how you implement multiversion concurrency control?
I'm trying to implement it in a toy project that simulates bank accounts withdrawing and depositing money in a multithreaded scenario where no money should be lost or created.
I found that the algorithm only worked when I considered only write timestamps. If there is a write timestamp that is greater than this commit's write timestamp, then abort and retry.
I have lectures available on Youtube:
Intro DB Class:
* https://15445.courses.cs.cmu.edu/fall2019/schedule.html#nov-...
Advanced DB Class (with reading list):
* Design Decisions: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja...
* Protocols: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja...
* Garbage Collection: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja...
I'd definitely go through the slide decks on concurrency control in both of these classes. They're an amazing resource for anyone interested in database internals. There's a ton of tradeoffs, and a lot of prior research into them. Andy's slide decks are something of a road map to the different choices.
What you describe is roughly snapshot isolation, which mostly works, but is vulnerable to write skew.
A very brief summary for the case of Postgres: every tuple has a pair of hidden columns `min_xid` and `max_xid`. Every transaction get assigned an `xid` that's always increasing (it wraps around on int_max, that's a problem for later), and it can only see rows where `xid > min_xid and (max_xid is null or xid <= max_xid)`.
On writes the database is checked for rows with a matching PK where min_xid > xid, if any are found an error is raised.
The reality is a lot more complex than this and involves some locks during transaction commits and the vacuum process to clean up dead rows and handle xid wrap-around, but that's the basic idea.