Skip to main content
This lesson explains a resharding technique that uses a fixed set of buckets to make resharding predictable and minimize data movement. The approach is similar in intent to consistent hashing but simpler to visualize and reason about. Concept overview
  • Create a fixed number of buckets. Example: 1000 buckets numbered 0..999.
  • For each user, compute a stable hash from the user ID and take the remainder modulo the number of buckets: hash(userID) % 1000. That remainder is the bucket assigned to the user.
  • Do not map users directly to shards. Instead, map users → buckets (via hash) and maintain a separate bucket map that maps buckets → shards.
  • Routing becomes two-step: user → bucket (deterministic hash) and bucket → shard (bucket map lookup).
Choose a stable, uniform hash function and keep the hash algorithm and seed constant across deployments. Changing the hash function or seed will remap users to different buckets and defeat the predictability of this scheme.
Recommended hash families include MurmurHash3, xxHash, or a deterministic truncation of a SHA-family hash. The important properties are uniformity (even distribution) and stability (no unexpected remappings). Example: hash-to-bucket (pseudocode)
For example, Chris’s hash might yield remainder 371, so Chris is assigned to bucket 371. Leo’s hash might yield remainder 120, so Leo is in bucket 120. The bucket map determines which shard currently owns bucket 371 or 120. This design keeps the user-to-bucket assignment stable when shards are added or removed, because hashing is always done modulo the fixed number of buckets. Shard-to-bucket distribution and what happens when we add a shard With 1000 buckets and 4 shards, each shard will own roughly 250 buckets. When a 5th shard is added, you update the bucket map to reassign buckets — you do not recompute per-user hashes. Roughly each of the 4 existing shards gives about 50 buckets to the new shard, so the new shard ends up with ~200 buckets (1000 / 5 = 200). Only ~200 buckets move (~20% of the data), and every user remains in the same bucket (their bucket assignment never changes).
A stylized diagram titled "Buckets" showing five vertical columns of small squares (each labeled 200 buckets) above barrel icons for Shard 0–3 and a New Shard, with one column colored purple. A "Bucket Map" table on the right lists bucket-to-shard mappings and two individual buckets are highlighted with tags (Leo 120 and Chris 371).
Key property
A user never changes buckets. Only the bucket→shard mapping changes when you add or remove shards. This containment makes resharding predictable and limits the amount of data that must be moved.
Moving a bucket (example: bucket 602) When you move a bucket from one shard to another you must ensure no writes are lost and the new shard becomes a consistent copy before routing traffic. You cannot merely copy rows and flip the map while writes continue. A safe migration proceeds in four stages:
  1. Copy (initial snapshot)
    • Take a background snapshot of all rows belonging to bucket 602 on the source shard and copy them to the destination shard.
    • The source shard continues to serve reads and writes for bucket 602 during this phase.
  2. Catch up (replicate ongoing changes)
    • While the snapshot is being copied and after it completes, stream or replicate all subsequent changes (inserts, updates, deletes) that affect bucket 602 from the source to the destination shard.
    • Use change-data-capture, MySQL binary log streaming, or write-ahead-log replay to continuously apply changes.
    • Preserve change ordering for the bucket, or use per-row sequence/version numbers to prevent reordering or lost updates.
  3. Cutover (brief pause and final sync)
    • Quiesce writes for bucket 602 briefly (pause writes for that bucket).
    • Send the final outstanding changes to the destination shard and verify both copies are consistent.
    • Update the bucket map so bucket 602 now points to the destination shard. From this moment reads/writes for bucket 602 are routed to the destination shard.
    • Resolve any in-flight transactions and verify consistency using checksums, row counts, or per-row version checks.
  4. Remove (cleanup)
    • Once traffic is confirmed to go to the new shard and the new shard is healthy, remove the old copy of bucket 602 from the source shard.
Only writes for the specific bucket are paused briefly during cutover. With careful implementation the pause can be very short (seconds or less), depending on system latency and replication throughput. Quick migration summary table
A dark schematic showing three user icons connecting to a central point that routes traffic down to five database cylinders labeled Shard 0, Shard 1, Shard 2, Shard 3 and New Shard. The top lists four numbered steps — Copy, Catch Up, Cutover, Remove — indicating a shard migration or resharding process.
Summary
  • Fixed buckets let you add or remove shards by updating a bucket map instead of recomputing user hashes.
  • Only the buckets that are reassigned move their data, which limits how much data must be copied during resharding.
  • A safe bucket migration follows the sequence: copy snapshot → replicate changes → short write pause and final sync → update bucket map → remove old data.
Trade-offs Operational considerations
  • Ensure your bucket map is stored in a highly available, consistent store (e.g., a distributed config service) so routers and application servers see the updates atomically.
  • Instrument and monitor per-bucket copy and replication throughput to estimate resharding time and plan maintenance windows.
  • Test cutover procedures to ensure the brief write quiesce can be achieved within acceptable SLAs.
  • If you use per-row versioning or sequence numbers, design them to be monotonic per-bucket so ordering guarantees are preserved during replication.
References and further reading

Watch Video