Atomic & CAS: đồng bộ lock-free cho thao tác trên một biến

TL;DR: Với thao tác trên đúng một biến, không cần khóa. Compare-and-swap (CAS) — lệnh nguyên tử của CPU — cho phép cập nhật lạc quan theo vòng lặp đọc-tính-thử: thất bại thì đọc lại và làm lại, không thread nào block. Các lớp Atomic* đóng gói vòng lặp đó; AtomicReference ghép với immutable holder để cập nhật nguyên tử cả cụm trường với nhiều writer. Ba góc khuất phải thuộc: ABA (CAS so giá trị, không so lịch sử — cần stamp), lambda trong updateAndGet phải thuần vì có thể chạy lại nhiều lần, và dưới contention ghi nặng thì LongAdder tản stripe thắng AtomicLong. Ranh giới cứng: CAS không gói được invariant trải trên nhiều biến — lúc đó quay về khóa.

1. Vì sao tăng một bộ đếm lại phải khóa cả object?

Bài trước, để sold của BookingService tăng đúng, ta quây nguyên cả object sau một intrinsic lock: mỗi khách đặt vé thì mọi khách khác xếp hàng, dù việc cần làm chỉ là cộng một vào bộ đếm. Gốc rễ nằm ở bài Atomicity: sold++ là read-modify-write ba bước, hai thread chen vào giữa có thể cùng đọc 9, cùng ghi 10, bốc hơi một lần tăng. volatile chỉ lo visibility, không gói ba bước thành một khối. Còn synchronized là hàng rào loại trừ sinh ra cho cả cụm thao tác phức tạp, nay bị bắt đi canh một biến.

Luận điểm của bài: với thao tác trên đúng một biến, ta đạt atomicity mà không cần khóa. Cơ sở là compare-and-swap (CAS), chỉ thị phần cứng mà mọi CPU hiện đại đều có. CAS nhận ba đối số — vị trí bộ nhớ, giá trị kỳ vọng, giá trị mới — và nguyên tử trong một nhịp: nếu giá trị ở đó còn bằng kỳ vọng thì ghi giá trị mới rồi báo thành công, ngược lại báo thất bại.

Điểm cốt lõi là cách dùng nó. Khóa bi quan: giả định sẽ có xung đột nên chặn trước rồi mới làm. CAS lạc quan: đọc giá trị hiện tại, tính giá trị mới, rồi ghi với điều kiện chưa ai đổi từ lúc ta đọc — thành công thì cả quãng đọc-tính-ghi không ai chen vào, thất bại thì vứt kết quả và thử lại. Nói cho chính xác: một cập nhật lock-free là một vòng lặp quanh chỉ thị CAS, không phải một lệnh duy nhất.

int oldValue, newValue;
do {
    oldValue = readCurrent();        // doc gia tri hien tai
    newValue = oldValue + 1;         // tinh gia tri moi dua tren no
} while (!compareAndSet(oldValue, newValue));  // chi ghi neu chua ai doi; that bai thi lap lai

Một analogy: cuốn sổ ghi chung chỗ đông người. Cách "khóa" là ai muốn viết phải cầm cây bút duy nhất; cách "CAS" là ai cũng có bút riêng, nhưng chỉ được viết nếu dòng cuối vẫn như lúc mình đọc.

Đặc tính ấy quyết định khi nào CAS thắng: contention thấp thì phần lớn lần thử thành công ngay, không block, không context switch; contention cao thì các vòng retry quay không tải, đốt CPU. Khóa biến tranh chấp thành chờ đợi (thread ngủ), CAS biến nó thành làm lại (thread bận) — điểm yếu này đẻ ra LongAdder ở mục 4.

Trên JVM, CAS phơi ra qua các method nội tại mà JIT dịch thẳng thành chỉ thị phần cứng: x86 là lock cmpxchg, ARM là cặp load-linked/store-conditional. Một chú thích cho chính xác: với phép cộng dồn trên x86-64, getAndAdd được intrinsify thành lock xadd — fetch-and-add, cộng và trả giá trị cũ trong một lệnh, không cần retry. CAS-loop là đường fallback khi không có lệnh chuyên dụng.

