Thread-safe method chưa đủ cho compound invariant

1. Ba kiểu iterator semantics

Đối chiếu nguồn: [C4] [C16] [C17]

2. ConcurrentHashMap mental model

Java 8+ không dùng segmented architecture cũ như câu trả lời phổ biến. Reads phần lớn không khóa; updates phối hợp bằng CAS và synchronization ở bin khi cần, với forwarding nodes trong resize. Tree bins xử lý collision dày. Đây là implementation-level mental model; API guarantee quan trọng hơn chi tiết lock.

• Không chấp nhận null key/value để null có thể biểu diễn “không có mapping” trong concurrent context.
• Retrieval phản ánh most recently completed update theo happens-before semantics được Javadoc mô tả, nhưng aggregate operations không tạo snapshot toàn map.
• size(), iteration và bulk operations dưới concurrent mutation mang tính quan sát, không dùng làm business invariant.

Đối chiếu nguồn: [C1] [C2]

3. Compound race và atomic APIs

// Sai: hai threads có thể cùng thấy null rồi overwrite/lặp construction.
if (!map.containsKey(key)) {
    map.put(key, createValue());
}

// Atomic theo key cho mapping operation.
Value value = map.computeIfAbsent(key, this::createValue);

Mapping function phải ngắn, không recursively update cùng key và không thực hiện remote I/O dài. “Atomic method” không làm side effect bên ngoài atomic với map; function có exception/retry vẫn cần thiết kế riêng.

ConcurrentHashMap<String, LongAdder> counters = new ConcurrentHashMap<>();
counters.computeIfAbsent(status, ignored -> new LongAdder()).increment();

LongAdder giảm contention cho hot counters nhưng sum() dưới concurrent updates không phải atomic snapshot.

Đối chiếu nguồn: [C1] [C5] [C10]

4. BlockingQueue và backpressure

put/take block; offer/poll có immediate/timed variants. Chọn reject/block/drop/coalesce policy theo semantics. Unbounded queue thường biến overload thành latency và OOM thay vì backpressure.

Đối chiếu nguồn: [C3] [C11] [C12] [C13] [C14] [C15]

5. ConcurrentLinkedQueue và lock-free

Non-blocking queue dùng CAS-linked algorithm, phù hợp nhiều producers/consumers khi không cần blocking/backpressure. Lock-free nghĩa system-wide progress dưới contention, không nghĩa mọi thread luôn tiến hoặc operation không bao giờ retry. size() có thể traverse và không phù hợp hot control loop.

Đối chiếu nguồn: [C6]

// Khong dung size() / isEmpty() de quyet dinh poll.
String item = queue.poll();
if (item != null) {
    process(item);
}

6. ConcurrentSkipListMap/Set

Sorted concurrent map/set dựa skip-list structure, hỗ trợ expected O(log n) lookup/update và range/navigable operations. Dùng khi cần cả concurrency lẫn sorted/range semantics; nếu chỉ lookup key, ConcurrentHashMap thường đơn giản/nhanh hơn.

Đối chiếu nguồn: [C7]

7. Backed views

• map.keySet(), values(), entrySet() liên kết với map; remove qua view có thể remove mapping.
• subList, subMap, headMap và tailMap thường là bounded/backed views.
• Collections.unmodifiableList(backing) chặn mutation qua wrapper nhưng backing vẫn đổi được.
• List.copyOf(source) tạo unmodifiable snapshot nông; elements bên trong vẫn có thể mutable.

Đối chiếu nguồn: [C8] [C9] [C17] [C18]

8. Immutable, unmodifiable và persistent

Unmodifiable nói về API mutation qua reference đó. Immutable aggregate yêu cầu observable state không đổi, gồm xử lý mutable elements. Persistent data structure tạo version mới bằng structural sharing; Java standard collections không mặc định persistent.

Đối chiếu nguồn: [C8] [C9]

Map<String, Integer> shared =
    Collections.synchronizedMap(new HashMap<>());

