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	Queue-local temporal indexing, cleanup range queries	O(log q)
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)

The delayed-job heap uses a different lazy-removal check: a Map<jobId, runAt> is the live source of truth. When no delayed jobs remain, the heap is cleared immediately. Otherwise it is rebuilt in O(n) once there are at least 256 stale entries and stale entries are at least as numerous as live entries. This bounds retained heap memory after cancellation or promotion churn.

Skip List

Used for queue-local temporal indexes (jobs ordered by createdAt, then job ID) and efficient range queries during cleanup. Each queue owns a separate skip list, while a direct job-ID map points to the corresponding entries for logarithmic removal. 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. Select the queue-local index O(1)

→

2. Walk forward at level 0 O(k)

→

3. Collect while createdAt < threshold

Total: O(log q + k), where q is the number of indexed jobs in that queue and k is the number returned. Removal uses the job-ID map plus a queue-local skip-list delete: O(log q).

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

Direct writer handoff reserve writer = true before resolving the oldest waiter; late arrivals cannot barge

timeout cancellation

Settle once, decrement live writer count once, skip cancelled heads, then dispatch writers or the compatible reader cohort

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	Queue-local skip list	O(log q + k)
Remove temporal entry	Job-ID map + queue skip list	O(log q)
Lock acquire	RWLock	O(1) uncontested