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

This post introduces and details the subclustered placement algorithm for M3DB. It explains the problems with the previous sharded placement algorithm, such as wide blast radius during failures and serialized cluster operations. The new algorithm partitions nodes into fixed-size subclusters, with each subcluster owning a non-overlapping shard space. It describes the algorithm's mechanics, including initialization and shard distribution, and addresses the 'skew problem' by introducing a greedy shard donation strategy that prioritizes shard removals that minimize intra-subcluster skew. The post also discusses transient cross-subcluster sharing during scale-up and scale-down operations, ensuring fault tolerance is maintained.