Designing Data-Intensive Applications, session 8

Partitioning

When one machine can’t hold the data or the load: split it, and spread the pieces evenly.

→ next · ← back · N notes · F full screen

Partition for scale, replicate for safety.

Each record belongs to exactly one partition. Each partition is a small database of its own.

Combined with replication, every node leads some partitions and follows others.

Node 1Node 2Node 3 P1 leader P2 follower P3 follower P2 leader P1 follower P3 follower P3 leader P1 follower P2 follower
01

Partitioning key-value data

The goal: no hot spots.

Key range or hash?

Key range

Contiguous ranges of keys per partition, like encyclopedia volumes. Range scans are cheap. Risk: sequential keys like timestamps pile into one partition.

Hash of key

A good hash spreads keys evenly. Range queries now have to ask every partition.

Compound key

Cassandra’s trick: hash the first column, sort by the rest. One user’s posts by time stay together.

Lab: where does the load go?

02

Secondary indexes

Indexes don’t partition neatly.

Local index or global index?

Partitioned by document (local)
Partitioned by term (global)
Each partition indexes only its own records
The index itself is split by the indexed value
Writes touch one partition
Writes may touch several index partitions
Reads scatter to all partitions and gather
Reads go to the one partition holding that term
Tail latency amplification on reads
Index updates are usually asynchronous
MongoDB, Cassandra, Elasticsearch
DynamoDB global secondary indexes
03

Rebalancing and routing

Moving partitions without moving everything.

Lab: never use hash mod N.

of keys move with hash mod N
move with a fixed number of partitions

Fixed partitions

Create many more partitions than nodes (say 1,000 for 10 nodes). New nodes steal whole partitions.

Dynamic

Split a partition when it grows too big (HBase: 10 GB), merge when it shrinks.

Per node

A fixed number of partitions per node (Cassandra), split when a node joins.

Which node has key “merchant:7”?

Any node forwardsRouting tierPartition-aware client client client client router

Someone must know the current assignment: ZooKeeper (HBase, Kafka, SolrCloud) or a gossip protocol (Cassandra, Riak).

Now, our system.

Do we need it yet?

PostgreSQL scales a long way on one node. What would force us to shard: data size, write rate, or isolation between merchants?

Our hot keys

Do a few merchants produce most of the volume? Which tables or locks feel that skew?

Partitioning by date

Are big settlement tables partitioned by date in PostgreSQL? Does that create a hot “today” partition?

Cross-partition queries

If we sharded by merchant, which reports would become scatter/gather?

Next session

Transactions, part 1

ACID, and the weaker isolation levels most databases actually give you. Chapter 7.