Building pemba: An Embedded Zanzibar-Style Authorization Engine in Rust
Why I moved permission checks into the process, and what broke along the way
Why I wanted authorization inside the process
My last post was about running SpiceDB as platform infrastructure, which is how I built Monstro's permissions system as its sole developer. For a lot of teams that is still the right shape. But SpiceDB, like OpenFGA, Ory Keto and Permify, is deployed as a separate service that the application calls over the network, and for small-to-medium applications that brings three costs:
- operational cost: another service to deploy, scale, secure and monitor.
- latency: every permission check is a network round trip.
- dual writes: relationships live in the authorization service and application data lives in the application database. Creating a document means writing to both, and a partial failure leaves them inconsistent. Teams build outbox patterns and reconciliation jobs to cope.
The third one is the one I kept coming back to. With two systems to keep in sync, there is always a window where a document exists that nobody can open.
pemba is my attempt at removing that gap. It is an embedded, Zanzibar-style relationship-based access control (ReBAC) engine, written in Rust with Python bindings, that runs inside your process and keeps its data in your database. The one-line pitch in the README is "SQLite for authorisation". The schema language is a strict subset of SpiceDB's, so you can move to SpiceDB if you outgrow it, and I can differential-test against SpiceDB with identical schemas.
What it looks like
You describe the permission model in a schema. This is the example from the README's schema guide, with groups, nested folders and a ban list:
definition user {}
definition group {
relation member: user | group#member
}
definition folder {
relation parent: folder
relation owner: user
relation viewer: user | user:* | group#member
permission edit = owner + parent->edit
permission view = viewer + edit + parent->view
}
definition document {
relation folder: folder
relation owner: user
relation viewer: user | user:* | group#member
relation banned: user
permission edit = owner + folder->edit
permission view = (viewer + edit + folder->view) - banned
}
Then you write relationships and ask questions. From Python:
engine = Engine.sqlite("app.db") # or Engine.memory()
engine.write_schema(open("authz.zed").read())
rev = engine.write(touch=["document:readme#viewer@user:anne"])
engine.check("document:readme", "view", "user:anne", at_least=rev) # True
Every write commits at a new revision, one counter per store. Every read resolves its consistency to exactly one revision when it starts and reads only that snapshot, so one answer never mixes two points in time. Passing the revision a write returned as at_least= gives you read-your-writes when another process or connection did the write.
The design rule for the schema language is that every schema pemba accepts must parse in SpiceDB and mean the same thing there. Where SpiceDB is surprising, such as a + b & c meaning (a + b) & c, pemba rejects rather than diverges.
The headline feature: writes that join your transaction
pemba's tables live in your database, prefixed pemba_. Because the engine is in-process, a relationship write can join a transaction you already opened:
conn = sqlite3.connect("app.db", isolation_level=None)
conn.execute("BEGIN IMMEDIATE")
conn.execute("INSERT INTO documents(id, title) VALUES (?, ?)", ("readme", "Readme"))
rev = engine.write(touch=["document:readme#owner@user:anne"], conn=conn)
conn.execute("COMMIT")
That example runs verbatim in CI. pemba neither commits nor rolls back. The returned revision becomes readable when you commit and never exists if you roll back. If the connection has no open transaction, the write raises ValueError unless you pass allow_autocommit=True, because otherwise it would not be atomic with your data.
Getting this right was most of the work. All write logic (validation, precondition reads, revision allocation, row inserts and updates) is implemented once in Rust, generic over a small WriteTxn trait with three methods: execute, query and last_insert_id. One implementation drives the engine's own connection. The other is an adapter in the Python binding that forwards the SQL to the caller's connection, so it runs inside the app's open transaction. A few of the details that came out of building it:
- Savepoints. The write runs inside
SAVEPOINT pemba_write and rolls back to it on error. Without that, an AlreadyExists on the third operation of a batch would leave a revision row and two operations behind for a caller who commits anyway. - Same-file check. The engine checks, on every write, that the caller's connection points at the same database file. I'd planned to cache this by
id(conn), but CPython reuses the id() of a collected object, so a connection to a different file could inherit a stale "verified" entry and the write would land in a database the engine never reads. - Revision order equals commit order. SQLite allows one writer at a time, so revisions can't interleave. If a deferred transaction reads a precondition and another connection commits first, SQLite refuses the lock upgrade with
SQLITE_BUSY_SNAPSHOT, and pemba surfaces a retryable conflict rather than committing on a stale precondition.
War story one: two copies of SQLite in one process
The first design said that reads use the engine's own connections. In Python, those were rusqlite connections with a bundled SQLite, while the app's sqlite3 module used CPython's own copy. Foreign-transaction mode put both copies on one file in one process, by design.
That turns out to be dangerous. On POSIX, close() drops every fcntl lock the process holds on a file. SQLite works around this by keeping a process-wide list of open files, but each copy of SQLite has its own list, so a close by one copy silently drops the other copy's locks.
I wrote a deterministic probe to see whether this was real. A bundled-copy connection holds BEGIN IMMEDIATE and an uncommitted insert on a WAL database. A separate process tries BEGIN IMMEDIATE and fails, as it should. Then, in the first process, Python runs sqlite3.connect, one SELECT and close(), and the separate process tries again.
The bug was real. The separate process got the write lock and committed, and the bundled connection committed too, believing it had held the lock throughout. Python's close also checkpointed and deleted the -wal and -shm files under the open writer. Afterwards PRAGMA integrity_check said ok, but the other process's committed row was gone. That is silent loss of a committed transaction, which is worse than a crash. It reproduced locally on WSL2 Ubuntu and in all four CI jobs on Linux and macOS. Windows locks per handle and doesn't have this mechanism, and I didn't test it there.
One way out was to link the extension against the interpreter's SQLite. It can't be made reliable for PyPI wheels: a manylinux wheel may not depend on libsqlite3.so.0, python.org macOS builds compile SQLite into the interpreter, and equal version strings prove nothing, because two copies of 3.45.1 still corrupt each other.
The other was a store whose every statement (reads, native writes, migrations, GC) runs on Python sqlite3 connections the engine owns, so only CPython's copy ever touches the file. All authorization logic stays in Rust behind the same traits. The prototype passed all 25 cases of the store conformance suite, and then I measured what it cost:
- single-threaded, a check went from 36 µs to about 100 µs at p50, roughly 2.7×.
- with 8 threads and no serialization it collapsed to 190 checks per second, because
sqlite3 releases the GIL inside every execute and the threads convoy on it. - holding the GIL for a whole check deadlocked once threads outnumbered pooled connections.
- serializing requests (take a Rust mutex without the GIL, then hold the GIL for the whole request) gave 6,700 checks per second, with p99 at 620 µs against the native store's 1,440 µs.
I went with the Python-owned store, serialized. Engine.sqlite() now goes through CPython's own sqlite3, the Python package no longer depends on rusqlite, and CI fails if the extension or the wheel contains SQLite. The probe became a permanent test, and the README warns against opening the same database with anything that brings its own SQLite, such as apsw.
The lesson I took from it: "the engine's own connections" had quietly assumed there was only one SQLite library in the process.
War story two: exponential checks on cyclic data
Cycles in data are legal. Groups contain each other and folders point at each other. pemba evaluates them to a fixed point, so a group that contains itself is a finite question (SpiceDB keeps dispatching until it reports max depth exceeded).
The original rule was simple: a node currently being evaluated counts as false for the purpose of breaking the cycle, and any result that depended on that assumption is not memoised. That is correct, but inside a cyclic region it re-walks every path. Cyclic group data is ordinary data that users can write, so a user could make one check arbitrarily expensive. That's a denial-of-service risk, and neither max_depth nor the fan-out limit bounds total work.
The property tests found it. One 1,000-case run took 3.0 seconds. The next, with a different random seed, was still running after 573 seconds when I stopped it. The pinned case had two types and 30 tuples with dense mutual recursion over ids a to f. One check made 32,726 store reads at depth 29, about 170 ms in release, while the reference evaluator answered the whole case in 21 ms.
My first fix, adding lowlink taint and memoising cycle heads, was still exponential. On a complete group graph with the subject in no group, store reads for n = 5 to 9 groups were 130, 652, 3,914, 27,400 and 219,202. The evaluator was walking every simple path, around (n−1)! of them.
The fix that worked is SCC fixed-point iteration, Tarjan-style. Each node of a strongly connected region is evaluated at most once per pass:
- a hit on a node still in progress returns its provisional value (
false if it has none) and marks it as assumed. - when the head of the region finishes, if no assumed
false finished true, the pass is consistent and every value in the region is memoised. - otherwise the provisional values are raised and the head re-runs.
Provisional values only grow, and a region of |S| nodes needs at most |S| + 1 passes, so one check is bounded at (|S| + 1) · Σ r(x) store reads per region, where r(x) is the reads one evaluation of a node makes. The complete group graph that blew up before now takes one pass and about 2n reads. One subtle bug on the way: lowlinks have to be SCC-stack positions, not call-stack indices, or a sibling that reuses a popped frame's index looks like the head of its own region and settles a false too early.
A cycle that crosses the subtracted side of an exclusion has no well-defined least fixed point, so pemba returns NonMonotonicCycle instead of guessing. And there's a backstop. max_check_reads (default 200,000) caps store reads per check and fails closed with ReadLimitExceeded. It guards against bugs in the rule and against large but legitimate graphs. At an estimated 5 to 20 µs per indexed SQLite point read, which I haven't measured yet, that caps a pathological check at roughly 1 to 4 seconds. After the change, the pinned case makes well under its 1,000-read bound and the 1,000-case property run finishes in about a second.
How I check that it's right
Authorization bugs that grant too much are the ones that matter, so most of the effort went into verification:
- a reference evaluator: a deliberately naive, obviously-correct evaluator used only in tests as an oracle. Even the oracle needed fixing: with recursion on an exclusion's base side, one variant of its iteration stopped on a wrong answer that looked like a fixed point. It now stratifies the schema and declines what it can't stratify.
- property tests:
check against the oracle on generated schemas and data, with the 1,000-case run as a separate workflow; store equivalence across the memory and SQLite stores; and the formatter, which must keep every comment exactly once. - differential tests against SpiceDB 1.56.2: 18 fixtures covering 23,621 questions and 500 compared generated cases covering 499,517 questions, with zero unexplained mismatches. Every known difference has a detector that needs the exact shape of the disagreement, so it can't hide an unrelated bug.
- fuzz targets, including one that runs the property-test generators under AddressSanitizer.
Generated cases sent to SpiceDB have no cycles and at most 16 relationships, because on the densest data one SpiceDB bulk check used 2.5 GB and the test server was OOM-killed on a 4 GB machine. Cyclic and larger data go through the fixtures.
The most interesting difference is KD-3. In pemba, a stored wildcard t:* matches every object of type t and never a subject set like t:x#r. SpiceDB matches the subject set too. On the granting side that makes pemba the stricter one, and I kept that. On the subtracted side of an exclusion it made pemba the more permissive one:
definition user {}
definition grp { relation member: user }
definition doc {
relation viewer: grp#member
relation banned: grp:*
permission view = viewer - banned
}
doc:d#viewer@grp:g#member
doc:d#banned@grp:*
check doc:d#view@grp:g#member -> pemba AMBIGUOUS_WILDCARD_EXCLUSION (was true), SpiceDB false
Before the fix, pemba allowed what SpiceDB denied. That is the fail-open direction, so pemba now refuses to answer there and returns AMBIGUOUS_WILDCARD_EXCLUSION. The reasoning, from the evaluation spec: an error can later become an answer without breaking callers, but an answer cannot change silently.
That doesn't mean every disagreement becomes an error. Where the difference is pemba's documented semantics, I kept them: on cyclic data pemba answers and SpiceDB errors (KD-1), and near the depth limit of 50 SpiceDB's answer depends on timing while pemba's is deterministic (KD-4). More generally, evaluation never turns a store error, a depth limit or an undefined cycle into True or False. It raises, and the caller decides.
What's next
pemba is pre-alpha. check, lookup_resources, lookup_subjects, the memory and SQLite stores, transactional writes and the Python bindings are implemented and tested, including against SpiceDB. Nothing is published to PyPI or crates.io yet, the 0.1 release gate isn't signed off, and you should expect breaking changes.
The biggest gap is performance. A benchmark harness exists, sharing one set of datasets across the Rust, Python and SpiceDB benches, but no benchmark has been run and no targets are set. The numbers in this post come from probes and tests, not benchmarks. The fuzz targets exist, but the 10-minute runs and mutation testing haven't happened. Postgres is planned, not started.
If many services in many languages need the same permissions, or you need multi-region scale or a mature product today, use SpiceDB. pemba is for a single application, or a few services sharing one database, that wants fine-grained sharing without running another service.
Why "pemba"
The project started under the codename warden. pemba comes from Pemba Island in the Zanzibar archipelago, a nod to Google's Zanzibar paper, and home of the Pemba flying fox, which lives nowhere else.
Tags: Joshua Fields, software engineer, Rust, Python, Zanzibar authorization, SpiceDB, SQLite, property-based testing, open source, London
Back to Writing | Joshua Fields Home | Industry Experience | pemba Project | pemba on GitHub | GitHub | LinkedIn
Joshua Fields — full portfolio
