Atomic và CAS — Compare-And-Swap bên dưới AtomicInteger

TL;DR: AtomicInteger và gia đình java.util.concurrent.atomic không dùng lock OS — chúng dùng CAS (Compare-And-Swap), một hardware instruction đơn lẻ nguyên tử (x86 CMPXCHG, ARM LL/SC). CAS: so sánh giá trị tại địa chỉ với expected, nếu match thì swap với new value, return kết quả — tất cả trong 1 cycle không bị interrupt. Khi contention thấp, atomic nhanh hơn synchronized vì không cần syscall. Nhưng CAS có ABA problem (fix bằng AtomicStampedReference), và khi contention cao thì LongAdder thắng AtomicLong. Bài này giải thích tận CPU instruction, đủ để bạn lý luận chính xác khi nào atomic đủ và khi nào phải lock.

Bài 02 giới thiệu AtomicInteger như "giải pháp cho counter++ race". Bài này đi sâu vào cơ chế bên dưới — CAS instruction, lock-free semantics, và những case atomic không replace được lock.

1. Scenario — counter shared, synchronized là bottleneck

API gateway đếm số request mỗi endpoint để rate limiting. 100 thread xử lý request song song, mỗi thread increment counter sau khi phục vụ xong.

Phương án synchronized:

class RequestCounter {
    private long count = 0;
    private final Object lock = new Object();

    public void increment() {
        synchronized (lock) {
            count++;
        }
    }

    public long get() {
        synchronized (lock) {
            return count;
        }
    }
}

Vấn đề: với 100 thread, 99 thread phải queue bên ngoài lock mỗi lần increment. Syscall futex (Linux) để manage lock → context switch → overhead. Benchmark JMH trên máy 8 core cho thấy AtomicLong throughput cao hơn synchronized counter 5-10 lần khi contention trung bình.

Tại sao? Vì AtomicLong dùng CAS — không cần OS, không cần syscall, không context switch.

2. CAS — Compare-And-Swap, hardware instruction nguyên tử

CAS (Compare-And-Swap) là CPU instruction nguyên tử: "So sánh giá trị tại địa chỉ memory X với giá trị expected. Nếu bằng nhau, ghi newValue vào X và trả true. Nếu khác, không làm gì và trả false." Toàn bộ 3 bước xảy ra như 1 đơn vị không thể bị interrupt.

Trên x86/x86-64: instruction CMPXCHG (Compare and Exchange):

; Pseudocode: atomically compare [mem] with EAX, if equal swap with EDX
CMPXCHG [mem], EDX    ; if [mem]==EAX then [mem]=EDX, ZF=1 else EAX=[mem], ZF=0

Trên ARM: cặp LDREX/STREX (Load-link/Store-conditional — LL/SC):

• LDREX r0, [addr]: load value và mark address "exclusive" trong hardware monitor.
• STREX r1, r2, [addr]: cố ghi r2 vào addr. Nếu không có thread/CPU khác modify addr kể từ LDREX, ghi thành công (r1=0). Nếu có, fail (r1=1). Caller retry.

Cả 2 đều là single-instruction atomic — CPU hardware đảm bảo không có thread nào khác thực hiện operation giữa compare và swap.

sequenceDiagram
    participant T1 as Thread 1
    participant T2 as Thread 2
    participant M as Memory [value=5]

    T1->>M: CAS(expected=5, new=6)
    Note over M: Atomic compare-and-swap
    M-->>T1: success (value now 6)
    T2->>M: CAS(expected=5, new=6)
    M-->>T2: FAIL (value is 6, not 5)
    T2->>M: CAS(expected=6, new=7)
    M-->>T2: success (value now 7)

3. Lock-free, wait-free, blocking — định nghĩa

3 đặc tính quan trọng khi nói về concurrent data structure:

Blocking: thread có thể bị block vô hạn bởi thread khác (mutex, semaphore). Nếu thread giữ lock bị kill, thread khác block mãi mãi.

Lock-free: ít nhất 1 thread tiến triển trong mọi khoảng thời gian hữu hạn — system không đứng yên, dù có thể một số thread retry nhiều lần. Không cần OS lock nhưng không guarantee mỗi thread cá nhân tiến triển.

Wait-free: tất cả thread đều tiến triển trong N bước bounded, không phụ thuộc hành động của thread khác. Mạnh nhất nhưng khó implement.

AtomicInteger với CAS loop là lock-free: nếu 1 thread CAS fail, ít nhất 1 thread khác CAS success → system tiến. Nhưng 1 thread cụ thể có thể retry nhiều lần trong môi trường contention cao — không wait-free.

LongAdder (striped cells) tiến gần hơn wait-free nhưng không guarantee.

4. AtomicInteger API và CAS loop pattern

import java.util.concurrent.atomic.AtomicInteger;

AtomicInteger counter = new AtomicInteger(0);

