Ordered key sharding in DynamoDB - death and gravity

Ordered key sharding in DynamoDB

June 2026<br>∙ eight minute read

PyCoder's Weekly<br>HN<br>Bluesky<br>Reddit<br>--><br>linkedin<br>Twitter

So, you want to keep a sorted index in DynamoDB,<br>but for whatever reason<br>– usually throughput-related –<br>it won't fit on a single partition . What do you do?

Today, we look at the available solutions,<br>do the math, and find out which is best.

Tip

This worked example is part of my DynamoDB crash course series.

Contents

Requirements

A sparse index is almost enough

But scan results are not ordered

But a single partition key causes throttling

But random suffixes are random

But hash suffixes are not ordered

But there are a lot of first characters

But some first bytes need multiple shards

But tries and prefix ranges are complicated

But the prefix distribution can change

Requirements #

Say you're using single table design<br>with a table of artists, albums, and songs.1

You keep an artist's items in a single collection<br>(aka same partition key),<br>and use sort keys artist, album#{Album}, and song#{Album}#{Song},<br>depending on their type:

# table Music (partition key: Artist, sort key: sk)<br>Solar Fields: !btree<br>'album#Leaving Home': { Album: Leaving Home, ... }<br>'artist': { ... }<br>'song#Leaving Home#Air Song': { ... }<br>'song#Leaving Home#Monogram': { ... }

To list albums without doing a full table scan,<br>you need a global secondary index.

Let's come up with some reasonable requirements; the GSI should support:

items up 500 bytes (we project additional attributes besides the keys)

10,000 queries/second, max 100 items/query, sorted alphabetically<br>list all albums

list albums by title

10,000 writes/second (to avoid write throttling during imports)

A sparse index is almost enough #

One way to do it is to use a dedicated<br>sparse index,<br>taking advantage of the fact that<br>items with missing index keys don't appear in the index.

If only albums have an Album attribute, we just create a new GSI:

# GSI Albums (partition key: Album, sort key: Artist)<br>Leaving Home: !btree<br>International Pony: { sk: 'album#Leaving Home', ... }<br>Solar Fields: { sk: 'album#Leaving Home', ... }<br>Heavy Migration: !btree<br>Dday One: { sk: 'album#Heavy Migration', ...}

If songs have an Album too,<br>we add a dedicated AlbumsPK attribute instead.

In many ways, this is the ideal solution.<br>To list all albums, we scan the index.<br>To list albums by title, we query an index partition key.<br>We have lots of unique partition keys<br>with items spread pretty evenly across them,<br>which should prevent throttling.

But scan results are not ordered #

...except scan results are not ordered,<br>so we're missing the sorted alphabetically part.

What is ordered are sort keys,<br>so we can use a single index collection instead:

# GSI GSI1 (partition key: gsi1pk, sort key: gsi1sk)<br>'albums': !btree<br>Heavy Migration: { Artist: Dday One, sk: 'album#Heavy Migration', ... }<br>Leaving Home: { Artist: Solar Fields, sk: 'album#Leaving Home', ... }<br>Leaving Home: { Artist: International Pony, sk: 'album#Leaving Home', ... }

This is also seemingly ideal.<br>To list all albums, we query the entire index partition key.<br>To list albums by title, we use a sort key.<br>The results are sorted as required,<br>and there's no limit on the number of items in a collection.

But a single partition key causes throttling #

However, there are<br>per-partition limits of<br>24 MB/s for reads and<br>1 MB/s for writes.

Let's see how they compare to our requirements:

reads: 500 bytes/item * 10k queries/s * 100 items/query = 500 MB/s (~21x )

writes: 500 bytes/item * 10k items/s = 5 MB/s (5x )

Uh-oh, turns out we need 21 times the throughput one partition can deliver.

One way to spread the load is<br>sharding,<br>using multiple synthetic partition keys of the form album#{shard_id}.<br>A common option for the shard id is a random number from a known range,<br>e.g. album#{randrange(21)}:

# GSI GSI1 (partition key: gsi1pk, sort key: gsi1sk)<br>'album#1': !btree<br>Leaving Home: { Artist: Solar Fields, ... }<br>'album#12': !btree<br>Heavy Migration: { Artist: Dday One, ... }<br>'album#20': !btree<br>Leaving Home: { Artist: International Pony, ... }

To list all albums, query each shard in turn:

for shard in range(21):<br>for item in dynamodb.query(f"album#{shard}"):<br>yield item

But random suffixes are random #

There's a problem, though –<br>with random shard ids we can't easily list albums by title,<br>since albums with the same title may end up on any shard.

A better option is to calculate the shard id<br>from the album title using a hash function:

def hash(s):<br>return int.from_bytes(sha256(s.encode()).digest())

def album_shard_id(album_title):<br>return hash(album_title) % 21

# GSI GSI1 (partition key: gsi1pk, sort key: gsi1sk)<br>'album#6': !btree<br>Leaving Home: { Artist: Solar Fields, ... }<br>Leaving Home: { Artist: International Pony, ... }<br>'album#8': !btree<br>Heavy Migration: { Artist: Dday One, ... }

To list albums by title:

dynamodb.query(f"album#{album_shard_id(album_title)}",...