Partitioning Strategy Advisor

Partitioning Strategy Advisor

When to Use

You are designing or evaluating a distributed database where data must be spread across multiple nodes (sharding) and need to select a partitioning key, a partitioning method, secondary index approach, rebalancing configuration, and request routing topology.

This skill applies when the partitioning scheme is open (new system), problematic (existing system with hotspots or unsupported query patterns), or needs documented justification (architecture decision record, team alignment). It produces a concrete recommendation covering partition key choice, range vs. hash vs. compound method, secondary index strategy, rebalancing approach, and routing topology.

Prerequisite check:

Context & Input Gathering

Required Context (must have — ask if missing)

1. Primary access pattern — how records are most frequently looked up

Why: The access pattern determines what the partition key must be. If records are always looked up by a single primary key (user ID, order ID), hashing that key achieves even distribution. If records are frequently fetched in sorted ranges (sensor readings by time, events by date), range partitioning on that key enables efficient range scans. Choosing the wrong key forces scatter/gather reads or hot single partitions on every query.

2. Write distribution characteristics — is the natural key monotonically increasing?

Why: Monotonically increasing keys (timestamps, auto-increment IDs, sequential order numbers) create sequential write patterns that concentrate all writes on the latest partition in range partitioning. This is the most common hotspot source. Even under hash partitioning, extremely popular individual keys (celebrity users, viral content IDs) can overwhelm a single partition. Understanding write distribution is required before selecting a partition key.

3. Secondary query requirements — does the application filter on non-primary-key attributes?

Why: Secondary indexes on partitioned data require a choice between document-partitioned (local) and term-partitioned (global) indexes. This choice forces a fundamental trade-off: local indexes are cheap to write (only the local partition is updated) but expensive to read (scatter/gather across all partitions). Global indexes are cheap to read (single partition lookup) but expensive to write (updates span multiple partition index entries, often asynchronously). You must know which queries are required before designing the index strategy.

4. Data volume and growth trajectory

Why: Affects rebalancing strategy selection. If total data volume is small and known, a fixed number of partitions sized correctly upfront is simplest. If data will grow significantly over time, dynamic partitioning (split/merge) adapts partition count automatically. If the cluster will scale out by adding nodes, proportional-to-nodes partitioning keeps partition size stable. Choosing a fixed partition count that's too small locks out future growth; too large creates excessive overhead.

5. Target database

Why: Different databases implement partitioning in fundamentally different ways — HBase and RethinkDB use dynamic key-range partitioning; Cassandra and Riak use hash partitioning with proportional-to-nodes rebalancing; Elasticsearch uses fixed-partition hash sharding; MongoDB supports both. The recommendation must fit what the target database actually supports. Additionally, Cassandra's compound primary key pattern is only available in Cassandra.

Optional Context (enriches recommendation)

Process

Step 1 — Classify Data Distribution Risk

Categorize the workload's skew profile before selecting any partitioning method.

Why: Partitioning is only useful if load is evenly distributed. A poorly chosen partition key can negate all the benefits of horizontal scaling by concentrating all reads or writes on one node (a hotspot). Identifying skew risk upfront determines whether extra mitigation (key prefixing, salting, compound keys) is needed on top of the base partitioning method.

Classify into one of three profiles:

| Profile | Signal | Risk | |---|---|---| | Monotonic key | Timestamps, sequential IDs, auto-increment PKs | All writes go to the single "latest" partition under range partitioning | | Celebrity key | A small number of keys receive orders of magnitude more traffic (viral content, celebrity users) | Single partition overloaded even under hash partitioning | | Uniform key | Random UUIDs, user IDs with no natural ordering, hashed values | Low hotspot risk; both range and hash partitioning are viable |

Mitigation for monotonic keys (range partitioning): Prefix the timestamp with a high-cardinality dimension (e.g., sensor name + timestamp, or user ID + timestamp). This distributes writes across the key space while preserving range-scan ability within each prefix bucket.

