DEV Community: Gagandeep Singh Ahuja

Building SaarDB, Part 7: SELECT Query

Gagandeep Singh Ahuja — Sat, 15 Aug 2026 16:30:28 +0000

In Part 6, we saw that CREATE TABLE and INSERT are just PUT operations. Basis that, we can simply build SELECT queries, just by modelling it as GET operations, right? Well, not quite.

SELECT queries can be complex with multiple joins, aggregations and multiple WHERE conditions. Add to that, we can have multiple possible indexes to choose or even full-table scans if appropriate index is not present.

We will not start with tackling all possible problems, but focus on solving the simplest set of problems. The simplest problem is primary-key based lookup queries as those are just GET queries with key as the primary key itself.

After solving for primary-key based lookup, we will move to full-table scan to fetch all rows of a table. This is the next important step, because it is a brute force approach which is usually taken when we don't have the required set of indexes. If we are able to do a full-table scan, we can still return result for any SELECT query in a specific table even if that might not be optimal.

Primary Key Lookup

SELECT * FROM payments WHERE id = 5

During insert, we had already set the following key: _table:payments:5 as id was the primary-key.
After running the GET query, we just need to deserialise the schema based on the binary serialisation deserialisation contract we had agreed to while working on INSERT query.

Full-table Scan

SELECT * FROM payments

This is a fundamentally different problem compared to SELECT by primary key. We need every row in the table, but:

We do not have a list of all the primary keys of a table anywhere. Our KV store only supports GET by exact key. How do we scan an entire table?

Full-table Scan Approach 1: Maintain a Separate Key List

The first idea that comes to mind is to store a separate key primary_keys:payments containing a regular list or a sorted list of all primary keys: [1, 2, 3, 5, 7, ...].

On every INSERT, update this list. On SELECT *, read the list, then GET each key individually.

This sounds simple but has multiple shortcomings. Let us walk through them.

Updating a sorted list is O(N). To insert a new key into a sorted list of N keys, we need to find the insertion point and shift everything after it. With millions of rows, this becomes expensive for every single INSERT.

The list itself becomes a hot key. Every INSERT to the payments table writes to primary_keys:payments. Under concurrent writes, this single key becomes a bottleneck. Every transaction needs a write lock on it.

It does not scale. With 10 million rows, the list of primary keys alone is a massive value. Reading it into memory, deserializing it, then doing 10 million individual GETs is wasteful.

This approach was actually explored during development and explicitly discarded. It is worth showing the wrong path as the right solution is much more elegant.

Full-table Scan Approach 2: Prefix Scan

When we look at how the keys (rows) would be stored, we realise a clear pattern and a much more simpler, elegant and optimal solution:

_table:payments:1   → [row data]
_table:payments:2   → [row data]
_table:payments:5   → [row data]
_table:payments:7   → [row data]

Notice that both memtable and SSTable are sorted. This means that all rows (keys) for payments table would already be adjacent to each other.

We can just search for the first key which has the prefix as _table:payments: and then carry out a sequential scan till we encounter a different key. This approach solves the two areas which made our previous approach inefficient:

We don't need to store any additional list of primary keys. The required data already exists sequentially adjacent in both SSTable and memtable.
Since the data exists sequentially together, we get the performance benefit of sequential scans during reads instead of random scans. On the other hand, the previous approach required random scan for each GET query as the search for each key had to be done again explicitly even if we know that the keys are adjacent to each other.

We saw in the second blog that a key can reside either in memtable or in multiple SSTable files. And the priority order is memtable, then the SSTable files from newest to the oldest. Hence for carrying out a full-table scan, we require search through both memtable and SSTable.

Let's explore how this would be done in both SSTable and memtable:

Prefix Scan in SSTable

Recalling the SSTable Structure

In blog 2, we built SSTables with three parts: data blocks, an index block, and a footer block.

Data blocks hold the actual key-value pairs in sorted order. The index block holds one entry per data block: the first key of that data block and its byte offset. The footer holds the offset of the index block so we can find it.

Let's say the payments table has 8 rows. The SSTable would look like this:

Data block 0 (offset 0):
  _table:payments:1   → [row bytes]
  _table:payments:3   → [row bytes]
  _table:payments:5   → [row bytes]

Data block 1 (offset 512):
  _table:payments:10  → [row bytes]
  _table:payments:12  → [row bytes]
  _table:payments:15  → [row bytes]

Data block 2 (offset 1024):
  _table:payments:20  → [row bytes]
  _table:payments:25  → [row bytes]

Index block:
  _table:payments:1   → offset 0      (first key of block 0)
  _table:payments:10  → offset 512    (first key of block 1)
  _table:payments:20  → offset 1024   (first key of block 2)

The index block is what makes search efficient. Instead of reading the entire file, we binary search the index to narrow down which data block to start from.

How GET Uses the Index Block

getLowerBound(target, indexBlock) returns the index of the largest key less than or equal to the target. If all keys in the index are greater than the target, it returns -1.

Let's dry run GET _table:payments:12:

getLowerBound("_table:payments:12", index):

  _table:payments:1  ≤ _table:payments:12  → candidate
  _table:payments:10 ≤ _table:payments:12  → candidate (larger, preferred)
  _table:payments:20 > _table:payments:12  → too far

Returns index 1 → data block 1 (offset 512)

We jump to data block 1 and scan within it for the exact key. The logic is straightforward: since the index stores the first key of each block, a key X must live in the block whose first key is ≤ X. The next block starts at something larger, so X cannot be there.

Prefix Scan: Same Function, One Edge Case

For SELECT * FROM payments, the prefix we are looking for is _table:payments:.

We apply the same getLowerBound on the prefix key to find the starting block:

getLowerBound("_table:payments:", index):

  _table:payments:1  ≤ _table:payments:  ?
  _table:payments:10 ≤ _table:payments:  ?
  _table:payments:20 ≤ _table:payments:  ?

To answer this, we need to think about how string comparison works. Strings are compared character by character. _table:payments:1 and _table:payments: are identical up to the last character. But _table:payments:1 has one more character after the colon. In string comparison, a longer string that extends a shorter one is always greater. So:

_table:payments:1  > _table:payments:
_table:payments:10 > _table:payments:
_table:payments:20 > _table:payments:

Every index entry is greater than the prefix string. getLowerBound returns -1.

This will always be the case. _table:payments: will always be lexicographically smaller than any actual row key like _table:payments:1 or _table:payments:42, because the moment you append an ID after the colon, the key becomes strictly greater than the bare prefix string.

So -1 does not mean "no matching rows." We need to look at the first key of the index to understand what -1 means in this context. There can be two possible situations:

Situation 1: The file contains rows from the payments table.

index[0].key = _table:payments:1
HasPrefix(_table:payments:1, "_table:payments:") → YES
→ Start scanning from data block 0

Situation 2: The file contains rows from a different table that sorts after payments.

index[0].key = _table:users:1
HasPrefix(_table:users:1, "_table:payments:") → NO
→ Skip this file entirely

Hence, when getLowerBound returns -1, we need to check the prefix of the first key of the SSTable with the table prefix. If the prefix matches, all of the start rows in the SSTable are part of the same table. We should check sequentially till we encounter a different prefix. In case of a different prefix, we stop the search immediately.
On the other, if the prefix of the first key of SSTable doesn't match the table prefix, we can skip the entire file as the table would come after the table that we are searching for.

When getLowerBound returns a valid index (not -1), it means there are keys in the index that are ≤ the prefix. We start from that data block.

This also handles the case where a data block contains rows from multiple tables. For example, if block 0 starts at _table:cart:1 but also contains _table:payments:1 through _table:payments:9, getLowerBound returns block 0, ensuring we do not miss those rows. Starting from the last block whose first key is ≤ the prefix guarantees we never miss rows that happen to sit across a block boundary.

Sequential Scan: Reading Beyond One Data Block

Once we have the starting data block, we read forward sequentially, collecting all keys that match the prefix. Unlike GET which stops at a single data block, prefix scan continues across multiple data blocks as long as the prefix keeps matching.

We stop when we encounter a key whose first N characters (where N is the length of the prefix) are greater than the prefix. That means we have left the table's key space.

Dry running the full scan with our example:

getLowerBound returns index 0 → start at data block 0

Data block 0:
  _table:payments:1  → has prefix → collect
  _table:payments:3  → has prefix → collect
  _table:payments:5  → has prefix → collect

Data block 1:
  _table:payments:10 → has prefix → collect
  _table:payments:12 → has prefix → collect
  _table:payments:15 → has prefix → collect

Data block 2:
  _table:payments:20 → has prefix → collect
  _table:payments:25 → has prefix → collect

End of file → done

If the next key were _table:products:1, the first 16 characters _table:products: > _table:payments:, so we stop immediately.

One more difference from GET is that prefix scan must go through every SSTable file from newest to oldest. This is because different rows of the same table can exist across multiple files from separate flushes. Unlike GET, which stops at the first file containing the key, we cannot skip any file.

The Code

Based on our learnings, the core logic becomes:

Go through every SSTable file from newest to oldest.
For each SSTable file, apply binary search on the index block array to find the lowerBound for the prefix key. Prefix key is nothing but the common prefix which each table has. Example: _table:payments:. Lower bound is the largest key in index block which is less than or equal to prefixKey. .
If the lowerBound is returned as -1, it could mean two things:
- If the prefix of the first index block key in the SSTable file is greater than the prefix key of the table, it means that all prefixes in this file are greater and the file can be skipped.
- On the other hand, if prefix is exactly the same, we sequentially scan the file from the first data block itself.
Sequentially go through from the start of the data block ( as per the found lowerBound data block) to the end of the data block (which is the start of the index block).
- Maintain an in-memory hashmap of result where key is the prefix key and the value is the serialised row. This hashmap is required to ensure that a key is only added if it is seen for the first time. The newest occurence in the newest file is the source of truth for a key as it has the most up-to-date value.
- If we encounter a prefix which is greater than the table prefix key, we can exit and move to the next file.

With this intuition, the code reads naturally:

func (st *SsTable) PrefixScan(prefixKey string) (map[string]string, error) {
    st.mutex.RLock()
    defer st.mutex.RUnlock()
    tableMap := map[string]string{}
    // go through every SSTable file. rows of the same table can exist across multiple files
    for i := len(st.firstLevelFiles) - 1; i >= 0; i-- {
        file := st.firstLevelFiles[i]
        ssTableIndex := st.indexBlocks[i]
        lowerBoundSliceIndex := getLowerBound(prefixKey, ssTableIndex)
        if lowerBoundSliceIndex == -1 {
            // all index keys are greater than the prefix string.
            // check the first key to understand why.
            if len(ssTableIndex) == 0 || !strings.HasPrefix(ssTableIndex[0].key, prefixKey) {
                // first key does not have our prefix. the file has no matching rows.
                continue
            }
            // first key has our prefix. start from data block 0 and let
            // the sequential scan stop when it moves past the prefix zone.
            lowerBoundSliceIndex = 0
        }
        endOffset := st.indexOffsets[i]
        var err error
        tableMap, err = st.sequentiallyScanTableAndUpdateMap(file, prefixKey,
            ssTableIndex[lowerBoundSliceIndex].offset, endOffset, tableMap)
        if err != nil {
            return nil, err
        }
    }
    return tableMap, nil
}

