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