LLD Series: Java Concurrency Essentials for LLD Rounds

Overview

Decision table
1. synchronized vs ReentrantLock
2. ReadWriteLock and StampedLock
3. Atomics (CAS)
4. ConcurrentHashMap
5. Deadlock and lock ordering (thread-safe bank transfer)
6. Thread pools, ExecutorService, CompletableFuture
7. Producer-consumer with BlockingQueue
8. Optimistic vs pessimistic locking
9. Idempotency in code
10. Other must-knows (rapid fire)

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

In fintech LLD rounds the follow-up is almost always: "now make it thread-safe" (two threads debit the same wallet, two users book the same seat, two requests carry the same idempotency key). Know the toolbox and when each tool fits. All snippets are Java 11, compiled and run.

Decision table

Need	Use
Simple mutual exclusion, short critical section	`synchronized`
tryLock/timeout, interruptible, fairness, multiple Conditions	`ReentrantLock`
Read-heavy shared state	`ReentrantReadWriteLock` / `StampedLock`
Single counter / flag / reference	`AtomicLong`, `AtomicReference` (CAS)
High-contention counter (metrics)	`LongAdder`
Shared map	`ConcurrentHashMap` + atomic methods (`merge`, `compute`)
Multi-object invariant (transfer A->B)	Lock both in a global order
Hand work between threads	`BlockingQueue`
Async pipelines	`ExecutorService`, `CompletableFuture`
Low conflict, rare retries OK	Optimistic (version/CAS)
High conflict, must not fail	Pessimistic (locks / `SELECT ... FOR UPDATE`)
Duplicate requests	Idempotency key

Golden rules: (1) protect invariants, not just variables; (2) keep critical sections small and never call unknown/external code while holding a lock; (3) unlock() in finally; (4) prefer immutability; (5) check-then-act is a bug unless atomic.

1. synchronized vs ReentrantLock

synchronized: intrinsic monitor, auto-release, reentrant, no timeout, not interruptible while blocked, one wait-set per object. Guarantees mutual exclusion + visibility (happens-before on unlock->lock).
ReentrantLock: explicit; tryLock(), tryLock(timeout), lockInterruptibly(), fair mode, multiple Conditions. Must unlock() in finally.
volatile: visibility + ordering only, no atomicity (count++ on volatile is still a race).

// File: LockBasics.java
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class LockBasics {
    static class SyncCounter {
        private int c;
        synchronized void inc() { c++; }
        synchronized int get() { return c; }
    }

    static class LockCounter {
        private int c;
        private final ReentrantLock lock = new ReentrantLock();
        void inc() { lock.lock(); try { c++; } finally { lock.unlock(); } }
        boolean tryInc(long ms) throws InterruptedException {
            if (lock.tryLock(ms, TimeUnit.MILLISECONDS)) {       // give up instead of blocking forever
                try { c++; return true; } finally { lock.unlock(); }
            }
            return false;
        }
        int get() { lock.lock(); try { return c; } finally { lock.unlock(); } }
    }

    // Bounded buffer with two Conditions (what synchronized+wait/notifyAll can't do cleanly)
    static class BoundedBuffer<T> {
        private final Object[] items; private int head, tail, count;
        private final ReentrantLock lock = new ReentrantLock();
        private final Condition notFull = lock.newCondition(), notEmpty = lock.newCondition();
        BoundedBuffer(int cap) { items = new Object[cap]; }
        void put(T t) throws InterruptedException {
            lock.lock();
            try {
                while (count == items.length) notFull.await();     // loop: guard against spurious wakeups
                items[tail] = t; tail = (tail + 1) % items.length; count++;
                notEmpty.signal();
            } finally { lock.unlock(); }
        }
        @SuppressWarnings("unchecked")
        T take() throws InterruptedException {
            lock.lock();
            try {
                while (count == 0) notEmpty.await();
                T t = (T) items[head]; head = (head + 1) % items.length; count--;
                notFull.signal();
                return t;
            } finally { lock.unlock(); }
        }
    }

    public static void main(String[] args) throws Exception {
        SyncCounter s = new SyncCounter(); LockCounter l = new LockCounter();
        Thread[] ts = new Thread[4];
        for (int i = 0; i < ts.length; i++) {
            ts[i] = new Thread(() -> { for (int j = 0; j < 10_000; j++) { s.inc(); l.inc(); } });
            ts[i].start();
        }
        for (Thread t : ts) t.join();
        System.out.println(s.get() + " " + l.get());                 // 40000 40000

        BoundedBuffer<Integer> buf = new BoundedBuffer<>(2);
        Thread prod = new Thread(() -> { try { for (int i = 1; i <= 5; i++) buf.put(i); } catch (InterruptedException e) { } });
        prod.start();
        int sum = 0; for (int i = 0; i < 5; i++) sum += buf.take();
        System.out.println("sum=" + sum);                            // 15
    }
}

