Range Sharding: Partitioning by Contiguous Key Ranges

In the physical world, organizing things by ranges feels intuitive—books on a library shelf arranged alphabetically, files in a cabinet sorted by date, customer records divided A-H, I-P, Q-Z. This natural ordering principle extends to database sharding through range sharding, a partitioning strategy that assigns data to shards based on contiguous ranges of the shard key.

Range sharding is one of the oldest and most widely understood sharding strategies. It offers powerful benefits for range-based queries while presenting unique challenges around hotspots and rebalancing. Understanding when to use range sharding—and when to avoid it—is essential knowledge for any database architect.

This page provides a comprehensive exploration of range sharding: its mechanics, advantages, pitfalls, and the operational realities of maintaining range-sharded systems in production.

In range sharding, the shard key space is divided into non-overlapping, contiguous ranges, with each range assigned to a specific shard. A routing table (shard map) maintains the mapping between ranges and shards.

Formal Definition:

Range sharding partitions a dataset such that records with shard key values in the range [Ri, Ri+1) are stored on shard Si. The complete set of ranges {[R0, R1), [R1, R2), ..., [Rn-1, ∞)} covers the entire key space with no gaps or overlaps.

Example Range Partition:

Routing Logic:

The routing algorithm for range sharding performs a range lookup:

def route_to_shard(key, range_map):
    """
    Find the shard for a given key using binary search on range boundaries.
    range_map: sorted list of (lower_bound, shard_id)
    """
    # Binary search for the largest lower_bound ≤ key
    for i in range(len(range_map) - 1, -1, -1):
        if key >= range_map[i].lower_bound:
            return range_map[i].shard_id
    raise ValueError(f"No range found for key: {key}")

Range Map Data Structure:

The range map is typically stored in a metadata service or configuration store, replicated to all routing components:

{
  "ranges": [
    { "lower": 1, "upper": 1000000, "shard": "shard-1" },
    { "lower": 1000000, "upper": 2000000, "shard": "shard-2" },
    { "lower": 2000000, "upper": 3000000, "shard": "shard-3" },
    { "lower": 3000000, "upper": null, "shard": "shard-4" }
  ]
}

Range sharding has specific characteristics that make it ideal for certain workloads. Understanding these sweet spots helps identify when range sharding is the right choice.

Use Case 1: Range Queries Are Primary Access Pattern

When most queries request data within a contiguous range of the shard key, range sharding enables single-shard or minimal-shard queries:

-- With range sharding by created_at (time buckets):
SELECT * FROM events 
WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31';

-- If January 2024 is entirely on Shard 5:
-- → Query hits ONLY Shard 5, not all shards!

Contrast with hash sharding where every range query becomes a scatter-gather across all shards.

Use Case 2: Ordered Data Processing

When data needs to be processed or scanned in order, range sharding preserves sort order within and across shards:

• Log processing pipelines
• Time-series compaction
• Sequential batch processing
• Merge operations across datasets

Use Case 3: Data Lifecycle Management

Range sharding enables efficient bulk operations on data segments:

-- Drop an entire shard when data expires
-- Instead of: DELETE FROM events WHERE created_at < '2023-01-01'
-- Simply: DROP SHARD shard_2023 (conceptually)

-- Or move historical shards to cheaper storage
ALTER SHARD shard_2023 SET STORAGE = 'cold_tier';

Use Case 4: Predictable Data Locality

When the application knows where data will land based on the key value, it can optimize accordingly:

• Pre-split ranges before bulk loads
• Route users to nearby shards geographically
• Co-schedule related processing on the same node

Range sharding's greatest vulnerability is hotspots—situations where one or more shards receive disproportionate traffic while others sit idle. Understanding hotspot causes and mitigations is essential for successful range sharding deployments.

Hotspot Cause 1: Monotonically Increasing Keys

The most infamous hotspot scenario occurs when the shard key increases monotonically (auto-increment IDs, timestamps):

Timeline:
- Day 1: Shard 1 receives ALL new writes (IDs 1-1M)
- Day 2: Shard 1 full, Shard 2 receives ALL new writes
- Day 3: Shard 2 receives ALL new writes
- ...
- Current: Whatever shard holds 'now' receives 100% of writes!

This creates a perpetual single-shard bottleneck for writes, completely defeating the purpose of sharding.

Hotspot Cause 2: Skewed Access Patterns

Even with uniform data distribution, access patterns may be skewed:

• Recent data accessed far more than old data
• Popular products/users in one range
• Events/promotions concentrating traffic

-- Data is evenly distributed across shards A-Z
-- But 90% of searches are for names A-C!
-- → Shards A, B, C are overwhelmed

Hotspot Cause 3: Poor Range Boundary Design

If ranges don't align with data density, some shards become overloaded:

• Equal-sized key ranges with unequal data per range
• Boundaries not accounting for growth patterns
• Static ranges that don't adapt to changing data

Effective range sharding requires thoughtful design of range boundaries. Poorly designed boundaries lead to imbalanced shards, hotspots, and frequent resharding. Well-designed boundaries enable smooth scaling and predictable performance.