func (st *SsTable) sequentiallyScanTableAndUpdateMap(ssTableFile *os.File, tableKey string,
    dataBlockStartOffset, fileEndOffset int, tableMap map[string]string) (map[string]string, error) {
    ssTableDataBlockBuf := make([]byte, fileEndOffset-dataBlockStartOffset)
    _, err := ssTableFile.ReadAt(ssTableDataBlockBuf, int64(dataBlockStartOffset))
    if err != nil && err != io.EOF {
        return nil, err
    }
    for i := 0; i < len(ssTableDataBlockBuf); {
        key, err := extractValueFromSsTable(ssTableDataBlockBuf, i)
        if err != nil {
            return nil, err
        }
        i += (4 + len(key))
        value, err := extractValueFromSsTable(ssTableDataBlockBuf, i)
        if err != nil {
            return nil, err
        }
        i += (4 + len(value))

        if strings.HasPrefix(key, tableKey) {
            // only set if not already found. newest file was processed first,
            // so the first value we see for a key is always the most recent.
            if _, ok := tableMap[key]; !ok {
                tableMap[key] = value
            }
        } else {
            // stop as soon as we have moved past the prefix zone
            keyPrefix := key[0:min(len(tableKey), len(key))]
            if keyPrefix > tableKey {
                return tableMap, nil
            }
        }
    }
    return tableMap, nil
}

Prefix Scan In Memtable

Since memtable contains most up-to date data, we would need to run a prefix scan on the memtable as well.
The prefix scan is much simpler for memtable compared to SSTable. This is because in case of SSTable, we had to deal with "data block first-keys" within index block (means that index block stores the first keys of the data block and their offset) and due to that, we need to find the last key in index block which is just less than the prefix key (lowerBound).

Lets take an example to make this more clear. Let's assume that the index block is:
_table:cart:4, _table:cart:20, _table:orders:10, _table:payments:25

If we are searching for payments table, we should be looking for keys from _table:orders:10 which is just less than or equal to _table:payments, even though the only index block containing payments keyword is _table:payments:25. This is because _table:orders:10 might contain some keys from payments:1 to payments:24 and we would miss out on those keys if we only search from _table:payments:25.

On the other hand, in case of memtable we deal with all the list of keys present in the in-memory sorted hashmap. Hence, we just need to find the first key which is just greater than or equal to the prefix key (we can call this upperBound). For example, in case of memtable, it will just return some key starting with _table:payments like _table:payments:4 for payments table and we don't need to look at keys which are less than _table:payments.

We have done exactly that in our memtable implementation. We have used github.com/google/btree go package which implements B-tree and provides AscendGreaterOrEqual function to return the first key greater than or equal to target and also allows iterating over those keys.

Using Both

Based on our learnings from blog 2, we now that memtable contains the most recent writes. Hence, in cases where the same key is present in both SSTable and Memtable, memtable is the source of truth.

We have done exactly that in the implementation:

func (db *DB) fullTableScan(tableName string) ([][]string, error) {
    key := fmt.Sprintf("%s:", tableName)
    memTableMap := db.memTable.PrefixScan(key)
    ssTableMap, err := db.ssTable.PrefixScan(key)
    if err != nil {
        return nil, err
    }

    scanOutput := [][]string{}
    // Process memtable results first
    for _, value := range memTableMap {
        values, err := db.deserializeRowValues(tableName, value)
        if err != nil {
            return nil, err
        }
        scanOutput = append(scanOutput, values)
    }

    // Process SSTable results, skip keys already in memtable
    for key, value := range ssTableMap {
        if _, ok := memTableMap[key]; ok {
            // memtable has the most up-to-date value. if key already ready in memtable, skip
            // reading SSTable.
            continue
        }
        values, err := db.deserializeRowValues(tableName, value)
        if err != nil {
            return nil, err
        }
        scanOutput = append(scanOutput, values)
    }
    return scanOutput, nil
}

Filtering by Non-Primary-Key Columns

Let's look at filtering queries like:

SELECT * FROM payments WHERE status = pending

status is not the primary key. We cannot do a targeted GET. There is no key payments:pending in our KV store. The key is payments:<id>, not payments:<status>.

Without any additional structures, the only option is:

Full table scan (prefix scan on payments:)
For each row, deserialize and check if status = pending
Return matching rows

This works. But it is O(N). We read every row in the table to find the ones that match. With 10 million rows and only 500 matching, 99.995% of the work is wasted.

What's Next

We were able to build solution for running full-table scan which can also be extended to filter based on the required conditions.

In Part 8, we will deep-dive into secondary and composite indexes and add support for them in our database. These would help optimise non-primary-key column queries to only go through the required number of rows.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb

Building SaarDB, Part 6: How SQL Queries Become Key-Value Operations

Gagandeep Singh Ahuja — Mon, 10 Aug 2026 03:15:41 +0000

In Blog 5, we built a SQL parser. It can take this:

INSERT INTO payments VALUES (500, payment_1, pending, 1)

and turn it into a struct:

InsertIntoTable{
    TableName: "payments",
    ColumnValues: []string{"500", "payment_1", "pending", "1"},
}

But this is still not enough for the storage engine.

Our storage engine only knows how to store key-value pairs. It does not know what a table is. It does not know what a column is. It does not know that 500 is an integer, pending is a string, and 1 is a boolean.

So, in this post we solve the missing bridge of persisting these in our key-value store.

CREATE and INSERT are PUT operations

This is the first major realisation. A key-value store is extensible to store literally anything. This is what we have been saying from the first post itself. But now we will be taking actual examples to prove that.

CREATE TABLE Example

Let's start with the create table example and see what should be the key and the value.

Serialisation

The key should be something that uniquely identifies the table, which is straightforward enough in this case as the table name. The value becomes everything else except the key, which is the schema of the table.

So, in order to store the table name, we can append a reserved keyword as prefix like schema as a unique identifier. The structure of the key becomes _schema:<table_name>.

The next question to answer is:

How do we store a struct like below into our key value store where the value is always string?

    CreateTable{
        TableName: "payments",
        ColumnDetails: []Column{
            {ColumnName: "amount", DataType: Int},
            {ColumnName: "id", DataType: String},
            {ColumnName: "status", DataType: String},
            {ColumnName: "captured", DataType: Bool},
        },
        PrimaryKeyColumnPosition: 1,
    }

One way is to serialise the entire struct into a string and store that directly. But in that case, deserialisation is a complex logic. JSON or struct serialisation and deserialisation is both space-heavy and compute intensive. This is because JSON and struct take up a lot of space, which is wasted space in case of a disk. They are good for external viewing purposes but not for internal use cases like this. Example: "ColumnDetails" is not needed to be stored and wasted space if we know that we need to write ColumnDetails first. Similar is the case for others fields like "ColumnName", "DataType" or "PrimaryKeyColumnPosition".

If we store the data in such a way that we already know the structure beforehand and can have an agreed common serialisation and deserialisation strategy, it would save up a lot of space. Example: value should start with the position of primary key column, followed by N different column types and data types.

Hence, the structure becomes something like:

