Difference between a ring buffer and a queue

Question

What is the difference between the ring (circular) buffer and a queue? Both support FIFO so in what scenarios I should use ring buffer over a queue and why?

Relevance to Hadoop

The map phase uses ring buffer to store intermediate key value pairs. What are the reasons for this choice over a queue?

Pegpega

Would you mind explaining what this has to do with Hadoop? – Giliana

Yes. The map phase uses ring buffer to store intermediate key value pairs. So I thought people with hadoop background might want to look at the question as well. – Pegpega

Thanks :) I'm interested in the answer as well as this isn't something I've ever looked into. – Giliana

It is new to me that it uses a ring buffer, can you add the source code where you've found it? In 1.x it was using a simple byte[] or buffer to store the k/v pairs for sorting. – Sulphide

Looking into the latest release tells me that nothing changed. (svn.apache.org/repos/asf/hadoop/common/tags/release-2.4.0/…) – Sulphide

@ThomasJungblut This was mentioned on page 206 of Hadoop Definitive Guide 3rd edition: "Each map task has a circular memory buffer that it writes the output to...." – Pegpega

@Pangea I think what Tom meant there is that the buffer is cycled once it is full and asynchronously sorted, it is not a circular buffer in the datastructure sense. – Sulphide

Answer 1

A RingBuffer is an array, which is used as Queue

It will maintain both Read & Write positions separately. When it reach end of Array, it will continue from beginning of Array.

Uses of RingBuffer over Queue.

1. Ring Buffers are fast.
2. When you have hard cut-off for how much data to be stored, RingBuffer is useful.

Have a look at this article by Jakob Jenkov for more details.

Have a look at related SE question :

Java - Ring Buffer

Apomict

Answer 2

A queue is an abstract data type supporting the operations enqueue and dequeue. A ring buffer is one possible implementation of a queue, though it's not the only one (for example, you could implement a queue using a linked list). In other words, queue is a general term for a data structure that can support FIFO insertions and ring buffers are one possible data structure you could use to implement a queue.

Hope this helps!

Counterpane

Answer 3

The 2 are very similar in implementation, but their subtle differences in usage can make them seem quite different. Here's the short answer:

Ring: intermediate values in the buffer can be read, like a "recent history buffer"

Fifo: only the oldest can be read (and often removed when read)

Long answer

A ring buffer has one pointer that advances and wraps around when it reaches the end. This permits data to be overwritten when it naturally becomes obsolete. It is useful if you need to keep the last N samples for something. Example usage:

• An FIR implementation, where you would use the most recent N samples. As new data points come in, the FIR would operate on the most recent N data points.
• Capture last N data points if a specific event occurs (like dash cams, that automatically save the last 5 seconds of video if an incident is detected)

A FIFO or Queue (both are one and the same), is often implemented as a ring buffer (templatetypedef's answer is correct, it could be a linked list). In contrast to the ring buffer, there will be 2 pointers; one for read and another for write. Just like the ring buffer pointer, either pointer will wrap around to the beginning of the physical buffer when incremented; giving the illusion of a continuous buffer. Note that it is considered an error for the write pointer to catch up to the read pointer. Example usage:

• One entity is producing data and another is to process it, but the processing can't happen in time or at the same time as the data producer. Like the lineup at the post office.
• messages being sent from one system to another. order is important, and none should be lost.

Aby

Answer 4

I would rather say that queue is a policy, dictating where items are placed, and from where they are removed. In a queue (also known as FIFO) customers are placed in the back, and removed from the front allowing the first one to come be the first one to be serviced.

On the other hand, buffer is a more general name and nothing is said about its policy, although most of the time people assume buffer is a FIFO. Buffer usually is a more "physical" structure, and therefore usually associated to some capacity limit (lets say 8 items).

In your case, circular buffer implements a FIFO that has an upper bound on the number of outstanding customers and if you exceed this maximum, it will discard the oldest customer and replace by the new one.

Dividers