# Memory/SQLite Data Structures: MinHeap, Skip List & LRU Data structures powering bunqueue's memory/SQLite engine: 4-ary MinHeap, skip lists, LRU cache, FNV-1a hashing, and read-write locks. Canonical: https://bunqueue.dev/architecture/data-structures/ ---

architecture · data structures

Heaps, skip lists, LRUs.

The memory/SQLite engine uses a 4-ary MinHeap, skip lists, LRU caches, FNV-1a hashing, and read-write locks. PostgreSQL uses database rows, indexes, and locks for authoritative ordering and ownership.

This page covers the base memory/SQLite engine and its in-process compatibility caches. PostgreSQL mode keeps only bounded projections needed by the shared API; its authoritative claim, scheduling, limit, and lifecycle structures are the database tables and indexes described in [Storage backends](/guide/databases/). ## 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` 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 in the memory/SQLite engine.

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 (memory/SQLite) | 4-ary heap | O(log₄ n) | | Pop job (memory/SQLite) | 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 | :::tip[Related] - [Architecture Overview](/architecture/) - Full component map - [Domain Layer](/architecture/domain-layer/) - Where these structures hold jobs and priorities - [Cron Scheduler](/architecture/cron-scheduler/) - Uses a MinHeap for time-ordered runs :::