DEV Community: Hamed Yousefi

The Actor Model: Why It Was Invented and How It Works

Hamed Yousefi — Mon, 26 Oct 2026 17:15:54 +0000

If you have written concurrent code with threads, you know the routine. Several threads touch the same data, so you put a lock around it. Then you add a second lock, take the two in the wrong order on a busy day, and two threads wait for each other forever. Or you forget the lock once, and a counter is off by one in production every few weeks.

The actor model starts from a different question: what if no two pieces of code ever shared memory at all?

This article covers where the idea came from, the problem each step in its history answered, and how an actor works, in pictures. A follow-up article looks at three companies that run actors in production.

The problem: shared memory and locks

Here is a tiny shop with one item left in stock, written two ways.

Left: every thread must remember the lock. Right: only the shop touches stock, so there is nothing to lock.

On the left, three threads read and write one stock variable. Correctness depends on every thread taking the lock, every time, in the same order. The lock also makes threads that want the stock run one after another, which is the opposite of why you added threads. Akka's documentation sums up the second risk in five words: "Locks introduce a new menace: deadlocks."

On the right, the stock belongs to one actor, the shop. Nobody else can read or write it. Anyone who wants to buy sends the shop a message, and the shop handles its messages one at a time. There's no shared variable, so there is nothing to lock.

That is the whole idea. The rest of this article explains how the idea grew up, and what you need around it to build real systems.

Where actors came from

Navy: the theory. Violet: Erlang and OTP, where supervision comes from. Blue and amber: the model reaching the JVM and .NET.

1973: a theory with one kind of object

In August 1973, Carl Hewitt, Peter Bishop and Richard Steiger presented A Universal Modular ACTOR Formalism for Artificial Intelligence at the third International Joint Conference on Artificial Intelligence (IJCAI). Their proposal was radical in its simplicity: everything is an actor, and everything an actor does is send messages to other actors.

The problem they were answering was how to describe computation that happens in many places at once. The usual tools of the time were goto, interrupts and shared variables guarded by semaphores. The paper says its formalism "does not have or need goto, interrupt, or semaphore primitives". Message passing replaces all of them.

1985: what an actor does with a message

The 1973 paper was broad. Gul Agha's 1985 MIT technical report, ACTORS: A Model of Concurrent Computation in Distributed Systems (a book from MIT Press in 1986), pinned the model down. When an actor receives a message, it responds with three things:

a set of messages it sends to other actors,
a set of new actors it creates,
a replacement behavior, which decides how it handles the next message.

Every actor has a mail address, and an actor can only send to addresses it knows. That is the definition most actor systems still follow. Hewitt's later papers state the same three actions and add a point worth remembering: the model itself does not require a mailbox or a thread. Those are implementation choices, though nearly every practical system adds a mailbox.

1986: Erlang reaches the same design by another road

At the Ericsson Computer Science Laboratory, Joe Armstrong, Robert Virding and Mike Williams started work on a new language in 1986. Armstrong's history of the language gives its goal: "a better way of programming telephony applications". A telephone switch handles a huge number of calls at once, must keep running for years, and can't stop because one call hit a bug.

Erlang's answer was many small processes that share no memory and communicate only by asynchronous messages. That is an actor in everything but name, and the name was missing on purpose. On a 2019 panel with Hewitt and Tony Hoare, Armstrong said: "I didn't know about the actor stuff at the time". In a 2014 mailing-list post he named Prolog and Smalltalk as Erlang's influences instead. Two groups, a theorist and a telecom lab, arrived at the same design from different problems.

1996 to 2003: supervision and "let it crash"

Ericsson started the Open Telecom Platform (OTP) project in 1996: a set of Erlang libraries for building telecom systems. It released Erlang and OTP as open source in December 1998.

Armstrong's 2003 PhD thesis, Making reliable distributed systems in the presence of software errors, explains the error-handling style behind OTP. Its slogan is "Let it crash." Instead of writing defensive code for every possible failure, a process that hits an unexpected error simply dies, and a separate process, its supervisor, recovers. Supervisors watch workers and other supervisors, so a whole system becomes a tree of them. We'll come back to this below.

The thesis also reports on Ericsson's AXD301 ATM switch, which had over 1.7 million lines of Erlang in 2003. You may have seen the famous "nine nines" (99.9999999%) availability figure for it. The thesis does quote a customer's figure of that size, and it also notes that how the figure was obtained was not documented. Treat it as a story about a very reliable system, not a measurement.

2009: actors on the JVM

Jonas Bonér started Akka in 2009 (its first commit is from February that year). Akka brought actors, mailboxes and supervision to the Java Virtual Machine, with Scala and Java APIs, so JVM teams could use the model without leaving their platform. Akka's documentation still opens with the problem it answers: the costs of locks and shared memory on modern CPUs.

2014: virtual actors

In 2014, Microsoft Research described Orleans, a .NET framework built around virtual actors. In classic actor systems you create an actor, keep its address, and stop it when you are done. Orleans actors are, in the paper's words, "purely logical entities that always exist, virtually". You never create or destroy them: you call an actor by its ID, and the runtime activates it on some server if it isn't already running. The problem it answered was cloud services with millions of objects, such as players, where managing each actor's lifecycle by hand is a burden. The second article shows Orleans running a real game backend.

How an actor works

With the history in place, here is the model in one picture.

An actor is an address, a mailbox and a behavior with private state. For each message it can do only the three things on the right.

An actor has three parts:

An address. You can send a message only to an actor whose address you have. You get one by creating the actor, or by receiving the address in a message. The address is how the rest of the system refers to the actor; nobody holds a pointer to its insides.
A mailbox. Messages wait here until the actor takes them. Sending is asynchronous: the sender drops the message off and carries on.
A behavior with private state. The actor takes one message at a time, runs its behavior to completion, and only then takes the next. Only the actor reads or writes its state.

For each message, the behavior can do three things: send messages to addresses it knows, spawn new actors, and become a new behavior for the next message. Agha called the last one a replacement behavior; Akka's classic API calls it become. In practice, "become" is often just "update my own state", like setting total from 6 to 7.

Here is a counter actor in pseudocode:

