a better ring buffer

[derekxgl]

1st of all, I think ring buffer should be compile time fixed sized so it's trivial to do modulus op.

I'm thinking about a better ring buffer which can be multiple producers & multiple consumers without using spinlock. It's kind of like https://en.wikipedia.org/wiki/Seqlock. Say a ring buffer of size 1024 * 1024. It has a seq number member variable (default 1). Each item in the ring buffer has a seq number atomic var (instead of your atomic_flag) as well. When ring buffer gets created, all items have default seq no 0. When a producer wants to add an item, ringbuffer::seqNo.fetch_add(1...) return the seq no of the item to be written by this producer. Obviously the index of item (or called bucket) is seq no % SIZE. Even all producers want to write items at same time, all got unique bucket to work on without race. So far it's similar to what you are doing now. I think it's fair to assume it's super fast to copy the data to bucket, so it won't happen that a producer logs so fast that it can compete same bucket with another producer. Basically it should be safe to assume that it's not possible that a producer or a few producers can log the whole ring buffer while one producer is still working on a particular bucket. Actually before producer writes data to bucket, it set bucket seq no to seq No - 1 indicating data might be dirty. Once finishing writing, update bucket seq no to seq No.

Now back to the consumer (or consumers). Consumer knows that 1st item is seq no 1. So it read the seq no atomic variable of the bucket (index 1 of the ring buffer). If atomic var has value less than the seq no consumer is expecting, it means data is not ready. So consumer keeps trying to read the atomic var. If var is greater than seq no consumer is expecting, then consumer is too slow. Assume consumer is fast, and atomic var is 1. Consumer copies the data, and read bucket seq no again to make sure data is not corrupted(it's possible that producer is updating same buffer while consumer is reading, which also means consumer is too slow). Suppose all good. Then consumer moves on to seq no 2, 3, ... . Consumer never updates anything on ring buffer, so multiple consumers are supported (assuming all read same data).

What do you think? It's similar to what i have done in the past (single producer though), but I think this should work, and it's not very complicated). I'm happy to write the code, but i think you probably have more free time than me.

[Iyengar111]

Hi Derek

Ideas are interesting.
Take a look at issue #4 must think of a solution for that first.

Karthik

[damondd]

You can take a look at:
https://github.com/facebook/folly/blob/master/folly/ProducerConsumerQueue.h
https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h

[Nimrod0901]

I have to point out that the ring-buffer here is not the same as in traditional ways. It allows the overwritten when overflow, which means multiple threads writing to the same place. As for a normal ring-buffer, writes will fail when it's full.

Aside:
The sequence number design is used to solve the ABA problem in a MPMC ring buffer. It's unnecessary in MPSC.
For a non-droppable MPSC ring buffer with try_pop and push, two indexes are enough.