database-sharding

Comprehensive database sharding patterns for horizontal scaling with hash, range, and directory-based strategies.

Quick Start (10 Minutes)

Step 1: Choose sharding strategy from templates:

# Hash-based (even distribution)
cat templates/hash-router.ts

# Range-based (time-series data)
cat templates/range-router.ts

# Directory-based (multi-tenancy)
cat templates/directory-router.ts

Step 2: Select shard key criteria:

• ✅ High cardinality (millions of unique values)
• ✅ Even distribution (no single value > 5%)
• ✅ Immutable (never changes)
• ✅ Query alignment (in 80%+ of WHERE clauses)

Step 3: Implement router:

import { HashRouter } from './hash-router';

const router = new HashRouter([
  { id: 'shard_0', connection: { host: 'db0.example.com' } },
  { id: 'shard_1', connection: { host: 'db1.example.com' } },
  { id: 'shard_2', connection: { host: 'db2.example.com' } },
  { id: 'shard_3', connection: { host: 'db3.example.com' } },
]);

// Query single shard
const user = await router.query('user_123', 'SELECT * FROM users WHERE id = $1', ['user_123']);

Critical Rules

✓ Always Do

✗ Never Do

Top 7 Critical Errors

Error 1: Wrong Shard Key Choice (Hotspots)

Symptom: One shard receives 80%+ of traffic Fix:

// ❌ Bad: Low cardinality (status field)
shard_key = order.status; // 90% are 'pending' → shard_0 overloaded

// ✅ Good: High cardinality (user_id)
shard_key = order.user_id; // Millions of users, even distribution

Error 2: Missing Shard Key in Queries

Symptom: Queries scan ALL shards (extremely slow) Fix:

// ❌ Bad: No shard key
SELECT * FROM orders WHERE status = 'shipped'; // Scans all 100 shards!

// ✅ Good: Include shard key
SELECT * FROM orders WHERE user_id = ? AND status = 'shipped'; // Targets 1 shard

Error 3: Sequential IDs with Range Sharding

Symptom: Latest shard gets all writes Fix:

// ❌ Bad: Range sharding with auto-increment
// Shard 0: 1-1M, Shard 1: 1M-2M, Shard 2: 2M+ → All new writes to Shard 2!

// ✅ Good: Hash-based sharding
const shardId = hash(id) % shardCount; // Even distribution

Error 4: No Rebalancing Strategy

Symptom: Stuck with initial shard count, cannot scale Fix:

// ❌ Bad: Simple modulo
const shardId = hash(key) % shardCount; // Adding 5th shard breaks ALL keys

// ✅ Good: Consistent hashing
const ring = new ConsistentHashRing(shards);
const shardId = ring.getNode(key); // Only ~25% of keys move when adding shard

Error 5: Cross-Shard Transactions

Symptom: Data inconsistency, partial writes Fix:

// ❌ Bad: Cross-shard transaction (will corrupt)
BEGIN;
UPDATE shard_1.accounts SET balance = balance - 100 WHERE id = 'A';
UPDATE shard_2.accounts SET balance = balance + 100 WHERE id = 'B';
COMMIT; // If shard_2 fails, shard_1 already committed!

// ✅ Good: Two-Phase Commit or Saga pattern
const txn = new TwoPhaseCommitTransaction();
txn.addOperation(shard_1, 'UPDATE accounts SET balance = balance - 100 WHERE id = ?', ['A']);
txn.addOperation(shard_2, 'UPDATE accounts SET balance = balance + 100 WHERE id = ?', ['B']);
await txn.execute(); // Atomic across shards

Error 6: Mutable Shard Key

Symptom: Records move shards, causing duplicates Fix:

// ❌ Bad: Shard by country (user relocates)
shard_key = user.country; // User moves US → CA, now in different shard!

// ✅ Good: Shard by immutable user_id
shard_key = user.id; // Never changes

Error 7: No Monitoring

Symptom: Silent hotspots, sudden performance degradation Fix:

// ✅ Required metrics
- Per-shard record counts (should be within 20%)
- Query distribution (no shard > 40% of queries)
- Storage per shard (alert at 80%)
- Latency p99 per shard

Load references/error-catalog.md for all 10 errors with detailed fixes.

Sharding Strategies

Load references/sharding-strategies.md for detailed comparisons with production examples (Instagram, Discord, Salesforce).

Shard Key Selection Criteria

Decision Tree:

• User-focused app → user_id
• Multi-tenant SaaS → tenant_id
• Time-series/logs → timestamp (range sharding)
• Product catalog → product_id

Load references/shard-key-selection.md for comprehensive decision trees and testing strategies.

Configuration Summary

Hash-Based Router

import { HashRouter } from './templates/hash-router';

const router = new HashRouter([
  { id: 'shard_0', connection: { /* PostgreSQL config */ } },
  { id: 'shard_1', connection: { /* PostgreSQL config */ } },
]);

// Automatically routes to correct shard
const user = await router.query('user_123', 'SELECT * FROM users WHERE id = $1', ['user_123']);

Range-Based Router

import { RangeRouter } from './templates/range-router';

