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 under MVCC

The last post ended with a file of pages that knew nothing about transactions: as described there, a page is just a page, shared by whoever touches the file. That cannot be the whole story. The MVCC post promised every transaction a world frozen at its start, and the heap keeps that promise by never overwriting anything: old versions stay where they are and a chain leads back to them. An index page is overwritten in place. The journal post mentioned in passing that this is why some entries remember the value they replaced. This post follows that sentence through the three places where it matters: what a writer touches before it commits, what an older reader sees when the page has moved on, and what happens when two writers want the same key.

Writers work on copies

A transaction never changes the persistent index. When a dictionary is used inside a transaction, it asks for its index and wraps it:

"SoilIndexedDictionary>>index"
index := ((transaction segmentAt: segment) indexAt: id) asCopyOnWrite

The wrapper is a copy-on-write version of the same index class, SoilCopyOnWriteSkipList or SoilCopyOnWriteBTree, with a page store of its own. It reads through to the persistent store, but copies every page it touches:

"SoilCopyOnWriteIndexStore>>pageFaultAt:"
pageFaultAt: anInteger
    | page |
    page := (wrappedStore pageAt: anInteger) copy.
    pages at: anInteger put: page.
    ^ page

Everything the transaction does to that page, an insert, an overwrite, a removal marker, happens on the copy. The wrapper's addDirtyPage: does nothing, so nothing is ever marked for writing, and the persistent file is not touched. Here is what that looks like in an index with 300 entries and 5528 bytes in the file. After a put inside a transaction the file was still 5528 bytes and had no dirty pages, the transaction's own page store held the two pages the put had walked through, and a second transaction did not see the new key. After an abort the file was unchanged. After the commit it was 5546 bytes, 18 more, the key and the value.

Three rows: the pages of the persistent index file, the copies transaction A made of pages 1 and 3, and the copy transaction B made of page 3. Changes stay in the copies

The copy is a snapshot of the page as it is at the moment of the first access, which is not the same as the page as it was when the transaction started. Another transaction may have committed in between. A transaction that reads the page only after that happened gets the newer page, and that is the problem the next section solves.

A reader meets a page that moved on

Every index page remembers the last transaction that changed it, lastTransaction, which the commit sets as it applies its entries. A reader has a readVersion. If lastTransaction is not newer than the readVersion, nothing happened to the page since the reader started, and the page is simply right. Otherwise the reader has to take back every change made after its version, and for that it has the journal.

The page does not know what it looked like. The journal does, because every key entry carries the value it replaced. SoilIndexedDictionary>>at:put: creates it together with the change:

"SoilIndexedDictionary>>at:put:, abridged"
oldValue := self newIterator at: key add: objectId.
transaction addJournalEntry: (SoilAddKeyEntry new
    key: (self index indexKey: key);
    value: objectId;
    oldValue: oldValue)

at:add: answers what the key held before, and that goes into the entry as oldValue. A removal does the same with SoilRemoveKeyEntry. The iterator a reader uses for lookups is a SoilRestoringIndexIterator, and what it does to an item is the interesting part:

"SoilRestoringIndexIterator>>historicValueFor:, abridged"
restored := item.
self currentPage lastTransaction to: readVersion + 1 by: -1 do: [ :transactionId |
    (journal transactionJournalAt: transactionId) entries reverseDo: [ :each |
        (each isForItem: restored index: index id)
            ifTrue: [ restored := restored key -> each oldValue ] ] ].
^ restored

It starts at the page's lastTransaction and walks down to the transaction right above the reader's version. In each transaction it looks at the entries from the last to the first, and whenever an entry is about this index and this key and produced the value the item holds, it replaces the item by the old value. Because it holds on to the result and keeps going, a key that was overwritten twice since the reader started goes back two steps, not one. The test for it is short:

"SoilIndexedDictionaryTest>>testAKeyOverwrittenTwiceKeepsItsValueForAnOlderReader, abridged"
dict at: #foo put: #one.                "committed"
reader := soil newTransaction.
tx root at: #foo put: #two.             "committed"
tx root at: #foo put: #three.           "committed by the next transaction"
self assert: (reader root at: #foo) equals: #one

A reader at version 4 and a page last changed by commit 7. The walk goes back through commits 7, 6 and 5, replaces the item for foo by the old value of each matching entry, and ends with foo = one

There are three possible outcomes. The key was overwritten after the reader started, and the reader gets the old value. The key did not exist when the reader started: the walk arrives at an entry whose old value is nothing, the item becomes empty, and the iterator skips the key. A key added after a reader started does not show up when it iterates, which is a test of its own. And the key was removed after the reader started: this is the removal marker from the last post, a value of 0:0 that the page still holds, and the entry's old value brings the real value back. If a journal is missing altogether, the item is taken as it is now.

Matching an entry to an item has one subtlety: a value has two representations. A page that was read back from disk holds its values as byte arrays, while a page changed in this image and a journal entry hold object ids, and the two are never equal. So there is one place that compares index values, SoilIndexItemsPage class>>value:matches:. Across representations the bytes decide, within one representation its own equality does, because an object id of a new object that has not been committed yet has no bytes of its own.

What an old reader costs

The walk visits every transaction between the page's lastTransaction and the reader's version, so a long-running reader gets more expensive the more the pages it reads change. The journal helps with a cache for the last 20 transaction journals:

"SoilPersistentDatabaseJournal>>initialize"
transactionJournals := LRUCache new maximumWeight: 20

Older journals are read back from the fragment files of the journal. The measurement below uses an index of 400 entries in two pages. A reader starts, then N transactions commit, and then the reader reads one key. In one case the commits overwrite another key on the same page as the one the reader reads, in the other case a key on the other page. Time is per read, three runs:

commits since the reader started same page other page
10 0 ms about 0 ms
20 0 ms about 0 ms
21 77 to 91 ms about 0 ms
50 317 to 398 ms about 0 ms
100 1151 to 1476 ms about 0 ms

There is a cliff at 20, which is the size of the cache, and there is no cost at all as long as the commits are on a different page than the one the reader reads, because then the page is older than the reader's version and returned as it is. The cost grows faster than the number of commits. The walk goes through more journals than the cache can hold, so it evicts the very journals it is about to need again, and a second read is not cheaper than the first. The absolute numbers come from one machine and one image and should not be quoted, but the shape is real: an old reader does not cost anything until the pages it reads are changed under it, then it costs per commit, and beyond 20 commits it costs a file read per commit. Version 6 added a metric, oldestReaderLag, that tells how far the oldest reader is behind, which is the number to watch.

Commit: check, then apply

When a transaction commits, its index changes are in its journal as key entries. The commit builds that journal, and then, still inside the one critical section that only one transaction can be in at a time, it does the following (the central lines of SoilTransaction>>basicCommit):

"SoilTransaction>>basicCommit, abridged"
journal := self buildJournal.
self detectIndexConflicts.
soil journal writeTransactionJournal: journal.
journal commitIn: soil.
soil journal addTransactionJournal: journal

The steps of a commit as boxes in a row: critical section, build the journal, detect conflicts (highlighted), write the journal, apply the entries, keep the journal in the cache

The check for objects is the one from the conflicts post. It looks at the records. Index entries are not records, and before version 6 nothing looked at them: two transactions that put the same key overwrote each other without a word, and a transaction that removed a key somebody else had just removed failed only after its journal had been written, with KeyNotFound. detectIndexConflicts closes that gap without reading a single page:

"SoilTransaction>>detectIndexConflicts, abridged"
writeVersion - 1 > readVersion ifFalse: [ ^ self ].
readVersion + 1 to: writeVersion - 1 do: [ :version |
    committed := soil journal
        transactionJournalAt: version
        ifAbsent: [ "unknown, cannot be ruled out" ^ SoilIndexHasConcurrentChange new signal ].
    committed entries do: [ :theirs |
        "for each entry of ours on the same index and key:"
        (index hasUniqueKeys or: [ ourValue matches: theirValue ])
            ifTrue: [ ^ SoilIndexHasConcurrentChange new signal ] ] ]

The first line is the common case. If no transaction committed since this one started, there is nothing to compare. Otherwise it collects its own key entries by index and key, which the code above leaves out, then goes through the journals of the transactions committed in between, the same ones the readers walk, and compares. An index with unique keys has a conflict when both touched the same key. An index that allows duplicate keys has one only when both touched the same key with the same value, because adding another value to a key is something two transactions can do side by side. If a journal is not available any more, the transaction cannot know and refuses to commit. The error is a SoilIndexHasConcurrentChange, a kind of commit error, and a test shows what that means:

"SoilIndexedDictionaryTest>>testPuttingAKeyAnotherTransactionPutIsAConflict, abridged"
tx := soil newTransaction.
tx2 := soil newTransaction.
tx2 root at: #two put: #theirs.
tx2 commit.
tx root at: #two put: #ours.
self should: [ tx commit ] raise: SoilIndexHasConcurrentChange

A neighbouring test pins down the other side. Both transactions put different keys, tx2 commits first, and tx commits afterwards without a problem, because its journal was looked at and held no key of the second. Only after this check passes does journal commitIn: soil run. For a key entry that means replaying it on the persistent index, and setting lastTransaction on the page it changed:

"SoilAddKeyEntry"
commitIn: soil recovery: aBoolean
    | index |
    index := (soil objectRepository segmentAt: self segment) indexAt: id.
    index newIterator
        at: key add: value;
        updateCurrentTransaction: transactionId

This is the first moment the index file changes. The same entries, read back from the journal, are what recovery replays after a crash, with the difference that a missing key on a removal is ignored there, because the removal may have been applied before the crash. The entries do three jobs: they are the log for recovery, they are what a conflict is detected from, and they are what an older reader takes its old values from.

The removed key and the checkpoint

The last post ended on the removal marker, an entry that stays on its page with the value 0:0 until something cleans it up, and left open when that is. Now there is enough to say when, shown on a small index with three keys. A reader starts, another transaction removes the key b and commits:

moment page holds size the older reader sees b
before the removal a, b, c 3 yes
removal committed, reader open a, b removed, c 2 yes
reader aborted a, b removed, c 2 –
checkpoint, reader open a, b removed, c 2 yes
checkpoint, reader gone a, c 2 –

The counter goes down with the commit, but the entry stays. The page cannot let go of it, because the older reader gets the removal taken back from the journal, and it can only do that for an entry that is still there. Abort of the reader changes nothing yet. Cleaning happens at a checkpoint, and Soil takes one with every commit that changed something. The checkpoint flushes the indexes and passes the smallest read version of the transactions that are still running to the SoilIndexCleaner, which only drops removed entries from pages that no running transaction can still need in their old state. The checkpoint that came with the removal ran while the reader was open and left the entry alone. The first one after the reader is gone removes it, and now it is really gone.

Where this leaves us

An index in Soil has three layers that do not know much of each other. The pages are plain and mutable. A transaction sees them through a copy and never writes to them, a reader sees them through the journal and never sees what happened after its version, and the commit that applies the changes first checks the same journal for somebody else's changes to the same keys. The price is paid at two places, by the one commit that has to look at the journals since it started, and by the readers that run long over pages that keep changing.

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.