actor Counter(total = 0):
    receive Add(n):
        total = total + n            # only this actor ever touches total
    receive Get(replyTo):
        send(replyTo, Total(total))  # answer with a message, not a return value

Notice what's missing: no lock, no synchronized, no atomic. total can't be corrupted by two threads, because only one message is ever being handled, and only this actor can see total. Akka's docs make the same point: because at most one message is processed per actor at a time, the actor's invariants hold without synchronization.

Also notice Get. There is no return value, because there is no call stack shared between the two actors. The asker includes its own address, and the counter replies with a message.

One message at a time

The mailbox is what turns concurrent senders into sequential processing. Here, three people use one bank account at the same moment:

Watch the balance box: it changes only when the account takes the next message from its mailbox, never while another message is in progress.

alice, bob and carol run concurrently, but the account handles their messages strictly one after another. It needs no lock on balance.

The last frame of the animation is the honest part. The order in which messages from different senders arrive is not fixed. In this run carol is declined; in another, bob would be. Actors remove data races, but they don't remove race conditions in your business logic. If order matters, you have to design for it, for example by putting the decision in one actor that sees all the requests, or by making the protocol explicit.

Location transparency

Because an actor is known only by its address, the sender's code doesn't depend on where the receiver runs.

Path 1 stays in memory. Path 2 is serialized and crosses the network. The send call looks the same for both.

Akka calls this location transparency. Its documentation says its functions work the same in a single JVM or on a cluster, because every interaction between actors is an asynchronous message anyway.

This is what lets an actor system grow from one machine to many without rewriting the code that sends messages. The warning icon in the picture is the catch. The code is the same, but the physics isn't: a remote message is slower and can be lost. Well-designed actor systems treat every message as one that might not arrive, and use timeouts and retries where it matters.

Let it crash: supervision trees

Actors that create other actors form a tree. In Erlang/OTP and Akka, each parent supervises its children: when a child fails, the parent decides what happens.

Follow worker-2's count: 41 before the crash, 0 after the restart. Its siblings never stop counting.

The numbered steps in the animation are the whole recovery:

A bad message makes worker-2 crash. It doesn't try to recover in place.
Its supervisor, payments, is told that the child exited.
The supervisor's strategy picks what to do. Here it's OTP's one_for_one: restart only the failed child.
The worker's old, possibly corrupt, state is thrown away.
It starts again from a known good state.
New messages reach the restarted worker, and the siblings never noticed.

OTP's supervisor documentation defines other strategies too. one_for_all restarts every child when one fails, for children that only make sense together. And restarts are bounded: if a child needs more than a set number of restarts within a set number of seconds (by default, more than 1 restart in 5 seconds), the supervisor gives up, stops its children and itself, and its own parent decides what to do next. A local problem that a restart can't fix gets escalated up the tree.

Why is crashing a good idea? Because most production bugs are rare combinations of state and input. Code that tries to handle every unexpected case gets long and usually wrong. A fresh start from known state fixes the common cases, keeps the error-handling code in one place (the supervisor), and keeps the failure contained to one small actor instead of the whole process.

What actors buy you, compared with locks

	Shared memory and locks	Actors
Who touches the data	Any thread with a reference	Only the owning actor
Data races	Possible whenever a lock is missed	Impossible on actor state
Deadlocks from lock ordering	Possible	No locks to order
Failure	An exception unwinds one thread's stack, often far from anyone who can fix it	The actor dies and its supervisor decides
Scaling out	A rewrite: shared memory doesn't cross machines	The same `send`, to an address on another node

Actors are not free, and it's worth being clear about the costs:

Ordering still matters. As the account example showed, messages from different senders can arrive in any order.
Mailboxes can fill up. If an actor receives messages faster than it handles them, its mailbox grows. Production systems need back-pressure, bounded mailboxes, or both. The second article shows a real case of exactly this.
Two actors can still wait on each other. If A waits for a reply from B while B waits for a reply from A, neither progresses. Timeouts help; so does designing protocols that don't need round trips.
Debugging is different. A bug is a sequence of messages, not a stack trace, so good tracing and logging matter more.

When to reach for actors

Actors fit best when your problem already looks like many independent things with their own state that talk to each other: users, sessions, devices, game players, chat rooms, orders. Each of those becomes an actor, and the runtime spreads them over your cores and machines.

They fit less well for bulk number crunching over shared arrays, or for simple request-response services that keep no state between requests.

The model is fifty years old, and it has outlived many of the languages that first used it, because the problem it answers hasn't changed. Concurrent programs are hard when everything can touch everything. Actors make each piece of state belong to exactly one owner, and they turn failure into something a supervisor can deal with.

In the next article, we'll look at how Discord, LinkedIn and the team behind Halo used actors to serve millions of users.

Sources

Hewitt, Bishop, Steiger. A Universal Modular ACTOR Formalism for Artificial Intelligence. IJCAI 1973, pp. 235–244. https://www.ijcai.org/Proceedings/73/Papers/027B.pdf
Agha. ACTORS: A Model of Concurrent Computation in Distributed Systems. MIT AI Lab Technical Report 844, June 1985. https://dspace.mit.edu/handle/1721.1/6952
Hewitt. Actor Model of Computation: Scalable Robust Information Systems. arXiv:1008.1459. https://arxiv.org/abs/1008.1459
Armstrong. A History of Erlang. HOPL III, 2007. https://doi.org/10.1145/1238844.1238850
Erlang FAQ, "Academic and Historical Questions". https://www.erlang.org/faq/academic.html
Erlang Solutions. Let's #TalkConcurrency panel discussion with Sir Tony Hoare, Joe Armstrong and Carl Hewitt, 2019. https://www.erlang-solutions.com/blog/lets-talkconcurrency-panel-discussion-with-sir-tony-hoare-joe-armstrong-and-carl-hewitt/
Armstrong. "Erlang is not a implementation of the Actor model", erlang-questions mailing list, 25 June 2014. http://erlang.org/pipermail/erlang-questions/2014-June/079891.html
Armstrong. Making reliable distributed systems in the presence of software errors. PhD thesis, KTH, December 2003. https://erlang.org/download/armstrong_thesis_2003.pdf
Erlang/OTP documentation, "Supervisor Behaviour". https://www.erlang.org/doc/system/sup_princ.html
Akka documentation, "Why modern systems need a new programming model". https://doc.akka.io/libraries/akka-core/current/typed/guide/actors-motivation.html
Akka documentation, "How the Actor Model Meets the Needs of Modern, Distributed Systems". https://doc.akka.io/libraries/akka-core/current/typed/guide/actors-intro.html
Akka documentation, "Location Transparency". https://doc.akka.io/libraries/akka-core/current/general/remoting.html
Akka documentation, "Classic Actors" (Become/Unbecome). https://doc.akka.io/libraries/akka-core/current/actors.html
Akka's first commit, 16 February 2009. https://github.com/akka/akka-core/commit/0a31ad718883ef0314de6dc8c6c2c9699eadfdae
Bernstein, Bykov, Geller, Kliot, Thelin. Orleans: Distributed Virtual Actors for Programmability and Scalability. Microsoft Research MSR-TR-2014-41, March 2014. https://www.microsoft.com/en-us/research/publication/orleans-distributed-virtual-actors-for-programmability-and-scalability/

