Language-Level Concurrency and Multithreading Questions

Control flow

• CounterService has a private int counter initialized to 0.
• increment() reads counter, adds 1, and writes it back.
• getAndReset() reads counter into local, sets counter = 0, returns the saved value.

Thread-safety issue / race conditions

• counter is a plain int; increment() and getAndReset() are non-atomic composite operations. Concurrent threads can interleave:
  • Lost increments: two threads executing counter += 1 can read same value and write same result.
  • Race on reset: getAndReset() may read a stale or partial value while increments are happening; increments can be lost if they occur concurrently with the reset.
• No visibility guarantees: without synchronization or volatility, one thread’s write may not be visible to another.

Two possible fixes

1. Use synchronization (simple, correct)

public class CounterService {
    private int counter = 0;

    public synchronized void increment() {
        counter += 1;
    }

    public synchronized int getAndReset() {
        int current = counter;
        counter = 0;
        return current;
    }
}

• Reasoning: synchronized provides atomicity and visibility; both methods are mutually exclusive so no interleaving.
• Trade-off: simple but serializes all accesses; may be a bottleneck under high contention.

2. Use AtomicInteger for lock-free atomic get-and-set

import java.util.concurrent.atomic.AtomicInteger;

public class CounterService {
    private final AtomicInteger counter = new AtomicInteger(0);

    public void increment() {
        counter.incrementAndGet(); // atomic increment
    }

    public int getAndReset() {
        return counter.getAndSet(0); // atomically returns old value and sets to 0
    }
}

• Reasoning: incrementAndGet and getAndSet are atomic; getAndSet prevents lost increments around reset.
• Trade-off: good performance under contention. Note: if you need to accumulate extremely high-volume concurrent updates, consider LongAdder for throughput; but LongAdder lacks a single atomic get-and-reset method (you can use sumThenReset() in Java 8+ which is atomic for LongAdder).

Alternative (high-throughput)

import java.util.concurrent.atomic.LongAdder;

public class CounterService {
    private final LongAdder counter = new LongAdder();

    public void increment() {
        counter.increment();
    }

    public long getAndReset() {
        return counter.sumThenReset(); // atomic for LongAdder
    }
}

Complexity

• Time: O(1) per operation.
• Space: O(1).

Edge cases and notes

• Ensure getAndReset semantic: callers expect the returned value to include all increments up to the call moment; use AtomicInteger.getAndSet or LongAdder.sumThenReset to satisfy this.
• If stronger ordering/consistency with other state is required, use external synchronization.

Documentation guidance (what to write in class javadoc / README)

• Explain concurrency contract explicitly:
  • "Thread-safe. increment() may be called concurrently. getAndReset() atomically returns the cumulative count up to invocation and resets the counter to zero. Implemented using AtomicInteger (or LongAdder) to guarantee atomicity and visibility."
• Note performance characteristics:
  • "AtomicInteger: low contention OK; synchronized: simple but blocks. LongAdder: optimized for high update throughput; sumThenReset used for atomic reset."
• Usage examples and expectations:
  • Show example sequence and promise (e.g., increments concurrent with getAndReset will either be included or not depending on ordering but no increments are lost).
• Testing guidance:
  • Add multi-threaded unit tests simulating concurrent increments + resets (e.g., use ExecutorService and latches) and property checks (total increments == sum of all returned values).
• Mention alternatives and when to choose each implementation.

Situation: On a Java microservice I maintained, a lazily-initialized singleton cache (using double-checked locking) intermittently returned null entries under load. Only reproduced in production under bursty traffic.

Task: Find root cause, reproduce reliably, fix code safely, and ensure all code paths covered.

Action:

• Reproduced locally with a stress test using 200 threads hitting cache.get() concurrently and asserting non-null. Wrote a JUnit test that spawns many threads with barriers to maximize contention.
• Added diagnostic logging with thread ids, stack traces, and timestamps around initialization paths. Used jstack and async-profiler to capture thread states during failure windows.
• Debugged with remote JVM to take a heap dump when assertion failed; inspected object graph in Eclipse MAT.
• Root cause: classic double-checked locking without volatile on the cache instance. Under JVM reordering, a reference could be visible before full construction — threads observed a partially-constructed object (ordering/shared-state bug).
• Fix: replaced the pattern with the Initialization-on-demand holder idiom (thread-safe without synchronization) — see code:

public class Cache {
  private Cache() { /* expensive init */ }

  private static class Holder {
    static final Cache INSTANCE = new Cache();
  }

  public static Cache getInstance() {
    return Holder.INSTANCE;
  }
}

• For a quick patch where refactor wasn't possible, I made the instance field volatile to enforce the required memory semantics.

Result / Verification:

• Extended unit tests with stress/fuzz tests (race-fuzzer that randomizes sleep points) and integrated them into CI to run nightly under higher thread counts.
• Added assertion checks in debug builds to fail-fast if a partially-initialized object is observed.
• Monitored production after deploy with increased sampling and logs; no recurrences after rollout.
• Learned: avoid ad-hoc double-checked locking unless fields are volatile or use language idioms designed for safe lazy init.

A simple, idiomatic thread-safe counter in Java can be implemented with AtomicLong. For higher contention, LongAdder offers better throughput by reducing CAS contention.

AtomicLong implementation (correct, simple):

import java.util.concurrent.atomic.AtomicLong;

public class AtomicCounter {
    private final AtomicLong value = new AtomicLong(0);

    public long incrementAndGet() {
        return value.incrementAndGet(); // atomic increment
    }

    public long get() {
        return value.get(); // volatile read, up-to-date view
    }
}

Higher-throughput alternative using LongAdder (better under contention):

import java.util.concurrent.atomic.LongAdder;

public class StripedCounter {
    private final LongAdder adder = new LongAdder();

    public void increment() {
        adder.increment(); // updates a cell to reduce contention
    }

    public long get() {
        return adder.sum(); // aggregates cells; slightly heavier read
    }
}

Why correct:

• AtomicLong uses atomic CAS operations and provides memory visibility guarantees (volatile semantics) so increments/read are linearizable.
• LongAdder internally maintains cells (striping) with CAS per-cell; sum() aggregates cells producing a logically consistent total (not strictly linearizable for concurrent updates but acceptable for counters/metrics).

Performance implications:

• AtomicLong: low memory, simple, but under high contention many threads contend on a single CAS leading to retries and reduced throughput.
• LongAdder: higher throughput under contention by sharding updates across cells; writes are fast, but get/sum is heavier and not strictly atomic with respect to concurrent increments. Also uses more memory and has slightly weaker consistency semantics (eventual aggregation). Choose AtomicLong when strict atomic read-after-update is required; choose LongAdder for high-throughput statistics where occasional stale reads are acceptable.

Edge cases:

• Handle overflow if long can wrap in long-running systems.
• If you need exact linearizable read-after-increment, prefer AtomicLong.

To show a read-modify-write race, imagine a threadsafe cache map isn't actually synchronized when updating a counter stored under a key. Two threads can read the same value, increment, and write back — losing one update.

// C++ example (not thread-safe)
#include <unordered_map>
using Cache = std::unordered_map<int,int>;
Cache cache;

void increment(int key) {
    int v = cache[key];   // read
    v = v + 1;            // modify
    cache[key] = v;       // write
}

Why intermittent corruption appears

• The race depends on timing. If Thread A reads v=5, then Thread B reads v=5 before A writes v=6, both write v=6 — one increment lost.
• On some runs CPU scheduling or memory ordering makes one thread complete before the other, so behavior appears correct; other interleavings expose the bug.
• With more cores, higher load, or added delays (I/O, logging) the window for problematic interleavings grows—hence intermittent and environment-dependent.

Locking fix

• Use a mutex per cache or per key.

#include <mutex>
std::mutex m;
void increment(int key){
  std::lock_guard<std::mutex> g(m);
  cache[key] = cache[key] + 1;
}

