Anne creates a document. The app inserts the row, tells the authorization service she owns it, and then the payment fails. The document is rolled back. Her permission, sitting in a separate service, is not.
I've written too many transactional outboxes to patch exactly this. pemba keeps permissions in your own database, so the relationship write commits or rolls back with the document. On SQLite that was most of the work. On Postgres it raised the real problem: numbering the writes.
The guarantee
Every write in pemba commits at a revision, a u64 from one counter per store. Reads resolve to exactly one revision, which is what makes at_least=rev (read-your-writes) and at_exactly (stable paging) work. Both depend on one rule: once any reader has observed revision N, no write numbered N or lower may become visible afterwards.
SQLite gives you this for free, because one writer holds the lock from drawing a number until it commits. Postgres runs writers concurrently, and they commit in any order. Draw the number with nextval() at write time and this happens:
T1 draws revision 10
T2 draws revision 11
T2 commits a reader sees head 11
T1 commits revision 10 appears below a head someone already saw
In the spike below, that naive scheme broke the rule in 39,355 of 39,371 observations.
There's a constraint underneath this. If a write learns its revision when it writes, and commits at some unknown later moment, then every other writer that commits in between has to be either blocked or hidden from readers until it ends. The only ways out are to drop the total order, or to not decide the number until commit.
The options, and a spike to pick one
I built a throwaway Python harness against Postgres 17.11 in Docker. Eight writer threads run on their own connections, and half their transactions stay open 0 to 30 ms after the write to force commits out of order. A ninth writer holds a transaction open for 3 s every 4 s, standing in for a slow request. Four readers resolve the latest revision and fingerprint what they see inside one REPEATABLE READ snapshot. The oracle compares each observation with the final state at the same revision, so any write that appeared under an observed head counts as a violation.
The main run, at READ COMMITTED for 20 seconds (compare the rows with each other, not as absolute numbers):
| Scheme | Writes/s | Violations | Writer wait p99 | Visibility lag p99 |
|---|---|---|---|---|
| No ordering (control) | 807 | 39,355 of 39,371 | 5.0 ms | 1.7 ms |
| Lock held to commit | 60 | 0 | 3,068 ms | 1.0 ms |
| Sequence + watermark | 643 | 0 | 9.2 ms | 2,920 ms |
| Assign at commit | 686 | 0 | 6.1 ms | 1.8 ms |
Lock held to commit is SQLite's approach moved to Postgres. It's correct, but every writer waits out the slow transaction, and taking a store-wide lock in the middle of the app's transaction invites deadlocks. SpiceDB's Postgres datastore worked this way before v1.14.
Sequence plus watermark lets writers draw freely, and a reader's head is the highest revision below the oldest one still in flight. Writers don't wait, but head freezes behind the slow transaction, so for about 3 seconds nobody sees anyone's writes. Finding what's in flight means scanning pg_locks on every read.
Assign at commit doesn't decide the number until the transaction commits. The slow transaction holds the lock only during its own commit, so it blocks nobody and hides nobody.
The fourth option is what SpiceDB does today: store transaction ids (xid8) on rows and make a revision a Postgres snapshot. It's correct, but a revision stops being a u64 in a total order, which is the largest API change pemba could make. Worse, pemba's tables live in your application's database, so they get dumped, restored and logically replicated with it, and stored transaction ids mean nothing after any of those. SpiceDB owns its database and ships a repair command. pemba can't ask every app's restore to run one.
Assigning at commit has a cost too. A write inside your transaction can't know its revision until that transaction commits, so write(conn=) now returns a PendingRevision that resolves after commit. It does on SQLite as well, so portable code never checks which store it's on.
The design that shipped
Each write call draws a batch id, which has no ordering meaning. Rows it creates carry the id in created_batch, rows it deletes carry it in deleted_batch, and the call inserts one row into pemba_pending. A deferred constraint trigger on that table fires at COMMIT, inside the committing transaction. It takes a store-wide advisory lock, draws the next revision with nextval(), and inserts one row mapping batch to revision. That's all it does.
A simplified version of the migration (the real one schema-qualifies every name, pins search_path, and detects when the trigger fires early):
CREATE TABLE pemba_revisions (
batch_id bigint PRIMARY KEY,
rev bigint NOT NULL UNIQUE,
kind text NOT NULL,
committed_at timestamptz NOT NULL
);
CREATE FUNCTION pemba_assign_revision() RETURNS trigger
LANGUAGE plpgsql AS $$
BEGIN
PERFORM pg_advisory_xact_lock(1885695330,
'pemba_revisions'::regclass::oid::int4);
INSERT INTO pemba_revisions (batch_id, rev, kind, committed_at)
VALUES (NEW.batch_id, nextval('pemba_rev_seq'),
NEW.kind, clock_timestamp());
RETURN NULL;
END $$;
CREATE CONSTRAINT TRIGGER pemba_assign_revision
AFTER INSERT ON pemba_pending
DEFERRABLE INITIALLY DEFERRED
FOR EACH ROW EXECUTE FUNCTION pemba_assign_revision();
The ordering argument rests on one detail. A transaction-level advisory lock is released when the transaction ends, and Postgres makes a committed transaction visible before it releases its locks (xact.c: "this must be done before releasing locks we hold"). So when the next committer gets the lock and draws a higher number, the previous commit is already visible to it and to every later snapshot. Revision order is commit order.
The lock is held from the trigger to the end of the commit. A 1,000-tuple batch commits in 0.95 ms, against 0.85 ms with no commit step at all. Reads at head need no map: open transactions are invisible, so deleted_batch IS NULL means visible. Reads at an older revision join the map, which made a 500-row lookup 34% slower at p50 in the spike.
The surprise: SERIALIZABLE
The first version of the trigger did more. Rows carried a provisional mark, and the trigger rewrote them to the real revision at commit. Rewriting with a predicate UPDATE made 45 to 58% of SERIALIZABLE attempts fail with 40001, because it took SIREAD locks on index pages every writer was inserting into. Rewriting by ctid brought failures down to 2.7 to 3.4% of commits, and I thought that was mostly solved.
It wasn't. With retries and backoff, 0.03 to 0.08% of transactions still failed every retry. The design review didn't accept a documented rate of lost transactions, and I agreed: a correct app that retries must not lose writes.
Before trying a fix, I went back over the harness and found it wasn't measuring the design. Each writer resolved its revision in a new SERIALIZABLE transaction on its own connection. The comparison scheme did no such read, and the real design resolves on a separate engine connection in autocommit. Rerunning the old behaviour put 0.57 to 0.72% of transactions into a 40001, with 1 to 9 give-ups per run. Part of what I'd measured was my own harness.
With the harness fixed, I compared the rewrite against the batch map, which rewrites nothing. Retrying up to 10 times with backoff, over four runs with and without the slow transaction:
- the rewrite still lost 5 transactions, in 2 of the 4 runs.
- the batch map lost 0 of 71,585. Between 0.10 and 0.25% of its transactions hit a 40001, at or below the comparison scheme without a commit step (0.25 to 0.27%).
- a 1,000-row commit went from 5.3 ms to 0.95 ms, because the commit no longer touches the rows.
Living with it
A permanent concurrency test. The spike became revision_order.rs, a Rust port that runs in CI at READ COMMITTED, REPEATABLE READ and SERIALIZABLE, with a long transaction at least twice per run. It asserts zero violations and, at SERIALIZABLE, zero transactions that fail every retry. It also runs a negative control that allocates at write time on the same tables, and fails unless the control shows violations, so the oracle can't pass vacuously. One honest note: with a precondition read in one write in ten, this test sees about 1% 40001s for pemba against about 0.4% for the control. That's an open question in the repo.
SET CONSTRAINTS ALL IMMEDIATE. This fires the deferred trigger at that statement, so the transaction holds the store-wide lock until it ends and behaves like "lock held to commit". In the spike, doing it in the 3 s transaction dropped throughput from 686 to 371 writes/s. Django's TestCase does it after every test. The trigger checks current_query(), and if the statement isn't COMMIT it raises a WARNING naming it. Correctness holds either way. It's a throughput trap, and the README says so.
Retry with backoff. Immediate retries lose transactions with or without pemba: up to 5 instant retries lost 2 to 6 per run with the batch map and 0 to 7 with the comparison scheme. The documented requirement is exponential backoff with jitter.
Round trips. This is what I want to improve next. A check costs about 5 round trips plus 2 to 3 per level of hierarchy walked. On a CI runner where SELECT 1 took 146 µs, a direct hit took 755 µs at p50. A statement cache and batched writes already halved most figures, but what's left is mostly network.
Pick it apart
The Postgres store shipped in pemba 0.1.0-alpha.3. The full reasoning, with every spike table, is in docs/10-postgres.md, and the code is on GitHub. The design leans on a few Postgres behaviours: commit visibility before lock release, deferred trigger ordering, and how SSI treats one index insert per batch. If you know Postgres internals better than I do and see a corner where one of those doesn't hold, I'd like to hear about it. Open an issue.
Originally published at joshuafields.uk.
Top comments (1)
The 39,355 of 39,371 number makes the nextval() problem very concrete. One approach worth benchmarking against your options is exposing readers only up to the oldest in-flight transaction, using pg_current_snapshot() / pg_snapshot_xmin(), so a revision becomes visible only once every lower-numbered writer has finished. It costs some read latency under long transactions, but it keeps the total order without serializing writers. How do your long-running transactions behave with the approach you picked?