Learning Notes on Designing Data-Intensive Applications (vi)

Chapter 6. Partitioning

Photo by Nathan Dumlao on Unsplash

Partition of key-value data

  • The goal with partitioning is to spread the data and the query load evenly across nodes.
  • If partition is unfair, it is skewed. It makes partitioning much less effective.
  • A partition with disproportionately high load is called a hot spot.

Partition by key range

  • Assign a continuous range of keys.
  • This range does not have to be evenly spaced. Once we know the boundaries between the ranges, it’s easy to determine which partition contains a given key. Keys could also be kept in sorted order within each partition.
  • The downside of this is that some access patterns can lead to hotspots.
  • The solution for above is to use a compound key, e.g. timestamp and item index. Though with this approach, a separate range query for each item name is required.

Partitioning by hash of key

  • Many distributed data stores use a hash function to determine the partition for a given key.
  • A good hash function takes skewed data and makes it uniformly distributed. The partition boundaries can be evenly spaced or chosen pseudo-randomly ( consistent hashing).
  • Unfortunately this loses the ability to do efficient range queries. Keys that were once adjacent are now scattered across all the partitions. Any range query has to be sent to all partitions.

Skewed workloads and relieving hot spots

  • In an extreme case where reads and writes are for the same key, then all requests being routed to the same partition (e.g. twitter celeb with millions followers).
  • A simple technique is to add a random number to the beginning or end of the key. This has the downside, though, that reads now have to do additional work to keep track of these keys.

Partitioning and secondary indexes

  • Document-based partitioning
  • Term-based partitioning

Partitioning secondary indexes by document

Partitioning secondary indexes by term

Rebalancing partitions

  • How not to do it: Hash mod n. The problem with mod N is that if the number of nodes N changes, most of the keys will need to be moved from one node to another, and the operation is very expensive.
  • Create many more partitions than there are nodes and assign several partitions to each node.
  • When a new node is added , it can steal a few partitions from every existing node until partitions are fairly distributed once again.
  • The number of partitions does not change, nor does the assignment of keys to partitions.
  • The only thing that change is the assignment of partitions to nodes.
  • Make the number of partitions adjusts to the total data volume.
  • An empty database starts with an empty partition. All the data could end up on one node.
  • When a partition grows to exceed a configured size, it is split into two partitions so that approximately half of the data ends up on each side of the split.
  • Conversely, if lots of data is deleted and a partition shrinks below some threshold, it can be merged with an adjacent partition.
  • Database like Cassandra makes the number of partitions proportional to the number of nodes.
  • Have a fixed number of partitions per node. This approach also keeps the size of each partition fairly stable.

Operations: automatic or manual rebalancing

  • Fully automated rebalancing can be unpredictable. The process can overload the network or the nodes and harm the performance of other requests while the rebalancing is in progress.
  • It can be good to have a human in the loop for rebalancing.

Request routing

  • Allow clients to contact any node and make them handle the request directly, or forward the request to the appropriate node.
  • Send all requests from clients to a routing tier first that acts as a partition-aware load balancer.
  • Make clients aware of the partitioning and the assignment of partitions to nodes.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store