# Sharding Deep Dive: Multi-Core Job Distribution

How bunqueue shards jobs across CPU cores using FNV-1a hashing for maximum throughput. Deep dive into power-of-2 shard architecture.

Canonical: https://bunqueue.dev/blog/sharding-deep-dive/

---

import { Aside } from '@astrojs/starlight/components';

<div class="bq-wrap bq-hero">
  <span class="bq-eyebrow">blog · architecture</span>
  <h1 class="bq-hero-h1 bq-bench-h1">One queue per core, not one lock for <em>all.</em></h1>
  <p class="bq-hero-sub">Instead of a single global queue behind a lock, bunqueue partitions jobs across independent shards with FNV-1a hashing, sized to your CPU cores. Here is how it works.</p>
</div>

## Why Shard?

A single priority queue becomes a bottleneck when multiple workers pull jobs simultaneously. Lock contention grows with concurrency. Sharding solves this by partitioning the job space:

- Each shard has its own priority queue
- Workers can pull from different shards concurrently
- Lock contention is reduced by a factor of N (shard count)

## Shard Count: Auto-Detected from CPU Cores

The number of shards is calculated at startup based on available CPU cores, rounded up to the nearest power of 2:

```typescript
function calculateShardCount(): number {
  const cores = navigator.hardwareConcurrency || 4; // fallback: 4

  // Find next power of 2 >= cores, capped at 64
  let shards = 1;
  while (shards < cores && shards < 64) {
    shards *= 2;
  }
  return shards;
}
```

| CPU Cores | Shard Count |
|-----------|-------------|
| 1         | 1           |
| 2         | 2           |
| 3-4       | 4           |
| 5-8       | 8           |
| 9-16      | 16          |
| 17-32     | 32          |
| 33+       | 64          |

The power-of-2 constraint is critical for the hashing strategy.

## FNV-1a: Fast Deterministic Hashing

Jobs are assigned to shards using FNV-1a hash on the queue name:

```typescript
function fnv1a(str: string): number {
  let hash = 0x811c9dc5; // FNV offset basis
  for (let i = 0; i < str.length; i++) {
    hash ^= str.charCodeAt(i);
    hash = Math.imul(hash, 0x01000193); // FNV prime, 32-bit multiply
  }
  return hash >>> 0; // Ensure unsigned
}

const SHARD_MASK = SHARD_COUNT - 1;

function shardIndex(queueName: string): number {
  return fnv1a(queueName) & SHARD_MASK;
}
```

Because `SHARD_COUNT` is always a power of 2, we use bitwise AND instead of modulo. This is a single CPU instruction vs. an expensive division:

```typescript
// Fast: single AND instruction
const idx = hash & SHARD_MASK;

// Slow: division + remainder
const idx = hash % SHARD_COUNT;
```

<Aside type="tip">
  All jobs for the same queue name always land in the same shard. This means operations on a single queue are serialized (no cross-shard coordination needed), while different queues can be processed in parallel across shards.
</Aside>

## The Shard Structure

Each shard manages multiple named queues, each backed by an `IndexedPriorityQueue`, plus per-queue state handled by composed managers (DLQ, deduplication, rate limiting, dependencies, temporal index):

```typescript
class Shard {
  /** Priority queues by queue name */
  readonly queues = new Map<string, IndexedPriorityQueue>();

  /** Composed managers for per-queue state */
  private readonly uniqueKeyManager = new UniqueKeyManager();  // dedup with TTL
  private readonly dlqManager: DlqShard;                       // dead letter queue
  private readonly limiterManager = new LimiterManager();      // rate + concurrency
  private readonly dependencyTracker = new DependencyTracker();
  private readonly temporalManager = new TemporalManager();    // delayed jobs

  getQueue(name: string): IndexedPriorityQueue {
    let queue = this.queues.get(name);
    if (!queue) {
      queue = new IndexedPriorityQueue();
      this.queues.set(name, queue);
    }
    return queue;
  }
}
```

## Processing Shards: Separate Lock Domain

Active jobs (being processed by workers) are tracked in a separate set of **processing shards** with their own locking:

```typescript
// Processing shards use job ID hashing (not queue name)
function processingShardIndex(jobId: string): number {
  return fnv1a(jobId) & SHARD_MASK;
}
```

This separation is intentional. The lock hierarchy is strictly enforced:

1. `jobIndex` (read) -> 2. `completedJobs` (read) -> 3. `shards[N]` (write) -> 4. `processingShards[N]` (write)

Violating this order would create deadlocks.

## Performance Impact

Sharding delivers measurable throughput improvements on multi-core systems:

| Scenario | Single Shard | 4 Shards | 16 Shards |
|----------|-------------|----------|-----------|
| 1 worker, 1 queue | baseline | ~same | ~same |
| 4 workers, 4 queues | contention | ~3.5x | ~3.8x |
| 16 workers, 16 queues | high contention | ~8x | ~14x |

The gains come from reduced lock contention. With a single queue, all workers compete for one lock. With N shards, workers on different queues never contend.

## Key Design Decisions

**Queue-name sharding, not job-ID sharding.** All jobs for a queue live in one shard. This means a single queue can't benefit from sharding, but it dramatically simplifies the pull operation (no need to check multiple shards).

**Separate processing shards.** Active jobs are tracked separately from queued jobs. This prevents pull operations from blocking ack/fail operations.

**Static shard count.** Shards are created at startup and never change. This avoids the complexity of resharding and makes the hash-to-shard mapping immutable.