Introduction

M3DB is a distributed time-series database built on a sharded architecture. Data is divided into shards, and each shard is replicated across multiple nodes (determined by the replica factor, or RF). A placement algorithm determines which nodes own which shards and how shards move when the cluster topology changes.

The sharded placement algorithm worked well for small-to-medium clusters, but as our clusters grew, it started to show cracks in operational reliability and maintenance overhead. This blog describes the problem and how we used a subclustered placement algorithm to address it.

The Problem with Sharded Placement

In the sharded algorithm, shard ownership is distributed freely across all nodes in the cluster. The only hard constraint the algorithm enforces is that no two replicas of the same shard land in the same isolation group—a fault domain such as a rack or availability zone. Beyond that, any node is a valid candidate to hold any shard.

To understand why this matters, consider what happens during bootstrapping—the process a node goes through to catch up on data when it first receives a shard. The new node must replicate data from ‌peers that currently own that shard. The peers it talks to are determined entirely by where those replicas reside, which depends on how freely the algorithm was allowed to spread shards during placement.

Shard ownership distribution depends heavily on isolation group settings. In permissive setups where every node is its own group, shards move freely, creating a fully connected dependency graph in which any change affects O(N) nodes. Restricting isolation groups to match the replication factor (like 3 zones for RF=3) forces zone-local movement. While this bounds the blast radius, nodes still share data with most of the cluster—up to 66.67% for RF=3. Consequently, sharing remains a function of RF rather than cluster size, leading to wide failure domains and serialized maintenance. There are two main consequences of this:

• Wide  blast radius during failures and maintenance. Node failures affect up to (n-1)/n of the cluster. In large clusters, this causes extensive I/O, network strain, and operational noise across many nodes.
• Lack of parallelism in cluster operations. Since nodes in different isolation groups often share shards, maintenance operations can interfere with each other. This uncertainty forces operators to serialize cluster changes to ensure safety.

The Insight: Subclusters

The subclustered placement algorithm introduces a structural constraint: nodes are partitioned into fixed-size groups called subclusters. Each subcluster is self-contained: it owns a distinct, non-overlapping slice of the total shard space.

For example, in a cluster of 12 nodes with RF=3 and 6 nodes per subcluster, there are 2 subclusters. Each subcluster contains 2 nodes per isolation group (to maintain fault tolerance), and each subcluster owns exactly half the shards. Crucially, no shard is ever shared between two nodes in different subclusters.

Subclustered placement requires meeting specific conditions:

• Homogeneous hardware (equal instance weights) for load calculation
• Cluster scaling in multiples of the subcluster size
• No support for changing the replica factor (AddReplica)
• Small subcluster sizes relative to the total cluster to maximize blast radius reduction

Figure 1 shows the difference between the sharded and subclustered algorithms. 

How the Algorithm Works

At initialization, nodes join subclusters in groups of instancesPerSubcluster. The shard space is evenly divided among subclusters, with remainders balanced one by one. Within each subcluster, shards are distributed across nodes according to the sharded algorithm, while respecting isolation groups for fault tolerance.

The algorithm maintains three structural invariants:

• Instances must have equal weight for even load calculation
• Isolation group counts must match the replica factor (RF)
• instancesPerSubcluster must be a multiple of RF

New nodes first fill existing incomplete subclusters before creating a new subcluster, preventing partially formed groups. When filling a new subcluster, a greedy shard assignment strategy prioritizes moving shards to leave the donor subcluster as balanced as possible, minimizing skew during migration.

The Skew Problem 

When a new subcluster joins the cluster, it needs to acquire shards from existing subclusters. Each existing subcluster must donate a portion of its shards to bring the new one up to its target. The question of which shards to give away turns out to be surprisingly tricky, and the wrong answer causes a problem called intra-subcluster skew. Skew, in this context, is the difference between the node with the most shards and the node with the fewest shards within a subcluster. 

Because subclusters are meant to be self-contained, internal skew directly threatens the guarantees that make subclustering valuable. If a subcluster is unbalanced after a scaling event, the overloaded nodes see more read/write traffic, more bootstrapping work, and more memory pressure than their peers—exactly the kind of hotspot that placement is supposed to prevent.

Why the Naive Approach Fails

Imagine a 6-node subcluster (RF=3, 2 nodes per zone: A11/A21, B11/B21, C11/C21) with 400 unique shards, totaling 200 per node. We need to donate 200 shards to a new subcluster.

Randomly selecting shards for donation risks uneven draws from specific nodes. Consequently, the donating subcluster could end up with a significant imbalance, such as one node holding 50 shards while another holds 150.

Why Not Just Rebalance After?

One natural reaction is: donate shards in any order, then run a rebalancing pass to fix the skew. This works, but it means moving shards twice—once to donate them, and once more to rebalance. In a distributed system, every shard movement is expensive: data must be transferred over the network, and the destination node must bootstrap (replay historical data for) each shard it receives. Moving a shard twice doubles that cost for no operational reason.

