Skip to content

State Mutation on Streams

If you compute state as a fold over a stream of events instead of changing it directly, you get undo, replay and traceability almost for free.

≈ 10 min readSoftwareReactive

State Mutation on Streams

var events = [
  { type: 'ItemAdded', sku: 'A-100', qty: 1 },
  { type: 'ItemAdded', sku: 'B-200', qty: 2 },
  { type: 'QuantityChanged', sku: 'B-200', qty: 3 },
  { type: 'ItemRemoved', sku: 'A-100' }
];

function applyEvent(state, event) {
  var items = {};
  Object.keys(state.items).forEach(function (sku) {
    items[sku] = state.items[sku];
  });

  if (event.type === 'ItemAdded') { items[event.sku] = event.qty; }
  if (event.type === 'QuantityChanged') { items[event.sku] = event.qty; }
  if (event.type === 'ItemRemoved') { delete items[event.sku]; }

  return { items: items };
}

var cart = events.reduce(applyEvent, { items: {} });
// -> { items: { 'B-200': 3 } }

Four events, one function, one call to Array.prototype.reduce – and at the end you have the current state of a shopping cart. What’s remarkable is everything this code lacks: no cart.addItem(), no setter, no place where someone touches an object and changes it. The cart isn’t maintained, it’s computed. The list of events is the actual truth; the state is just its summary.

At first that sounds like sleight of hand, because of course memory gets mutated somewhere. But the perspective flips, and for a while now I’ve found this very flip more exciting than any new framework: state here is not a thing with a life story but the result of a fold over everything that has happened so far.

A fold, not a setter#

In the functional world, this pattern is called foldl – a left fold. You take an initial value, walk over a sequence from left to right and, in each step, combine the current intermediate result with the next element. reduce in JavaScript is exactly that, part of the language standard since ES5 and available in every current browser in 2014; only the remaining IE8 installations still need an es5-shim.

The signature of the step function is the interesting part:

// (state, event) -> state
function applyEvent(state, event) { /* ... */ }

Two properties make this function valuable. First, it’s deterministic: the same sequence of events and the same initial value always produce the same state. Second, it’s complete: there is no second way for the state to change, no method that reaches into the object past the fold. If you want to know why the cart looks the way it does, you read the events. Period.

Whether applyEvent builds a fresh object internally or writes to the state passed in directly is, by contrast, almost a matter of taste. In the example above, I copy the items because I’ll need intermediate states later. In a tight loop over a hundred thousand events, the function may mutate too – as long as the mutation stays locked inside the fold and only the result is visible from the outside. The discipline isn’t in the immutability of the objects but in the one single door that changes go through.

flowchart LR
  S0[Initial state<br/>empty shopping cart] --> F1((applyEvent))
  E1[ItemAdded<br/>A-100] --> F1
  F1 --> F2((applyEvent))
  E2[ItemAdded<br/>B-200] --> F2
  F2 --> F3((applyEvent))
  E3[QuantityChanged<br/>B-200] --> F3
  F3 --> F4((applyEvent))
  E4[ItemRemoved<br/>A-100] --> F4
  F4 --> S[current state<br/>as a projection]

A small experiment from 2012#

I didn’t come up with the idea on the drawing board. In October 2012, I created a tiny repository called statemutatejs. The README consists of a single line: “simple projection functions, alias foldl, that mutate state on a stream of elements”. The thing never aimed for more – an experiment that grew out of the question of what projection functions feel like when you consistently write them as a fold over a stream instead of as methods on an object.

I’m not mentioning this because it turned into a library anyone should use. But because, while tinkering, I noticed something I only half understood back then: as soon as the step function is separated from the container, what you fold over becomes interchangeable. An array, a Node stream, an observable sequence – the projection function stays literally the same. In hindsight, the one word “foldl” in the README was the whole point of the experiment.

Two years later, I see the same pattern in more and more places, and it’s worth laying the variants side by side.

The same pattern on Node streams#

Since Node 0.10, there has been the revised stream interface – streams2 – and with it objectMode, in which a stream carries arbitrary objects instead of buffers. This frees the fold from the array: the events no longer have to be fully in memory; they can arrive whenever they like.

var stream = require('stream');
var util = require('util');

function StateFold(applyFn, initialState) {
  stream.Writable.call(this, { objectMode: true });
  this.state = initialState;
  this.applyFn = applyFn;
}
util.inherits(StateFold, stream.Writable);

StateFold.prototype._write = function (event, encoding, done) {
  this.state = this.applyFn(this.state, event);
  done();
};

// same projection function as before, no changes needed
var fold = new StateFold(applyEvent, { items: {} });
eventSource.pipe(fold);

fold.on('finish', function () {
  console.log(fold.state); // -> { items: { 'B-200': 3 } }
});

