Nội thất ConcurrentHashMap: per-bin lock, CAS và snapshot

TL;DR: Mở nắp các concurrent collection để thấy vì sao chúng nhanh mà vẫn an toàn. ConcurrentHashMap giữ mảng Node[] với val/next volatile, nên get() đọc không khóa nhờ happens-before của volatile; đường ghi leo thang hai nấc — bin rỗng cắm bằng CAS không khóa, bin va chạm mới synchronized trên node đầu bin — nên đơn vị tranh chấp là từng bin chứ không phải cả map, còn size() chỉ xấp xỉ vì đếm phân tán kiểu LongAdder. CopyOnWriteArrayList chép cả mảng mỗi lần ghi để reader đọc một snapshot bất biến không khóa. Chọn collection theo workload: map nóng, list read-heavy, sorted theo key, hay queue non-blocking.

1. ConcurrentHashMap khóa per-bin và không khóa get() bằng cách nào?

Ta đã dùng ConcurrentHashMap như một hộp đen với ba tính chất nghe có vẻ mâu thuẫn: reader và writer trên key khác nhau không chặn nhau, get() không cần khóa mà vẫn thấy giá trị mới nhất, còn size() lại chỉ gần đúng. Cả ba đều rơi ra từ vài chi tiết cài đặt. Nội bộ map là mảng Node[] — mỗi ô một bin, mỗi bin là danh sách liên kết các Node cùng hash. Giống HashMap, nhưng hai field đặc biệt: mảng table đọc qua volatile-read, và val cùng next của mỗi Node đều volatile.

get() không cần khóa vì cả đường đọc — mảng table, chuỗi next, field val — đều là volatile read. Như bài volatile & synchronized đã dựng nền, volatile read thiết lập happens-before với volatile write phía writer: writer vừa put giá trị mới vào val thì mọi reader sau đó thấy ngay, không cần khóa — song song không phải vì may mắn mà vì mô hình bộ nhớ bảo đảm.

Đường ghi leo thang hai nấc. Bin rỗng (phổ biến khi map đủ rộng): cắm Node mới vào đầu bin bằng một compare-and-swap — đúng cơ chế CAS bài Atomic & CAS đã mổ; CAS trượt vì thread khác cắm trước thì thử lại. Bin đã có node (hai key va nhau ở cùng ô): mới cần khóa, bằng synchronized trên chính node đầu bin — chỉ thread đụng đúng bin này phải xếp hàng. Nghĩa là ConcurrentHashMap hiện đại (từ Java 8) không có "mảng 16 khóa" như lời đồn thời segment cũ — đơn vị tranh chấp là từng bin, fast path còn không khóa:

// So do duong put cua ConcurrentHashMap (gian luoc tu putVal, Java 8+)
for (;;) {
    Node<K,V>[] tab = table;                     // volatile read
    int i = (tab.length - 1) & hash;
    if (tab[i] == null) {
        if (casTabAt(tab, i, null, newNode)) break;   // bin rong: CAS, khong khoa
        // CAS truot -> lap lai voi trang thai moi
    } else {
        synchronized (tab[i]) {                  // va cham: khoa node dau bin
            // update val neu trung key, hoac noi node moi vao cuoi
        }
        break;
    }
}

Vòng for (;;) cộng CAS-trượt-thì-thử-lại chính là optimistic loop của bài Atomic & CAS, chỉ khác đích đến là một ô trong mảng thay vì một biến đơn.

Treeify khi bin quá dài. Hash xấu dồn nhiều key vào một bin thì danh sách dài ra, mỗi lần tra phải duyệt tuyến tính. Khi một bin đạt 8 node (và bảng đủ lớn — từ 64 ô trở lên; nhỏ hơn thì map resize trước thay vì treeify), bin đó thành cây đỏ-đen, đưa thao tác từ O(n) về O(log n) — tấm lưới an toàn trước cả hash collision vô tình lẫn cố ý.

size() chỉ xấp xỉ vì đếm chính xác đòi hỏi đứng yên cả map — một khóa toàn cục mà thiết kế này từ chối. Số phần tử cộng dồn vào một dải counter cell phân tán (kỹ thuật striping của LongAdder): mỗi thread cập nhật một cell ít tranh chấp, size() chỉ cộng các cell tại một thời điểm không đảm bảo đứng yên. Con số đúng "cỡ đó", có thể đã cũ ngay khi bạn cầm — đánh đổi có chủ đích, vì hiếm nghiệp vụ cần size chính xác tuyệt đối trên map đang bị ghi dồn dập.

