When a sorted DynamoDB GSI can't fit on a single partition due to throughput limits, you need to shard it. This post walks through the evolution of sharding strategies: sparse indexes (unordered), single partition key (throttling), random suffixes (can't query by title), hash suffixes (not ordered), first-letter shards (too many Unicode characters), first-byte shards (some bytes need multiple shards), and finally ordered key sharding using equal-range boundaries derived from real MusicBrainz data. The solution uses bisect on a precomputed list of title prefix boundaries to assign each album to a shard, preserving alphabetical order across shards while distributing load evenly.
Table of 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 #457 Impressions