Ringbuffer in the inspectIT agent

Meetings

Requirements

The ringbuffer will replace the buffering strategy in the agent completely, while the sending strategy will be kept, as it defines when data should be sent.

The ringbuffer uses a FIFO policy:

• threads put data to this buffer "at the end" (measurements that are gathered and being sent to the CMR)
• ONE sending thread takes data from "the beginning" of this buffer and sends the data to the CMR
• the sending thread takes all the elements it finds in the buffer

As  we are dealing with a highly multi-threaded environment, the following requirements for the ringbuffer are important:

• thread-safe
• correctly sinchronized
• highly concurrent and performant
  • as fast as possible
  • as little locking as possible

Furthermore, the size of the buffer is limited, either by

• maximum number of elements or
• maximum memory

In case the buffer is full and an insertion operation is desired, the oldest element(s) must be dropped to make room for the new element(s).
Moreover, when the limitation is done with respect to memory occupancy, a utility to calculate object sizes is also required.

Approach

There are two issues that have to be dealt with:

1. implementing the concurrent access, enqueue and dequeue operations.
2. implementing the eviction of old elements when the buffer has reached its size limit

Approach for implementing a concurrent queue [1][2]

• non-blocking - for better performance in highly multi-threaded environments
• linked list:
  
  • each element holds a reference to the next element
  • sentinel nodes: head and tail
  • head - points to the first element in the list
  • tail - points to the last element in the list
  • the last element has a NULL reference for next element
• non-blocking enqueue/dequeue: use compare-and-set to set the values of head and tail
• lazy approach - enqueue/dequeue are both done in two steps [1]
• two-step enqueue:
  
  • compare-and-set to append new element
  • compare-and-set to change the value of tail
  • "every other method call must be prepared to encounter a half-finished enqueue call, and to finish the job"
  • an enqueue call never waits for a dequeuer
• two-step dequeue:
  
  • read the value from the first element
  • compare-and-set to change the value of head
  • make sure that tail does not lag behind

Refer to Section 10.5 "An Unbounded Lock-Free Queue" in [1] and Section 2 in [2] for a more detailed explanation.
Another possibility to implement a concurrent queue:

• using two locks, one for queing and one for dequeueing
• livelock free
• but high contention

Both locking and lock-free approaches will be implemented in order to find the best approach.

Approach for eviction of old elements

• similar to CMR atomic buffer implementation [4]
• use AbstractObjectSizes class for calculating object sizes [5]
• separate thread for analyzing and calculating the buffer size
• separate thread for eviction operation by FIFO policy; this operation has to be suspended while the size of all objects in the buffer is smaller than the buffer maximum size
• in the analysis thread, signal the eviction thread if needed
• use conditions for suspending and activating the threads that work on eviction and analysis

The object size can also be computed when enqueueing an element instead of on a different thread. Both approaches introduce some overhead: size calculation on a separate thread means locking and context switching, while synchronous size calculation means slowing down the enqueue operation, which has to be very fast. Nevertheless, it is hard to say which approach is faster, so both of them will be implemented.

Therefore, we have the following approaches that have to be implemented and compared:

Realization

Class diagram for a lock-free RingBuffer with separate eviction and analysis threads (Approach 2):

The following diagram shows how the enqueueing and dequeueing are performed without using locks.

The dequeue operation takes all the elements in the buffer, while enqueue adds one element.

The first node in the buffer is always a dummy node with a null object. The tail is an atomic reference to the last element in the buffer. In this example, there is no need for an atomic reference to the first element in the buffer, as there is only one sending thread that can dequeue elements and thus change the dummy node's next element.

Testing

Issues that need to be checked:

• Performance
  
  • measure time for different number of threads
  • compare the different approaches
• Correctness (harder to check)
  
  • linearizability
  • thread safety
  • no deadlocks
  • no livelocks

The general structure of a test application for RingBuffer has:

• 1 sending thread
  
  • loop:
    
    • sleeps 5s
    • dequeues all the elements in the buffer
    • prints them
• n threads that enter data:
  • n = 2, 10, 100 ...
  • loop that adds elements
  • no sleeping between enqueues to make it fast
  • limiting the size by number of elements:
    
    • use random Floats as data
    • object size not important, only the number of elements
  • limiting the size by memory
    • use Strings with variable length

References

[1] Maurice Herlihy, Nir Shavit, "The Art of Multiprocessor Programming, Revised Reprint"
[2] Maged M. Michael, Michael L. Scott, "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms"
[3] ConcurrentLinkedQueue implementation in Java
[4] CMR buffer specifications
[5] Calculation of object sizes