Bỏ qua nội dung chính

Tổng hợp các container concurrent thường gặp trong Java

GuideJavaJava ConcurrencyKhoảng 2878 từKhoảng 10 phút

Phần lớn các container do JDK cung cấp nằm trong package java.util.concurrent.

  • ConcurrentHashMap : HashMap thread-safe
  • CopyOnWriteArrayList : List thread-safe, performance rất tốt khi đọc nhiều, ghi ít, tốt hơn Vector rất nhiều.
  • ConcurrentLinkedQueue : concurrent queue hiệu quả, được triển khai bằng linked list. Có thể xem đây là LinkedList thread-safe; đây là một non-blocking queue.
  • BlockingQueue : Đây là một interface; JDK triển khai nó bằng linked list, array và các cách khác. Đây là blocking queue, rất phù hợp để làm kênh chia sẻ dữ liệu.
  • ConcurrentSkipListMap : Bản triển khai của skip list. Đây là một Map sử dụng cấu trúc dữ liệu skip list để tìm kiếm nhanh.

ConcurrentHashMap

HashMap không thread-safe. Nếu sử dụng trong môi trường concurrent, một cách thường gặp là dùng phương thức Collections.synchronizedMap() để bọc HashMap, biến nó thành thread-safe. Tuy nhiên, cách này đồng bộ các truy cập concurrent giữa các thread bằng một global lock, gây bottleneck nghiêm trọng về performance, đặc biệt trong môi trường high concurrency.

Để giải quyết vấn đề này, ConcurrentHashMap ra đời. Đây là phiên bản thread-safe của HashMap, cung cấp khả năng xử lý concurrent hiệu quả hơn.

Trong JDK1.7, ConcurrentHashMap chia bucket array thành các segment (Segment, segmented lock). Mỗi lock chỉ khóa một phần dữ liệu trong container (như hình minh họa bên dưới). Khi nhiều thread truy cập dữ liệu thuộc các segment khác nhau trong container, sẽ không xảy ra lock contention, nhờ đó tăng khả năng truy cập concurrent.

Cấu trúc lưu trữ ConcurrentHashMap trong Java 7

Đến JDK1.8, ConcurrentHashMap loại bỏ segmented lock Segment, sử dụng Node + CAS + synchronized để đảm bảo thread-safe. Cấu trúc dữ liệu tương tự cấu trúc của HashMap 1.8: array + linked list/red-black tree. Trong Java 8, khi độ dài linked list vượt quá ngưỡng nhất định (8), linked list (độ phức tạp tìm kiếm là O(N)) được chuyển thành red-black tree (độ phức tạp tìm kiếm là O(log(N))).

Trong Java 8, phạm vi lock của thao tác update nhỏ hơn: khi cần lock, synchronized khóa node đầu của bucket tương ứng; các thao tác update trên các bucket khác nhau thường có thể thực hiện concurrent. Thao tác read thường không cần lock và cũng có thể thực hiện concurrent với thao tác update.

Cấu trúc lưu trữ ConcurrentHashMap trong Java 8

Để xem phần giới thiệu chi tiết về ConcurrentHashMap, hãy đọc bài viết: Phân tích source code ConcurrentHashMap.

CopyOnWriteArrayList

Trước khi CopyOnWriteArrayList được đưa vào JDK 1.5, ngoài Vector ra đời khá sớm, cũng có thể bọc List thông thường bằng Collections.synchronizedList() để có khả năng truy cập đồng bộ. Các phương thức thêm, xóa, sửa, tìm kiếm của Vector về cơ bản đều có synchronized; một lần gọi phương thức đơn lẻ có tính thread-safe, nhưng các thao tác kết hợp vẫn cần đồng bộ thêm.

JDK1.5 đưa package Java.util.concurrent (JUC) vào, trong đó cung cấp nhiều container thread-safe có performance concurrent tốt. Implementation List thread-safe duy nhất là CopyOnWriteArrayList.

Trong phần lớn trường hợp sử dụng, số lần read thường lớn hơn rất nhiều số lần write. Vì thao tác read không sửa dữ liệu hiện có, việc lock cho mỗi lần read thực chất là lãng phí tài nguyên. Ngược lại, nên cho phép nhiều thread cùng truy cập dữ liệu bên trong List, vì điều này an toàn đối với thao tác read.

Tư tưởng này rất tương tự thiết kế của read-write lock ReentrantReadWriteLock: read-read không loại trừ lẫn nhau, read-write loại trừ lẫn nhau, write-write loại trừ lẫn nhau (chỉ read-read không loại trừ lẫn nhau). CopyOnWriteArrayList hiện thực tư tưởng này ở mức cao hơn. Để tối ưu performance của thao tác read, các thao tác read trong CopyOnWriteArrayList hoàn toàn không cần lock. Đặc biệt, thao tác write cũng không block thao tác read, chỉ write-write loại trừ lẫn nhau. Nhờ vậy, performance của thao tác read có thể được nâng cao đáng kể.

Điểm cốt lõi giúp CopyOnWriteArrayList thread-safe là nó sử dụng cơ chế copy-on-write, thể hiện ngay trong tên CopyOnWriteArrayList.

Khi cần sửa nội dung của CopyOnWriteArrayList (các thao tác như add, set, remove), không sửa trực tiếp array ban đầu mà trước tiên tạo một bản sao của array bên dưới, sửa trên array bản sao, sau khi sửa xong mới gán array đã sửa trở lại. Nhờ vậy, thao tác write không ảnh hưởng đến thao tác read.

Để xem phần giới thiệu chi tiết về CopyOnWriteArrayList, hãy đọc bài viết: Phân tích source code CopyOnWriteArrayList.

ConcurrentLinkedQueue

Queue thread-safe do Java cung cấp có thể chia thành blocking queue và non-blocking queue. Ví dụ điển hình của blocking queue là BlockingQueue, còn ví dụ điển hình của non-blocking queue là ConcurrentLinkedQueue. Trong ứng dụng thực tế, cần chọn blocking queue hoặc non-blocking queue tùy nhu cầu. Blocking queue có thể được triển khai bằng lock, còn non-blocking queue có thể được triển khai bằng thao tác CAS.

Nhìn từ tên có thể thấy queue ConcurrentLinkedQueue sử dụng linked list làm cấu trúc dữ liệu. ConcurrentLinkedQueue có thể xem là queue có performance tốt nhất trong môi trường high concurrency. Sở dĩ nó có performance tốt là nhờ cách triển khai bên trong phức tạp.

Không phân tích source code bên trong ConcurrentLinkedQueue ở đây; chỉ cần biết ConcurrentLinkedQueue chủ yếu sử dụng thuật toán non-blocking dựa trên CAS để đảm bảo thread-safe.

ConcurrentLinkedQueue phù hợp với trường hợp yêu cầu performance tương đối cao, đồng thời có nhiều thread cùng đọc và ghi queue. Nói cách khác, nếu chi phí lock queue cao thì phù hợp dùng ConcurrentLinkedQueue không lock để thay thế.

BlockingQueue

Giới thiệu về BlockingQueue

Ở trên đã đề cập ConcurrentLinkedQueue là non-blocking queue có performance cao. Tiếp theo là blocking queue BlockingQueue. Blocking queue (BlockingQueue) được sử dụng rộng rãi trong bài toán “producer-consumer”, vì BlockingQueue cung cấp các phương thức insert và remove có thể block. Khi queue container đầy, producer thread sẽ bị block cho đến khi queue không còn đầy; khi queue container rỗng, consumer thread sẽ bị block cho đến khi queue không còn rỗng.

BlockingQueue là một interface kế thừa từ Queue, vì vậy các class triển khai nó cũng có thể được sử dụng như implementation của Queue; còn Queue lại kế thừa interface Collection. Dưới đây là các class triển khai liên quan của BlockingQueue:

Các class triển khai của BlockingQueue

Sau đây giới thiệu 3 class triển khai BlockingQueue thường gặp: ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue.

ArrayBlockingQueue

ArrayBlockingQueue là class triển khai bounded queue cho interface BlockingQueue, bên dưới sử dụng array.

public class ArrayBlockingQueue<E>
extends AbstractQueue<E>
implements BlockingQueue<E>, Serializable{}

Sau khi được tạo, capacity của ArrayBlockingQueue không thể thay đổi. Cơ chế kiểm soát concurrent sử dụng reentrant lock ReentrantLock; cả thao tác insert và read đều phải acquire lock mới có thể thực hiện. Khi queue đầy, việc thử đưa element vào queue sẽ khiến thao tác bị block; việc thử lấy một element từ queue rỗng cũng block tương tự.

Theo mặc định, ArrayBlockingQueue không đảm bảo fairness cho các thread đang chờ truy cập queue. Sau khi bật fair strategy, khi xảy ra contention, queue sẽ cấp cơ hội truy cập cho producer hoặc consumer đang chờ theo thứ tự FIFO. Điều này chỉ mô tả thứ tự chờ trong queue, không đồng nghĩa với việc OS strict schedule thread theo thời gian thực. Ở non-fair mode, thread bị block trong thời gian dài vẫn có thể không truy cập queue kịp thời. Fair strategy thường làm giảm throughput. Nếu cần, có thể dùng code sau:

private static ArrayBlockingQueue<Integer> blockingQueue = new ArrayBlockingQueue<Integer>(10,true);

LinkedBlockingQueue

LinkedBlockingQueue là blocking queue được triển khai bên dưới dựa trên singly linked list. Có thể dùng nó như unbounded queue hoặc bounded queue, đồng thời đáp ứng đặc tính FIFO. So với ArrayBlockingQueue, nó có throughput cao hơn. Để tránh capacity của LinkedBlockingQueue tăng nhanh và tiêu tốn nhiều memory, khi tạo object LinkedBlockingQueue thường nên chỉ định capacity. Nếu không chỉ định, capacity bằng Integer.MAX_VALUE.

Các constructor liên quan:

    /**
      * Unbounded queue theo một nghĩa nhất định
     * Creates a {@code LinkedBlockingQueue} with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    public LinkedBlockingQueue() {
        this(Integer.MAX_VALUE);
    }

    /**
     * Bounded queue
     * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity.
     *
     * @param capacity the capacity of this queue
     * @throws IllegalArgumentException if {@code capacity} is not greater
     *         than zero
     */
    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node<E>(null);
    }

PriorityBlockingQueue

PriorityBlockingQueue là unbounded blocking queue có hỗ trợ priority. Theo mặc định, element được sort theo natural order. Ngoài ra, có thể chỉ định quy tắc sort bằng cách tự triển khai phương thức compareTo() trong class, hoặc chỉ định Comparator thông qua constructor khi khởi tạo.

Cơ chế kiểm soát concurrent của PriorityBlockingQueue sử dụng reentrant lock ReentrantLock. Queue là unbounded queue (ArrayBlockingQueue là bounded queue; LinkedBlockingQueue cũng có thể chỉ định capacity tối đa của queue bằng cách truyền capacity vào constructor, nhưng PriorityBlockingQueue chỉ có thể chỉ định initial queue size; về sau khi insert element, nếu không đủ space thì queue sẽ tự động mở rộng).

Nói đơn giản, đây là phiên bản thread-safe của PriorityQueue. Không thể insert giá trị null; đồng thời object được insert vào queue phải có thể so sánh với nhau (comparable), nếu không sẽ báo exception ClassCastException. Thao tác insert put của nó không block vì đây là unbounded queue (thao tác take sẽ block khi queue rỗng).

