Queue

Distributed systems must handle incoming messages efficiently. Messages arrive and need to be stored temporarily before processing.

Storage choices directly impact performance, memory usage, and system stability.

A queue provides ordered, temporary storage with predictable behavior.

A queue is a data structure used to store messages in memory.

It follows the first-in, first-out (FIFO) principle.

The first message added is the first one removed.

Queues can be bounded or unbounded.

An unbounded queue has no size limit.

It may use all available memory.

A bounded queue has a fixed capacity.

This capacity is set when the queue is created.

Queues can be implemented using linked lists or arrays.

A linked list implementation is straightforward.

It requires a pointer to the first node and a pointer to the last node.

This allows fast insertion at the tail and deletion from the head.

Array-based implementation is less efficient.

Adding elements to the end is easy.

Removing elements from the beginning requires shifting all elements.

This operation takes linear time and is slow.

A ring buffer is a specialized array-based queue.

It tracks two positions: read and write.

The read index marks the next position to read.

The write index marks where the next element is added.

When either index reaches the end, it wraps back to zero.

This creates a circular traversal.

When full, two options exist:

• Overwrite the oldest data

• Throw an exception

Ring buffers are used in logging.

Log data is stored in memory.

It is written to disk periodically by a background process.

Ring buffers are used in Hadoop MapReduce.

Mappers generate key-value pairs.

These are stored in memory using a ring buffer.

When the buffer reaches a threshold, a background thread copies data to disk.

This process is called spilling.