Bài 33 của sê-ri mổ xẻ HashMap bên trong. Bài này nói về chuyện xảy ra khi hai luồng cùng chạm vào nó, và về những bộ sưu tập sinh ra để chịu được điều đó.

HashMap hỏng thế nào

Tám luồng, mỗi luồng ghi 20.000 khoá không trùng nhau vào cùng một HashMap:

  lần 1: mong đợi 160.000 khoá -> thực tế  79.040   MẤT 80.960
  lần 2: mong đợi 160.000 khoá -> thực tế 119.516   MẤT 40.484
  lần 3: mong đợi 160.000 khoá -> thực tế 117.299   MẤT 42.701

Một nửa dữ liệu biến mất. Và chú ý ba lần ra ba con số khác nhau — đúng đặc tính điều kiện đua ở bài 68: không hỏng đều đặn, nên không bao giờ tin được vào việc chạy thử.

Nguyên nhân là lúc bảng băm giãn nở: hai luồng cùng thấy bảng đầy, cùng cấp mảng mới, cùng chuyển các mục sang — và một trong hai bản đồ chuyển đó bị ghi đè.

Trên Java 7 còn tệ hơn: giãn nở đồng thời có thể tạo ra vòng lặp trong danh sách liên kết, khiến get() chạy mãi và ăn hết một nhân CPU. Java 8 đổi cách chuyển nên không còn treo, nhưng vẫn mất dữ liệu như trên.

ConcurrentHashMap, cùng phép thử:

  lần 1: 160.000    lần 2: 160.000    lần 3: 160.000

synchronizedMap an toàn, nhưng vẫn không đủ

Collections.synchronizedMap bọc mọi phương thức trong synchronized. Mỗi thao tác đơn lẻ là nguyên tử, và nó thật sự không mất dữ liệu.

Nhưng mẫu mã này thì vẫn sai:

if (!m.containsKey(khoa)) {
    m.put(khoa, taoGiaTri());     // đắt tiền
}

  containsKey rồi put : 20.000 khoá, hàm khởi tạo chạy 20.041 lần  <- CHẠY THỪA 41 lần
  computeIfAbsent     : 20.000 khoá, hàm khởi tạo chạy 20.000 lần  (đúng)

Hai thao tác đều nguyên tử, nhưng khoảng giữa chúng thì không. Hai luồng cùng thấy khoá vắng mặt, cùng gọi taoGiaTri(), cùng ghi vào.

41 lần thừa nghe ít, nhưng nếu taoGiaTri() là mở một kết nối, tải một tệp cấu hình, hay khởi tạo một bộ nhớ đệm thì đó là 41 lần làm việc thừa — và tệ hơn, 41 đối tượng khác nhau được tạo ra trong khi mã của bạn giả định chỉ có một.

Đây là điểm quan trọng nhất của bài. Bọc từng thao tác trong khoá không làm chuỗi thao tác trở nên nguyên tử. Mẫu "kiểm tra rồi hành động" luôn cần một phép nguyên tử duy nhất, hoặc một khoá bao cả hai bước.

ConcurrentHashMap cho sẵn các phép nguyên tử đó:

m.computeIfAbsent(khoa, k -> taoGiaTri());   // tạo đúng một lần
m.merge(tu, 1, Integer::sum);                // đếm
m.putIfAbsent(khoa, gt);                     // trả giá trị cũ nếu đã có
m.replace(khoa, cu, moi);                    // chỉ đổi nếu giá trị hiện tại đúng như mong đợi
m.compute(khoa, (k, v) -> v == null ? 1 : v * 10);

  merge để đếm        : {a=3, b=2, c=1}
  putIfAbsent         : 3 (trả giá trị cũ, không ghi đè)
  replace có điều kiện: true -> b=20

merge là cách gọn nhất để đếm tần suất, và nó nguyên tử — khác hẳn map.put(k, map.get(k)+1).

Bẫy: computeIfAbsent không được gọi lại chính nó

Ghi nhớ kết quả đệ quy là một trong những cách dùng map tự nhiên nhất:

static long fib(ConcurrentHashMap<Integer,Long> c, int n) {
    if (n < 2) return n;
    return c.computeIfAbsent(n, k -> fib(c, k-1) + fib(c, k-2));
}

  IllegalStateException: Recursive update
  số lần ném lỗi: 200/200

Hai trăm lần chạy, hai trăm lần hỏng.

ConcurrentHashMap khoá một phần bảng trong lúc chạy hàm bạn đưa vào, nên nếu hàm ấy lại sửa chính map đó thì có thể tự khoá chính mình. Java 9 thêm phép kiểm để ném lỗi thay vì treo — thà hỏng rõ ràng.

Nghĩa là: hàm truyền vào computeIfAbsent, compute, merge phải ngắn, thuần tuý, và không được chạm vào chính map đó. Với ghi nhớ đệ quy, hãy dùng HashMap thường (nếu một luồng) hoặc tách thành get rồi putIfAbsent.

Vòng lặp trên bộ sưu tập đang bị sửa

  ArrayList        : ConcurrentModificationException
  synchronizedList : ConcurrentModificationException
  HashMap          : ConcurrentModificationException
  CopyOnWriteList  : duyệt xong, còn 4 phần tử
  ConcurrentHashMap: duyệt xong, còn 2 mục