Mitigation for celebrity keys (hash partitioning): Append a two-digit random suffix (00–99) to the hot key at write time. This splits writes across 100 partitions. Reads must then query all 100 suffix variants and merge — track which keys are "hot" in a separate lookup table to apply this only where needed.

Step 2 — Select Partitioning Method

Choose range partitioning, hash partitioning, or compound key (hybrid) based on access patterns and skew profile.

Why: This is the central decision. Range partitioning preserves sort order, enabling efficient range scans but requiring careful key design to avoid hotspots. Hash partitioning destroys sort order (making range queries require scatter/gather) but distributes load evenly. Compound keys (Cassandra model) combine both — hashing on the first part distributes across partitions, sorting within the partition on the remaining parts supports range scans within a single partition.

Decision framework:

PRIMARY ACCESS PATTERN
├── Range queries are critical (fetch records within a time window,
│   scan sorted ranges, support range-based pagination)
│   ├── Key is monotonically increasing → RANGE with prefix mitigation
│   │   Example: (sensor_name, timestamp) compound range key
│   └── Key has natural, non-monotonic distribution → RANGE partitioning
│       Example: alphabetically distributed last names (encyclopedia volumes)
│
├── Point lookups dominate (fetch a single record by ID) AND
│   range queries are not needed
│   → HASH partitioning
│   Example: user profiles by user_id, order records by order_id
│
└── Point lookups on partition key AND range queries within that key
    → COMPOUND KEY (hash partition key + range sort key)
    Example: (user_id [hash], update_timestamp [range]) in Cassandra
    → Efficiently fetch all updates for a user, sorted by time,
       in a single partition lookup

Range partitioning: Used by Bigtable, HBase, RethinkDB, MongoDB (pre-2.4). Partition boundaries must adapt to data distribution — automatic boundary management (dynamic partitioning) is strongly preferred over manually configured boundaries to avoid under/over-filled partitions.

