In Parts 1-3, we built a storage engine: WAL, memtable, SSTables, and compaction. Every operation is a single GET or PUT.
But real applications rarely need just one write at a time.
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
Time T1 T2
─────────────────────────────────────────────
1 PUT balance 100
2 GET balance → 100
3 ROLLBACK (undo PUT)
4 // T2 now holds value 100
// but that value never existed!
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
Time T1 T2
─────────────────────────────────────────────
1 GET balance → 50
2 GET balance → 50
3 balance = 50 + 20 = 70
4 PUT balance 70
5 balance = 50 + 30 = 80
6 PUT balance 80
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
Time T1 T2
─────────────────────────────────────────────
1 READ x → 5, READ y → 5
2 READ x → 5, READ y → 5
3 Check: x + y = 10 >= 0 ✓
4 SET x = -5
5 Check: x + y = 10 >= 0 ✓
6 SET y = -5
7 COMMIT
8 COMMIT
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 writesx, T2 writesy, 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 preventing more anomalies than the one before it. But with increasing isolation level, the concurrency and hence the overall througput can drop. This is because, in order to solve for these isolation anomalies, we can require acquiring more locks.
| Level | Dirty Reads | Lost Updates | Write Skew |
|---|---|---|---|
| Read Uncommitted | Possible | Possible | Possible |
| Read Committed | Prevented | Possible | Possible |
| Repeatable Read | Prevented | Prevented | Possible |
| Serializable | Prevented | Prevented | Prevented |
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:
Time T1 T2
─────────────────────────────────────────────
1 LOCK balance
2 GET balance → 50
3 LOCK balance → blocked (T1 holds it)
4 PUT balance 70
5 UNLOCK balance
6 (unblocked)
7 GET balance → 70
8 PUT balance 100
9 UNLOCK balance
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?
Time T1 T2
─────────────────────────────────────────────
1 LOCK x
2 GET x → 5
3 UNLOCK x
4 LOCK x
5 PUT x = -5
6 UNLOCK x
7 LOCK y
8 GET y → 5
9 PUT y = -5
10 UNLOCK y
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: db.Begin() returns a Transaction object with a unique ID, and all subsequent operations (Get, Put, Commit) are called on that object.
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 {
txn.db.transactionManager.mu.Lock()
err := txn.tryAcquireWriteLock(key)
txn.db.transactionManager.mu.Unlock()
if err != nil {
return err
}
if txn.bufferedWriteMap == nil {
txn.bufferedWriteMap = map[string]string{}
}
txn.bufferedWriteMap[key] = value
return nil
}
The tryAcquireWriteLock function is where the core locking logic resides. keyVsLocksAcquiredMap is a shared variable that multiple transactions can try to read and update concurrently. Hence the entire function is wrapped in a mutex lock by the caller (Put), ensuring only one transaction modifies the lock table at a time.
As the name states, we try to acquire the lock. It returns an error if some other transaction has already acquired a read or write lock on the key. The only cases where we can safely acquire is when no other transaction holds any lock on the key. If the current transaction already holds a read lock, we upgrade it to a write lock provided that only the current transaction holds a read lock.
The implementation takes care of the following:
- Check if write lock is acquired by some other transaction. If yes, return error.
- If already acquired by the current transaction, return early.
- Check if read locks are held by other transactions. If yes, return error.
- If only the current transaction holds a read lock, upgrade it (clear reader, set writer).
- Set
writerTxnIdto the current transaction ID and track the key inlockAcquiredKeys.
func (txn *Transaction) tryAcquireWriteLock(key string) error {
locksAcquired, ok := txn.db.transactionManager.keyVsLocksAcquiredMap[key]
readLockAlreadyAcquired := false
if !ok {
locksAcquired = &LocksAcquired{}
} else {
writerTxnId := locksAcquired.writerTxnId
if writerTxnId != 0 && writerTxnId != txn.id {
return fmt.Errorf("cannot acquire write lock as write lock acquired by transaction '%d'",
writerTxnId)
}
if writerTxnId == txn.id {
return nil
}
readerTxnIds := locksAcquired.readerTxnIds
if len(readerTxnIds) > 1 {
return errors.New(WriteLockNotAcquiredDueToReadLocksError)
}
if len(readerTxnIds) == 1 {
if readerTxnIds[0] == txn.id {
readLockAlreadyAcquired = true
locksAcquired.readerTxnIds = []uint64{}
} else {
return errors.New(WriteLockNotAcquiredDueToReadLocksError)
}
}
}
locksAcquired.writerTxnId = txn.id
if !readLockAlreadyAcquired {
txn.lockAcquiredKeys = append(txn.lockAcquiredKeys, key)
}
txn.db.transactionManager.keyVsLocksAcquiredMap[key] = locksAcquired
return nil
}
The readLockAlreadyAcquired flag prevents double-tracking the key in lockAcquiredKeys. If the transaction previously acquired a read lock on this key, the key is already in the list from that earlier call. Adding it again would cause releaseAllLocks to process it twice.
Read Path
On GET, we check the buffered writes first (read-your-own-writes) and then fall through to the storage engine.
func (txn *Transaction) Get(key string) (string, error) {
txn.db.transactionManager.mu.Lock()
err := txn.tryAcquireReadLock(key)
txn.db.transactionManager.mu.Unlock()
if err != nil {
return "", err
}
if value, ok := txn.bufferedWriteMap[key]; ok {
return value, nil
}
return txn.db.Get(key)
}
The tryAcquireReadLock implementation follows the same pattern as tryAcquireWriteLock. keyVsLocksAcquiredMap[key] is still a shared variable and requires using mutex lock.
The difference in the logic is that we return an error only if another transaction holds a write lock. Multiple read locks from different transactions can coexist, so existing read locks are not a conflict.
Commit Flow
We discussed earlier how atomicity is achieved by serializing all buffered writes into a single WAL entry (see "Achieving Atomicity in COMMIT" above). Here we focus on the order of operations.
The order matters. This follows the same principle we established in Part 1: write to WAL first, then update in-memory state. If the process crashes after the WAL write but before memtable updates, recovery replays the WAL and rebuilds the memtable. If it crashes before the WAL write, the transaction is simply lost as if it never happened.
func (txn *Transaction) Commit() error {
txn.writeSingleWalEntryForCommit()
for key, value := range txn.bufferedWriteMap {
txn.db.memTable.Put(key, value)
}
if txn.db.memTable.ShouldFlush() {
if err := txn.db.createSsTableAndClearWalAndMemTable(); err != nil {
return err
}
}
txn.releaseAllLocks()
txn.cleanupBufferedWriteMap()
}
Walking through the order:
- WAL write first. This is the durability guarantee. Once this succeeds, the transaction is committed regardless of what happens next.
-
Apply to memtable. Makes the writes visible to future reads. We write to the memtable directly (
txn.db.memTable.Put) rather than going throughdb.Put, sincedb.Putwould write separate WAL entries for each key. - Flush check. If the memtable is full, flush to SSTable. Same as the normal write path.
- Release locks. Other transactions that were blocked can now proceed.
- Cleanup. Discard the buffered write map.
releaseAllLocks iterates over txn.lockAcquiredKeys (the list we discussed earlier for efficient release) and for each key, does an O(1) lookup in keyVsLocksAcquiredMap to clear the lock. If the transaction held a write lock, it sets writerTxnId to 0. If it held a read lock, it removes the transaction ID from readerTxnIds.
Rollback Flow
Rollback is simpler: release all locks and discard the buffered writes. Since nothing was written to the WAL or the memtable, there is nothing to undo on disk or within in-memory memtable.
Improvement Areas
Our 2PL implementation works for the basics but has several simplifications:
No wait queue. When a lock conflict is detected, we return an error immediately. The caller must retry. A production database would maintain a wait queue. Transactions block until the conflicting transaction commits or rolls back.
No deadlock detection. If T1 holds lock on A and wants B, while T2 holds lock on B and wants A, both will error out. A proper system would detect this cycle and abort one transaction.
Single global mutex for the lock manager. All lock acquisitions and releases go through
transactionManager.mu. Under high concurrency, this becomes a bottleneck. Production databases shard the lock table across multiple mutexes.2PL vs MVCC. Our 2PL approach means readers block writers and writers block readers. PostgreSQL uses Multi-Version Concurrency Control (MVCC) instead where multiple versions of the same row coexist, and each transaction sees a consistent snapshot from its start time. Readers never block writers and vice versa. This is much better for read-heavy workloads but significantly more complex to implement.
What's Next
We have a transactional key-value store. Atomic multi-key writes. Isolation from concurrent readers. Rollback on failure.
In the upcoming parts, we will deep-dive on the SQL layer. This will include:
- The intuition and implementation of
CREATE TABLE,INSERTandSELECT. - Implementing secondary indexes for efficient reads.
- Implementing a query planner to choose the most efficient index or read path.
The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb
Top comments (0)