[pkColumnPosition][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...

Notice the following here: we are following the same binary serialisation strategy which we have been doing since the first and second blog. columnName is of type string (variable length), hence it is prefixed with length. On the other hand, pkColumnPosition, columnDataType are integers (fixed length), hence they are directly written. This also means that we will continue to write the data as array of bytes. In the end, it is bytes which is written to WAL or SS-Table Files.

    // serialisation strategy: [PK_column_position][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...
    // secondary index serialisation is covered separately even though it is part of the same CREATE TABLE input.
    func serialiseCreateTableInput(createTableInput sqlparser.CreateTable) []byte {
        serialisedSchema := []byte{}
        // 1. append primary key column position
        serialisedSchema = binary.BigEndian.AppendUint32(serialisedSchema, uint32(createTableInput.PrimaryKeyColumnPosition))

        for _, col := range createTableInput.ColumnDetails {
            // 2. append column data type (byte: 8 bit integer)
            serialisedSchema = append(serialisedSchema, byte(col.DataType))
            // 3. append length of column name
            serialisedSchema = binary.BigEndian.AppendUint32(serialisedSchema, uint32(len(col.ColumnName)))
            // 4. append column name
            serialisedSchema = append(serialisedSchema, []byte(col.ColumnName)...)
        }

        return serialisedSchema
    }

There is one more interesting thing in the above code. Notice the second comment where we append the data type. Data type appears to be a string. But due to the limited set of possible values of a column data type, we use a byte (8 bit integer) here allowing us to save space. For example: if we are only supporting 3 different datatypes: INT, STRING, BOOL, then all of them can be represented as unique integers: 0, 1, and 2. 8 bit integer means 2^8 (= 256) possible values which we can support.

Once we have the key and the serialised value, this covers the write path. During the create table command, we just write this key value pair by utilising the Put command.

Deserialisation

In the earlier section, we discussed how the CREATE TABLE can be modelled into a Put operation by binary serialisation of the schema.

While inserting the row using INSERT command, we require knowing the schema of the table. This is because, within the AST struct we had represented every column value as string (500 was "500"). But while storing those values on disk, we require storing it as per the relevant data type.

In order to fetch the schema, we require firing a GET query for the specific table name as the key. It would be wasteful to fire this GET query everytime an INSERT query needs to be performed. Hence, a series of GET queries for all the tables should be performed during the application bootup itself to store the schema of each table in-memory.

Since, we already know the structure of create table value as below, we need to iterate through the byte array and read the required number of bytes.

    [pkColumnPosition][columnDataType1][columnNameLength1][columnName1][columnDataType2][columnNameLength2][columnName2]...

Below code demonstrates this logic. This deserialisation logic is run for each table during the application bootup:

func deserialiseCreateTableInput(buf []byte) (*sqlparser.CreateTable, error) {
    var createTableMeta sqlparser.CreateTable
    i := 0
    if len(buf) < 4 {
        return nil, errors.New("unexpected error while reading primary key column position")
    }
    // 1. read 4 bytes of pk column position. primary key column position is a 32-bit integer.
    // iterate byte array by 4 (can be done within a byte itself if we set a limit of 255 columns in a table)
    primaryKeyColumnPosition := binary.BigEndian.Uint32(buf[i : i+4])
    createTableMeta.PrimaryKeyColumnPosition = int(primaryKeyColumnPosition)
    i += 4

    columnDetails := []sqlparser.Column{}
    for i < len(buf) {
        var columnMeta sqlparser.Column
        dataType := buf[i]
        if i+1 > len(buf) {
            return nil, errors.New("unexpected error while reading column data type")
        }
        // 2. read 1 byte of data type and convert to internal enum
        // iterate byte array by 1
        columnMeta.DataType = sqlparser.DataType(dataType)
        i++

        if i+4 > len(buf) {
            return nil, errors.New("unexpected error while reading column length")
        }
        // 3. read 4 bytes of column name length
        // iterate byte array by 4
        columnNameLength := binary.BigEndian.Uint32(buf[i : i+4])
        i += 4

        if i+int(columnNameLength) > len(buf) {
            return nil, errors.New("unexpected error while reading column name")
        }
        // 4. read column_name_length bytes to fetch column name
        // iterate byte array by column_name_length
        columnMeta.ColumnName = string(buf[i : i+int(columnNameLength)])
        i += int(columnNameLength)

        columnDetails = append(columnDetails, columnMeta)
    }
    createTableMeta.ColumnDetails = columnDetails

    return &createTableMeta, nil
}

Atomicity in CREATE TABLE

We are still missing one piece in the application bootup process.

If we require fetching all create table rows, how do we come to know of all of the tables?

A simple solution is to write all of the table names in a separate key called _catalog:table_names with the value as comma separated list of all tables. This makes the Create Table operation non-atomic with multiple PUT commands (PUT for "table schema" and "table names").

In order to make the CREATE TABLE atomic, we will utilise the transaction capability we built in blog 4. Our CreateTable function would look something like:

    func (db *DB) createTable(createTableInput sqlparser.CreateTable) error {
        // 1. Transaction Begin
        txn, err := db.Begin()
        if err != nil {
            return err
        }

        var tableNames string
        for _, table := range db.tableNameVsSchemaMap {
            tableNames += table.TableName
            tableNames += ","
        }
        tableNamesLength := len(tableNames)
        tableNames = tableNames[:tableNamesLength-1]

        // 2. PERFORM PUT operation with _catalog key and all table names.
        // If PUT operation fails, rollback the transaction
        if err := txn.Put(CatalogKey, tableNames); err != nil {
            txn.Rollback()
            return errors.New(transactionRolledback)
        }

        tableName := createTableInput.TableName

        // 3. PERFORM PUT operation with _schema:[table_name] key
        // If PUT operation fails, rollback the transaction
        if err := txn.Put(fmt.Sprintf(SchemaTemplate, tableName), string(
        serialiseCreateTableInput(createTableInput))); err != nil {
            txn.Rollback()
            return errors.New(transactionRolledback)
        }

        // 4. Transaction Commit
        txn.Commit()

        return nil
    }

INSERT INTO Example

We now have a fairly good understanding on how CREATE TABLE converts AST struct into raw bytes. We will now carry out a similar deep-dive with the INSERT INTO command.

INSERT INTO payments VALUES (500, payment_1, pending, 1)

Serialisation

Similar to CREATE TABLE case, we need to figure out what should be the key and the value. The key choice is straightforward in this case as well. A primary key is the unique identifier for a row. Storing the primary key as the key for the key-value store also ensures that we don't require scanning the full table to find out the required key. We can just fire a GET query with the specific key to fetch the specific row. So, the key can be something like _table:<table_name>:<primary_key_value>.

The value would contain all of the values. Example: (500, payment_1, pending, 1) in this case. To reduce space, we can remove primary key from the value. For simplicity, we have not done that in the current version.

In order to serialise the value, each column value is stored as per the column datatype. We utilise the schema saved in-memory during application bootup to check the schema instead of firing a GET query explicitly.

As of now, we only support 3 data types: Int, String and Bool. Only string values are prefixed with length while Int and Bool don't require length prefix.

So, the serialisation and deserialisation structure would be:

key: _table:<table_name>:<primary_key_value>
value: [value1][size_of_value2][value2][value3]

Note: value1 and value3 are fixed sized datatype like int and bool while value2 is variable sized datatype like string.

    func (db *DB) serialiseInsertIntoTableInput(insertIntoTableInput sqlparser.InsertIntoTable) (
        key string, valueSchemaBuf []byte, err error) {
        tableName := insertIntoTableInput.TableName
        table := db.tableNameVsSchemaMap[tableName]
        primaryKeyValue := ""
        for i, columnValue := range insertIntoTableInput.ColumnValues {
            if i == table.PrimaryKeyColumnPosition {
                primaryKeyValue = columnValue
            }
            switch table.ColumnDetails[i].DataType {
            case sqlparser.Int:
                valueInt, err := strconv.Atoi(columnValue)
                if err != nil {
                    return "", nil, err
                }
                // 1. Integer case: append 4 byte integer directly
                valueSchemaBuf = binary.BigEndian.AppendUint32(valueSchemaBuf, uint32(valueInt))
            case sqlparser.String:
                // 2. String case: first append length of the string which is 4 bytes and then append the string
                valueSchemaBuf = binary.BigEndian.AppendUint32(valueSchemaBuf, uint32(len(columnValue)))
                valueSchemaBuf = append(valueSchemaBuf, []byte(columnValue)...)
            case sqlparser.Bool:
                // 3. Boolean case: append 1 byte boolean directly
                valueInt, err := strconv.Atoi(columnValue)
                if err != nil {
                    return "", nil, err
                }
                if valueInt != 0 && valueInt != 1 {
                    return "", nil, errors.New("only 0 and 1 values supported for BOOL data type")
                }
                valueSchemaBuf = append(valueSchemaBuf, uint8(valueInt))
            }
        }

        return fmt.Sprintf("_table:%s:%s", tableName, primaryKeyValue), valueSchemaBuf, nil
    }

Optimising Space

When we implement more data types, we see the beauty on how they help optimise space of the row and in turn the entire table. A few datatype examples are:

VARCHAR(255)

As of now, the string datatype that we added is taking up 32 bit or 4 bytes for storing length. We would have frequently seen the VARCHAR datatypes capped at a length of 255 characters.

This number 255 is intentional (2^8 = 256). Keeping varchar limited till 255 ensures that a single byte is sufficient rather than requiring 4 bytes length prefix for an integer.

For most use cases 255 characters are sufficient for representing the required string datatype.

CHAR(14)

Apart from VARCHAR, we would have also seen constant character datatypes, CHAR used while creating tables in MySQL or Postgres. They are especially useful for columns which require storing a unique id.
These constant character datatypes help reduce space. This is because unlike regular string or VARCHAR datatypes, a prefix for indicating length is not required to be written, potentially saving 1 to 4 bytes of space.

TINYINT

TINYINT is a datatype which takes up 1 byte of space. This means that it can take up 2^8 values from -128 to 127. If we use UNSIGNED, values from 0 to 255 can be supported.

It can help save space from regular 4 bytes to 1 byte in tables where we know that the value will not exceed this range. Example: percentage or student marks or student ages.

ENUMs

ENUMs are a very useful datatype in cases where we know that the column has low cardinality values. This just means that the number of unique possible values are quite low.

As an example: payment status could only have a limited set of values. Instead of storing string every time, enums allow mapping each string to a unique number. For example: payment status "success" is mapped to number 0, "failed" is mapped to number 1, "captured" is mapped to number 2 and so on.

This means that every time we just need to store a 1 byte number or a TINYINT instead of storing the actual strings where the actual string could take around 21 bytes of space for a 20 character string (1 byte for indicating length and 20 bytes for the actual string).

Atomicity in INSERT INTO

Soon, similar to CREATE TABLE command, we will require wrapping the INSERT INTO command also in a transaction block to achieve atomicity. This is because secondary index updates require a separate PUT operation. We will deep-dive more on this in a future blog.

Deserialisation

Deserialisation of the value stored during INSERT would be required during SELECT query.

We already covered a deep-dive on deserialisation in the CREATE TABLE section by iterating through the byte array and reading bytes based on the common contract structure which is agreed during serialisation. The deserialisation implementation is hence kept out of the blog and can be tried out by the reader as an interesting exercise.

What's Next

In blog 5 and 6, we got the intuition behind how CREATE and INSERT SQL queries can be converted into PUT operations within our existing key-value store.
In the upcoming blogs, we shift the focus to the read path and supporting SELECT queries.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb

Building SaarDB, Part 5: SQL Parsing

Gagandeep Singh Ahuja — Mon, 03 Aug 2026 03:37:48 +0000

In Parts 1-4, we built a transactional key-value store. It has WAL for durability, memtables and SSTables for storage, compaction to control file growth, and transactions for atomic multi-key writes.

Now we move to the query layer where users can actually fire SQL queries like:

CREATE TABLE payments (amount INT, id STRING, status STRING, captured BOOL, PRIMARY KEY (id))
INSERT INTO payments VALUES (500, payment_1, pending, 1)
SELECT * FROM payments WHERE id = payment_1

In this blog and the next one we answer:

How do we translate SQL strings into operations our key-value store already understands?

This post focuses on the first half of that bridge, which is parsing SQL into structured commands. In the next post, we will take those commands and turn CREATE TABLE and INSERT into bytes on disk.

The Core Idea: SQL Becomes Structured Data

The storage engine does not understand SQL. It understands keys, values, WAL entries, memtables, SSTables, and transactions.

So the SQL layer has two jobs:

Parse a human-readable SQL string into a structured object.
Translate that structured object into key-value operations.

For example:

CREATE TABLE payments (...)
    -> CreateTable{TableName: "payments", ColumnDetails: ...}

INSERT INTO payments VALUES (...)
    -> InsertIntoTable{TableName: "payments", ColumnValues: ...}

SELECT * FROM payments WHERE id = payment_1
    -> SelectFromTable{TableName: "payments", QueryConditions: ...}

Once we have these structs, the rest of the database can stop dealing with raw strings.

Why Not Parse SQL Directly in the DB Layer?

Imagine if db.CreateTable() directly walked through the SQL string and also updated storage. That would mix two very different responsibilities:

parsing grammar,
executing database operations.

Keeping them separate makes the system easier to reason about. The parser validates syntax and builds an AST. The DB layer receives that AST and decides what to store.

An AST, or Abstract Syntax Tree, is just a structured representation of the command.

This is how the AST struct for the 3 common use cases, CREATE, INSERT, SELECT would look like:

type CreateTable struct {
    TableName                string
    ColumnDetails            []Column
    PrimaryKeyColumnPosition int
    SecondaryIndexes         []SecondaryIndex
}

type InsertIntoTable struct {
    TableName    string
    ColumnValues []string
}

type SelectFromTable struct {
    TableName       string
    ColumnsRequired []string
    QueryConditions []QueryCondition
}

Notice that InsertIntoTable.ColumnValues is still []string. The parser does not convert 500 into an integer yet. That conversion can happen while storing in the database. The parser only understands syntax.

Parsing SQL Queries

Let's take an example for parsing one of the SQL queries.

For CREATE TABLE, the expected shape is:

CREATE TABLE <table_name> (
    <column_name> <data_type>,
    ...
    PRIMARY KEY (<column_name>)
);

We need to extract all of the useful properties out of the string into our AST CreateTable struct. One way could be to go through each of the words and keep on extracting character by character and word by word.

So, in case of CREATE TABLE queries, the parser should do something like:

Expect keyword CREATE.
Expect keyword TABLE.
Expect the table name. Store those in the AST struct.
Expect (.
Read column definitions until ). While reading column definitions, extract the column name and the data type. Store those in the AST struct.
If it sees PRIMARY KEY (...), store the primary-key column.
Return a CreateTable struct.

The SQL query could also contain whitespaces (spaces, tabs '\t' and new lines '\n'). The SQL query should also end with a ;.

Notice that the CREATE TABLE query parsing requires identifying a lot of details which are specific to this query like table name, column names and data type and the primary key column name, along with the necessary validations.

Apart from these distinct requirements for the specific query, there is a lot of common logic that needs to be handled for each SQL query. This includes:

Each query includes keywords like CREATE, TABLE, INSERT, INTO, SELECT, FROM, WHERE and AND.
Each query includes one or more of expressions like (, ), ,, ;, and *.
Each query can contain unique identifiers based on the use case. In case of CREATE TABLE queries, this could be table name, column name, data type or primary key column name. Similarly in case of SELECT query, it could be a column name or its query condition.

Tokeniser: Breaking SQL Into Small Pieces

Tokenisation is a common operation applicable across all SQL queries. We break the input string into small meaningful pieces called tokens.

For this query:

CREATE TABLE payments (amount INT, id STRING);

The tokens are:

CREATE     keyword
TABLE      keyword
payments   identifier
(          symbol
amount     identifier
INT        identifier
,          symbol
id         identifier
STRING     identifier
)          symbol
;          symbol

Tokenisation is the first step performed to avoid directly parsing the string. We will soon see how this step drastically simplifies things because of us working with tokens and not raw characters.

We will build a function whose job is to find the next token from the input string. It tracks the index position in the input string in a private variable pos which indicates the index till which we have already tokenised.

The tokeniser walks through the input character by character:

Skip whitespace.
Return symbols like (, ), ,, ;, and *.
Return conditional operators like =, <, <=, >, and >=.
Read alphanumeric words and decide whether they are keywords or identifiers.

This is how the NextToken function looks like:

func (t *Tokeniser) NextToken() Token {
    t.skipWhiteSpace()
    // the entire input string is read
    if t.pos >= len(t.input) {
        return Token{Type: EOF}
    }

    ch := t.input[t.pos]
    // SYMBOL token
    if ch == '(' || ch == ')' || ch == ',' || ch == ';' || ch == '*' {
        t.pos++
        return Token{Type: SYMBOL, Value: string(ch)}
    }

    // CONDITIONAL_OPERATOR token 
    if strings.ContainsRune(conditionalOperators, t.input[t.pos]) {
        start := t.pos
        for t.pos < len(t.input) && strings.ContainsRune(conditionalOperators, t.input[t.pos]) {
            t.pos++
        }
        return Token{Type: CONDITIONAL_OPERATOR, Value: string(t.input[start:t.pos])}
    }

    start := t.pos
    for t.pos < len(t.input) && isAlphanumeric(t.input[t.pos]) {
        t.pos++
    }

    // KEYWORD or IDENTIFIER token
    word := t.input[start:t.pos]
    if _, ok := keywordsMap[strings.ToUpper(word)]; ok {
        return Token{Type: KEYWORD, Value: strings.ToUpper(word)}
    }
    return Token{Type: IDENTIFIER, Value: word}
}

keywordsMap would contain the list of all supported SQL keywords like CREATE, INSERT, SELECT, etc.

Note that the only job of NextToken is to find the next upcoming token and classify it as a KEYWORD, IDENTIFIER, SYMBOL or CONDITIONAL_OPERATOR.

This is a common step required for parsing each SQL query.

Consuming Tokens

Once we know the NextToken, consuming, validating the token and converting into AST struct becomes much simpler.

We also have a common consume function which is used by each of the parser implementation functions (ParseCreateTable, ParseInsertInto, ParseSelect).

While parsing the input query, we always know what is the expected token type (KEYWORD or SYMBOL or IDENTIFIER). In case of token type as KEYWORD or SYMBOL, we also know what is the expected value. For example: In case of CREATE TABLE, the first two expected keywords are CREATE and TABLE. After that we expect the table name and just after that we expect the symbol (.

This is how the consume function looks like.


type TokenType string

// Supported Token Types
const (
    IDENTIFIER           TokenType = "IDENTIFIER"
    KEYWORD              TokenType = "KEYWORD"
    SYMBOL               TokenType = "SYMBOL"
    CONDITIONAL_OPERATOR TokenType = "CONDITIONAL_OPERATOR"
    EOF                  TokenType = "EOF"
)

func (p *Parser) consume(tt TokenType, expectedVal string) error {
    if p.currentToken.Type != tt || (expectedVal != "" && p.currentToken.Value != expectedVal) {
        return fmt.Errorf("syntax error: expected %s %q, got %s %q",
            tt, expectedVal, p.currentToken.Type, p.currentToken.Value)
    }
    p.currentToken = p.tokeniser.NextToken()
    return nil
}

Notice that in case of identifier, we would not be having any expected value (expectedVal = "") as identifiers are used to fill in the AST structure. While in case of keyword or symbol, we know the expected value (expectedVal != "").

Parsing CREATE TABLE

Let's take CREATE TABLE as an example to solidify our understanding. Rest of the queries would have similar logic for parsing queries. We can utilise the consume function for parsing any SQL query.

CREATE TABLE payments (amount INT, id STRING, status STRING, captured BOOL, PRIMARY KEY (id))

The algorithm would look something like:

Consume CREATE as a KEYWORD.
Consume TABLE as a KEYWORD.
Consume IDENTIFIER for table name and set that within the AST struct of CreateTable.
Consume ( as a SYMBOL.
Run a for loop till we encounter ) SYMBOL as the current token.
- Consume identifier for column name and data type and set that within the AST struct of CreateTable
- The next token could be the keyword PRIMARY. If yes,
  - Consume keywords PRIMARY and KEY
  - Consume identifier for primary key column and set that within the AST struct of CreateTable.
- Consume symbol ,

What we wrote can be modeled into code as:

    func (p *Parser) ParseCreateTable() (*CreateTable, error) {
        if err := p.consume(KEYWORD, KeywordCreate); err != nil {
            return nil, err
        }
        if err := p.consume(KEYWORD, KeywordTable); err != nil {
            return nil, err
        }
        tableName := p.currentToken.Value
        if err := p.consume(IDENTIFIER, ""); err != nil {
            return nil, err
        }

        if err := p.consume(SYMBOL, SymbolOpenRoundBracket); err != nil {
            return nil, err
        }

        columnDetails := []Column{}
        pkColumn := ""
        for p.currentToken.Value != SymbolClosedRoundBracket {
            if p.currentToken.Value == "," {
                p.consume(SYMBOL, ",")
            }
            if p.currentToken.Value == KeywordPrimary {
                var err error
                pkColumn, err = p.parsePrimaryKeyColumn()
                if err != nil {
                    return nil, err
                }
                continue
            }

            columnName := p.currentToken.Value
            if err := p.consume(IDENTIFIER, ""); err != nil {
                return nil, err
            }
            columnType := p.currentToken.Value
            if err := p.consume(IDENTIFIER, ""); err != nil {
                return nil, err
            }
            dataType, err := getDataTypeFromString(columnType)
            if err != nil {
                return nil, err
            }
            columnDetails = append(columnDetails, Column{
                ColumnName: columnName,
                DataType:   dataType,
            })
        }

        if len(columnDetails) == 0 {
            return nil, fmt.Errorf("expected atleast one column detail, found none")
        }

        // current simplification that if PRIMARY KEY is not provided, consider first column as primary key
        pkColumnPosition := 0
        if pkColumn != "" {
            pkColumnPosition = -1
            for i, col := range columnDetails {
                if col.ColumnName == pkColumn {
                    pkColumnPosition = i
                }
            }
            if pkColumnPosition == -1 {
                return nil, fmt.Errorf("primary key column '%s' not found", pkColumn)
            }
        }

        if err := p.consume(SYMBOL, SymbolClosedRoundBracket); err != nil {
            return nil, err
        }

        return &CreateTable{
            TableName:                tableName,
            ColumnDetails:            columnDetails,
            PrimaryKeyColumnPosition: pkColumnPosition,
        }, nil
    }

The parser returns:

CreateTable{
    TableName: "payments",
    ColumnDetails: []Column{
        {ColumnName: "amount", DataType: Int},
        {ColumnName: "id", DataType: String},
        {ColumnName: "status", DataType: String},
        {ColumnName: "captured", DataType: Bool},
    },
    PrimaryKeyColumnPosition: 1,    // 1 is the index of "id" in the ColumnDetails array, which is the primary key
}

This is already much easier for the DB layer to use than a raw SQL string.

Current Parser Limitations

This parser is intentionally small. A few examples:

String literals are not quoted yet, so examples use pending, not 'pending'.
INSERT requires values for all columns in schema order.
SELECT supports simple WHERE conditions and AND, not joins, grouping, or expressions.
CREATE supports limited set of datatypes.

These limitations are acceptable for now because the goal is to build intuition one layer at a time.

What's Next

Parsing turns SQL strings into structs. But a struct is still not durable data.

Now we need to answer the deeper question in the next post:

Once we have CreateTable and InsertIntoTable AST structs, how do we store them inside a key-value engine?

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb

Building SaarDB, Part 4: Transactions

Gagandeep Singh Ahuja — Sun, 26 Jul 2026 22:21:55 +0000

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 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 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 writerTxnId to the current transaction ID and track the key in lockAcquiredKeys.

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 through db.Put, since db.Put would 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, INSERT and SELECT.
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

Building SaarDB, Part 3: Compaction

Gagandeep Singh Ahuja — Mon, 20 Jul 2026 04:25:08 +0000

In Parts 1 and 2, we built a storage engine: WAL for durability and LSM tree for efficient disk reads.

This works. But there is a problem growing quietly in the background.

Problem: SSTable Files Keep Growing

Every memtable flush creates a new SSTable file. After 10 flushes, you have 10 files. After 1000 flushes, you have 1000 files.

Now consider what happens when you serve a GET request:

GET user_42

Search SSTable 1000 (newest) → not found
Search SSTable 999           → not found
Search SSTable 998           → not found
...
Search SSTable 1             → found!

In the worst case, we search ALL 1000 files before finding the key (or confirming it doesn't exist). Each search binary searching the index block, and potentially reading a data block from disk.

This is called read amplification: the ratio of total data read to the actual data requested. We wanted 1 key-value pair. We had to touch 1000 files to find it.

As the number of SSTable files grows, read performance degrades linearly.

Problem: Duplicate Keys Waste Space

There is a second problem. Consider this write pattern:

PUT user_1 Alice     → flushed to SSTable 1
PUT user_1 Bob       → flushed to SSTable 2
PUT user_1 Charlie   → flushed to SSTable 3

Three SSTable files each contain a value for user_1. But only the newest value (Charlie in SSTable 3) matters. The entries in SSTables 1 and 2 are pure waste. They consume disk space but will never be returned to a reader.

This is called space amplification: the ratio of total storage used to the actual live data size. If a key is updated 100 times, we store 100 copies. Space amplification = 100x for that key.

Append-only writes are fast, but they accumulate garbage over time.

Solution: Merge Files Periodically

The idea is straightforward:

Read multiple SSTable files
For each key, keep only the newest value
Write a single compacted file with the deduplicated data
Delete the old files

Before compaction:
SSTable 1: [user_1=Alice, user_2=Bob]
SSTable 2: [user_1=Charlie, user_3=Dave]
SSTable 3: [user_2=Eve, user_4=Frank]

After compaction:
SSTable 5: [user_1=Charlie, user_2=Eve, user_3=Dave, user_4=Frank]

Fewer files means faster reads (less read amplification). Deduplicated keys means less wasted space (less space amplification).

But compaction introduces a new cost: write amplification. We are reading and rewriting data that has not changed. user_3=Dave and user_4=Frank were perfectly fine in their original files. We read them, wrote them again, and deleted the originals. This is extra I/O for data that was already correct.

Compaction trades write amplification for reduced read and space amplification.

This creates a three-way tension:

Read Amplification ←→ Write Amplification ←→ Space Amplification
       ↑                       ↑                      ↑
  (more files =             (compaction             (duplicates
   slower reads)             rewrites data)          waste space)

You cannot minimize all three simultaneously. Every compaction strategy is a different point in this tradeoff space.

Problem: When Do We Trigger Compaction?

If we compact after every single flush, we minimize read and space amplification but maximize write amplification because we are constantly rewriting data.

If we never compact, write amplification is zero but read and space amplification grow forever.

We need a middle ground. Think about what changes as you increase the threshold:

Threshold = 2: Almost every flush triggers compaction. You rewrite data constantly. Write amplification is very high for marginal read benefit.
Threshold = 4: You batch a few files before merging. Compaction happens less frequently, and you amortize the I/O cost across more files.
Threshold = 8 or 10: Compaction is rare, so write amplification is low. But reads degrade because you search through 8-10 files before compaction kicks in. And when compaction finally runs, it is a bigger burst of I/O.

Our implementation uses 4 as a simple learning threshold. Production systems use more sophisticated compaction policies.

Compaction Runs in the Background

Up until now, we have been discussing compaction at a conceptual level: what it does, why it helps, when to trigger it. The implementation is where things get interesting. Since compaction runs concurrently with reads and writes, we need to be careful about shared state.

Compaction is expensive. It reads all data blocks from multiple files, merges them, and writes a new file. We cannot block all reads and writes while this happens, so it runs in a background goroutine.

What is shared state?

Shared state means that multiple goroutines can read and write the same variables concurrently. Without a mutex lock, this leads to data races and unexpected behaviour.
Within compaction, the list of files, the index blocks and index offsets are all shared variables.

All of these follow the same access pattern: they are read by the Get function and written by flush during writes. We saw this in our previous blog. Now compaction adds another writer running in parallel, deleting old files and replacing them with new ones.

Side Note
go test -race ./... is a great way to identify shared state if we are not able to spot it ourselves.

Read and Write Locks

Before deep-diving into race condition and potential problems, we should be aware of the two ways of acquiring mutex locks: read (shared) locks and write (exclusive) locks.

Multiple processes can hold read locks on the same key simultaneously. But a write lock is exclusive, meaning no other process can hold any lock on that key while a write lock is active.

This is because, two readers cannot corrupt each other since neither is modifying data. But a writer must be alone because any concurrent reader would see a partially updated or inconsistent value.

Hence, from a performance perspective it is critical that we use write lock only when a write operation is being used.

Golang provides RLock and Lock in sync.Mutex package for read lock and write lock respectively. You will see more of this being used especially in the next blog where we will require acquiring locks within database rows.

Race Conditions Due To Shared State

Before diving into implementation, we need to better understand the shared state and potential race conditions that can come up.

Problem 1: New files can arrive mid-compaction

Let's say we start compacting files [1, 2, 3, 4]. While the merge is running, a new write triggers a memtable flush, creating file 5. File 5 was not part of our compaction. Compaction also created a file 6 as its output. If compaction blindly replaces the entire file list with its output, file 5 disappears and there is only a single file 6 with lost data.

Solution: Snapshot the file list before compaction starts
We snapshot the file list at the start. Snapshot here just means that we store the list of files being compacted in an in-memory variable. We also acquire a read lock while doing so.

Later, when we swap out old files and add the newly compacted file, we know exactly which files were part of compaction and should be deleted. Files that were not part of the snapshot (like file 5) are left untouched.

The entire swap operation should also be behind a write lock, since regular flushes could be happening at the same time.

Problem 2: Order of the files

In the last blog, we ensured that file names are monotonically increasing. This was important to identify the newest file. But in the above example, compaction's output file gets ID 6 (next auto-incremented), while the flush that happened during compaction created file 5. File 5 has the newest data but a lower numeric ID than file 6. File names are no longer an indicator of how new the data is.

Solution
We maintain a manifest.json file (and an in-memory reference) that tracks the expected search order. In the above case, the order should be [5, 6]: file 5 (newest data from the flush) is searched first, file 6 (compacted older data) is searched after.

Our swap function should update the file list in this order and persist it to manifest.json.

Problem 3: Two compactions can start at once

While compaction is running, a series of flushes happening in parallel can push the file count above the threshold again. Now two compactions are merging overlapping file sets.

Solution
We need a guard to ensure only one compaction runs at a time. We maintain a flag called compacting. A new compaction can only start when this flag is false.

compacting is itself a shared variable and should be read or written via a mutex lock. We set it to true when compaction starts and back to false when it ends. Our shouldRunCompaction function checks this flag in addition to checking the file count.

Problem 4: Readers might be using files we want to delete.

Let's say compaction finishes and wants to delete files 1 to 4. But a GET request is currently reading file 1's data block. If we delete the file now, that reader gets a corrupted read or a crash.

Solution
We need to make sure all in-flight reads are done before we swap out the old files. Our swap function takes a write lock before replacing the file list. Since readers hold a read lock for the duration of their Get call, the write lock blocks until every in-flight reader releases their lock. Only then does the swap proceed.

All four problems are solved with Go's sync.RWMutex and a compacting flag. Let's look at the implementation.

Implementation

When to trigger compaction

The compaction process should only start when memtable is being flushed to SSTable. We also require two additional checks: enough files to justify the cost (4 in this case), and no compaction already in progress.

Note that the go keyword in go db.ssTable.RunCompaction() in Golang is used to trigger a goroutine (a light-weight thread) in parallel in Golang.

func (db *DB) flushMemtableToSsTable() error {
    ssTableFile, err := db.ssTable.NewFile()
    if err != nil {
        return err
    }

    err = db.ssTable.Write(ssTableFile, db.memTable.Iterate)
    if db.ssTable.ShouldRunCompaction() {
        go db.ssTable.RunCompaction()
    }
    return err
}

func (st *SsTable) ShouldRunCompaction() bool {
    st.mutex.RLock()
    defer st.mutex.RUnlock()
    return !st.compacting && len(st.firstLevelFiles) >= 4
}

Compaction Logic

func (st *SsTable) RunCompaction() {
    // 1. Set compacting flag
    st.mutex.Lock()
    st.compacting = true
    st.mutex.Unlock()

    defer func() {
        st.mutex.Lock()
        st.compacting = false
        st.mutex.Unlock()
    }()

    // 2. Snapshot files to compact
    st.mutex.RLock()
    filesToCompact := make([]*os.File, len(st.firstLevelFiles))
    copy(filesToCompact, st.firstLevelFiles)
    st.mutex.RUnlock()

    // 3. Build compacted map
    compactedMap, err := st.buildCompactedMap(filesToCompact)
    if err != nil {
        return
    }

    // 4. Sort keys for ordered SSTable output
    sortedKeys := sortedKeys(compactedMap)

    // 5. Create iterator and write compacted file
    iterator := func(fn func(key, value string)) {
        for _, key := range sortedKeys {
            fn(key, compactedMap[key])
        }
    }
    compactedFile, _ := st.NewFile()
    compactedIndexOffset, compactedIndexBlock, _ := st.writeToFile(compactedFile, iterator)

    // 6. Atomic swap of file and index arrays
    st.atomicSwap(compactedFile, filesToCompact, compactedIndexBlock, compactedIndexOffset)

    // 7. Delete old files
    for _, file := range filesToCompact {
        file.Close()
        os.Remove(file.Name())
    }
}

Step 1 sets the compacting flag so that ShouldRunCompaction returns false for the duration. This prevents double compaction (problem 3).

Step 2 snapshots the file list under a read lock. This is the fix for the "new file arrives mid-compaction" problem (problem 1). Any files flushed after this point are not part of filesToCompact and will be preserved during the swap in step 6.

Steps 3-5 are the actual merge. buildCompactedMap reads all data blocks from the snapshotted files, oldest to newest. Since it iterates oldest-first, newer values for the same key naturally overwrite older ones in the map:

func (st *SsTable) buildCompactedMap(files []*os.File) (map[string]string, error) {
    compactedMap := map[string]string{}
    for _, file := range files {
        indexOffset, _ := st.getIndexOffset(file)
        buf := make([]byte, indexOffset)
        file.ReadAt(buf, 0)
        for i := 0; i < len(buf); {
            key, _ := extractValueFromSsTable(buf, i)
            i += (4 + len(key))
            value, _ := extractValueFromSsTable(buf, i)
            i += (4 + len(value))
            compactedMap[key] = value  // newer file's value overwrites older
        }
    }
    return compactedMap, nil
}

Step 6 is the most critical part. This is where we solve the concurrent reader problem (problem 4):

func (st *SsTable) atomicSwap(compactedFile *os.File, oldFiles []*os.File,
    compactedIndexBlock []indexBlockEntry, compactedIndexOffset int) {
    st.mutex.Lock()
    defer st.mutex.Unlock()

    oldFilesMap := map[string]bool{}
    for _, file := range oldFiles {
        oldFilesMap[file.Name()] = true
    }

    // Compacted file first (oldest data), then new files created during compaction
    swappedFiles := []*os.File{compactedFile}
    swappedIndexBlocks := [][]indexBlockEntry{compactedIndexBlock}
    swappedIndexOffsets := []int{compactedIndexOffset}

    for i, file := range st.firstLevelFiles {
        if !oldFilesMap[file.Name()] {
            swappedFiles = append(swappedFiles, file)
            swappedIndexBlocks = append(swappedIndexBlocks, st.indexBlocks[i])
            swappedIndexOffsets = append(swappedIndexOffsets, st.indexOffsets[i])
        }
    }

    st.firstLevelFiles = swappedFiles
    st.indexBlocks = swappedIndexBlocks
    st.manifest.FileNames = fileNames
    st.saveManifest()
}

The write lock ensures no reader is mid-read during the swap. Readers hold RLock during their entire read operation, so acquiring Lock here blocks until all in-flight reads complete. After the swap, new readers see the compacted file. Old readers have already finished.

The compacted file is placed first in the list because it contains the oldest data. Any files created during compaction (not in oldFilesMap) are appended after it. This preserves the newest-to-oldest search order that Get() relies on (solves problem 2).

After swap has successfully happened in step 6, we don't need the old files which got compacted and hence it is safe to delete them in step 7.

Benchmark Results

We benchmarked read performance with and without compaction. The setup writes repeated keys to generate duplicate entries, then the benchmark measures bulk Get operations (without compaction, with compaction):

Metric	With Compaction	Without Compaction	Improvement
Iterations	3,104	656	~4.7x more throughput
Time/op	386,022 ns	1,573,801 ns	~4.1x faster
Memory/op	203,957 B	848,196 B	~4.2x less memory
Allocs/op	3,459	13,429	~3.9x fewer allocations

The improvement is across the board. Without compaction, each read potentially searches through many more files. The extra file I/O shows up in time, memory (more buffers), and allocations.

Known Limitations

Our compaction implementation is simple and has several limitations worth acknowledging:

buildCompactedMap loads everything into memory. Production databases use streaming merge iterators that read entries from multiple files in sorted order without loading everything at once. Our approach works for small datasets but would blow up RAM with large ones.
No tombstones. We have no way to represent deletes. If a key is deleted, its old value still lives in SSTables until it happens to be overwritten. A proper implementation would write a tombstone marker that compaction can use to discard the key entirely.
No leveled compaction. We merge all L0 files into one. Production LSM trees like LevelDB and RocksDB use tiered or leveled compaction with multiple levels (L0, L1, L2...), where each level is progressively larger. This gives much better control over the amplification tradeoffs.

What's Next

We now have a complete storage engine:

WAL for durability
Memtable for fast in-memory writes
SSTables for efficient disk reads
Compaction to keep file count and duplicate keys manageable

These are the basics of a persisted key-value store. But for building a relational database, we need ACID guarantees and we have only focused on durability till now.

What happens when you need multiple writes to succeed or fail together? (Atomicity) What happens when two users read and write the same key concurrently? (Isolation)

In Part 4, we will build transactions with Two-Phase Locking: atomic multi-key writes, isolation from concurrent readers, and rollback on failure.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb

Building SaarDB, Part 2: LSM Trees

Gagandeep Singh Ahuja — Sat, 11 Jul 2026 07:16:25 +0000

In Part 1, SaarDB had two pieces:

a Write Ahead Log (WAL) for durability,
an in-memory map for serving reads and writes.

That works as a starting point, but it has limits.

The in-memory map cannot grow forever, we are bounded by RAM limitations.
Replaying a larger WAL on every startup gets slower.

So the next problem is:

How do we keep writes simple, but move older data into a searchable disk format?

Why WAL Alone Is Not Enough

WAL is fundamentally an append-only log. This is excellent for durability and sequential disk writes, but eventually it creates two major problems.

Problem 1: Repeated Keys

Imagine the following operations:

PUT user_1 Alice
PUT user_2 Bob
PUT user_1 Charlie
PUT user_1 David

The WAL now contains multiple values for the same key.

[user_1 -> Alice]
[user_2 -> Bob]
[user_1 -> Charlie]
[user_1 -> David]

But during reads, only the latest value matters.

user_1 -> David

As updates increase, the WAL keeps growing while also accumulating stale values. Even if we periodically delete stale values, another much bigger problem still remains.

Problem 2: Startup Gets Slow, and Memory Runs Out

Suppose the database has accepted millions of writes.

The WAL keeps growing on disk. The in-memory map also keeps growing because every live key-value pair is kept in RAM.

During normal reads, this is fast:

GET user_987654

The database can simply check the in-memory map.

But now imagine the process restarts.

To rebuild that in-memory map, the database has to read the WAL from the beginning and replay every write:

PUT user_1 Alice
PUT user_2 Bob
PUT user_1 Charlie
...

For a small WAL, this is fine.

For a huge WAL, startup becomes slow because the database must process a large file before it can serve reads. And after replay finishes, all live keys still need to fit in memory.

Could we avoid rebuilding the full in-memory map?

We can do that by reading directly from the WAL during GET.

But that is slow. The WAL is not sorted or indexed by key. It is just a long list of writes. So finding one key means scanning WAL entries one by one, on disk. And because older entries may be followed by newer updates for the same key, the database may need to keep scanning to know the latest value.

That turns every read into a linear search over a growing file.

So WAL alone gives us two bad choices:

Replay the entire WAL on startup and keep everything in memory.
Avoid replaying everything, but make reads slow because they must search through the WAL.

Neither works well once the data grows.

A WAL is great for remembering writes in order. It is not a good long-term format for searching keys.

So we need a second structure:

Keep recent writes in memory, but move older data to disk in a format that can be searched efficiently.

That disk format should help us quickly narrow down where a key may exist. The most common way to reduce search space efficiently is:

Binary Search

But this leads to another interesting problem.

The Real Challenge: How Do You Apply Binary Search On Disk?

Binary search is trivial in memory. Arrays support:

direct indexing,
constant-time jumps,
cheap random access.

Disk files do not naturally behave like arrays. The fundamental reason is that entries are variable-length. In an array, every element is the same size, so computing the position of the Nth element is trivial. But in a disk file storing key-value pairs, each entry can be a different size. Without reading and parsing every entry before it, there is no way to know where the Nth entry begins.

So the real challenge becomes:

How do we structure data on disk such that binary search becomes possible?

LSM (Log-Structured Merge) tree storage solves this using:

SSTables (on disk)
Memtables (in memory)

SSTable: Making Disk Reads Efficient

SSTable stands for Sorted String Table.
The key idea is simple:

Store keys on disk in sorted order to allow efficient search.

But applying binary search directly on one huge disk file is still not straightforward. So SSTables organize data carefully.

How SSTables Are Structured

Instead of storing one massive blob of sorted data, SSTables divide data into smaller blocks. Typically:

each block is bounded by size (for example ~100 KB),
keys inside each block remain sorted.

Example:

Data Block 1:
[user_1]
[user_2]
[user_3]

Data Block 2:
[user_4]
[user_5]
[user_6]

Data Block 3:
[user_7]
[user_8]
[user_9]

Notice something important:

All keys in Block 2 > all keys in Block 1
All keys in Block 3 > all keys in Block 2

This ordering enables efficient lookup.

The Index Block: The Real Enabler

Each SSTable also contains an Index Block. The index block stores:

the starting key of every data block,
the offset of that block inside the file.

Example:

user_1 -> offset 0
user_4 -> offset 1024
user_7 -> offset 2048

Now suppose we want:

GET user_5

We first load the index block into memory.

Then we binary search the block-start keys:

user_1, user_4, user_7

The largest key less than or equal to "user_5" is:

user_4

So we immediately know:

If "user_5" exists, it must exist in the block starting with "user_4".

Instead of searching the entire SSTable, we reduced the search space to a single block. This is the core idea behind SSTables.

Once the correct block is found, entries within the block are scanned sequentially till we either find the required key (key found case) or till the entire block is completely read (key not found case).

This leads us to the core lookup rule used in SSTables:

Find the largest block-start key less than or equal to the input key.

SSTable File Layout

A typical SSTable layout looks like this:

+-------------+
| Data Block 1|
+-------------+
| Data Block 2|
+-------------+
| Data Block 3|
+-------------+
| Index Block |
+-------------+
| Footer      |
+-------------+

Why Do We Need A Footer?

Interesting problem:

How do we know where the index block starts?

The index block is usually near the end of the file. But during reads, we don't want to scan the entire file just to find it.

So SSTables store a small Footer Block at the end. Index block can of variable bytes, hence there is no way to know the position of index block until we store the index block offset. On the other hand, if we store the index block offset at the start (header) or end (footer) of the file, we can easily find the index block offset. This is because header and footer are fixed positions in the file.

The footer typically contains:

index block offset,
metadata about the SSTable.

This allows readers to directly jump to the index block.

Memtable: How Data Enters the SSTable

SSTables require their keys to be sorted. So how does data get into an SSTable in sorted order?

This is where the Memtable comes in. A Memtable is simply an in-memory sorted map.

In-memory means we are bounded by RAM. We cannot keep writing to memory indefinitely. At some point, data must be written to disk.

Sorted is what makes the flush to disk efficient. Because the Memtable maintains keys in order, when it is time to write an SSTable, the data is already sorted. There is no need for an expensive sort step. The Memtable simply iterates its keys in order and writes them out sequentially.

The primary purpose of keeping the Memtable sorted is not to speed up reads. It is to make the flush to SSTable efficient.

Whenever writes arrive:

They are appended to WAL for durability.
They are inserted into Memtable for fast reads/writes.

Because Memtable is sorted, keys are always maintained in order. Example:

user_1  -> Alice
user_2  -> Bob
user_3  -> Charlie
user_4  -> David

But we cannot keep growing Memtable forever because RAM is limited. So eventually:

Memtable is flushed to disk as an SSTable.

Write Path

Now let's connect the intuition with implementation.

Challenge: How Do We Flush a Memtable to an SSTable?

When Memtable reaches a size threshold:

a new SSTable file is created,
Memtable contents are written in sorted order,
Memtable is reset.
WAL can be cleared because those key-values no longer need to be replayed from the log.

Since Memtable is already sorted, SSTable creation becomes efficient.

Writing Data Blocks

While flushing:

Memtable keys are iterated in sorted order.
Key-value pairs are written sequentially into data blocks.
Once the block size threshold is reached, a new block is started.

This is different from the Memtable threshold. The Memtable threshold decides when a flush starts. The block threshold only decides how the new SSTable file is split into smaller data blocks.

During the part 1, we saw the following encoding format while writing to disk:

[length_of_key][key][length_of_value][value]

Example:

[5][apple][2][10]

Length prefixes are important because:

keys and values are variable-sized

Indicating length of the key before the start of the key enables readers to know how many bytes to read.

While writing data blocks, we also maintain:

block starting key,
block offset.

These are later used to build the index block.

Here is the core loop from our implementation (sstable/sstable.go) that writes data blocks:

iteratorFunc(func(key, value string) {
    if blockFirstKey == "" {
        blockFirstKey = key
    }
    // [length_of_key][key][length_of_value][value]
    ssTableEntryBuf := []byte{}
    ssTableEntryBuf = binary.BigEndian.AppendUint32(ssTableEntryBuf, uint32(len(key)))
    ssTableEntryBuf = append(ssTableEntryBuf, []byte(key)...)
    ssTableEntryBuf = binary.BigEndian.AppendUint32(ssTableEntryBuf, uint32(len(value)))
    ssTableEntryBuf = append(ssTableEntryBuf, []byte(value)...)
    offset += len(ssTableEntryBuf)
    blockLength += len(ssTableEntryBuf)
    ssTableBlockBuf = append(ssTableBlockBuf, ssTableEntryBuf...)
    if blockLength > st.blockLength {
        // one data block completed
        indexBlock = append(indexBlock, indexBlockEntry{
            key:    blockFirstKey,
            offset: blockStartOffset,
        })
        file.Write(ssTableBlockBuf)

        // start new block
        blockStartOffset = offset
        blockFirstKey = ""
        blockLength = 0
        ssTableBlockBuf = []byte{}
    }
})

Notice how this single loop handles the work inside a Memtable flush: length-prefix encoding each entry, accumulating entries into a block buffer, writing the current data block to the SSTable file when the block size threshold is exceeded, and tracking the first key and offset for the index block.

Writing Strategy: Preserving Sequential Writes

One of the biggest reasons WAL performs well is that it relies on append-only sequential disk writes. SSTable creation preserves this exact property. During a Memtable flush, we create a new file and write data blocks, then the index block, then the footer. All are written sequentially, never going back to modify earlier parts of the file:

    [Data Blocks][Index Block][Footer Block]

So even though SSTables solve the problem of efficient reads, they still preserve the append-only write pattern that made WAL fast in the first place.

Writing Index Block And Footer Block

Using the same length-prefix encoding from data blocks, each index block entry stores:

the starting key of a data block,
the offset of that block within the SSTable file.

This leads to the following structure:

[length_of_start_key][start_key][offset]

Notice an important distinction here.

The start_key is variable-sized, so we prefix it with its length.

However, offset is a fixed-size unsigned 32-bit integer.

Since the size of the offset is already known during reads, we do not need to prefix it with a length.

This leads to an important encoding rule commonly used in storage systems:

Variable-sized data types usually require length prefixes.

Fixed-sized data types usually do not.

The footer block follows the same idea.

Since the footer only stores the index block offset, its structure simply becomes:

[index_offset]

During reads, this footer allows us to directly jump to the index block without scanning the entire SSTable.

Read Path

Problem: A Key Can Exist In Multiple Places

An interesting property of LSM Trees is that the same key can exist:

in Memtable,
in multiple SSTables,
and potentially with different values.

This happens because updates do not immediately overwrite older values on disk.

For example:

PUT user_1 Alice
PUT user_1 Charlie
PUT user_1 David

Older SSTables may still contain stale values:

SSTable 1 -> user_1 = Alice
SSTable 2 -> user_1 = Charlie
Memtable  -> user_1 = David

During reads, only the latest value matters.

So while serving a GET key query, the database must search in an order that guarantees the newest value is found first.

This leads to the following mental model for reads:

Memtable -> Newest SSTable -> Older SSTables

As soon as the key is found, the search stops.

Challenge: How Do We Search Efficiently Inside An SSTable?

Naively reading:

footer,
then index block,
during every query would still create repeated disk reads.

So databases usually cache:

index blocks,
metadata,
file handles in memory.

This makes reads significantly faster.

Searching Inside A File

Once the index block is in memory, searching an SSTable for a key involves four steps:

Step 1: Binary search the index block. We use the same "largest key less than or equal to the input" rule from earlier.

Step 2: Calculate the exact byte range to read. Once we know which data block to search, we need to figure out:
* where it starts and
* ends on disk.
The start offset comes directly from the matched index entry. The end offset comes from the next index entry's offset. Or if this is the last data block, the end offset is the start of the index block itself (which we already stored in memory during startup).

Step 3: Read only that one block from disk. This is the key insight. We use file.ReadAt() golang function to read exactly the bytes between the start and end offsets. We are not reading the entire file. We are not even reading from the beginning of the file. We jump directly to the relevant block.

Step 4: Sequential scan within the block. Once the block is in memory, we decode entries one by one using the length-prefix format. Which is to:
* read the key length,
* read that many bytes for the key,
* read the value length,
* read that many bytes for the value
* and then check if the key matches.

Here is the Get() function from our implementation (sstable/sstable.go):

func (st *SsTable) Get(key string) (string, error) {
    // newest file to oldest file
    for i := len(st.firstLevelFiles) - 1; i >= 0; i-- {
        file := st.firstLevelFiles[i]
        ssTableIndex := st.indexBlocks[i]
        lowerBoundSliceIndex := getLowerBound(key, ssTableIndex)
        if lowerBoundSliceIndex == -1 {
            continue
        }
        endOffset := st.indexOffsets[i]
        if lowerBoundSliceIndex < len(ssTableIndex)-1 {
            endOffset = ssTableIndex[lowerBoundSliceIndex+1].offset
        }
        value, err := st.getValueFromSsTableDataBlock(file, key,
            ssTableIndex[lowerBoundSliceIndex].offset, endOffset)
        if value == "" && err == nil {
            continue
        }
        return value, err
    }
    return "", nil
}

A few things to notice:

Reverse iteration (len - 1 down to 0): Newest files are searched first so that the most recent value for a key is found first.
getLowerBound returning -1: The key is smaller than every block-start key in this file. No point reading any block, so we continue to the next file.
endOffset calculation: If the matched block is the last data block, the end offset defaults to indexOffsets[i]: the start of the index block. Otherwise, it uses the next index entry's offset. This gives us the precise byte range for the block we need to read.
continue on empty value with no error: The key wasn't found in this file's candidate block, so we try the next (older) file.

If we exhaust all files without finding the key, Get() returns an empty string with no error. Which just means that the key simply doesn't exist in the database.

Startup: Preparing SSTables for Reads

Earlier, we saw that SSTable reads depend on two things being ready in memory for efficient reads:

open file handles,
index blocks.

We need to prepare both of them during database startup.

1. Open existing SSTable files. These files were created by earlier Memtable flushes. The database opens them in the order it needs for reads.

2. Keep file handles open. Instead of opening and closing files on every Get(), the database keeps handles ready for reuse.

3. Load index blocks into memory. For each SSTable, it reads the footer, which is exactly the last 4 bytes of the file. That footer tells us where the index block starts. Then the database reads that index block and parses it into memory.

This is the function that loads the index block for one SSTable file:

func (st *SsTable) buildIndexFromFile(file *os.File) (int, []indexBlockEntry, error) {
    info, err := os.Stat(file.Name())
    if err != nil {
        return 0, nil, err
    }
    fileSize := info.Size()
    indexOffset, err := st.getIndexOffset(file)
    if err != nil {
        return 0, nil, err
    }

    indexBlockLength := (fileSize - 4) - int64(indexOffset)
    indexBlockBuf := make([]byte, indexBlockLength)
    if _, err = file.ReadAt(indexBlockBuf, int64(indexOffset)); err != nil {
        return 0, nil, err
    }

    ssTableIndex := []indexBlockEntry{}
    for i := 0; i < int(indexBlockLength); {
        keyLengthBuf := indexBlockBuf[i : i+4]
        keyLength := binary.BigEndian.Uint32(keyLengthBuf)

        i += 4
        key := string(indexBlockBuf[i : i+int(keyLength)])

        i += int(keyLength)
        offsetBuf := indexBlockBuf[i : i+4]
        offset := binary.BigEndian.Uint32(offsetBuf)

        ssTableIndex = append(ssTableIndex, indexBlockEntry{key: key, offset: int(offset)})
        i += 4
    }
    return int(indexOffset), ssTableIndex, nil
}

Footer read: getIndexOffset reads the last 4 bytes to find where the index block starts.
Precise byte range: reads exactly the bytes between indexOffset and fileSize - 4: no more, no less.
Same length-prefix decoding: the loop mirrors the data block decoding pattern: 4-byte key length, key bytes, 4-byte offset and builds the in-memory index entry by entry.

After this, the earlier Get() implementation has everything it expects: file handles it can reuse and index blocks it can search without first scanning the SSTable file.

Replaying WAL into the Memtable

SSTables cover data that has already been flushed. But writes after the last flush still live only in the WAL.

This is the same recovery idea from Part 1. On startup, SaarDB replays WAL entries from oldest to newest.

The only difference is the target:

in Part 1, replay rebuilt a plain in-memory hashmap,
now, replay rebuilds the current Memtable.

Because the Memtable is sorted, those replayed writes are immediately ready for reads and for the next SSTable flush.

After startup, the full picture is:

recent writes: rebuilt from WAL into the Memtable,
older writes: already stored in SSTables,
SSTable index blocks: loaded into memory for reads.

What's Next

At this point, we have a working storage engine. WAL gives us durability. Memtable gives us fast in-memory writes with sorted ordering. SSTables give us efficient disk lookups using index blocks and binary search. And on startup, all the index blocks are pre-loaded so that reads only touch one candidate data block per SSTable checked.

But several problems remain:

The number of SSTable files keeps growing. Every Memtable flush creates a new file. Over time, the number of files on disk keeps increasing.
Duplicate keys accumulate across files. If a key is updated 100 times, 100 different SSTable files may contain a value for it. Only the newest matters. The rest are wasted space.
Reads slow down. Every Get() call may need to search through more and more files before finding the key (or confirming it doesn't exist).
Deletes don't exist yet. In an append-only system, what does "delete" even mean? We can't go back and erase a key from an already-written SSTable file.

In upcoming parts, we will cover:

Compaction: to be covered in part 3: merging multiple SSTables into fewer, larger ones, eliminating duplicates and reclaiming space.
Tombstones: a way to represent deletes in an append-only world.
Bloom filters: a probabilistic data structure that lets us skip SSTable files that definitely don't contain a key, without reading anything from them.
Tuning flush size and block size: how large should the Memtable grow before flushing? How large should each data block be? These are not arbitrary choices and involve careful tradeoffs.

Building SaarDB, Part 1: Write-Ahead Log (WAL)

Gagandeep Singh Ahuja — Sat, 04 Jul 2026 17:08:25 +0000

SaarDB is a learning project: build a relational database from first principles in Go, one layer at a time.

The goal is not to build a production database. The goal is to make database internals feel intuitive by building the core ideas directly and explaining the tradeoffs along the way.

When we think of a relational database, it is tempting to start with SQL parsing, tables, data types, and query execution. But that starts with the interface before understanding the storage layer underneath it.

So Part 1 starts smaller: a key-value store. From there, we will hit the first serious database problem: how do we make writes survive a crash?

Where to Start: Why a Key-Value Store?

The initial instinct may be to start with the query layer. This includes SQL parsing, operations like CREATE TABLE, multiple data types, and so on. But the storage layer is the foundation beneath all of that.

The key insight is that:

A key-value store can be extended to support everything a relational database needs.

This can feel surprising at first. How can a relational database, with tables and rows and SQL, start from something as small as key-value operations?

The reason for this is that every SQL operation can be mapped to a key-value operation. For example:

CREATE TABLE payments (...) can be mapped to storing the schema as a value under key _schema:payments. The value can be stored in a serialized manner and can be deserialized when we need to read it.
INSERT INTO payments VALUES (1, 500, 'pending') can be mapped to a PUT operation: PUT payments:1 <serialized_row>. This design also ensures efficient lookup by primary key.

If this mapping still feels abstract, that is fine. Later posts will come back to this when we build more of the SQL layer on top of the storage engine.

Starting Simple: An In-Memory Key-Value Store

Whatever problem we are solving, we start with the simplest thing that works.

Correctness before performance. Performance before scale.

The simplest database is a hashmap in memory to support GET and PUT commands. We will build a REPL (Read-Eval-Print-Loop) around it so users can interact via the command line.

Building the REPL

A REPL is just a loop: accept input, process it, print the result, repeat. In Go, bufio.Scanner reads from STDIN line by line:

func main() {
    db := map[string]string{}
    scanner := bufio.NewScanner(os.Stdin)
    for scanner.Scan() {
        line := scanner.Text()
        args := strings.SplitN(line, " ", 3)
        cmd := args[0]
        switch cmd {
        case "GET":
            fmt.Println(db[args[1]])
        case "PUT":
            db[args[1]] = args[2]
        case "EXIT":
            return
        default:
            fmt.Println("command not supported")
        }
    }
}

This works. We can store and retrieve data. But there is an obvious problem.

The First Problem: Memory Is Volatile

If we kill the process and restart it, everything is gone. The hashmap lived in memory and memory does not survive process restarts.

How do we make data survive crashes?

This is the problem of durability: guaranteeing that once a write succeeds, the data is permanently saved.

The answer is straightforward: write to disk. Memory is volatile. Disk is not. But this raises a new question.

Choosing the Write Order

For every PUT, we need two updates:

Write to disk so the data survives a crash.
Write to the in-memory map so reads are fast.

The order matters.

If we update memory first, there is a dangerous window where memory contains data that disk does not. If the process crashes in that window, the update disappears after restart.

Even without a crash, if the disk write fails after the memory update, we now have to undo the memory change. That makes the write path more complicated.

If we write to disk first, the rule is simpler: only update memory after the durable write succeeds.

So the rule is: write to disk first, then update memory.

Why Append-Only Writes Help

There is a golden rule for database performance:

Sequential writes are significantly faster than random writes.

Let's go over what sequential and random writes actually are and why that is the case.

Sequential write means that while writing data, we write in such a way that the data is stored in adjacent blocks on the storage drive.

On the other hand, random write means that the data is written in a scattered way across non-contiguous locations.

For HDDs, random writes are slow because the disk head has to physically jump around. SSDs do not have a moving head, but the file-write pattern still matters.

Consider two updates to the same key:

PUT user_1 Alice
PUT user_1 Bob

Suppose the file already contains:

[user_1 = Alice]

Now we want to update user_1 to Bob. If we overwrite the old value in place, we first have to find the old bytes, check whether the new value fits in the same space, and handle the case where it does not.

A simpler approach is to never rewrite old bytes. Just append the new value to the end of the file and treat the latest value as the source of truth:

[user_1 = Alice]
[user_1 = Bob]

The fastest possible write pattern is append-only: always add data to the end of the file, never go back to modify earlier data.

Yes, we store the key twice. That is wasted space. But the write is fast, and we know the latest value is always at the end. We will deal with the duplication problem later.

This append-only file is called a Write-Ahead Log (WAL).

Encoding WAL Entries

We need to write a command like PUT user_1 Alice to the file. The naive approach is to use a separator like a space or newline:

PUT user_1 Alice\n
PUT user_2 Bob\n

This looks readable, but it hides two different problems.

Problem 1: Where Does One WAL Record End?

Suppose the value contains a newline:

PUT user_1 Alice
Bob

If our WAL reader treats newline as the end of an entry, it will think Bob is a separate command. So the first thing we need is a way to say: this WAL record is exactly N bytes long.

The solution is a length prefix around the whole WAL payload:

[wal_payload_length][wal_payload]

Here is a concrete byte-level example. Suppose the WAL payload is "PUT a 1" (7 bytes):

[00 00 00 07][50 55 54 20 61 20 31]
 └─ length ─┘└──── WAL payload ────┘
     = 7        P  U  T     a     1

The WAL reader knows: read 4 bytes for the length (7), then read exactly 7 bytes for the payload. This removes ambiguity about where this WAL record ends.

In plain English: the first 4 bytes say, "the next chunk is 7 bytes long."

That solves record boundaries. But it does not yet solve how to parse the command inside the payload.

Problem 2: How Do We Parse the Command Inside the Payload?

If the payload itself is still a string like this:

PUT user_1 Alice Bob

we are back to the same problem. Is the value Alice? Or is the value Alice Bob?

So the payload also needs length prefixes for its internal fields:

[cmd_len][cmd][key_len][key][value_len][value]

For example, PUT user_1 "Alice Bob" becomes:

[3][PUT][6][user_1][9][Alice Bob]

The exact bytes use 4-byte integers for the lengths, but conceptually this is the format. First we read the command, then the key, then the value. Spaces and newlines inside the value are just bytes; they do not confuse the parser.

In Go, the write flow looks like:

func appendLengthPrefixedString(buf []byte, value string) []byte {
    buf = binary.BigEndian.AppendUint32(buf, uint32(len(value)))
    buf = append(buf, []byte(value)...)
    return buf
}

func serialisePutCommand(key, value string) []byte {
    buf := []byte{}
    buf = appendLengthPrefixedString(buf, "PUT")
    buf = appendLengthPrefixedString(buf, key)
    buf = appendLengthPrefixedString(buf, value)
    return buf
}

Think of buf as a growing byte slice: a resizable list of bytes. For each field, we first append its 4-byte length, then append the actual bytes.

And for reading one length-prefixed field:

func readLengthPrefixedString(buf []byte, offset *int) (string, error) {
    valueLen := binary.BigEndian.Uint32(buf[*offset : *offset+4])
    *offset += 4

    value := string(buf[*offset : *offset+int(valueLen)])
    *offset += int(valueLen)
    return value, nil
}

Here, offset is just a cursor. It remembers where the next field starts inside the byte slice.

The important idea is that we use length prefixes at two levels:

The WAL layer frames the whole record.
The database command layer frames the fields inside that record.

This pattern of [length][data] shows up everywhere in storage systems. We will use it again in future blogs.

Handling Partial Writes

Let's consider this scenario:

We start writing a 100-byte payload
The OS writes the 4-byte length header: [00 00 00 64]
The process crashes after writing only 50 bytes of the payload

The file now contains:

...[valid entries]...[00 00 00 64][50 bytes of partial data]

This is where the length prefix helps. Because the payload length is written before the payload, the reader knows exactly how many bytes to expect:

[wal_payload_length][wal_payload]

The writer side looks like this:

func (w *Wal) WriteEntry(payload []byte) error {
    buf := make([]byte, 4+len(payload))
    binary.BigEndian.PutUint32(buf[0:4], uint32(len(payload)))
    copy(buf[4:], payload)

    _, err := w.file.Write(buf)
    return err
}

Here, buf[0:4] stores the length header. buf[4:] stores the payload right after it.

The reader uses the length to read exactly the expected number of bytes:

func (w *Wal) ReadEntry() ([]byte, error) {
    lengthBuf := make([]byte, 4)
    _, err := io.ReadFull(w.file, lengthBuf)
    if err == io.EOF {
        return nil, io.EOF
    }
    if err == io.ErrUnexpectedEOF {
        return nil, errors.New("partial write: incomplete length")
    }
    if err != nil {
        return nil, err
    }

    payloadLength := binary.BigEndian.Uint32(lengthBuf)

    payload := make([]byte, payloadLength)
    _, err = io.ReadFull(w.file, payload)
    if err == io.ErrUnexpectedEOF {
        return nil, errors.New("partial write: incomplete payload")
    }
    if err != nil {
        return nil, err
    }

    return payload, nil
}

If the length says 100 bytes but only 50 bytes exist, io.ReadFull returns io.ErrUnexpectedEOF. That tells us the last WAL record was only partially written.

Detecting Corrupted Bytes

A partial write is about missing bytes.

A corrupted write is different: all bytes may be present, but some bytes are wrong. This is not just a theory. Disks, SSDs, filesystems, OS crashes, power loss, and storage controllers can all fail in ways that leave bad bytes behind.

Most writes work fine. But databases are built for the cases where bytes are missing or wrong. The length prefix catches missing bytes. It does not prove that the bytes we read are the correct bytes.

How does the reader know the bytes are correct?

A checksum solves this. A checksum is a small fingerprint computed from data. If the payload bytes are the same, the checksum will be the same. If even one byte changes accidentally, the checksum will most likely change.

For example, suppose the writer stores this payload:

PUT user_1 Alice

The writer computes a checksum from these bytes and stores it next to the payload. Later, if the payload somehow becomes:

PUT user_1 Aljce

the length may still be valid, but the checksum will likely be different. That tells us the payload bytes are not trustworthy.

Now we extend the same WAL record by adding a 4-byte checksum at the end:

[wal_payload_length][wal_payload][checksum]

This problem is commonly solved in storage systems using CRC32, which is a fast checksum algorithm. The writer computes the CRC32 checksum over the payload bytes and appends it. The reader reads the payload, independently computes the checksum, and compares it with the stored checksum.

On the writer side, the length and payload logic stays the same. We only add space for the checksum, compute it from the payload, and append it:

func (w *Wal) WriteEntry(payload []byte) error {
    buf := make([]byte, 4+len(payload)+4)

    // ...same length and payload writes as before...
    binary.BigEndian.PutUint32(buf[0:4], uint32(len(payload)))
    copy(buf[4:4+len(payload)], payload)

    // New part: append checksum after the payload.
    checksum := crc32.ChecksumIEEE(payload)
    binary.BigEndian.PutUint32(buf[4+len(payload):], checksum)

    _, err := w.file.Write(buf)
    return err
}

buf[4+len(payload):] means "start writing after the 4-byte length header and the payload." That is where the checksum goes.

With length prefixes and checksums together, the reader can handle these failure modes:

Incomplete length (less than 4 bytes written): io.ReadFull returns io.ErrUnexpectedEOF. We know this is a partial write.
Incomplete payload: Length says 100 bytes but only 50 exist. Same error.
Incomplete checksum: Payload looks complete but checksum is truncated.
Corrupted data: All bytes present but checksum does not match. Data is bad.

After the reader has already read the length and payload, the checksum check is the extra part:

// ...same length and payload reads as before...

checksumBuf := make([]byte, 4)
_, err = io.ReadFull(w.file, checksumBuf)
if err == io.ErrUnexpectedEOF {
    return nil, errors.New("partial write: incomplete checksum")
}
if err != nil {
    return nil, err
}

storedChecksum := binary.BigEndian.Uint32(checksumBuf)
computedChecksum := crc32.ChecksumIEEE(payload)
if storedChecksum != computedChecksum {
    return nil, errors.New("corrupt: checksum mismatch")
}

return payload, nil

The intended recovery strategy is: if we detect a partial write at the end of the file, we can truncate it because it was the last write that did not complete. In the current implementation, we detect and return the error first; truncating the partial tail is a follow-up cleanup. On the other hand, if corruption is detected mid-file, that is a more serious problem (bit rot, hardware failure) that requires manual intervention.

Making Writes Actually Reach Disk

There is one more subtlety. Consider this code:

file.Write(buf)
// process reports "write successful"
// power goes out

Did the data actually reach the disk? No, not necessarily.

When we call file.Write(), the OS copies the data into a page cache (a buffer in RAM). The OS returns success immediately. It will eventually flush the page cache to the physical disk, but "eventually" might be seconds or minutes later. If power fails before that flush, the data is gone despite Write() returning success.

file.Write() guarantees the data reached the OS. It does not guarantee the data reached the disk.

The solution is fsync:

file.Write(buf)
file.Sync() // forces OS to flush page cache to physical disk

file.Sync() (which calls the fsync system call) blocks until the OS confirms the data is on the physical storage device. Only after Sync() returns, we can be confident that the data is durable.

There is a tradeoff though. fsync is expensive. On an HDD, it can take 5-10ms. On an SSD, it is faster but still significant. Calling it after every single write gives maximum durability but reduces throughput. Production databases like PostgreSQL batch multiple writes before a single fsync, trading a small window of vulnerability for much higher throughput.

For our database, we call file.Sync() after every WAL entry. This means maximum safety and simpler reasoning but with performance tradeoff.

The Write Path

Now we can put it all together. When a user calls PUT key value:

Serialize the command payload into bytes: [cmd_len][cmd][key_len][key][value_len][value]
Append it as a WAL record: [wal_payload_length][wal_payload][checksum] and fsync
Insert into the in-memory hashmap

func (db *DB) Put(key, value string) error {
    // Step 1-2: Write to WAL (disk first)
    walPayload := serialisePutCommand(key, value)
    if err := db.wal.WriteEntry(walPayload); err != nil {
        return err
    }
    // Step 3: Write to memory
    db.data[key] = value
    return nil
}

The WAL write happens first (disk before memory). If it fails, we return an error so that the user knows the write did not succeed.
If the process crashes after the WAL write but before the in-memory map is updated, the data is safe on disk and will be recovered on restart.

The Read Path

Reads are simple right now. We just look up the in-memory map:

func (db *DB) Get(key string) (string, error) {
    value, ok := db.data[key]
    if !ok {
        return "", nil // key not found
    }
    return value, nil
}

The WAL is never read during normal operation. It is purely a durability mechanism for writes. The in-memory map serves all reads.

Application Init: Rebuilding State from WAL

When the database process starts, the in-memory hashmap is empty. But the WAL on disk contains every write since the last checkpoint. We need to replay it:

func (db *DB) buildInMemoryMapFromWal() (map[string]string, error) {
    data := map[string]string{}
    for {
        payload, err := db.wal.ReadEntry()
        if err == io.EOF {
            return data, nil // reached end of WAL
        }
        if err != nil {
            return nil, err // corruption or partial write
        }

        offset := 0
        cmd, err := readLengthPrefixedString(payload, &offset)
        if err != nil {
            return nil, err
        }
        if cmd == "PUT" {
            key, value, err := deserialisePutCommand(payload, &offset)
            if err != nil {
                return nil, err
            }
            data[key] = value
        }
    }
}

This is the only time the WAL is read. The loop reads entries from oldest to newest.
For duplicate keys, the newest value naturally overwrites the older one in the hashmap, which is exactly the behavior we want.

After replay, the in-memory map contains the same state as before the crash. The database is ready to serve reads.

The full initialization sequence:

Open WAL file
Replay all WAL entries into a fresh in-memory map
Start accepting reads and writes

What's Next

WAL gives us durability and fast writes (append-only, sequential). Reads go through the in-memory hashmap.

But we run into multiple issues at scale.

The WAL grows forever. Every update to the same key adds another entry, leading to a lot of redundant data.
An in-memory hashmap gives us O(1) lookups but cannot scale beyond RAM.
Replaying the entire WAL during application startup becomes painfully slow.

In Part 2, we will introduce LSM trees, which solve these problems by adding sorted in-memory structures and searchable disk files.

The code for SaarDB is available here:
GitHub: https://github.com/gagandeepahuja09/saardb