counter.get();                           // read current value
counter.set(10);                         // set value
counter.getAndSet(20);                   // set, return old value
counter.incrementAndGet();               // atomic ++, return new value
counter.getAndIncrement();               // atomic ++, return old value
counter.addAndGet(5);                    // atomic +=5, return new value
counter.getAndAdd(5);                    // atomic +=5, return old value

// CAS truc tiep
boolean ok = counter.compareAndSet(10, 20);
// If current==10: set to 20, return true
// If current!=10: no change, return false

// Higher-level update operations (Java 8+)
counter.updateAndGet(x -> x * 2);       // atomic: x = x*2, return new
counter.accumulateAndGet(3, (x, y) -> x + y);  // atomic: x = x+y, return new

CAS loop pattern — idiomatic khi cần custom update:

AtomicInteger counter = new AtomicInteger(0);

// Increment chi khi value < 100 (bounded counter)
public boolean tryIncrement() {
    int current, next;
    do {
        current = counter.get();
        if (current >= 100) return false;  // boundary check
        next = current + 1;
    } while (!counter.compareAndSet(current, next));
    return true;
}

Cơ chế: đọc current, tính next. CAS thử swap. Nếu fail (thread khác đã modify), đọc lại current và thử lại. Mỗi fail có nghĩa là ít nhất 1 thread khác thành công — system tiến triển.

Vì sao không race condition: compareAndSet là 1 hardware instruction. Không thread nào chen vào giữa compare và set. Nếu 2 thread cùng đọc current=5, cùng tính next=6, chỉ 1 CAS thành công. Thread kia fail và retry với current=6, tính next=7. Không mất update.

5. Vì sao CAS nhanh hơn synchronized khi contention thấp

synchronized cần:

1. Check lock state (atomic instruction).
2. Nếu locked: syscall futex_wait (Linux) → kernel mode, thread bị suspend, context switch.
3. Khi release: futex_wake → kernel mode, wake waiting thread.

Mỗi lock/unlock cần 2 syscall khi có contention. Kernel mode transition tốn ~1000ns.

AtomicInteger.incrementAndGet() khi không contention:

1. LOCK XADD (x86) — 1 instruction, no syscall.
2. Tốn ~10-50ns.

Khi contention thấp (vài thread), CAS retry hiếm khi xảy ra → throughput cao.

Khi contention rất cao (100 thread cùng update 1 counter): CAS fail nhiều → CPU spin retry → CPU cycles lãng phí mà không tiến triển. Đây là lúc LongAdder thắng.

6. AtomicReference — CAS trên object reference

AtomicReference<V> áp CAS lên object reference (pointer), không phải primitive.

import java.util.concurrent.atomic.AtomicReference;

record Config(int timeout, int maxConn) {}

AtomicReference<Config> configRef = new AtomicReference<>(new Config(30, 100));

// Hot-swap config atomic -- no lock needed
Config oldConfig = configRef.get();
Config newConfig = new Config(60, 200);
boolean swapped = configRef.compareAndSet(oldConfig, newConfig);

Lưu ý quan trọng: CAS của AtomicReference so sánh reference equality (==), không phải equals(). Hai object cùng nội dung nhưng khác instance sẽ CAS fail.

String a = new String("hello");
String b = new String("hello");
AtomicReference<String> ref = new AtomicReference<>(a);

// CAS voi b -- FAIL vi a != b (khac reference du cung content)
boolean ok = ref.compareAndSet(b, "world");
System.out.println(ok); // false

Pattern đúng với AtomicReference: giữ tham chiếu đến object cũ, dùng tham chiếu đó để CAS:

Config currentConfig = configRef.get();   // keep reference
// ... decide newConfig based on currentConfig ...
boolean ok = configRef.compareAndSet(currentConfig, newConfig);  // reference compare

7. ABA problem — khi CAS không đủ

ABA problem là lỗi tinh tế nhất với CAS. Scenario:

1. Thread 1 đọc value = A.
2. Thread 2 đổi A → B.
3. Thread 2 đổi B → A lại.
4. Thread 1 CAS: "value vẫn là A, swap!" → thành công. Nhưng intermediate B đã xảy ra và có thể đã thay đổi state liên quan.

Trong nhiều trường hợp ABA vô hại (counter đơn giản). Nhưng trong lock-free linked list hay stack, ABA nguy hiểm:

Stack ban dau: [A] -> [B] -> [C]
Thread 1 doc head=A, chuan bi pop A
Thread 2 pop A, pop B (stack gio: [C])
Thread 2 push A lai (stack gio: [A] -> [C])
Thread 1 CAS head: A -> B? Thanh cong (head van la A)
Nhung B da bi pop boi Thread 2, node B co the da bi gc hoac reuse!
Stack gio bi corrupt: [B] -> [C] trong khi B da invalid