Còn iterator của ConcurrentHashMap là weakly consistent chứ không fail-fast: duyệt được mà không bao giờ bị ném ConcurrentModificationException, phản ánh trạng thái map tại một thời điểm nào đó kể từ khi tạo và có thể — nhưng không bắt buộc — thấy các thay đổi sau đó. Cùng gốc rễ với get() không khóa: reader đi trên volatile chain, không đòi ai đứng yên.

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

flowchart TB
    subgraph SM["synchronizedMap: 1 khoa ca map"]
        A1["Thread A: get(k1)"] --> LK["khoa duy nhat - moi thao tac xep hang"]
        A2["Thread B: put(k2)"] --> LK
        A3["Thread C: get(k3)"] --> LK
        LK --> HM["HashMap ben trong"]
    end
    subgraph CM["ConcurrentHashMap: khoa theo bin"]
        B1["Thread A: get(k1)"] -->|"volatile read, khong khoa"| BIN1["bin 3"]
        B2["Thread B: put(k2)"] -->|"CAS dau bin rong"| BIN2["bin 7"]
        B3["Thread C: put(k3)"] -->|"synchronized dau bin khi va cham"| BIN2
    end
    style LK fill:#FCD34D
    style BIN1 fill:#6EE7B7
    style BIN2 fill:#6EE7B7

Bên trái, ba thread nối đuôi qua một cổ chai dù chạm ba key khác nhau. Bên phải, hai thread chỉ tranh khi cùng rơi vào bin 7 — phần còn lại của map vẫn thông suốt. Đó là lý do chênh lệch throughput trên map nóng.

2. CopyOnWriteArrayList và CopyOnWriteArraySet: snapshot khi ghi

Không phải workload nào cũng là map đọc-ghi cân bằng. Có một mẫu phổ biến mà ConcurrentHashMap không phải lựa chọn tự nhiên nhất: một danh sách đọc rất nhiều, sửa rất hiếm. Danh sách listener đăng ký nhận sự kiện là ví dụ kinh điển — bị duyệt mỗi lần phát sự kiện, có thể hàng nghìn lần mỗi giây, nhưng chỉ đổi khi ai đó đăng ký/hủy, họa hoằn mới xảy ra.

Cho đúng mẫu đó, java.util.concurrent có CopyOnWriteArrayList và phiên bản set CopyOnWriteArraySet. Cơ chế nằm trong tên: copy-on-write. Đối tượng giữ một mảng nội bộ bất biến; mọi thao tác sửa — add, set, remove — không sửa tại chỗ mà tạo hẳn một bản sao mới của mảng, áp thay đổi lên bản sao, rồi thay con trỏ sang mảng mới. Hệ quả đẹp cho phía đọc: đọc hoàn toàn không cần khóa vì mảng reader đang nhìn là bất biến; và iterator làm việc trên đúng mảng tại thời điểm nó được tạo — một snapshot đông cứng thật sự, nên duyệt không bao giờ ném ConcurrentModificationException và không cần khóa quanh vòng lặp dù thread khác đang sửa danh sách giữa chừng.

// Danh sach listener: doc (duyet de phat su kien) cuc nhieu, ghi (dang ky) cuc hiem
private final List<SaleListener> listeners = new CopyOnWriteArrayList<>();

public void addListener(SaleListener l) { listeners.add(l); }   // hiem khi goi

public void fireSale(Booking b) {
    for (SaleListener l : listeners) {     // khong khoa, khong CME, ke ca khi addListener chay song song
        l.onSale(b);
    }
}

Cái giá lộ ngay từ cơ chế: mỗi lần ghi sao chép nguyên cả mảng. Với danh sách lớn bị sửa thường xuyên, chi phí copy nhanh chóng đắt đỏ và rác sinh ra gây áp lực lên garbage collector. Vì thế copy-on-write chỉ hời khi số lần đọc áp đảo số lần ghi: read-heavy, write-rare thì copy-on-write; ghi đáng kể thì quay về ConcurrentHashMap hoặc cấu trúc khác.

3. Các concurrent collection còn lại: sorted và non-blocking

