bunqueue Data Structures: MinHeap, Skip List & LRU

architecture · data structures

Heaps, skip lists, LRUs.

bunqueue uses specialized data structures optimized for job queue operations: a 4-ary MinHeap, skip lists, LRU caches, FNV-1a hashing, and read-write locks.

Overview

Structure	Use Case	Complexity
4-ary MinHeap	Priority queue, cron scheduling, delayed-job tracking	O(log₄ n)
Skip List	Temporal indexing, cleanup range queries	O(log n)
LRU Cache	Job results, custom IDs	O(1)
Hash (FNV-1a)	Sharding, distribution	O(len)

4-ary MinHeap

Used for priority queues, cron scheduling, and delayed-job tracking (TemporalManager keeps delayed jobs in a MinHeap ordered by runAt for O(k) refresh).

Why 4-ary vs binary?cache locality

Binary heap height log₂(n) = 16 levels for 65k items, 2 children per node, more memory indirections

4-ary heap height log₄(n) = 8 levels for 65k items, 4 children per node, children fit in cache line (64 bytes), fewer cache misses

Trade-off: 4 comparisons per level vs 2. Win: better cache locality outweighs extra comparisons.

Heap with Lazy Deletion

Generation trackinglazy deletion

Each entry has a generation number { jobId, priority, runAt, generation: 42n }

Index maps jobId → { job, generation }

REMOVE delete from index O(1), heap entry becomes stale

POP loop: peek, check generation match, mismatch: skip stale entry, match: return job

COMPACT, stale ratio > 20% filter valid entries, rebuild heap O(n)

Skip List

Used for the temporal index (jobs ordered by createdAt) and efficient range queries during cleanup. Delayed jobs are tracked separately in a MinHeap, not here.

Skip list structuresorted list with express lanes

level 3

→

level 2

→

level 1

→

level 0

→

Properties: probabilistic level assignment (p=0.5), expected height O(log n), simpler than balanced trees, good cache locality (sequential links).

Range Queries

Range querygetOldJobs(threshold, limit)

1. Navigate to leftmost element O(log n)

→

2. Walk forward at level 0 O(k)

→

3. Collect while createdAt < threshold

Total: O(log n + k) where k = results. Use case: find jobs older than X for cleanup.

LRU Cache

Used for job results, custom ID mapping, and logs.

Doubly-linked LRUMap<Key, Node> plus doubly-linked list

A HEAD, most recent

↔

D TAIL, LRU

GET(key) find in map O(1), move to head, O(1) pointer updates

SET(key, value) if at capacity remove tail, evict LRU, add new node at head

All operations: O(1).

Memory Bounds

Bounded collectionsmax size, eviction

completedJobs 50,000, FIFO batch (10%)

jobResults 10,000, LRU

jobLogs 10,000, LRU

customIdMap 50,000, LRU

DLQ per queue 10,000, FIFO

BoundedSet (FIFO): no recency tracking (faster), batch eviction removes 10% when full, amortized cost across many operations.

Hash Function (FNV-1a)

Used for sharding and distribution.

FNV-1a hashalgorithm

hash = FNV_OFFSET 0x811c9dc5

→

for each byte: hash = hash XOR byte, hash = hash * FNV_PRIME 0x01000193

→

return hash unsigned 32-bit

Fast ~10-15 CPU cycles per character

Good distribution

Deterministic

Non-cryptographic speed over security

Sharding

Shard selectionshardIndex = fnv1a(queueName) & SHARD_MASK

SHARD_COUNT auto-detected from CPU cores, power of 2, SHARD_MASK = SHARD_COUNT - 1

4 cores SHARD_COUNT=4, SHARD_MASK=0x03, binary 11

10 cores SHARD_COUNT=16, SHARD_MASK=0x0f, binary 1111

20 cores SHARD_COUNT=32, SHARD_MASK=0x1f, binary 11111

64+ cores SHARD_COUNT=64, capped

Why bitwise AND? 3-5x faster than modulo, requires power-of-2 shard count, hash & SHARD_MASK is equivalent to hash % SHARD_COUNT.

Lock Structures

RWLock (Read-Write Lock)

Read-write lockRWLock

Multiple concurrent readers

Single exclusive writer

Writer priority prevents starvation

Fast path, uncontested write if (!writer && readers === 0) { writer = true; return guard; }, synchronous, no Promise

timeout cancellation

Mark entry as cancelled O(1), skip cancelled entries on release, no O(n) array splice

Complexity Summary

Operation	Structure	Time
Push job	4-ary heap	O(log₄ n)
Pop job	4-ary heap	O(log₄ n)
Find job	Index map	O(1)
Remove job	Lazy deletion	O(1)
Get result	LRU map	O(1)
Shard lookup	Hash + AND	O(len)
Range query	Skip list	O(log n + k)
Lock acquire	RWLock	O(1) uncontested