Research notes

The density problem

Everything in this section descends from one measurement.

A node that executes every block writes a new version of each trie node it touches. The store is content-addressed, so those versions accumulate and a block's working set scatters uniformly across the whole database. On RSK mainnet that gives an archival store of 131 GB and 1.25 billion entries, of which the nodes reachable from the current state root — the live set — are 0.87%. Consecutive live nodes sit roughly 115 stored entries apart.

Traversal throughput then tracks that density rather than the algorithm:

This matters well beyond disk cost. Re-executing the chain to check that a change has not broken consensus backwards is the core development loop of a second client, it is read-bound, and the reads are the worst kind: a trie descent issues dependent random reads, so the device sees one outstanding request at a time. A 29× penalty on that loop is a 29× penalty on the project.

Epoch-based garbage collection

A design for reclaiming space in a store that holds every historical version of the state trie — originally worked out for rskj, written up as a specification with a correctness argument, failure and recovery analysis, and cost model, then implemented in Rustock and measured.

Result

Experiment 2, 800 blocks of a synthetic high-churn workload, both backends identically configured:

Smaller store, no throughput penalty, and warm random reads roughly twice as fast — the last of which is the density effect running in reverse.

Range-segmented trie store

proposal A different attack on the same problem: instead of collecting garbage, reorder the same data by block number rather than by hash. Each segment holds exactly the nodes some block range touches, so density within a segment is close to 100% and the working set is small enough to stay resident.

Nothing is implemented beyond the measurement tool (cargo run --example trie_footprint), and the write-up is explicit about that. It also contains a case worth reading on its own: a tool that executes blocks without validating them proves the state transition and nothing else — and the distinction mattered in practice.

The proposal, with measurements →

Sync parallelism

Rustock's forward sync keeps rskj's shape — connection point, skeleton, chunks, bodies, execute — and parallelises three places rskj does not:

• Header chunks across every peer, four requests in flight each, with responses matched to chunks by content rather than arrival order and drained back into strict order before they touch the store. rskj uses one peer, one request at a time.
• Bodies overlapped with execution, so the network is not idle waiting for the EVM.
• Pipelined chunk refills — every peer is topped back up to capacity each round rather than at the end of a batch.

The write-up sketches how each could be ported back to rskj, which is the more useful half: Rootstock gets nothing from Rustock being faster, and something from rskj being faster. Read it →

FlatDB: a trie store that stores no keys

A port of rskj's co.rsk.flatdb to Rust, and the largest single win of the three storage-performance levers below. It is a store for data whose key is the hash of its value, and every structural decision follows from that plus three facts about the workload: no deletions, no range queries, no mutation.

What that buys is unusual. The index stores no key bytes at all — just a table of 8-byte slots. A probe resolves a collision by fetching the candidate record and recomputing H(value), which means every successful short-record read is also a verification of the bytes against their own address. A corrupted record cannot be returned as if it were correct.

The precondition was checked rather than assumed. Rustock's trie store makes exactly two kinds of write, and converting the benchmark fixture copied 9,299,999 of 9,299,999 nodes with none skipped — the converter skips any entry whose key is not its value's digest. On the real mainnet store it copied 25,371,307 nodes across three epochs, also none skipped. The invariant holds in fact, not only in design.

On disk it is four files: an append-only mmap'd heap, an open-addressed index, a flock on the directory, and one double-buffered CRC'd checkpoint record. A flush is three ordered steps — heap, then index, then checkpoint — and the checkpoint is the only thing that makes a batch real, so a crash between steps loses the batch rather than half of it. Torn sectors are tested by tearing real ones rather than simulating a crash.

What real data did to the headline

The fixture said reads were 3.5× faster. Re-measured against the real mainnet epoch store — same data both sides, same state root, same disk, page cache dropped by name before each run, medians of three:

Batched they are a dead heat, 2.5% apart and inside the run-to-run spread. The 3.5× did not survive contact with real state. The fixture had been built bottom-up, so the top of its trie sat contiguously at the end of the heap and a walk was nearly a sequential read; a real store is written in traversal order over months and spread across three epochs, and that locality is gone.

Serially FlatDB is still 1.76×, and that is not a consolation prize — block execution issues dependent reads and cannot batch them, so the serial column is the one execution actually lives in. But 1.76× is the number to carry.

The bottleneck that looked like a lock

Four threads on four cores reached 99% CPU — about one core's worth — which looks exactly like a lock. FlatDB had an obvious candidate: a writer mutex held across the probe, the key comparison, the heap append and the slot store, roughly 6,900 times a block. It was removed, in favour of claiming space with a CAS and publishing slots with a compare-exchange.