Cutting etcd/raft failover from 1.25 s to 343 ms, checked against 2,000 simulated leader crashes

Hamed Yousefi — Mon, 19 Oct 2026 12:50:09 +0000

When the leader of a three-node etcd/raft cluster dies, the other two servers wait between 1 and 1.9 seconds before one of them holds an election. That's with a tick every 100 ms and the settings from etcd/raft's README: ElectionTick 10 and HeartbeatTick 1. Until a new leader is in place, no write commits. I wanted that gap under a second.

Lowering ElectionTick is a one-line change. What I didn't know was what it does once servers crash and links drop. On a test cluster I could kill leaders and time the gap, but every attempt sees different timing. When one is slow, there's no way to run it again and see why.

So I tried it with faultline, the deterministic simulation testing tool for Go I've been building. Version 0.1.1 came out today. A faultline test runs a distributed system in virtual time on a simulated network and disk. Every random choice in the simulation comes from a seed, so a run replays exactly.

faultline includes a harness for etcd/raft v3.7.0. It runs a cluster of RawNodes with a write-ahead log on the simulated disk and clients that write and read keys, and checks raft's safety properties after every event. It tests the raft library with your settings. The key-value store, the log and the transport on top are the harness's own, not your service's.

Is a shorter timeout still safe?

I started with safety. The first test runs 500 seeds with elections after 3 ticks instead of 10. Each seed runs 60 seconds of virtual time under partitions, an isolated leader, cut and lossy links, crashes, pauses, failed disk syncs and clock drift. The last 10 seconds are quiet, and the cluster must make progress again.

func TestFastElectionsStaySafe(t *testing.T) {
    cfg := etcdraft.DefaultConfig()
    cfg.ElectionTick = 3 // elections after 3 to 5 ticks of 100 ms, instead of 10 to 19
    etcdraft.Test(t, cfg, faultline.Options{Seeds: 500})
}

$ go test -run '^TestFastElectionsStaySafe$' .
ok      example.com/failover    37.110s

No seed broke a safety check or left the cluster stuck. That makes the change safe in these runs. It says nothing yet about how fast failover got.

How long does failover take?

Then I timed it. The next test crashes whichever server leads at 5 seconds, with no other faults, and checks the time until another server becomes leader. etcdraft.Setup builds the cluster inside faultline.Run, and LeaderChanges lists every change of leadership in the run:

// failover crashes whichever server leads at 5s. check gets the time until the next leader and
// the number of elections it took.
func failover(t *testing.T, cfg etcdraft.Config, seeds int, check func(time.Duration, uint64) error) {
    cfg.Faults = etcdraft.FaultsNone // no faults except the crash below
    cfg.Duration = 20 * time.Second
    opts := faultline.Options{Seeds: seeds, Duration: cfg.Duration, Net: etcdraft.NetConfig()}
    faultline.Run(t, opts, func(w *faultline.World) {
        c := etcdraft.Setup(w, cfg)
        crash := kernel.Time(5 * time.Second)
        w.Plan(fault.Script(fault.Event{At: crash, Kind: fault.KindCrash, Role: "leader"}))
        w.Final("new leader after the crash", func() error {
            var oldTerm uint64
            for _, ch := range c.LeaderChanges() {
                if ch.State != raft.StateLeader {
                    continue
                }
                if ch.At <= crash {
                    oldTerm = ch.Term
                    continue
                }
                return check(time.Duration(ch.At-crash), ch.Term-oldTerm)
            }
            return errors.New("no new leader after the crash")
        })
    })
}

func TestFailoverUnderOneSecond(t *testing.T) {
    cfg := etcdraft.DefaultConfig()
    cfg.ElectionTick = 3
    failover(t, cfg, 200, func(d time.Duration, _ uint64) error {
        if d > time.Second {
            return fmt.Errorf("new leader %v after the crash", d)
        }
        return nil
    })
}

It failed on the 45th seed:

$ go test -run '^TestFailoverUnderOneSecond$' .
--- FAIL: TestFailoverUnderOneSecond (1.14s)
    failover_test.go:30: faultline: running 200 seeds from base 0xf41bc040834225b9 (test name)
    --- FAIL: TestFailoverUnderOneSecond/seed=0xe05bdf977f330e42 (0.19s)
        faultline: final check "new leader after the crash" failed after the run at t=20.000000000s
          new leader 1.783042452s after the crash
        replay:    FAULTLINE_SEED=0xe05bdf977f330e42 go test -v -run '^TestFailoverUnderOneSecond$' example.com/failover
        artifacts: /tmp/faultline-501/example.com_failover/TestFailoverUnderOneSecond/e05bdf977f330e42/
    failover_test.go:30: faultline: stopping after failing seed 0xe05bdf977f330e42; 155 of 200 seeds not run (set Options.KeepGoing to run all)
FAIL
FAIL    example.com/failover    1.678s
FAIL

Reading the slow seed

This time I could run the slow one again as often as I liked. The replay command runs the identical run, with the same events at the same virtual times. The failing seed also left an artifact directory, and its text timeline shows what happened after the crash:

grep -E "fault.crash|became (candidate|leader)" timeline.txt

    254  0.220702122s n3#1    etcdraft.raft_log    3 became candidate at term 2 level=info <-253
    300  0.225595569s n3#1    etcdraft.raft_log    3 became leader at term 2 level=info <-299
  18833  5.000000000s n3#1    fault.crash          crash n3 id=1 source=script node=n3 effect=applied <-18832
  18905  5.473915956s n2#1    etcdraft.raft_log    2 became candidate at term 3 level=info <-18904
  18916  5.474188777s n1#1    etcdraft.raft_log    1 became candidate at term 3 level=info <-18915
  19083  5.873566634s n1#1    etcdraft.raft_log    1 became candidate at term 4 level=info <-19082
  19094  5.874618666s n2#1    etcdraft.raft_log    2 became candidate at term 4 level=info <-19093
  19271  6.374222166s n1#1    etcdraft.raft_log    1 became candidate at term 5 level=info <-19270
  19290  6.375359195s n2#1    etcdraft.raft_log    2 became candidate at term 5 level=info <-19289
  19457  6.774700502s n1#1    etcdraft.raft_log    1 became candidate at term 6 level=info <-19456
  19505  6.783042452s n1#1    etcdraft.raft_log    1 became leader at term 6 level=info <-19504

n1 and n2 became candidates within about a millisecond of each other, three rounds in a row. Each voted for itself, so neither got the second vote it needed, and both waited out another timeout. In the fourth round only n1 ran, and it won.

etcd/raft picks each server's timeout in whole ticks: electionTimeout + rand.Intn(electionTimeout), drawn from crypto/rand, which faultline seeds for every run. With ElectionTick 3, a server waits 3, 4 or 5 ticks. The harness starts each server's ticks at a random point within the first interval, as real servers that started at different times would. In this seed, n1's and n2's ticks landed less than half a millisecond apart, and they kept drawing the same number of ticks.

How often does it happen?

One slow seed doesn't give a rate. The next test runs 2,000 crashes per setting and records the time to the next leader and the number of election rounds it took. More than one round means at least one round elected nobody, as in the seed above:

func TestFailoverDistribution(t *testing.T) {
    for _, c := range []struct {
        name  string
        tick  time.Duration
        ticks int
    }{
        {"10 ticks of 100ms", 100 * time.Millisecond, 10},
        {"3 ticks of 100ms", 100 * time.Millisecond, 3},
        {"10 ticks of 30ms", 30 * time.Millisecond, 10},
    } {
        var took []time.Duration
        var repeated, slow int
        t.Run(c.name, func(t *testing.T) {
            cfg := etcdraft.DefaultConfig()
            cfg.TickInterval, cfg.ElectionTick = c.tick, c.ticks
            failover(t, cfg, 2000, func(d time.Duration, elections uint64) error {
                took = append(took, d)
                if elections > 1 {
                    repeated++ // at least one election round elected nobody
                }
                if d > time.Second {
                    slow++
                }
                return nil
            })
        })
        slices.Sort(took)
        n := len(took)
        ms := func(d time.Duration) time.Duration { return d.Round(time.Millisecond) }
        t.Logf("%-17s median %v, p99 %v, max %v; repeated elections in %d, over 1s in %d of %d",
            c.name, ms(took[n/2]), ms(took[n*99/100]), ms(took[n-1]), repeated, slow, n)
    }
}

$ go test -v -run '^TestFailoverDistribution$' . | grep repeated
    failover_test.go:91: 10 ticks of 100ms median 1.249s, p99 1.893s, max 3.155s; repeated elections in 16, over 1s in 1797 of 2000
    failover_test.go:91: 3 ticks of 100ms  median 343ms, p99 622ms, max 1.177s; repeated elections in 27, over 1s in 1 of 2000
    failover_test.go:91: 10 ticks of 30ms  median 381ms, p99 814ms, max 1.418s; repeated elections in 32, over 1s in 7 of 2000

With 3 ticks, half the failovers finished within 343 ms and 99% within 622 ms, against 1.249 s and 1.893 s with the default. One failover in 2,000 took more than a second. About 1.4% needed more than one round.

Fewer ticks or shorter ticks?

The third line is the other way to reach a 300 ms timeout: keep 10 ticks and make each one 30 ms. I expected it to repeat elections less often, because a server then picks from 10 timeouts instead of 3. It didn't. Its median was close, and its tail was worse: 7 failovers over a second, and a p99 of 814 ms.

Three more settings, 2,000 crashes each, point at the reason. Settings whose shortest timeout is 300 ms repeated an election in 24 to 32 of 2,000 failovers, whether they used 3, 10 or 20 ticks. Settings that start at 600 ms or later repeated one in 14 to 20. So the timeout in milliseconds, not the number of ticks, seems to set how often two servers start an election together.

30 ms ticks also cost something that 3 ticks don't. With HeartbeatTick 1, the leader sends a heartbeat every tick, so 30 ms ticks send heartbeats more than three times as often. The same settings passed 500 seeds of the full fault mix, like the 3-tick version:

func TestShortTicksStaySafe(t *testing.T) {
    cfg := etcdraft.DefaultConfig()
    cfg.TickInterval = 30 * time.Millisecond
    etcdraft.Test(t, cfg, faultline.Options{Seeds: 500})
}

$ go test -run '^TestShortTicksStaySafe$' .
ok      example.com/failover    43.569s

What a shorter timeout costs

A shorter timeout reacts faster to every missed heartbeat, not only to a dead leader. I counted the elections in 200 runs of 60 seconds for each setting. With no faults, all three settings held exactly one election per run, the first. Under the default faults, the default setting held 8.95 per run, and the two 300 ms settings 12.7 and 12.4. Each election is a short window with no leader. Some of the extra ones are faster reactions to real failures; others are elections a longer timeout would have ridden out, and these runs don't separate the two.

etcd/raft's documentation suggests ElectionTick = 10 * HeartbeatTick "to avoid unnecessary leader switching". In these runs, the 3:1 setting and the 10:1 setting held the same number of extra elections, so the timeout in milliseconds mattered and the ratio didn't. On a network that loses messages in bursts, the ratio may still matter. The harness doesn't model that kind of loss.