Hai cấu trúc trên phủ phần lớn nhu cầu, nhưng java.util.concurrent còn vài lựa chọn đáng biết cho các tình huống cụ thể hơn.

Khi cần một map hoặc set vừa thread-safe vừa giữ thứ tự sắp xếp theo key, ConcurrentSkipListMap và ConcurrentSkipListSet là lời giải — phiên bản concurrent của TreeMap/TreeSet, cài bằng skip list, cung cấp các thao tác navigable (firstKey, floorEntry, ceilingKey, subMap) đều thread-safe. ConcurrentHashMap không giữ thứ tự nào; nếu nghiệp vụ đòi duyệt theo thứ tự key — ví dụ bảng giá theo mốc thời gian cần tra "giá gần nhất trước t" — thì skip list map là thứ bạn muốn, đổi lại độ phức tạp logarit thay vì hằng số.

Khi cần một queue hoặc deque thread-safe nhưng không muốn ngữ nghĩa blocking, ConcurrentLinkedQueue và ConcurrentLinkedDeque là lựa chọn non-blocking, dựa trên thuật toán lock-free với compare-and-swap. Chúng không bao giờ chặn thread gọi: offer luôn thành công ngay (queue không giới hạn dung lượng), poll trả null ngay nếu queue rỗng thay vì chờ. Điểm phân biệt then chốt: nếu thứ bạn cần là một thread chờ cho tới khi có phần tử để lấy, hoặc chờ cho tới khi có chỗ để đặt — producer và consumer cần phối hợp nhịp — thì non-blocking queue không phải công cụ. Lúc đó bạn cần BlockingQueue, đúng chủ đề bài kế tiếp.

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

• Delegation & concurrent collections — bài này là "nội thất" của chiến lược delegation ở bài đó; các compound action nguyên tử (compute/merge/putIfAbsent) chạy được là nhờ đúng cơ chế khóa per-bin mổ ở đây.
• Volatile & synchronized — get() không khóa của ConcurrentHashMap đứng trên happens-before của volatile read/write.
• Atomic & CAS — fast path của put là một CAS retry loop; hiểu optimistic loop ở bài đó là hiểu vì sao bin rỗng không cần khóa.
• Blocking Queues & Producer–Consumer — khi bài toán cần phối hợp nhịp chứ không chỉ chia sẻ dữ liệu, ConcurrentLinkedQueue nhường chỗ cho BlockingQueue.

5. Tóm tắt

• ConcurrentHashMap giữ mảng Node[] với val/next volatile; get() đọc không khóa vì volatile read thiết lập happens-before với volatile write của writer — nhiều reader chạy song song với writer mà không cần khóa.
• Đường put leo thang hai nấc: bin rỗng cắm bằng CAS trong một vòng for (;;) optimistic, bin va chạm mới synchronized trên node đầu bin. Đơn vị tranh chấp là từng bin, không có "mảng 16 khóa" như thời segment cũ. Bin đạt 8 node (bảng từ 64 ô) thì treeify về O(log n).
• size()/isEmpty() chỉ xấp xỉ và iterator weakly consistent (không bao giờ ném ConcurrentModificationException) — cái giá của việc từ chối khóa toàn cục để đổi lấy throughput. Số phần tử đếm phân tán kiểu LongAdder.
• CopyOnWriteArrayList/Set hợp read-heavy, write-rare: đọc không khóa, iterator snapshot đông cứng, đổi lại mỗi lần ghi sao chép cả mảng nên đắt khi ghi nhiều.
• ConcurrentSkipListMap/Set cho sorted thread-safe (navigable, O(log n)); ConcurrentLinkedQueue/Deque cho queue non-blocking lock-free. Chọn theo workload chứ không mặc định ConcurrentHashMap cho mọi thứ.

Concurrent collection cho ta chia sẻ dữ liệu an toàn, nhưng không điều phối nhịp giữa thread tạo việc và thread xử lý việc: producer nhanh hơn consumer thì ai bảo nó chờ, hết việc thì consumer chờ thế nào cho khỏi đốt CPU? ConcurrentLinkedQueue cố tình không trả lời — nó không bao giờ chặn. Câu trả lời là BlockingQueue, xương sống của mẫu producer–consumer, và là chủ đề bài kế tiếp.

6. Tự kiểm tra

Bài tiếp theo: Blocking Queues & Producer–Consumer — tách nhịp sản xuất khỏi tiêu thụ