Chapter 6: Partitioning

Core Concepts #

Why Partitioning? #

• Data too large for single machine
• Query throughput exceeds single machine's capacity
• Horizontal scalability

Two Main Approaches #

1. Key-range partitioning: Assign contiguous key ranges
2. Hash partitioning: Use hash function to determine partition

---

Partitioning Strategies #

Partitioning by Hash of Key #

Concept: Use hash function to determine partition

Advantages:

• Distributes load evenly
• Handles hotspots well
• Simple to implement

Disadvantages:

• Loses key ordering
• Range queries require scanning all partitions

Consistent Hashing:

• Minimize key redistribution when nodes added/removed
• Used in DynamoDB, Cassandra

Partitioning by Key Range #

Concept: Assign contiguous key ranges to partitions

Advantages:

• Preserves key ordering
• Efficient range queries
• Simple to understand

Disadvantages:

• Risk of hotspots (sequential keys)
• May need to rebalance ranges

Used by: HBase, MongoDB, RethinkDB

Rebalancing #

Automatic Rebalancing:

• System automatically moves data when nodes added/removed
• Challenge: Minimize data movement
• Solution: Consistent hashing or proportional partitioning

---

Secondary Indexes #

Partitioning Secondary Indexes by Document #

Concept: Each partition has its own secondary index

Write: Update all partitions (scatter-gather) Read: Query all partitions, merge results

Disadvantages: Slow reads across partitions

Partitioning Secondary Indexes by Term #

Concept: Secondary index partitioned by term, not document

Write: Update only affected partitions Read: Query single partition

Advantages: Efficient reads Disadvantages: Writes span multiple partitions

---

Request Routing #

Approaches #

1. Client-side: Client knows partition locations
2. Routing tier: Single routing service
3. Partition-aware: Client connects directly

Service Discovery #

• ZooKeeper for tracking cluster membership
• Partition assignment algorithms
• Handling node failures

---

Transactions in Distributed Systems #

The Challenge #

• Data spread across multiple partitions
• Need atomic operations across partitions
• Failure handling becomes complex

Single-Partition Transactions #

• Simple: Lock, modify, unlock
• Fast and efficient

Multi-Partition Transactions #

• Two-Phase Commit (2PC): Coordinator + participants
• Three-Phase Commit (3PC): Attempt to reduce blocking
• Percolator: Google's approach using single leader

---

Key Takeaways #

1. Hash partitioning distributes load evenly but loses ordering
2. Range partitioning preserves ordering but risks hotspots
3. Secondary indexes in distributed systems require careful design
4. Request routing can be client-side, server-side, or tier-based
5. Multi-partition transactions are complex and slow