M3DB subcluster placement algorithm tames shards

Uber Engineering rebuilt how M3DB places shards at scale, and the M3DB subcluster placement algorithm walls off failure domains by design.

The old sharded algorithm let any shard land on any node.

The only hard rule was that replicas couldn't share an isolation group, like a rack or zone. In permissive setups with one node per group, any change touched O(N) nodes. Even with zones matched to RF=3, a node still shared shards with up to 66.67% of the cluster.

That created two problems. A single node failure fanned out to (n-1)/n of the cluster. Maintenance had to be serialized because nodes in different zones still overlapped on shards.

How the new placement actually works

Subclusters partition nodes into fixed-size groups, each owning a distinct slice of the shard space with no overlap in steady state. Think of sealed aisles in a warehouse: a spill stays in one aisle instead of flooding the floor.

In Uber's example, a 12-node cluster with RF=3 and 6 nodes per subcluster has two subclusters, each with 2 nodes per zone and half the shards. Within a subcluster the old sharded logic still runs, but cross-subcluster sharing is forbidden. A greedy donation algorithm picks which shards to hand to a new subcluster by simulating removal of each shard and choosing the one that leaves donor skew, max minus min shards per node, lowest.

Why this matters and what it still can't do

Failures now recover only inside the affected subcluster. Parallel work across subclusters becomes safe, so automation doesn't have to serialize everything and network and I/O noise stays contained.

The trade is rigidity. It requires homogeneous instance weights, scaling in multiples of instancesPerSubcluster which must itself be a multiple of RF, no AddReplica support, and only one partial subcluster at a time while AddInstances or RemoveInstances run node by node. Cross-subcluster sharing still appears transiently during scale up or down, but replicas never relax the isolation group rule.

For startups running high-cardinality metrics on M3DB or Thanos or ClickHouse, the lesson echoes what Uber hit: sharding that optimizes for placement freedom eventually taxes operations. Uber kept the instance-level API to avoid rewriting tooling and to avoid a bootstrapping storm, a choice smaller teams copying the idea should steal.