const router = new RangeRouter(shardConfigs, [
  { start: Date.parse('2024-01-01'), end: Date.parse('2024-04-01'), shardId: 'shard_q1' },
  { start: Date.parse('2024-04-01'), end: Date.parse('2024-07-01'), shardId: 'shard_q2' },
  { start: Date.parse('2024-07-01'), end: Infinity, shardId: 'shard_q3' },
]);

// Range queries target specific shards
const janEvents = await router.queryRange(
  Date.parse('2024-01-01'),
  Date.parse('2024-02-01'),
  'SELECT * FROM events WHERE created_at BETWEEN $1 AND $2'
);

Directory-Based Router

import { DirectoryRouter } from './templates/directory-router';

const router = new DirectoryRouter(directoryDBConfig, shardConfigs);

// Assign tenant to specific shard
await router.assignShard('tenant_acme', 'shard_enterprise');

// Route automatically
const users = await router.query('tenant_acme', 'SELECT * FROM users');

When to Load References

Choosing Strategy

Load references/sharding-strategies.md when:

• Deciding between hash, range, directory
• Need production examples (Instagram, Discord)
• Planning hybrid approaches

Selecting Shard Key

Load references/shard-key-selection.md when:

• Choosing shard key for new project
• Evaluating existing shard key
• Testing distribution with production data

Implementation

Load references/implementation-patterns.md when:

• Building shard router from scratch
• Implementing consistent hashing
• Need transaction handling (2PC, Saga)
• Setting up monitoring/metrics

Cross-Shard Operations

Load references/cross-shard-queries.md when:

• Need to aggregate across shards (COUNT, SUM, AVG)
• Implementing cross-shard joins
• Building pagination across shards
• Optimizing scatter-gather patterns

Rebalancing

Load references/rebalancing-guide.md when:

• Adding new shards
• Migrating data between shards
• Planning zero-downtime migrations
• Balancing uneven load

Error Prevention

Load references/error-catalog.md when:

• Troubleshooting performance issues
• Reviewing shard architecture
• All 10 documented errors with fixes

Complete Setup Checklist

Before Sharding:

• Tested shard key distribution with production data
• Shard key in 80%+ of queries
• Monitoring infrastructure ready
• Rebalancing strategy planned

Router Implementation:

• Shard routing layer (not hardcoded shards)
• Connection pooling per shard
• Error handling and retries
• Metrics collection (queries/shard, latency)

Shard Configuration:

• 4-8 shards initially (room to grow)
• Consistent hashing or virtual shards
• Replicas per shard (HA)
• Backup strategy per shard

Application Changes:

• All queries include shard key
• Cross-shard joins eliminated (denormalized)
• Transaction boundaries respected
• Connection pooling configured

Production Example

Before (Single database overwhelmed):

// Single PostgreSQL instance
const db = new Pool({ host: 'db.example.com' });

// All 10M users on one server
const users = await db.query('SELECT * FROM users WHERE status = $1', ['active']);
// Query time: 5000ms (slow!)
// DB CPU: 95%
// Disk: 500GB, growing

After (Sharded across 8 servers):

// Hash-based sharding with 8 shards
const router = new HashRouter([
  { id: 'shard_0', connection: { host: 'db0.example.com' } },
  { id: 'shard_1', connection: { host: 'db1.example.com' } },
  // ... 6 more shards
]);

// Query single user (targets 1 shard)
const user = await router.query('user_123', 'SELECT * FROM users WHERE id = $1', ['user_123']);
// Query time: 10ms (500x faster!)

// Query all shards (scatter-gather)
const allActive = await router.queryAll('SELECT * FROM users WHERE status = $1', ['active']);
// Query time: 800ms (parallelized across 8 shards, 6x faster than single)

// Result: Each shard handles ~1.25M users
// DB CPU per shard: 20%
// Disk per shard: 65GB
// Can scale to 16 shards easily (consistent hashing)

Known Issues Prevention

All 10 documented errors prevented:

1. ✅ Wrong shard key (hotspots) → Test distribution first
2. ✅ Missing shard key in queries → Code review, linting
3. ✅ Cross-shard transactions → Use 2PC or Saga pattern
4. ✅ Sequential ID hotspots → Use hash-based sharding
5. ✅ No rebalancing strategy → Consistent hashing from day 1
6. ✅ Timestamp sharding hotspots → Hybrid hash+range approach
7. ✅ Mutable shard key → Choose immutable keys (user_id)
8. ✅ No routing layer → Abstract with router from start
9. ✅ No monitoring → Track per-shard metrics
10. ✅ Weak hash function → Use MD5, MurmurHash3, xxHash

See: references/error-catalog.md for detailed fixes

Resources

Templates:

• templates/hash-router.ts - Hash-based sharding
• templates/range-router.ts - Range-based sharding
• templates/directory-router.ts - Directory-based sharding
• templates/cross-shard-aggregation.ts - Aggregation patterns

References:

• references/sharding-strategies.md - Strategy comparison
• references/shard-key-selection.md - Key selection guide
• references/implementation-patterns.md - Router implementations
• references/cross-shard-queries.md - Query patterns
• references/rebalancing-guide.md - Migration strategies
• references/error-catalog.md - All 10 errors documented

Production Examples:

• Instagram: Range sharding for media
• Discord: Hash sharding for messages
• Salesforce: Directory sharding for orgs

Production-tested | 10 errors prevented | MIT License