Concurrency, Synchronization & Deadlock Questions

Recommendation

Default to ordinary locks (a mutex, a sharded mutex, or a reader-writer lock). Use lock-free structures only when a measurement shows the lock is the bottleneck, or when a hard constraint forbids blocking (a signal handler, a real-time thread, a path where a lock holder being descheduled would break a latency target). Even then, take a tested implementation instead of writing your own. A lock-free structure is not automatically faster; the measurement below shows a case where it is slower.

Progress guarantees, in plain terms

A blocking algorithm can be stuck forever if one thread (say, a lock holder) is descheduled or dies. The non-blocking levels are:

• Obstruction-free: a thread running alone finishes in a bounded number of steps. Example: an update that backs out and retries when it detects another thread interfering; two threads can keep backing each other out, but one running alone completes.
• Lock-free: when the program runs long enough, at least one thread makes progress (the system is never stuck, but an individual thread can retry indefinitely). Example: a CAS retry loop.
• Wait-free: every operation finishes in a bounded number of steps (no individual thread starves). Example: the single hardware atomic add mentioned below, which has no retry loop.

(These match the definitions in the Wikipedia article "Non-blocking algorithm".) A compare-and-swap (CAS) loop (read a value, compute a new one, store it only if nobody changed it, otherwise retry) is lock-free: a failed CAS means another thread's CAS succeeded, but one thread can keep losing. A single hardware atomic add (fetch_add) has no retry loop on CPUs that implement it directly.

What lock-free costs

• Memory reclamation: when a node is unlinked, other threads may still hold a pointer to it, so freeing it is dangerous. You need hazard pointers (each thread publishes "I am using this node" in a slot, and nobody frees a node that appears in a slot), epochs (a global counter; a node is freed only after every thread has moved past the epoch in which it was unlinked) or RCU (read-copy-update, a scheme where deleters wait until readers are done), which add code and per-thread state.
• The ABA problem: a CAS sees the same value A, but in between it changed to B and back to A (for example, a node freed and its address reused). The CAS succeeds when it should not. Concrete values (illustrative addresses): thread 1 reads head = node A at 0x100 whose next is B, and is paused. Thread 2 pops A, pops B, frees both, then pushes a new node that the allocator places at 0x100 again, whose next is C. Thread 1 resumes and runs CAS(head, A, B): head is 0x100, so it succeeds and sets head to B, which was freed (and is no longer in the stack), so the stack is now corrupt.
• Memory ordering: you must choose the weakest correct order for each atomic. Wrong choices often work on x86 and fail on Arm.
• Composability: an atomic operation changes one word. Updating two fields consistently needs a different design.
• Retry cost under contention: failed CAS attempts are wasted work and cache-line traffic.

Measured contention behaviour

A deliberately simple case: all threads increment one shared counter, using a mutex, an atomic fetch_add, and a CAS loop. The numbers are total throughput in millions of operations per second (Mops/s, summed over all threads, higher is better) from the program below, built with g++ -std=c++20 -O2 -pthread and run in a Docker Linux VM (aarch64, 14 vCPUs) on a Mac that was also running other jobs. checks: 1 means true: the three counters all ended equal to the expected total, so no increment was lost. One sample run:

threads  mutex   fetch_add  cas_loop   (Mops/s total)
1        209      542         541
2        28      238         304
4        57      151         91
8        59      37         16
checks: 1

Repeated runs of the same program varied a lot (the two-thread and eight-thread rows most of all, and a column order seen in one run was sometimes reversed in another), so the table is one sample, not a result. What recurred across many re-runs is the broad shape: with one thread the atomics are well ahead of the mutex; with two threads the atomics are ahead and the mutex is much lower; with four threads the three are closer together and the CAS loop can drop to the mutex's level; with eight threads the atomics lose their lead and the mutex is usually, but not always, on top. The shape matters more than the digits. Reading it (the explanations below are ESTIMATES, not measured):

• One thread, no contention: the atomic versions are typically about two to three times faster than the mutex (about 2.6 times in the sample), because a mutex does extra work to lock and unlock.
• Two to four threads: the atomics are ahead of the mutex (for example 238 and 304 against 28 at two threads in the sample), but the gap shrinks quickly and the spread is wide; at four threads the CAS loop can fall to the mutex's level. The mutex drop in the sample, from 209 to 28 once a second thread appears, is plausibly because a contended mutex makes waiting threads sleep and be woken, which costs far more than the uncontended lock and unlock.
• Eight threads on one hot counter: the atomic versions lose their lead: in most runs the mutex is ahead of both the CAS loop and fetch_add, though not in every run (in the sample, 59 against 37 for fetch_add and 16 for CAS). A plausible explanation: every operation needs exclusive ownership of the same cache line, failed CAS attempts add wasted work, and under a mutex blocked threads sleep instead of all fighting for the line. Do not treat these numbers as general; they come from one shared VM, one trivial critical section, and say nothing about tail latency (the time taken by the slowest few percent of operations, which is what a user notices).

The better fix for a hot counter is neither: keep one counter per thread and add them up when read.

The program that produced the table:

#include <atomic>
#include <chrono>
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>
using namespace std::chrono;

template <class F>
double run(int threads, long per_thread, F body) {   // million ops per second
    std::vector<std::thread> ts;
    auto t0 = steady_clock::now();
    for (int i = 0; i < threads; ++i) ts.emplace_back([&] { for (long k = 0; k < per_thread; ++k) body(); });
    for (auto& t : ts) t.join();
    double s = duration<double>(steady_clock::now() - t0).count();
    return threads * per_thread / s / 1e6;
}

