A prefix table in one file: built once, queried where it sits, and kept current by a log.
Ship it
One file and one content id. No service to run, and nothing to build on the reader side.
Query it
The whole trie in place: longest-prefix match, covering entries, children, a full walk. Microseconds per lookup.
Keep it current
Append what changed, sync, and checkpoint into the next
object. Readers keep serving the object they hold.
Built on rkyv and prefix-trie. The container around them is ours: header, section table, content id, journal.
Quick start
The derive feature is what brings
#[snap_value].
# the derive feature brings #[snap_value], and rkyv stays out of your manifest
bgpkit-snap = { version = "0.2", features = ["derive"] }
# the CLI
cargo install bgpkit-snap --features cli Build once, read many
A snapshot is an immutable object: a prefix trie plus your values, in one file. Build it once from a RIB, a CSV, or a crawl, then answer lookups against the file instead of reprocessing the source.
use bgpkit_snap::{snap_value, Opts, Snapshot, Writer};
// one attribute: it adds rkyv's derives and the type id, so this crate needs no rkyv
#[snap_value("demo.origin:v1")]
#[derive(Debug)]
struct Origin(u32);
fn main() -> Result<(), Box<dyn std::error::Error>> {
// build once: any key -> value table, written to one file
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())?;
// read many times: open the file and ask
let snap: Snapshot<Origin> = Snapshot::open("origins.snap")?;
let (prefix, origin) = snap.owned().search("8.8.8.8".parse()?)?.unwrap();
println!("{prefix} -> AS{}", origin.0);
Ok(())
} What it is for
- • A prefix table that ships as a file: no service, no database, no index build on the reader side.
-
• Values are any type you mark with
#[snap_value]: a peer count, origins, ROA sets, flags. - • A journal for the part that changes: append updates, sync, checkpoint when you like.
- • One binary to build, inspect and verify any object, whatever wrote it, and four verbs to keep one current.
# one JSON object per line: {"prefix": "..", "value": n}
bgpkit-snap build prefixes.jsonl --out table.snap
# any object, whatever wrote it: what is it, what is in it, is it intact
bgpkit-snap info table.snap
bgpkit-snap stats table.snap
bgpkit-snap verify table.snap
# one JSON object per command, for scripts and agents
bgpkit-snap --json stats table.snap | jq '{type_id, entries, v4_entries, v6_entries}' The whole trie, not a subset
Snap is a container around a compressed prefix trie, and every trie operation is
available on the file directly: longest-prefix and shortest-prefix match, exact
lookup, covering entries, children under a prefix, a full walk, iteration from a
prefix, and address-space counts. Both address families are dispatched for you, so
a query takes an IpNet and the right trie answers.
use bgpkit_snap::{Opts, Snapshot, Writer};
let snap: Snapshot<Origin> = Snapshot::open("origins.snap")?;
// Origin is the value type from the quick start. Snapshot<Origin> answers with
// archived values; snap.owned() decodes them into Origin.
// by address: longest-prefix match
snap.search("8.8.8.8".parse()?); // Some((8.8.8.0/24, &archived value))
// by prefix
snap.lpm("8.8.8.0/25".parse()?); // most specific entry covering it
snap.spm("8.8.8.0/25".parse()?); // the least specific one
snap.get_exact("8.8.8.0/24".parse()?); // only the entry stored right here
snap.cover("8.8.8.0/25".parse()?); // every entry covering it
snap.children("8.8.0.0/16".parse()?); // every entry under it
snap.iter(); // the whole table
snap.iter_from("8.8.0.0/16".parse()?, true); // from a prefix upward
snap.values(); // just the values
snap.address_counts(); // how much of the space is covered
// values come back as T through the owned view, decoded only when you ask
let (prefix, origin) = snap.owned().search("8.8.8.8".parse()?)?.unwrap(); | call | the question it answers | back |
|---|---|---|
search(addr) | what covers this address | (IpNet, T) |
lpm(prefix) | the most specific entry covering it | (IpNet, T) |
spm(prefix) | the least specific entry covering it | (IpNet, T) |
get_exact(prefix) | what is stored right here, no fallback | T |
cover(prefix) | every entry covering it | Vec<(IpNet, T)> |
children(prefix) | every entry under it | Vec<(IpNet, T)> |
iter() | the whole table | Vec<(IpNet, T)> |
iter_from(prefix, ..) | from a prefix upward | Vec<(IpNet, T)> |
values() | just the values | Vec<T> |
address_counts() | how much of the space is covered | AddressCounts |
- • Reads are zero-copy: opening validates the archives once, and every query after that touches the mapped bytes instead of rebuilding an index.
-
•
Snapshotanswers with archived values;snap.owned()answers with your ownT, decoded per value. -
• A second trie with a different value type lives in a profile section, queried
with the same
lpm,get_exactanditerthroughsection_trie::<U>(id). - • What it is not: a query language. There is no filter, join or projection; you get the trie and you write the loop.
Continuous updating
A snapshot cannot be edited, so without something else one changed prefix would mean one full build. The journal is that something: an append-only record of inserts and withdrawals over one base object. A checkpoint folds base and log into a complete new object, so the file a reader opens is always a real snapshot with a real content id, never a replayed log.
scroll the figure sideways to see all of it
Writing
use bgpkit_snap::journal::Journal;
// the log keeps one object current: origins.snap is the base
let mut j: Journal<Origin> = Journal::attach("origins.snap", "origins.journal")?;
j.insert("8.8.8.0/24".parse()?, Origin(15169))?; // append one change
j.withdraw("1.1.1.0/24".parse()?)?; // and one withdrawal
j.sync()?; // durable on return
j.checkpoint(&Opts::now())?; // base + log -> next object Serving and recovering
# attach a log to an existing object, then keep it current
bgpkit-snap journal init table.snap table.journal
# one record per line: insert, or withdraw
bgpkit-snap journal append table.journal changes.jsonl
# where it stands: base id, sequence, last checkpoint
bgpkit-snap journal status table.journal
# fold base + log into the next object, inside the journal directory
bgpkit-snap --json journal checkpoint table.journal -
•
syncis the durability point;checkpointverifies the object against the live tree before it commits and prunes. - • Recovery replays from the last checkpoint, so the checkpoint cadence is the recovery time.
-
•
checkpointwrites the next object for everyone else, verified before it is named, and leaves the base object exactly as it was.
When the snapshot is already loaded
This is the shape most services end up in: one object is being served and changes keep arriving. Two handles, one lineage. The read side never changes; the write side holds the base plus the changes since; only a checkpoint moves the reader to the next object.
use bgpkit_snap::journal::Journal;
use bgpkit_snap::{Opts, Snapshot};
// read side: one validated open, then queries that never touch the disk
let mut current: Snapshot<Origin> = Snapshot::open("origins.snap")?;
// write side: one journal over that same object
let mut log: Journal<Origin> = Journal::attach("origins.snap", "origins.journal")?;
// the feed arrives
log.insert("8.8.8.0/24".parse()?, Origin(15169))?;
log.sync()?; // durable from here
// the loaded object has not changed: readers keep the answers they had
assert!(current.owned().lpm("1.1.1.1/32".parse()?)?.is_none());
// the writer sees base plus log through the same queries
let seen = log.lpm("8.8.8.1/32".parse()?);
// publish: a new object inside the journal directory, named in state.json
let next = log.checkpoint(&Opts::now())?;
current = Snapshot::open(&next)?; // the reader moves by reopening - • The snapshot is immutable. A process that opened an object keeps answering from those bytes whatever the writer does, which is why several processes can read one file with no lock.
-
• The journal is the writer's view.
log.lpm(..)andlog.to_snapshot(&opts)answer from base plus the records so far, so a service that must answer with the newest data queries the journal or swaps to a new snapshot. - • Cost. The writer holds the tree in memory, so a process that serves a snapshot and writes its journal pays for both. Reopening is tens of milliseconds for a RIB-sized table, so swapping per checkpoint is fine and swapping per record is not.
-
• One writer per directory. A second writer gets
Locked; readers never take the lock.
Backup and restore
This is the part that decides whether a format is easy to live with. An object is a single immutable file, and its content id is a BLAKE3 hash over the identity bytes, the section table and every section body, so a copy can prove itself without trusting the medium it came from.
A snapshot
# the object is a file: that is the backup
cp table.snap /backup/table.snap
# the content id is the checksum, so a copy can prove itself
bgpkit-snap --json verify /backup/table.snap | jq -e '.ok'
# restore is putting the file back
cp /backup/table.snap table.snap - • No writable state, so no backup window and no lock.
-
•
verifyreads the header, the section table and the content id: the whole file, without the value type. - • A truncated or edited copy is refused, not half-read.
A journal directory
# backup: the directory holds the base, the log and current.snap
tar czf origins.journal.tgz origins.journal/
# restore: unpack, then open; state.json is the commit point
tar xzf origins.journal.tgz -
• The directory is self-describing:
state.jsonsays what wrote it and where the log has got to. - • A crash mid-append costs only the unacknowledged record; the next append cuts the torn bytes away.
-
•
current.snapis the reader's stable path: every checkpoint republishes it after the state names it. -
• Copy between checkpoints, or accept that a
tarthat races a checkpoint can see the link change or a covered segment disappear. We have not measured that window, so we do not claim it is safe. -
• If
state.jsonis ever lost,Journal::repairrebuilds it from the checkpoints, and proves the directory opens before it writes.
The file, byte by byte
The container is ours. The tries inside it are not: a snapshot is a 192-byte header, a section table, then one archived prefix trie per family, written by rkyv from a prefix-trie map. What we added is everything around them: identity, layout and alignment.
Two shapes are fixed on purpose. Both family tries are always present, even when one
holds nothing, and the entry counts are recorded in the object, so a client never has to
ask which families a file contains and stats works whatever
the value type is. Because the header is fixed at 192 bytes, identification is one small
read.
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
scroll the figure sideways to see all of it
Each section is described by one 64-byte table row, which is why a tool without the value type can still list what an object holds.
scroll the figure sideways to see all of it
What verification proves
Verification is what makes a file you hand to someone else trustworthy. It runs in layers, cheapest first, and each layer answers a different question.
CLI
# any object, whatever wrote it: header, section table, every byte
bgpkit-snap verify table.snap
# ok: 2 entries, bodies checked
# machine-readable, and a non-zero exit on failure
bgpkit-snap --json verify table.snap | jq -e '.ok'
# a foreign value type still gets the container checked
bgpkit-snap verify roas-v4f.snap
# ok: container ok, 2 sections, bodies not checked (type bgpkit.roa-set:v1 ...) SDK, the same layers
use bgpkit_snap::{recorded_counts, Snapshot, verify_bytes};
let raw = std::fs::read("table.snap")?;
// layer 1, no value type: header, CRC, layout, section table, content id
let header = verify_bytes(&raw)?; // Err(ContentId) if one byte changed
// layer 2, with your type: the type check plus rkyv bytecheck of both tries
let snap: Snapshot<Origin> = Snapshot::from_bytes(&raw)?; // or Snapshot::open(path)
// layer 3: decode the values and compare with the count the writer recorded
let counted = recorded_counts(&raw)?; // None for an object written before the counts section
assert_eq!(counted.map(|c| c.entries), Some(snap.len() as u64)); - • Container, no value type. Magic and format version; every header field's range and cross-field rule; the header CRC32C; the declared layout against the real file length; the section table (strictly ascending ids, kind agrees with id, zero padding, lengths that stay inside the file, sections that end the file); and the content id, a BLAKE3 hash over the header's identity bytes, the section table and every section body.
-
• Typed. Adds the value type check and rkyv's bytecheck over both trie
archives, so a body that is not a valid archive of your type is refused before any query
can read it. A profile that registers a
Validatorgets its cross-section checks here too. -
• Content.
verifyadditionally decodes every value and compares the result with the entry count the writer recorded in the object, so a file cannot claim more or fewer entries than it holds. - • Journal. Every record carries a CRC32C and a dense sequence number, so a hole or a torn frame is an error, not a shorter tree; a checkpoint is verified against the live tree before it is committed, and a journal whose base object was replaced refuses to open.
What it does not prove
- • Not that the data is true. A content id says "these are the bytes", never "these claims are correct". Verification is about integrity, not accuracy.
- • Not who wrote it. There is no signature in the format. Anyone can build an object with the same shape.
-
• Not provenance.
created_atand the coverage window sit outside the content id: they are covered by the header CRC, which catches damage, but a re-dated copy keeps the same content id. We checked: editingcreated_atand fixing the CRC leavesverifypassing with an unchanged id. Treat those fields as claims to be recorded elsewhere, not as evidence. -
• Not the bodies, for a type the tool does not know. On a foreign value
type the CLI checks the container and says so: the strongest check for that file is
Snapshot::<T>::openin the program that declares the type.
What the numbers look like
Measured on one machine against one RouteViews RIB
(rib.20200617.1800.bz2): 19,566,193 announcements
collapsing to 941,112 unique prefixes, so the object stores the collapsed table, not
the feed. Timings are from a debug build except the lookup, which is a release
build. A debug build is slower, so read the open and walk figures as an upper bound,
not a floor. One machine, one RIB, and no baseline against a database or a loaded
Parquet table: this is a shape, not a benchmark.
Simplified by design
Three places where the format takes the simple answer on purpose. Each one costs a caller something, so each cost is stated next to the choice.
Two more limits are absences rather than choices: there is no signature in the format,
and created_at and the coverage window sit outside the
content id. Both are spelled out under verification.