What this doesn't tell you

The harness runs etcd/raft with its own state machine, log and transport. Your service's code is not in the run. To test it, you port it to faultline's node API, and the harness is one worked example of such a port.

The network is a model with 1 ms of latency and up to 2 ms of jitter. One message in 100 is delayed by up to 50 ms more, one in 1,000 is lost, and one in 1,000 is duplicated. A real network with longer stalls, or a process with long garbage collection pauses, needs more headroom than these runs show. Inside the simulation a callback takes no time, so CPU load doesn't slow the cluster down.

Try it

Every test above runs with go test, against the released modules. All four took under four minutes on my laptop, an Apple M4 Max with Go 1.27.1:

go get github.com/hmdsefi/faultline/harness/etcdraft@v0.1.1

I first ran these tests on v0.1.0, and v0.1.1 gives the same numbers. v0.1.1 also adds faultline.RunSeeds, which keeps a failing seed like the slow one above as a regression test.

Test etcd/raft with the harness covers the rest of the harness: cluster sizes, fault presets, snapshots and membership changes. The documentation starts with how an AI coding agent runs the same loop, from a failing seed to a pinned regression test, and the repository is on GitHub.

A Go test that passed 40,000 times, then lost a write under load

Hamed Yousefi — Tue, 13 Oct 2026 16:51:28 +0000

Say a client writes a value and gets a success back. Later, the value is gone. It happens once in production, around the time a node restarts, and every test is green. A week later a CI job fails on a test nobody touched. The re-run passes, so someone adds a retry and moves on.

Bugs like this need a rare timing, such as a partition during a leader election, or a crash after a write was acknowledged but before it reached the disk. Production hits that timing eventually, because it runs all day on busy machines.

A test that passes 40,000 times

Here is a write path cut down to one test, which you can save as wal_test.go in a new module (go mod init wal) and run. The caller puts an entry on a queue and is told the write is safe. A background goroutine moves queued entries to disk, and shutdown tells it to stop.

package wal

import (
    "testing"
    "time"
)

func TestAckedWriteSurvivesShutdown(t *testing.T) {
    queue := make(chan string, 8)
    stop, done := make(chan struct{}), make(chan struct{})
    var disk []string

    go func() { // the writer moves queued entries to disk
        defer close(done)
        for {
            select {
            case e := <-queue:
                disk = append(disk, e)
            case <-stop:
                return // bug: anything still in the queue is lost
            }
        }
    }()

    queue <- "x=1"                    // the caller is told the write is safe
    time.Sleep(50 * time.Microsecond) // "give the writer a moment"
    close(stop)
    <-done
    if len(disk) != 1 {
        t.Fatalf("acknowledged write lost: disk=%v", disk)
    }
}

The bug is in the writer's select. If an entry is still in the queue when the stop signal arrives, both cases are ready. The Go spec says select then picks one of them by uniform pseudo-random selection. If stop wins, the writer returns and the acknowledged entry is lost.

On my 16-core Apple M4 Max laptop with Go 1.27.1, the test passed 40,000 runs in a row while the machine was idle (go test -count=10000, four times). Then I kept every core busy with 32 copies of yes > /dev/null and ran 60,000 more. The test failed 23 times, between 1 and 7 times per 10,000 runs.

The race detector does not catch it. go test -race stayed quiet for 2,200 runs, because there is no data race: closing done orders the writer's last append before the test reads disk.

When the test does fail, this is all you get:

--- FAIL: TestAckedWriteSurvivesShutdown (0.00s)
    wal_test.go:30: acknowledged write lost: disk=[]

There is nothing in that output you can run again. The next run makes its own random choices, and in the 40,000 idle runs, no run lost the write.

Why normal tests miss these bugs

A test controls its inputs. It does not control the clock, goroutine scheduling, the network or the disk, and in a distributed system those decide when things happen:

time.Now and timers follow the wall clock, so whether a timeout fires first depends on how busy the machine is.
The Go runtime decides which goroutine runs next, on several OS threads, and since Go 1.14 it can preempt goroutines asynchronously. There is no way to hand the scheduler a seed.
A TCP connection over localhost does not lose or reorder bytes, and it never runs into a partition. On a real network, packets get lost and reordered, connections stall and break, and partitions happen.
A write that returned is not durable until it is synced, and a test process does not crash between the two.

So a normal test explores a small part of the timings your system can see, mostly the ones an idle laptop produces, and sleeps and retries make this worse. Say someone added the sleep in the example after the test failed once. Without it, the test failed 971 times in 2,000 runs on the same laptop. The sleep did not fix the bug. It made the losing timing rarer, which made the bug harder to find. A retry in CI does the same for the whole suite: it turns a test that hit a bad timing into a green check mark.

That is why I treat a flaky test in a distributed system as a bug report until I can show otherwise. It may have hit a timing the code mishandles, and it came with no steps to reproduce it.

What deterministic simulation testing is

Deterministic simulation testing (DST) takes those sources of nondeterminism away from the machine and gives them to the test. In its usual form, you run the whole system, every node, inside one process, in a simulated world with its own clock, network and disk. The clock there runs on virtual time: it jumps from one event to the next and never waits. Every random choice comes from one number, the seed: which message arrives next, how long it takes, which ready task runs first, whether a disk write survives a crash.

Then you add faults on purpose. The simulator delays and drops messages or delivers them out of order, cuts the network into partitions, crashes and restarts nodes, and fails disk writes. A test runs many seeds and checks, after each run, that the system kept its promises, for example that no acknowledged write was lost.

When a seed fails, you replay it: you run the same seed again and get the same run. Every message and every fault lands at the same point as before, and the run ends in the same failure. The seed is the reproduction. You can add logging or step through the run in a debugger, and once you have a fix, you run the same seed to see whether it passes. After a code change, though, the same seed can take a different path, so one passing seed does not prove the fix.

Apply that to the example. A simulator that controlled the writer's select would make its choice from the seed, so a losing seed would lose the write on every replay.

