Bài hôm qua kết luận: volatile lo chuyện nhìn thấy, không lo chuyện nguyên tử, và những chỗ cần nguyên tử thì dùng các lớp Atomic*.

Hôm nay là bên trong những lớp đó. Chúng không dùng khoá — chúng dùng một lệnh của CPU, và cái giá phải trả cho việc không khoá là thứ tôi muốn đo cho bạn thấy.

Một lệnh, ba tham số

AtomicInteger x = new AtomicInteger(10);
x.compareAndSet(10, 20);   // "nếu đang là 10 thì đổi thành 20"

  giá trị hiện tại: 10
  CAS(10 -> 20) : true    giờ là 20
  CAS(10 -> 30) : false   vẫn là 20   <- vì không còn là 10

So sánh-và-đổi nói: nếu ô nhớ này vẫn đang giữ giá trị tôi mong đợi thì hãy ghi giá trị mới vào; không thì đừng làm gì và báo cho tôi biết.

Điều làm nó đặc biệt là toàn bộ việc đó xảy ra trong một lệnh của bộ xử lý — trên x86 là CMPXCHG, trên ARM là cặp load-linked/store-conditional. Không luồng nào chen vào giữa được, vì không có "giữa".

Từ đó, incrementAndGet chỉ là một vòng lặp:

int cu, moi;
do {
    cu = y.get();
    moi = cu + 1;
} while (!y.compareAndSet(cu, moi));

Đọc giá trị, tính giá trị mới, rồi thử ghi. Nếu có ai đó chen vào giữa và đổi giá trị, compareAndSet trả false và ta làm lại từ đầu. Đây gọi là lạc quan: cứ làm, hỏng thì thử lại.

Ngược với synchronized là bi quan: giành khoá trước, rồi mới làm.

Cái giá của lạc quan, đo được

Vòng lặp "hỏng thì thử lại" nghe rẻ, cho tới khi có nhiều luồng cùng thử. Tôi đếm số lần compareAndSet trả false, mỗi luồng cộng 200.000 lần vào cùng một biến:

   1 luồng:    5 ms |           0 lần thử lại  (0,00 lần/phép)
   2 luồng:    7 ms |      36.939 lần thử lại  (0,09 lần/phép)
   4 luồng:   18 ms |     201.414 lần thử lại  (0,25 lần/phép)
   8 luồng:  184 ms |   3.250.574 lần thử lại  (2,03 lần/phép)
  16 luồng:  617 ms |   9.052.743 lần thử lại  (2,83 lần/phép)

Với 16 luồng: 9 triệu lần thử hỏng cho 3,2 triệu phép cộng thành công. Gần ba lần công đổ sông đổ biển cho mỗi lần cộng được.

Và đó là công việc có ích bằng không — mỗi lần thử lại là đọc lại, tính lại, thử ghi lại, rồi lại hỏng. CPU chạy hết công suất mà chẳng tiến thêm được gì.

Chú ý bước nhảy từ 4 lên 8 luồng: 18 ms thành 184 ms, gấp mười. Đây không phải suy giảm tuyến tính — đó là lúc mức tranh chấp vượt ngưỡng và mọi luồng bắt đầu dẫm chân nhau.

Chỗ AtomicLong thua cả khoá

Cùng khối lượng công việc, ba cách viết:

  luồng    synchronized    AtomicLong    LongAdder
    1              3 ms          1 ms         2 ms
    2             14 ms          4 ms         4 ms
    4             29 ms         21 ms         3 ms
    8             61 ms         55 ms         1 ms
   16            104 ms        171 ms         2 ms
   32            251 ms        347 ms         9 ms

Đọc theo cột thì thấy ba câu chuyện khác nhau.

AtomicLong thắng khi ít luồng, rồi thua. Ở 1–8 luồng nó nhanh hơn synchronized; từ 16 luồng thì chậm hơn, và ở 32 luồng thì chậm hơn 38%.

Điều này đi ngược trực giác phổ biến rằng "không khoá thì luôn nhanh hơn khoá". Lý do nằm ở bảng trước: khi tranh chấp cao, luồng dùng CAS quay vòng đốt CPU, còn luồng chờ khoá thì được hệ điều hành cho ngủ và nhường CPU cho luồng đang thật sự làm việc.

LongAdder gần như phẳng. Từ 1 tới 32 luồng, nó ở trong khoảng 1–9 ms.

LongAdder làm gì mà hay vậy

Nó không giữ một ô đếm. Nó giữ một mảng ô, mỗi luồng cộng vào ô riêng của mình, và sum() mới cộng tất cả lại.

Tôi soi vào nội bộ sau khi cho 16 luồng cộng 8 triệu lần:

  tổng = 8.000.000
  số ô Cell đã cấp phát: 16   (số nhân CPU: 16)

Đúng bằng số nhân. Nó không cấp trước — mà cấp thêm khi phát hiện tranh chấp, và dừng ở số nhân vì nhiều hơn cũng vô ích.

Đánh đổi rất rõ ràng: increment() cực rẻ, sum() phải duyệt cả mảng và không phải ảnh chụp nguyên tử — nếu có luồng đang cộng thì kết quả là một giá trị "gần đúng tại một thời điểm nào đó". Và LongAdder không có compareAndSet, nên không dùng được cho những chỗ cần đọc-rồi-quyết-định.

Nên chọn thế này:

Nhu cầu Dùng
Đếm, cộng dồn, đọc tổng thi thoảng LongAdder
Cần compareAndSet, getAndUpdate, hoặc đọc giá trị hiện tại liên tục AtomicLong
Cần cập nhật nhiều biến cùng lúc một cách nhất quán khoá

