Introducing bgpkit-snap: A Prefix Table in One File
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.
| Measurement | Result |
|---|---|
| object | 7.64 MiB |
| build | 34.9 s to parse the MRT with bgpkit-parser, single-threaded, then 0.04 s to encode |
| open | 7.5 ms, including the header and layout checks, the content id, and rkyv bytecheck of both tries |
| longest-prefix match | 36 ns mean over 40,000 lookups, per-lookup p99 under 100 ns |
| walk every prefix | 19.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())?;
scroll the figure sideways to see all of it
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.
scroll the figure sideways to see all of it
- 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.
scroll the figure sideways to see all of 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.
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
Lockedrather 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
- Tool page: bgpkit.com/tools/snap
- Source: github.com/bgpkit/bgpkit-snap
- Format document:
docs/format.md; usage guide:docs/usage.md
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.