2. ReadWriteLock and StampedLock

ReentrantReadWriteLock: many concurrent readers OR one writer. Good when reads >> writes and the read section is not trivial. Can't upgrade read->write (deadlocks); can downgrade write->read.
StampedLock: adds optimistic read (tryOptimisticRead + validate): no lock taken, retry with a real read lock if a write intervened. Not reentrant, no Conditions.

// File: RwLocks.java
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantReadWriteLock;
import java.util.concurrent.locks.StampedLock;

public class RwLocks {
    static class RateCache {
        private final Map<String, Double> m = new HashMap<>();
        private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();
        Double get(String k) { rw.readLock().lock(); try { return m.get(k); } finally { rw.readLock().unlock(); } }
        void put(String k, double v) { rw.writeLock().lock(); try { m.put(k, v); } finally { rw.writeLock().unlock(); } }
    }

    static class Point {
        private double x, y; private final StampedLock sl = new StampedLock();
        void move(double dx, double dy) {
            long st = sl.writeLock();
            try { x += dx; y += dy; } finally { sl.unlockWrite(st); }
        }
        double dist() {
            long st = sl.tryOptimisticRead();            // no blocking
            double cx = x, cy = y;
            if (!sl.validate(st)) {                      // a writer slipped in -> fall back
                st = sl.readLock();
                try { cx = x; cy = y; } finally { sl.unlockRead(st); }
            }
            return Math.sqrt(cx * cx + cy * cy);
        }
    }

    public static void main(String[] args) {
        RateCache c = new RateCache(); c.put("USD", 83.5);
        System.out.println(c.get("USD"));
        Point p = new Point(); p.move(3, 4);
        System.out.println(p.dist());                    // 5.0
    }
}

3. Atomics (CAS)

AtomicInteger/Long/Boolean/Reference use hardware compare-and-swap: lock-free, no blocking, but retry loops under contention and the ABA problem (use AtomicStampedReference). LongAdder stripes the counter across cells: far faster under heavy write contention, sum() is not an atomic snapshot.

// File: AtomicsDemo.java
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.LongAdder;

public class AtomicsDemo {
    // Lock-free wallet debit via CAS loop: never goes negative
    static class Wallet {
        private final AtomicLong balance;
        Wallet(long b) { balance = new AtomicLong(b); }
        boolean debit(long amt) {
            while (true) {
                long cur = balance.get();
                if (cur < amt) return false;
                if (balance.compareAndSet(cur, cur - amt)) return true;   // retry if someone changed it
            }
        }
        long get() { return balance.get(); }
    }

    public static void main(String[] args) throws Exception {
        Wallet w = new Wallet(1000);
        LongAdder ok = new LongAdder();
        Thread[] ts = new Thread[8];
        for (int i = 0; i < ts.length; i++) {
            ts[i] = new Thread(() -> { for (int j = 0; j < 50; j++) if (w.debit(10)) ok.increment(); });
            ts[i].start();
        }
        for (Thread t : ts) t.join();
        System.out.println("balance=" + w.get() + " successfulDebits=" + ok.sum());  // 0, 100

        AtomicReference<String> ref = new AtomicReference<>("INIT");
        System.out.println(ref.compareAndSet("INIT", "RUNNING") + " " + ref.get());
        System.out.println(ref.updateAndGet(s -> s + "!"));
    }
}

4. ConcurrentHashMap

Thread-safe, no global lock (bin-level CAS/synchronized in Java 8+). No null keys/values.
Individually atomic methods: putIfAbsent, computeIfAbsent, compute, merge. A sequence if (!containsKey) put is not atomic.
computeIfAbsent function must be short, must not modify the map.
Iterators are weakly consistent (no ConcurrentModificationException). size() is an estimate under concurrency.

// File: ChmDemo.java
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.List;

public class ChmDemo {
    public static void main(String[] args) throws Exception {
        Map<String, Long> totals = new ConcurrentHashMap<>();
        Map<String, List<String>> byUser = new ConcurrentHashMap<>();
        Thread[] ts = new Thread[4];
        for (int i = 0; i < ts.length; i++) {
            final int id = i;
            ts[i] = new Thread(() -> {
                for (int j = 0; j < 1000; j++) {
                    totals.merge("alice", 1L, Long::sum);                                   // atomic read-modify-write
                    byUser.computeIfAbsent("alice", k -> new CopyOnWriteArrayList<>());     // atomic create
                }
                byUser.get("alice").add("t" + id);
            });
            ts[i].start();
        }
        for (Thread t : ts) t.join();
        System.out.println(totals.get("alice") + " " + byUser.get("alice").size());          // 4000 4
    }
}

