Rust library + CLI

BGPKIT Snap

A prefix table in one file. Build it once, open it in milliseconds, back it up with cp, and keep it current with a journal.

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].

Install
# 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.
CLI
# 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.

Query surface
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 fallbackT
cover(prefix)every entry covering itVec<(IpNet, T)>
children(prefix)every entry under itVec<(IpNet, T)>
iter()the whole tableVec<(IpNet, T)>
iter_from(prefix, ..)from a prefix upwardVec<(IpNet, T)>
values()just the valuesVec<T>
address_counts()how much of the space is coveredAddressCounts
  • • Reads are zero-copy: opening validates the archives once, and every query after that touches the mapped bytes instead of rebuilding an index.
  • • Snapshot answers with archived values; snap.owned() answers with your own T, decoded per value.
  • • A second trie with a different value type lives in a profile section, queried with the same lpm, get_exact and iter through section_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.

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; the reader's path moves only after state.json names the new object.

Writing

Append, sync, checkpoint
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

Init, append, status, checkpoint
# 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
  • • sync is the durability point; checkpoint verifies 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.
  • • checkpoint writes 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.

Serve from a snapshot, write through a journal
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(..) and log.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

cp, verify, cp back
# 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.
  • • verify reads 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

One directory, one backup
# 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.json says 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.snap is the reader's stable path: every checkpoint republishes it after the state names it.
  • • Copy between checkpoints, or accept that a tar that 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.json is ever lost, Journal::repair rebuilds 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.

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: the band shows the order and the 16-byte alignment rule, not relative size. The 192-byte header is drawn wider than its share of a multi-megabyte file. 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
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; created_at, the id itself and the CRC follow, so a copy can be checked without knowing what any field means.

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.

0 8 16 24 0 32 id 0…1 kind 2…5 flags 6…7 length 8…15 reserved 16…63 ↳ reserved 16…63

scroll the figure sideways to see all of it

One section table entry: 64 bytes over two display rows, four fields and 48 bytes of reserved zeros.

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.

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. Each one is a superset of the one above it, which is why the CLI can check a foreign value type and stop.

CLI

verify
# 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

verify_bytes, Snapshot, counts
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 Validator gets its cross-section checks here too.
  • • Content. verify additionally 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_at and 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: editing created_at and fixing the CRC leaves verify passing 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>::open in 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.

941,112
prefixes in 7.6 MiB
from a RouteViews RIB
52 ms
to open that object
no parse, no index build
2 to 10 µs
per longest-prefix lookup
release build
239 ms
to walk every prefix
one pass, no allocation per entry

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.

One value type per object
One type id in the header instead of one per trie, so a reader knows what a file holds before it touches the body. Cost: a second structure with another value type goes in a profile section the profile reads itself.
One writer per journal
An advisory lock on the directory instead of multi-writer coordination, so a log is never two logs. Cost: a second writer gets Locked and has to wait.
A build holds the tree in memory
One in-memory pass instead of an external merge, so building a table needs no scratch space and no sorting step. Cost: a table larger than RAM is out of scope.