From Chaos to Control: Addressing Shard Distribution Challenges in M3DB with Subclusters

Summary

M3DB’s sharded placement algorithm lets replicas spread across nodes subject primarily to isolation-group constraints, but large clusters experienced broad failure and maintenance impacts. The subclustered placement algorithm partitions nodes into fixed-size, self-contained groups, each owning a distinct shard slice while preserving replica separation across isolation groups. It requires equal instance weights, scaling in multiples of the subcluster size, a replica factor that cannot change through AddReplica, and instancesPerSubcluster divisible by RF. During scaling, a greedy donation strategy simulates removing each candidate shard, ranks the resulting per-node skew, and chooses the shard that leaves the donor most balanced, avoiding a second rebalancing move. The resulting model contains recovery within subclusters, enables parallel maintenance, and reduces arbitrary shard sharing from O(cluster) to O(subcluster), while the original algorithm remains suitable for smaller clusters or impractical scaling steps.

Takeaways

1. 1

   Each subcluster owns a distinct shard slice, so a node failure initiates recovery work only within its own subcluster.

2. 2

   The greedy migration strategy evaluates the skew caused by removing every candidate shard and chooses the removal that leaves the donor subcluster most balanced.

3. 3

   Subclustered placement requires equal instance weights, subcluster-sized scaling steps, instancesPerSubcluster divisible by RF, and no replica-factor changes through AddReplica.