Serguei Filimonov

What is Accretive State?

Published on

I'd like to propose a term for a range of software tools and techniques: accretive state. Not merely "accumulating" state (files on disk accumulate, logs accumulate), but accreting like rings of a tree trunk (each ring layered onto the previous). Accretive state is when the "past" state of your software is sorted and available for first-class access. It roughly covers systems like Git (the version control system everyone knows), Datomic, XTDB, event sourcing, and other ways to arrange the data so that the past is accessible.

The Definition

I borrow the word "accretive" from Rich Hickey (creator of Clojure and Datomic), describing Datomic as being "accretive". As new records arrive, they're "accretions". He uses "rings of a tree trunk" as an analogy. The past state is untouched. You can ask Datomic "What was the state of everything as of a time?". That's one of the main hallmarks of accretive state. Remember the difference between "accreting" and "accumulating". The distinction isn't simply that accretion is ordered — accumulation can be ordered too. It's that an accretion has observed the state it's layered onto. A write that doesn't read what's already there accumulates; a write that reads the prior state and builds on it accretes. Rings of a tree accrete because each ring is laid onto the previous one. Two files with identical timestamps don't accrete — neither saw the other. I would also say that the set of past states must be granular enough to be useful for access. Having periodic "snapshots" of state is ordered by time, but likely allows for too many states between 2 snapshots, which may be valuable to inspect. For an application with complex logic reading state N to compute state N+1, we really want all the states to be accessible for inspection.

Naming the states to access them

When I say a past state needs to be first-class accessible, we clearly need a handle or a name to use as the pointer to that state. And "timestamp" is not necessarily the best way to name these states: wall-clock timestamps collide, carry no total order across instances, and carry no meaning the application can reason about. Git uses SHA hashes, event sourced systems use an integer version counter, XTDB uses timestamps, but makes them suitable for global ordering (within a DB instance) by disallowing 2 transactions having an identical timestamp. So the typical way to refer to a past state is a combination of a partition (account:27) and a "pseudotime" (17) Pseudotime means the application models its own, discrete, ordered sense of time rather than relying on wall-clock timestamps. See "What is pseudotime?" to learn more about pseudotime, given it's an extremely related concept. Accretive state and pseudotime often go hand in hand.

Git - the accretive system we all know

The above is my attempt to describe what accretive state is, but really, the simplest way to understand accretive state is to see Git, the version control system we're all familiar with in a slightly different light:

  • A file tracked in Git is like an "entity" a business application stores and updates.
  • A repo is an "aggregate" of many files. A commit groups together changes to multiple files in a single "moment".
  • The main/master branch is the 'timeline' and each commit adds to the history in an append-only fashion. We use Git shas to point/refer to past states of the repo. (To be fair, merge-commits muddy things a bit by allowing timelines to branch and merge, but for the main experience of incrementally adding to the branch, the accretion works)
  • when you update files and make a commit, the previous commit (and all before it) are still accessible for full examination, you can revert to or make a copy of that past state "as of" a past commit.
  • Your system/organization might consist of multiple Git repos. There isn't a single Git sha that refers to a past state across multiple repos. 2 repos are separate timelines as far as merges and timeline are concerned.

Limits to ordering every change

