Circular Queue

  • 8/5/2015

Software developers aren’t keen on losing data. In certain tasks, though–retaining a limited event history, say, or buffering a realtime stream–data loss might be a fully-underwritten feature of the system. In these scenarios, we might employ a circular queue; a fixed-size queue with the Ouroborosian behavior that stale data from the end of the queue are overwritten by newly-arrived items.

Getting Started

We’ll use the circular-queue package from NPM to get started:

$ npm install circular-queue

Let’s create our first queue and specify how many items it can hold. The maximum size will vary greatly between applications, but 8 is as good a number as any for demonstration.

var CircularQueue = require('circular-queue');
var queue = new CircularQueue(8);

Operations

Our new queue has two basic operations: queue.offer(item), which adds items to the queue, and queue.poll(), which will remove and return the queue’s oldest item:

queue.offer(3);
queue.poll();  // 3
queue.isEmpty; // true

It can also be useful to inspect the next item from the queue before deciding whether to poll it. We can do this using queue.peek():

queue.offer(3);
queue.peek(); // 3
queue.poll(); // 3

Here’s what it looks like in action. Use offer() and poll() methods to add and remove additional items, noting the “rotation” of the oldest element (blue) as the contents shift:

Eviction

The idea at the heart of the circular queue is eviction. As new items are pushed onto an already-full queue, the oldest items in the queue are “evicted” and their places overwritten. Using circular-queue, we can detect evictions as they happen using the 'evict' event.

queue.addEventListener('evict', function (item) {
  console.info('queue evicted', item);
});

How we handle eviction will vary from one domain to the next. It’s an opportunity to apply error-correcting behavior–to expand a buffer, allocate new workers, or take other steps to relieve upstream pressure–but even if the loss is “expected”, it may be worth at least a note in the logs.

To see eviction in practice, use offer() to overrun the full queue below. Note the value of the evicted item and the “rotation” of the queue as its head and tail move.

Buffering

We’re now ready to put it all together. In a live application, we’ll rarely be clicking offer and poll ourselves. Rather, some upstream “producer” will be pushing new data to the queue while a downstream “consumer” races to pull items off.

We can get a sense for how this behaves using a final demo. Try adjusting the rate of production and consumption to see the queue in balance (consumption matches production), filling up (production exceeds consumption), or draining (consumption exceeds production).

Hey, I'm RJ! For more learnings about software and management, find me @rjzaworski or sign up for my semi-regular newsletter.

Let’s keep in touch

Send me timely updates on software, product, and process.