None of this is new. FoundationDB's simulation runs a whole cluster deterministically in a single-threaded process. It injects faults from broken connections and rebooting machines up to whole datacenters, and the team estimates they have run the equivalent of about a trillion CPU-hours of simulation. TigerBeetle's simulator, the VOPR, stubs out the clock, the network and the disk. It drops and reorders packets, partitions the network, corrupts disk reads and writes, and replays any failure from its seed and Git commit.

Antithesis takes a different route. It built a deterministic hypervisor that runs your whole system on a single CPU core, so the software inside does not have to change. Any bug it finds can be reproduced. FoundationDB and TigerBeetle went the other way: their code is written to run inside their own simulators. FoundationDB even built its own runtime, Flow, which runs the same code in production or in simulation.

Why this is hard in Go

A simulator has to make every choice itself, and the scheduler's choices are not the only ones a Go test cannot control:

Besides select, the spec leaves map iteration order unspecified, and since Go 1.20 the global math/rand generator gets a random seed at startup.
net and os call into the operating system, which a test cannot partition or crash.

Since Go 1.25, the clock is the exception. That release added the testing/synctest package to the standard library. synctest.Test runs a function in a "bubble" whose goroutines see a fake clock. That clock moves forward only when every goroutine in the bubble is durably blocked. Durably blocked means only another goroutine in the bubble can wake it, for example because it waits on a channel created inside the bubble. Tests with timeouts run fast, and the times they read are the same on every run.

I put the example in a bubble with a second file in the same package:

package wal

import (
    "testing"
    "testing/synctest"
)

func TestAckedWriteInBubble(t *testing.T) {
    synctest.Test(t, TestAckedWriteSurvivesShutdown)
}

With the sleep, go test -count=10000 -run TestAckedWriteInBubble passed 10,000 runs out of 10,000, both idle and with every core busy. The fake clock does not move until the writer has emptied the queue and blocked again, so the window for the bug never opens. With the time.Sleep line and the time import deleted, it failed 5,017 times in 10,000: select still picks a ready case at random, and nothing records which one it picked.

Apart from the clock, synctest leaves a test without the controls DST needs. Its API takes no seed, and its documentation says nothing about goroutine order. It has no simulated network or disk and no way to inject faults such as crashes, and the same documentation tells you to avoid the network and use a fake.

So DST in Go today means picking a trade-off. One way is to write the core of a system as a state machine that a simulator drives. The etcd/raft library is built like this: it implements only the Raft algorithm and leaves network and disk I/O to the caller. That gives exact replay, but only for code written that way. The other way is to run ordinary goroutine code and take control of the runtime underneath it. That works with the code you already have. Exact replay is the hard part, because the simulator would have to take over the scheduler and every item in the list at the start of this section.

What I am building

faultline is an open-source deterministic simulation testing tool for Go that runs inside go test. Its first release, v0.1.0, is out. It runs code written for its simulator, plus etcd/raft through a ready-made harness. Running ordinary goroutine code like the example above is the next phase on the roadmap.

Finding cycles and hidden dependencies in go mod graph

Hamed Yousefi — Mon, 12 Oct 2026 17:27:57 +0000

go mod graph prints every requirement in your module graph, one per line. For Prometheus that's 2,510 lines covering 893 module versions. All the information is there, but not in a form you can read. Questions like "do any of these modules require each other?", "what depends on this module?" or "what did this pull request change in my dependencies?" turn into a lot of grep.

The output is a graph, so I loaded it into gograph, the graph library I maintain, and wrote a small program, gomodgraph, that answers those questions. Each command turns out to be a few lines on top of a standard graph algorithm. This post walks through them, with real output from Prometheus. The same algorithms are on gograph.dev, on graphs small enough to step through.

You can run it on your own module with:

go mod graph | go run github.com/hmdsefi/gograph/examples/gomodgraph@latest cycles

Loading the graph

Each line of go mod graph is from to, meaning from requires to:

github.com/prometheus/prometheus cloud.google.com/go/auth@v0.23.3
golang.org/x/crypto@v0.57.0 golang.org/x/net@v0.58.0

The main module has no version, and every other module is written as path@version. Each line becomes one edge:

g := gograph.New[string](gograph.Directed())

scanner := bufio.NewScanner(r)
for scanner.Scan() {
    fields := strings.Fields(scanner.Text())
    if len(fields) != 2 {
        continue
    }
    from, to := fields[0], fields[1]
    _, _ = g.AddEdge(vertex(g, from), vertex(g, to))
}

vertex returns the vertex with that label, or adds it if it's new. The real program also skips the go@ and toolchain@ lines, which aren't modules.

The direction matters for everything that follows. With an edge from -> to, the dependencies of a module are the vertices it can reach, and the modules that depend on it are the vertices that can reach it.

Cycles

Requirement cycles are allowed in Go, and they're common between modules that are released together. They're usually harmless, but they mean that upgrading any module in the cycle raises the others too. That's good to know when an upgrade pulls in more than you expected.

In a directed graph, a cycle is a strongly connected component with more than one vertex. gograph has three algorithms for these. The example uses Tarjan's:

for _, component := range connectivity.Tarjan(g) {
    if len(component) < 2 {
        continue
    }
    labels := make([]string, len(component))
    for i, v := range component {
        labels[i] = v.Label()
    }
    sort.Strings(labels)
    fmt.Println(strings.Join(labels, " "))
}

On Prometheus it finds one cycle:

$ gomodgraph -f graph.txt cycles
go.opentelemetry.io/otel/metric@v1.46.0 go.opentelemetry.io/otel/trace@v1.46.0 go.opentelemetry.io/otel@v1.46.0

otel requires otel/metric and otel/trace, and both of them require otel back. They're released from the same repository with the same version, so that's expected. Loading the graph and finding the cycle takes about 10 ms on my laptop. On a small call graph, the same finder is Tarjan on gograph.dev. The number on that page is measured on the server, separate from this laptop run.

Dependents

"What depends on this module?" means "which vertices can reach it?" The example builds a reversed copy of the graph and walks it breadth-first from each version of the module:

reversed := gograph.New[string](gograph.Directed())
for _, e := range g.AllEdges() {
    _, _ = reversed.AddEdge(
        vertex(reversed, e.Destination().Label()),
        vertex(reversed, e.Source().Label()),
    )
}