Trade-offs: simple and correct; serializes access (contention) and can reduce throughput; careful to avoid deadlocks and long-held locks.

Lock-free fixes

1. Use atomics for values (std::atomic<int>) so increments are atomic:

std::unordered_map<int,std::atomic<int>> cache;
void increment(int key){ cache[key].fetch_add(1, std::memory_order_relaxed); }

2. Use compare-and-swap if you must update compound data or install-if-absent:

• Use concurrent hashmap (e.g., Java ConcurrentHashMap::compute) or lock-free algorithms with CAS loops.

Trade-offs: atomics give high throughput and lower latency under contention but only work for simple operations and need careful memory-order reasoning. Lock-free code is more complex to get right. Per-key locks balance contention and simplicity.

Conclusion: detect with stress tests and tools (helgrind/tsan), then choose mutexes for correctness/ease or atomics/concurrent data structures for performance-sensitive hot paths.

Approach: use a LinkedHashMap(accessOrder=true) to maintain LRU order and a single ReentrantLock to serialize mutations and accesses (get updates order). This is simple, correct for capacity=1 and N, and resists concurrent get/put races because every operation that can change state or rely on consistent ordering grabs the lock. For higher throughput you could use segmented caches (sharding) or a ConcurrentLinkedDeque + ConcurrentHashMap with finer-grained locking, but complexity increases.

Java implementation:

import java.util.*;
import java.util.concurrent.locks.ReentrantLock;

public class LRUCache<K, V> {
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final LinkedHashMap<K, V> map;

    public LRUCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity > 0 required");
        this.capacity = capacity;
        this.map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                return size() > LRUCache.this.capacity;
            }
        };
    }

    public V get(K key) {
        if (key == null) throw new NullPointerException("null keys not allowed");
        lock.lock();
        try {
            return map.get(key); // accessOrder=true updates order on get
        } finally {
            lock.unlock();
        }
    }

    public void put(K key, V value) {
        if (key == null || value == null) throw new NullPointerException("null keys/values not allowed");
        lock.lock();
        try {
            map.put(key, value);
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        lock.lock();
        try {
            return map.size();
        } finally {
            lock.unlock();
        }
    }

    // for testing/visibility
    public List<K> snapshotKeysInOrder() {
        lock.lock();
        try {
            return new ArrayList<>(map.keySet());
        } finally {
            lock.unlock();
        }
    }
}

Key points / locking strategy:

• Single ReentrantLock ensures mutual exclusion for get and put because get modifies internal order (LinkedHashMap). This prevents race conditions where concurrent gets/puts interleave and corrupt order or violate capacity.
• All public ops that touch state acquire the lock; small critical sections minimize hold time.
• Complexity: get/put O(1) amortized. Space O(capacity).
• Bottlenecks: single lock serializes all operations — under very high concurrency this becomes a contention point. Mitigations: sharded caches (multiple LRU segments keyed by hash), or lock-free designs using ConcurrentHashMap + concurrent deque (more complex to keep exact LRU).
• Capacity=1 works because LinkedHashMap will evict properly under lock.

Testing under concurrency:

• Unit tests for null rejection, capacity edge cases, and basic LRU behavior.
• Concurrency stress tests: use ExecutorService with many threads performing randomized get/put sequences. Use CountDownLatch to start threads simultaneously, run many iterations, then validate invariants: size() <= capacity, no nulls present, and most-recent ordering consistent with a serialized log of operations (you can run a single-threaded reference LRU for the same sequence to compare).
• For races: create targeted tests where many threads repeatedly get the same key and other threads put new keys; assert no exceptions, size bound maintained, and no structural corruption (snapshotKeysInOrder should be valid).
• Add long-running stress test and monitor for deadlocks; include thread dumps if failures observed.

Edge cases:

• capacity <= 0 rejected.
• null keys/values rejected immediately.
• Concurrent access where get must update order — hence locking get.
• Eviction callback/notification would need to run outside lock to avoid long-held locks.

This design favors correctness and simplicity; for production with heavy read traffic consider segmented caches or a specialized concurrent LRU implementation.