Hot partitions, celebrity keys and key salting

One viral post draws 8 % of all likes. At a peak of 20,000 likes a second, the partition that owns its counter takes 2,202 likes a second against a limit of 1,000, while the average partition takes 625. Partitions like that one are hot partitions: they receive far more requests than the rest of a cluster, so they reach their limits while the other partitions are half idle.

They usually come from celebrity keys: single keys, such as one viral post or one famous account, that draw a large share of all reads or writes. Hashing spreads keys evenly, but every request for one key still goes to the one partition that owns it, so no better hash can help. Key salting splits a hot key into several keys by adding a suffix, which spreads its writes over several partitions. The fix depends on whether the heat comes from reads or from writes.

A hash spreads keys, not the requests for one key

Hashing spreads keys, not requests. If one post draws 8 % of all likes, 8 % of the like writes reach the partition that owns its counter, however many partitions there are. Each partition has a ceiling: DynamoDB designs every partition for at most 3,000 read units and 1,000 write units a second, and its adaptive capacityA DynamoDB feature that lets a busy partition use throughput that quieter partitions of the table leave unused, and that can move frequently accessed items onto partitions of their own. can move a hot item onto a partition of its own, but no further than that ceiling. This run spreads a sample of likes over 32 partitions by hash and scales it to a peak of 20,000 likes a second:

import random
import zlib

POSTS = 100_000
LIKES = 200_000          # a sample of the day's likes
PARTITIONS = 32
PEAK = 20_000            # likes a second at the peak, spread like the sample
LIMIT = 1_000            # writes a second one partition takes (the per-partition limit DynamoDB documents)
rng = random.Random(7)   # fixed seed: the same likes on every run

# A few posts draw most likes: the post of rank r is liked in proportion to 1 / r.
weights = [1 / (rank + 1) for rank in range(POSTS)]
likes = rng.choices(range(POSTS), weights=weights, k=LIKES)


def partition(key):
    """Hash partitioning: CRC-32 of the key, modulo the partition count."""
    return zlib.crc32(key.encode()) % PARTITIONS


load = [0] * PARTITIONS
for post in likes:
    load[partition(f"post:{post}")] += 1
top_post = sum(1 for post in likes if post == 0)
busiest = max(range(PARTITIONS), key=lambda p: load[p])


def row(name, count):
    share = 100 * count / LIKES
    rate = PEAK * count / LIKES
    mark = " !" if rate > LIMIT else ""
    print(f"{name:<15}{share:>5.1f} %{rate:>11,.0f}{mark}")


print(f"{LIKES:,} likes on {POSTS:,} posts, {PARTITIONS} partitions,")
print(f"{PEAK:,} likes a second at the peak\n")
print(f"{'':<15}{'share':>7}{'a second':>11}")
row("average", LIKES / PARTITIONS)
row(f"busiest (P{busiest})", load[busiest])
row("quietest", min(load))
row(f"top post (P{partition('post:0')})", top_post)
print(f"! over the limit of {LIMIT:,} a second")

200,000 likes on 100,000 posts, 32 partitions,
20,000 likes a second at the peak

                 share   a second
average          3.1 %        625
busiest (P21)   11.0 %      2,202 !
quietest         1.9 %        387
top post (P21)   8.3 %      1,651 !
! over the limit of 1,000 a second

The figure follows the top post’s likes to its partition, then through seven salted keys:

The average partition takes 625 likes a second, well inside a limit of 1,000, so hot partitions do not show in averages. The busiest partition takes 2,202, more than twice the limit, because the top post alone sends it 1,651. That post would be throttled even on a partition of its own, so its counter has to become at least 2 keys (1,651 ÷ 1,000, rounded up), or 7 keys if each key may use only a quarter of a partition.

Hot keys get different fixes for reads and for writes:

• Key salting adds a suffix such as #0 to #6, so one hot key becomes several keys on different partitions.
• Replicas and small local caches serve a read-hot key from many copies instead of one partition. Replicas fit data that is read far more often than it is written.
• Request coalescing turns many concurrent reads of one key into a single read of the store.
• Batching adds increments up in memory and writes one sum per interval. Batching fits a count that may lag by a moment, such as the likes under a post.
• Fan-out on read handles celebrity keys in feeds: a famous account’s post is stored once and fetched by each follower, instead of being copied into millions of feeds.

Hot keys show in the busiest partition, not in averages Pro: opens with a Pro, Premium or Ultimate pass