Fix: AtomicStampedReference<V>

AtomicStampedReference (Java 5) ghép value với một integer stamp (version counter). CAS phải match cả value VÀ stamp:

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

// Doc value va stamp cung luc
int[] stampHolder = new int[1];
String value = ref.get(stampHolder);  // value="A", stampHolder[0]=0

// CAS: chi swap neu ca value va stamp match
boolean ok = ref.compareAndSet(
    "A", "B",        // expectedRef, newRef
    0,   1           // expectedStamp, newStamp
);

// Thread khac doi A->B->A nhung stamp tang: 0->1->2
// Khi thread 1 thu CAS voi stamp=0, fail vi stamp hien tai=2

Mỗi lần update tăng stamp. Thread không thể phân biệt A lần đầu với A sau khi qua B, nhưng stamp khác nhau — CAS fail. ABA bị detect.

Trade-off: AtomicStampedReference tốn thêm memory (giữ cả value lẫn stamp) và đọc phức tạp hơn (phải truyền int[] để nhận stamp).

Có thể dùng AtomicMarkableReference nếu chỉ cần 1 bit mark (boolean) thay vì full stamp.

8. LongAdder vs AtomicLong — chọn loại nào cho counter

AtomicLong dùng 1 cell memory. Tất cả thread update cùng 1 location → cache line bouncing: mỗi lần 1 thread write, CPU phải invalidate cache của tất cả core khác, các core re-read từ memory. Với 100 thread, đây là bottleneck.

LongAdder (Java 8, cùng package với AtomicLong) dùng striped counter — mảng cell, mỗi thread update 1 cell riêng (hash by thread ID). Khi gọi sum(), cộng tất cả cell lại.

// AtomicLong -- 1 cell, good for low contention
AtomicLong atomicCounter = new AtomicLong(0);
atomicCounter.incrementAndGet();
long val = atomicCounter.get();   // exact atomic snapshot

// LongAdder -- striped, good for high contention
LongAdder adder = new LongAdder();
adder.increment();
adder.add(5);
long sum = adder.sum();           // NOT atomic snapshot -- cells may change
                                  // between reads; OK for stats, NOT for CAS

Benchmark trên máy 8 core, 32 thread cùng increment:

• AtomicLong: ~200M ops/sec.
• LongAdder: ~900M ops/sec (4.5x speedup).

Trade-off của LongAdder:

• sum() đọc tất cả cell, không atomic — giữa khi đọc cell 1 và cell 8, thread khác có thể đã update cell 5. Không dùng được cho CAS logic.
• Tốt cho metrics, request counter, throughput tracking — không cần exact snapshot.
• Kém hơn AtomicLong khi contention thấp (overhead cell management).

// Dung dung use case:
LongAdder requestCount  = new LongAdder();  // metrics, ok voi approximate sum
AtomicLong userId       = new AtomicLong(); // ID generation, phai exact, sequence
AtomicReference<Config> cfg = new AtomicReference<>();  // hot-swap config

Tương tự: LongAccumulator (tổng quát hơn, cho phép custom reduction function), DoubleAdder, DoubleAccumulator.

9. Atomic vs lock — khi nào dùng cái nào

Atomic phù hợp khi:

• Update 1 biến đơn theo operation không phụ thuộc biến khác.
• Logic đủ đơn giản để biểu diễn bằng CAS loop (increment, max, min, CAS-and-swap).
• Contention thấp đến trung bình.

Lock phù hợp khi:

• Cần update nhiều biến mà phải giữ invariant (ví dụ: cập nhật cả x và y sao cho x + y == constant).
• Logic phức tạp hơn 1 CAS — cần nhiều bước atomic cùng nhau.
• Cần Condition (waiting set) — không có với AtomicXxx.

Ví dụ không thể thay lock bằng atomic:

// SAI -- dung 2 atomic rieng biet de giu invariant
AtomicLong balance  = new AtomicLong(1000);
AtomicLong reserved = new AtomicLong(0);
// Invariant: balance + reserved == 1000

void reserve(long amount) {
    balance.addAndGet(-amount);    // step 1
    // <-- Thread khac co the doc giua step 1 va step 2
    reserved.addAndGet(amount);    // step 2
}
// Thread khac thay balance=900, reserved=0 (invariant bi vi pham thoang qua)

Fix bằng lock:

void reserve(long amount) {
    synchronized (lock) {
        balance  -= amount;   // step 1
        reserved += amount;   // step 2
    }
    // Invariant luon dung trong lock
}

10. So sánh tổng hợp

11. Deep Dive

12. Self-check

private final Object lock = new Object();
private int x = 60, y = 40;  // khong can atomic nu dung lock

void transfer(int amount) {
  synchronized (lock) {
      x -= amount;  // step 1
      y += amount;  // step 2
  }
  // invariant luon dung trong lock
}