title: Lock-free container with flipping buffers
body: <p>For one of my projects, which has to support concurrent reads and writes, I need a container that is able to buffer items till a consumer has taken each currently buffered item at once. As producers should be able to produce data regardless of whether the consumer read the current buffer I came up with a custom implementation that, with the help of <code>AtomicReference</code>, adds every entry to a backing <code>ConcurrentLinkedQueue</code> until a flip is performed which causes the current entry to get returned while storing a new entry with empty queue and metadata to be stored in that <code>AtomicReference</code> atomically.</p>
  
  <p>I came up with a solution such as</p>
  
  <pre class="lang-java prettyprint-override"><code>public class FlippingDataContainer&lt;E&gt; {
  
    private final AtomicReference&lt;FlippingDataContainerEntry&lt;E&gt;&gt; dataObj = new AtomicReference&lt;&gt;();
  
    public FlippingDataContainer() {
      dataObj.set(new FlippingDataContainerEntry&lt;&gt;(new ConcurrentLinkedQueue&lt;&gt;(), 0, 0, 0));
    }
  
    public FlippingDataContainerEntry&lt;E&gt; put(E value) {
      if (null != value) {
        while (true) {
          FlippingDataContainerEntry&lt;E&gt; data = dataObj.get();
          FlippingDataContainerEntry&lt;E&gt; updated = FlippingDataContainerEntry.from(data, value);
          if (dataObj.compareAndSet(data, updated)) {
            return merged;
          }
        }
      }
      return null;
    }
  
    public FlippingDataContainerEntry&lt;E&gt; flip() {
      FlippingDataContainerEntry&lt;E&gt; oldData;
      FlippingDataContainerEntry&lt;E&gt; newData = new FlippingDataContainerEntry&lt;&gt;(new ConcurrentLinkedQueue&lt;&gt;(), 0, 0, 0);
      while (true) {
        oldData = dataObj.get();
        if (dataObj.compareAndSet(oldData, newData)) {
          return oldData;
        }
      }
    }
  
    public boolean isEmptry() {
      return dataObj.get().getQueue().isEmpty();
    }
  }
  </code></pre>
  
  <p>As the current value needs to be pushed to the backing queue certain care needs to be taken now. The current implementation of the <code>from(data, value)</code> method does look something like this:</p>
  
  <pre class="lang-java prettyprint-override"><code>static &lt;E&gt; FlippingDataContainerEntry&lt;E&gt; from(FlippingDataContainerEntry&lt;E&gt; data, E value) {
    Queue&lt;E&gt; queue = new ConcurrentLinkedQueue&lt;&gt;(data.getQueue());
    queue.add(value);
    return new FlippingDataContainerEntry&lt;&gt;(queue,
        data.getKeyLength() + (value.getKeyAsBytes() != null ? value.getKeyAsBytes().length : 0),
        data.getValueLength() + (value.getValueAsBytes() != null ? value.getValueAsBytes().length : 0),
        data.getAuxiliaryLength() + (value.getAuxiliaryAsBytes() != null ? value.getAuxiliaryAsBytes().length : 0));
  }
  </code></pre>
  
  <p>Due to possible retries caused by an other thread updated the value right before this thread could perform the update, I need to copy the actual queue on each write attempt as otherwise an entry would be added to the shared queue even though the atomic reference couldn't get updated. Simply adding the value to the shared queue could therefore lead to the value entry being added to the queue multiple times when it actually only should occur once.</p>
  
  <p>Copying the whole queue is quite an expensive task so I tinkered around with just setting the current queue instead of copying the queue within the <code>from(data, value)</code> method and instead of adding the value element to the shared queue in the block executed when the update occurred:</p>
  
  <pre class="lang-java prettyprint-override"><code>public FlippingDataContainerEntry&lt;E&gt; put(E value) {
    if (null != value) {
      while (true) {
        FlippingDataContainerEntry&lt;E&gt; data = dataObj.get();
        FlippingDataContainerEntry&lt;E&gt; updated = FlippingDataContainerEntry.from(data, value);
        if (data.compareAndSet(data, updated)) {
          updated.getQueue().add(value);
          return updated;
        }
      }
    }
    return null;
  }
  </code></pre>
  
  <p>Within the <code>from(data, value)</code> I now only set the queue without adding the value element directly</p>
  
  <pre class="lang-java prettyprint-override"><code>static &lt;E&gt; FlippingDataContainerEntry&lt;E&gt; from(FlippingDataContainerEntry&lt;E&gt; data, E value) {
    return new FlippingDataContainerEntry&lt;&gt;(data.getQueue(),
        data.getKeyLength() + (value.getKeyAsBytes() != null ? value.getKeyAsBytes().length : 0),
        data.getValueLength() + (value.getValueAsBytes() != null ? value.getValueAsBytes().length : 0),
        data.getAuxiliaryLength() + (value.getAuxiliaryAsBytes() != null ? value.getAuxiliaryAsBytes().length : 0));
  }
  </code></pre>
  
  <p>While this allows to run the test 10+ times faster compared to the code copying the queue, it also fails the consumption test quite often as now the addition of the value element to the queue could occur right after the consumer thread flipped the queue and processed the data and therefore not all of the items appeared to be consumed.</p>
  
  <p>The actual question now is, can the copying of the backing queue be avoided to gain a performance boost while still allowing to update the queue's content atomically with lock-free algorithms and therefore also avoid losing some entries mid way?</p>