The mutex was not the bottleneck. It existed, it did serialise writers, and removing it bought nothing measurable — scaling went from 1.09× to 1.12×, inside the spread. The lock-free write path is kept because it is better structure and measures no worse, but the performance claim attached to it is withdrawn.

What only production data could find

Two things the fixture could never have surfaced, both found by converting the real store.

• Long records had never been exercised. The fixture contains none at all, and a trie walk does not reach them either — a long value hangs off a node's value hash rather than being one of its children. The real store holds 5,589, 450 and 475 across its three epochs, up to 24 KB of contract code. Read back explicitly through the path that recomputes H(value): all verified, none failed.
• The record-size constant was wrong. 80 bytes came from the fixture; the real mean is 73.5, so the key count sat 9% above the estimate. It is now 72, rounded down deliberately, because the figure is a divisor and under-estimating it over-sizes the index — which is the cheap error.

--trie-engine flatdb selects it, and the default stays rocksdb. It is marked experimental for one precise reason: it has not run on a real chain. The node refuses to start if the directory was written by the other engine rather than opening an empty store beside the data, and the mainnet rollout is deliberately staged — phase 0 is the new binary on the unchanged RocksDB configuration, so the engine change can later be measured on its own rather than credited with eleven commits of unrelated work.

Making a block faster, and the defect worth more than three ways of trying

FlatDB above is one of three levers, and they were investigated separately before turning out to be the same investigation: executing RSKIP-144 sublists in parallel, replacing the trie store, and prefetching a block's access list. Each was measured alone and all three together.

They do not add up. Measured against one thread on RocksDB, 100 synthetic blocks of 200 native transfers against a 1 GB state:

The levers do not compose, and the reason is the finding. All three are ways of not waiting on a dependent trie read. Once one of them has removed the waiting, the others have nothing left to remove — which is why all three together are worse than the best two.

The thing none of them was about

Profiling the three eventually pointed at a line of code that was not a lever at all. Applying a block's changes to the trie took time quadratic in the number of accounts the block touched, because NodeRef::Node held a Box<TrieNode> and a Box cannot share — so every descent deep-copied the subtrees it passed. One Arc later the commit is 15× cheaper and a block 3.4× faster end to end, which is worth more than the three levers put together.

It also moved the conclusions. "The best configuration uses one thread" was an artefact of a cost four sublists paid four times; re-measured, one thread and four are indistinguishable with the list prefetched, and four threads win 1.47× without it. Adding threads is no longer a loss — it is still not, on this evidence, a reason to add threads.

What the measurements cost in retracted claims

This is the part worth publishing. Three written conclusions in this area did not survive repetition: a batching speedup of 1.16–1.80×, a writer mutex said to be holding back parallelism, and a regression filed as an issue and closed the same way. All three came from single runs, and all three made the story more interesting than the truth happened to be. FlatDB's 3.5× read advantage went the same way — re-measured against real mainnet state rather than a bottom-up fixture, it is 1.76× serially, and batched the two engines are a dead heat.

Why the workload is synthetic

Two reasons, each disqualifying alone. Mainnet has no partitioned blocks — RSKIP-144 is unscheduled there, so no mainnet header has ever carried a non-empty edges field. And testnet's are too small to measure: of 1,020,420 canonical headers above its activation height, 203,419 split, but their edges are [1], [1, 2], [1, 3] — one or two transactions per sublist at about 45,000 gas. Dividing one transaction between two threads measures the cost of starting a thread.

On today's mainnet there is nothing to measure at all: blocks run at roughly 1% of the gas limit, and a node in follow mode executes one in 38 ms and then idles for thirty seconds.

Test coverage against rskj

The project publishes the comparison rather than the headline, because the ratio is not the interesting part — where it is worst is.

A ratio below one is expected: rskj is a decade old and carries a miner, its own bitcoinj fork, a Solidity compiler bridge and an RPC surface Rustock does not implement. What is not expected is a low ratio lining up with code no test has ever executed — and in several places it does.

The document exists because of one such place. While implementing the Bridge's federation-address getters it turned out that getFederationAddress was a stub returning raw serialized bytes, and that no caller could reach it anyway, because Rustock had rskj's local-call gate without rskj's local-call flag. Two defects, both surviving because eth_call had no test at all. The obvious next question — what else is untested, and therefore possibly unimplemented or wrong — is what the comparison answers.

It is also careful about its own limits: counting test functions rewards granularity rather than thoroughness, and an area showing zero can be a mapping artifact between two different module trees. Every zero was checked by hand before it was reported. The full comparison →

Upstream disclosure

Replaying nine years of mainnet finds things about the client that produced it. One was written up and sent to the rskj team.

This is, in a small way, the argument for client diversity that does not depend on Rustock ever being used in production. A second implementation reads the first one's behaviour out of the chain itself, and what it finds is useful to everyone regardless of which client anybody runs.