The greedy approach avoids this by choosing the optimal order of donations up front, so that the donor subcluster remains balanced throughout the migration and no corrective rebalancing is needed afterward.

How the Greedy Approach Works

For each shard, the algorithm considers donating from the source node; it simulates the counterfactual: if all replicas of this shard were removed from this subcluster, what would the resulting per-node shard counts look like, and what would the skew be?

It does this for every candidate shard, collects those (shard, skew-after-removal) pairs, sorts them in ascending order of resulting skew, and picks from that list. In other words, it always donates the shard whose removal will leave the subcluster most balanced.

Concretely:

1. Start from the current per-node shard counts in the donor subcluster.
2. For each candidate shard, simulate decrementing the count of every node in the subcluster that holds a replica of that shard.
3. Compute the skew of that simulated state: max_count - min_count.
4. Rank shards by that skew score ascending. The shard that leaves the cluster most balanced goes first.

Figure 3 shows an example of this. For replication factor = 3, number of nodes = 6, 2 per zone/isolation group, and 8 shards

Figure 3: Shard distribution in a 6-node subcluster.

Figure 4: Starting shard count before adding new subcluster.

Figure 5: Skew score calculation for each shard.

Figure 7: Skew score calculation after the first move and chosen shard to reduce skew.

Why Not an Optimal Search?

The truly optimal ordering would require evaluating all possible subsets of shards to donate—an exponential search. For a subcluster donating 600 out of 1,200 shards, that’s combinatorially infeasible.

The greedy approach is a well-understood approximation for this class of problem. It runs in O(S log S) time (sorting dominates), with O(S × N) simulation work, where N is the number of nodes per subcluster. In practice, both are small numbers, and the greedy ordering consistently produces near-zero skew in the donor after migration.

Transient Cross-Subcluster Sharing: Safe by Construction

Subclustered placement guarantees that shards aren’t shared between subclusters in stable states, though transient sharing occurs during scale-up or scale-down. This is intentional and doesn’t compromise fault tolerance.

During scale-up operations, new subclusters form incrementally via AddInstances. During this window, shards are temporarily split between donors and the new partial subcluster. The algorithm ensures cross-subcluster moves respect the isolation groups, preserving fault tolerance. Once complete, the transient sharing window closes.

When a subcluster is removed, its instances depart one by one. The algorithm requires that all replicas of a shard migrate to the same target subcluster, thereby preventing fragmentation. The algorithm ensures that, when removing shards from a subcluster, they move directly to their destination subcluster rather than first moving to the nodes in the subcluster being removed and then to the destination subcluster.

To maintain system predictability, only one partial subcluster can exist at a time; validatePartialSubclusters blocks concurrent operations. This tradeoff ensures transitions are easy to reason about and recover from.

The isolation group constraint is never relaxed. Shard replicas always reside in different isolation groups to ensure fault tolerance. Cross-subcluster sharing is a temporary operational relaxation of subcluster isolation, not of correctness-critical fault isolation.

Reusing the Existing Algorithm Interface

Instead of adding atomic subcluster-level operations like AddSubcluster or RemoveSubcluster to the placement interface, we maintained instance-level methods for two reasons:

• Migration cost. Existing sharded placement callers and tooling remain compatible without code updates. Migration is a simple configuration change via an embedded placement flag.
• Operational safety. Atomic subcluster operations could trigger a bootstrapping storm—a massive surge in read traffic and migrations that threatens cluster stability. Using existing instance-level operations (AddInstances/RemoveInstances) enforces a safer, sequential node-by-node approach that spreads load over time.

By keeping the interface at the instance level, subclusters remain an internal algorithmic concept. This provides a drop-in upgrade with superior operational properties.

Conclusion

Adopting subclustered placement gives us a cleaner operational model for large M3DB clusters:

• Failures are contained. A node going down initiates recovery work only within its subcluster.
• Maintenance is faster. Automation can work on multiple subclusters in parallel without coordination overhead.
• Predictability improves. The set of nodes that interact with any given node is fixed and small, making it easier to reason about the impact of changes.
• Shard sharing between arbitrary node pairs drops from O(cluster) to O(subcluster). The implicit dependency graph of the cluster becomes much sparser.

The sharded algorithm remains appropriate for smaller clusters or use cases where subcluster-sized scaling steps aren’t practical. But for large, operationally intensive clusters, subclustered placement substantially reduces the cost of keeping things running.

Acknowledgments 

Cover Photo Attribution: Image created by Google Gemini

Figure 3 Attribution: Image created by Google Gemini

Figure 5 Attribution: Image created by Google Gemini

Figure 7 Attribution:  Image created by Google Gemini

Google® is a trademark of Google LLC and this blog post is not endorsed by or affiliated with Google in any way.