3 ms·

This is really cool. Does anybody know how you implement multiversion concurrency control? I'm trying to implement it in a toy project that simulates bank acc

This is really cool. 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.

sitharus 6y ago
It really depends on your use-case. 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.
jasonwatkinspdx 6y ago
So this comes out of Andy Pavlo's group. He teaches an undergrad and graduate level database class each year, and makes nearly all of his course materials available (there's some guest lectures that don't want to be public sadly): http://www.cs.cmu.edu/~pavlo/ http://www.cs.cmu.edu/~pavlo/ 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.
apavlo 6y ago
> Does anybody know how you implement multiversion concurrency control? I have lectures available on Youtube: Intro DB Class: * https://15445.courses.cs.cmu.edu/fall2019/schedule.html#nov-04-2019 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#jan-22-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja... * Protocols: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#jan-27-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja... * Garbage Collection: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#jan-29-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja...

sitharus 6y ago

It really depends on your use-case. 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.

jasonwatkinspdx 6y ago

So this comes out of Andy Pavlo's group. He teaches an undergrad and graduate level database class each year, and makes nearly all of his course materials available (there's some guest lectures that don't want to be public sadly): http://www.cs.cmu.edu/~pavlo/ http://www.cs.cmu.edu/~pavlo/ 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.

apavlo 6y ago

> Does anybody know how you implement multiversion concurrency control? I have lectures available on Youtube: Intro DB Class: * https://15445.courses.cs.cmu.edu/fall2019/schedule.html#nov-04-2019 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#jan-22-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja... * Protocols: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#jan-27-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja... * Garbage Collection: https://15721.courses.cs.cmu.edu/spring2020/schedule.html#jan-29-2020 https://15721.courses.cs.cmu.edu/spring2020/schedule.html#ja...