Bài viết đề xuất: Đọc hiểu Java concurrent queue BlockingQueue

ConcurrentSkipListMap

Phần nội dung dưới đây tham khảo chuyên mục Vẻ đẹp của cấu trúc dữ liệu và thuật toán của Geek Time, cùng sách Thiết kế chương trình Java high concurrency trong thực tế.

Để giới thiệu ConcurrentSkipListMap, trước tiên tìm hiểu sơ lược về skip list.

Với một singly linked list, ngay cả khi đã được sort, muốn tìm một element cũng chỉ có thể duyệt từ đầu đến cuối, nên performance rất thấp. Skip list thì khác: đây là cấu trúc dữ liệu hỗ trợ tìm kiếm nhanh, khá giống balanced tree. Cả hai đều có thể tìm kiếm element nhanh. Tuy nhiên, điểm khác biệt quan trọng là insert và delete trên balanced tree thường có thể khiến toàn bộ tree phải điều chỉnh, còn trên skip list chỉ cần thao tác trên một phần của cấu trúc dữ liệu. Vì vậy, trong high concurrency, cần global lock để đảm bảo thread-safe cho toàn bộ balanced tree, trong khi skip list chỉ cần partial lock. Nhờ đó, skip list có performance tốt hơn trong môi trường high concurrency. Về query, time complexity của skip list cũng là O(logn), nên JDK dùng skip list để triển khai một Map trong concurrent data structure.

Bản chất của skip list là duy trì đồng thời nhiều linked list được phân tầng.

Skip list với index cấp 2

Linked list ở tầng thấp nhất duy trì toàn bộ element trong skip list; linked list ở mỗi tầng phía trên là một subset của tầng bên dưới.

Các element trong mọi linked list của skip list đều được sort. Khi tìm kiếm, có thể bắt đầu từ linked list cấp cao nhất. Khi phát hiện element cần tìm nhỏ hơn successor của node đang truy cập (hoặc successor là null), quá trình sẽ chuyển xuống linked list ở tầng tiếp theo để tiếp tục tìm. Điều này có nghĩa là trong quá trình tìm kiếm, việc search được thực hiện theo kiểu nhảy qua các node. Như hình trên minh họa, hãy tìm element 18 trong skip list.

Tìm element 18 trong skip list

Khi tìm 18, trước đây cần duyệt 18 lần, còn hiện tại chỉ cần 7 lần. Khi độ dài linked list tương đối lớn, việc xây dựng index giúp nâng cao rõ rệt performance tìm kiếm.

Từ những điều trên có thể dễ dàng thấy rằng, skip list là một thuật toán dùng space để đổi lấy time.

Một điểm khác giữa việc sử dụng skip list để triển khai Map và sử dụng hash algorithm để triển khai Map là: hash không lưu thứ tự của element, còn toàn bộ element trong skip list đều được sort. Vì vậy, khi duyệt skip list, sẽ nhận được kết quả có thứ tự. Do đó, nếu ứng dụng cần thứ tự thì skip list là lựa chọn phù hợp nhất. Class triển khai cấu trúc dữ liệu này trong JDK là ConcurrentSkipListMap.

Tham khảo

Lời cuối

Nếu nội dung hữu ích với bạn, hãy tiện tay tặng JavaGuide một Star miễn phí để ủng hộ: GitHub | Gitee.

JavaGuide đã được duy trì gần bảy năm, tích lũy 6100+ commit, với sự chung tay hoàn thiện của 620+ contributor. Star, phản hồi và PR của bạn đều là động lực để dự án tiếp tục cập nhật.

Nếu bạn đang chuẩn bị phỏng vấn backend / phát triển ứng dụng AI, có thể tham khảo Knowledge Planet của tôi, bao gồm các project thực tế về backend và AI, tối ưu CV, hỏi đáp 1-1 và tài liệu về các trọng điểm thường gặp, đã được duy trì liên tục sáu năm.