This is deliberately unspectacular: a Writable in object mode that calls the step function once per event and keeps the intermediate result. applyEvent is unchanged from the first example. Whether eventSource is a file with line-by-line serialized JSON events, a TCP socket or a parser that turns log lines into objects makes no difference to the fold. Along the way, the backpressure mechanics of streams2 ensure that a slow consumer slows down the source instead of piling up events in memory.

In a project earlier this year, we built exactly this kind of evaluation over several gigabytes of log data: read events from files, fold them through a handful of projection functions, done. No cache, no database for the evaluation itself – just streams and folds. The code was so small that the discussion in the review took longer than writing it.

scan() makes the intermediate states visible#

reduce delivers exactly one value at the end. On an endless stream – user input, sensor data, price data – there is no end, and therefore no single result. The Reactive Extensions for JavaScript, currently in version 2.x, have the scan operator for this: the same fold, except that every intermediate state is passed on as an element of a new stream.

var cartStates = cartEvents
  .scan({ items: {} }, applyEvent);

cartStates.subscribe(function (state) {
  renderCart(state); // every intermediate state, as it happens
});

Again the same projection function, not a single character changed. Bacon.js offers the same operator with scan if the Rx style isn’t your thing. It gets interesting in the browser: if every user interaction is an event and the application state is a scan over it, then the UI is at any point in time a function of the event stream so far. I tried this in a prototype for a dashboard, and the most unfamiliar experience wasn’t the code at all. It was debugging: instead of searching the debugger for the object that was breaking, I printed the last twenty events and found the bug in the projection function. The broken state was no longer a mystery but the traceable result of a concrete sequence of events.

Undo, replay, traceability – by-products#

And that brings me to the real reason this pattern won’t let go of me. In classic mutating code, certain requirements are expensive because the old state is destroyed when it changes. If you want undo, you have to take snapshots or maintain inverse operations. If you want to know how a state came about, you need logging that someone has to have built in beforehand. In the world of folds, these requirements simply fall out:

function stateAt(events, count) {
  return events.slice(0, count).reduce(applyEvent, { items: {} });
}

var current = stateAt(events, events.length);     // state now
var undone = stateAt(events, events.length - 1);  // state before the last event
var initial = stateAt(events, 0);                 // start over

Undo is a fold over all events except the last one. Replay is the same fold once more, also step by step as a time lapse if you like. And traceability lives in the event list itself – it is the log you’d otherwise have to painstakingly retrofit.

flowchart TB
  L[Event list<br/>e1, e2, e3, e4] --> A[Fold over all<br/>= current state]
  L --> B[Fold over e1 to e3<br/>= undo]
  L --> C[Fold step by step<br/>= replay / time travel]
  L --> D[Read the list itself<br/>= audit log]

A few things you get practically for free this way:

  • undo and redo without writing inverse operations
  • reproducing bugs by folding the recorded event sequence again
  • new views on old data through a second projection function over the same events
  • tests that consist of nothing but an event list and an expected end state

The last point is the most underrated in everyday work. A test for applyEvent needs no mock, no database, no setup – event list in, compare the end state, done.

From toy to architecture question#

The idea isn’t new, of course. Martin Fowler described the pattern back in 2005 under the name Event Sourcing: the application state isn’t stored directly but reconstructed from a sequence of events. Greg Young took it further in his work on CQRS – separating the write side, which produces events, from the read side, which builds projections over them. What my small JavaScript experiment showed me above all is how short the path is from the reduce one-liner to this architecture question: as soon as you treat events as the truth and state as a projection, you’ve already built Event Sourcing on a small scale – just in memory instead of in a database.

I don’t want to make the idea bigger than it is. If you turn the fold into a system architecture, you buy yourself real problems. The event list grows without bound, so at some point you need snapshots so that not every startup folds through millions of events. The structure of the events changes with the application, but old events have to stay readable – this schema evolution stays with you permanently and is anything but a footnote. And for a simple admin dialog whose history nobody cares about, a direct update is simply the more honest tool. Keeping events pays off where the history means something in the domain: orders, accounts, contracts, measurement series.

That’s why, for now, my approach is: consistent in the small, cautious in the large. Folding events within a module costs almost nothing and forces a clean separation of “what happened” and “what follows from it.” Whether that should become a persistent event store for the whole system is a much bigger decision that you don’t make on the side during a refactoring.

What I take away from this#

The README of statemutatejs was one line long, and yet the experiment taught me more than many a framework manual. The lesson is inconspicuous: when changes exist as values – as events you can keep, look at and replay – then the current state is just one of many possible evaluations. reduce over an array, a Writable in object mode, scan in RxJS or Bacon.js: four times the same fold, four times the same projection function.

Since then, I ask one question more often in code reviews than I used to: where does this state come from, and could we record the changes as events instead? Most of the time the answer is “not worth it here,” and that’s fine. But in the cases where someone is building an undo function, an audit log or a reconciliation of two data sets by hand, the question almost always points to the same way out: the properties you want are already in the events. You just have to fold them.

Further reading#

Revised and translated from German with the help of AI.