This post is part of an ongoing series building Soil, a file-based, transactional object database for Pharo, from the ground up — one real mechanism at a time.

Read the whole Soil series →

Soil: indexes on disk, B-tree and skip list

The identity post ended with an object that can be found by its id: two bytes of segment, six bytes of index, one lookup in the object index file, and the position in the heap is known. That answers "where is object 42". It does not answer the question every application asks first: "which object belongs to this name". Something has to map a key to an object id, keep that mapping sorted so ranges can be read, and survive on disk without being loaded as a whole. That something is an index, and Soil has two of them: a B-tree and a skip list.

This post is about how they sit on disk. Transactions come later, so everything here is a single writer on a single index file. The interesting part is that both trees share one page format and one API, and where they do not, the differences are small and deliberate.

A key is a number

Before any tree, there is the key. Whatever an application uses to look something up, by the time it reaches an index it is an integer:

"ByteArray"
asIndexKeyOfSize: anInteger
    ^ (self asByteArrayOfSize: anInteger) asInteger

"String"
asIndexKeyOfSize: anInteger
    ^ self asByteArray asIndexKeyOfSize: anInteger

The bytes of the key are padded on the left up to the key size of the index and read as one big-endian number. That makes comparing keys trivial and fast, and it is the reason a page can store keys at a fixed width. It also has a consequence that surprises people once:

key as an index key of size 8
'b' 98
'aa' 24929
'Zoe' 5926757
'Alice' 280991720293
'Zimmer' 99408853951858

A longer string is a bigger number than any shorter one, so the length decides before the content does. Putting those five strings into an index and reading the values back gives 'b', 'aa', 'Zoe', 'Alice', 'Zimmer', which is order by length and not alphabetical. The index is perfectly sorted, just by a different rule than a person would guess. A test that compares values against a hand-sorted list is really testing how long its test data is, and passes by accident as long as the names have the same length. Looking a key up is always right; relying on the order of keys of different lengths is not.

One page format, two trees

An index file is a sequence of pages of 4 KB. That number is not arbitrary, 4 KB is the unit an operating system works in. File systems hand out disk space in blocks of that size, the memory manager caches file contents in pages of that size, and the disk underneath reads and writes whole blocks and nothing smaller. Changing one byte of a file makes the OS read and write the entire block around it. Systems are built this way because every disk access has a fixed cost no matter how little it transfers, so moving data in uniform chunks is cheaper than in bytes, and fixed-size chunks are easy to track, cache and reuse. An index that uses pages of exactly this size gets a simple correspondence: one page of the index is one block for the OS, so reading it is one access and writing it leaves its neighbours alone.

That only works if the two grids line up, and in Soil they do by construction. Page numbers start at 1, and a page sits at a position that is a multiple of the page size:

"SoilPagedFileIndexStore"
filePageSize
    "most OSses use a file page size of 4k today"
    ^ 4096

positionOfPageIndex: anInteger
    ^ (anInteger - 1) * self filePageSize

Every page therefore starts exactly on a block boundary of the file and never straddles two of them. Soil keeps the pages it has touched in memory, marks the ones it changed, and writes only those, one page at a time, at its own position and with the bytes it actually uses. A page that is not full is therefore shorter than its slot, and the last page makes the file end early, but a page never leaves its slot. The OS below does the same with its own cache in the same units. One changed Soil page is one changed OS page, so nothing has to read a neighbour just to write around it, and the OS can cache, evict and write back the pages of an index exactly the way Soil thinks about them. Three columns: the pages of the Soil index file on the left, the OS pages that cache them in the middle, the disk on the right. Page n starts at byte (n - 1) x 4096, and each index page maps to exactly one OS page

The first byte of every page, its page code, says what kind of page it is, and that is all SoilIndexPage class>>readPageClassFrom: needs to turn bytes into the right class:

code page job
1 SoilSkipListHeaderPage skip list header and entry point
2 SoilSkipListDataPage skip list node holding items
3 SoilBTreeHeaderPage B-tree header, and the first leaf
4 SoilBTreeDataPage B-tree leaf
5 SoilBTreeIndexPage B-tree inner node
6 SoilBTreeRootPage B-tree root
7 SoilFreePage list of recycled pages