Wrong: Long v = m.get(k); m.put(k, v == null ? 1 : v + 1); loses updates.

5. Deadlock and lock ordering (thread-safe bank transfer)

Deadlock needs four conditions: mutual exclusion, hold-and-wait, no preemption, circular wait. Break one. In LLD, break circular wait by always acquiring locks in a global order (e.g., by account id). Alternatives: tryLock with timeout + back-off, a single coarse lock, or a single-threaded actor/queue per account.

Bad: from.lock(); to.lock(); -> T1 transfers A->B, T2 transfers B->A, each holds one lock, waits for the other.

// File: BankTransfer.java
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;

class InsufficientFundsException extends Exception {
    InsufficientFundsException(String m) { super(m); }
}

class Account {
    final long id;
    private long balance;
    final ReentrantLock lock = new ReentrantLock();
    Account(long id, long balance) { this.id = id; this.balance = balance; }
    long balance() { return balance; }          // callers hold the lock for consistent reads
    void debit(long amt) throws InsufficientFundsException {
        if (balance < amt) throw new InsufficientFundsException("acct " + id + " has " + balance);
        balance -= amt;
    }
    void credit(long amt) { balance += amt; }
}

class TransferService {
    // DEADLOCK-PRONE (for contrast, never called): from.lock then to.lock, inconsistent order
    void badTransfer(Account from, Account to, long amt) throws InsufficientFundsException {
        from.lock.lock();
        try { to.lock.lock(); try { from.debit(amt); to.credit(amt); } finally { to.lock.unlock(); } }
        finally { from.lock.unlock(); }
    }

    // SAFE: global ordering by id
    void transfer(Account from, Account to, long amt) throws InsufficientFundsException {
        if (from == to) throw new IllegalArgumentException("same account");
        Account first = from.id < to.id ? from : to;
        Account second = first == from ? to : from;
        first.lock.lock();
        try {
            second.lock.lock();
            try {
                from.debit(amt);          // throws before any mutation -> atomic failure
                to.credit(amt);
            } finally { second.lock.unlock(); }
        } finally { first.lock.unlock(); }
    }
}

public class BankTransfer {
    public static void main(String[] args) throws Exception {
        Account[] accts = new Account[5];
        for (int i = 0; i < accts.length; i++) accts[i] = new Account(i, 10_000);
        TransferService svc = new TransferService();
        ExecutorService ex = Executors.newFixedThreadPool(8);
        List<Future<?>> fs = new ArrayList<>();
        for (int i = 0; i < 20_000; i++) {
            fs.add(ex.submit(() -> {
                ThreadLocalRandom r = ThreadLocalRandom.current();
                int a = r.nextInt(accts.length), b = r.nextInt(accts.length);
                if (a == b) return;
                try { svc.transfer(accts[a], accts[b], r.nextInt(1, 500)); }
                catch (InsufficientFundsException e) { /* expected sometimes */ }
            }));
        }
        for (Future<?> f : fs) f.get();
        ex.shutdown(); ex.awaitTermination(10, TimeUnit.SECONDS);
        long total = 0; for (Account a : accts) total += a.balance();
        System.out.println("total=" + total + " (expected 50000)");
    }
}

Interview talking points: invariant = sum of balances constant; debit-before-credit and validate-before-mutate; lock ordering by immutable unique id (use System.identityHashCode + tie-breaker lock only if no id exists); in a DB use SELECT ... FOR UPDATE ORDER BY id.

6. Thread pools, ExecutorService, CompletableFuture

Executors.newFixedThreadPool(n): CPU-bound ~ #cores; I/O-bound larger. Unbounded queue can OOM: for production use ThreadPoolExecutor with bounded ArrayBlockingQueue + RejectedExecutionHandler (CallerRunsPolicy gives back-pressure).
submit returns Future (exceptions surface at get()); execute loses the result.
Always shutdown() then awaitTermination.
CompletableFuture: compose async stages (supplyAsync, thenApply, thenCompose flat-map, thenCombine, allOf, exceptionally/handle). Pass your own executor for blocking I/O so you don't starve the common pool.

// File: AsyncDemo.java
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;
import java.util.stream.Collectors;

public class AsyncDemo {
    static long fxRate(String ccy) { return ccy.equals("USD") ? 83 : 90; }             // pretend remote call
    static boolean fraudOk(long paise) { return paise < 1_000_000; }

