Circular Queue
- 8/5/2015
- ·
- #index
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).