It's been 9 months since the original post set me on this Colored Petri Net journey! Imagining myself back then, that would sound like a long time, but I now realize just how deep this goes. It started as an itch I needed to scratch, and has grown into a full-blown "wow this could change how we do application state", manifesting as a framework that lets you compile your own application-specific database with blazing speed and complete safety.
It's been relatively easy to extrude the code with claude, but it is constructing narrative that lays the conceptual foundation which that code lies on, and which allows the really big strides to happen. That's why I'm writing this - to share the insight I see, and hear the opportunity it inspires in others. Even with agentic coding, the hard part still seems to be figuring out which concepts to say "yes" to, and how to compose them.
CPN overview
Knowing that you likely haven't read up on petri nets, here's a brief description:
In traditional databases, state is modeled as structs in collections, with "correctness" implemented as static typing, check constraints, and foreign key references. The state space of one of those systems is "anything that can be written under the defined schema". E.g., the state space is huge. Changes in state are largely driven by separately deployed applications that connect and permute data arbitrarily (from the database's perspective). Correctness of these application-driven changes is asserted by "happy path" and "adversarial" unit testing. Unfortunately, the DDL that creates structure in these flexible systems, along with the inserts/updates which change state, are also the things that makes their meta-state inherently uncertain. It's easy to imagine purpose-derived services disagreeing about order state, and much architecture talk has been made of it (2-phase commits, saga pattern, etc).
Petri nets are similar, in that they have collections with structs in them, but where traditional datastores externalize next state calculation, petri nets internalize them (via "transitions"). A transition is a reactive function that consumes tokens (rows) from places (collections) and produces tokens in other places. Transitions fire only when their binding conditions are met - e.g. the input tokens they would use are present, etc. There's more nuance when you go deeper, but that is 90% of the idea. (The "Colored" of colored petri nets means tokens hold data - traditional petri nets' tokens hold no data)
Here's a slightly longer, still very-application-focused description (with diagrams!) cpn.sao.dev
This means: in a petri net, the system can only be in states created by the net itself, and it is actively difficult to make the resulting state space large. This makes petri-net-based systems simple in a way that "open" data stores simply can't be.
Why a state store framework? Why CPNs?
State management really seems to be one of the "hard problems" in software engineering, and we make it harder by casually factoring it among "open state" systems with very large state spaces with limited external promises about said state. It's common for different services to have different databases, and many orgs give up system level atomicity almost immediately, to their own detriment. People use technologies like Temporal to sweep the resulting complexity and uncertainty "under the rug" (don't get me wrong, temporal is great), and as a result the practice of authoring and deploying software becomes this complex, layered distributed consistency problem.
I can see a world where we don't need to make these trade-offs, where products of every scale can keep system-level atomicity while improving performance and reliability.
In my early career I worked with digital electronics, which gave me high expectations for the speed and parallelism of distributed systems. Every circuit board, microprocessor, or FPGA is a distributed system on a smaller scale, and they achieve insane levels of performance with relatively low external complexity. It was always in the back of my head, "Why is it so hard to achieve the same for software?" Why can't we achieve the same for state storage?
The framework's perspective is essentially "if you can describe your product state as tokens in places (e.g. rows in tables), and describe the superset of state changes as transitions, then you get performance, safety, and scale for free". My honest bet is that essentially every product we use today can be modeled this way, with sufficient honesty in adapters/periphery code.
This is the hook that caught me: by providing specification for state's data structure and locking down how that state can transition, we can achieve a level of certainty about the state of a system that makes changing the state, and the system that defines the state totally safe and much simpler. In literature I see CPNs discussed at a much smaller scale: modeling a USB communication interface, a lighting control system, etc. We can apply these ideas at much, much larger scale for way more value/impact.
Example
Let's take the "scraper with cooldown and proxies" example from the original post. We could describe the system as follows:
places:
targets : { url, domain }
proxies : { addr }
in_flight : { url, addr, started }
fetched_pages : { url, body } # filled by the HTTP adapter
pages : { url, body }
cooling : { url, until }
transition fetch:
in target from targets, proxy from proxies
out { url: target.url, addr: proxy.addr, started: now } -> in_flight
transition done:
in f from in_flight, result from fetched_pages where result.url == f.url
out { addr: f.addr } -> proxies
{ url: f.url, until: now + 10m } -> cooling
result -> pages
transition warm:
in c from cooling where c.until <= now
out { url: c.url } -> targets
This description can then be compiled to a binary that implements this network, storing current state on disk, and probably exposing relevant interfaces to interact with the model (implementing fetch, reading scraped pages, etc). This is conceptually similar to using an embedded SQLite database.
Generally the funcitoning of the system should be pretty obvious from the above net description. This also demonstrates the separation of state management from "actual work", e.g. side effecting or fallible actions, like fetching the page to be scraped. The net description only tees up the fetch (via fetch transition creating the in_flight token), and relies on adapter code bolted on to the net to do the actual fetch, with the adapter inserting the resulting data as a fetched_pages token. This allows the net to stay pure and deterministic, pushing non-determinism to the boundaries (similar to this).
Killer features of CPNs
Below is a short list of "brags" about what the framework has achieved, and why it's impressive.
- Infallible state and state updates: There's literally no other way it could be!
- Blazing performance: Over double the speed of SQLite on TPC-C (~172k tpmC for CPN vs ~80k tpmC for SQLite on my laptop, single threaded). Microsecond-level state transitions.
- "Affordances" which act as the moving skeleton that clients build on: Internalizing the transitions that advance state also means a CPN system can advertise what transitions are one token away from firing, AKA "what button clicks would work?" or "which jobs can run?" Not via a separately coded "readiness indicator", but as a derived interpretation of graph structure and token state.
- Extremely powerful testing via state reachability walks: "Model state as place" is a useful design perspective for petri nets. With places describing state (e.g. token in
pending_email_validationplace), and system-derived affordances as potential walk steps, you can state product-level properties like "A user can create an account and then delete it within 5 clicks", and prove it is true without needing to describe the affirmative case. You can also describe negatives via transition omission: "banned users cannot comment on a post" - proven by no transition producing a comment with an arc from thebanned_usersplace. Very similar vibes to "you don't need to write tests for your type system". - CPNs constitute product features in graph structure: I'm a big believer in "constitutiveness" in software, as it makes it easier to describe correct and powerful systems succinctly. CPNs are eminently constitutive: the net's graph structure is literally the mechanism that state is implemented via, giving you much higher leverage on the problem you're solving.
This last one isn't a directly measurable brag, but I'll add it here as flavor. A big theme above is the graph described by a CPN providing the conceptual leverage for very high level claims about system correctness. This means it is easy and succinct to describe the correct operating of a CPN system from domain/business logic. This also means it is very easy to go from the english description of said domain logic to a functioning and verifiable net, and functioning application. This is particularly relevant these days, as it answers a big part of the "how would you develop applications 100x faster with agents?" question.
On the horizon
I didn't foresee these opportunities when I first bit into CPNs, but they are now potentially a majority of what makes this idea is compelling:
Categorically correct deploys: You can view CPNs through the category theory lens, which then opens up the potential for categorically safe deploys/migrations. Your vN+1 net could know, categorically, the set of nets it can follow, and ensure that a deployment will succeed before it is attempted. Zooming out, you can compose successive deployments of versions stacked on prior nets, knowing (again categorically) that your current net can walk any valid path to permute it's structure, adding, removing, and changing subnets and be confident that it will succeed all steps with enough time and compute.
Automatic live resharding, simple out-of-host scaling (and its caveats): the transition graph also tells you what data interacts via what transitions. This means you can use the graph-structured description of your product to horizontally scale it with strategic factoring of subnets (or modules via the hierarchical CPN lens) and placement of them onto different hosts. I am confident that this is "just a runtime away" from producing inherently scalable products based only on their net definition. That "just a runtime" sounds pretty challenging, but the foundations are there.
Tunable memory residency to balance performance with memory usage: In principle, almost none of a net's data needs to be in memory for the application to function, as it can be read from disk. In practice, high memory residency improves product performance, and allows you to get past interesting perf elbows. Another angle of this is that there are classes of workloads for which you can fully predict the online resource usage per user/item/etc based on the graph and token types alone. This would let you set caps that prevent OOMs and inform scaling directly.
Appendix
TPC-C Results
For posterity, and so someone can tell me how they did better! This is a single run of the multiple used to produce the numbers above. (run on an m1 max macbook pro)
Loading CPN (sf=1, warehouses=4, terminals=8)...
Durability: power loss costs <=1s of acked work (SQLite synchronous=NORMAL)
Running 8 terminals for 150s (5s warmup, pace=false)...
==============================================================================
CPN | 8 terminals | 150.00s measured | tpmC: 166562.6
Total: 928003 txns | Aborts: 4258
==============================================================================
Transaction Count Aborts p50 p90 p95 p99 p90-vs-ceiling
----------------------------------------------------------------------------------------
NEW_ORDER 416416 4258 0.05 0.07 0.09 45.90 PASS (5000ms)
PAYMENT 397425 0 0.01 0.02 0.03 32.53 PASS (5000ms)
ORDER_STATUS 38057 0 2.25 4.48 4.95 37.54 PASS (5000ms)
DELIVERY 37796 0 0.11 0.12 0.13 13.35 PASS (5000ms)
STOCK_LEVEL 38309 0 0.54 0.78 0.83 18.75 PASS (20000ms)
C1-C12 verification:
C1: PASS (0 violations)
C2_orders: PASS (0 violations)
C2_new_orders: PASS (0 violations)
C3: PASS (0 violations)
C4: PASS (0 violations)
C5_undelivered: PASS (0 violations)
C5_marker: PASS (0 violations)
C6: PASS (0 violations)
C7_null_carrier: PASS (0 violations)
C7_set_carrier: PASS (0 violations)
C8: PASS (0 violations)
C9: PASS (0 violations)
C10: PASS (0 violations)
C12: PASS (0 violations)
Loading SQLite (sf=1, warehouses=4, terminals=8)...
Durability: power loss costs <=1s of acked work (SQLite synchronous=NORMAL)
Running 8 terminals for 150s (5s warmup, pace=false)...
==============================================================================
SQLite| 8 terminals | 150.00s measured | tpmC: 74030.3
Total: 410404 txns | Aborts: 1804
==============================================================================
Transaction Count Aborts p50 p90 p95 p99 p90-vs-ceiling
----------------------------------------------------------------------------------------
NEW_ORDER 185079 1804 0.18 0.25 0.27 14.81 PASS (5000ms)
PAYMENT 175715 0 0.04 0.07 0.08 0.15 PASS (5000ms)
ORDER_STATUS 16789 0 1.08 2.30 2.51 2.95 PASS (5000ms)
DELIVERY 16617 0 0.46 0.53 12.67 15.55 PASS (5000ms)
STOCK_LEVEL 16204 0 0.47 0.54 0.57 0.63 PASS (20000ms)
C1-C12 verification:
C1: PASS (0 violations)
C2_orders: PASS (0 violations)
C2_new_orders: PASS (0 violations)
C3: PASS (0 violations)
C4: PASS (0 violations)
C5_undelivered: PASS (0 violations)
C5_marker: PASS (0 violations)
C6: PASS (0 violations)
C7_null_carrier: PASS (0 violations)
C7_set_carrier: PASS (0 violations)
C8: PASS (0 violations)
C9: PASS (0 violations)
C10: PASS (0 violations)
C12: PASS (0 violations)
==============================================================================
Comparison: CPN 166562.6 vs SQLite 74030.3 tpmC (+125.0%)
Per-core: CPN 0 vs SQLite 0 tpmC/core
Resources: CPN 0.00 cpu-s / 0 MB peak vs SQLite 0.00 cpu-s / 0 MB peak