Đếm request, đếm lỗi, đếm byte đã xử lý — gần như luôn là LongAdder, và đó là loại biến đếm phổ biến nhất trong ứng dụng thật.

Bài toán ABA

Đây là chỗ CAS có một lỗ hổng mà lập luận trực giác không nhìn ra.

CAS hỏi "giá trị có còn là A không?". Nó không hỏi "giá trị có bị đổi lần nào không?".

  luồng 1 đọc được: A  (rồi bị hoãn)
  luồng 2 đổi A -> B
  luồng 2 đổi B -> A
  luồng 1 tỉnh dậy, CAS(A -> C): true   <- THÀNH CÔNG, dù đã đổi hai lần ở giữa

Luồng 1 tin rằng không có gì xảy ra trong lúc nó ngủ, vì giá trị vẫn là A. Nhưng cả một chuỗi thao tác đã diễn ra và kết thúc ở chỗ trông giống lúc đầu.

Với một biến đếm thì vô hại — 5 vẫn là 5. Vấn đề nằm ở tham chiếu tới đối tượng: nút đầu của một ngăn xếp bị lấy ra, dùng xong, rồi được tái sử dụng và đẩy lại vào đúng vị trí cũ. CAS thấy cùng địa chỉ nên chấp nhận, trong khi cấu trúc bên dưới đã khác hẳn — và bạn có một danh sách liên kết hỏng.

Cách chữa là gắn thêm số phiên bản, đổi câu hỏi thành "có còn là A và vẫn ở phiên bản 0 không?":

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

  luồng 1 đọc: A (tem=0)
  luồng 2: A -> B (tem=1)
  luồng 2: B -> A (tem=2)
  luồng 1 CAS với tem cũ 0: false   <- BỊ TỪ CHỐI, đúng như mong muốn

Số phiên bản chỉ tăng, nên một chu trình quay về giá trị cũ vẫn để lại dấu vết.

Có AtomicMarkableReference cho trường hợp chỉ cần một bit đánh dấu thay vì cả số đếm — hay dùng khi đánh dấu nút đã bị xoá logic.

Thành thật mà nói: nếu bạn đang phải nghĩ về ABA, hãy cân nhắc dùng cấu trúc dữ liệu có sẵn thay vì tự viết. ConcurrentLinkedQueue và ConcurrentHashMap đã xử lý những chuyện này, và chúng được viết bởi những người dành nhiều năm cho đúng việc đó.

Viết vòng lặp CAS mà không phải viết vòng lặp

Từ Java 8, không cần tự gõ do { } while (!compareAndSet(...)) nữa:

s.updateAndGet(String::toUpperCase);
max.accumulateAndGet(v, Math::max);

  XIN CHAO
  giá trị lớn nhất bằng accumulateAndGet: 9

updateAndGet nhận một hàm và tự lo vòng lặp thử lại. accumulateAndGet gộp một giá trị mới vào giá trị cũ theo hàm bạn đưa.

Một điều bắt buộc phải nhớ: hàm truyền vào có thể được gọi nhiều lần khi có tranh chấp. Nên nó phải thuần tuý — không ghi log, không tăng biến đếm, không gọi mạng, không sửa gì bên ngoài. Đặt một System.out.println vào đấy là bạn sẽ thấy nó in ra nhiều hơn số lần cập nhật thật.

Cấu trúc dữ liệu không khoá

Với AtomicReference, dựng được một ngăn xếp không dùng khoá nào:

void day(T v) {
    Nut<T> cu, moi;
    do { cu = dinh.get(); moi = new Nut<>(v, cu); } while (!dinh.compareAndSet(cu, moi));
}

  8 luồng đẩy 10.000 phần tử mỗi luồng -> lấy ra được 80.000

Không mất phần tử nào. Toàn bộ tính đúng đắn nằm ở chỗ: nút mới trỏ vào đỉnh đã đọc được, và phép CAS chỉ thành công nếu đỉnh vẫn đúng là nút đó.

Tôi đưa ví dụ này vì nó cho thấy CAS làm được gì, không phải để bạn chép vào mã sản xuất. Bản trên có đúng lỗ hổng ABA vừa nói, và ConcurrentLinkedDeque đã có sẵn.

Ba câu khi chọn

Chỉ có một biến cần cập nhật nguyên tử? Dùng Atomic*. Nhiều biến phải nhất quán với nhau thì phải khoá — CAS không gộp được hai ô nhớ.

Tranh chấp cao hay thấp? Bảng ở trên là bằng chứng rằng câu trả lời đổi theo mức tranh chấp, và cách duy nhất để biết là đo trên chính tải của bạn.

Chỉ đếm thôi à? Vậy thì LongAdder, gần như không cần cân nhắc gì thêm.

Thử ba mươi giây

Lấy đúng đoạn đếm số lần compareAndSet trả false ở đầu bài, chạy với 1 luồng rồi với số luồng bằng số nhân máy bạn.

Con số thử lại nhảy từ 0 lên hàng triệu. Đó là thứ không hiện ra ở bất kỳ đâu — không trong log, không trong thời gian phản hồi trung bình — nhưng nó là toàn bộ lý do vì sao một biến đếm tưởng chừng vô hại lại trở thành chỗ nghẽn của hệ thống khi tải tăng.

Ngày mai quay lại phía khoá: ReentrantLock và ReadWriteLock — thử khoá có thời hạn để thoát khỏi deadlock, khoá công bằng, và tách khoá đọc khỏi khoá ghi.