Serializable Validation (with a Scan Limitation)

By the end of this chapter, you will be able to:

• Detect a tracked read/write dependency against transactions committed after a snapshot began.
• Serialize validation and publication under one commit lock.
• Explain why key-only scan tracking does not prevent phantom anomalies.

To copy and run the test cases:

cargo x copy-test --week 3 --day 6
cargo x scheck

Before You Begin

Day 5 provides stable snapshots and crash-atomic writes, but two transactions can still make decisions from the same old state and produce write skew. Day 6 validates a transaction immediately before commit.

This chapter does not implement the full Serializable Snapshot Isolation (SSI) algorithm from the research literature. For point reads, it uses a simpler and more conservative rule: abort when the current transaction’s read set intersects the write set of any transaction committed after its snapshot. Holding one commit lock across validation and publication lets each accepted writing transaction be serialized at its commit position; read-only transactions remain at their snapshot position. The rule may reject some histories that were already serializable. For scans, recording only returned keys misses gaps and therefore cannot provide the same guarantee.

Keep these invariants in mind:

1. Validation and write publication happen under commit_lock, so no transaction can commit between the check and the write.
2. For a transaction at read_ts, compare its read set with the write sets committed after read_ts and before its own publication.
3. Record a point-read key even when get returns None; the absence influenced the transaction.
4. A failed validation publishes no data and no committed write-set record.
5. Transactions with an empty write set skip conflict validation; optimizing their timestamp and metadata path is a bonus task.
6. Recording only keys returned by a scan does not record gaps, so inserts into those gaps can create phantoms.

Predict before coding: Two transactions begin at timestamp 10. T1 reads b and writes a; T2 reads a and writes b. T1 commits at 11. Which set intersection must abort T2? How would the answer change if T2’s dependency came only from an empty range scan?

Let us go through an example of serializable. Consider that we have two transactions in the engine that:

txn1: put("key1", get("key2"))
txn2: put("key2", get("key1"))

The initial state of the database is key1=1, key2=2. Serializable means that the outcome of the execution has the same result of executing the transactions one by one in serial in some order. If we execute txn1 then txn2, we will get key1=2, key2=2. If we execute txn2 then txn1, we will get key1=1, key2=1.

However, with our current implementation, if the execution of these two transactions overlaps:

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit
txn2: put key2=1, commit

We will get key1=2, key2=1. This cannot be produced with a serial execution of these two transactions. This phenomenon is called write skew.

With serializable validation, we can ensure the modifications to the database corresponds to a serial execution order, and therefore, users may run some critical workloads over the system that requires serializable execution. For example, if a user runs bank transfer workloads on Mini-LSM, they would expect the sum of money at any point of time is the same. We cannot guarantee this invariant without serializable checks.

One technique of serializable validation is to record read set and write set of each transaction in the system. We do the validation before committing a transaction (optimistic concurrency control). If the read set of the transaction overlaps with any transaction committed after its read timestamp, then we fail the validation, and abort the transaction.

Back to the above example, if we have txn1 and txn2 both started at timestamp = 1.

txn1: get key2 <- 2
txn2: get key1 <- 1
txn1: put key1=2, commit ts = 2
txn2: put key2=1, start serializable verification

When we validate txn2, we will go through all transactions started before the expected commit timestamp of itself and after its read timestamp (in this case, 1 < ts < 3). The only transaction satisfying the criteria is txn1. The write set of txn1 is key1, and the read set of txn2 is key1. As they overlap, we should abort txn2.

Task 1: Track Read Set in Get and Write Set

In this task, you will need to modify:

src/mvcc/txn.rs
src/mvcc.rs

When get is called, you should add the key to the read set of the transaction. In our implementation, we store the hashes of the keys, so as to reduce memory usage and make probing the read set faster, though this might cause false positives when two keys have the same hash. You can use farmhash::hash32 to generate the hash for a key. Note that even if get returns a key is not found, this key should still be tracked in the read set.

In LsmMvccInner::new_txn, you should create an empty read/write set for the transaction if serializable=true.

Task 2: Track Read Set in Scan

In this task, you will need to modify:

src/mvcc/txn.rs

In this course, we only guarantee full serializability for get requests. You still need to track the read set for scans, but in some specific cases, you might still get non-serializable result.

To understand why this is hard, let us go through the following example.

txn1: put("key1", len(scan(..)))
txn2: put("key2", len(scan(..)))