Boundary Design Principles:

1. Size-Based Boundaries

Set boundaries so each shard holds approximately equal amounts of data:

def calculate_range_boundaries(total_keys, num_shards, key_distribution):
    """
    Calculate boundaries that give equal data per shard.
    Accounts for non-uniform key distribution.
    """
    target_per_shard = total_keys / num_shards
    boundaries = []
    cumulative = 0
    
    for key_value, count in key_distribution:
        cumulative += count
        if cumulative >= target_per_shard * (len(boundaries) + 1):
            boundaries.append(key_value)
    
    return boundaries

2. Traffic-Based Boundaries

In read-heavy systems, balance by query load rather than data volume:

-- Analyze query patterns to find traffic-balanced splits
SELECT 
    NTILE(4) OVER (ORDER BY user_id) AS proposed_shard,
    MIN(user_id) AS range_start,
    MAX(user_id) AS range_end,
    SUM(query_count) AS expected_traffic
FROM user_query_stats
GROUP BY proposed_shard;

3. Pre-Splitting for Anticipated Growth

Before bulk loads or known growth events, pre-split ranges:

# Before importing 10M new users (IDs 5M - 15M)
# Pre-split the receiving range into smaller chunks

original_ranges = [
    (1, 5_000_000, 'shard-1'),
    (5_000_000, float('inf'), 'shard-2'),  # Will receive 10M users!
]

pre_split_ranges = [
    (1, 5_000_000, 'shard-1'),
    (5_000_000, 7_500_000, 'shard-2'),
    (7_500_000, 10_000_000, 'shard-3'),
    (10_000_000, 12_500_000, 'shard-4'),
    (12_500_000, float('inf'), 'shard-5'),
]
# Load distributed across 4 new shards instead of 1

4. Automatic Split Detection

Monitor shard metrics and trigger splits when thresholds are exceeded:

Implementing range sharding requires careful attention to routing logic, metadata management, and handling edge cases. Here are production-tested patterns.

Pattern 1: Centralized Metadata with Cached Routing

Store authoritative range map in a metadata store (etcd, ZooKeeper, database). Routers cache the map locally and refresh periodically or on miss.

Pattern 2: Directory-Based Lookup Table

For very large number of ranges or complex routing logic, use a dedicated lookup table:

-- Range directory table
CREATE TABLE range_directory (
    range_id SERIAL PRIMARY KEY,
    lower_bound BIGINT NOT NULL,
    upper_bound BIGINT,  -- NULL for unbounded
    shard_id VARCHAR(50) NOT NULL,
    created_at TIMESTAMP DEFAULT NOW(),
    
    CONSTRAINT no_overlap CHECK (
        -- Enforced by application; complex to do in constraints
        TRUE
    )
);

CREATE INDEX idx_range_lookup ON range_directory (lower_bound);

-- Route a key
SELECT shard_id FROM range_directory
WHERE lower_bound <= 1500000
  AND (upper_bound IS NULL OR upper_bound > 1500000)
LIMIT 1;

Pattern 3: Consistent Hashing with Virtual Nodes (Hybrid)

For systems needing both range efficiency and automatic rebalancing, use consistent hashing with ordered virtual nodes:

Operating range-sharded systems requires ongoing attention to balance, performance, and evolution. Here are the key operational concerns and practices.

Monitoring and Alerting:

Range-sharded systems require specific metrics:

Rebalancing Strategies:

When shards become imbalanced, several strategies can restore equilibrium:

1. Range Splitting: Divide an oversized range into smaller ranges, each assigned to a different shard.

Before: Shard A owns [1, 1000000) — 80GB
After:  Shard A owns [1, 500000)   — 40GB
        Shard B owns [500000, 1000000) — 40GB

2. Range Merging: Combine adjacent underutilized ranges.

Before: Shard X owns [1000, 2000) — 1GB
        Shard Y owns [2000, 3000) — 1GB
After:  Shard X owns [1000, 3000) — 2GB

3. Range Migration: Move a range from one physical shard to another without changing boundaries.

# Move range [5000, 6000) from shard-3 to shard-7
1. Create replica of range on shard-7
2. Catch up to current state
3. Update routing to point to shard-7
4. Decommission range from shard-3

Schema Changes Across Shards:

DDL operations must be coordinated across all shards:

-- Adding a column requires:
-- 1. Apply to all shards (sequentially or in parallel)
-- 2. Handle partial failure scenarios
-- 3. Ensure application compatibility during rollout

-- Options:
-- a) Online DDL with compatibility window
-- b) Ghost tables / shadow table approach
-- c) Database-specific online schema change tools (pt-osc, gh-ost)

Backup and Recovery:

• Each shard should be backed up independently
• Point-in-time recovery requires coordinated timestamps across shards
• Test recovery procedures regularly for each shard
• Document shard dependencies and recovery order

Range sharding and hash sharding represent fundamentally different tradeoffs. Understanding when to use each is essential for system design.

Comprehensive Comparison:

Decision Framework: