Building a Key-Value Store from Scratch

A key-value store saves a value under a key. It also provides a way to read the value later. A file and two operations, Put and Get, are enough to begin.

That simple idea raises more questions as the file grows. How can a key be found without reading every record? What happens when a new value is written for the same key? How can old values be removed? These questions shaped the Go project db_engine.

The repository has two storage paths. One uses an append-only log and segments. The other uses a memtable and sorted files. They are experiments, not one complete database. Each part appears when the earlier design needs it. The small examples show the idea. Code examples and GitHub links show parts of the implementation.

Contents

• Start with one file
• Add an index
• Change the record format
• Split the log into segments
• Remove old values with compaction
• Keep new writes in a sorted memtable
• Find a key inside an SSTable
• Merge SSTables
• Current state

Start with one file

The first Put can add a line to the end of a file:

bytes := []byte(key + "," + string(val) + "\n")
n, err := file.Write(bytes)

After two writes, data.log could contain:

color,blue
size,large

Adding a new record does not change the old data. Finding the end of an append-only file takes O(1) work with append mode. The write still has to transfer all L bytes of a record, so its byte cost is O(L). It does not depend on the number of older records.

The next operation is:

Get("size")

The simple answer is to read the file from the start and compare each key. A missing key requires a read of the whole file. With N records, that takes O(N) comparisons, plus the work of reading the bytes.

scanner := bufio.NewScanner(file)

for scanner.Scan() {
    parts := strings.SplitN(scanner.Text(), ",", 2)
    if len(parts) == 2 && parts[0] == key {
        return parts[1], nil
    }
}

This example has another problem. Suppose a new color is written:

color,blue
size,large
color,green

The scan above returns blue. But green is the latest value. Without a better way to find it, the scan must continue to the end and remember the last match. Every read can become slow.

Add an index

An index tells the reader where data is stored. When a record is added, its starting position in the file is known. This position is a byte offset. The example records start here:

0:  color,blue\n
11: size,large\n
22: color,green\n

A map can save the latest offset for each key:

index[key] = offset

After the last write, the offset for color is 22. Get can look up that offset, move to it in the file, and read the record. A hash map lookup takes O(1) time on average. Reading the value still takes time based on its size. The map uses O(K) memory for K keys.

The index is only in memory. When the program restarts, it must read the stored records to build the index again. That takes O(N) work for N records. The repository has a function to build an index for a segment, but there is no startup flow that runs it for all files.

The map points to the latest value in one file. Old values still use disk space. Compaction will address that problem later.

Change the record format

The line format is easy to read, but it has limits. What if a value contains a comma or a newline? Those characters would need escaping rules. Before more files are created and later merged, the reader needs a clear way to find where each record ends.

A length-prefixed record puts the size of each field before the data. The binary format uses four bytes for the key length and four bytes for the value length:

┌──────────────┬──────────────┬───────────┬─────────────┐
│ key length   │ value length │ key bytes │ value bytes │
│ 4 bytes      │ 4 bytes      │ variable  │ variable    │
└──────────────┴──────────────┴───────────┴─────────────┘

The encoder writes the two lengths and then copies the bytes:

bytes := make([]byte, 8+keyLen+valLen)

binary.BigEndian.PutUint32(bytes[0:4], uint32(keyLen))
binary.BigEndian.PutUint32(bytes[4:8], uint32(valLen))

copy(bytes[8:8+keyLen], key)
copy(bytes[8+keyLen:], val)

For color=blue, the key has 5 bytes and the value has 4 bytes. The full record has 17 bytes: 8 bytes for the header and 9 bytes for the data.

To read it, the decoder reads the header first. Then it knows how many more bytes to read. It also knows where the next record starts:

keyLen := binary.BigEndian.Uint32(header[0:4])
valLen := binary.BigEndian.Uint32(header[4:8])

totalLen := int64(keyLen) + int64(valLen)
data := make([]byte, totalLen)
_, err = file.ReadAt(data, offset+8)

key = data[:keyLen]
val = data[keyLen:]
nextOffset = offset + 8 + totalLen

Encoding or decoding L bytes takes O(L) time. From here on, the files contain binary records. The text examples below only make them easier to see.

Split the log into segments

One file can grow for as long as the program writes to it. The log can instead be split into segments. A segment is one file that holds part of the log. The active file is called write.bin. When it becomes large enough, the writer gives it a new name, marks it read-only, and starts another write.bin.

The segment writer uses a 400 KiB threshold. Its rollover code includes:

if (info.Size() + (int64(len(key)) + int64(len(val)))) >= THRESHOLD {
    segmentName := filepath.Join(storage, newSegmentFileName())

    if err := os.Chmod(writableSegmentFile, 0444); err != nil {
        return -1, err
    }
    if err := os.Rename(writableSegmentFile, segmentName); err != nil {
        return -1, err
    }

    return Put(key, val)
}

After a rollover, the files might hold these values:

older segment: color=blue, size=large
write.bin:     color=green

An offset is no longer enough to find a value. Offset 0 exists in every file. The index must store both the segment and the offset. The hash index keeps a key-to-offset map for each segment:

val, _ := hi.indexes.LoadOrStore(segment, &sync.Map{})
segmentMap := val.(*sync.Map)
segmentMap.Store(key, offset)

A normal append still takes O(1) work to find the end and transfers O(L) bytes for a record of L bytes. A rollover renames a file; it does not copy all its records. But finding a key may now check as many as S segment maps for S segments. The maps use O(E) memory for E key-and-segment entries.

There is a problem in this implementation: it does not search the segment maps from newest to oldest. If the same key exists in two files, it may choose the older value. The later sections explain the design, but the current code still needs this lookup fixed.

Remove old values with compaction

Segments stop one file from growing forever. They do not stop the total data from growing. Every update leaves an old record behind. Replacement files should contain only the latest values.

This process is compaction. It reads old, read-only segments, keeps the latest value for each key, and writes new segments. It leaves the active write.bin alone because that file can still change.

Before: old segment = color=blue
        new segment = color=green

After:  replacement segment = color=green

The segment compactor reads the older segments first. A map keeps the last value seen for each key:

for {
    key, val, nextOffset, err := format.DecodeBinary(file, offset)
    if err != nil {
        if err == io.EOF {
            break
        }
        return err
    }

    latest[string(key)] = val
    offset = nextOffset
}

The compactor writes its results to temporary files, flushes and syncs them, and then renames them. For N input records and K keys that remain, reading and rewriting take O(N + K) record operations. The map needs O(K) memory. Sorting S segment files by age takes O(S log S) comparisons. These costs leave out the time to read and write the bytes.

The map makes this easy to understand, but it may use a lot of memory when there are many different keys. This memory cost creates a reason to consider another way to store data.

Keep new writes in a sorted memtable

If a file is sorted by key, a reader can search it with a smaller index. For example:

Write order: zebra, apple, mango
File order:  apple, mango, zebra

Sorting the file after every write would be expensive. Recent writes can first stay in memory. This structure is a memtable. When it is full, its keys are written to disk in order.

The memtable uses a red-black tree. This kind of tree keeps keys sorted as they are added. Finding or replacing a key takes O(log M) time for M keys in the tree. When the tracked size reaches 4 MiB, the code writes the tree to a sorted file and starts a new tree:

if memtable.SizeBytes() >= THRESHOLD {
    sstable := sstable.Construct(memtable.tree)

    if err := sstable.Create(); err != nil {
        return err
    }

    memtable.totalBytes = 0
    memtable.tree = redblacktree.NewWith(byteComparator)
}

The sorted file is an SSTable, short for sorted string table. It does not change after it is written. Writing M already sorted memtable entries takes O(M) record operations, plus the bytes written.

Writing to a memtable, flushing it to SSTables, and later merging those SSTables is the basic idea of an LSM tree (log-structured merge tree). This path is separate from the segment path. The repository does not join them into one engine.

Find a key inside an SSTable

A sorted file helps, but the reader still needs to know where to start. Reading every record would return to a slow O(N) scan.

The SSTable writer puts nearby records into blocks. A block is a group of records stored together. The block code uses a 16 KiB threshold.

For every block, the writer saves its first key and its file offset. These entries form a sparse index: one index entry per block, not one per record. The writer puts the index after the data blocks. Then it adds an eight-byte footer that says where the index starts:

data blocks → block index → index-offset footer

The writer records a block’s first key when it writes that block:

if block.GetSize() >= block.GetThreshold() {
    n, err := writer.Write(block.GetBlock())
    if err != nil {
        return fmt.Errorf("error writing block: %v", err)
    }

    indexBlock.Append(index.Index{Key: block.GetFirstKey(), Offset: offset})

    block.Reset()
    offset += int64(n)
    block.SetOffset(offset)
}

Imagine this index:

apple → block 1
mango → block 2
zebra → block 3

For orange, the block that starts with mango is the candidate. The key is after mango and before zebra. The index search uses binary search to find that block:

for lo <= hi {
    mid := (lo + hi) / 2
    cmp := bytes.Compare(block.indexes[mid].Key, key)

    if cmp == 0 {
        return true, block.indexes[mid].Offset
    } else if cmp < 0 {
        lo = mid + 1
    } else {
        hi = mid - 1
    }
}

if hi >= 0 {
    return false, block.indexes[hi].Offset
}

If the index is already in memory, choosing a block takes O(log B) comparisons for B blocks. Scanning up to R records inside that block takes O(R) comparisons. The sparse index needs O(B) entries.

This is the intended search. The current Search method reads the index on every call, which would add O(B) work. Its index parsing and stopping condition still need fixes, so the full lookup does not yet work as described.

Merge SSTables

Each memtable flush makes another SSTable. Over time, the same key can appear in several tables. A newer table should win:

Older table:  color=blue, size=large
Newer table:  color=green
Merged table: color=green, size=large

Because both input files are sorted, a merge can compare their next keys. When the keys match, it should write the newer value and move forward in both files. A correct two-table merge examines at most N₁ + N₂ input records, so it takes O(N₁ + N₂) record comparisons, plus output work.

The SSTable compactor attempts this merge. Its equal-key branch chooses the newer value, but advances only the newer file:

case 0:
    key = key2
    val = val2
    r = nextOffset2

The old record can then appear again. The code also writes some records twice. This part needs correction and tests before it can reliably remove old values. The O(N₁ + N₂) cost describes the intended algorithm, not a verified result from this code.

Current state

The project currently contains an append-only log, an in-memory index, binary records, segments, compaction, a sorted memtable, and indexed SSTables. These parts are still separate experiments. The database is not complete yet; the parts will be connected and the remaining work finished in the future.