Hàng đợi chặn Java nào hiệu quả nhất cho các kịch bản một người tiêu dùng sản xuất đơn

Question

Tôi đang làm việc trên một hệ thống Java chuẩn với các yêu cầu thời gian quan trọng cho các nhà sản xuất của tôi (1/100s ms).

Tôi có một nhà sản xuất đặt nội dung trong hàng đợi chặn và một người tiêu dùng duy nhất sau đó chọn công cụ đó và bán nó vào một tệp. Khối người tiêu dùng khi dữ liệu không có sẵn.

Rõ ràng, hàng đợi chặn là giao diện thích hợp, nhưng nên triển khai thực hiện thực tế nào nếu tôi muốn giảm thiểu chi phí cho nhà sản xuất? Tôi muốn chơi càng ít càng tốt vào những thứ như khóa và phân bổ khi tôi đặt hàng trong hàng đợi, và tôi không ngại nếu người tiêu dùng phải đợi lâu hơn hoặc làm việc chăm chỉ hơn nhiều.

Có triển khai nào có thể nhanh hơn vì tôi chỉ có một người tiêu dùng và một nhà sản xuất duy nhất không?

Answer 1

Vâng, thực sự không có quá nhiều tùy chọn. Hãy để tôi xem qua số listed subclasses:

DelayQueue, LinkedBlockingDeque, PriorityBlockingQueue và SynchronousQueue đều được thực hiện cho các trường hợp đặc biệt yêu cầu chức năng bổ sung; chúng không có ý nghĩa trong kịch bản này.

Chỉ để lại ArrayBlockingQueue và LinkedBlockingQueue. Nếu bạn biết làm thế nào để biết liệu bạn có cần ArrayList hoặc LinkedList, bạn có thể tự mình trả lời câu hỏi này.

Lưu ý rằng trong LinkedBlockingQueue, "các nút được liên kết được tạo động trên mỗi lần chèn"; điều này có thể có xu hướng đẩy bạn về phía ArrayBlockingQueue.

Answer 2

Nếu yêu cầu về thời gian rất chặt chẽ, có thể bạn sẽ cần phải thực hiện đo điểm chuẩn trên cùng một phần cứng để xác định mức độ phù hợp nhất.

Nếu tôi đoán, tôi sẽ đi với ArrayBlockingQueue vì các bộ sưu tập dựa trên mảng có khuynh hướng có địa điểm tham chiếu tốt đẹp.

Answer 3

LinkedBlockingQueue sẽ có O (1) chi phí chèn trừ khi có sự chậm trễ cấp phát bộ nhớ. Một ArrayBlockingQueue rất lớn sẽ có chi phí chèn O (1) trừ khi hệ thống bị chặn do thu gom rác thải; nó sẽ, tuy nhiên, chặn trên chèn khi ở công suất.

Ngay cả khi thu thập rác đồng thời, tôi không chắc liệu bạn có nên viết hệ thống thời gian thực bằng ngôn ngữ được quản lý hay không.

Answer 4

ArrayBlockingQueue có thể sẽ nhanh hơn khi bạn không cần phải tạo các nút liên kết khi chèn. Lưu ý, tuy nhiên, ArrayBlockingQueue có độ dài cố định, nếu bạn muốn hàng đợi của bạn phát triển tùy ý lớn (ít nhất là Integer.MAX_INT), bạn sẽ phải sử dụng một LinkedBlockingQueue (trừ khi bạn muốn cấp phát một mảng các phần tử Integer.MAX_INT) .

Answer 5

Tôi đồng ý với nhận xét của Andrew Duffy rằng việc triển khai hệ thống hạn chế thời gian trong java có thể là một sai lầm. Bất kể, giả sử bạn đã kết hôn với JVM và bạn không mong đợi hàng đợi này đang chạy đầy đủ (nghĩa là người tiêu dùng có thể xử lý tải), tôi nghĩ bạn có thể được phục vụ tốt nhất bằng cách triển khai tùy chỉnh, tương tự như một ArrayBlockingQueue nhưng được cắt bớt/tối ưu hóa cho kịch bản sản xuất/người tiêu dùng đơn lẻ. Đặc biệt, tôi thích ý niệm quay về phía nhà sản xuất để chờ không gian, thay vì chặn.