If the database starts with an initial state of a=1,b=2, we should get either a=1,b=2,key1=2,key2=3 or a=1,b=2,key1=3,key2=2. However, if the transaction execution is as follows:

txn1: len(scan(..)) = 2
txn2: len(scan(..)) = 2
txn1: put key1 = 2, commit, read set = {a, b}, write set = {key1}
txn2: put key2 = 2, commit, read set = {a, b}, write set = {key2}

This passes our serializable validation and does not correspond to any serial order of execution! Therefore, a fully-working serializable validation will need to track key ranges, and using key hashes can accelerate the serializable check if only get is called. Please refer to the bonus tasks on how you can implement serializable checks correctly.

Task 3: Engine Interface and Serializable Validation

In this task, you will need to modify:

src/mvcc/txn.rs
src/lsm_storage.rs

Implement validation in the commit phase. Hold commit_lock across validation, timestamp allocation, write publication, and insertion into committed_txns.

You will need to go through all transactions with commit timestamp within range (read_ts, expected_commit_ts) (both excluded bounds), and see if the read set of the current transaction overlaps with the write set of any transaction satisfying the criteria. If we can commit the transaction, submit a write batch, and insert the write set of this transaction into self.inner.mvcc().committed_txns, where the key is the commit timestamp.

Skip validation if write_set is empty. If the transaction’s write batch is empty, return successfully without allocating a commit timestamp or retaining committed-transaction metadata.

You should also modify the put, delete, and write_batch interface in LsmStorageInner. We recommend you define a helper function write_batch_inner that processes a write batch. If options.serializable = true, put, delete, and the user-facing write_batch should create a transaction instead of directly creating a write batch. Your write batch helper function should also return a u64 commit timestamp so that Transaction::Commit can correctly store the committed transaction data into the MVCC structure.

Task 4: Garbage Collection

In this task, you will need to modify:

src/mvcc/txn.rs

After a successful write transaction commits, remove committed transaction records strictly below the watermark; no future transaction can have an older active read_ts.

Chapter Checkpoint

Point-read dependencies should now produce an execution equivalent to commit order, while the documented scan-phantom limitation remains visible.

Verify these cases explicitly:

1. Reproduce write skew and confirm exactly one of the overlapping transactions aborts.
2. Read a missing key, let another transaction insert it, then attempt to commit a dependent write from the first transaction.
3. Confirm that disjoint read and write sets both commit, and that two blind writes to the same key can serialize by commit order.
4. Run the scan-phantom example and explain why returned-key hashes cannot represent the missing predicate.
5. Keep the oldest transaction alive and confirm committed write-set metadata is retained until its watermark advances.

Test Your Understanding

• If you have some experience with building a relational database, you may think about the following question: assume that we build a database based on Mini-LSM where we store each row in the relation table as a key-value pair (key: primary key, value: serialized row) and enable serializable verification, does the database system directly gain ANSI serializable isolation level capability? Why or why not?
• The point-key rule is related to write snapshot isolation (see A critique of snapshot isolation): it aborts on any relevant read-after-snapshot write conflict instead of detecting only cycles. Construct a serializable execution that this conservative rule still rejects.
• There are databases that claim they have serializable snapshot isolation support by only tracking the keys accessed in gets and scans (instead of key range). Do they really prevent write skews caused by phantoms? (Okay… Actually, I’m talking about BadgerDB.)
• Why must commit_lock cover both validation and publication? Construct an interleaving that fails if the lock is released between them.
• Why does a get miss belong in the read set?
• Why can two transactions that only write the same key both commit without violating serializability?
• Which committed transaction records are safe to garbage-collect at a given watermark?

Use the Week 3 end-of-week self-check to calibrate the core invariants. The remaining design questions may have several defensible answers; state your workload and assumptions before comparing tradeoffs. You can also discuss them in the Discord community.

Bonus Tasks

• Read-Only Fast Path. Detect an empty transaction before acquiring commit_lock. The required implementation already avoids allocating a commit timestamp or retaining an empty validation record, but it may still serialize briefly with writers before discovering that the batch is empty.
• Precision/Predicate Locking. The read set can be maintained using a range instead of a single key. This would be useful when a user scans the full key space. This will also enable serializable verification for scan.

Your feedback is greatly appreciated. Welcome to join our Discord Community.
Found an issue? Create an issue / pull request on github.com/skyzh/mini-lsm.
mini-lsm-book © 2022-2026 by Alex Chi Z is licensed under CC BY-NC-SA 4.0.