SoilIndex is the abstract class on top, with SoilBTree and SoilSkipList as the two implementations and a dictionary style API: a key that is an integer, a value that is a byte array. Everything that reads or iterates goes through an iterator, so code that does not care which tree is underneath does not have to. The two even agree on the setup: maxLevel: exists on the base class as a no-op, so a skip list parameter does not break when someone switches to a B-tree. Pages that are no longer needed are not given back to the file system. They go on a free list and are reused by the next allocation.

What makes the two different is how pages find each other.

A skip list whose nodes are pages

A classic skip list is a linked list with express lanes: every node has a random height, and a search walks right along the highest lane as far as it can, drops one lane, and repeats. Soil's skip list is exactly that, except that a node is not one entry but one page full of sorted items. A page has a level, chosen once when the page is created by flipping a coin:

"SoilSkipListPage"
initializeLevel: maxLevel
    | promote level |
    level := 1.
    promote := true.
    [ (level < maxLevel) and: [ promote ] ] whileTrue: [
        level := level + 1.
        promote := self class random next > 0.5 ].
    left := Array new: level withAll: 0.
    right := Array new: level withAll: 0.

Each page carries a left and a right array with one page offset per level it takes part in. Page offsets are four bytes, which caps an index at about 17 TB with 4 KB pages. A skip list whose nodes are pages: the header page with eight levels, data pages of one to eight levels each holding sorted items, and the lookup of key 75 as a dashed arrow that moves right on a lane, drops a level, and ends on the page that holds the key

The picture shows a lookup of key 75. It starts at the header page and works its way down:

"SoilSkipListIterator"
findPageFor: indexKey
    | pageIndex candidatePage |
    currentPage := index headerPage.
    levels size to: 1 by: -1 do: [ :level |
        [
            pageIndex := currentPage rightAt: level.
            (pageIndex > 0) and: [
                candidatePage := self pageAt: pageIndex.
                candidatePage smallestKey <= indexKey ] ]
                    whileTrue: [ currentPage := candidatePage ].
        self atLevel: level put: currentPage ].
    currentPageIndex := 0.
    ^ currentPage

On every level it moves right while the next page still starts at or below the key, and remembers where it stopped. When it reaches level one, currentPage is the page the key belongs on, and levels holds, for every level, the last page it passed. That list is what an insert needs to wire in a new page.

A page that is full has to be split, and here the skip list has a small optimization that matters more than it looks:

"SoilBasicSkipList"
splitPage: aIterator forKey: aKey
    | newPage currentPage |
    currentPage := aIterator currentPage.
    newPage := (currentPage isLastPage and: [ currentPage lastKey < aKey ])
        ifTrue: [ store allocatePage ]
        ifFalse: [ currentPage split: store allocatePage ].
    "... rewire the left and right pointers on every level of the new page ..."
    ^ newPage

If the page is the last one and the new key is bigger than everything in it, nothing is split: an empty page is appended and the key goes there. Keys that only grow, like timestamps or counters, fill each page completely instead of leaving every page half empty after a split in the middle. In every other case the page is split with half of its items going to the new one.

The header page is where the structure has to be a little untidy. It is the first node and has all maxLevel lanes, it is never removed, and the skip list has no separate tail node. The tail pointers are kept in the left array of the header page, which is a deliberate misuse: the source says so in a comment, and previous on the header page answers a hard-coded 0 so that nobody reads those pointers as a real predecessor.

A B-tree with a fixed root

The B-tree is the textbook B+ tree: leaves hold the items and are chained to each other, inner pages hold only routing entries. Two choices about where things live are Soil's own. The header page, which carries the key size, the value size, the size counter and the free list, is also the first leaf: SoilBTreeHeaderPage has the same superclass as the leaf pages and behaves as one, so a B-tree with a single leaf has no extra page for its metadata. And the root page lives at a fixed offset, 2, for the whole life of the file. It never moves, which means nothing needs to be updated when the tree grows.

That second choice is visible in what a root split does:

"SoilBTreeRootPage"
insertItem: item for: iterator
    | foundItem return newIndexPage1 newIndexPage2 |
    foundItem := self findKey: item key.
    return := (iterator index pageAt: foundItem value) insertItem: item for: iterator.
    return indexEntryNeeded ifFalse: [ ^ return ].
    self addItem: return indexEntry.
    iterator index addDirtyPage: self.
    self hasRoom ifTrue: [ ^ return indexEntry: nil ].
    "we are the root index page, thus we have to create another index page and move items there"
    newIndexPage1 := iterator index newIndexPageFromRoot: self.
    newIndexPage2 := iterator index splitIndexPage: newIndexPage1.
    self addItem: newIndexPage1 smallestKey -> newIndexPage1 offset.
    self addItem: newIndexPage2 smallestKey -> newIndexPage2 offset.
    ^ return

A normal inner page that overflows splits and hands a new routing entry upwards. The root has nobody above it and may not move, so it does the opposite: it empties itself into a fresh inner page, that page is split in two, and the root is left with exactly two entries pointing at the halves. The tree gets one level taller and the root is still at offset 2.

A B-tree before and after a root split. Before: the root page at offset 2 routes to four chained leaves, the first of which is the header page. After: the root has emptied itself into a new index page that was split in two, the root holds two entries, and the leaves and their chain are unchanged

The helper that moves the items is where Soil v6 fixes a bug, found by Paul Wilke:

"SoilBasicBTree"
newIndexPageFromRoot: rootIndexPage
    | newPage |
    newPage := self newIndexPage.
    self store pageAt: newPage offset put: newPage.
    self addDirtyPage: newPage.
    "now move over all items"
    newPage setItems: rootIndexPage items.
    rootIndexPage setItems: OrderedCollection new.
    ^ newPage

The line self addDirtyPage: newPage is the fix, and it is one line. Without it, the new page went into the in-memory page cache and was never marked for writing, so the commit wrote nothing for it. Everything kept working as long as the file stayed open. After a close and a reopen, the page was a block of zeros on disk, and reading anything through it failed with SoilIndexItemsPage had the subclass responsibility to implement #valueSize, which tells you nothing about a missed dirty flag. It needed a root index page that had been completely filled, which is 12 entries at a key size of 1016 bytes but around 20,000 entries at a key size of 20. With small keys that is a long way into an index, which is how it stayed hidden for so long. The test that came with the fix runs the reopen for both backends, and only the B-tree one failed before.

What removal does, and what it does not do

Removing a key does not remove anything from the page. The iterator finds the page and the item, and overwrites the value with a marker:

"SoilIndexIterator>>removeKey:ifAbsent:, the relevant lines"
"We replace the value with the removed ID. As the key stays, we do not need to do a full insert
(e.g no need to update index pages for the BTree"
currentPage items at: currentPageIndex put: indexKey -> (SoilRemovedObjectId for: oldValue).
currentPage markForWrite.
index addDirtyPage: currentPage.
index decreaseSize.
^ oldValue

The marker is an object id like any other value, but with segment 0 and index 0, which no real object ever has. isRemoved is nothing more than a test for that pair. So on disk a removed entry is a key with the value 0:0, in the same slot, on the same page. Nothing moves, no routing entry in a B-tree changes, and the removal costs one dirty page. The size counter goes down right away, and a page counts its present items by skipping the markers.

Two things need the entry to stay for a while. The old value is not lost: it is written to the transaction journal in a SoilRemoveKeyEntry together with the key, and that is what lets a transaction that started before the removal see the key again. How that works is the subject of the next post. And the page may still be needed in its old state by such a transaction, so physically dropping the entries is a separate step. SoilIndexCleaner does it at a checkpoint, and only for pages where no running transaction has a read version older than the page's last change. Until then a removed key is a key whose value reads as removed.

Everything else about removal is lazy as well. There is no merging and no rebalancing: a page that is half empty stays half empty, and the only page that is ever given up is one that has become completely empty, which is unlinked and put on the free list. The low-level remove methods carry a warning that a page left empty breaks the search, because the search needs at least one key per page, and that the caller has to clean the page up. Getting space back from sparse pages is a different operation, compact, which writes a new index file with only the live items and swaps it in. It trades the complexity of rebalancing for a rewrite that is easy to reason about and happens when someone decides to run it.

The header page also holds the number of entries as a stored counter, updated on every insert and remove. That makes size cheap and makes it something that can drift, if a bug ever skips an update. So v6 adds recomputeSize, which counts what the pages really hold and writes that back. It walks the whole index, so it is a repair tool and not something for the hot path.

Free pages

A page that becomes empty is not cut out of the file, files do not shrink from the middle. It is recycled:

"SoilIndex"
recyclePage: aPage
    "the header stays untouched even it it gets empty"
    aPage isHeaderPage ifTrue: [ ^ aPage ].
    "remove page from chain of item pages"
    self removePage: aPage.
    "add page to free list chain"
    ^ self addToFreePages: aPage

Two things happen. The page is unlinked from the chain of data pages, so searches no longer reach it. For the skip list that means the neighbours' left and right entries on every level the page took part in, for the B-tree the previous and next pointers of the leaf chain and the routing entries in the inner pages. And the page is overwritten in place by a SoilFreePage, an object with the same offset and the same size, the page with code 7 from the table above. The file keeps its length, and data pages and free pages end up mixed in whatever order things were removed.

The free pages are not a linked list of single pages. The header page holds firstFreePageIndex, and the page it points to is a free page that doubles as a list: it stores the offsets of other free pages, two bytes for the count and four bytes per offset, plus a next pointer to another free page that continues the list. The picture shows the common case, a short list in one page.

"SoilIndex"
addToFreePages: aPage
    | currentFreePage newFreePage |
    newFreePage := aPage asSoilFreePage.
    store pageAt: aPage offset put: newFreePage.
    currentFreePage := self firstFreePage ifNil: [
        "no first free page yet, aPage becomes it"
        self headerPage firstFreePageIndex: newFreePage offset.
        ^ newFreePage ].
    "scan for a free page that has room to store another free page"
    [ currentFreePage hasRoom ] whileFalse: [
        currentFreePage next == 0
            ifTrue: [
                currentFreePage next: newFreePage offset.
                ^ newFreePage ]
            ifFalse: [ currentFreePage := store pageAt: currentFreePage next ] ].
    currentFreePage addPage: newFreePage.
    ^ newFreePage

The first page that is given up becomes the list. Every further one is entered into the first list page that still has room. A list page holds about a thousand offsets, so the next pointer only comes into play after that many freed pages. If the list is full and has no next, the page that is being freed becomes the next list page. Allocating a page is the reverse:

"SoilIndex"
allocatePage
    | page |
    page := self newPage
        version: self version;
        offset: (self nextFreePageIndex
            ifNil: [ self nextPageOffset ]).
    self store pageAt: page offset put: page.
    self addDirtyPage: page.
    ^ page

nextFreePageIndex takes the first offset out of the list, and when the first list page is empty it gives out the list page itself and moves firstFreePageIndex to its next. Only when there is no free page at all does the index grow the file with nextPageOffset. A page that comes back from the free list is a new page object at an old offset, and everything on disk that pointed at the old page already stopped pointing at it when it was unlinked.

The index file as a row of header, data and free pages. The data pages are connected to each other by a chain of left and right pointers that skips the free pages. The header points to the first free page, which stores a list of the offsets of the other free pages and a next pointer

Where this leaves us

An index is a file of 4 KB pages that know their own kind by their first byte. A key is a fixed-width number. The skip list is a skip list of pages, with a coin flip per page and a cheap append for keys that only grow, and the B-tree is a B+ tree whose root never changes address and whose header page is also its first leaf. None of this knows about transactions yet: as described here, a page is just a page, shared by whoever touches the file. What happens when two transactions touch the same index, why a reader on an older version can still see the world as it was, and what a commit has to log for that to work, is the next post.

The code is on github if you want to read ahead.

Found something worth flagging? Send feedback.
This work is licensed under CC BY 4.0.