A Snapshot on a Tick Boundary
The tick boundary snapshot
The Hollow lives entirely inside one process. Stop the process and the ground, the plants, the animals, the genomes, the pedigree, the species register and nine generator positions are gone. The database on the other end of the bridge has seven tables and nothing whatever in any of them.
A snapshot names a tick and is taken between two of them: after
terra.Valley.Tick has returned and before the next call, when no phase is
part way through, no view is open and no creature is half stepped. Every part of it is
written in one transaction, so a snapshot is whole or it is absent, and a restart has two
states to reason about instead of three.
The first thing to go into the tables is not a creature and not a line of history. It is the world, written down at one moment, in enough detail that a process started tomorrow on a machine that has never run this valley can pick it up and carry on as though nothing had happened.
Writing a world down is easy. Writing one down at a moment that means anything is the whole problem, and the reason is the creature phase. Its order is build the view, cast every fan, step the roster in order, sweep the struck, bury the dead, mint the births.
Catch it four creatures in and look at what you are holding: an index describing a valley that has already changed, a roster where some animals have had their tick and some have not, a list of the dead that nothing has acted on yet, and a generator that has already spent numbers on a creature not yet on any list. Write that down and you have written down a moment the world was never in.
What goes in it is the list at the top of this page, in eight parts: the clock and the dials and both sets of books; the bed's two numbers a cell and the litter's two; every stand; the seed bank; the air; every genome the pool holds, the dead ones included, with the pedigree, the species register and the mint's counter; the roster in order with every number on every creature; and the marshalled state of every generator the run reads. One row a part, all of them written together or not at all.
Here is exactly what that buys, stated before any of it is built, because the claim is the point and the code is only how it is kept. A world restored from the snapshot at tick T runs ticks T+1 onward identically to the run that wrote it. The same digest a tick, the same rows in the archive, the same populations, the same species numbers, the same innovation numbers. Not nearly the same and not statistically indistinguishable: the same run, and the last section of this chapter runs one valley straight through, runs a second that stops in the middle and comes back in a different process, and holds the two against each other byte for byte.
What it does not buy matters as much. Nothing about the wall clock. Nothing about the rate the ticks came at, which is a fact about the machine and never about the world. Nothing about the order the rows reached the database. A world that took four hours and a world that took forty minutes are the same world if they have taken the same ticks, and a page that let a reader think otherwise would be selling determinism it has not got.
One rule from the chapter that opened this database has to survive all of this, and it is
the load-bearing one: nothing in internal/sim, internal/terra,
internal/beast, internal/gene or internal/mind
imports internal/store, and nothing inside a tick calls into it. A snapshot
reads every one of those packages. The only reason that is survivable is the boundary:
the thing that reads the whole world runs between two ticks and never inside one, so the
arrows still run one way and the test that says so is untouched by this chapter.
Four things are deliberately not here. Nothing is written into the creature table, which
is as empty at the end of this page as at the start. No question is asked of a pedigree.
The genesis column is not null and is handed an empty object, because what
an operator writes in it is a different question from what a snapshot is. And there is no
daemon: the process that carries the world on is started by hand, at a shell, and the
whole of what it does is read a snapshot and keep ticking.
No views or half steps
Taking the snapshot between ticks sounds like tidiness, the sort of rule somebody writes in a design document because it reads well. It earns its place a different way: it decides what is on the list. Two things in this world would have to be carried by a snapshot taken anywhere else, and at a boundary neither of them can be reached at all. The mint is the sharper of the two.
A quick reminder of what it is for. Every link and every node a controller grows is minted a number, and that number is its name for the whole run: two links in two different genomes carrying the same number are the same link, which is what lets a crossing line two wirings up. The mint keeps a counter that only ever goes up, and beside it a table of what has been minted on the tick now being worked. Two creatures born on one tick that both put a node into link 57 have made the same change and are handed one number. Two that make that change a thousand ticks apart are two lineages that arrived at the same wiring separately, and this world lets them keep separate names for it. The table is what tells the two cases apart, and it is emptied whenever the tick changes.
So consider a snapshot taken between two ticks. Whatever is in that table cannot be read again by anything, ever, because the only road into it goes through the call that says which tick is being worked, and being told a new tick empties it. The table is dead at a boundary whether or not it happens to be empty, and the whole of what has to be written down is the counter. A snapshot taken in the middle of a breeding pass is a different matter: it would have to carry the table as well, and a restart that dropped it would hand two children of one tick two names for one change, quietly, in a number that is supposed to mean the same thing for the rest of the run.
// internal/gene/save.go
// Held is how many marks the mint's table is holding for the tick it is
// working: the changes something has already made this tick, kept so
// that a second creature making the same change on the same tick is
// handed the same number.
//
// It is on the record because of what a snapshot does not have to
// carry. The table is emptied whenever the tick changes, and the only
// road to it goes through Now, so nothing that is in it when a tick
// closes can ever be read again. What has to be kept is the counter.
func (m *Mint) Held() int { return len(m.same) }
// Load puts a counter back where a snapshot found it: the next number
// it will hand out, and the two totals a run prints about it. The table
// is left empty and the tick left unset, which is the state the first
// Now of the next tick would have put it in anyway.
func (m *Mint) Load(next, minted, shared int) error {
if next < m.next-m.Minted {
return fmt.Errorf("gene: a mint that has handed out %d numbers cannot go back to %d",
m.Minted, next)
}
m.next, m.Minted, m.Shared = next, minted, shared
m.tick, m.open = 0, false
clear(m.same)
return nil
}$ go test ./internal/gene/ -run 'OnlyTheCounterOutlivesATick|EveryCounterSurvivesASnapshot' -v
=== RUN TestOnlyTheCounterOutlivesATick
save_test.go:56: one table emptied whenever the tick changes, and three numbers to carry across a boundary
--- PASS: TestOnlyTheCounterOutlivesATick (0.00s)
=== RUN TestEveryCounterSurvivesASnapshot
save_test.go:87: 23 counters written down and 23 read back
--- PASS: TestEveryCounterSurvivesASnapshot (0.00s)
PASS
ok theworld/internal/gene 0.00s
The first test is the argument in eight lines: the same change twice on one tick is one number, the table holds one mark, the tick changes and the table holds none, the same change again is a different number, and a counter put back from three saved integers hands out exactly what the counter it was copied from hands out. The second test is about a different kind of forgetting and is worth a paragraph of its own further down.
The second thing that cannot be reached is the force accumulator on a body. A creature's
tick piles
forces into it and field.Body.Step spends them and empties it, and every path
through a creature's tick ends in that call, including the paths where the creature rests
and the paths where its action was refused. So at a boundary every accumulator in the
valley holds nothing at all. That is fortunate, because it is an unexported field of a
struct in another package and there is no way to write it down. A snapshot taken mid-phase
would need it and could not have it.
Both of those are the same observation twice. What a boundary gives you is a moment at which everything a tick keeps in flight has already been spent, so the only things still holding anything are the things a snapshot can name.
With that settled, the list of what a snapshot holds can be made and measured. The chapter's bench founds a valley of both rows, runs it to the end of its fourth year, stops between ticks and writes the world into eight parts. It opens no socket: every number below comes out of the world's own memory.
$ go run ./cmd/save -mode parts | tail -71 | head -18
save: what a snapshot of this world holds, and what one costs
a 16x12 valley, 21 browsers off stream 12 and 8 hunters off stream 22
founded on world seed 5, ticked to the end of year 4 and stopped between ticks
the world at the boundary
the tick it is standing on 14851
ticks it has taken since it was founded 13950
plants standing 124
browsers walking 19
hunters walking 0
seeds waiting in the ground 7049
seeds still falling 0
seeds this air has carried, in all 11112
the most it ever held at once 3336
genomes the pool holds, the dead included 224
species it has opened 1
numbers it has taken off its five streams 1331290
The tick it is standing on is the tick it has not run yet, which is the only reading of “tick 14851” that a boundary allows. Two of those lines are there to be argued with. The air is empty because nothing is falling on this particular day of the year, and the part that describes it is written all the same: this air has carried eleven thousand seeds and held three thousand at once, and a snapshot taken on one of those days has three thousand bodies in flight to write down. The hunters are gone — the restore two boxes below counts none of them walking — and every genome they were ever stamped from is still in the pool, because a pool never forgets one.
$ go run ./cmd/save -mode parts | tail -52 | head -12
the eight parts, in the order they are put back
part bytes share what is in it
valley 753 0.03% the clock, the dials an operator set, both sets of books
bed 6360 0.29% two numbers a cell, and the litter lying on top of them
stands 19600 0.90% every plant standing, and what its last tick came to
bank 114328 5.23% every seed waiting in the ground
air 32 0.00% every seed still falling
pool 2041943 93.40% every genome it holds, the dead ones included
roster 2667 0.12% every creature walking, and every number on it
luck 518 0.02% the generators, at twenty bytes apiece
2186201 100.00%
a snapshot of this world is 2186201 bytes and 93.4% of it is genomes
Two megabytes, and ninety-three percent of it is heredity. The ground everything is standing on is six kilobytes; the animals walking about on it are two and a half; the seed bank is the second biggest thing in the world and the only reason it is bigger than the ground is that seven thousand seeds are lying in it waiting for a season. The order is the order the parts are put back, and it is the one thing about that listing that is not free: a creature is priced off the genome the pool holds for it, so the pool has to be filled before the roster is.
The parts are written in different formats and that is on purpose. Seven of them are plain numbers appended big-endian, with no field names and no lengths beyond the ones written deliberately, because the reader is the same list of calls in the same order and a format whose only definition is a pair of functions cannot drift between them. The pool is JSON, written the way the archive writes a genome, and that is the schema chapter's rule about what a part is rather than an inconsistency: a genome already has a written form that reads back as the same genome, checked every time an archive is opened, and inventing a second one would be two descriptions of one animal that have to agree forever.
$ go run ./cmd/save -mode parts | tail -11 | head -4
the ground, which is not in the snapshot at all
the valley that wrote it, as terrain c424c8718845f28f
the valley built back out of three numbers c424c8718845f28f
16x12 cells made by sim.Generate off seed 5, and no tick can move one
Terrain is the one thing about this world that is completely determined and completely
fixed: a hundred and ninety-two cells of rock, soil and water that sim.Generate
makes out of a width, a height and a seed, and that nothing in a tick can change. So
the valley part carries those three numbers and the loader makes the ground
again. Storing it would cost almost nothing and it would still be the wrong call: a
snapshot that carried a copy of something derived would be a snapshot that can disagree
with the program reading it, and the fix for that argument is to have only one of them.
The saved PCG state
Every random number in this world comes off a numbered generator, one number a purpose, and the registry has been added to a volume at a time: the terrarium owns seed flight, germination, plant mortality and the scattering of a founding generation; the pool owns mutation, crossover, mate choice, structural mutation and birth placement. The running world holds nine of them. The streams a founding spends are not among the nine — the two that scatter a population over the ground and the one its brains are drawn off — because all three are opened, spent and dropped before the first tick, and a world being restored is not being founded.
Those nine are the whole of this world's luck, and until this chapter there was no way to
ask any of them a single question. rand.New(rand.NewPCG(seed, n)) is the line
every stream in this book has been opened with, and it throws away the only half of the
pair that can be written down: rand.PCG marshals, and the rand.Rand
wrapped round it will hand you numbers forever and can never be asked what state it is in.
A generator you cannot ask is a generator you cannot save. So a stream is now opened in
one place that keeps both halves, with the same constructor, the same seed and the same
stream number, and every run in this book reads the numbers it always read.
// internal/sim/luck.go
// Stream is one of this world's numbered generators, kept as the two
// things it actually is: the *rand.Rand a run draws from, and the
// *rand.PCG underneath it, which is the only half of the pair that can
// be written down.
type Stream struct {
N int // its number in the registry, which no two streams share
What string // what it is for, for a run that prints the registry
Src *rand.PCG
R *rand.Rand
}
// State is everything this generator is, as bytes. A PCG holds two
// unsigned sixty-four bit numbers and marshals to those sixteen bytes
// with four in front of them naming the kind of generator they belong
// to, which is what stops a state written by one generator being read
// back into another.
func (s Stream) State() ([]byte, error) { ... }
// Load puts this generator back into the state those bytes describe.
// The Rand drawing from it is unchanged and does not have to be told:
// it holds the source, not a copy of it.
func (s Stream) Load(b []byte) error { ... }$ go run ./cmd/save -mode luck | tail -40 | head -18
save: twenty bytes a stream, written down and read back
a 16x12 valley at the end of year 4, and every generator standing in it
stream what it decides bytes tag the sixteen bytes of state reads back
8 seed flight 20 pcg: 16ff9946e8b98cdad7eb87ff13f9c110 yes, 8 of 8
9 germination 20 pcg: e37b83bb7c956b4b6acb1a6a71da1853 yes, 8 of 8
10 plant mortality 20 pcg: 64314aca93ea179b68bbc21897914697 yes, 8 of 8
11 founding plants 20 pcg: 8425ed5d19cc94e8753e1814b160032b yes, 8 of 8
16 mutation 20 pcg: 9b74ee4129c45a7f913cc9bc6fe468fc yes, 8 of 8
17 crossover 20 pcg: e1ee3e8808b31d1ca90651919b39a6a6 yes, 8 of 8
18 mate choice 20 pcg: e752ea9183a9634973001b56abb8975d yes, 8 of 8
19 structural mutation 20 pcg: 3a9df5ae320cf46864719441eaf8c5d7 yes, 8 of 8
20 birth placement 20 pcg: 3a40a76e8d1b6aebbc9a8f4e472a1b16 yes, 8 of 8
9 streams, 20 bytes apiece, 180 bytes for the whole of this world's luck
four bytes naming the kind of generator and sixteen of state, which is
two unsigned sixty-four bit numbers and the entire memory a PCG has
Twenty bytes, nine times. The four in front are the ASCII characters
pcg:, and they are the format saying what kind of generator it came off, so
that sixteen bytes belonging to one kind of generator cannot be read into another. The
sixteen behind them are the entire memory this generator has: a PCG is a state and an
increment, both unsigned sixty-four bit numbers, and everything it will ever hand out
follows from them. The last column is a check and not a claim: the bytes are read
into two fresh generators, both are asked for eight numbers, and the answers are held
against each other.
One of the nine is only ever read while a valley is being founded, which is stream 11, and it is written down with the rest. A generator the world is holding is a generator the world can read, and twenty bytes is not a price anybody has to think about.
$ go run ./cmd/save -mode luck | tail -16
two worlds built out of that snapshot, and in the second one stream 16 is
opened fresh off the world seed instead of put back where the run left it
ticks the two of them ran as one world 168
the tick they parted on 15019
births on that tick 1
and 400 ticks on from the restore
restored whole c79d09c6fe0da253 alive 21 born 198
stream 16 left out 2187908b241c5070 alive 21 born 198
A generator opened on the same seed and the same stream number is not the
same generator. The one this run was holding had been drawn from since the
first tick; the fresh one is standing at the beginning of the world, and
the two of them part company the first time anything asks stream 16 for a
number.
That is what the twenty bytes are for, run instead of asserted. The second world is built out of the same snapshot with one line changed: stream 16 is opened on the world seed and the stream number, which is exactly how it was opened when the valley was founded, instead of being handed the state the snapshot saved. For a hundred and sixty-eight ticks the two worlds are the same world, because nothing is born in either of them and mutation is only ever asked for a number at a birth. Then something is born, and from that tick on there are two valleys. Both of them have twenty-one animals walking about four hundred ticks later and both have had a hundred and ninety-eight births, and only one of them is this world.
Start with the luck, because it is the smallest and the most surprising. Nine generators at twenty bytes each is 9 × 20 = 180 bytes. The part that holds them is 518, because each one is written with its number and the word for what it decides beside its state, and those labels are most of it. Against a snapshot of 2,186,201 bytes that is 518 ÷ 2,186,201, or 0.024 percent. Every decision this world will ever make that is not arithmetic comes out of those 180 bytes.
Now the other end. The pool part is 2,041,943 bytes and the whole snapshot is 2,186,201, so the genomes are 2,041,943 ÷ 2,186,201 = 93.4 percent of it. The 224 genomes in it work out at 2,041,943 ÷ 224 = 9,116 bytes each, which is a wired controller written as its links and their numbers. The ground under all of them is 6,360 bytes: two float64s a cell for the soil and two for the litter is 4 × 8 = 32 bytes a cell, and 192 cells at 32 bytes plus a little bookkeeping is what that comes to. The bed is a fixed size for the life of a world. The pool is not.
Which gives the comparison that matters. The archive these four years wrote is 2,045,639 bytes, and the snapshot of the world at the end of them is 2,186,201: the snapshot is 2,186,201 ÷ 2,045,639 = 106.9 percent of the whole history. The two are nearly the same size for one reason, and it is not a coincidence. The archive holds a line for every birth, and every one of those lines is a genome. The pool holds every genome it has ever handed out, the dead included, because that is where a run's history lives while it is running. So they grow at the same rate, and a snapshot of this world in its hundredth year is a hundred years of genomes whether or not anything is still standing.
Four claims have been made now: the state is twenty bytes and reads back, a snapshot is eight parts and not seven, a world built out of one runs the same ticks, and a snapshot taken under one set of rules cannot be loaded into a program running under another. All four are checkable with no database anywhere near them, so all four are tests, and they run beside two more: the architectural rule this chapter had every reason to break, and what becomes of a part that arrives a byte short.
$ go test ./internal/store/ -run 'EveryGeneratorIsTwentyBytes|ASnapshotIsEightParts|AWorldRestoredRunsTheSameTicks|ASnapshotTakenUnderOtherLaws|APartThatIsShort|NoSimulationPackageImportsTheStore' -v
=== RUN TestNoSimulationPackageImportsTheStore
rule_test.go:61: every file in every sealed package read, and not one of them names it
--- PASS: TestNoSimulationPackageImportsTheStore (0.00s)
=== RUN TestEveryGeneratorIsTwentyBytesAndReadsBack
save_test.go:177: 9 streams, 20 bytes each, 180 bytes of luck, all of it read back
--- PASS: TestEveryGeneratorIsTwentyBytesAndReadsBack (0.00s)
=== RUN TestASnapshotIsEightPartsAndNoOthers
save_test.go:211: 8 parts, every one of them once, and 237438 bytes between them
--- PASS: TestASnapshotIsEightPartsAndNoOthers (0.00s)
=== RUN TestAWorldRestoredRunsTheSameTicks
save_test.go:239: 200 ticks after the snapshot, both worlds at a6cb1188fc54c47f, 11 alive and 13 born
--- PASS: TestAWorldRestoredRunsTheSameTicks (0.00s)
=== RUN TestASnapshotTakenUnderOtherLawsIsRefused
save_test.go:256: store: this snapshot was taken under laws 43531c7331ee91ca and this program runs under 32d5b7eb1d93b547: a world restored across that difference is a different world
--- PASS: TestASnapshotTakenUnderOtherLawsIsRefused (0.00s)
=== RUN TestAPartThatIsShortIsRefused
save_test.go:278: all 8 parts refused a byte short
--- PASS: TestAPartThatIsShortIsRefused (0.00s)
PASS
ok theworld/internal/store 0.00s
The first of them is the architectural rule, restated here rather than taken on trust, because this chapter is the one that had a reason to break it. Five simulation packages, none of them importing the store, and a package that reads all five of them from the outside.
The last two are about refusing rather than working. A snapshot carries a digest of the rules it was taken under, the founding rows of both tables folded in with them, so a world restored into a program whose prices have moved since is stopped with both digests in the message instead of quietly running under numbers no caller chose. And every part is read with the length it says it has: take one byte off any of the eight and the load fails, which is what keeps a truncated part from becoming a valley with one number in the wrong place.
The claim in the middle of that list is the one the volume rests on, and a test that runs two hundred ticks proves it on a valley small enough to fit in a test. The same claim on a real valley, in two processes with a database between them, is the last section of this chapter. Before that, the transaction.
The snapshot transaction
The database is where the last two chapters left it: a second container on a bridge with
no route off it, and a schema made by six numbered migrations that a run applies by
consulting a ledger. The bench asks for those migrations before it does anything else,
every time, and against a database that already has them that costs the one statement
that makes sure the ledger is there, one query to read it, and nothing else. Then it
writes the row the world table holds, because
snapshot names a world by a foreign key and the database will not take a save
for a world it has never heard of.
Nine statements go to the server for one snapshot: the row that says a save happened, and eight rows of parts. Any of them can fail. The machine can stop between any two of them. What must not be possible is a snapshot that is there and short of a part, because a restart that found one would have a valley with no seed bank in it and no way to know.
// internal/store/snap.go
// Save writes one snapshot: the row that says a save happened, and one
// row for each part of what was saved, all of it inside one
// transaction.
//
// The transaction is the whole point and it is worth being plain about
// what it buys. Nine statements go to the server. Any of them can fail;
// the machine can stop between any two of them. What cannot happen is a
// snapshot that is there and short of a part, because until the commit
// nothing any other connection can see has changed, and after it
// everything has. A restart therefore has two states to reason about
// and not three: the snapshot is there whole, or it is not there.
func (d *DB) Save(ctx context.Context, world string, tick int, parts []Part) error {
return d.save(ctx, world, tick, parts, 0)
}
func (d *DB) save(ctx context.Context, world string, tick int, parts []Part, stop int) error {
if err := Whole(parts); err != nil {
return err
}
tx, err := d.pool.Begin(ctx)
if err != nil {
return fmt.Errorf("store: saving %q at tick %d: %w", world, tick, err)
}
defer tx.Rollback(ctx)
const head = `INSERT INTO snapshot (world, tick, parts) VALUES ($1, $2, $3)`
if _, err := tx.Exec(ctx, head, world, tick, len(parts)); err != nil {
return fmt.Errorf("store: saving %q at tick %d: %w", world, tick, err)
}
const row = `INSERT INTO snapshot_part (world, tick, part, bytes) VALUES ($1, $2, $3, $4)`
for i, p := range parts {
if stop > 0 && i == stop {
return fmt.Errorf("store: the machine went away after %d of %d parts", stop, len(parts))
}
if _, err := tx.Exec(ctx, row, world, tick, p.Name, p.Bytes); err != nil {
return fmt.Errorf("store: saving %q at tick %d: the %s part: %w", world, tick, p.Name, err)
}
}
if err := tx.Commit(ctx); err != nil {
return fmt.Errorf("store: saving %q at tick %d: %w", world, tick, err)
}
return nil
}$ podman exec -w /bench world-go go run ./cmd/save -mode take
save: one snapshot, written in one transaction
the world row written: "valley", seed 5
8 parts written at tick 14851
what went in, and what came back out
part bytes sha256, first 16 read back
valley 753 383678b2fd3f339c the same bytes
bed 6360 36656fe758c26965 the same bytes
stands 19600 d2d4ebbdc07d800a the same bytes
bank 114328 a1209ddda915a9af the same bytes
air 32 74f775f4f5c490fd the same bytes
pool 2041943 271b1e94d7267ced the same bytes
roster 2667 d4ee7843705c92ce the same bytes
luck 518 42e02a427c308216 the same bytes
8 of 8 parts came back byte for byte, 2186201 bytes in all
a bytea column hands back what it was given: nothing on the way in
parsed it and nothing on the way out rebuilt it
tick parts bytes
14851 8 2186201
1 snapshot, and the tick is the only clock any of this reads
The check in the middle of that is the one the schema chapter argued for and could not
run: bytes is bytea and not jsonb, so the column's
whole job is to hand back what it was given. Eight parts went in, eight came back, and
the sixteen characters beside each are a sha256 over bytes this program is holding.
That is arithmetic over a snapshot's own bytes and not a number the database made up,
which is the difference between a figure this book may quote and one it may not.
The tick is the only clock in that listing. The snapshot table has a
taken_at column with the server's own now() as its default,
and nothing on this page selects it, because two runs of this would disagree about it
and a run whose output cannot be compared is a run that is not being checked.
A SELECT * against snapshot_part prints four million characters
of hex into your terminal and teaches you nothing. Ask about the bytes instead of for
them: octet_length(bytes) is how long a bytea value is,
sha256(bytes) is its digest as another bytea,
encode(..., 'hex') turns that into text and left(..., 16) cuts
it to something that fits on a line. \d+ snapshot_part shows the column's
storage as extended, which is Postgres saying it will compress a big value
and move it out of the row.
$ podman exec world-db psql -U world -d world -c "SELECT part, octet_length(bytes) AS bytes, left(encode(sha256(bytes), 'hex'), 16) AS sha256 FROM snapshot_part WHERE world = 'valley' AND tick = 14851 ORDER BY part;"
part | bytes | sha256
--------+---------+------------------
air | 32 | 74f775f4f5c490fd
bank | 114328 | a1209ddda915a9af
bed | 6360 | 36656fe758c26965
luck | 518 | 42e02a427c308216
pool | 2041943 | 271b1e94d7267ced
roster | 2667 | d4ee7843705c92ce
stands | 19600 | d2d4ebbdc07d800a
valley | 753 | 383678b2fd3f339c
(8 rows)
Eight rows in ORDER BY part, which is alphabetical and not the order they
were written, because a SELECT with no ORDER BY on it has no
order at all and a page quoting one is quoting whatever the planner felt like that
morning. Every digest matches the one the program worked out before it sent the bytes.
Two different machines did the same arithmetic over the same bytes and agreed, which is
rather more convincing than the program checking its own work.
Now the other half of the claim. A transaction is only interesting when something goes wrong inside it, so the bench has a mode that gives up in the middle: the same nine statements, with the connection abandoned after three of them and no commit ever sent.
$ podman kill world-db && podman start world-db world-db world-db $ podman exec -w /bench world-go go run ./cmd/save -mode botch save: a snapshot that stops half way through the world row written: "valley", seed 5 before it starts snapshot 0 rows snapshot_part 0 rows the write, with the machine going away in the middle of it save: store: the machine went away after 3 of 8 parts and what the database is holding now snapshot 0 rows snapshot_part 0 rows no snapshot, no parts, and nothing to reason about: the transaction was never committed, so none of the 3 rows it had written was ever there the same snapshot again, committed this time snapshot 1 row snapshot_part 8 rows
Three inserts reached the server and did what inserts do. The connection then went away without a commit, and the server threw all three of them out: not the parts, not the parent row, nothing. The counts before and after are identical, and there was never a moment when a second connection could have seen a half-written save. The database is killed and started first so it is properly empty; its data directory is a tmpfs, so a restart is a fresh server with nothing in it.
One transaction a snapshot, and not one a part: a part on its own describes nothing and there is no useful state between the third row and the fourth. Nor one transaction around a run of snapshots, which would hold locks for however long a world is left running and throw away a good save because a later one failed. The unit of the transaction is the unit of the thing, and the thing here is one moment of one world.
The interrupted restart run
Everything so far is a claim about one process. The claim has to be about two, and the only way to make it is to run the experiment: one valley from its founding to the end of its eighth year with nothing interrupting it, and a second valley that stops at the end of its fourth year, writes itself into the database and exits, followed by a process that never founded anything and reads that snapshot to carry on. Then hold the two against each other.
Held against each other how, exactly. Each run writes a tape: one line a year, carrying the tick, how many animals are alive, how many have been born and struck off, how many numbers the pool has drawn, and a digest folded a tick at a time over the tick number, every plant and where it stands, every creature in roster order with its position, its heading and its store, what the ground and the litter are holding, and four counters. The digest is that year's own and it is opened empty at the top of each year, because a process that starts at year five never folded years one to four and a running digest would have nothing it could match.
Each run also keeps an archive: a line for every birth and every death, written the way the evolution volume settled on. Two comparisons come out of that. The lines the interrupted run wrote before it stopped ought to be the lines the straight run wrote over the same years, and the lines the process that carried on wrote ought to be all the rest.
The database is killed and started once more before the experiment begins, for the
reason it was killed and started before the botched write: the run above committed a
snapshot of "valley" at tick 14851, and the run two boxes below
writes the same world at the same tick. The second of those is a primary key that is
already taken, and a database left holding the first one answers with
snapshot_key and no save at all. Starting the experiment from an
empty server is not tidiness here; it is the difference between the comparison
happening and not.
$ podman kill world-db && podman start world-db
world-db
world-db
$ podman exec -w /bench world-go go run ./cmd/save -mode straight -dir /tmp/save-77
save: one valley, run straight through 8 years
year 1 tick 4050 alive 11 born 45 gone 63 draws 91408 e09c3d30cfd2fd4d
year 2 tick 7650 alive 23 born 84 gone 90 draws 392048 ac9ed3eeebe1f34e
year 3 tick 11250 alive 25 born 122 gone 126 draws 1095584 39347c182b518301
year 4 tick 14850 alive 19 born 195 gone 205 draws 1331290 fef4513ca7afefed
year 5 tick 18450 alive 43 born 252 gone 238 draws 1939693 1a2611692c2fdd18
year 6 tick 22050 alive 12 born 338 gone 355 draws 2868540 354ddb516a91ef4e
year 7 tick 25650 alive 28 born 385 gone 386 draws 3202100 a0db07ee59ad5bf7
year 8 tick 29250 alive 105 born 628 gone 552 draws 7916597 6807eaa544057b83
the tape: /tmp/save-77/straight.tape
the archive: /tmp/save-77/straight.jsonl, 6000378 bytes
Eight years of a valley with two rows in it, and the population doing what the last three chapters said it would: eleven animals after the first winter, forty-three in the fifth year, twelve in the sixth, a hundred and five in the eighth. Those eight lines are what everything below has to match.
$ podman exec -w /bench world-go go run ./cmd/save -mode stop -dir /tmp/save-77
save: the same valley, stopped at the end of year 4
year 1 tick 4050 alive 11 born 45 gone 63 draws 91408 e09c3d30cfd2fd4d
year 2 tick 7650 alive 23 born 84 gone 90 draws 392048 ac9ed3eeebe1f34e
year 3 tick 11250 alive 25 born 122 gone 126 draws 1095584 39347c182b518301
year 4 tick 14850 alive 19 born 195 gone 205 draws 1331290 fef4513ca7afefed
the world row written: "valley", seed 5
8 parts, 2186201 bytes, written at tick 14851 in one transaction
the tape: /tmp/save-77/stopped.tape
the archive: /tmp/save-77/stopped.jsonl, 2045639 bytes
and this process stops here, holding nothing
$ podman exec -w /bench world-go go run ./cmd/save -mode carry -dir /tmp/save-77
save: a fresh process, carrying on from a snapshot
the newest snapshot "valley" holds is at tick 14851, in 8 parts and 2186201 bytes
restored: 124 plants standing, 19 browsers, 0 hunters, 224 genomes in the pool
year 5 tick 18450 alive 43 born 252 gone 238 draws 1939693 1a2611692c2fdd18
year 6 tick 22050 alive 12 born 338 gone 355 draws 2868540 354ddb516a91ef4e
year 7 tick 25650 alive 28 born 385 gone 386 draws 3202100 a0db07ee59ad5bf7
year 8 tick 29250 alive 105 born 628 gone 552 draws 7916597 6807eaa544057b83
the tape: /tmp/save-77/carried.tape
the archive: /tmp/save-77/carried.jsonl, 3954739 bytes
it founded nothing, scattered nobody and drew no founding number:
every number in it came out of 2186201 bytes of snapshot
The second process is a different process. It generated the terrain out of three numbers, opened nine generators and loaded twenty bytes into each of them, priced two hundred and twenty-four genomes back into animals through the same function a founder goes through, and started ticking. It never scattered a founding population and never drew a number off streams 12 or 22, which are the two things a founding does. Its first line is year five, and every figure on it is the figure the straight run printed for year five: forty-three alive, two hundred and fifty-two born, two hundred and thirty- eight struck off, 1,939,693 numbers drawn, and the same sixteen characters of digest.
$ podman exec -w /bench world-go go run ./cmd/save -mode same -dir /tmp/save-77
save: the run that was interrupted, against the run that was not
the tapes, a line a year
bytes sha256, first 16
straight through, the whole run 792 3bfcdae4f1f5cbbb
of it, the years up to the snapshot 396 6709b7edc37c7fe9
what the run that stopped wrote 396 6709b7edc37c7fe9
the same bytes, and therefore the same run
of it, the years after the snapshot 396 4e111692e8ce173a
what the process that carried on wrote 396 4e111692e8ce173a
the same bytes, and therefore the same run
the archives, a line a birth and a line a death
bytes sha256, first 16
straight through, the whole run 6000378 d58a4dfadac7fffd
of it, up to the snapshot 2045639 39faba8f3d234b23
what the run that stopped wrote 2045639 39faba8f3d234b23
the same bytes, and therefore the same run
of it, after the snapshot 3954739 35abcb939c262e71
what the process that carried on wrote 3954739 35abcb939c262e71
the same bytes, and therefore the same run
Four comparisons and four agreements. The interrupted run and the straight run wrote the same 396 bytes of tape over their first four years, which says nothing about snapshots and everything about the seed. The interesting ones are underneath: 396 bytes of tape and 3,954,739 bytes of archive written by a process that was not alive when the world was founded, matching the run that was, to the byte. Four hundred and thirty-three births and every one of them in the same order, with the same parents, the same species numbers and the same innovation numbers on the same links.
That is the claim from the first page of this chapter, run. The world that stopped and the world that did not are one world, and whatever time passed between the two processes is not in the tape anywhere, because it is not in the world.
Everything above rests on when the snapshot was taken. So take the same world's snapshot once at the boundary and once in the middle of the phase that follows it, and run both. The mid-phase one is taken through the seam a valley leaves for whatever lives in it, after the view has been built and before a single creature has been stepped, which is about as early inside a phase as it is possible to be.
$ go run ./cmd/save -mode torn | tail -45 | head -22
save: a snapshot taken in the middle of a phase
a 16x12 valley at the end of year 4, and the tick after it
the two snapshots
part boundary mid-phase
valley 753 753 different bytes
bed 6360 6360 different bytes
stands 19600 19600 different bytes
bank 114328 114328 the same bytes
air 32 32 the same bytes
pool 2041943 2041943 the same bytes
roster 2667 2667 the same bytes
luck 518 518 different bytes
2186201 2186201
Both of them name tick 14851. Both are the same size, both hold all eight
parts, and neither of them has anything wrong with it that a reader could
point at. What is different is what tick 14851 means: the first was taken
before any of it had happened and the second half way through it, with the
plants already fed and their income in the books, which went from
426522.6916 grams to 426596.6832.
The first thing to notice is that nothing is wrong. Both snapshots are 2,186,201 bytes. Both hold eight parts. Both name tick 14851. Every check this chapter has written passes on both of them, because every one of those checks is about whether a snapshot is complete, and this one is.
The second thing is which four parts came out different. The bed and the stands, because the plants of tick 14851 have already taken their water and their minerals and grown on them. The valley, because their income is in the books. And the luck, because the plant half of a tick draws from germination and from plant mortality, so two of the nine generators have already been spent on a tick that is about to be run again.
$ go run ./cmd/save -mode torn | tail -22 | head -16
and both of them run on beside the world that wrote them
tick from the boundary from mid-phase
14851 ebb6904bdd7d8ac1 3d57f9c753fed96c not the same tick
14852 bc95862f9b980844 32dafc983a973ad5 not the same tick
14853 5c7427557191213e b17737c888c8f3d0 not the same tick
14854 dd400d049b00b8bb 6597b2045ddd6073 not the same tick
14855 e37b1076f6e6a10b fb5ee8d05c6ec1d7 not the same tick
the books at the end of those 5 ticks
grams manufactured out of light, from the boundary 426893.5375
grams manufactured out of light, from mid-phase 426967.0961
the difference 73.5586
Seventy-odd grams of tissue that nothing grew: the second world ran the
first half of tick 14851 twice, and the books counted both of them.
The two part company on the first tick they take, and the reasoning from that symptom
back to the cause is short. A restored world starts by calling Tick, and
Tick runs a whole tick: the calendar, the light, the plants, the phase, the
weather. The world restored from the boundary runs tick 14851 for the first time. The
world restored from the middle of the phase runs the first half of tick 14851 for the
second time, and there is no way for it to know that, because a snapshot is a set of
numbers and not a diary. Seventy-three grams of plant tissue exist in the second world
that nothing in it ever grew, and the audit that has balanced since the terrarium
volume now has a hole in it the size of one tick's photosynthesis.
The cure is not a check inside Take. There is nothing for such a check to
read: the valley does not know whether it is half way through a phase, and a flag that
said so would be one more thing every tick has to keep true, which is the sort of
bookkeeping that is right for a year and then is not. The cure is where the call sits.
The loop that runs a world has exactly one place a snapshot can go, after
Tick returns and before the next call, and a rule about where a line of
code lives is kept by reading the code rather than by running it.
Why snapshots need consistent moments
Underneath the eight parts and the transaction there is one idea, and it travels a long way past valleys. A running system passes through moments when everything it holds is consistent and moments when it is half way through making that true, and the second kind is much more common than people expect. Saving state is only difficult because somebody tried to do it during the second kind. Find the moment when nothing is in flight, put the save there, and most of the difficulty stops existing instead of getting solved.
The mint's table is the clearest example of what that buys, and it generalises into a rule you can apply to code you have never seen: state that cannot be read again does not have to be written down. Anything reachable only through a call that clears it, anything an operation empties as it spends it, anything derived from what you have already saved. The valley's light field is rebuilt from the plants at the top of every tick; the roster's index is refilled before every phase; the pool's sorted link lists are a cache of what the genomes already say. None of those are in a snapshot and all of them are correct a tick later. Working out which of your program's fields are like that is most of the design, and the answer changes depending on where you take the save, which is why the boundary comes first and the list comes second.
The second idea is the split between what a snapshot holds and what the program is. A snapshot here holds what a tick can change. It does not hold the price of a mouthful, the compatibility threshold, the founding rows of either table or what wariness costs: those are the world's laws, they live in code, and a snapshot that carried a copy of them would be a second opinion about the rules that can disagree with the first. What it carries instead is a digest of all of them, so that a world restored into a program whose rules have moved is refused with both digests in the message. Complete and self-describing are different goals, and a system that tries for both usually gets neither.
The third is what a transaction is for, put more plainly than a database manual usually puts it. A transaction is there so that the number of states your program has to reason about after a crash stays small. Nothing else was writing to this database while that snapshot went in, so the concurrency half of the story never came up, and the guarantee was still the whole point. Nine statements have ten places to stop between them. One transaction turns those ten into two, and the code that reads the result afterwards gets to be an if-statement instead of a recovery procedure.
And the fourth is a lesson about proof, which is the one this book keeps arriving at from different directions. There was no argument available that would have convinced anybody that a restart is exact. Reading the eight parts and nodding at them proves nothing; a list of what is in a snapshot is exactly the kind of thing that looks complete right up until the run where it is not. The only thing that settles it is two runs and a comparison, and the comparison has to be over something detailed enough to catch a single number moving. A tape folded a tick at a time over every body in the valley is such a thing. A population count is not.
- Say what is open in the middle of a creature phase that is not open between two ticks, in terms of the four things the phase is holding when it is four creatures in.
- The mint's table is not in a snapshot and the mint's counter is. Give the reason, and say what a snapshot taken in the middle of a breeding pass would have to carry that this one does not.
- A generator's state is twenty bytes: four and sixteen. Say what each group is for, and why the four in front are there at all.
- The terrain is not in the snapshot and the seed bank is. Both are properties of the ground. Say what separates them.
- Nine statements write one snapshot. Say what the transaction around them buys, in terms of how many states a restart has to be able to handle.
- Given the run on this page, work out what fraction of a snapshot is generator state and what fraction is genomes, and say which of the two numbers grows as a world gets older.
Exercise 1 — leave a different generator out. The bench restores a world twice and opens one of the nine generators fresh instead of putting it back. With mutation left out the two worlds run as one for 168 ticks. Predict what happens with plant mortality, which is drawn for every standing plant every single tick.
It takes longer than one tick, which is the part to keep in view. The two worlds draw the same count of numbers off stream 10 on every tick; what differs is the values, and a different value only shows up in the tape when it lands on the other side of a threshold and a plant that was going to live dies instead.
$ go run ./cmd/save -mode luck -fresh 'plant mortality' | tail -13
ticks the two of them ran as one world 56
the tick they parted on 14907
births on that tick 0
and 400 ticks on from the restore
restored whole c79d09c6fe0da253 alive 21 born 198
stream 10 left out 78e10314ff07b81c alive 21 born 198
A generator opened on the same seed and the same stream number is not the
same generator. The one this run was holding had been drawn from since the
first tick; the fresh one is standing at the beginning of the world, and
the two of them part company the first time anything asks stream 10 for a
number.
Fifty-six ticks. Now run it with -fresh germination and watch four
hundred ticks go by with the two worlds still identical, because a seed only asks
that generator anything in the part of the year when a seed would try. Both worlds
have the same number of animals alive and the same number born at the end of it,
and neither is the world that wrote the snapshot. A forgotten generator does not
announce itself; it waits.
Exercise 2 — how much of a snapshot is age. The snapshot on this page was taken at the end of year 4 and came to 2,186,201 bytes. Before you run anything, predict which parts are smaller at the end of year 2 and which are exactly the same size.
The bed is fixed for the life of a world: two numbers a cell for the soil and two for the litter, whatever is happening on top of them. The pool grows every time anything is born and never shrinks, because a dead creature's genome does not leave it. The bank and the stands move with the season rather than with the age.
$ go run ./cmd/save -mode parts -after 2 | tail -52 | head -12
the eight parts, in the order they are put back
part bytes share what is in it
valley 753 0.07% the clock, the dials an operator set, both sets of books
bed 6360 0.57% two numbers a cell, and the litter lying on top of them
stands 19284 1.73% every plant standing, and what its last tick came to
bank 46920 4.21% every seed waiting in the ground
air 32 0.00% every seed still falling
pool 1038554 93.09% every genome it holds, the dead ones included
roster 3215 0.29% every creature walking, and every number on it
luck 518 0.05% the generators, at twenty bytes apiece
1115636 100.00%
a snapshot of this world is 1115636 bytes and 93.1% of it is genomes
The bed and the valley and the luck are the same to the byte. The pool has roughly doubled, and it will keep doing that for as long as anything breeds. Two years further on there are fewer animals walking about and more genomes in the pool, which is a sentence about history and not about population.
Exercise 3 — ask the database how big a save is. The bench printed 2,186,201 bytes before it sent anything. Write the query that adds the parts up on the server side, and get the same number without trusting the program that wrote them.
sum(octet_length(bytes)) over the rows of one save, grouped by tick so
that a database holding several saves answers about each of them separately. The
ORDER BY is not decoration: without it the rows come back in whatever
order suited the server.
$ podman exec world-db psql -U world -d world -c "SELECT tick, count(*) AS parts, sum(octet_length(bytes)) AS bytes FROM snapshot_part WHERE world = 'valley' GROUP BY tick ORDER BY tick;"
tick | parts | bytes
-------+-------+---------
14851 | 8 | 2186201
(1 row)
Then try it with the GROUP BY taken out and see what the server says,
and with count(*) replaced by count(bytes), which counts
the rows where that column is not null and is the same number here only because the
column is NOT NULL.
There is a world in the database now and it is one row and eight blobs. Two megabytes of it are genomes, every genome this valley has ever handed out, and not one of them can be asked a question: the pool part is a single value under a single name, fetched whole or not at all, exactly as designed. Meanwhile the creature table that the schema chapter argued into existence, with its seven integer columns and its four indexes, is still empty. Everything this world knows about who came from whom is sitting in a blob, and answering the simplest question anybody has about a lineage still means reading a file from the beginning.