// Moi access phai qua shared; khoa wrapper, khong khoa keySet().
synchronized (shared) {
    for (var entry : shared.entrySet()) {
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

9. Interview scenarios

Đối chiếu nguồn: [C1] [C2]

10. Race labs: điều khiển interleaving, không chờ may rủi

Bổ sung thực hành · Ba chương trình độc lập, Java 21. Dùng barrier/latch thay vì sleep để tạo thứ tự mong muốn. Timeout chỉ ngăn lab treo; không là latency SLO.

Lab D1 · Hai method thread-safe vẫn tạo construction trùng

Failure-first: buộc hai threads cùng đọc absent trước khi put. Sau đó giữ cùng mục tiêu nhưng đổi sang computeIfAbsent; callback chỉ tăng counter local, không remote I/O.

CompoundRaceLab.java

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

public class CompoundRaceLab {
    static int run(boolean atomic) throws Exception {
        var map = new ConcurrentHashMap<String, Integer>();
        var constructions = new AtomicInteger();
        var barrier = new CyclicBarrier(2);

        Callable<Void> task = () -> {
            if (atomic) {
                barrier.await(5, TimeUnit.SECONDS);
                map.computeIfAbsent("key",
                    ignored -> constructions.incrementAndGet());
            } else {
                boolean absent = !map.containsKey("key");
                barrier.await(5, TimeUnit.SECONDS); // Both observed absent.
                if (absent) map.put("key", constructions.incrementAndGet());
            }
            return null;
        };

        try (var pool = Executors.newFixedThreadPool(2)) {
            Future<Void> a = pool.submit(task);
            Future<Void> b = pool.submit(task);
            a.get(10, TimeUnit.SECONDS);
            b.get(10, TimeUnit.SECONDS);
        }
        if (map.size() != 1) throw new AssertionError("mapping count");
        return constructions.get();
    }

    public static void main(String[] args) throws Exception {
        int raced = run(false);
        int fixed = run(true);
        if (raced != 2 || fixed != 1) {
            throw new AssertionError("Unexpected construction counts");
        }
        System.out.printf("check-then-put=%d, computeIfAbsent=%d%n",
            raced, fixed);
        System.out.println("PASS: per-method safety vs compound invariant");
    }
}

javac --release 21 CompoundRaceLab.java
java CompoundRaceLab

Quan sát / acceptance: map cuối đều có một mapping, nhưng construction counts là 2 ở check-then-put và 1 ở computeIfAbsent. Counter construction mới là evidence lỗi; map.size()==1 không đủ. Nộp: stdout và timeline của hai threads. Không suy rộng kết quả này thành exactly-once external side effect.

Lab D2 · Backed view, shallow snapshot và queue đầy

Failure-first: sửa backing sau khi tạo wrapper/copy; sửa object nằm trong bản copy; thêm phần tử COW sau khi tạo iterator; offer vào bounded queue đã đầy mà không có consumer.

ViewsQueueLab.java

import java.util.*;
import java.util.concurrent.*;

public class ViewsQueueLab {
    static void check(boolean ok, String message) {
        if (!ok) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        var base = new ArrayList<>(List.of(1, 2));
        var view = Collections.unmodifiableList(base);
        var copy = List.copyOf(base);
        base.add(3);
        check(view.size() == 3 && copy.size() == 2, "view vs copy");
        base.subList(0, 2).set(0, 99);
        check(base.get(0) == 99, "subList is backed");

        var text = new StringBuilder("a");
        var shallow = List.copyOf(List.of(text));
        text.append("b");
        check(shallow.get(0).toString().equals("ab"), "shallow copy");

        var map = new HashMap<String, Integer>();
        map.put("A", 1);
        map.keySet().remove("A");
        check(map.isEmpty(), "keySet removal must affect map");

        var cow = new CopyOnWriteArrayList<>(List.of("old"));
        var iterator = cow.iterator();
        cow.add("new");
        check(iterator.next().equals("old") && !iterator.hasNext(),
            "snapshot iterator must not see later addition");

        var queue = new ArrayBlockingQueue<String>(1);
        check(queue.offer("first"), "first offer");
        check(!queue.offer("second"), "full queue must reject immediate offer");
        check("first".equals(queue.poll()) && queue.poll() == null,
            "poll and empty result");
        System.out.println("PASS: backed, shallow, snapshot, bounded queue");
    }
}

javac --release 21 ViewsQueueLab.java
java ViewsQueueLab

Acceptance: wrapper nhìn thấy phần tử mới nhưng copy không thấy thay đổi cấu trúc; StringBuilder trong copy vẫn đổi; remove qua keySet xóa mapping; iterator COW không thấy phần tử mới; lần offer thứ hai trả false. Nộp: stdout và policy xử lý false; không thay bounded queue bằng queue unbounded rồi gọi đó là sửa overload.

Lab D3 · Counter bị tách khỏi mapping

Failure-first: worker giữ LongAdder cũ; luồng điều khiển remove rồi thay mapping; worker mới increment. Từng thao tác đều hợp lệ nhưng metric đọc từ map không chứa increment vừa xong.

CounterLifecycleLab.java

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

public class CounterLifecycleLab {
    public static void main(String[] args) throws Exception {
        var counters = new ConcurrentHashMap<String, LongAdder>();
        var old = new LongAdder();
        counters.put("ok", old);
        var loaded = new CountDownLatch(1);
        var replaced = new CountDownLatch(1);

        try (var pool = Executors.newSingleThreadExecutor()) {
            Future<?> worker = pool.submit(() -> {
                LongAdder reference =
                    counters.computeIfAbsent("ok", ignored -> new LongAdder());
                loaded.countDown();
                try {
                    if (!replaced.await(5, TimeUnit.SECONDS)) {
                        throw new AssertionError("replacement timeout");
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    throw new RuntimeException(e);
                }
                reference.increment(); // Increments the detached object.
            });

            if (!loaded.await(5, TimeUnit.SECONDS)) {
                throw new AssertionError("load timeout");
            }
            try {
                counters.remove("ok", old);
                counters.put("ok", new LongAdder());
            } finally {
                replaced.countDown();
            }
            worker.get(10, TimeUnit.SECONDS);
        }
        long visible = counters.get("ok").sum();
        if (old.sum() != 1 || visible != 0) {
            throw new AssertionError("Unexpected lifecycle observation");
        }
        System.out.printf("detached=%d, mapped=%d%n", old.sum(), visible);
        System.out.println("PASS: lifecycle race, not a LongAdder increment bug");
    }
}

javac --release 21 CounterLifecycleLab.java
java CounterLifecycleLab

Acceptance: detached=1, mapped=0. Đây là kết quả interleaving do lab cố ý tạo, không là mất increment bên trong LongAdder. Nộp: timeline và bản sửa có lifecycle rõ: không remove active counter, hoặc mọi update/removal cùng protocol khóa/compute; không còn writer giữ reference ngoài protocol. Chạy lại bản sửa để chứng minh cả lifecycle lẫn tổng sau khi quiescent.

11. Review checklist: từ data structure tới business invariant