Introducing bgpkit-snap: A Prefix Table in One File

· Mingwei Zhang
release snap

On one RouteViews RIB, 941,112 prefixes fit in 7.64 MiB and open in 7.5 ms. There is no service to run: open the file and query it.

bgpkit-snap is a Rust library and CLI that writes a prefix table to one immutable file: the prefixes, a value of your type at each one, and a 192-byte header that says what the file is. It removes two things our archives kept paying for. A RIB dump, a ROA set or a prefix-to-ASN map has to be parsed before any question can be answered, and a database index only answers while its machine, its version and its maintenance window stay put.

Copy the file and the copy answers; a journal of inserts and withdrawals keeps it current without a rebuild. What that costs instead is stated up front: a build holds the tree in memory, an open object holds its bytes in memory, one journal takes one writer, and one object carries one value type.

Measured on one RIB

A RIB from the RouteViews amsix collector, 2020-06-17 18:00 UTC, with origin ASNs as the values: 19,566,193 announcement entries, one per announcing peer, covering 941,112 unique prefixes.

MeasurementResult
object7.64 MiB
build34.9 s to parse the MRT with bgpkit-parser, single-threaded, then 0.04 s to encode
open7.5 ms, including the header and layout checks, the content id, and rkyv bytecheck of both tries
longest-prefix match36 ns mean over 40,000 lookups, per-lookup p99 under 100 ns
walk every prefix19.9 ms, reading archived values without decoding them

AMD Ryzen 9 3950X, release build, single thread, files in page cache. No baseline against a database or a loaded Parquet file: this says what this file costs to build and serve, not whether it beats another engine.

Using it

use bgpkit_snap::{snap_value, Opts, Snapshot, Writer};

#[snap_value("demo.origin:v1")]
#[derive(Debug)]
struct Origin(u32);

let mut w: Writer<Origin> = Writer::new();
w.insert("8.8.8.0/24".parse()?, Origin(15169))?;
w.insert("1.1.1.0/24".parse()?, Origin(13335))?;
w.finish_to("origins.snap", &Opts::now())?;

let snap: Snapshot<Origin> = Snapshot::open("origins.snap")?;
let (prefix, origin) = snap.owned().search("8.8.8.8".parse()?)?.unwrap();

The value type is one attribute: #[snap_value] adds rkyv’s derives and the type id, so the crate that uses it needs no rkyv dependency of its own. Everything the trie offers is available on the file: longest-prefix and shortest-prefix match, exact lookup, covering entries, children under a prefix, iteration from a prefix, a full walk, and address-space counts. Both address families are dispatched for you: search takes an address, lpm takes a prefix. Opening reads the file into memory and keeps it there, so a reader pays about the file size in RAM; after that reads are zero-copy, and snap.owned() decodes a value when you want to keep it.

The CLI builds and inspects objects:

bgpkit-snap build prefixes.jsonl --out table.snap --value u32
bgpkit-snap info table.snap
bgpkit-snap stats table.snap
bgpkit-snap verify table.snap

It has no query command: a query depends on what a value means, and only the program that declared the type can answer it. The CLI knows the five integer types and can check their bodies; anything else it verifies as a container and stops.

Keeping it current

A snapshot cannot be edited, so a feed of changes would mean a full build per batch. The journal is that something: an append-only record of inserts and withdrawals over one base object, folded back into a complete file when you checkpoint.

use bgpkit_snap::journal::Journal;

let mut log: Journal<Origin> = Journal::attach("origins.snap", "origins.journal")?;
log.insert("192.0.2.0/24".parse()?, Origin(64512))?;
log.withdraw("1.1.1.0/24".parse()?)?;
log.sync()?;                          // durable from here
let next = log.checkpoint(&Opts::now())?;
objects journal directory base snapshot table.snap · content id A never modified table.journal ── log of changes dense sequence numbers, one CRC32C per record base + log, at checkpoint appends: insert · withdraw · sync new snapshot snapshot-4-1.snap · content id B readers open current.snap the link moves only after state.json names the new object the checkpoint verifies the new object against the live tree before state.json names it, then prunes the segments it covers

scroll the figure sideways to see all of it

One base, one log, one next object. The base is never modified, and the reader's path moves only after state.json names the new object.

On the command line the journal has four verbs of its own:

bgpkit-snap journal init table.snap table.journal
bgpkit-snap journal append table.journal changes.jsonl
bgpkit-snap journal status table.journal
bgpkit-snap journal checkpoint table.journal

The base is recorded by content id: until the first checkpoint the journal cannot be opened without that object, and a base that was replaced is refused instead of silently adopted. Journal::start(dir, tree_id) is the empty-base case, for a stream that has no file yet.

The shape a service ends up in is one object being served while changes arrive, and it works because the two sides are separate handles:

let mut current: Snapshot<Origin> = Snapshot::open("origins.snap")?;   // read side
let mut log: Journal<Origin> = Journal::attach("origins.snap", "origins.journal")?;

log.insert("192.0.2.0/24".parse()?, Origin(64512))?;
log.sync()?;

// the loaded object did not change: readers keep the answers they had
assert!(current.owned().lpm("192.0.2.1/32".parse()?)?.is_none());

