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)
• sending thread(s) take data from "the beginning" of this buffer and send the data to the CMR

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, put and take 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

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

Realization

Testing

t.b.a.

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