Learn Rust Series (#67) - Memory Ordering: Relaxed, Acquire, Release, and SeqCst

scipio(71)

Published in

StemSocial

Words

3101

Reading

14 min

Listen

Play

Learn Rust Series (#67) - Memory Ordering: Relaxed, Acquire, Release, and SeqCst

What will I learn

You will learn why every atomic operation takes an Ordering, and what "reordering" by the CPU and compiler actually means;
what Relaxed guarantees (atomicity, and nothing more) and the narrow cases where that is genuinely enough;
how Release and Acquire pair up to publish data written around an atomic and observe it safely on the other side;
what SeqCst buys you -- a single global order every thread agrees on -- and what it costs;
a practical, honest rule of thumb for picking an ordering without needing a PhD in memory models.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Rust toolchain (via rustup, from rustup.rs);
The previous sixty-six episodes, especially atomics (episode 66), Arc (episode 34), and threads;
The ambition to learn systems programming from the ground up.

Difficulty

Advanced

Curriculum (of the `Learn Rust Series`):

Learn Rust Series (#67) - Memory Ordering: Relaxed, Acquire, Release, and SeqCst

Every single atomic operation in the last episode took a second argument I quietly waved away as "a black box marked Relaxed", and I promised we would open the box today. Here it is. This is the deepest water in the whole series, so I am going to keep it as concrete and hands-on as I can, and I am going to be honest with you about where the genuinely hard parts begin ;-)

The one-sentence version is this: memory ordering is how you tell the compiler and the CPU which reorderings of memory operations they are not allowed to do around an atomic. That sentence will only make sense once you accept a surprising fact -- that both the compiler and the hardware routinely reorder your memory reads and writes, on purpose, for speed. On a single thread you never notice, because they are careful to preserve the result as that one thread would observe it. Across threads, that reordering leaks into view, and one thread can genuinely see another thread's writes land in a different order than the source code performed them. Ordering is the dial that reins that in.

First, though, as always, last episode's homework. Episode 66 was atomics -- AtomicUsize, fetch_add, and compare-and-swap -- so all three solutions live in std::sync::atomic.

Solutions to Episode 66 Exercises

Exercise 1 asked you to use AtomicUsize::fetch_add from several threads to count how many events happened across all of them, join the threads, and confirm the exact total:

use std::sync::Arc;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;

fn main() {
    let events = Arc::new(AtomicUsize::new(0));
    let mut handles = Vec::new();
    for _ in 0..5 {
        let e = Arc::clone(&events);              // share the one counter
        handles.push(thread::spawn(move || {
            for _ in 0..20 {
                e.fetch_add(1, Ordering::Relaxed); // indivisible +1, no update lost
            }
        }));
    }
    for h in handles { h.join().unwrap(); }
    println!("{}", events.load(Ordering::Relaxed)); // 100, exactly, every run
}

Five threads, twenty increments each, and fetch_add fuses the read-add-write into one uninterruptible step -- so the answer is always exactly 100. Relaxed is the correct ordering here, and the rest of this episode is largely about explaining why it is correct here and dangerous elsewhere.

Exercise 2 wanted a one-shot "claim" built on compare_exchange over an AtomicBool: many threads race, but only the very first to flip false to true may win, and it should announce that it won:

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;

fn main() {
    let claimed = Arc::new(AtomicBool::new(false));
    let mut handles = Vec::new();
    for id in 0..8 {
        let c = Arc::clone(&claimed);
        handles.push(thread::spawn(move || {
            // succeeds for exactly ONE thread: the one that sees false and installs true
            if c.compare_exchange(false, true, Ordering::SeqCst, Ordering::SeqCst).is_ok() {
                println!("thread {id} won the claim");
            }
        }));
    }
    for h in handles { h.join().unwrap(); }
}

The whole point is that compare_exchange reads and conditionally writes in a single indivisible motion. The first thread finds false, swaps in true, and gets Ok; every later thread now finds true, the comparison fails, it gets Err, and it stays silent. Exactly one winner, no lock, no coordination -- and which thread wins varies run to run, because that is the scheduler being honest with you.

Exercise 3 was the CAS loop that atomically doubles a stored value -- an operation the hardware does not offer as a single fetch_* -- called from two threads:

use std::sync::Arc;
use std::sync::atomic::{AtomicI64, Ordering};
use std::thread;

fn double(a: &AtomicI64) {
    let mut current = a.load(Ordering::Relaxed);
    loop {
        let doubled = current * 2;
        match a.compare_exchange_weak(current, doubled, Ordering::Relaxed, Ordering::Relaxed) {
            Ok(_) => return,                 // our doubling landed
            Err(actual) => current = actual, // lost the race; retry from the fresh value
        }
    }
}

fn main() {
    let n = Arc::new(AtomicI64::new(3));
    let a = Arc::clone(&n);
    let b = Arc::clone(&n);
    let h1 = thread::spawn(move || double(&a));
    let h2 = thread::spawn(move || double(&b));
    h1.join().unwrap();
    h2.join().unwrap();
    println!("{}", n.load(Ordering::Relaxed)); // 12, always: 3 -> 6 -> 12
}

Here is the subtle bit worth reasoning about: even though the two threads race, the final value is deterministic. Doubling twice always multiplies by four, and 3 times 4 is 12, regardless of who goes first. The CAS loop guarantees neither doubling is ever lost -- if the two threads read 3 at the same instant, one wins with 6, the other's swap fails, it re-reads 6, and doubles that to 12. The retry is what turns a racy read-modify-write into a correct one. Right, homework cleared -- now let us finally open the Ordering box.

Why ordering exists at all

Start with the thing that trips everyone up the first time. Consider two threads sharing two plain variables, x and y, both starting at zero. Thread A writes x = 1 then reads y. Thread B writes y = 1 then reads x. Your intuition says at least one of them must read a 1 -- surely they cannot both read 0, because one write must happen first. And yet on real hardware, both threads reading 0 is a genuinely possible outcome. The CPU is allowed to buffer thread A's write to x in a private store buffer and let A's read of y run first, and symmetrically for B. Neither thread violated its own single-threaded logic, but together they produced a result no sequential interleaving can explain.

That is reordering, and it comes from two places. The compiler reorders instructions during optimisation (moving a load earlier, sinking a store later, keeping a value in a register instead of re-reading memory). The CPU reorders at runtime through store buffers, out-of-order execution, and per-core caches. Both are free to do this as long as a single thread cannot tell -- and a single thread never can. The trouble is only ever between threads, which is exactly the world atomics live in.

So an atomic operation with Relaxed ordering guarantees the operation itself is indivisible, but promises nothing about how it orders relative to the surrounding memory accesses. The compiler and CPU stay free to slide independent operations across it:

use std::sync::atomic::{AtomicUsize, Ordering};

fn main() {
    // The Ordering argument says what may NOT be reordered around this access.
    // Relaxed says: keep this operation atomic, but otherwise reorder freely.
    let a = AtomicUsize::new(0);
    a.store(1, Ordering::Relaxed); // atomic write, but no ordering promise vs other memory
    let seen = a.load(Ordering::Relaxed);
    println!("{seen}"); // 1
}

The four orderings you will actually use are, from weakest to strongest, Relaxed, then the Acquire/Release pair, then SeqCst. Each one forbids strictly more reordering than the last, and costs strictly more to enforce. The whole game is picking the weakest ordering that is still correct for what you are doing.

Relaxed: atomicity without any ordering

Relaxed gives you the atomicity and nothing else. That sounds nearly useless, but there is one very common situation where it is exactly right: a standalone counter or statistic, where each thread only needs its own update not to be lost, and no thread ever draws a conclusion about other memory from the counter's value. A hit counter, a metrics tally, a number of processed jobs -- none of these are guarding anything else, so their ordering with other data simply does not matter:

use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
use std::thread;

fn main() {
    let hits = Arc::new(AtomicU64::new(0));
    thread::scope(|s| {
        for _ in 0..4 {
            let h = &hits;
            s.spawn(move || {
                for _ in 0..100 {
                    h.fetch_add(1, Ordering::Relaxed); // just don't lose an update
                }
            });
        }
    });
    println!("{}", hits.load(Ordering::Relaxed)); // 400
}

The test I use to decide whether Relaxed is safe is a single question: does any thread use this atomic's value to decide it is safe to touch some other piece of memory? If the answer is no -- as with a pure counter -- Relaxed is correct and it is the cheapest option you have. The moment the answer becomes yes, you have left Relaxed behind, and you need the next tool.

Release and Acquire: publishing data through a flag

This is the pairing that earns its keep in real code, so slow down here. The classic pattern is: one thread prepares some data, then sets a flag to say "it is ready"; another thread spins until it sees the flag, then reads the data. For this to be correct, the reader must be guaranteed that once it sees the flag set, it also sees every write the writer made before setting the flag. Relaxed does not give you that. Release and Acquire do.

A Release store acts as a one-way barrier: no memory write that appears before it in program order may be moved after it. An Acquire load is the mirror image: no memory read after it may be moved before it. When an Acquire load reads the value written by a Release store on the same atomic, the two form a happens-before edge, and every write the writer did before its Release becomes visible to the reader after its Acquire:

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, AtomicU32, Ordering};
use std::thread;

fn main() {
    let ready = Arc::new(AtomicBool::new(false));
    let data = Arc::new(AtomicU32::new(0));

    let (r2, d2) = (Arc::clone(&ready), Arc::clone(&data));
    let producer = thread::spawn(move || {
        d2.store(99, Ordering::Relaxed);   // 1: write the payload first
        r2.store(true, Ordering::Release); // 2: publish -- no earlier write may cross this
    });

    while !ready.load(Ordering::Acquire) {} // 3: once we observe true, the 99 is visible too
    producer.join().unwrap();
    println!("consumer sees: {}", data.load(Ordering::Relaxed)); // 99, guaranteed
}

Trace the guarantee. The producer's data store is Relaxed, yet the consumer is still guaranteed to see 99. Why? Because the Release on ready forbids the data = 99 write from sliding past it, and the Acquire on the consumer side forbids the data read from sliding before the flag check. The happens-before edge, created the instant the Acquire load observes the Release store's true, drags all the surrounding writes across with it. That is the entire mechanism behind safely handing data from one thread to another without a lock.

The rule to burn into memory: a Release store pairs with an Acquire load on the same atomic. Release is the sender, Acquire is the receiver. Neither one does anything useful alone -- a lone Release with no Acquire reading it, or an Acquire reading a value nobody Released, buys you nothing. They are two halves of one handshake. And notice this is exactly what a Mutex does under the hood: lock() performs an Acquire, unlock() performs a Release, which is precisely why everything you did inside one critical section is visible to the next thread that takes the lock.

SeqCst: one global order everyone agrees on

SeqCst -- sequentially consistent -- is the strongest ordering and, paradoxically, the easiest to reason about. It gives you everything Acquire/Release do, and adds one more promise on top: all SeqCst operations across all threads appear in a single total order that every thread agrees on. There is one global timeline, and every sequentially-consistent operation slots into it at one point. This is the model your intuition already wants the hardware to have, before you learned it does not:

use std::sync::atomic::{AtomicUsize, Ordering};

fn main() {
    let x = AtomicUsize::new(0);
    x.store(1, Ordering::SeqCst);
    x.fetch_add(41, Ordering::SeqCst);
    println!("{}", x.load(Ordering::SeqCst)); // 42
}

Because it restores that single-timeline intuition, SeqCst is the safe default when you are not sure -- and remember the store-buffer puzzle from earlier (both threads reading 0)? Make all four of those accesses SeqCst and that outcome becomes impossible, because a global order cannot let both loads precede both stores. The price is real, though: on x86 a SeqCst store typically needs a full memory fence instruction, and on weaker architectures like ARM it is more expensive still. So SeqCst is correct-but-slightly-slow, and in concurrent code correct-but-slightly-slow beats fast-but-wrong every single time.

A tour of all four on one atomic

Here they are together, weakest to strongest, so the progression sits in one place:

use std::sync::atomic::{AtomicUsize, Ordering};

fn main() {
    let a = AtomicUsize::new(0);
    a.store(1, Ordering::Relaxed);     // atomicity only, no ordering promise
    let _ = a.load(Ordering::Acquire); // pairs with a Release store elsewhere
    a.store(2, Ordering::Release);     // pairs with an Acquire load elsewhere
    a.fetch_add(1, Ordering::SeqCst);  // also joins the single global order
    println!("{}", a.load(Ordering::SeqCst)); // 3
}

Note that a read-modify-write like fetch_add can carry an AcqRel ordering too -- Acquire on the value it reads and Release on the value it writes -- which is the natural choice when a single operation both consumes a published value and publishes a new one. It is Ordering::AcqRel, and it is the fifth name you will meet once the two lock-free structures in the next episodes need it.

Fences: a barrier not tied to any one atomic

Occasionally you want an ordering barrier that is not attached to a specific atomic operation -- the constraint spans several accesses rather than living on one of them. std::sync::atomic::fence gives you exactly that: a standalone ordering point:

use std::sync::atomic::{AtomicBool, Ordering, fence};

fn main() {
    let flag = AtomicBool::new(false);
    flag.store(true, Ordering::Relaxed);
    fence(Ordering::Release); // barrier independent of any single atomic operation
    let seen = flag.load(Ordering::Relaxed);
    fence(Ordering::Acquire);
    println!("{seen}"); // true
}

Fences show up mostly in advanced lock-free code where you want a batch of Relaxed operations to be published all at once by a single Release fence, rather than paying for ordering on each individual store. You will not need them often, but it is worth knowing the tool exists so it does not look like magic when you meet it in someone else's crate.

How Python and Go would frame this

A glance sideways sharpens the picture, as it usually does in this series. Python essentially hides the whole topic behind the Global Interpreter Lock. Because only one thread runs Python bytecode at a time, the language behaves as if it were sequentially consistent at the bytecode level -- there is no Ordering to pick because there is no user-visible reordering to control. You pay for that simplicity with the GIL itself:

import threading

ready = False
data = 0

def producer():
    global ready, data
    data = 99
    ready = True   # no Release needed: the GIL serialises bytecode already

def consumer():
    while not ready:  # no Acquire needed for the same reason
        pass
    print("consumer sees:", data)  # 99

t1 = threading.Thread(target=consumer)
t2 = threading.Thread(target=producer)
t1.start(); t2.start()
t1.join(); t2.join()

It works, but only because the GIL is doing globally, and expensively, what a single Release/Acquire pair does locally and cheaply in Rust. Go, being a systems language, has real atomics in sync/atomic, but it made the opposite choice from Rust: every atomic operation is sequentially consistent, full stop. There is no dial to turn:

import "sync/atomic"

var ready atomic.Bool
var data atomic.Int32

func producer() {
    data.Store(99)   // always SeqCst-strength in Go
    ready.Store(true)
}

// consumer spins on ready.Load(), then reads data.Load()

Go's memory model then layers a separate happens-before story on top, expressed mostly through channels rather than orderings. The trade is clear: Go is simpler because it welds the dial to SeqCst, and Rust is more to learn but lets you say Relaxed on a hot counter and shave off the barriers you do not need. Same primitives underneath -- Rust just hands you the knob the others hide.

The honest, practical guidance

Full memory-model reasoning is genuinely hard, and I am not going to pretend otherwise. So here is the guidance I actually use, and it will carry you a very long way. Use Relaxed for standalone counters and statistics, where no other memory hangs off the value. Use a Release/Acquire pair whenever you publish data through a flag -- Release on the store that announces it, Acquire on the load that observes it. Reach for SeqCst when several atomics must agree on a single global order, or simply when you are unsure and want the least surprising mental model. And whenever you write genuinely lock-free code, test it hard -- ideally under Miri or a thread sanitiser -- because ordering bugs love to stay invisible on your machine and then ruin someone else's, only on Tuesdays, only under load.

The reason this matters so much right now is that we are about to spend it. Next episode we stop reasoning about ordering in the abstract and put it to work building a real lock-free stack -- the first data structure in this series with no Mutex anywhere, where a misplaced Relaxed is the difference between a structure that works and one that quietly corrupts itself. Everything you just learned about Release publishing a node and Acquire observing it is the machinery that makes that stack correct. The deep water was worth wading into, because now we get to swim ;-)

Exercises

Build a Release/Acquire flag that publishes a value stored just before the flag is set: one thread writes a number with a Relaxed store then sets an AtomicBool with Release; another spins on an Acquire load and prints the number once the flag is seen.
Count from several threads into one AtomicU64 with fetch_add(1, Ordering::Relaxed), join them, print the total, and in a comment explain in your own words why Relaxed is safe for this particular use.
Use SeqCst on an atomic where a single global order genuinely matters -- for example a one-shot claim that several threads race for -- and describe in a comment why a weaker ordering would leave you unsure of the outcome.