5 Partitioning
This chapter introduces partitioning as a latency optimization that complements colocation and replication. By splitting a large logical dataset into smaller, independently accessible parts, systems can reduce costly synchronization, increase concurrency, and execute requests closer to the data they need. The payoff is lower average and tail latency through less coordination and more parallelism across CPU cores or machines. The trade-offs include added complexity in managing partitions, routing requests to the right place, and handling operations—especially transactions—that span partitions.
The chapter surveys physical and logical partitioning strategies and their latency implications. Physical strategies include horizontal partitioning (sharding) for OLTP-style access to whole records, with key hash vs. key range trade-offs; vertical partitioning (columnar) for OLAP to minimize read amplification and maximize compression and SIMD utilization; and hybrid partitioning to balance OLTP/OLAP needs by combining both. Logical strategies shape data by usage: functional (separating read-heavy and write-heavy domains), geographical (reducing network distance), user-based (per-user isolation), time-based (time-sliced partitions), and overpartitioning (replicating hot partitions for concurrency). Effective query performance depends on good partition keys and routing; without a key, systems rely on secondary indexes or multi-partition scans. Request routing options—direct, proxy, and forward routing—strike different balances between latency (hops) and operational coupling.
Partitioning also brings pitfalls that can degrade latency if left unaddressed. Hot partitions arise from poor key choices or uneven value sizes; skewed workloads create temporal or regional hotspots even with balanced data. Mitigations include choosing high-cardinality keys, preferring hash over range where appropriate, repartitioning and rebalancing, provisioning extra capacity for known spikes, partitioning within partitions, and selectively duplicating data for aggregate queries while handling consistency. A practical example demonstrates how a partition-aware client and a set of horizontally partitioned API nodes improve tail latency by enabling parallel request execution, with further gains possible by hashing identifiers to pick target nodes. Ultimately, the right partitioning and routing choices depend on workload characteristics, and continuous measurement is essential to maintain low latency.
Example of horizontal partitioning of a database table. At the left side of the diagram, you see the full logical table with four rows. On the right side of the diagram, you see three horizontal partitions.
Example of vertical partitioning of a database table. At the top of the diagram, you see the full logical table with four rows. At the bottom of the diagram, you see two vertical partitions of the same table, each with four rows, but only two columns.
Example of hybrid partitioning of a database table. At the top of the diagram, you see the full logical table with four rows. At the bottom of the diagram, you see the logical table first partitioned into two vertical partitions and then further partitioned into two horizontal partitions, creating four partitions in total.
With direct routing, the clients knows the topology of the cluster and communicates directly with the node that manages the partition the client needs to access.
With proxy routing, the client communicates with a routing layer that consists of one or more nodes. The routing layer forwards the request to the node that manages the partition the client needs to access.
With forward routing, the client communicates with one or more nodes in the cluster that either serve the request or forward the request to a node that manages the partition the client wants to access. The main difference to proxy routing is that the routing layer is implicitly part of the nodes in the system, not a separate component.
REST API latency eCDF showing how the tail latency with five nodes is lower than with just one because HTTP requests can execute in parallel.
Summary
- Partitioning is a technique employed in distributed systems to divide logical data into multiple, smaller physical chunks, enhancing scalability and reducing latency. By isolating data into independent partitions, synchronization overhead between users is minimized, enabling efficient data access.
- Partitioning offers advantages, but it also adds complexity to the system. Nonetheless, it proves essential for handling large volumes of data and accommodating numerous concurrent clients.
- Partitioning strategies include horizontal, vertical, and hybrid partitioning, which are all about how partitions are laid out. You can also partition data by workload with functional, geographic, user, and time-based partitioning.
- Partitioning decisions go hand in hand with request routing strategies, direct, proxy, and forward routing.
FAQ
What is data partitioning and why would I use it?
Partitioning divides a large logical dataset into smaller, independently accessible subsets. It reduces latency by minimizing global coordination and synchronization, lowering contention, and increasing concurrency. Independent partitions can be placed on different CPU cores or machines, allowing more parallel work and shorter tail latencies.How do horizontal, vertical, and hybrid partitioning differ, and when should I use each?
- Horizontal partitioning: Splits records (rows/documents/keys) across multiple partitions. A natural fit for OLTP workloads with many short, independent transactions. Pros: concurrency, scalability, availability. Cons: cross-partition joins/transactions are harder.
- Vertical partitioning: Splits records by fields/columns (columnar layout). A good fit for OLAP workloads that scan and aggregate large datasets. Pros: read less data, better compression, SIMD-friendly processing. Cons: writes touch multiple column slices, harder to scale because partitions still span all rows.
- Hybrid partitioning: Combines both (e.g., vertical first, then horizontal). Pros: balances load and keeps partitions small for both OLTP and OLAP needs. Cons: added coordination and complexity; may dilute some vertical-partitioning benefits.
How should I choose a partition key? Hash vs. range?
- Key hash partitioning: Hashes the key to spread records evenly across partitions, reducing hotspots and aiding scalability. Best for point lookups and when key distributions are skewed.
- Key range partitioning: Assigns contiguous key ranges to partitions, enabling efficient range scans and ordered processing. Best when you need range queries and data is naturally ordered.
What are the main trade-offs and downsides of partitioning?
Partitioning adds operational and application complexity: request routing and partition discovery; harder cross-partition joins and transactions (sometimes unsupported); maintaining secondary indexes; potential scans across partitions; rebalancing when partitions grow unevenly; handling data movement (for example, users changing geography). Poor key choice can create hot partitions and worse latency.How do I route requests efficiently to the right partition?
- Direct routing: Clients send requests straight to the node managing the target partition. Lowest latency (single hop) but tightly couples clients to cluster topology and increases security/maintenance complexity.
- Proxy routing: Clients talk to a routing layer that forwards to the correct node. Simpler clients, but adds an extra hop. Clients can cache locations to reduce proxy hits.
- Forward routing: Any node can forward to the right node. Often behaves like direct routing with client-side caching, but can introduce a hop when the first node doesn’t host the partition.
What causes hot partitions and how can I mitigate them?
Hot partitions arise from uneven data distribution or value sizes (e.g., skewed keys, large objects). Mitigations include switching to hash-based partitioning, choosing a better key with higher cardinality, repartitioning or rebalancing, splitting very large items further, allocating more resources to hot partitions, or replicating hot partitions to increase concurrency.What are skewed workloads and how do I handle them?
Skewed workloads concentrate access on a subset of partitions (often temporarily), such as product launches or seasonal events. Unlike hot partitions from data distribution, these are driven by access patterns. Address them by incorporating workload characteristics into your scheme, overprovisioning for known events, adding load balancing, scaling partitions, and replicating or overpartitioning hot data during spikes.What logical (workload) partitioning strategies can reduce latency?
- Functional partitioning: Separate data by use (e.g., read-heavy product catalog vs. write-heavy orders) to avoid interference.
- Geographical partitioning: Place data near users to minimize network distance, handling movement and edge cases across regions.
- User-based partitioning: Per-user slices to isolate access; beware of many small partitions, discovery overhead, and cross-user transactions.
- Time-based partitioning: Partition by time windows (e.g., hourly/daily) for efficient time-range queries in time series and audit logs.
Latency ebook for free
