LongAdder & VarHandle: đếm dưới contention ghi cao

TL;DR: AtomicLong bắt mọi thread tranh đúng một ô nhớ; dưới contention ghi cao, cache line của ô đó nảy qua lại giữa các core và CAS thất bại liên tục — một thao tác lẽ ra rẻ thành nút cổ chai. LongAdder (Java 8) né bằng striping: rải tổng ra nhiều cell, mỗi thread cộng vào cell riêng, sum() gộp lại khi cần. Đổi lại tốn bộ nhớ và sum() không phải snapshot nguyên tử. Tiêu chí chọn: ghi rất nhiều, đọc thưa (metric, throughput counter) thì LongAdder; cần đọc chính xác từng bước hay cần compareAndSet thật thì AtomicLong. LongAccumulator tổng quát hóa cho phép giao hoán-kết hợp; VarHandle áp CAS thẳng lên một field sẵn có, khỏi bọc object.

Một bộ đếm metric toàn cục — số request phục vụ — bị hàng chục thread cùng incrementAndGet mỗi mili giây. Trên máy 4 core nó chạy êm; lên 32 core, throughput giảm dù thêm core. Không phải bug logic: tất cả thread đang tranh đúng một ô nhớ, và chính sự tranh chấp đó là nút cổ chai.

Bài 10 đã cảnh báo điểm yếu này: khóa biến tranh chấp thành chờ, CAS biến nó thành làm lại — và làm lại dưới contention cao là đốt CPU. Bài này mổ cách LongAdder tản chỗ tranh, khi nào nó thắng AtomicLong, và VarHandle để áp CAS lên field trần.

1. Vì sao AtomicLong nghẽn khi nhiều thread cùng đếm?

AtomicLong gói một vòng lặp CAS quanh đúng một ô nhớ. Với một thread nó rẻ. Nhưng khi nhiều thread cùng dồn dập tăng, hai chi phí chồng lên nhau. Một: CAS chỉ một người thắng mỗi vòng, kẻ thua phải retry — càng đông càng nhiều vòng quay không tải. Hai, và nặng hơn: mỗi lần một thread ghi thành công, ô đó đổi giá trị, làm vô hiệu bản cache của nó trên mọi core khác. Core khác muốn đọc/ghi lại phải kéo cache line về — cache line nảy qua lại giữa các core như quả bóng.

Đây là cache contention: nhiều core tranh cùng một cache line. Nó biến một phép cộng lẽ ra vài nano-giây thành thao tác đồng bộ xuyên core, và càng thêm core càng tệ. Đó là lý do bộ đếm ở đầu bài chậm đi khi lên 32 core.

2. LongAdder — đừng bắt các thread tranh một ô

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 (chọn ô theo một hash của thread). Đây là striped counter, bộ đếm chia sọc; khi cần giá trị thật, sum() cộng tất cả các ô cộng với một base.

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

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 (chỉ một ô, không có cache contention để né). Nhưng đẩy lên hàng chục thread cùng dồn dập, AtomicLong tụt dốc: mọi thread tranh một cache line, còn LongAdder giữ throughput gần như phẳng vì mỗi thread phần lớn chỉ đụng cell riêng. Chênh lệch phụ thuộc số core và mức dồn dập, nên đừng tin con số truyền miệng — tự đo bằng JMH trên máy đích: 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ớ.

3. Cái giá: bộ nhớ và một sum() yếu-nhất-quán

Sự khéo léo đó có giá. Một, LongAdder tốn bộ nhớ cho mảng cell (mảng lớn dần theo mức contention). Hai, quan trọng hơn: sum() không phải snapshot nguyên tử. Nó duyệt cộng từng ô trong khi ô khác vẫn có thể đang được ghi, nên trả về một ước lượng tại một thời điểm gần, không phải giá trị chốt tại một lằn ranh. Nếu đang có ghi đồng thời, hai lần sum() liên tiếp có thể lệch nhau, và không có compareAndSet trên LongAdder — nó không cho phép "chỉ tăng nếu tổng còn bằng X".

4. Choose: LongAdder hay AtomicLong?

Ghép ba điểm trên lại thành tiêu chí chọn:

Nói gọn: LongAdder là bộ đếm ghi nhanh, đọc mờ; AtomicLong là ô chính xác, có CAS. Chọn theo việc đọc của bạn cần chính xác tới đâu và có cần điều kiện hóa phép ghi không.

5. LongAccumulator — tổng quát hóa cho hàm giao hoán-kết hợp

LongAccumulator là bản tổng quát: 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();

Ràng buộc: 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, min, cộng, nhân thỏa; phép trừ thì không (a - b khác b - a).

6. VarHandle — áp CAS thẳng lên field sẵn có

Đế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ó — 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 và họ hàng) vốn cồng kềnh vì dựng qua reflection.

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
    }
}

Ngoài CAS trên field trần, VarHandle còn phơi ra cả một quang phổ chế độ truy cập với memory ordering ở nhiều mức (plain, opaque, acquire/release, volatile) — thứ các lớp Atomic* không cho chọn. Acquire/release cho đúng "nửa hàng rào" mà nhiều thuật toán lock-free cần, rẻ hơn volatile hai chiều. Nhưng chọn sai mức là lỗi không lộ trên CPU này mà bung ra trên CPU khác có mô hình bộ nhớ lỏng hơn — nên các mức dưới volatile là lãnh địa của thư viện và chuyên gia. Ở mức ứng dụng, dùng VarHandle chủ yếu để có compareAndSet trên field mà khỏi bọc Atomic*.

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

• Bài 10 — Atomic & CAS: nền của bài này — vòng lặp CAS và điểm yếu retry-quay-không-tải dưới contention chính là thứ LongAdder né.
• Bài 08 — volatile & synchronized: field trong ví dụ VarHandle vẫn volatile; bốn mức memory ordering của VarHandle là tinh chỉnh happens-before mà bài này định nghĩa.
• Bài 13 — Delegation & concurrent collections: ConcurrentHashMap dùng chính CAS + striping (như LongAdder) — hưởng lock-free mà khỏi tự viết retry loop.

8. 📚 Deep Dive Oracle

9. Tóm tắt

• AtomicLong bắt mọi thread tranh một cache line: dưới contention cao, line nảy giữa các core và CAS trượt liên tục, throughput tụt khi thêm core.
• LongAdder rải tổng ra nhiều cell, mỗi thread cộng vào cell riêng nên gần như không tranh; sum() gộp các cell — không phải snapshot nguyên tử, và không có compareAndSet.
• Choose LongAdder khi ghi rất nhiều - đọc thưa (metric, throughput); choose AtomicLong khi cần đọc chính xác từng bước hoặc cần compareAndSet thật.
• LongAccumulator tổng quát cho hàm giao hoán-kết hợp (max/min/nhân); hàm không giao hoán (phép trừ) cho kết quả phụ thuộc thứ tự striping nên không dùng được.
• VarHandle áp CAS thẳng lên field sẵn có (thay bộ field-updater cũ) và mở quang phổ memory ordering — mức dưới volatile dành cho thư viện.

10. Tự kiểm tra

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