int main() {
    const long N = 2'000'000;
    std::mutex m; long locked = 0;
    std::atomic<long> faa{0}, cas{0};
    std::cout << "threads  mutex   fetch_add  cas_loop   (Mops/s total)\n";
    for (int t : {1, 2, 4, 8}) {
        double a = run(t, N, [&] { std::lock_guard<std::mutex> g(m); ++locked; });
        double b = run(t, N, [&] { faa.fetch_add(1, std::memory_order_relaxed); });
        double c = run(t, N, [&] {
            long v = cas.load(std::memory_order_relaxed);
            while (!cas.compare_exchange_weak(v, v + 1, std::memory_order_relaxed)) {}
        });
        std::cout << t << "        " << (long)a << "      " << (long)b << "         " << (long)c << "\n";
    }
    const long expected = N * (1 + 2 + 4 + 8);   // every thread count adds threads * N increments
    std::cout << "checks: " << (locked == expected && faa.load() == expected && cas.load() == expected) << "\n";
}

When lock-free is actually faster

• Low contention per memory location, many cores, short operations: as in the one and two thread rows.
• Readers that write no shared, contended memory (RCU-style reads write nothing; hazard-pointer reads write only to a per-thread slot): reads scale while a lock's reader count would bounce a cache line.
• A lock holder can be descheduled (more runnable threads than cores): with a lock, everyone waits for the sleeping holder; with lock-free, others proceed. This helps tail latency, which the benchmark above does not measure.
• Places that cannot take a lock at all: signal handlers, interrupt handlers sharing data with threads, real-time threads where taking a lock invites priority inversion (a high-priority thread waiting on a low-priority lock holder).

It is slower or no better when one word is hammered by many threads (the eight-thread row), when the critical section is large (the lock-free version just copies more), or when the team cannot maintain the subtle code. Verify any lock-free code with ThreadSanitizer and stress tests, and test on a weakly ordered CPU such as Arm as well as x86.

Direct answer

Use a token bucket in its single-word form (the Generic Cell Rate Algorithm, GCRA): each limiter keeps one 64-bit atomic, the theoretical arrival time (TAT, the earliest time the next request would be on schedule). A caller computes a new TAT from the current time and either rejects (no write) or installs it with one compare-and-swap (CAS), an atomic "write this only if the value is still what I read" instruction. There is no lock, state is one word per key, bursts up to burst are allowed, and the long-run rate can never exceed rate.

Why one word instead of the textbook bucket

The textbook bucket holds up to capacity tokens and spends one per request; it stores tokens (how many are left) and last_refill (when tokens were last topped up), and on each request it first adds (now - last_refill) * rate tokens, capped at capacity, then spends one if any remain. Those two fields must change together, so a naive version needs a mutex (or a double-width CAS). GCRA folds both into the single value TAT, so one CAS updates the whole state.

Let T = 1/rate be the emission interval and B = burst * T the burst tolerance. For a request at time now:

start   = max(TAT, now)
new_TAT = start + T
allow   iff  new_TAT - now <= B

Why one number is enough: max(TAT - now, 0) is how far the schedule is ahead of the clock, which is the burst allowance already used, so the tokens left are floor((B - max(TAT - now, 0)) / T). A request is allowed exactly when at least one token is left, which is the same test as new_TAT - now <= B. Time passing lowers TAT - now by itself, so refilling needs no stored last_refill.

Hand trace with rate = 10/s, burst = 5 (so T = 100 ms, B = 500 ms), TAT starting at 0 and times in milliseconds. Requests at now = 0: TAT goes 100, 200, 300, 400, 500 (five allowed, tokens left 4, 3, 2, 1, 0); the sixth would give new_TAT = 600, and 600 - 0 = 600 > 500, so it is rejected with no write. At now = 300 tokens left are (500 - 200) / 100 = 3: three requests move TAT to 600, 700, 800 and a fourth is rejected. The equivalent textbook bucket (capacity 5) goes 5, 4, 3, 2, 1, 0 tokens, refills 3 tokens in 300 ms, and spends them, matching the program output below.

If allowed, CAS TAT from the value you read to new_TAT. If the CAS fails another caller moved TAT; reload and recompute. The time until a rejected caller may retry is TAT + T - B - now, usable for a Retry-After value (the HTTP response header that tells a client how long to wait, given either as a number of seconds or as a date).

Implementation, run under ThreadSanitizer

#include <atomic>
#include <cstdint>
#include <cstdio>
#include <thread>
#include <vector>

