Building SaarDB, Part 4: Transactions

Problem: Multiple Writes Need to Be Atomic

Consider a bank transfer: move $100 from account A to account B.

• PUT account_A 400 (was 500, debit 100)
• PUT account_B 600 (was 500, credit 100)

Now imagine the process crashes between these two writes. The first PUT succeeds, account A has $400. The second PUT never happens, account B still has $500. $100 has vanished. The system is in an inconsistent state.

In our current system, each PUT is independent. There is no way to say: "these two writes must both succeed or both fail." This is the atomicity problem. We need a way to group multiple writes into a single logical operation, a transaction that either commits entirely or has no effect at all.

Problem: Concurrent Users Can Mess Each Other Up

Atomicity is not the only issue. When multiple transactions run concurrently, they can interfere with each other in subtle ways. This is the isolation problem. Let us walk through three concrete scenarios.

Scenario 1: Dirty (Uncommitted) Read

T2 read a value that T1 wrote but then rolled back. T2 is now making decisions based on data that was never committed. From the database's perspective it is data that never existed. Hence, a transaction should only be reading committed values.

Scenario 2: Lost Update

Let's say we solve for dirty reads by only reading committed values. In that case, we run into other issues. Let's say T1 adds $20. T2 adds $30. The correct final balance should be $100 (50 + 20 + 30). But the actual result is $80. T1's update is silently overwritten by T2 (hence the name lost update) because T2 read the old value before T1's write was visible.

Scenario 3: Write Skew

A more subtle problem. Suppose we have two variables with a constraint: x + y >= 0. Initial state: x = 5, y = 5.

Result: x = -5, y = -5, x + y = -10 (VIOLATES constraint!)

Each transaction individually validated the constraint. But their combined effect violates it. Neither transaction saw the other's write because they both read before either wrote. This is write skew. Each transaction makes a decision based on a snapshot that becomes stale by the time it commits.

Lost update and write skew look similar but the distinction matters: in a lost update, two transactions race on the same key. In write skew, no single key is contested, T1 writes x, T2 writes y, but their combined effect violates a constraint that spans both keys.

What Isolation Levels Exist?

To solve these isolation problems (or anomalies), SQL databases define four isolation levels. Each level prevents more anomalies than the one before it. But with increasing isolation level, the concurrency and hence the overall throughput can drop. This is because, in order to solve for these isolation anomalies, we can require acquiring more locks.

In this blog, we will focus on Serializable, the strongest isolation level. The result of concurrent transactions is equivalent to some serial (one-at-a-time) execution order.

Our Approach: Two-Phase Locking (2PL)

Though there are multiple ways of implementing serializable isolation, we will focus on the simplest approach for the current blog called two-phase locking. Though this approach also leads to the least level of concurrency and throughput.

Before a transaction reads or writes a key, it must acquire a lock on that key. Other transactions that want to access the same key have to wait (or fail).

Let's see how locks solve the lost update problem from earlier:

T2 cannot read balance until T1 is done. No lost update.

But when should a transaction release its locks? What if T1 unlocks balance and then needs to access another key?

Result: x = -5, y = -5 (write skew!)

T1 released x before the end of the transaction and in this case immediately after GET. T2 snuck in and wrote to x before T1 was done. T1 then read y and since T1 has stale value of x = 5, the x + y >= 0 still applied. Hence, even after applying locks, we still faced the write skew problem.

The solution is to hold all locks until commit. This is the core distinction and the purpose of a transaction. Locks are held till the transaction is complete. Lock is released only when we commit or abort a transaction. If T1 never releases x until it is done with everything, T2 cannot sneak in.

This is where the Two-Phase Locking name comes from:

• Phase 1: Growing or acquiring phase (BEGIN to COMMIT): acquire locks as needed. Never release any.
• Phase 2: Shrinking or releasing phase (COMMIT or ROLLBACK): release all locks at once.

Read And Write Locks In A Transaction

We talked about the need of read and write locks in the last blog from a process or goroutine perspective. Now, we will be applying the concepts of read and write locks within a transaction as well.

GET command requires acquiring a read lock on a key while PUT command requires acquiring a write lock. Similar to what we studied in the last blog, multiple transactions can hold read locks on the same key simultaneously. But only one transaction can hold write lock on a key at a time.

Tracking Lock State

When a transaction wants to acquire a lock on a key, we need to answer: has some other transaction already acquired a lock on this key? And if so, is it a read lock or a write lock?

Tracking locks per key. While performing PUT or GET operation within a transaction, for each key, we need to know: which transactions currently hold a lock on it, and is it a read lock or a write lock? A map from key to lock state is the natural fit. And as we discussed above and in last blog, we know that a key can either have multiple readers or a single writer, never both. So the value struct needs to track both cases.

In the code snippet below, keyVsLocksAcquiredMap is the map to identify the write lock or read locks acquired by different transactions for a specific key.

keyVsLocksAcquiredMap map[string]*LocksAcquired

type LocksAcquired struct {
    readerTxnIds []uint64
    writerTxnId  uint64
}

Identifying transactions. The above struct uses transaction IDs to identify who holds what. Each transaction gets a unique ID via an auto-incrementing counter assigned at BEGIN.

type Transaction struct {
    id uint64
}

Efficiently releasing locks. When a transaction commits or rolls back, we need to release all its locks. If we only had keyVsLocksAcquiredMap, we would have to scan the entire map to find which keys this transaction locked. That is O(total keys in the system). Hence apart from a shared global keyVsLocksAcquiredMap, each transaction maintains its own list of locked keys. This list would be part of the Transaction struct.