it, err := traverse.NewBreadthFirstIterator(reversed, "github.com/golang/protobuf@v1.3.2")
if err != nil {
    return err
}
for it.HasNext() {
    fmt.Println(it.Next().Label())
}

gograph 0.8 also has a dag package, and dag.Ancestors(g, label) does the same walk without building a second graph. Its names follow the build graph convention, where A -> B means "B depends on A". For a requirement graph like this one the meanings swap, so Ancestors returns the dependents.

In Prometheus, 39 modules require some version of github.com/golang/protobuf, directly or indirectly:

$ gomodgraph -f graph.txt dependents github.com/golang/protobuf
github.com/armon/go-metrics@v0.4.1
github.com/envoyproxy/go-control-plane/envoy@v1.39.0
github.com/google/s2a-go@v0.1.10
github.com/hashicorp/consul/api@v1.34.5
...

A shorter walk of the same kind is breadth-first search on gograph.dev.

Why is this module here?

go mod why -m answers a related question, but it looks at the package import graph. It shows which chain of imports needs a module. For a module that no package imports, it prints (main module does not need module ...), even though the module is still in the graph and in go.sum. The requirement graph answers the other half: which chain of go.mod files brought it in.

In a graph where every edge has the same cost, the shortest path comes from a breadth-first search. The iterator returns vertices in order of distance, so the first vertex that has an edge to a new vertex is on a shortest path to it. matches accepts either a module path, which matches every version, or path@version:

parent := map[string]string{start: ""}
for it.HasNext() {
    v := it.Next()
    if v.Label() != start && matches(v.Label(), module) {
        var path []string
        for label := v.Label(); label != ""; label = parent[label] {
            path = append([]string{label}, path...)
        }
        return path
    }
    for _, n := range v.Neighbors() {
        if _, ok := parent[n.Label()]; !ok {
            parent[n.Label()] = v.Label()
        }
    }
}

The output uses the format of go mod why -m:

$ gomodgraph -f graph.txt why github.com/golang/protobuf
# github.com/golang/protobuf
github.com/prometheus/prometheus
github.com/armon/go-metrics@v0.4.1
github.com/golang/protobuf@v1.3.2

Ancestors on gograph.dev answers the same question on a module graph small enough to draw.

What changed between two versions?

Module versions are vertices and requirements are edges, so comparing two graphs takes two set differences. A module version is removed if the new graph doesn't contain its vertex, and a requirement is removed if the new graph doesn't contain its edge:

for _, v := range oldGraph.GetAllVertices() {
    if !newGraph.ContainsVertex(v) {
        fmt.Println("- module", v.Label())
    }
}
for _, e := range oldGraph.AllEdges() {
    if !newGraph.ContainsEdge(e.Source(), e.Destination()) {
        fmt.Println("- require", e.Source().Label(), e.Destination().Label())
    }
}

The same loops with the graphs swapped print what was added. Between Prometheus v3.14.0 and v3.15.0, 277 module versions left the graph and 235 came in, and 1,472 requirements were removed while 1,504 were added. Most of that is version bumps deep in the graph. The lines for the main module show the direct changes. Here are the golang.org/x ones:

$ gomodgraph diff v3.14.0.txt v3.15.0.txt | grep 'require github.com/prometheus/prometheus golang.org/x/'
- require github.com/prometheus/prometheus golang.org/x/crypto@v0.54.0
- require github.com/prometheus/prometheus golang.org/x/mod@v0.38.0
- require github.com/prometheus/prometheus golang.org/x/net@v0.57.0
- require github.com/prometheus/prometheus golang.org/x/text@v0.40.0
- require github.com/prometheus/prometheus golang.org/x/tools@v0.48.0
+ require github.com/prometheus/prometheus golang.org/x/crypto@v0.56.0
+ require github.com/prometheus/prometheus golang.org/x/net@v0.58.0
+ require github.com/prometheus/prometheus golang.org/x/text@v0.41.0

Three of them are upgrades. golang.org/x/mod and golang.org/x/tools have a - line and no + line, so v3.15.0 doesn't list them in its go.mod any more. That's easy to miss in a go.mod diff with dozens of changed lines.

Running it on pull requests

The example's README has a GitHub Actions workflow that runs go mod graph on the base and head commits of a pull request and posts the diff as a comment. That way, reviewers see what a dependency bump pulls in before they approve it.

Watching it run

The Prometheus graph is too big to draw step by step. gograph.dev runs the same algorithms on small graphs, and the timing on each page is measured on the server when the site starts, on the released library.

Tarjan on a call graph, the cycle finder from the first section.
Breadth-first on a network, the walk behind dependents and why.
Ancestors on a module graph, the same question as dependents, on a graph small enough to draw.
Topological sort on that module graph.

Wrapping up

The whole program is about 340 lines, and most of that is argument parsing and output. The graph work is a Tarjan call, two breadth-first searches and a few set checks.

gograph is a generic graph library with no dependencies outside the standard library. It covers dependency graphs (Acyclic() graphs that reject cycles, TopologySort, and the dag package), traversal, shortest paths, strongly connected components and partitioning, and encoding/mermaid writes any graph as a Mermaid flowchart. Version 0.8 made the order of vertices and edges predictable, so results are the same on every run. I wrote about how that works in an earlier post.

Repository: https://github.com/hmdsefi/gograph
Live runs: https://gograph.dev
Documentation: https://pkg.go.dev/github.com/hmdsefi/gograph
Roadmap: https://github.com/hmdsefi/gograph/issues/136

If you run it on your own module and find something surprising, I'd like to hear about it.

Why your topological sort gives a different answer on every run

Hamed Yousefi — Mon, 05 Oct 2026 13:21:27 +0000

You have a few tasks, and some of them depend on others. You put them in a graph, sort it topologically, and print the order. Then you run the program again and get a different order. Both are correct, but your test that compares against an expected slice fails every few runs. And the file you generate from the order changes every time you rebuild it, even though nothing changed.

This happened in gograph, the Go graph library I maintain, until version 0.8. This post explains where the randomness came from, how the library got rid of it without changing its API, and what to do when insertion order isn't enough. The pipeline from the next section is on gograph.dev, where you can step through the sort instead of only reading the code.

Where the randomness comes from

