The multi-producer-single-consumer ring buffer is not lock-free (so not wait-free)

[namniav]

The used algorithm can be reduced to

producer:
    pos = write_cursor.fetch_add(num);
    write_data(blocks[pos].data)                    #1
    blocks[pos].status.store(ready, release)

consumer:
    pos = read_cursor.load(relaxed)
    if blocks[pos].status.load(acquire) == ready:   #2
        read_data(blocks[pos].data)
        blocks[pos].status.store(free, release)
        

Consumer and producers rely on a flag(status) indicating whether data is ready. If a producer is suspended at #1, then the consumer is blocked at #2, waiting the producer to finish writing. No further data from other producers can be consumed. When the ring buffer become full, all other producers are blocked by the consumer which is blocked by the suspended producer. No thread can make progress until the suspended producer finish writing.

[pippocao]

This is a very interesting and worthy discussion, so I moved it from the Issue list to the Discussion. Here are our thoughts on this topic.

Firstly, our view is that lock-free or wait-free refers to a situation where there's no blocking during multithreaded race conditions. The blocking wait you mentioned is due to a lack of resources for the consumer or producer, not a wait induced by the algorithm itself.

For example, std::vector's push_back is not an atomic operation, so it needs to be locked in multithreaded environments, which means it's not lock-free. However, some universally recognized lock-free or wait-free linked lists may also encounter blocks if there isn't enough memory to allocate new data, similar to your description of what happens when a ring buffer is full. We believe this is a block caused by insufficient resources, and such blocks can exist in all systems that claim to be lock-free or wait-free, whether due to a lack of memory or I/O.

Therefore, the size of bq::ring_buffer can be adjusted according to different use scenarios, as described in our README.MD.

Regarding your first example, it is also a type of block caused by insufficient resources. For the consumer thread, the producer thread's data is a resource. If the resource isn't ready, indeed, the consumer has nothing to do. However, the ring buffer itself doesn't block in this situation; it returns a failure, and then the log's worker, as an external scheduler, can choose to temporarily sleep. Regarding "No further data from other producers can be consumed," I'd like to clarify that bq::ring_buffer uses a multiple-producer, single-consumer setup, rather than multiple producers and multiple consumers, because it is designed specifically for logging. This is why the code of bq::ring_buffer is in the bq_log directory, not the bq_common directory. One of the main aspects of logging is keeping things in order. Even though writing might result in small order mistakes due to thread priorities, considering logs ultimately need to be saved on disk in a specific order, the consumer thread must handle the data in the ring buffer in order and cannot skip unread data to read what's next.

These are some of our views, and we welcome further discussion.

[namniav]

The blocking wait you mentioned is due to a lack of resources for the consumer or producer, not a wait induced by the algorithm itself.

This isn't the case. It is the suspended producer that cause the ring buffer to become full. Using a buffer of infinite size doesn't help because it doesn't change the fact that consumer is blocked and the data structure cannot make progress until the producer finish writing. If a producer is suspended forever or killed at #1, the data structure become unusable.

some universally recognized lock-free or wait-free linked lists may also encounter blocks if there isn't enough memory to allocate new data, similar to your description of what happens when a ring buffer is full.

Correct lock-free or wait-free algorithm ("correct lock-free or wait-free" doesn't mean better performance) can always make progress(or stay usable) regardless of the thread states, suspended or killed at any point.

One of the main aspects of logging is keeping things in order. Even though writing might result in small order mistakes due to thread priorities, considering logs ultimately need to be saved on disk in a specific order, the consumer thread must handle the data in the ring buffer in order and cannot skip unread data to read what's next.

The write order of different threads near race conditions are subtle and not reliable. So do the order of starting the call to logging, the order of formatting strings and the order of writing strings. I don't think it is that important. However, even considering it is really important so that BpLog cannot skip unread data to read what's next isn't enough to make algorithm lock-free. As mentioned above, it is the fact that consumer waits a particular producer to change the flag makes the algorithm insufficient to be lock-free.

Some useful links:
https://en.wikipedia.org/wiki/Non-blocking_algorithm
https://stackoverflow.com/questions/45907210/lock-free-progress-guarantees-in-a-circular-buffer-queue

[namniav]

@pippocao If you agree that the ring buffer is not lock-free, please remove or modify the claim that the ring buffer is wait-free/lock-free. It delivers two misconceptions that a) what is lock-free/wait-free; b) how wait-free affect performance.

[pippocao]

Thank you very much for your rigorous feedback. Indeed, if we adhere to the strict definitions of true lock-free and wait-free, the bq::ring_buffer does not meet these criteria. I've reviewed the entire repository, and I feel that the article about the ring buffer may be the most likely source of any misleading information in this regard. We will amend the wording in the article accordingly.

However, regarding the topic of wait-free, we had already considered related aspects as I mentioned in my previous response. We placed bq::ring_buffer in the "bq_log" directory rather than the "bq_common" directory because we believe that it achieves a de facto state of wait-free under the bq_log system. Aside from failures due to lack of resources like insufficient buffer space, we are quite confident that suspensions or killing of producer threads between alloc and commit should not occur. This section was deliberately kept to simple memory assignments, and the only risk would be scenarios like sigsegv, which theoretically would crash the entire program.

[namniav]

we are quite confident that suspensions or killing of producer threads between alloc and commit should not occur.

There's context switch. Wait/lock-free is a property of algorithm, usually independent on hardware or system you run it. Wait-free algorithms don't imply good performance, in fact wait-free algorithms except very simple ones usually have suboptimal throughput compared to lock-free or even blocking design, your ring buffer for example. You may invent your own words instead of wait/lock-free because they are already used for something else.

[pippocao]

Documents and Comments are updated in main branch.