lockAcquiredKeys []string

type Transaction struct {
    id               uint64
    lockAcquiredKeys []string
}

At release time, we iterate over this list and do O(1) lookups in keyVsLocksAcquiredMap to clear each lock.

A note on durability

None of these data structures need to be persisted to disk. Lock state and in-flight transaction metadata are purely in-memory. If the process crashes mid-transaction, the transaction was never committed, so there is nothing to recover. Only committed transactions are durable (via the WAL entry we write at commit time).

Lock Upgrades

Consider a bank transfer. The transaction first reads the balance to check if there are sufficient funds, then writes the new balance:

• T1: GET balance → 50 (acquires read lock)
• // application logic: 50 + 20 = 70, sufficient funds ✓
• T1: PUT balance 70 (needs write lock)

But T1 already holds a read lock on balance. It now needs a write lock on the same key. Can we just upgrade the lock from read to write? This depends on who else is reading. Suppose T2 also holds a read lock on balance:

• T1: holds read lock on balance
• T2: holds read lock on balance
• T1 wants to upgrade to write lock...

If we allow the upgrade, T1 can now write a new value while T2 is still reading the old one. T2 would make decisions based on a value that no longer exists. This is exactly the dirty read problem we are trying to prevent.

So the rule for lock upgrades is: If T1 is the only reader, it can safely upgrade. No one else is reading the old value. If another transaction also holds a read lock, T1 cannot upgrade. In our implementation, if an upgrade is not safe, we return an error immediately rather than waiting. Simple, but it means the caller must retry.

Where Do Uncommitted Writes Go?

Let's trace what happens during a transaction:

T1: BEGIN
T1: PUT balance 70
T1: GET balance → 70
T1: PUT account_B 600
// ... more operations ...
T1: COMMIT

Between BEGIN and COMMIT, the writes are not yet final. The transaction might still roll back. So where do these writes go?

• They cannot go to the WAL. If they did and the transaction rolls back, the WAL would contain data that should never have existed. On recovery, those writes would be replayed as if they were committed.
• They cannot go to the memtable either. If they did, other transactions running concurrently could read the uncommitted values. This is the dirty read problem.

The solution is to buffer writes in-memory within the transaction itself. Each transaction maintains its own private map of key-value pairs. These buffered writes are invisible to everyone else (every other transaction or read outside transaction). Only at commit time do they get written to the WAL and memtable together.

T1: PUT balance 70 (buffered in transaction memory)
T1: GET balance → 70 (read from buffered memory)

The read path should be such that, on every GET within a transaction we check the buffered writes first. If the key exists there, return the buffered value. Only if the key is not in the buffer do we acquire a read lock and read from the underlying storage. Hence, we also add bufferedWriteMap to the Transaction struct now:

type Transaction struct {
    id               uint64
    db               *DB
    bufferedWriteMap  map[string]string
    lockAcquiredKeys []string
}

Achieving Atomicity in COMMIT

At commit time, we need to persist all buffered writes. But if we write them to the WAL one at a time:

WAL: [PUT account_A 400]  ← written
   [PUT account_B 600]  ← process crashes here, never written

We get a partial commit. Account A is debited, account B is not credited. This violates atomicity.

The solution is to serialize ALL buffered writes into a single WAL entry. The WAL already guarantees that each entry either fully exists on disk or does not (via length prefix + checksum). By packing the entire transaction into one single entry, we can achieve atomicity in a transaction.

The WAL entry format for a transaction becomes:

[len("TRANSACTION")]["TRANSACTION"][num_writes][len(payload_1)][payload_1][len(payload_2)][payload_2]...

For example, a bank transfer committing two writes would produce:

[11]["TRANSACTION"][2][18]["PUT account_A 400"][18]["PUT account_B 600"]

This entire sequence is written as a single WAL record with one checksum covering everything. If any byte is missing or corrupt, the entire transaction entry is rejected on recovery.

After the WAL write, we apply the buffered writes to the memtable and release all locks. Even if the process crashes after the WAL write but before memtable updates, recovery will replay the transaction entry and apply all writes.

This also means our WAL deserialization logic (which rebuilds the memtable on application startup) needs to be updated. Previously it only understood PUT commands. Now it must also recognize the TRANSACTION command and unpack the individual writes from within it.

Implementation

We discussed several data structures in the problem sections above: keyVsLocksAcquiredMap, LocksAcquired for read and write, transaction IDs, lockAcquiredKeys, and buffered writes as bufferedWriteMap. Let's put them all together and see how they look as Go structs.

type TransactionManager struct {
    mu                    sync.Mutex
    keyVsLocksAcquiredMap map[string]*LocksAcquired
    nextTxnId             uint64
}

type LocksAcquired struct {
    readerTxnIds []uint64
    writerTxnId  uint64
}

type Transaction struct {
    id               uint64
    db               *DB
    bufferedWriteMap  map[string]string
    lockAcquiredKeys []string
}

TransactionManager is shared across all transactions. It owns the lock table and a mutex to protect it. Transaction is per-session, each BEGIN creates a new transaction with a fresh ID.

From the caller's perspective, the API follows the pattern used by golang libraries like GORM:

txn := db.Begin()
val, err := txn.Get("balance")
err = txn.Put("balance", "70")
txn.Commit()

Write Path

When a transaction calls PUT, we acquire the write lock and buffer the value in bufferedWriteMap. Nothing touches the WAL or memtable.

func (txn *Transaction) Put(key, value string) error {
    // acquire write lock for key
    // if fails, return error
    txn.bufferedWriteMap[key] = value
    return nil
}