Triển khai Ring Buffer trong Java

1. Khái quát chung

Trong hướng dẫn này, chúng ta sẽ học cách triển khai Ring Buffer trong Java.

2. Vòng đệm

Bộ đệm vòng (hoặc Bộ đệm tròn) là một cấu trúc dữ liệu hình tròn có giới hạn được sử dụng để đệm dữ liệu giữa hai hoặc nhiều luồng . Khi chúng ta tiếp tục ghi vào bộ đệm vòng, nó sẽ quấn quanh khi đến cuối.

2.1. Làm thế nào nó hoạt động

Ring Buffer được thực hiện bằng cách sử dụng một mảng có kích thước cố định bao quanh các ranh giới .

Ngoài mảng, nó theo dõi ba thứ:

  • khe có sẵn tiếp theo trong bộ đệm để chèn một phần tử,
  • phần tử chưa đọc tiếp theo trong bộ đệm,
  • và cuối mảng - điểm mà bộ đệm bao quanh đầu mảng

Cơ chế của cách bộ đệm vòng xử lý các yêu cầu này thay đổi tùy theo việc triển khai. Ví dụ, mục nhập Wikipedia về chủ đề này hiển thị một phương pháp sử dụng bốn con trỏ.

Chúng tôi sẽ mượn cách tiếp cận từ việc triển khai bộ đệm vòng của Disruptor bằng cách sử dụng các chuỗi.

Điều đầu tiên chúng ta cần biết là dung lượng - kích thước tối đa cố định của bộ đệm. Tiếp theo, chúng tôi sẽ sử dụng hai trình tự tăng đơn điệu :

  • Viết trình tự: bắt đầu từ -1, tăng dần 1 khi chúng tôi chèn một phần tử
  • Đọc trình tự: bắt đầu từ 0, tăng dần 1 khi chúng ta sử dụng một phần tử

Chúng ta có thể ánh xạ một chuỗi thành một chỉ mục trong mảng bằng cách sử dụng thao tác mod:

arrayIndex = sequence % capacity 

Các hoạt động mod kết thúc tốt đẹp các chuỗi xung quanh ranh giới để lấy được một khe trong bộ đệm :

Hãy xem cách chúng tôi sẽ chèn một phần tử:

buffer[++writeSequence % capacity] = element 

Chúng tôi đang tăng trước trình tự trước khi chèn một phần tử.

Để sử dụng một phần tử, chúng tôi thực hiện tăng sau:

element = buffer[readSequence++ % capacity] 

Trong trường hợp này, chúng tôi thực hiện tăng sau trên chuỗi. Việc sử dụng một phần tử không xóa nó khỏi bộ đệm - nó chỉ ở trong mảng cho đến khi bị ghi đè .

2.2. Bộ đệm trống và đầy đủ

Khi chúng ta quấn quanh mảng, chúng ta sẽ bắt đầu ghi đè dữ liệu trong bộ đệm. Nếu bộ đệm đầy, chúng ta có thể chọn ghi đè lên dữ liệu cũ nhất bất kể trình đọc đã sử dụng hoặc ngăn ghi đè lên dữ liệu chưa được đọc .

Nếu người đọc có thể bỏ sót các giá trị trung gian hoặc giá trị cũ (ví dụ: mã giá chứng khoán), chúng tôi có thể ghi đè dữ liệu mà không cần đợi nó được tiêu thụ. Mặt khác, nếu người đọc phải sử dụng tất cả các giá trị (như với các giao dịch thương mại điện tử), chúng ta nên đợi (khối / bận-chờ) cho đến khi bộ đệm có sẵn một chỗ trống.

Bộ đệm đầy nếu kích thước của bộ đệm bằng với dung lượng của nó , trong đó kích thước của nó bằng số phần tử chưa đọc:

size = (writeSequence - readSequence) + 1 isFull = (size == capacity) 

Nếu trình tự ghi chậm hơn trình tự đọc, bộ đệm trống :

isEmpty = writeSequence < readSequence 

Bộ đệm trả về giá trị null nếu nó trống.

2.2. Ưu điểm và nhược điểm

Bộ đệm vòng là bộ đệm FIFO hiệu quả. Nó sử dụng một mảng kích thước cố định có thể được cấp phát trước và cho phép một kiểu truy cập bộ nhớ hiệu quả. Tất cả các hoạt động bộ đệm là thời gian không đổi O (1) , bao gồm cả việc sử dụng một phần tử, vì nó không yêu cầu dịch chuyển các phần tử.

Mặt khác, việc xác định kích thước chính xác của bộ đệm vòng là rất quan trọng. Ví dụ, các hoạt động ghi có thể bị chặn trong một thời gian dài nếu bộ đệm có kích thước nhỏ hơn và đọc chậm. Chúng tôi có thể sử dụng định cỡ động, nhưng nó sẽ yêu cầu dữ liệu di chuyển xung quanh và chúng tôi sẽ bỏ lỡ hầu hết các lợi thế được thảo luận ở trên.

3. Triển khai trong Java

Bây giờ chúng ta đã hiểu cách thức hoạt động của bộ đệm vòng, hãy tiến hành triển khai nó trong Java.

3.1. Khởi tạo

Đầu tiên, hãy xác định một phương thức khởi tạo khởi tạo bộ đệm với dung lượng được xác định trước:

public CircularBuffer(int capacity) { this.capacity = capacity; this.data = (E[]) new Object[capacity]; this.readSequence = 0; this.writeSequence = -1; } 

Thao tác này sẽ tạo một bộ đệm trống và khởi tạo các trường trình tự như đã thảo luận trong phần trước.

3.3. Phục vụ

Tiếp theo, chúng tôi sẽ triển khai hoạt động cung cấp chèn một phần tử vào bộ đệm tại vị trí khả dụng tiếp theo và trả về true khi thành công. Nó trả về false nếu bộ đệm không thể tìm thấy vị trí trống, nghĩa là chúng ta không thể ghi đè các giá trị chưa đọc .

Hãy triển khai phương thức cung cấp trong Java:

public boolean offer(E element) { boolean isFull = (writeSequence - readSequence) + 1 == capacity; if (!isFull) { int nextWriteSeq = writeSequence + 1; data[nextWriteSeq % capacity] = element; writeSequence++; return true; } return false; } 

Vì vậy, chúng tôi đang tăng trình tự ghi và tính toán chỉ mục trong mảng cho vị trí có sẵn tiếp theo. Sau đó, chúng tôi đang ghi dữ liệu vào bộ đệm và lưu trữ trình tự ghi được cập nhật.

Hãy thử nó ra:

@Test public void givenCircularBuffer_whenAnElementIsEnqueued_thenSizeIsOne() { CircularBuffer buffer = new CircularBuffer(defaultCapacity); assertTrue(buffer.offer("Square")); assertEquals(1, buffer.size()); } 

3.4. Poll

Finally, we'll implement the poll operation that retrieves and removes the next unread element. The poll operation doesn't remove the element but increments the read sequence.

Let's implement it:

public E poll() { boolean isEmpty = writeSequence < readSequence; if (!isEmpty) { E nextValue = data[readSequence % capacity]; readSequence++; return nextValue; } return null; } 

Here, we're reading the data at the current read sequence by computing the index in the array. Then, we're incrementing the sequence and returning the value, if the buffer is not empty.

Let's test it out:

@Test public void givenCircularBuffer_whenAnElementIsDequeued_thenElementMatchesEnqueuedElement() { CircularBuffer buffer = new CircularBuffer(defaultCapacity); buffer.offer("Triangle"); String shape = buffer.poll(); assertEquals("Triangle", shape); } 

4. Producer-Consumer Problem

We've talked about the use of a ring buffer for exchanging data between two or more threads, which is an example of a synchronization problem called the Producer-Consumer problem. In Java, we can solve the producer-consumer problem in various ways using semaphores, bounded queues, ring buffers, etc.

Let's implement a solution based on a ring buffer.

4.1. volatile Sequence Fields

Our implementation of the ring buffer is not thread-safe. Let's make it thread-safe for the simple single-producer and single-consumer case.

The producer writes data to the buffer and increments the writeSequence, while the consumer only reads from the buffer and increments the readSequence. So, the backing array is contention-free and we can get away without any synchronization.

But we still need to ensure that the consumer can see the latest value of the writeSequence field (visibility) and that the writeSequence is not updated before the data is actually available in the buffer (ordering).

We can make the ring buffer concurrent and lock-free in this case by making the sequence fields volatile:

private volatile int writeSequence = -1, readSequence = 0; 

In the offer method, a write to the volatile field writeSequence guarantees that the writes to the buffer happen before updating the sequence. At the same time, the volatile visibility guarantee ensures that the consumer will always see the latest value of writeSequence.

4.2. Producer

Let's implement a simple producer Runnable that writes to the ring buffer:

public void run() { for (int i = 0; i < items.length;) { if (buffer.offer(items[i])) { System.out.println("Produced: " + items[i]); i++; } } } 

The producer thread would wait for an empty slot in a loop (busy-waiting).

4.3. Consumer

We'll implement a consumer Callable that reads from the buffer:

public T[] call() { T[] items = (T[]) new Object[expectedCount]; for (int i = 0; i < items.length;) { T item = buffer.poll(); if (item != null) { items[i++] = item; System.out.println("Consumed: " + item); } } return items; } 

Luồng tiêu dùng tiếp tục mà không in nếu nó nhận giá trị null từ bộ đệm.

Hãy viết mã trình điều khiển của chúng tôi:

executorService.submit(new Thread(new Producer(buffer))); executorService.submit(new Thread(new Consumer(buffer))); 

Thực hiện chương trình nhà sản xuất-người tiêu dùng của chúng tôi sẽ tạo ra sản phẩm như sau:

Produced: Circle Produced: Triangle Consumed: Circle Produced: Rectangle Consumed: Triangle Consumed: Rectangle Produced: Square Produced: Rhombus Consumed: Square Produced: Trapezoid Consumed: Rhombus Consumed: Trapezoid Produced: Pentagon Produced: Pentagram Produced: Hexagon Consumed: Pentagon Consumed: Pentagram Produced: Hexagram Consumed: Hexagon Consumed: Hexagram 

5. Kết luận

Trong hướng dẫn này, chúng ta đã học cách triển khai Ring Buffer và khám phá cách sử dụng nó để giải quyết vấn đề của người sản xuất và người tiêu dùng.

Như thường lệ, mã nguồn cho tất cả các ví dụ đều có sẵn trên GitHub.