Out of the Tar Pit

Picture Facebook around 2011. The messages icon on the page shows a 1. You click it, expecting something new, and there is nothing there. You refresh the page, and the 1 is gone. In a 2014 talk, a Facebook engineer called this "our most annoying chat bug": users "would get an unseen count and there would be no unseen messages behind it." When Facebook posted on its blog in 2011, the first comment asked them to improve chat, with 898 likes.

The team fixed it again and again, one edge case at a time, and each time the bug came back. Why does a bug like this keep coming back, and what kind of design would make it impossible? A 2006 paper gives a sharp answer, and it starts by blaming one thing: state.

One Number, Three Writers

The engineer walked through how the feature grew. First came the chat tab, a list of messages; a new message is appended to it. Then came the messages icon (Facebook calls it the messages jewel), which "shows you the number of threads that have unseen messages on them." It was built separately, so the code that handles a new message also bumps an unseen counter, and lowers it again "if we think that the user is looking at it." A few months later came a larger messages view, and the same handler now had to keep three things in step and decide when the user was looking at either view.

Here is one way such a counter can drift (an illustration, not Facebook's exact code path):

The real fact, which threads have unseen messages, is already in the lists. The counter is a copy of that fact, kept in step by hand, in every place that changes it. Miss one step and the copy drifts. As the engineer put it: "It's hard to tell that you only want to increment and then decrement. You don't want to do either of those more than once."

The Argument With Brooks

In 2006 Ben Moseley and Peter Marks wrote a 66-page paper about this kind of mess. It picks a fight with Fred Brooks's essay No Silver Bullet. Brooks named four things that make software hard: complexity, conformity, changeability and invisibility. Moseley and Marks argue that only complexity matters; the other three "can either be classified as forms of complexity, or be seen as problematic solely because of the complexity in the system." By complexity they mean one plain thing: what makes large systems hard to understand (not complexity theory, which is about the resources a machine uses).

Complexity is the single major difficulty in the successful development of large-scale software systems. Following Brooks we distinguish accidental from essential difficulty, but disagree with his premise that most complexity remaining in contemporary systems is essential.

(p. 1)

Brooks wrote that "the complexity of software is an essential property, not an accidental one." The paper replies: "We disagree." Much of the complexity in existing software is not part of the problem at all, so you can find it and remove it.

Two Ways to Understand a System

Why put understanding at the center? Because, they argue, unreliability, late delivery, lack of security and often even poor performance all derive from unmanageable complexity: you cannot avoid any of them in a system you cannot understand. You have two ways to understand one:

They call informal reasoning "the most important by far," because better reasoning means fewer errors are made in the first place, while better testing only finds more of them. They quote Dijkstra: testing can show the presence of bugs "but never to show their absence." Both kinds of understanding get easier when the system is simpler, so they put simplicity above either.

Cause One: State

By state they mean mutable state: values a program remembers and can change. You have met it if a support desk ever told you to "reload the document," "restart the program" or "reboot your computer." Those remedies work because the system has wandered into a bad internal state, and starting over forces it back into a good one.

State hurts testing and reasoning in the same way. In the paper's words, "for every single bit of state that we add we double the total number of possible states." Three threads, each seen or unseen, give the messages app 8 possible states. And "a test (of any kind) on a system or component that is in one particular state tells you nothing at all about the behaviour of that system or component when it happens to be in another state." Tests usually start from a clean state and quietly assume the hidden state won't matter.

A Copy Multiplies the Bad States

Now store the unseen counter on its own, with any value from 0 to 3. Four counter values for each of the 8 states gives 32 combinations. Only 8 of them can be true: for each pattern of seen and unseen threads, exactly one counter value is right. The other 24 are bad states, reachable only through a bug. "All three threads seen, counter 1" is one of them: the zombie badge. Storing one extra number made the states four times as many and added 24 ways to be wrong. Compute the count from the threads every time you need it, and none of those bad states can exist.

Contamination

A small function that builds the icon's label keeps no state of its own, so you would hope it is easy to understand. But it reads the stored counter, so you cannot understand it without knowing every place that changes the counter, and the same goes for every function that calls it, all the way up. The paper calls this contamination: when a stateless procedure uses a stateful one, "even indirectly," it "becomes contaminated and we can only understand it in the context of state." They borrow an old saying: "when you let the nose of the camel into the tent, the rest of him tends to follow." Their verdict:

As a result of all the above reasons it is our belief that the single biggest remaining cause of complexity in most contemporary large systems is state, and the more we can do to limit and manage state, the better.

(p. 8)

Cause Two: Control

Control is the order in which things happen. The paper's example:

a := b + 3
c := d + 2
e := f * 4

The programmer does not care which line runs first; they only want three relationships to hold. But most languages run statements in the order they are written, so the code says more than the programmer meant: it over-specifies the problem. A compiler may then work to establish that the order can be ignored, and every reader has to repeat that work in their head. Here it is easy; in real code it can be very hard, and a wrong guess causes subtle bugs.

Concurrency makes it worse. With shared state, running the same test twice, from the same starting state, with the same inputs, can give different results (picture two updates racing on one counter: one run ends at 2, another at 1). In the paper's words, "things can't really get any worse than that."

Cause Three: Code Volume

Code volume is partly a side effect: "much code is simply concerned with managing state or specifying control." Brooks wrote of complexity's "nonlinear increase with size," and the authors agree this holds in most current systems. But they side with Dijkstra, who argued that with good abstraction the effort to understand a program "need not grow more than proportional to program length." Their bet is that with state and control under control, complexity grows far less clearly nonlinearly with code.

They list the everyday causes (duplicated code, dead code, unnecessary and missed abstraction, poor modularity, poor documentation) and trace them to three principles:

The Classic Fixes

The paper weighs three styles of programming:

• Objects wrap state inside objects, with methods guarding it. But all forms of object-oriented programming still rely on state, and a rule that spans several objects (like "the counter matches the threads") is awkward to enforce: it is "unclear where such multiple-object constraints should reside."
• Pure functions always return the same result for the same arguments (referential transparency), which makes testing and reasoning far more effective. But real programs must remember things. In a pure style the counter becomes an extra parameter in and out (getNextCounter(old) returns (new, result)), and passing one big bundle of values through every function "recreates a single pool of global variables." There is a real trade-off: a stateful program lets you add state without touching the callers; a functional one makes you change every caller, but you can always see what controls the result.
• Logic programming states facts and rules, and in its ideal form leaves the order of the work to the system, with "the tantalising promise" of escaping the complexity caused by control. Prolog only partly delivers it: it processes sub-goals left to right and clauses top down, so "it is necessary to be concerned with the operational interpretation of the program whilst writing the axioms."

None gives you everything, so the paper goes back to first principles.

Essential and Accidental

The paper sharpens Brooks's two words:

Essential Complexity is inherent in, and the essence of, the problem (as seen by the users). … We hence see essential complexity as "the complexity with which the team will have to be concerned, even in the ideal world".

(p. 21)

Accidental complexity is all the rest, "e.g. complexity arising from performance issues and from suboptimal language and infrastructure." The test is strict: if the users do not even know what something is (their examples: "a thread pool or a loop counter"), it cannot be essential. A stored count fails the same test.

In their ideal world, nobody worries about speed. Users describe what they want in informal requirements; you turn them into formal requirements with no view to execution; and the computer simply runs those. They call this "absolute simplicity," and "the very essence of declarative programming": say what you require, not how to achieve it.

Sorting the Data

With that test they sort every kind of data (their Table 1, p. 26), shown here on the messages app:

The ideal world keeps no caches and no stores of derived calculations of any kind. The authors believe "the vast majority of state (as encountered in typical contemporary systems) simply isn't needed." They admit two reasons to keep some accidental complexity anyway: performance (the common one) and ease of expression, the rare case where stored state is the most natural way to say something, like the position of a computer-controlled opponent in a game.

Avoid, Then Separate

The advice fits in two words: avoid and separate. Avoid state and control "where they are not absolutely and truly essential." Then separate what is left into three parts, each written in its own restricted language (their Table 2 and Figure 1):

That gives a powerful test: the system "should still function completely correctly if the 'accidental but useful' bits are removed," just perhaps more slowly. The idea is old: Robert Kowalski, a co-inventor of Prolog, titled a 1979 paper "Algorithm = Logic + Control."

Functional Relational Programming

The second half of the paper sketches an architecture that follows this advice, functional relational programming (FRP), built on Codd's relational model:

• Essential state is stored only as relations: sets of records with named attributes, no duplicates and no order. Here, one relation Thread {thread, seen}.
• Essential logic is relational algebra plus pure functions, with derived relations and integrity constraints that "must hold at all times." In the style of the paper's own example:

Unseen      = restrict(Thread | seen == false)
UnseenCount = count(Unseen)
candidate key Thread = (thread)

Nobody stores the count and nobody updates it by hand. The infrastructure rejects any change that would break a constraint.

• Accidental state and control is a separate list of declarative performance hints, for example declare store UnseenCount, which the infrastructure keeps up to date.
• Feeders turn input into new relation values; observers react when a derived value changes (the icon showing the count).

Because derived data is never fed back in as input, "errors in the logic of the system can never cause it to get into a 'bad state'": you correct the logic, and the system never needs "restarting" or "rebooting." Declarative constraints also add complexity "only linearly," because they cannot interact. Their worked example, an estate agency, uses six base relations, thirteen derived relations and three performance hints.

Facebook's Fix

The fix Facebook shipped reads straight off this picture. In the engineer's words, "what we really want is to keep track of a list of the unseen threads, not just the unseen count." A new message adds its thread to the list; seeing a thread removes it; marking it seen twice is "a no op." The lesson: "we should use more explicit data on the client instead of derived data," where "the unseen threads list is the explicit data and the unseen count is the [derived] data which is the length of that list." That is the paper's split: the list is essential state, the count is derived.

They built this into Flux, where every change flows one way: actions go into the stores, and the stores update the views. The Flux docs tell the same story:

We originally set out to deal correctly with derived data: for example, we wanted to show an unread count for message threads while another view showed a list of threads, with the unread ones highlighted. … These dependencies and cascading updates often occur in a large MVC application, leading to a tangled weave of data flow and unpredictable results.

(Flux docs, In-Depth Overview)

After the switch, the engineer said, the "zombie unseen count" stopped, user tickets about chat dropped sharply, and "this bug hasn't been back to haunt us."

Where It Lives Today

The split is now standard advice for frontend code. React's guide:

Think of state as the minimal set of changing data that your app needs to remember. … Figure out the absolute minimal representation of the state your application needs and compute everything else on-demand.

(React docs, Thinking in React)

Its own example could be our icon: don't store the number of items in a list as another state value, read the length of the array. Another page says it directly: "When something can be calculated from the existing props or state, don't put it in state. Instead, calculate it during rendering."

Redux maps onto the paper's parts: the global state lives "in an object tree within a single store," the only way to change it is to dispatch an action, changes are made by pure functions called reducers, and selectors derive everything else; its docs recommend keeping "the Redux state minimal" and treating "a portion of your store as if it were a database." Redux itself "evolves the ideas of Flux" and takes cues from Elm, whose architecture splits an app into a model (the state), a view and an update.

The performance hints survived too. React's useMemo caches a calculation, and its docs say: "You should only rely on useMemo as a performance optimization. If your code doesn't work without it, find the underlying problem and fix it first." That is the paper's removal test: take the speed trick away, and the answers must not change. None of the pages quoted here cite the paper; they arrived at the same split.

What Aged

FRP was hypothetical when it was written. The authors said so themselves:

FRP is currently a purely hypothetical approach to system architecture that has not in any way been proven in practice.

(p. 42)

At the time it existed only as "token experimental implementations" by the authors; their prototype of the essential state and logic infrastructure was "a mere 1500 lines of Scheme." Later projects took it up: the Project:M36 relational algebra engine, written in Haskell, says it "implements the requirements of this paper." But in everyday frontend code, what spread were the pieces, in a looser form.

Relations lost to object trees. Redux keeps state as an object tree, not relations. Normalizing it like a database (so that each item is "only defined in one place") is a recommendation in Redux's docs ("There is no single required way to store relationships"), not an integrity constraint that the store checks for you, as an FRP infrastructure would.

Speed tricks did not stay in a separate list. Memoization (caching a result so it is not computed again) did not become a declared hint: useMemo is called "at the top level of your component," right next to the logic it speeds up. React Compiler now adds memoization automatically at build time, which is close to the paper's wish to "simply declare" accidental state and "leave it to a completely separate infrastructure" to maintain.

The name. The paper's own footnote warns: "Not to be confused with functional reactive programming," a different idea. Elm's early design came from functional reactive programming, and in 2016 its author replaced everything related to signals with The Elm Architecture (Evan Czaplicki, "A Farewell to FRP").

Still argued, still useful. The paper never measures how much complexity is accidental; it argues it. Its closing lines are honest about that: "So, what is the way out of the tar pit? What is the silver bullet? . . . it may not be FRP, but we believe there can be no doubt that it is simplicity." For systems where the full separation is out of reach, they recommend "avoiding state, avoiding explicit control where possible, and striving at all costs to get rid of code."

The Takeaway

Users give you inputs, and only the inputs you will need again become state. Everything else, like the unseen count, is logic computed from that state, never a copy kept in step by hand. Speed tricks sit off to the side, and taking them away changes how fast the answers come, never what they are.

Store only what the users gave you, derive everything else, and keep anything you add for speed separate from both.

Splitting state from logic is one way to cut a system apart, but the logic itself still has to be divided into modules. Which raises the question that Parnas's paper on decomposing systems into modules answers: when you divide a system into modules, what should each module hide?

References

• Ben Moseley and Peter Marks, "Out of the Tar Pit," February 6, 2006. PDF.
• Fred Brooks, "No Silver Bullet: Essence and Accidents of Software Engineering," 1986 (as cited by the paper).
• "Hacker Way: Rethinking Web App Development at Facebook," 2014 talk, Meta Developers. YouTube (Flux segment from 10:20; quotes from the auto-generated transcript).
• Flux docs, "In-Depth Overview." facebookarchive.github.io/flux.
• React docs: Thinking in React, You Might Not Need an Effect, useMemo, React Compiler.
• Redux docs: Three Principles, Deriving Data with Selectors, Normalizing State Shape, Prior Art.
• Project:M36, README.
• Elm guide, The Elm Architecture; Evan Czaplicki, A Farewell to FRP, 2016.