Hash partitioning: Used by Cassandra, Riak, Voldemort, MongoDB (hash mode). The hash function must be stable across processes — language-native hash functions (Java's Object.hashCode(), Ruby's Object#hash) are not safe for this purpose because they can return different values in different processes. Use a purpose-built stable function: Cassandra and MongoDB use MD5, Voldemort uses Fowler-Noll-Vo. Assign each partition a range of hash values (not hash mod N — see rebalancing step).

Compound key (Cassandra): The partition key (first component) is hashed to determine the partition. The clustering columns (remaining components) determine sort order within the partition. A query that fixes the partition key can perform an efficient range scan over the clustering columns without touching other partitions. This is the primary pattern for one-to-many relationships in Cassandra: (user_id, post_timestamp) stores all posts for a user in one partition, sorted by time.

Step 3 — Design the Secondary Index Strategy

If the application requires queries on non-primary-key attributes, choose between document-partitioned (local) and term-partitioned (global) secondary indexes.

Why: Secondary indexes do not map cleanly to partitions. The choice of local vs. global index makes a fundamental trade-off between write cost and read cost that cannot be undone without a full reindex. Making this decision explicitly — and documenting it — prevents later surprises when a secondary index query turns out to require scatter/gather across every partition in the cluster.

Document-partitioned (local) index:

Term-partitioned (global) index:

Index partition boundary choice (for global indexes):

Step 4 — Select Rebalancing Approach

Choose fixed-partition, dynamic, or proportional-to-nodes rebalancing.

Why: As data grows and nodes are added or removed, partitions must be redistributed. The rebalancing strategy determines how disruptive this is, how much data moves, and how much operational overhead it requires. Using hash mod N — the naive approach — is explicitly wrong: it causes the vast majority of keys to move when N changes, making rebalancing catastrophically expensive.

Fixed number of partitions:

Dynamic partitioning:

Proportional to nodes:

Automatic vs. manual rebalancing:

Step 5 — Select Request Routing Approach

Choose how clients discover which node owns a given partition.

Why: As partitions rebalance, the mapping from partition to node changes. Clients or proxies must track these changes to route requests to the correct node. Using stale routing metadata results in forwarded requests (extra latency), re-tried requests, or errors. The routing approach must match the database's coordination model.

Three options:

Option 1 — Any-node with forwarding (gossip-based):

Option 2 — Routing tier (coordination service):

Option 3 — Partition-aware client:

What Can Go Wrong

Hotspot from monotonically increasing write key The most common partitioning failure. A table keyed on created_at, id SERIAL, or any auto-increment column with range partitioning sends 100% of writes to the partition covering the current moment. The newest partition is overloaded while all others sit idle. Fix: Switch to compound key with a high-cardinality prefix, or switch to hash partitioning if range queries are not needed. For time-series with range-query requirements, use (source_id, timestamp) compound range key.

Scatter/gather latency on secondary index queries Document-partitioned (local) secondary indexes require querying all partitions. With 100 partitions, the query waits for the slowest of 100 responses (tail latency amplification). Secondary index queries that were fast in a single-node database become 10–100x slower after partitioning. Fix: If secondary index reads are frequent and latency-sensitive, switch to a global (term-partitioned) index and accept asynchronous write propagation. Alternatively, structure the primary partition key to co-locate records that will be queried together (e.g., partition by tenant_id if secondary queries are always within a tenant).

Rebalancing storm from automatic rebalancing + false-positive failure detection A temporarily overloaded node responds slowly. Other nodes declare it dead. Automatic rebalancing begins moving its partitions to other nodes. The extra rebalancing traffic overloads the already-struggling node further. The added load on other nodes triggers further detection false-positives. Fix: Use semi-automatic (operator-approved) rebalancing in production. Tune failure detection timeouts conservatively. Set rebalancing rate limits to bound the bandwidth consumed during rebalancing.

Wrong partition count with fixed-partition scheme Fixed partitions chosen at setup cannot be changed later (in databases that do not support dynamic partitioning). Too few partitions caps how many nodes can be added. Too many creates excessive per-partition overhead. Choosing 10 partitions for a system that grows to 100 nodes means 10 nodes must carry the entire load. Fix: For fixed-partition systems, choose initial partition count 10–20x the expected maximum node count. For variable-growth scenarios, prefer dynamic partitioning.

Language-native hash functions used for partitioning Java's Object.hashCode() and Ruby's Object#hash return different values for the same string in different JVM processes (randomization is intentional for security). Using these for partitioning produces incorrect routing — the partition computed at write time differs from the partition computed at read time. Fix: Use a purpose-built stable hash function: MD5 (Cassandra, MongoDB), Fowler-Noll-Vo (Voldemort), MurmurHash, or similar. Verify hash stability across process restarts before deploying.

Stale routing metadata causes misrouted requests If routing metadata is cached client-side and not refreshed after rebalancing, requests are sent to nodes that no longer own the target partition. The node either returns an error or silently returns stale data. Fix: Use a routing approach that subscribes to partition assignment changes (ZooKeeper watches, gossip convergence). Test routing after every rebalancing event. Implement retry-with-redirect at the client layer.

Examples

Example 1 — IoT sensor time-series platform

Scenario: Storing sensor readings where each reading has (sensor_id, timestamp, value). Queries: fetch all readings for a sensor within a date range; write throughput is high and continuous.

Trigger: "We're building a sensor data platform on HBase. Our current key is just the timestamp, and we're seeing one region server getting all the writes."

Process: 1. Skew classification: Monotonic key — timestamp as the sole partition key causes all writes to go to the "now" partition. 2. Method selection: Range partitioning is required (range scans by date are the primary read pattern). Apply compound range key with sensor name as prefix: key = (sensor_name, timestamp). 3. Secondary index: None required — all queries fix sensor_name (partition prefix) and scan a timestamp range within the partition. 4. Rebalancing: Dynamic partitioning (HBase default). Pre-split with known sensor names to avoid cold-start single-partition writes. 5. Routing: ZooKeeper-based routing tier (HBase default via HMaster).

Output: Compound range key (sensor_name, timestamp). All writes for a sensor go to the same partition, distributed across sensors. Range queries within a sensor are efficient single-partition scans. Dynamic rebalancing handles data growth.

Example 2 — Social media post feed (Cassandra)

Scenario: Storing user posts where queries are: "fetch all posts by user X sorted by time" (dominant) and "fetch a single post by post_id" (secondary). Write pattern: each user writes to their own posts; no cross-user write conflicts.

Trigger: "We're modeling user posts in Cassandra. We need to efficiently retrieve all posts by a user, sorted from newest to oldest, but we also need to look up individual posts by ID."

Process: 1. Skew classification: User ID as partition key is approximately uniform (assuming large user base). No celebrity-user mitigation needed unless specific users are known to be viral. 2. Method selection: Compound key pattern — user_id as hash partition key (evenly distributes users across nodes), post_timestamp DESC as clustering column (sorts posts within the partition, newest first). 3. Secondary index: Post-by-ID lookup can be handled by a separate table keyed on post_id (denormalization, Cassandra idiom) rather than a secondary index, avoiding scatter/gather entirely. 4. Rebalancing: Proportional-to-nodes (Cassandra default, 256 vnodes/node). Automatic with gossip-based partition assignment. 5. Routing: Gossip protocol with token-aware driver (Cassandra default). No ZooKeeper dependency.

Output: Compound primary key (user_id, post_timestamp DESC). Fetching all posts by user is a single-partition range scan. Individual post lookup uses a separate posts_by_id table. Scales horizontally by adding Cassandra nodes.

Example 3 — E-commerce product catalog with multi-attribute search

Scenario: Product records with attributes (product_id, category, color, price). Queries: look up by product_id (dominant write target), filter by category + color (secondary index query), filter by price range (secondary index query).

Trigger: "We have 50 million products partitioned by product_id hash across 20 Elasticsearch shards. Our 'filter by category and color' queries are slow and getting slower as we add shards."

Process: 1. Skew classification: product_id hash partitioning is uniform — no hotspot risk on writes. 2. Method selection: Hash partitioning on product_id is correct for primary key lookups. Do not change this. 3. Secondary index analysis: Elasticsearch uses document-partitioned (local) indexes by default. The category + color filter query is scatter/gathered across all 20 shards. Query latency scales with shard count. 4. Secondary index strategy: Two options: - If category queries are always within a tenant/store, consider routing documents by (store_id, product_id) compound key to co-locate products from the same store, reducing scatter/gather to intra-store shards. - If global catalog search is required, accept scatter/gather and optimize by reducing shard count (fewer, larger shards perform better for scatter/gather than many small shards) or pre-aggregate category+color facets. 5. Rebalancing: Fixed partitions (Elasticsearch uses fixed shard count). Choose initial shard count = projected node count × 2–3. Do not over-shard. 6. Routing: Elasticsearch coordinator node (partition-aware proxy, equivalent to routing tier option).

Output: Keep hash partitioning on product_id. Accept scatter/gather for secondary index queries — this is the Elasticsearch design. Reduce total shard count to the minimum needed; over-sharding amplifies scatter/gather cost. Add replica shards for read scaling on hot index queries.

Cross-References

References

See references/ for:

License

This skill is licensed under CC-BY-SA-4.0. Source: BookForge — Designing Data-Intensive Applications by Martin Kleppmann.

Related BookForge Skills

Install related skills from ClawhHub:

Or install the full book set from GitHub: bookforge-skills

Example 1 — IoT sensor time-series platform

Scenario: Storing sensor readings where each reading has (sensor_id, timestamp, value). Queries: fetch all readings for a sensor within a date range; write throughput is high and continuous.

Trigger: "We're building a sensor data platform on HBase. Our current key is just the timestamp, and we're seeing one region server getting all the writes."

Process: 1. Skew classification: Monotonic key — timestamp as the sole partition key causes all writes to go to the "now" partition. 2. Method selection: Range partitioning is required (range scans by date are the primary read pattern). Apply compound range key with sensor name as prefix: key = (sensor_name, timestamp). 3. Secondary index: None required — all queries fix sensor_name (partition prefix) and scan a timestamp range within the partition. 4. Rebalancing: Dynamic partitioning (HBase default). Pre-split with known sensor names to avoid cold-start single-partition writes. 5. Routing: ZooKeeper-based routing tier (HBase default via HMaster).

Output: Compound range key (sensor_name, timestamp). All writes for a sensor go to the same partition, distributed across sensors. Range queries within a sensor are efficient single-partition scans. Dynamic rebalancing handles data growth.

Example 2 — Social media post feed (Cassandra)

Scenario: Storing user posts where queries are: "fetch all posts by user X sorted by time" (dominant) and "fetch a single post by post_id" (secondary). Write pattern: each user writes to their own posts; no cross-user write conflicts.

Trigger: "We're modeling user posts in Cassandra. We need to efficiently retrieve all posts by a user, sorted from newest to oldest, but we also need to look up individual posts by ID."

Process: 1. Skew classification: User ID as partition key is approximately uniform (assuming large user base). No celebrity-user mitigation needed unless specific users are known to be viral. 2. Method selection: Compound key pattern — user_id as hash partition key (evenly distributes users across nodes), post_timestamp DESC as clustering column (sorts posts within the partition, newest first). 3. Secondary index: Post-by-ID lookup can be handled by a separate table keyed on post_id (denormalization, Cassandra idiom) rather than a secondary index, avoiding scatter/gather entirely. 4. Rebalancing: Proportional-to-nodes (Cassandra default, 256 vnodes/node). Automatic with gossip-based partition assignment. 5. Routing: Gossip protocol with token-aware driver (Cassandra default). No ZooKeeper dependency.

Output: Compound primary key (user_id, post_timestamp DESC). Fetching all posts by user is a single-partition range scan. Individual post lookup uses a separate posts_by_id table. Scales horizontally by adding Cassandra nodes.

Example 3 — E-commerce product catalog with multi-attribute search

Scenario: Product records with attributes (product_id, category, color, price). Queries: look up by product_id (dominant write target), filter by category + color (secondary index query), filter by price range (secondary index query).

Trigger: "We have 50 million products partitioned by product_id hash across 20 Elasticsearch shards. Our 'filter by category and color' queries are slow and getting slower as we add shards."

Process: 1. Skew classification: product_id hash partitioning is uniform — no hotspot risk on writes. 2. Method selection: Hash partitioning on product_id is correct for primary key lookups. Do not change this. 3. Secondary index analysis: Elasticsearch uses document-partitioned (local) indexes by default. The category + color filter query is scatter/gathered across all 20 shards. Query latency scales with shard count. 4. Secondary index strategy: Two options: - If category queries are always within a tenant/store, consider routing documents by (store_id, product_id) compound key to co-locate products from the same store, reducing scatter/gather to intra-store shards. - If global catalog search is required, accept scatter/gather and optimize by reducing shard count (fewer, larger shards perform better for scatter/gather than many small shards) or pre-aggregate category+color facets. 5. Rebalancing: Fixed partitions (Elasticsearch uses fixed shard count). Choose initial shard count = projected node count × 2–3. Do not over-shard. 6. Routing: Elasticsearch coordinator node (partition-aware proxy, equivalent to routing tier option).

Output: Keep hash partitioning on product_id. Accept scatter/gather for secondary index queries — this is the Elasticsearch design. Reduce total shard count to the minimum needed; over-sharding amplifies scatter/gather cost. Add replica shards for read scaling on hot index queries.