2. Các lớp Atomic*

java.util.concurrent.atomic gói CAS và vòng lặp retry vào những lớp dễ dùng — AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference — mỗi lớp bọc một giá trị duy nhất. Đây là lời giải lock-free cho bộ đếm vé của TicketFlow, biến thể của bước v1 trong capstone.

public class SeatCounter {
    private final AtomicInteger sold = new AtomicInteger(0);

    public int reserve()   { return sold.incrementAndGet(); }   // khong khoa, van nguyen tu
    public int soldCount() { return sold.get(); }               // reader khong can khoa
}

incrementAndGet là getAndIncrement đảo chiều trả về — cả hai nguyên tử, ngữ nghĩa đúng vòng lặp CAS ở mục trên, chỉ là JDK viết hộ (trên x86 chúng intrinsify thành một lệnh lock xadd). So với bản Monitor Pattern, hai khách đặt vé không còn ngủ chờ nhau mà cùng thử CAS.

Bộ method chia ba nhóm. Cộng dồn — getAndIncrement, getAndAdd, addAndGet — cho số nguyên. CAS trần — compareAndSet(expected, new) — trả boolean đúng như chỉ thị phần cứng, là viên gạch để tự xây cập nhật phức tạp hơn. Cập nhật theo hàm — updateAndGet, accumulateAndGet, getAndUpdate — nhận lambda "giá trị mới tính từ giá trị cũ thế nào" rồi tự chạy vòng retry:

private final AtomicInteger sold = new AtomicInteger(0);

// chi giu cho neu chua het ve — compound action van nguyen tu nho retry quanh lambda
public boolean reserveIfAvailable() {
    int prev = sold.getAndUpdate(cur -> cur < capacity ? cur + 1 : cur);
    return prev < capacity;   // prev < capacity nghia la lan nay ta gianh duoc mot cho
}

Cảnh báo gắn liền với nhóm cuối là hệ quả của vòng lặp retry: hàm bạn truyền vào có thể bị gọi nhiều lần khi có contention, vì mỗi lần CAS thất bại nó chạy lại trên giá trị mới. Hàm đó phải thuần — không side effect. Một lambda tưởng vô hại như "cộng một và đồng thời tăng một metric" sẽ tăng metric nhiều hơn số cập nhật thật, và bẫy này không lộ trong test đơn luồng.

AtomicReference mở cơ chế đó cho một tham chiếu object thay vì một số — cầu nối tới bài Immutability: gói nhiều trường vào một holder immutable rồi đặt holder sau một AtomicReference, ta cập nhật nguyên tử cả cụm trường bằng CAS.

public record Availability(int sold, int capacity) {
    Availability soldOne() { return new Availability(sold + 1, capacity); }
}
private final AtomicReference<Availability> state = new AtomicReference<>(new Availability(0, 100));

public boolean reserve() {
    Availability prev, next;
    do {
        prev = state.get();
        if (prev.sold() >= prev.capacity()) return false;   // het ve, khong retry vo ich
        next = prev.soldOne();
    } while (!state.compareAndSet(prev, next));   // ai chen vao thi prev cu → CAS truot → lap lai
    return true;
}

Đây là chỗ atomic vượt qua volatile của bài trước: bản volatile chỉ đúng khi một writer, còn bản AtomicReference đúng với nhiều writer, vì CAS lọc ra đúng một người thắng mỗi vòng. Giới hạn vẫn còn: ta cập nhật nguyên tử một tham chiếu duy nhất. Nếu invariant trải trên hai AtomicReference phải đổi cùng lúc, CAS từng cái một không gói được cả hai vào một thao tác, và ta lại phải về với khóa — ranh giới đó là chủ đề kết bài.

3. ABA problem

CAS hỏi đúng một câu: "giá trị hiện tại có còn bằng giá trị tôi kỳ vọng không?" Lớp lỗi tinh vi nằm ở chỗ nó chỉ so giá trị chứ không so lịch sử. Nếu một biến đi từ A sang B rồi quay lại A trong lúc ta đang tính toán, CAS vẫn thấy A và vẫn thành công — dù thế giới đã thay đổi rồi trở lại. Đây là ABA problem.

Với bộ đếm số nguyên thuần, ABA vô hại: giá trị quay lại đúng số cũ thì phép cộng vẫn đúng. ABA chỉ thành lỗi khi giá trị mang ý nghĩa về danh tính hoặc cấu trúc — kinh điển nhất là CAS trên tham chiếu node trong cấu trúc lock-free như ngăn xếp. Một thread đọc node đỉnh A, định CAS đỉnh sang node kế; xen giữa, thread khác pop A, pop cả node kế, rồi push lại A. CAS của thread đầu thấy đỉnh vẫn là A nên thành công, nhưng "node kế của A" đã bị gỡ khỏi stack — cấu trúc hỏng âm thầm.

sequenceDiagram
    participant T1 as Thread 1
    participant S as Stack (top)
    participant T2 as Thread 2
    T1->>S: doc top = A, next cua A = B
    Note over T1: tam dung truoc khi CAS(A, B)
    T2->>S: pop A, pop B
    T2->>S: push lai A
    Note over S: top van la A, nhung B da bi go khoi stack
    T1->>S: CAS(top: A -> B) THANH CONG
    Note over S: top tro vao node B da chet - cau truc hong am tham

Lời giải là gắn vào mỗi giá trị một dấu hiệu đổi-mỗi-lần-ghi. AtomicStampedReference ghép tham chiếu với một con tem số nguyên — stamp — tăng mỗi lần cập nhật; CAS chỉ thành công khi cả tham chiếu lẫn stamp đều khớp, nên chuyến đi A→B→A bị lộ ngay vì stamp đã nhảy.

// stamp tang moi lan ghi → chuyen di A→B→A bi phat hien vi stamp khong con khop
AtomicStampedReference<Node> top = new AtomicStampedReference<>(initial, 0);

int[] stampHolder = new int[1];
Node cur = top.get(stampHolder);   // doc kem stamp hien tai
top.compareAndSet(cur, cur.next, stampHolder[0], stampHolder[0] + 1);   // khop ca ref lan stamp

AtomicMarkableReference là biến thể gọn hơn: thay con tem đếm bằng một bit boolean — cờ "đã bị đánh dấu" — cho thuật toán chỉ cần biết node đã bị logic xóa chưa. Cả hai đắt hơn CAS trần vì phải đóng gói cặp tham-chiếu-và-dấu, nên chỉ rút ra khi ABA thật sự là rủi ro (khi ta tự xây cấu trúc lock-free), chứ không rải mặc định lên mọi AtomicReference.

4. LongAdder và LongAccumulator

Quay lại điểm yếu ở mục 1: dưới contention cao, vòng lặp CAS của AtomicLong quay không tải. Hình dung bộ đếm metric toàn cục bị hàng chục thread cùng incrementAndGet mỗi mili giây: tất cả tranh một ô nhớ, và mỗi lần một thread CAS thành công, ô đó đổi, làm vô hiệu bản cache của nó trên mọi core khác. Đây là cache contention: một thao tác lẽ ra rẻ thành nút cổ chai khi số core tăng.

LongAdder (Java 8) né bằng một ý tưởng đẹp: nếu tranh một ô gây đau thì đừng bắt các thread tranh một ô. Nó rải tổng ra một mảng nhiều ô — cells — mỗi thread dưới contention cộng vào ô riêng. Đây là striped counter, bộ đếm chia sọc; khi cần giá trị thật, sum() cộng tất cả các ô.

private final LongAdder requestsServed = new LongAdder();

public void onRequest() { requestsServed.increment(); }  // cong vao o rieng theo thread, it dung do
public long total()     { return requestsServed.sum(); } // cong don tat ca o — KHONG phai snapshot

Đặt hai thiết kế cạnh nhau:

flowchart TD
    subgraph AL[AtomicLong: moi thread tranh MOT o]
        T1[Thread 1] --> V[value - CAS lien tuc that bai]
        T2[Thread 2] --> V
    end
    subgraph LA[LongAdder: moi thread hash vao cell rieng]
        U1[Thread 1] --> C0[Cell 0]
        U2[Thread 2] --> C1[Cell 1]
        C0 --> S["sum() = base + Cell 0 + Cell 1"]
        C1 --> S
        B0[base] --> S
    end

    style V fill:#FCA5A5
    style S fill:#6EE7B7

Khác biệt hiệu năng không hề vi tế. Với một thread, hai bên gần như ngang nhau — AtomicLong còn nhỉnh hơn chút vì không phải quản lý mảng cell. Nhưng đẩy lên hàng chục thread cùng dồn dập tăng, AtomicLong tụt dốc: mọi thread tranh một cache line, CAS thất bại liên tục, cache line nảy qua lại giữa các core, còn LongAdder giữ throughput gần như phẳng. Chênh lệch phụ thuộc số core và mức dồn dập, nên hãy tự đo bằng JMH: contention ghi càng cao, lợi thế stripe càng lớn; không contention thì stripe chỉ tốn thêm bộ nhớ.

Đánh đổi nằm trong cái khéo đó. Một, LongAdder tốn bộ nhớ cho mảng cell. Hai, quan trọng hơn, sum() không phải snapshot nguyên tử: nó duyệt cộng các ô trong khi ô khác vẫn có thể đang được ghi, nên trả về ước lượng tại một thời điểm gần. Tiêu chí chọn: LongAdder thắng khi ghi rất nhiều, đọc thưa — metric, throughput counter; cần đọc chính xác ngay sau mỗi lần ghi, hoặc cần compareAndSet thật trên bộ đếm, thì AtomicLong.

LongAccumulator là tổng quát hóa: thay vì cố định phép cộng, nó nhận một hàm kết hợp hai toán hạng (LongBinaryOperator) và một giá trị gốc — LongAdder chẳng qua là LongAccumulator với phép cộng và gốc 0. Với nó ta gom max, min, hay tích theo cùng kiểu chia sọc:

// theo doi so ve ban duoc trong mot lan giao dich cao nhat, duoi tai ghi nang
LongAccumulator peakBatch = new LongAccumulator(Long::max, 0);

peakBatch.accumulate(batchSize);   // gop bang max, rai soc nhu LongAdder
long peak = peakBatch.get();

Vì hàm kết hợp được áp theo thứ tự không xác định trên các ô, nó phải giao hoán và kết hợp để kết quả không phụ thuộc thứ tự gộp — max và cộng thỏa, phép trừ thì không.

5. VarHandle

Đến giờ ta luôn thao tác qua một object Atomic* bọc lấy giá trị. Đôi khi ta muốn áp chính ngữ nghĩa CAS lên một field bình thường đã có sẵn — tiết kiệm một lớp object, giữ field ở dạng nguyên thủy. VarHandle (Java 9) làm việc đó, thay cho bộ ba field updater cũ (AtomicIntegerFieldUpdater, AtomicLongFieldUpdater, AtomicReferenceFieldUpdater) vốn cồng kềnh vì dựng qua reflection và kiểm tra access mỗi lần dùng.

Một VarHandle là tham chiếu có kiểu, mạnh, tới một biến — một field, một phần tử mảng — cho phép gọi thao tác nguyên tử thẳng lên biến đó. Xin nó một lần qua MethodHandles.lookup() rồi dùng lại:

public class Node {
    private volatile int state;     // field thuong, van volatile
    private static final VarHandle STATE;
    static {
        try { STATE = MethodHandles.lookup().findVarHandle(Node.class, "state", int.class); }
        catch (ReflectiveOperationException e) { throw new ExceptionInInitializerError(e); }
    }
    public boolean tryActivate() {
        return STATE.compareAndSet(this, 0, 1);   // CAS thang tren field, khong can wrapper
    }
}

Giá trị thật của VarHandle không chỉ là CAS trên field trần — nó phơi ra cả một quang phổ chế độ truy cập với memory ordering ở các mức khác nhau, thứ các lớp Atomic* không cho chọn. Phần này dành cho người đã nắm chắc happens-before của bài trước.

Bốn nhóm chế độ, từ lỏng tới chặt. Plain (get/set) — như field thường, không bảo đảm ordering. Opaque — bảo đảm thao tác thật sự xảy ra và các thao tác opaque trên cùng biến không bị reorder với nhau, nhưng không bắc cầu happens-before sang biến khác. Acquire/Release (getAcquire/setRelease) — ngữ nghĩa cặp đọc-ghi volatile nhưng một chiều: setRelease bảo đảm mọi ghi trước nó hiển thị cho thread đọc bằng getAcquire, không áp hàng rào hai chiều. Volatile (getVolatile/setVolatile/compareAndSet) — ngữ nghĩa volatile đầy đủ, mạnh nhất và đắt nhất.

Ý nghĩa thực dụng: volatile là hàng rào hai chiều, an toàn nhưng đắt vì cấm cả reorder vô hại; acquire/release cho đúng nửa hàng rào mà nhiều thuật toán lock-free cần — chẳng hạn công bố một object đã khởi tạo xong — với chi phí thấp hơn. Nhưng chọn sai mức là lỗi không lộ trên kiến trúc CPU này mà bung ra trên kiến trúc khác có mô hình bộ nhớ lỏng hơn. Vì vậy các mức dưới volatile là lãnh địa của thư viện và chuyên gia.

6. Liên hệ các bài khác

• Bài 04 — Atomicity: định nghĩa read-modify-write và sold++ ba bước — bài toán CAS giải bằng đường lock-free.
• Bài 07 — Immutability: immutable holder là nửa kia của mẫu AtomicReference + CAS — holder lo nhất quán, CAS lo nhiều writer.
• Bài 08 — volatile & synchronized: JVM dùng đúng lệnh CAS này cho thin lock; xem lại mục mark word để thấy CAS ở cả hai tầng.
• Bài 11 — ReentrantLock và Condition: khi invariant trải trên nhiều biến, CAS bó tay và explicit lock là bước kế tiếp.
• Bài 13 — Delegation & concurrent collections: ConcurrentHashMap dựng trên chính CAS + striping — hưởng lock-free mà khỏi tự viết retry loop.

7. 📚 Deep Dive Oracle

8. Tóm tắt

• Thao tác trên đúng một biến không cần khóa: CAS cho cập nhật lạc quan — đọc, tính, ghi có điều kiện, trượt thì thử lại. Cập nhật lock-free là vòng lặp quanh chỉ thị CAS (riêng getAndAdd trên x86-64 thành lock xadd, một lệnh).
• Các lớp Atomic* đóng gói vòng lặp đó; AtomicReference ghép holder immutable cho phép cập nhật nguyên tử cả cụm trường với nhiều writer. Lambda của updateAndGet phải thuần, vì nó chạy lại mỗi lần CAS trượt.
• ABA: CAS so giá trị chứ không so lịch sử — dùng AtomicStampedReference hay AtomicMarkableReference khi danh tính quan trọng.
• Ghi nhiều đọc thưa: LongAdder/LongAccumulator tản stripe thắng AtomicLong, đổi lại bộ nhớ và một sum() không nguyên tử. VarHandle cho CAS thẳng trên field sẵn có và mở quang phổ memory ordering.

Ranh giới cứng, đúng chỗ bài sau bắt đầu: CAS chỉ nguyên tử trên một biến. Khi invariant trải trên nhiều biến phải đổi cùng lúc, ta buộc quay về khóa. Mà synchronized thiếu nhiều thứ hệ thống thật cần: không thử-rồi-thôi, không timeout, không hủy giữa chừng, không tách đọc khỏi ghi. Đó là bài kế tiếp về explicit locks, nơi BookingService thay khóa của v1 bằng ReentrantLock (rồi read-write lock và StampedLock ở bài 12).

9. Tự kiểm tra

Bài tiếp theo: ReentrantLock và Condition — khóa tường minh khi synchronized không đủ