    public static void main(String[] args) throws Exception {
        ThreadPoolExecutor pool = new ThreadPoolExecutor(
            2, 4, 30, TimeUnit.SECONDS,
            new ArrayBlockingQueue<>(10),                       // bounded
            new ThreadPoolExecutor.CallerRunsPolicy());         // back-pressure

        CompletableFuture<Long> rate = CompletableFuture.supplyAsync(() -> fxRate("USD"), pool);
        CompletableFuture<Boolean> fraud = CompletableFuture.supplyAsync(() -> fraudOk(5_000), pool);

        CompletableFuture<String> result = rate.thenCombine(fraud, (r, ok) -> ok ? "APPROVED inr=" + (r * 100) : "DECLINED")
            .thenApply(s -> "[" + s + "]");
        System.out.println(result.get(2, TimeUnit.SECONDS));

        // Fan-out to gateways, take all results; failure of one handled without failing the rest
        List<String> gateways = Arrays.asList("A", "B", "C");
        List<CompletableFuture<String>> calls = gateways.stream()
            .map(g -> CompletableFuture.supplyAsync(() -> {
                if (g.equals("B")) throw new IllegalStateException("B down");
                return g + ":ok";
            }, pool).exceptionally(t -> g + ":failed"))
            .collect(Collectors.toList());
        CompletableFuture.allOf(calls.toArray(new CompletableFuture[0])).join();
        System.out.println(calls.stream().map(CompletableFuture::join).collect(Collectors.toList()));

        pool.shutdown();
        System.out.println(pool.awaitTermination(5, TimeUnit.SECONDS));
    }
}

7. Producer-consumer with BlockingQueue

BlockingQueue (ArrayBlockingQueue bounded, LinkedBlockingQueue, PriorityBlockingQueue, DelayQueue, SynchronousQueue) does the locking and waiting for you. Bounded = back-pressure. Shut down with a poison pill.

// File: ProducerConsumer.java
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.atomic.AtomicLong;

public class ProducerConsumer {
    static final class Txn {
        final String id; final long paise;
        Txn(String id, long paise) { this.id = id; this.paise = paise; }
    }
    static final Txn POISON = new Txn("POISON", 0);