Tôi đã đề cập đến java.đồng thời sources để được hướng dẫn, và soạn thảo thuật toán này ...

Có vẻ khá tốt với tôi, nhưng nó hoàn toàn chưa được kiểm tra và có thể không nhanh hơn trong thực tế (có thể không phải là cách mạng, nhưng tôi đã tự quây mình ra:). Tôi đã vui vẻ với nó, dù sao ... Bạn có thể tìm thấy một lỗ hổng?

Mã giả:

private final ReentrantLock takeLock = new ReentrantLock(); 
private final Condition notEmpty = takeLock.newCondition(); 
private final E[] buffer; 
private int head = 0 
private int tail = 0; 

public void put(E e) { 
    if (e == null) throw NullPointerException(); 

    while (buffer[tail] != null) { 
    // spin, wait for space... hurry up, consumer! 
    // open Q: would a tight/empty loop be superior here? 
    Thread.sleep(1); 
    } 

    buffer[tail] = e; 
    tail = (tail + 1) % buffer.length; 

    if (count.getAndIncrement() == 0) { 
    sync(takeLock) { // this is pseudocode -- should be lock/try/finally/unlock 
     notEmpty.signal(); 
    } 
    } 
} 

public E take() { 
    sync(takeLock) { 
    while (count.get() == 0) notEmpty.await(); 
    } 
    E item = buffer[head]; 
    buffer[head] = null; 
    count.decrement(); 
    head = (head + 1) % buffer.length; 

    return item; 
} 

Answer 6

Bạn có thể viết một hệ thống nhạy cảm độ trễ trong Java nhưng bạn phải cẩn thận phân bổ bộ nhớ, thông tin truyền giữa chủ đề và khóa. Bạn nên viết một số thử nghiệm đơn giản để xem thời gian những thứ này có giá trị như thế nào trên máy chủ của bạn. (Chúng khác nhau dựa trên hệ điều hành và kiến ​​trúc bộ nhớ)

Nếu bạn làm điều này, bạn có thể nhận được thời gian ổn định cho các hoạt động lên đến 99,99% thời gian. Đây không phải là thời gian thực thích hợp, nhưng nó có thể đủ gần. Trên một hệ thống giao dịch, sử dụng Java thay vì C chi phí có thể có giá £ 100/d, tuy nhiên chi phí phát triển trong C/C++ hơn là Java có khả năng cao hơn nhiều so với điều này. ví dụ. về tính linh hoạt nó mang lại cho chúng ta và số lượng lỗi mà nó tiết kiệm được.

Bạn có thể nhận được khá gần cùng một số lượng jitter bạn sẽ thấy trong một chương trình C làm điều tương tự. Một số người gọi đây là "C-like" Java.

Thật không may, nó mất khoảng 8 micro giây để truyền một đối tượng giữa các luồng trong Java thông qua một ArrayBlockingQueue trên các máy chủ mà tôi làm việc và tôi đề nghị bạn thử nghiệm trên máy chủ của bạn. Một thử nghiệm đơn giản là truyền System.nanoTime() giữa các luồng và xem mất bao lâu.

ArrayBlockingQueue có một "tính năng" nơi nó tạo đối tượng trên mỗi phần tử được thêm vào (mặc dù không có nhiều lý do để làm như vậy) Vì vậy, nếu bạn tìm thấy một triển khai chuẩn không thực hiện việc này, hãy cho tôi biết .

Answer 7

Bạn có thể xem xét sử dụng LinkedTransferQueue, triển khai "Hàng đợi kép với Slack" và phù hợp tốt với Nhà sản xuất và Người tiêu dùng. Xem phần sau để biết thêm chi tiết Java 7 TransferQueue, Dual Synchronous Queues (.pdf) và LinkedTransferQueue source