Bộ sưu tập thường dùng iterator hỏng-sớm: nó đếm số lần cấu trúc bị sửa, và ném ngoại lệ ngay khi phát hiện thay đổi. Chú ý synchronizedList cũng ném — bọc khoá không đổi được điều đó, và đây là chỗ người ta hay tưởng nhầm là đã an toàn.

Các bộ sưu tập đồng thời dùng iterator nhất quán yếu: nó không ném lỗi, nhưng chỉ đảm bảo phản ánh trạng thái tại một thời điểm nào đó. Phần tử thêm vào giữa chừng có thể thấy hoặc không.

Hệ quả cần biết: size() của ConcurrentHashMap chỉ là ước lượng khi đang có luồng ghi, và duyệt hai lần có thể ra hai kết quả. Có mappingCount() trả về long cho map rất lớn.

Nếu bạn cần một ảnh chụp nhất quán thật sự, không bộ sưu tập đồng thời nào cho bạn — phải tự khoá.

Tốc độ

Tám luồng, 80% đọc và 20% ghi, một triệu thao tác:

  HashMap + synchronized      : 103 ms
  Collections.synchronizedMap :  58 ms
  ConcurrentHashMap           :  45 ms

ConcurrentHashMap nhanh hơn hơn hai lần, và khoảng cách nới rộng khi thêm luồng.

Lý do nằm ở cách khoá: synchronizedMap có một khoá cho cả map — mọi thao tác xếp hàng. Từ Java 8, ConcurrentHashMap khoá ở mức từng ngăn của bảng băm, nên hai luồng chạm vào hai khoá khác nhau thường không đụng nhau chút nào. Đọc thì thậm chí không cần khoá gì, vì các nút được khai volatile.

Bản Java 7 chia bảng thành 16 mảnh cố định; bản mới mịn hơn nhiều và bỏ luôn tham số concurrencyLevel — nếu bạn thấy nó trong mã cũ thì nó chỉ còn là gợi ý về kích thước ban đầu.

CopyOnWriteArrayList: đọc miễn phí, ghi trả đủ

Nó chép toàn bộ mảng mỗi lần ghi. Đó là toàn bộ thiết kế, và toàn bộ đánh đổi:

  kích thước    1000 lần ghi        so với synchronizedList
  10              0,3 micro giây      2,9 lần chậm hơn
  100             0,2 micro giây      6,4 lần chậm hơn
  1.000           0,8 micro giây     31,5 lần chậm hơn
  10.000         11,5 micro giây    260,3 lần chậm hơn

Chi phí ghi tăng tuyến tính theo kích thước danh sách, nên thêm n phần tử vào một danh sách rỗng là O(n²).

Đổi lại, đọc không khoá gì cả. Bảng dưới đo 8 luồng với các tỷ lệ ghi khác nhau:

  tỷ lệ ghi     CopyOnWrite   synchronizedList
  0,0%              43 ms          43 ms
  0,1%              34 ms          48 ms   <- COW thắng
  1,0%              23 ms          24 ms   <- hoà
  10,0%           1349 ms          38 ms   <- COW thua 35 lần

Ranh giới nằm quanh 1% ghi. Dưới ngưỡng đó thì CopyOnWriteArrayList có lợi; trên ngưỡng đó nó sụp rất nhanh.

Chỗ nó đúng là những danh sách gần như chỉ đọc: danh sách listener đăng ký lúc khởi động, bảng cấu hình nạp một lần rồi thi thoảng nạp lại, danh sách trắng địa chỉ IP. Đặc điểm chung: ghi vài lần trong cả vòng đời ứng dụng, đọc hàng triệu lần.

Chỗ nó sai là mọi hàng đợi, mọi bộ đệm, mọi danh sách tích luỹ dữ liệu. Với những thứ đó dùng ConcurrentLinkedQueue hoặc BlockingQueue ở bài 73.

Bảng chọn

Cần Dùng
Map đa luồng ConcurrentHashMap
Map có thứ tự, đa luồng ConcurrentSkipListMap
Set đa luồng ConcurrentHashMap.newKeySet()
Danh sách gần như chỉ đọc CopyOnWriteArrayList
Hàng đợi giữa các luồng ArrayBlockingQueue / LinkedBlockingQueue có giới hạn
Hàng đợi không chặn ConcurrentLinkedQueue
Dữ liệu không đổi sau khi tạo List.of / Map.of — bất biến thì an toàn sẵn

Dòng cuối là lời khuyên tôi muốn nhấn mạnh: cách rẻ nhất để an toàn luồng là không có trạng thái thay đổi được. List.of(...) không cần khoá, không cần chép, không có cái bẫy nào trong bài này.

Và Collections.synchronizedMap thì gần như không còn lý do tồn tại trong mã mới — nó vừa chậm hơn, vừa không cho phép ghép thao tác nguyên tử, vừa vẫn ném ConcurrentModificationException khi duyệt.

Thử ba mươi giây

Tìm trong dự án của bạn mẫu if (!map.containsKey(k)) map.put(k, ...) hoặc if (map.get(k) == null) ....

Mỗi chỗ như vậy là một điều kiện đua, kể cả khi map đã được bọc synchronizedMap. Đổi sang computeIfAbsent là sửa một dòng — và nếu phần khởi tạo có tác dụng phụ, bạn vừa chặn được một lỗi rất khó tái hiện.

Ngày mai: ThreadLocal — dùng nó để làm gì, và vì sao quên gọi remove() trong môi trường có pool luồng là một kiểu rò rỉ bộ nhớ rất khó lần ra.