    public static void main(String[] args) throws Exception {
        BlockingQueue<Txn> q = new ArrayBlockingQueue<>(4);
        AtomicLong processed = new AtomicLong();
        int consumers = 3;

        Thread producer = new Thread(() -> {
            try {
                for (int i = 1; i <= 100; i++) q.put(new Txn("t" + i, i));      // blocks when full
                for (int i = 0; i < consumers; i++) q.put(POISON);            // one pill per consumer
            } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        });

        Thread[] cs = new Thread[consumers];
        for (int i = 0; i < consumers; i++) {
            cs[i] = new Thread(() -> {
                try {
                    while (true) {
                        Txn t = q.take();                                       // blocks when empty
                        if (t == POISON) return;
                        processed.addAndGet(t.paise);
                    }
                } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            cs[i].start();
        }
        producer.start(); producer.join();
        for (Thread c : cs) c.join();
        System.out.println("sum=" + processed.get());                           // 5050
    }
}

8. Optimistic vs pessimistic locking

	Pessimistic	Optimistic
Idea	Lock first, then work	Work, then verify nobody changed it; retry on conflict
Java	`synchronized`, `Lock`, DB `SELECT ... FOR UPDATE`	CAS/`Atomic*`, `StampedLock.tryOptimisticRead`, version column
Good when	High contention, expensive retries (money movement on a hot account)	Low contention, read-heavy (profile edits, seat hold)
Risk	Deadlock, lower throughput	Livelock/retry storms

DB optimistic update (the version column pattern):

UPDATE wallet SET balance = balance - :amt, version = version + 1
WHERE id = :id AND version = :seenVersion AND balance >= :amt;   -- 0 rows => conflict, re-read and retry

In-memory equivalent using an immutable snapshot and CAS:

// File: OptimisticDemo.java
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;

public class OptimisticDemo {
    static final class Snapshot {                       // immutable value
        final long balance; final long version;
        Snapshot(long b, long v) { balance = b; version = v; }
    }

    static class VersionedAccount {
        private final AtomicReference<Snapshot> ref = new AtomicReference<>(new Snapshot(1000, 0));
        final AtomicInteger retries = new AtomicInteger();
        boolean debit(long amt) {
            while (true) {
                Snapshot s = ref.get();
                if (s.balance < amt) return false;
                Snapshot next = new Snapshot(s.balance - amt, s.version + 1);
                if (ref.compareAndSet(s, next)) return true;     // reference compare: succeeds only if unchanged
                retries.incrementAndGet();                       // conflict -> retry
            }
        }
        Snapshot get() { return ref.get(); }
    }

    public static void main(String[] args) throws Exception {
        VersionedAccount a = new VersionedAccount();
        Thread[] ts = new Thread[4];
        for (int i = 0; i < ts.length; i++) {
            ts[i] = new Thread(() -> { for (int j = 0; j < 100; j++) a.debit(2); });
            ts[i].start();
        }
        for (Thread t : ts) t.join();
        System.out.println("balance=" + a.get().balance + " version=" + a.get().version);   // 200, 400
    }
}

9. Idempotency in code

Networks retry. A payment API must produce the same result and same side effects for the same Idempotency-Key. Design:

Client sends key (UUID per logical operation).
Server atomically "claims" the key. First caller executes; concurrent/later callers receive the stored (or in-flight) result.
Persist key + request hash + response (TTL ~24h). Same key with a different payload -> 422/409.
In DB: unique constraint on (merchant_id, idempotency_key); insert-then-process, or INSERT ... ON CONFLICT DO NOTHING.
Consumers of queues are at-least-once, so dedupe by message id.

// File: IdempotencyDemo.java
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

class PaymentService {
    static final class Entry {
        final String requestHash; final CompletableFuture<String> result = new CompletableFuture<>();
        Entry(String h) { requestHash = h; }
    }
    private final ConcurrentMap<String, Entry> store = new ConcurrentHashMap<>();
    final AtomicInteger realCharges = new AtomicInteger();

    String pay(String idemKey, String payload) throws Exception {
        Entry mine = new Entry(payload);
        Entry existing = store.putIfAbsent(idemKey, mine);       // atomic claim
        if (existing != null) {
            if (!existing.requestHash.equals(payload)) throw new IllegalArgumentException("key reused with different payload");
            return existing.result.get();                         // wait for the in-flight/finished result
        }
        try {
            realCharges.incrementAndGet();                        // the side effect happens exactly once
            Thread.sleep(50);                                     // simulate gateway call
            String r = "charged:" + payload;
            mine.result.complete(r);
            return r;
        } catch (Exception e) {
            store.remove(idemKey, mine);                          // allow retry after failure
            mine.result.completeExceptionally(e);
            throw e;
        }
    }
}

public class IdempotencyDemo {
    public static void main(String[] args) throws Exception {
        PaymentService svc = new PaymentService();
        ExecutorService ex = Executors.newFixedThreadPool(8);
        List<Future<String>> fs = new ArrayList<>();
        for (int i = 0; i < 8; i++) fs.add(ex.submit(() -> svc.pay("key-1", "100INR")));   // 8 duplicate requests
        for (Future<String> f : fs) f.get();
        System.out.println("real charges: " + svc.realCharges.get());                       // 1
        try { svc.pay("key-1", "999INR"); } catch (IllegalArgumentException e) { System.out.println(e.getMessage()); }
        ex.shutdown(); ex.awaitTermination(5, TimeUnit.SECONDS);
    }
}

Distributed note: in-memory map only covers one JVM. In real systems use DB unique constraint or Redis SET key NX EX, and handle "claimed but crashed" via a lock TTL / status column (IN_PROGRESS, DONE).

10. Other must-knows (rapid fire)

Visibility vs atomicity: volatile gives visibility/ordering; atomics/locks give atomicity.
Immutability (final fields, defensive copies, Money value class) removes the need for locks.
ThreadLocal: per-thread state (request context, SimpleDateFormat); clear it in thread pools.
Semaphore: limit concurrency (N parallel gateway calls, parking spots). CountDownLatch: wait for N events once. CyclicBarrier: threads wait for each other repeatedly.
ScheduledExecutorService: periodic jobs (token refill, expiring holds, retry).
Fine-grained / striped locking: lock per key (ConcurrentHashMap<Key, Lock>) beats one global lock; per-seat/per-account locking is the usual LLD answer.
Single-writer / actor: route all ops of one entity to one thread (queue per account); no locks, natural ordering.
Livelock (retrying forever, no progress) and starvation (unfair locks): fairness flag or randomized back-off.
Virtual threads (Java 21): cheap blocking-I/O concurrency; do not pool them; avoid synchronized pinning in hot blocking paths (prefer ReentrantLock).
Testing concurrency: hammer with N threads + CountDownLatch start gate, assert invariants (total money conserved, no double booking), repeat many times.

Previous Blog← DSA Series: Dynamic Programming (Blind 75, Java)

Next BlogHow to Add Semantic Search to an Existing Web Application →