title: Circular lock-free buffer
body: <p>I'm in the process of designing a system which connects to one or more stream of data feeds and do some analysis on the data than trigger events based on the result. In a typical multi-threaded producer/consumer setup, I will have multiple producer threads putting data into a queue, and multiple consumer threads reading the data, and the consumers are only interested in the latest data point plus n number of points. The producer threads will have to block if slow consumer can not keep up, and of course consumer threads will block when there are no unprocessed updates. Using a typical concurrent queue with reader/writer lock will work nicely but the rate of data coming in could be huge, so i wanted to reduce my locking overhead especially writer locks for the producers. I think a circular lock-free buffer is what I needed. </p>
  
  <p><strong>Now two questions:</strong></p>
  
  <ol>
  <li><p>Is circular lock-free buffer the answer?</p></li>
  <li><p>If so, before i roll my own, do you know any public implementation that will fit my need?</p></li>
  </ol>
  
  <p>Any pointers in implementing a circular lock-free buffer are always welcome.</p>
  
  <p>BTW, doing this in C++ on Linux.</p>
  
  <p><strong>Some additional info:</strong></p>
  
  <p>The response time is critical for my system. Ideally the consumer threads will want to see any updates coming in as soon as possible because an extra 1 millisecond delay could make the system worthless, or worth a lot less.</p>
  
  <p>The design idea I'm leaning toward is a semi-lock-free circular buffer where the producer thread put data in the buffer as fast as it can, let's call the head of the buffer A, without blocking unless the buffer is full, when A meets the end of buffer Z. Consumer threads will each hold two pointers to the circular buffer, P and P<sub>n</sub>, where P is the thread's local buffer head, and P<sub>n</sub> is nth item after P. Each consumer thread will advance its P and P<sub>n</sub> once it finish processing current P and the end of buffer pointer Z is advanced with the slowest P<sub>n</sub>. When P catch up to A, which means no more new update to process, the consumer spins and do busy wait for A to advance again. If consumer thread spin for too long, it can be put to sleep and wait for a condition variable, but i'm okay with consumer taking up CPU cycle waiting for update because that does not increase my latency (I'll have more CPU cores than threads). Imagine you have a circular track, and the producer is running in front of a bunch of consumers, the key is to tune the system so that the producer is usually runing just a few step ahead of the consumers, and most of these operation can be done using lock-free techniques. I understand getting the details of the implementation right is not easy...okay, very hard, that's why I want to learn from others' mistakes before making a few of my own. </p>