Hình dung hai người ở chung nhà. Cả hai mở tủ lạnh, thấy hết sữa, cả hai đi siêu thị — và tối về nhà có hai hộp sữa. Không ai làm sai cả: mỗi người "kiểm tra rồi hành động" đúng quy trình. Cái sai nằm ở khoảng trống giữa lúc kiểm tra và lúc hành động, khoảng mà người kia chen vào được. Gần như mọi lỗi của bộ sưu tập đa luồng đều là biến thể của hai hộp sữa ấy, và bài này đo từng biến thể. 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 — đúng hai hộp sữa.

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

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.

Mẫu số chung

Cả cái bảng chọn ở trên gói một sự thật mà nhiều người bỏ qua: không có "bộ sưu tập an toàn luồng" theo nghĩa phổ quát. An toàn luôn được mua bằng một loại tiền tệ khác nhau — một khoá lớn (mọi thao tác xếp hàng), khoá chia ngăn (chỉ đụng nhau khi trùng ngăn), chép-khi-ghi (đọc miễn phí, ghi trả cả mảng) — và loại nào đáng chọn phụ thuộc vào hình dạng tải: tỷ lệ đọc trên ghi. Cái ngưỡng 1% của CopyOnWriteArrayList chính là điều đó hiện ra thành con số. Hỏi "cấu trúc này có an toàn luồng không" là hỏi sai; câu đúng là "nó tối ưu cho tải đọc-nhiều hay ghi-nhiều".

Đổi ngăn xếp, cùng bài toán:

  • Go có sync.Map được thiết kế riêng cho tải đọc-nhiều/chỉ-thêm (hai kho, gần như chép-khi-ghi), và tài liệu nói thẳng nó chỉ hơn một map bọc sync.RWMutex ở đúng vài kiểu truy cập — ngoài ra thì không. Cùng "an toàn có hình dạng". Và triết lý gốc của Go né hẳn vấn đề: "chia sẻ bộ nhớ bằng cách giao tiếp" — dùng channel chuyển quyền sở hữu thay vì nhiều luồng cùng ghi một chỗ.
  • Và có một hướng xoá sạch cả lớp bẫy này: bất biến. Cấu trúc bền vững của Clojure (chia sẻ cấu trúc, an toàn luồng sẵn), mô hình không-chia-sẻ-trạng-thái của Erlang, và quyền sở hữu của Rust biến chính data race thành lỗi biên dịch. Không có trạng thái thay đổi được thì không có gì để bảo vệ.

Nên câu hỏi đúng khi nhiều luồng cùng chạm một cấu trúc không phải "chọn bộ sưu tập an toàn nào" mà là, theo thứ tự: "tôi có thể làm nó bất biến không" (rẻ nhất, dùng List.of/Map.of), nếu không thì "tải của tôi đọc-nhiều hay ghi-nhiều" để chọn đúng loại tiền tệ. Cách rẻ nhất để an toàn luồng vẫn luôn là không có trạng thái thay đổi được.

Muốn bắt lỗi ngay hôm nay: tìm trong dự á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 — đúng hai hộp sữa — 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.