We intuitively understand that it's not feasible to globally order all inputs/writes into the system. To order/serialize the writes would introduce "contention" and limit the throughput of the system to a single piece of hardware. (or slower if going through a consensus algorithm) Once a system spans more than a single database instance, we can't access the state across all instances with a simple/single name. The accretion must be scoped to a partition of the state. Multi-tenancy is an easy one to reach for, as an easy partition to make the order less global. For example, in a project management software like Linear, every "project" (or at least "account") is said to have its own state and we could imagine there being a history of those states. The Git analogy above alluded to this by riffing on the tolerable inability to commit "across repos". It is because of this physical limit to "total write contention" that different accretive systems (see Directory below) vary by how the state is scoped. For example, Datomic gives you a t via which you can access the state of the entire database as of that t. (In a cluster of Datomic instances, of course, you can't dereference/lookup that t beyond the single instance). Whereas in event sourcing, the application has to, upfront, design its "aggregates", and each aggregate accretes state and has its own timeline to be explored via its own pseudotime. Despite that variability, most accretive systems will nevertheless provide plenty of benefits for the overall software system.

The Many Benefits

Accretive state is all about taking the sense of "time" (navigating the past) we're used to with Git and expecting something similar from all data in our application. Some benefits of this below:

Time-travel debugging

The ability to access/export/examine the past states is a big productivity boost because whenever you (or your LLM) are exploring an issue or not-quite-working behavior, it's a godsend to obtain the state "right before the problem happened". This will a) allow you to step and see where/why the code updated the "current state" incorrectly, but also you can easily export this state and use it as a unit test fixture. In a recent, event-sourced, Rails app I've built, i've encountered the following situation numerous times: - A bug is reported affecting a customer, I look up the precise timeline of every version of the customer. - I see that since around the time the customer experienced an issue, a customer support agent did a bunch of modifications to the account in an attempt to fix or work around the bug. And the customer cancelled their subscription. All of this means the customer state is now very different from what it was when the issue was reported. - From the timeline, i see that the customer must have encountered an issue when their state was at version 157. - I ssh into production, look up the customer at that version via:

  # full customer state (including associations) "as of" version 157
  customer = Customer.find(id).value(version: 157)
  # observe incorrect value that caused a visible problem
  customer.some_method
  • I export the timeline (anonymized) upto version 157 as a json file, and use that data as a unit test "fixture" to capture the issue and prevent a similar bug from occurring next time somebody changes this code.
  • Note: code agent LLMs have sped up the process of combing through the data timeline tremendously. When the exact version/moment of the issue is hard to tell quickly, pointing Claude to the whole anonymized timeline to find anomalies and problems has been incredible.

Other common benefits

  • As-of reporting / business analytics . This is a well documented benefit in the Datomic / XTDB communities, so I won't rehash it here , but the richness of information you can get by just having access to past, real states is immensely greater than relying on periodic ETL extracts / reports, which you have to design the content of ahead of time. With accretive state, you're already ready for many more cases without planning ahead. In my experience this came up when calculating ARR (annualized recurring revenue) for past dates at a startup I worked at. ARR calculations allow some wiggle room to re-interpret what the customer will spend in the future depending on arbitrary aspects of their account. It was extremely valuable to "rewind time" to various past months and calculate ARR "as of" that time.
  • Undo/Revert as development/QA facility - As you're modifying state in a local or staging environment, it's so useful to be able to explore multiple branches of a set of choices. With the past accessible, you can explore a path A through the app, restore the state to just-before-the-fork-in-the-road and explore state B. I've seen this make both development and QA acceptance much more productive. Click, click, click, undo. Useful, but surprisingly uncommon in many webapps during development.
  • Undo/Revert as a feature - Desktop apps have had "undo" for decades, then webapps mostly lost this feature because it's been difficult to implement and provide reasonable multi-user UX for. But it's an important feature for almost any software and it's worth striving to offer it whenever possible. Users/operators of the software would be able to be more bold and productive, knowing there's a way to undo a mistake.
  • Slow readers don't need to block - No matter how slow of a query/process/calculation you need to run on the whole state, the reader doesn't need to block any writers or other readers, because the past state it grabbed on to is immutable and forever accessible by querying that aggregate/partition's moment in pseudotime.
  • You can find more benefits and success stories via the many sales pitches online for Datomic, XTDB, or event sourcing.

Disk is cheap, Records are valuable

I hope this was a helpful overview of "accretive state" as something to expect from data systems. A lot of ink has been spilled over decades about the value of data to the business, but it tended to mean a separate, data warehousing capacity that has little to offer when it comes to actually developing the applications better (faster, fewer bugs, readiness for change). I'll write about more development productivity experiences in future blog posts. Thank you for reading.

Appendix: More Examples of Accretive Tech

The following is a living directory of accretive state systems, databases, and other tools, to supplement the definition and point towards "how to do it":

  • Datomic - Directly emphasizes "as of" queries and the "t" pseudotime handle for past states. Datomic provides a "global" pseudotime (within a single instance), which is a fantastic default for many systems/apps.
  • XTDB - a Postgres-protocol compatible database where the "system time" acts as pseudotime and "as of system time" queries can be made. In addition to providing accretive state, it has additional "bitemporality" features too. The pseudotime in XTDB is global, like Datomic.
  • Event Sourcing - uses an append-only log as the source-of-truth for state, which is accretive in a very direct way. Note: the "pseudotime" is not global, but per "aggregate". So depending on how your application models aggregates, your state is accretive within that scope.
  • Git - as described above, Git is the most intuitive accretive system because we use it for our source code precisely for its accretive nature. There are also databases that either use Git as the underlying storage technology or implement faithful "git for data" experience: Dolt, TerminusDB, etc.
  • Redux - event sourcing for the frontend. It's ephemeral (history within the lifespan of a React page), but provides the same experience of accretive state in that microcosm.
  • ...More entries to be added soon...