What Are the Main Data Partitioning Strategies?
Compare range, hash, and directory-based data partitioning strategies, their hot spot risks, and how each affects query performance.
Expected Interview Answer
Data partitioning splits a large dataset across multiple nodes using a strategy such as range partitioning (contiguous key ranges per node), hash partitioning (a hash function maps keys to nodes), or directory-based partitioning (a lookup service tracks which node owns which key), each trading off query efficiency, load balance, and rebalancing cost differently.
Range partitioning keeps keys in sorted order per partition, which makes range scans fast but risks hot spots when writes cluster around one range (like sequential IDs or timestamps). Hash partitioning spreads keys evenly by hashing the partition key, avoiding hot spots for random access but making range queries expensive since related keys scatter across nodes. Directory-based partitioning uses an explicit lookup table mapping keys or key ranges to nodes, offering maximum flexibility for custom placement and rebalancing at the cost of an extra lookup hop and a potential single point of contention on the directory itself. In practice, systems often combine a hash of a partition key with range partitioning within that hash bucket (composite keys), balancing even distribution with efficient scans over related data.
- Range partitioning enables efficient sorted scans and range queries
- Hash partitioning evens out load and avoids hot spots for point lookups
- Directory-based partitioning gives fine-grained control for custom rebalancing
- Composite (hash + range) strategies combine even distribution with efficient local scans
AI Mentor Explanation
Range partitioning is like organizing a scorebook by match date ranges, so browsing an entire series in order is fast, but if every team plays its matches in the same week, that shelf gets overloaded while others sit empty. Hash partitioning is like assigning each match to a shelf based on a hash of the team names, spreading matches evenly regardless of when they were played, but now finding every match in March means checking every shelf. Directory-based partitioning is like keeping a separate ledger that explicitly records which shelf holds which match, giving full control over placement at the cost of checking that ledger first. Choosing between them means weighing fast ordered browsing against even shelf load and flexible control.
Step-by-Step Explanation
Step 1
Choose a partition key
Pick a key that reflects real access patterns, such as user ID, tenant ID, or a composite key.
Step 2
Pick a partitioning strategy
Use range partitioning for ordered scans, hash partitioning for even load, or directory-based for custom control.
Step 3
Route requests to the owning partition
A routing layer (client library, proxy, or coordinator) maps each request to the correct node using the chosen scheme.
Step 4
Rebalance as data grows
Split hot range partitions, add hash buckets and remap via consistent hashing, or update the directory as nodes are added or removed.
What Interviewer Expects
- Names at least range, hash, and directory-based partitioning and their trade-offs
- Explains hot spot risk in range partitioning and how hash partitioning mitigates it
- Recognizes that hash partitioning makes range queries expensive
- Mentions rebalancing strategy (splitting ranges, consistent hashing, or directory updates)
Common Mistakes
- Assuming one partitioning strategy is universally best regardless of query patterns
- Ignoring hot spots created by sequential keys under range partitioning
- Forgetting that hash partitioning breaks efficient range scans
- Not discussing how rebalancing happens as data or traffic grows
Best Answer (HR Friendly)
“Data partitioning means splitting a large dataset across multiple servers so no single machine has to hold or serve all of it. You can split by ranges of values for fast ordered access, by a hash of the key for even load, or through a lookup directory for full control, and each option makes different trade-offs between query speed and balance.”
Code Example
def range_partition(key, boundaries):
# boundaries is a sorted list of range upper bounds
for i, upper in enumerate(boundaries):
if key <= upper:
return i
return len(boundaries)
def hash_partition(key, num_partitions):
return hash(key) % num_partitions
class DirectoryPartitioner:
def __init__(self):
self.directory = {} # key_range -> node_id
def assign(self, key_range, node_id):
self.directory[key_range] = node_id
def lookup(self, key):
for key_range, node_id in self.directory.items():
if key_range[0] <= key <= key_range[1]:
return node_id
raise KeyError("no partition owns this key")Follow-up Questions
- How would you rebalance a range-partitioned system that develops a hot partition?
- Why does hash partitioning make it expensive to run range queries?
- How does consistent hashing relate to hash-based partitioning at scale?
- When would you choose directory-based partitioning over range or hash partitioning?
MCQ Practice
1. Which partitioning strategy is most prone to hot spots from sequential keys like auto-incrementing IDs?
Sequential keys all land in the same or adjacent range under range partitioning, concentrating writes on one partition.
2. What is the main downside of hash partitioning for query patterns?
Hashing scatters related, adjacent keys across different partitions, so range queries must fan out to every partition.
3. What extra component does directory-based partitioning require compared to hash partitioning?
Directory-based partitioning relies on an explicit mapping service that must be consulted before routing a request to a node.
Flash Cards
Range partitioning strength? — Efficient ordered scans and range queries over contiguous keys.
Range partitioning weakness? — Hot spots when writes cluster around sequential keys like timestamps or auto-increment IDs.
Hash partitioning trade-off? — Even load distribution for point lookups, but expensive range queries since related keys scatter.
Directory-based partitioning? — An explicit lookup table maps keys/ranges to nodes, giving flexible custom placement at the cost of an extra hop.