An index in memory

Goal

Understand Stash's index, how opening the log rebuilds it, and what that costs as the log grows.

Where is acorn:1?

To read acorn:1 from the log alone, you would scan every record and keep the last match. Stash keeps an index instead: a dictionary from key to the position and length of its latest value. A read is one seek and one read, from lab/stash/store.py:

    def get(self, key: str) -> str | None:
        where = self.index.get(key)
        if where is None:
            return None
        self.file.seek(where[0])
        return self.file.read(where[1]).decode()

This design has a name: Bitcask. It was built for the Riak database. Writes append to the log; reads use the index; all keys live in memory.

The index is rebuilt on open

The index lives only in memory, so every open replays the whole log. Each record moves its key to the new position, and a tombstone removes the key. Fill a log with a lot of history and time it:

uv run python -m stash fill data/garden.stash 100000
uv run python -m stash stats data/garden.stash

wrote 100,000 values over 20 keys
keys      20
size      5,049,235 bytes
garbage   5,048,208 bytes (100%)
opened in 0.152 s

100,000 records, 20 live keys. Opening took 0.15 seconds on the laptop this was written on; yours will differ. With a million records over 100,000 keys, it took 2.0 seconds. Startup time grows with the log, not with the number of keys. Chapter 06 fixes that.

The garbage line counts bytes no key points at any more: old values and tombstones. It rounds to 100% here, because only the last of 5,000 values per key still counts.

Check it works

• stats shows 20 keys and about 5 MB for 100,000 writes.
• You can say why opening gets slower as the log grows, even with the same number of keys.

Exercise

Write a scan_get(path, key) function that finds a value by reading the whole log with record.read, with no index. Time it against Stash.get on data/garden.stash, using time.perf_counter. How many times faster is the index?

More to try

• Bitcask writes a hint file next to each finished log: just the keys and positions, no values. Opening reads the hint file instead of the log. Sketch what Stash's hint file would contain.
• What happens to the index if two processes open the same file and both write? Stash does not guard against it. How would you?