let next = log.checkpoint(&Opts::now())?;   // a complete new object
current = Snapshot::open(&next)?;           // the reader moves by reopening

Nothing updates in place. A checkpoint writes a complete object, verifies it against the live tree, records it in state.json and republishes current.snap. The process that holds the journal answers from the live tree, because the writer lock is exclusive; everyone else keeps serving the file they opened, and a reader moves by reopening the new object. examples/live.rs runs this flow and asserts each step.

The design, byte by byte

The container is ours; the tries are not. A file is a 192-byte header, a section table, then one archived trie per address family. The tries come from prefix-trie, laid out by rkyv; what this crate adds is everything around them.

header 192 B 0 section table N × 64 B v4 trie rkyv archive v6 trie rkyv archive counts 32 B profile sections 0 or more end each section starts on a 16-byte boundary; padding must be zero

scroll the figure sideways to see all of it

One object, start to end, and not to scale. Violet is the container; blue is a payload archive this crate reads through rkyv.
  • header : fixed size, everything above
  • section table : one row per section, ascending ids
  • v4 trie : prefix-trie map, archived by rkyv
  • v6 trie : same, for IPv6
  • counts : entry count, so stats needs no value type
  • profile sections : id 16 and up, owned by the profile

The header is fixed at 192 bytes, which makes identification one small read: a reader knows the value type, the file size, the section count and whether the object came from a journal before it touches the body.

0 8 16 24 0 32 64 96 128 160 magic 0…7 ver, flags 8…11 tree id 12…27 generation 28…43 ↳ generation 28…43 base seq 44…51 value type id 52…83 ↳ value type id 52…83 file len 84…91 sections 92…95 table 96…99 window 100…115 reserved 116…147 ↳ reserved 116…147 created at 148…155 content id 156…187 ↳ content id 156…187 crc 188…191

scroll the figure sideways to see all of it

The 192-byte header. Everything above the dashed line is hashed into the content id, together with the section table and every section body; created_at, the id itself and the CRC follow it.

Three ideas carry the format.

Sections. The body is a table of sections, each described by one 64-byte row. Sections are packed in ascending id order and each starts on a 16-byte boundary. Ids 2 and 3 are the two tries, id 4 is the entry count, and 16 and up belong to whoever writes the file. A reader that does not implement a section skips it unless it is marked required, in which case the object is refused. Optional sections are how the format grows without breaking a reader that predates them.

Each row is 64 bytes: id, kind, flags and length in the first 16, then 48 reserved zeros.

A coverage window. Two i64 unix seconds sit in the header, meaningful only when the window flag is set. A consumer that merges two objects, or decides whether an answer is stale, needs to know what period the data describes; without it that fact lives in a sidecar that gets lost when the file moves.

Profiles. A section id of 16 or more belongs to the caller. The container carries the bytes and does not interpret them; a reading program implements Validator for the ids it knows and opens the object with it. A second table with a different value type lives there, and so does the blob arena a journal uses.

Verification

A file you can check is a file you can hand to somebody else. Verification runs in four layers, cheapest first.

1. Container
needs nothing but the bytes: magic, version, header fields and CRC, layout against file length, section table, content id · costs one pass over the file
2. Typed
needs your value type: type id match, rkyv bytecheck of both trie archives, profile cross-checks · costs one validated open
3. Content
needs a decoder for the value: every value decoded and counted, compared with the count the object records · costs walks the whole table
4. Journal
needs the base object: per-record CRC32C, dense sequence numbers, checkpoint verified before it is named, base identity · costs pays at every open
Four layers, cheapest first. The CLI can stop after the first for a foreign value type because that layer needs no value type at all, not because the layers nest.
use bgpkit_snap::verify_bytes;

let raw = std::fs::read("table.snap")?;
let header = verify_bytes(&raw)?;     // Err(ContentId) if one byte changed

What it does not prove: that the data is true, since a content id only says “these are the bytes”; who wrote it, since there is no signature; or where it came from, since created_at and the coverage window sit outside the content id, so a re-dated copy keeps the same id. On a value type the CLI does not implement, verify checks the container and says so.

What it is not

  • Not a database. No query language, no update in place, no transaction. You get a trie and you write the loop.
  • Not an out-of-core builder. A build holds the tree in memory, so the table has to fit in RAM, and a checkpoint builds a new object the same way.
  • Not a multi-writer system. One journal directory takes one writer; a second gets Locked rather than a corrupted log. Readers never take the lock.
  • Not a mixed-type table. One value type per object. A second table with different values is a profile section the reading program has to be told about, and that is a real cost.

Get it

bgpkit-snap 0.2.0 is on crates.io and docs.rs. The Rust interface is pre-1.0 and will keep changing while we use it; the bytes are the contract, documented in docs/format.md, and the format version has stayed at 4 since 0.1.

# the derive feature brings #[snap_value], and rkyv stays out of your manifest
bgpkit-snap = { version = "0.2", features = ["derive"] }
cargo install bgpkit-snap --features cli

If you have a table that keeps being rebuilt, or an index that keeps being copied by hand, we would like to hear what shape it is and where the current path hurts.