// Token bucket in "virtual scheduling" form (GCRA): one atomic word, the
// theoretical arrival time (TAT) in nanoseconds. Time is injected so the test is deterministic.
class RateLimiter {
public:
    RateLimiter(std::uint64_t rate_per_sec, std::uint64_t burst)
        : interval_ns_(1'000'000'000ull / rate_per_sec),
          burst_ns_(burst * interval_ns_), tat_(0) {}

    bool try_acquire(std::uint64_t now_ns) {
        std::uint64_t tat = tat_.load(std::memory_order_relaxed);
        for (;;) {
            std::uint64_t start = tat > now_ns ? tat : now_ns;
            std::uint64_t new_tat = start + interval_ns_;
            if (new_tat - now_ns > burst_ns_) return false;   // bucket empty: reject, no write
            if (tat_.compare_exchange_weak(tat, new_tat,
                                           std::memory_order_relaxed,
                                           std::memory_order_relaxed))
                return true;                                  // on failure tat is reloaded; retry
        }
    }
private:
    const std::uint64_t interval_ns_, burst_ns_;
    alignas(64) std::atomic<std::uint64_t> tat_;              // own cache line
};

// Releases all threads at the same instant (a spin gate), so their first calls really overlap.
static long hammer(RateLimiter& rl, std::uint64_t now_ns, int threads, int tries) {
    std::atomic<long> granted{0};
    std::atomic<bool> go{false};
    std::vector<std::thread> ts;
    for (int i = 0; i < threads; ++i)
        ts.emplace_back([&] {
            while (!go.load()) {}
            for (int k = 0; k < tries; ++k)
                if (rl.try_acquire(now_ns)) granted.fetch_add(1, std::memory_order_relaxed);
        });
    go.store(true);
    for (auto& t : ts) t.join();
    return granted.load();
}

int main() {
    const std::uint64_t t0 = 5'000'000'000ull;       // arbitrary start: 5 s on the injected clock
    RateLimiter rl(10, 5);                            // 10 per second, burst of 5
    // Contention check: 2000 rounds, each a fresh limiter and 8 gated threads at one frozen instant.
    // Only the first 5 admissions write, so a single round gives the race a tiny window; many rounds do not.
    int wrong_rounds = 0;
    for (int r = 0; r < 2000; ++r) {
        RateLimiter fresh(10, 5);
        if (hammer(fresh, t0, 8, 50) != 5) ++wrong_rounds;
    }
    std::printf("2000 gated rounds: %d granted something other than 5 (expect 0)\n", wrong_rounds);
    std::printf("burst at t=0:      granted %ld (expect 5)\n", hammer(rl, t0, 8, 1000));
    std::printf("after +300 ms:     granted %ld (expect 3)\n", hammer(rl, t0 + 300'000'000ull, 8, 1000));
    std::printf("after +10 s idle:  granted %ld (expect 5, bucket does not bank more than burst)\n",
                hammer(rl, t0 + 10'300'000'000ull, 8, 1000));
    // Long-run rate: one request every 10 ms for 20 s of injected time (2000 attempts).
    RateLimiter rl2(10, 5);
    long ok = 0;
    for (std::uint64_t i = 0; i < 2000; ++i) ok += rl2.try_acquire(t0 + i * 10'000'000ull);
    std::printf("20 s at 100 req/s offered: granted %ld (5 + floor(10 * 19.99) = 204)\n", ok);
}

g++ -std=c++17 -O2 -Wall -Wextra -fsanitize=thread rate_limiter.cpp -o rate_limiter -pthread && ./rate_limiter

Output (GCC 14, Linux container, TSan reported nothing; the run takes on the order of half a minute under TSan and about a second without it, depending on the machine):

2000 gated rounds: 0 granted something other than 5 (expect 0)
burst at t=0:      granted 5 (expect 5)
after +300 ms:     granted 3 (expect 3)
after +10 s idle:  granted 5 (expect 5, bucket does not bank more than burst)
20 s at 100 req/s offered: granted 204 (5 + floor(10 * 19.99) = 204)

The clock is passed in so the decisions are deterministic for a given instant. In each of the 2,000 gated rounds a fresh limiter faces eight threads released together by a spin gate at one frozen instant, and exactly the burst (5) gets through every time. The gate and the repetition matter: only the first five admissions write, so a single ungated run gives the race a tiny window (threads started one after another can finish their calls before the next one exists). To confirm the check can fail, replace the compare-and-swap with a plain store, a lost-update bug: the 2,000 gated rounds then report many rounds wrong and the burst line often grants more than 5 (some runs still print 5 on that line). The exact numbers differ from run to run and machine to machine, so only the direction of the rounds line is stable. The remaining lines are single frozen-instant checks: after 300 ms at 10 per second exactly 3 more pass (T = 100 ms), and an idle period never banks more than the burst. The last line checks the long-run cap: 2,000 attempts spread over 19.99 s admit 5 + 199 = 204 requests.

Synchronization choices

• Memory order is relaxed. memory_order_relaxed asks only for atomicity of the operation, with no ordering guarantees about other memory. The limiter publishes no other data: the decision is the value itself. Acquire/release would add cost for nothing. (If an allowed request also hands over data through the limiter, that changes.)
• No write on rejection. Under an abusive flood most calls hit the early return false, which is a read of a cache line that stays shared. Only admitted requests write.
• A failed compare-exchange is cheap, and the system still makes progress. A failed CAS normally means another caller changed the word (hardware that implements CAS with load-linked/store-conditional can also fail spuriously, which the loop absorbs), so the system as a whole keeps progressing: lock-free (some caller always finishes), not wait-free (every caller finishing in a bounded number of steps), because one unlucky caller can retry repeatedly. Load-linked/store-conditional is a pair of instructions where the store succeeds only if nothing disturbed the location since the load.
• Clock source. Use a monotonic clock (steady_clock), never wall time that can jump. Threads read the clock slightly out of order; max(TAT, now) tolerates a stale now because TAT never moves backwards.
• Cache line. A cache line is the fixed-size block in which cores exchange memory (64 bytes on x86-64 and most Arm cores; some chips, such as Apple's M-series, use 128); alignas(64) places the word at a 64-byte boundary (use 128 where the line is 128 bytes) so it keeps the hot word off lines holding other data, avoiding false sharing (unrelated variables on one cache line forcing the cores to trade ownership).

Keeping the hot path fast with many callers

Per-key limiters live in a map. Look the key up with a read-mostly structure (a hash map split into shards, each with a reader-writer lock that lets many readers in at once and one writer alone, or an immutable snapshot: a read-only copy of the map that is replaced wholesale on update) and create the limiter object once. Then the hot path is one atomic load, arithmetic, and at most one CAS.

When one key is so hot that its single CAS word becomes the bottleneck (every core hammering one cache line), the options and their costs are:

I would ship the single-word CAS version and only move to batching when profiling shows that line contended.

Sliding window state under concurrency

A sliding-window log (for example login attempts) stores one timestamp per recent attempt: memory is O(limit) per key and appending and pruning the deque needs a lock or a more complex structure. A sliding-window counter keeps two fixed-window counts and weights them, which is O(1) and atomic-friendly but approximate. A plain fixed window is cheapest but can admit about twice the limit across a window boundary. The token bucket keeps O(1) state, allows the burst the question asks for, and has no boundary effect; its cost is that it cannot express "exactly N in any rolling minute".

Pitfalls

• Using wall-clock time (jumps break the cap).
• Charging cost c per request: use new_TAT = start + c*T; a request costing more than burst can never pass, so reject it up front.
• Integer overflow in the time arithmetic: 64-bit nanoseconds last for centuries; 32-bit milliseconds do not.
• A limiter per key that is never evicted leaks memory under key-spraying attacks.

Direct answer

Take thread dumps first (three, about ten seconds apart, before restarting anything) and read the state and the CPU of each blocked thread. A deadlock is a cycle: every thread in it waits for a lock another thread in it holds, the threads use almost no CPU and the stacks are identical in every dump. A livelock is threads that keep running (high CPU) and keep changing state, each retrying or backing off in response to the others, so the stacks differ between dumps and no work completes. Priority inversion is a high-priority thread blocked on a lock held by a low-priority thread that cannot run because medium-priority threads are using the CPU; it exists only under strict-priority scheduling (the scheduler always runs the highest-priority runnable thread) and ends when the medium work finishes. Collect dumps, per-thread CPU and a core file; recover by draining (taking the instance out of load-balancer rotation so no new requests arrive) and restarting the instance (a lock cycle among monitors, the per-object locks the Java virtual machine uses for synchronized, cannot be broken from outside); prevent a repeat with a global lock order, timeouts, and a lock-order check in CI.

Ordered checks

1. Confirm the hang is real and scope it. Is any request counter still moving? Does only one instance hang? Take the instance out of the load balancer rotation (drain) before touching it, so users stop hitting it.
2. Dump three times. For a Java virtual machine (JVM): jstack PID > dump1.txt (and again after 10 s and 20 s). For native code: gdb -p PID -batch -ex "thread apply all bt" (not run in the demos here: gdb was not available in the container image used) or gcore PID to keep a core file (a snapshot of the process's memory and thread state written to disk, which you can inspect after the process is gone) for offline analysis. Capture per-thread CPU: top -H -p PID or ps -L -o tid,pcpu,stat,wchan -p PID (one line per thread: pcpu is its CPU use, stat its state, and wchan the kernel function it is sleeping in, which shows a futex wait, the kernel-assisted sleep on a lock, when it is blocked on a lock).
3. Classify with the table. A wait-for graph has one node per thread and an arrow from each thread to the thread whose lock it is waiting for; a cycle in that graph is a deadlock.

4. Find the cycle. The JDK prints it for you. Here is a program with the classic opposite-order locks:

public class Transfer {
    static final Object ACCOUNT_A = new Object(), ACCOUNT_B = new Object();

    static void move(String name, Object first, Object second) {
        synchronized (first) {
            pause(200);                       // widen the window so the demo is deterministic
            synchronized (second) { System.out.println(name + " done"); }
        }
    }
    static void pause(long ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { } }

    public static void main(String[] args) {
        new Thread(() -> move("a-to-b", ACCOUNT_A, ACCOUNT_B), "worker-1").start();
        new Thread(() -> move("b-to-a", ACCOUNT_B, ACCOUNT_A), "worker-2").start();
    }
}

Built with javac Transfer.java and run with java Transfer in a Linux container (JDK 21), then checked after 5 seconds with ps -o pid,pcpu,stat,comm, the process showed well under 1 percent CPU and state Sl (sleeping, multithreaded). jstack PID ended with:

Found one Java-level deadlock:
=============================
"worker-1":
  waiting to lock monitor 0x0000ffff40001d30 (object 0x00000007152139d0, a java.lang.Object),
  which is held by "worker-2"

"worker-2":
  waiting to lock monitor 0x0000ffff44000f00 (object 0x00000007152139c0, a java.lang.Object),
  which is held by "worker-1"
...
Found 1 deadlock.

(addresses differ per run; the per-thread stack sections below the cycle list the lines waiting to lock and locked for each thread.) Read each block as an arrow: worker-1 waits for a lock held by worker-2, and worker-2 waits for one held by worker-1. That is the cycle. In the ps check, near-zero CPU says nothing is running, and Sl says the process is sleeping (S) and multithreaded (l), the signature of threads that are all blocked. For native code the same information comes from the backtraces: threads parked in pthread_mutex_lock or a futex wait, and the owning thread of each mutex (not run here).

5. Priority inversion check. Is a high-priority thread blocked while a lower-priority thread holds the lock and is runnable but not running? Under real-time priorities that is the signature. The fix is a mutex with a priority-inheritance protocol: POSIX PTHREAD_PRIO_INHERIT means "when the calling thread is blocked because the mutex is owned by another thread, that owner thread shall inherit the priority level of the calling thread as long as it continues to own the mutex".
6. Livelock check. Compare two dumps: identical retry loops, rising CPU and flat progress counters. The usual cause is symmetric retry with no randomness (both back off by the same amount).
7. A long-running holder. If one thread holds the lock and is calling a remote service or waiting on a disk, it is not a deadlock: look at that holder's stack, not at the waiters.

Recover

A deadlock among JVM monitors cannot be broken without a restart: you cannot safely kill one thread. Order of actions: drain the instance, save the dumps and (for native code) a core file, restart, and shift traffic back. Two mitigations that need no restart for a service that cannot be stopped: drain traffic away from the stuck instance so the fleet keeps serving, and switch off with a feature flag (or route around) the single code path that takes both locks until the fix is deployed. Lock timeouts help only if they already exist in the code: ReentrantLock.tryLock(timeout) in Java, pthread_mutex_timedlock in POSIX.

For processes that deadlock across file locks (a second tool for a different failure; the thread dump and lock order above are the main path): POSIX fcntl locks taken with F_SETLKW are checked by the kernel and one process gets EDEADLK. In this program two processes lock two files in opposite order (compiled with gcc 14.4.0 and run in a Linux container):

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

static int lock_wait(int fd) {
    struct flock fl = { .l_type = F_WRLCK, .l_whence = SEEK_SET, .l_start = 0, .l_len = 1 };
    return fcntl(fd, F_SETLKW, &fl);                 // blocks until granted, or fails with EDEADLK
}
static void worker(const char* name, const char* first, const char* second) {
    int f1 = open(first, O_RDWR | O_CREAT, 0600), f2 = open(second, O_RDWR | O_CREAT, 0600);
    lock_wait(f1);
    usleep(300000);
    if (lock_wait(f2) == -1) printf("%s: second lock failed: %s\n", name, strerror(errno));
    else printf("%s: got both locks\n", name);
    fflush(stdout);
}
int main(void) {
    pid_t p1 = fork();
    if (p1 == 0) { worker("proc-1", "lockA", "lockB"); return 0; }
    pid_t p2 = fork();
    if (p2 == 0) { worker("proc-2", "lockB", "lockA"); return 0; }
    waitpid(p1, 0, 0); waitpid(p2, 0, 0);
    return 0;
}

In the program, F_WRLCK asks for an exclusive write lock, l_whence, l_start and l_len say "one byte at the start of the file", and F_SETLKW means set the lock and Wait if it is held. It printed:

proc-2: second lock failed: Resource deadlock avoided
proc-1: got both locks

Which process loses varies from run to run (either proc-1 or proc-2 can be the one refused, so the two lines above can appear with the names swapped): the one whose second request would close the wait cycle is refused, and the other then gets both locks. EDEADLK is the error number the kernel returns when granting the lock would complete a wait cycle. The man page for F_SETLKW says the error means "It was detected that the specified F_SETLKW operation would cause a deadlock" and that the kernel limits its dependency search to 10 steps, so longer cycles are not detected. To inspect held locks on a live system, /proc/locks and lslocks list them (not run here).

Prevent a repeat

1. One global lock order. Always lock the lower account id first. The fixed program ran two threads doing 1,000,000 opposite-direction transfers each, with a 30-second timeout on each result, so a deadlock would have shown as a failure:

import java.util.concurrent.*;

public class Ordered {
    record Account(int id, Object lock) { Account(int id) { this(id, new Object()); } }

    static void move(Account from, Account to) {
        Account first = from.id() < to.id() ? from : to;     // one global order: lowest account id first
        Account second = first == from ? to : from;
        synchronized (first.lock()) {
            synchronized (second.lock()) { /* debit from, credit to */ }
        }
    }

    public static void main(String[] args) throws Exception {
        Account a = new Account(1), b = new Account(2);
        ExecutorService pool = Executors.newFixedThreadPool(2);
        Future<?> f1 = pool.submit(() -> { for (int i = 0; i < 1_000_000; i++) move(a, b); });
        Future<?> f2 = pool.submit(() -> { for (int i = 0; i < 1_000_000; i++) move(b, a); });
        f1.get(30, TimeUnit.SECONDS);                         // a deadlock would surface as a TimeoutException
        f2.get(30, TimeUnit.SECONDS);
        pool.shutdown();
        System.out.println("2 x 1,000,000 opposite-direction transfers finished, no deadlock");
    }
}

javac Ordered.java && java Ordered printed: 2 x 1,000,000 opposite-direction transfers finished, no deadlock.

2. Detect order violations without waiting for a hang. ThreadSanitizer (a tool that reports data races and lock misuse at run time) finds lock-order inversions even in a run that did not deadlock. This program takes the two locks in opposite orders one after the other, so nothing can hang:

#include <mutex>
#include <thread>
std::mutex account_a, account_b;
void a_then_b() { std::lock_guard<std::mutex> x(account_a); std::lock_guard<std::mutex> y(account_b); }
void b_then_a() { std::lock_guard<std::mutex> x(account_b); std::lock_guard<std::mutex> y(account_a); }
int main() {
    a_then_b();                       // run the two paths one after the other: no deadlock can happen in this run
    std::thread t(b_then_a);
    t.join();
}

g++ -std=c++20 -O1 -g -fsanitize=thread lockorder.cpp -o lo && ./lo printed WARNING: ThreadSanitizer: lock-order-inversion (potential deadlock) with Cycle in lock order graph: M0 => M1 => M0 and the two stacks that took the locks in opposite order. Run the test suite under TSan in continuous integration (CI). Where TSan is not available, record the order locks are acquired in a debug build and fail on a violation.
3. Never hold a lock across a call to unknown code (callbacks, remote calls); that is how long, unexplained cycles appear.
4. Timeouts with backoff on try-lock where a lock order cannot be imposed; add randomness so symmetric retries do not livelock.
5. Alert on a stuck-thread watchdog (no progress counter movement for N seconds) so the next hang is a page with dumps attached, not a customer report.

Verify the fix

Reproduce the original hang with the old code in a test (as in the first program), confirm the new code survives the same harness with a timeout, and keep the TSan job in CI.

Direct answer

The problem is called a cache stampede or thundering herd: when a popular entry is missing, a crowd of threads all miss together and all call the backing store at once. Use a single-flight table: a concurrent map from key to a future (a placeholder for a result that will arrive) holding the fetch that is currently running. The first thread to miss a key inserts its own future and becomes the leader and fetches. Every other thread that misses the same key finds that future and waits on it. The leader writes the value to the cache, completes the future, and removes the entry from the table in a finally block, so the table only ever contains keys with a fetch in progress. That is the leak-prevention rule: bookkeeping lives exactly as long as the work.

Why not the obvious designs

The Go ecosystem has this exact tool: golang.org/x/sync/singleflight ensures only one execution is in flight for a key, and duplicate callers wait and receive the same result.

The algorithm

1. Look in the cache. A hit returns immediately.
2. On a miss, make a new future mine and call inflight.putIfAbsent(key, mine), an atomic operation that either inserts mine (and returns null) or leaves the table alone and returns the entry already there.
3. If an entry already existed, you are a follower: wait on it and return its result. If waiting can be long, wait with a timeout.
4. If you inserted, you are the leader. Check the cache again: a previous leader may have finished and removed its entry between your first miss and your insert, and without this re-check you would fetch a second time. Timeline with two threads (illustrative clock times): at 0 ms thread T1 checks the cache for key k and misses; at 1 ms thread T2, the leader, finishes its fetch, writes the value to the cache and removes its entry; at 2 ms T1 runs putIfAbsent, finds no entry, so it becomes a leader for a value that is already cached. Without the re-check, T1 fetches again at 2 ms; with it, T1 finds the value and returns.
5. Fetch, put the value in the cache first, then complete the future. If you removed the entry before the cache write, a new arrival would miss the cache, find no entry and fetch again.
6. On failure, complete the future exceptionally (completeExceptionally puts the future into a failed state, so every follower waiting on it fails too: join() throws a CompletionException whose cause is the leader's original exception, so followers must unwrap it, and the demo below exercises only the leader's failure) and cache nothing.
7. In finally (the block that runs whether the fetch succeeded or threw), call inflight.remove(key, mine). The two-argument form removes the entry only if it is still the one you inserted.

Worked example, run in a Linux container

300 threads release at once, 100 per key across three keys, and the simulated fetch takes 50 ms. The second part makes the first fetch for a fourth key fail.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.function.*;

public class SingleFlight {
    static final ConcurrentHashMap<String, String> cache = new ConcurrentHashMap<>();
    static final ConcurrentHashMap<String, CompletableFuture<String>> inflight = new ConcurrentHashMap<>();

    static String get(String key, Function<String, String> loader) {
        String hit = cache.get(key);
        if (hit != null) return hit;
        CompletableFuture<String> mine = new CompletableFuture<>();
        CompletableFuture<String> theirs = inflight.putIfAbsent(key, mine);
        if (theirs != null) return theirs.join();            // follower: wait for the leader
        try {
            String again = cache.get(key);                   // re-check: a leader may have just finished
            String v = again != null ? again : loader.apply(key);
            if (again == null) cache.put(key, v);            // publish to the cache BEFORE leaving inflight
            mine.complete(v);
            return v;
        } catch (Throwable t) {
            mine.completeExceptionally(t);                   // followers' join() throws a CompletionException wrapping this failure, nothing cached
            throw t;
        } finally {
            inflight.remove(key, mine);                      // bookkeeping removed on every path
        }
    }

    public static void main(String[] args) throws Exception {
        AtomicInteger fetches = new AtomicInteger();
        String[] keys = {"a", "b", "c"};
        int N = 300;
        ExecutorService pool = Executors.newFixedThreadPool(N);
        CountDownLatch go = new CountDownLatch(1);
        List<Future<String>> fs = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            final String k = keys[i % 3];
            fs.add(pool.submit(() -> {
                go.await();
                return get(k, kk -> { fetches.incrementAndGet(); sleep(50); return "value-of-" + kk; });
            }));
        }
        go.countDown();
        for (Future<String> f : fs) f.get();
        System.out.println("requests=" + N + " distinct keys=3 backing-store fetches=" + fetches.get());
        System.out.println("inflight entries left=" + inflight.size());

        // failure path: leader fails, followers see the failure, entry is gone, next call retries
        AtomicInteger tries = new AtomicInteger();
        Function<String, String> flaky = k -> { if (tries.incrementAndGet() == 1) throw new IllegalStateException("backend down"); return "ok"; };
        try { get("z", flaky); } catch (IllegalStateException e) { System.out.println("first call failed: " + e.getMessage()); }
        System.out.println("inflight after failure=" + inflight.size() + ", cached=" + cache.containsKey("z"));
        System.out.println("retry returns " + get("z", flaky) + " after " + tries.get() + " loader calls");
        pool.shutdown();
    }
    static void sleep(long ms) { try { Thread.sleep(ms); } catch (InterruptedException e) { throw new RuntimeException(e); } }
}

Run with docker run --rm -v "$PWD":/w -w /w eclipse-temurin:21-jdk java SingleFlight.java:

requests=300 distinct keys=3 backing-store fetches=3
inflight entries left=0
first call failed: backend down
inflight after failure=0, cached=false
retry returns ok after 2 loader calls

Three fetches for 300 requests, one per key. The table is empty afterwards, including after the failed call, and the failure was not cached: the next call retried and succeeded.

Trade-offs and pitfalls

• A hung leader hangs every follower. Put a timeout on the fetch itself and a timeout on the wait. Decide whether a follower that times out falls back to its own fetch (risking the stampede returning) or returns an error (shedding load); for a protected backing store, prefer the error.
• Cancellation. If the leader's own request is cancelled, do not cancel the shared fetch the followers need. Run the fetch on the leader's thread but treat the leader's cancellation as "stop waiting", or hand the fetch to a separate executor.
• Expiry stampedes. Entries that expire at the same moment bring the stampede back, because all of them miss together. Add random jitter (a small random amount added to each time-to-live, so entries expire at scattered moments), or serve a stale value while one thread refreshes.
• Negative results. (A negative result is an answer of "this key does not exist".) Decide on purpose whether to cache "not found" (usually yes, briefly) and whether to cache errors (usually no, or for a very short time).
• Scope. This protects one process. With many instances each does one fetch, so the store sees one per instance. Coordinating across instances is a different, distributed-locking problem.

Design in one paragraph

Many producer threads append records to a shared log; one consumer thread reads them in the exact order they were appended. The approach is a fixed-size ring buffer (an array of N slots that is reused in a circle: position 4 in a 4-slot ring lands in slot 0 again, and each pass around the circle is a lap) whose slots are numbered by a global position. A producer claims a position by moving a shared tail counter forward with an atomic operation, writes its record into the slot for that position, and then publishes the slot. The single consumer reads positions in order, head, head+1, ... and stops at the first slot that is not yet published. The log's order is the order of positions, so the global order is whatever order the claims happened in.

How producers claim positions

• Unconditional claim: pos = tail.fetch_add(1, std::memory_order_relaxed). Every producer gets a unique position with one read-modify-write (an atomic operation that reads and updates a variable as one indivisible step). Compiled with GCC 14 at -O2, the relaxed fetch_add becomes a single lock xaddq instruction on x86-64 (xadd, the exchange-and-add form, because the old value is the claimed position and is used; the default sequentially consistent form compiles to the same instruction there). On AArch64 (64-bit Arm) with default flags it becomes a call to a helper, __aarch64_ldadd8_relax, which uses a single atomic-add instruction when the CPU has one; with -march=armv8.1-a it emits one ldadd, and with -march=armv8-a+nolse -mno-outline-atomics it emits a load-exclusive/store-exclusive loop (ldxr/stxr/cbnz). The default sequentially consistent form on AArch64 uses the acquire-release variants instead (__aarch64_ldadd8_acq_rel, ldaddal, ldaxr/stlxr). In the loop case, that loop is lock-free (some thread always finishes) but not wait-free (a given thread may retry an unbounded number of times). With a fixed-size ring, a producer that gets a position more than N ahead of the consumer must wait for the slot to be freed, so this variant can block. A thread that is descheduled (paused by the operating system in the middle of its work) while holding a claimed position has the same effect on everyone behind it.
• Conditional claim (shipped below): a producer only claims position pos if the slot for pos is free (its sequence number equals pos), using a compare-and-swap loop on tail. If the slot is not free the ring is full and the producer returns false instead of waiting, which keeps the hot path non-blocking. The cost is that a record can be dropped, so the caller counts drops.

Each slot has an atomic sequence number. It starts as the slot index i. A slot is free for position pos when seq == pos; the producer publishes by storing pos + 1; the consumer frees it for the next lap by storing pos + N.

A trace on a ring with N = 4 (cells 0 to 3, seq starts as [0, 1, 2, 3], tail = 0, head = 0):

1. Producer P1 appends: it reads pos = 0, cell 0 has seq = 0 == pos, so it is free. The CAS moves tail to 1, P1 writes the record, and stores seq[0] = 1 (published).
2. Producer P2 appends: pos = 1, seq[1] = 1 matches, tail becomes 2, the record is written, seq[1] = 2.
3. The consumer, with head = 0, sees seq[0] == head + 1 == 1, reads the record, and stores seq[0] = 0 + 4 = 4; head becomes 1. It does the same for position 1 and stores seq[1] = 5.
4. Later, when tail reaches 4, a producer with pos = 4 looks at cell 4 & 3 = 0. seq[0] = 4 == pos, so the cell is free for lap two.
5. Full ring: with all four cells published and nothing consumed, seq = [1, 2, 3, 4] and tail = 4. A producer with pos = 4 sees seq[0] = 1 < 4: the consumer has not freed the cell, so the ring is full and append returns false.
6. Head-of-line blocking: suppose P1 claims position 2 and is descheduled before storing seq[2] = 3, and P2 claims position 3 and publishes seq[3] = 4. The consumer reads positions 0 and 1, then at head = 2 finds seq[2] = 2, not 3, and stops even though position 3 is ready.

How append reads: it loads the cell for pos and its seq. If seq == pos the cell is free for this lap, so it tries the CAS on tail. If seq < pos the cell still holds last lap's record, so the ring is full. If seq > pos another producer already took this position and tail has moved on, so it reloads tail and tries again.

#include <atomic>
#include <cstdint>
#include <iostream>
#include <thread>
#include <vector>

struct Record { uint32_t writer; uint32_t writer_seq; };   // plain data, not atomic

template <size_t N>   // N must be a power of two
class AppendLog {
    struct Cell { std::atomic<uint64_t> seq; Record rec; };
    Cell cells[N];
    alignas(64) std::atomic<uint64_t> tail{0};   // next position to claim (producers); alignas(64) puts each counter on its own 64-byte cache line
    alignas(64) uint64_t head = 0;               // next position to read (consumer only)
    alignas(64) std::atomic<uint64_t> dropped{0};
public:
    AppendLog() { for (uint64_t i = 0; i < N; ++i) cells[i].seq.store(i, std::memory_order_relaxed); }

    // Producer: never blocks. Returns false (and counts a drop) if the log is full.
    bool append(const Record& r) {
        uint64_t pos = tail.load(std::memory_order_relaxed);
        for (;;) {
            Cell& c = cells[pos & (N - 1)];
            uint64_t s = c.seq.load(std::memory_order_acquire);
            if (s == pos) {                                    // cell free for this lap
                if (tail.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed)) {
                    c.rec = r;                                 // we own position pos
                    c.seq.store(pos + 1, std::memory_order_release);   // publish
                    return true;
                }                                              // CAS failed: pos reloaded, retry
            } else if (s < pos) {                              // consumer has not freed it: full
                dropped.fetch_add(1, std::memory_order_relaxed);
                return false;
            } else {
                pos = tail.load(std::memory_order_relaxed);    // another producer got ahead
            }
        }
    }
    // Single consumer: returns false if the next position is not published yet.
    bool take(Record& out, uint64_t& pos_out) {
        Cell& c = cells[head & (N - 1)];
        if (c.seq.load(std::memory_order_acquire) != head + 1) return false;
        out = c.rec;
        pos_out = head;
        c.seq.store(head + N, std::memory_order_release);      // hand the cell back for the next lap
        ++head;
        return true;
    }
    uint64_t drops() const { return dropped.load(); }
};

int main() {
    constexpr int P = 4, PER = 20000;
    static AppendLog<1024> log;
    std::atomic<int> producers_done{0};
    std::vector<std::thread> ps;
    std::vector<uint64_t> accepted(P, 0);
    for (int w = 0; w < P; ++w)
        ps.emplace_back([&, w] {
            for (uint32_t s = 0; s < PER; ++s)
                if (log.append({(uint32_t)w, s})) ++accepted[w];
            ++producers_done;
        });
    std::vector<int64_t> last(P, -1);
    uint64_t got = 0, expect_pos = 0; bool order_ok = true, pos_ok = true;
    Record r; uint64_t pos;
    auto consume = [&] {
        while (log.take(r, pos)) {
            ++got;
            if (pos != expect_pos++) pos_ok = false;
            if ((int64_t)r.writer_seq <= last[r.writer]) order_ok = false;   // per-writer order
            last[r.writer] = r.writer_seq;
        }
    };
    while (producers_done.load() < P) consume();   // run while producers are active
    consume();                                     // final drain after all producers finished
    for (auto& t : ps) t.join();
    uint64_t acc = 0; for (auto a : accepted) acc += a;
    std::cout << "produced=" << P * PER << " accepted=" << acc << " dropped=" << log.drops()
              << " consumed=" << got << "\n"
              << "accepted+dropped==produced: " << (acc + log.drops() == (uint64_t)P * PER) << "\n"
              << "consumed==accepted: " << (got == acc) << "\n"
              << "positions contiguous: " << pos_ok << "  per-writer order kept: " << order_ok << "\n";
}

Compiled with g++ -std=c++20 -O1 -g once with -fsanitize=thread and once with -fsanitize=address,undefined in a gcc:14 container, neither build reported anything. The dropped count varies from run to run because producers race the consumer. A TSan run printed:

produced=80000 accepted=77277 dropped=2723 consumed=77277
accepted+dropped==produced: 1
consumed==accepted: 1
positions contiguous: 1  per-writer order kept: 1

The program checks three things on every run (the dropped count changes between runs, the three checks print 1 every time): nothing is lost or invented, the consumer sees positions 0, 1, 2, ... with no gaps, and each producer's own records come out in the order it wrote them.

The minimum synchronization for correct visibility

Visibility means the consumer sees the fully written record, not a half-written one. The record itself is plain, non-atomic data (Record), so it is the atomics around it that must create a happens-before relationship (a guarantee that everything before one event is visible after the other):

• The producer writes c.rec, then does a release store of seq = pos + 1. A release store means writes before it cannot be seen out of order after it.
• The consumer does an acquire load of seq and only reads c.rec if it saw head + 1. An acquire load pairs with that release: if the load sees the stored value, it also sees everything written before the store.
• The consumer frees the slot with a release store of seq = head + N, and a producer's acquire load of seq == pos pairs with it, so the producer's overwrite of the old record cannot be seen before the consumer finished reading it.
• The tail claim itself needs only atomicity (relaxed): uniqueness of positions comes from the atomic read-modify-write, and the record's visibility comes from the slot's sequence number, not from tail.

No sequentially consistent (seq_cst) operation and no separate fence is needed. The consumer must test the specific slot's sequence number, not tail, because tail moves when a position is claimed, before the data is written.

Per-writer ordering and the cost of a global order

A single thread's second append starts after its first returned, so it reads a larger tail and gets a larger position: per-writer order follows from global order. Each record carries a per-writer sequence number (writer_seq) so the consumer can verify it and see gaps if the log drops records. For a security audit log, dropping a record may be unacceptable. The alternatives are to let the producer wait (the unconditional claim) and accept that it can block, or to treat a full log as a fault.

The price of a global order is head-of-line blocking (everything behind one stalled item waits for it, as in step 6 of the trace): if the producer holding position k is descheduled before publishing, the consumer cannot read k+1, k+2, ... even though those slots are published. The log is as fast as its slowest claimer.

An alternative that keeps each producer wait-free is one single-producer single-consumer queue per producer, with each record tagged by a ticket from a shared fetch_add; the consumer merges by ticket. That gives per-producer order for free but the merge must wait for any missing ticket, so it reintroduces the same stall, and it needs a space-overflow policy per queue.