Here's a small build pipeline. Four tasks can run in any order, and release has to wait for all of them:

g := gograph.New[string](gograph.Acyclic())

release := g.AddVertexByLabel("release")
for _, name := range []string{"lint", "vet", "test", "build"} {
    _, _ = g.AddEdge(g.AddVertexByLabel(name), release)
}

for i := 0; i < 5; i++ {
    order, _ := gograph.TopologySort(g)
    // print the labels
}

With gograph v0.7.2, five calls in the same process gave this:

vet test build lint release
lint vet test build release
lint vet test build release
test build lint vet release
lint vet test build release

A topological sort only promises that every vertex comes after the vertices it depends on. Whenever more than one vertex is ready at the same time, the algorithm has to pick one, and any choice is valid. Here, all four tasks are ready from the start.

The graph stored its vertices in a map[T]*Vertex[T], and GetAllVertices built its result by ranging over it. TopologySort then counted the incoming edges of each vertex in another map and found the starting vertices by ranging over that one. The Go spec says the iteration order of a map "is not specified and is not guaranteed to be the same from one iteration to the next", and the runtime randomizes it on purpose, so code can't come to depend on it. So the tie-break was random, and so was the result. That's also why the fix needed more than one change. The maps are still there for lookups, but every loop over a map on that path had to become a loop over a slice.

The same thing happened in every function built on top of the vertex list: the strongly connected component algorithms (Tarjan, Kosaraju and Gabow), maximal cliques, Girvan-Newman communities and transitive reduction. They all gave correct results, but not the same correct result twice. gograph.dev runs those too. Tarjan on a call graph is the one that finds the groups of vertices that can all reach each other.

Keeping the insertion order

The fix is to remember the order the vertices were added. The graph still needs the map, because finding a vertex by its label has to stay fast. Next to it, it now keeps a slice, and each vertex stores its index in that slice:

func (g *baseGraph[T]) addVertex(v *Vertex[T]) *Vertex[T] {
    // ...
    g.vertices[v.label] = v
    v.position = len(g.order)
    g.order = append(g.order, v)
    // ...
}

Adding is an append. Removing is the only tricky part, since deleting from the middle of a slice means moving everything after it. Instead, a removed vertex leaves an empty slot, and once more than half of the slots are empty, the remaining vertices move to the front:

func (g *baseGraph[T]) removeFromOrder(v *Vertex[T]) {
    g.order[v.position] = nil
    g.removedCount++
    if g.removedCount <= len(g.order)/2 {
        return
    }

    n := 0
    for _, u := range g.order {
        if u != nil {
            u.position = n
            g.order[n] = u
            n++
        }
    }
    clear(g.order[n:])
    g.order = g.order[:n]
    g.removedCount = 0
}

Each compaction moves at most as many vertices as were removed since the last one, so a removal still costs O(1) on average.

GetAllVertices now walks the slice and skips the empty slots. Edges got the same treatment: AllEdges groups them by source vertex in insertion order, and within each vertex they're in the order they were added. After that, the algorithms that ranged over maps were changed to range over these slices.

The same program with v0.8.1:

lint vet test build release
lint vet test build release
lint vet test build release
lint vet test build release
lint vet test build release

lint was added first, so it comes first. When several vertices are ready, TopologySort now takes them in the order they were added. All the algorithms listed above give the same result on every run for a graph built the same way. The build pipeline on gograph.dev is this case: lint, vet, test, build, then release.

The change was also faster. Walking a slice beats ranging over a map, and in my benchmarks GetAllVertices got about 6 times faster, AllEdges 3 times and EdgesOf 5 times. On a graph with 100,000 vertices, TopologySort takes about 7 ms.

None of the signatures changed. The order was never documented before, so code that didn't depend on it keeps working, and the docs now say what the order is.

When insertion order isn't enough

Insertion order moves the problem to whoever builds the graph. If you fill the graph from a map, from files listed in directory order, or from results that come back from goroutines, the insertion order is random again, and so is the sort. Here's the same pipeline built twice, with the tasks added in a different order:

a := build([]string{"lint", "vet", "test", "build"})
b := build([]string{"build", "test", "vet", "lint"})

TopologySort follows each graph's insertion order, so the results differ:

lint vet test build release
build test vet lint release

For this case, 0.8 added StableTopologySort. It takes a compare function, and whenever several vertices are ready, it picks the smallest one:

stableA, _ := gograph.StableTopologySort(a, cmp.Compare[string])
stableB, _ := gograph.StableTopologySort(b, cmp.Compare[string])

build lint test vet release
build lint test vet release

The ready vertices go in a heap ordered by the compare function, so the sort runs in O((V + E) log V) instead of O(V + E). On the 100,000 vertex graph it takes about 15 ms, twice as long as TopologySort. That's the price of an order that doesn't depend on how the graph was built. If you build the graph in a fixed order anyway, TopologySort is enough. gograph.dev runs that stable sort on the same pipeline, and both graphs come out build lint test vet release.

The general lesson

Any algorithm that has to make an arbitrary choice, like which ready vertex goes next or which neighbor to visit first, takes that choice from whatever order its data is in. If the data is in a map, the choice is random. The algorithm is still correct, but its output can't be tested with a simple comparison, cached or diffed.

The fix doesn't have to be expensive. Keep a slice next to the map when you need insertion order, or sort the candidates when you need an order that doesn't depend on history. It's worth deciding which one your API promises and writing it in the docs, because someone will eventually depend on it.

gograph is a generic graph library for Go with no dependencies outside the standard library. Besides topological sorting, it covers traversal, shortest paths, strongly connected components and partitioning. Version 0.8 also added a dag package for dependency questions and encoding/mermaid for drawing graphs. gograph.dev runs the ones in the current release, step by step, and each page shows how long that run took on the server.

The sort from this post: https://gograph.dev/algorithms/topological-sort/build-pipeline
The stable sort: https://gograph.dev/algorithms/stable-topological-sort/build-pipeline
All of the runs: https://gograph.dev
Repository: https://github.com/hmdsefi/gograph
Documentation: https://pkg.go.dev/github.com/hmdsefi/gograph
The change itself: https://github.com/hmdsefi/gograph/pull/167