Write Snapshot Isolation (WSI) Implementation

This project aims to implement Write Snapshot Isolation (WSI) as an effort to explore and understand how databases and transaction isolation work. It is likely full of bugs! 🐞

What is Write Snapshot Isolation?

Write Snapshot Isolation (WSI) is a transaction isolation level introduced in the paper A Critique of Snapshot Isolation to achieve serializable isolation on top of Multi-Version Concurrency Control (MVCC) without using locking.

Write Skew

One of the issues with non-serializable transactions is write skew.

Consider a hospital system that requires at least one doctor to be on call at all times. Two doctors, Alice and Bob, are currently on call. Their on-call status is stored in separate database records (alice_status and bob_status). They concurrently attempt to go off duty:

Transaction 1 (Alice):

• Reads bob_status: "on call"
• Reads alice_status: "on call"
• Sees that Bob is on call, so it's safe to go off duty
• Updates alice_status to "off duty"

Transaction 2 (Bob):

• Reads alice_status: "on call"
• Reads bob_status: "on call"
• Sees that Alice is on call, so it's safe to go off duty
• Updates bob_status to "off duty"

Both transactions see a consistent snapshot showing both doctors on call, so each determines it is safe to go off duty. However, after both commit:

• alice_status is "off duty"
• bob_status is "off duty"
• No doctors are on call

The invariant that at least one doctor must be on call has been violated, even though each transaction made a valid decision based on its snapshot. This is a write skew anomaly, which Write Snapshot Isolation prevents.

This is a brief summary of write skew and the motivation behind WSI. For more comprehensive information, please refer to the resources at the bottom.

What is Missing?

• Deletion of keys through tombstones. There is currently no way to delete a key, but a simple approach could be to set the value to a specific tombstone marker. We cannot simply remove the key and all its entries because there may be transactions that began when the key still existed.
• Uncommitted transactions persist indefinitely. Perhaps they should have a timeout mechanism.
• Removing old entries. If there are old versions of values which no transaction will ever be able to read, the outdated entries can be removed to prevent unbounded data growth. This aspect was intentionally left out to focus strictly on implementing version visibility and conflict handling.
• Probably a bunch of optimizations. ⚡️

Resources

• Gómez Ferro, D., & Yabandeh, M. (2008). A Critique of Snapshot Isolation
• Kleppmann, M. (2017). Designing Data-Intensive Applications. O'Reilly Media.
• Eaton, P. (2024). Implementing MVCC and major SQL transaction isolation levels.
• Makhija, S. (2023). Serializable Snapshot Isolation.