Full and empty queue problems

Every queue in the broker memory must have a limited size.

Without size limits, a single queue can consume all available memory, leading to broker crashes.

When a queue is full, and when a queue is empty.

When messages arrive faster than consumers can process, the queue becomes full.

When messages are consumed faster than they are produced, the queue becomes empty.

All producer and consumer requests are handled by a server running on the broker.

This server may be a TCP or HTTP server.

It may use blocking or non-blocking I/O.

For simplicity, assume it is an HTTP server with non-blocking I/O and a thread request model.

This is referred to as a web server throughout the discussion.

When a queue is full, incoming messages must be managed.

Options include:

• Dropping incoming messages
• Forcing producers to slow down
• Scaling consumers to process messages faster

Load shedding

On a single machine: monitor queue size. When depth exceeds a threshold, drop new messages.

In distributed systems: monitor cluster-wide metrics like CPU load, memory utilization, or average response latency.

When a metric exceeds a safe threshold, all machines drop a fraction of incoming traffic.

Rate limiting

Each producer is assigned a quota.

For example: a producer may send no more than 1,000 messages per second.

All messages beyond this limit are dropped.

On a single machine: count requests per client per second and store the count in memory.

In distributed systems: store quotas in an external cache.

Any machine in the cluster can read and update the quota.

When the broker drops messages, it must notify producers.

This is done via a response message or exception sent back to the producer.

The notification indicates that message delivery is being rejected due to queue fullness.

When the broker is busy, producers face several response options. They may choose to do nothing—ignore the exception and continue sending messages.

This behavior is not ideal, as producers act like poor citizens. However, it is a valid choice.

The broker must be prepared to handle such situations and drop incoming messages as needed.

If producers honor the pushback exception, they have multiple valid strategies.

Producers may buffer messages on their side—either in memory or on disk—and attempt to resend them later.

Producers may propagate the exception upward through the call stack, all the way to the original request generator.

This approach works only if all upstream calls are synchronous.

Another option is to send messages over the limit to temporary storage.

Such storage may include a standby broker or a completely different system.

Crucially, producers must never retry failed messages immediately.

The broker is already overwhelmed and cannot keep up.

Immediate retries create a retry storm, worsening the load.

With rate limiting and low trading, the broker asks producers not to send more messages.

Producers may ignore this request or fail to respond appropriately.

In such cases, the system may enforce a slowdown.

This is the purpose of backpressure.

Backpressure introduces a feedback mechanism.

When a component is under stress, it communicates this to upstream components and requests reduced load.

In a single-machine environment, backpressure can be implemented using a limited number of message processing threads.

When producers send too many messages, all threads become exhausted.

Messages are blocked during attempts to write to a full queue.

Because all threads are blocked, producers cannot establish new connections.

They also cannot send additional messages over existing connections.

Producers are forced to wait for a thread to become available.

Thread pools and blocking queues support this implementation.

Distributor systems use a similar principle.

A load balancer sits in front of a machine cluster.

For each incoming request, it selects a machine with the fewest open connections.

When load is too high and all machines are exhausted, the load balancer cannot open new connections.

It cannot forward the request to any machine.

The load balancer then propagates backpressure to clients.

In this scenario, producers should respond similarly to load sharing and write limiting.

Options include buffering messages, propagating backpressure upward, switching to a different message processing system, or logging and dropping the message.

Next is elastic scaling—also known as dynamic allocation or auto scaling.

In a single-machine setup, this can be achieved by managing a dynamic pool of read threads.

More threads are added when queue size exceeds a threshold.

Idle threads are destroyed when queue size decreases to reduce memory usage.

Semaphores can help implement this approach.

In distributed systems, elastic scaling involves dynamically adding more consumers to process messages in parallel.

This reflects the competing consumers pattern.

Now consider an MTQ.

What makes an MTQ special?

Pause and reflect on how you would implement reading elements from a queue.

Both infinite loops and scheduled tasks are common approaches for consuming messages from a queue.

An infinite loop repeatedly attempts to retrieve a message from the queue on each iteration.

A scheduled task runs periodically to check for new messages in the queue.

When a message is found, it is processed and the system attempts to retrieve the next message.

This approach works well while messages are present in the queue.

However, when the queue becomes empty, both methods do nothing useful.

They continuously attempt to retrieve a message, wasting resources on both the consumer and the broker side.

Reducing the frequency of loop or task execution helps slightly.

But this introduces a new issue: messages may remain in the queue longer than necessary.

This increases message processing latency.

One solution is for the broker to push messages directly to consumers.

The broker detects when a message is available and sends it to one or more consumers.

This eliminates the need for consumers to repeatedly poll the queue.

In pull-based systems, consumers request messages from the broker.

If the queue is empty, the broker does not respond immediately.

Instead, it blocks the request until a new message appears in the queue.

This technique is known as long pulling.

To enable push-based delivery, a TCP connection must be established between the broker and consumers.

Messages can be pushed using either raw TCP or a custom TCP-based protocol.

Existing protocols like WebSocket support this functionality.

The discussion illustrates core distributed system design principles.

These concepts emerge from a simple setup: one broker and a queue.

This demonstrates how complex distributed system ideas connect to basic data structures.

Further examples of such connections will be explored in later videos.