Uber redesigns M3DB sharding with subclusters to contain cascading failures

Uber published a redesign of M3DB's shard placement algorithm, its distributed time-series database, to solve a problem that any team operating a large cluster of replicated data recognizes: as the cluster grows, the failure of a single node starts affecting an ever-larger fraction of the system. The change, described by Uber and reported by InfoQ, introduces fixed-size subclusters as the unit of isolation, instead of letting any node in the cluster be eligible to receive any shard.

The problem: a node can share data with 66% of the cluster

In M3DB's original placement model, a shard could be assigned to any node, as long as its replicas weren't placed in the same isolation group (a rack or availability zone, for example). This works well in small or medium clusters, but it creates a shard dependency graph that grows along with the cluster: in a permissive configuration, a topology change can affect O(N) nodes.

Uber's example is direct: even with isolation groups corresponding to three zones and a replication factor of three, a single node can end up sharing data with up to 66.67% of the cluster. In practice, this means that a node going down triggers recovery activity across a good part of the fleet, and that maintenance operations need to be serialized, one at a time, because there's no safe way to know that two nodes don't share replicas.

Anyone who has operated a distributed database cluster in production recognizes the symptom: the cluster runs smoothly up to a certain size, and from there on, every rebalancing or maintenance patch becomes a calculated-risk event, because the blast radius of any operation stops being predictable.

How the subcluster model works

Uber's solution partitions the cluster's nodes into fixed-size subclusters, each responsible for a distinct, non-overlapping portion of the shard space. The example Uber itself uses: a 12-node cluster, with a replication factor of three and six nodes per subcluster, results in two subclusters, each owning half of the shards. Within each subcluster, M3DB keeps distributing replicas across isolation groups, exactly as before.

The core difference is that shard dependency now stays contained within the subcluster's boundary. A node failure in one subcluster has no way to propagate to another, because there's no shard shared between them. This mathematically limits the blast radius: instead of O(N) potentially affected nodes, the ceiling becomes the subcluster's size.

The rebalancing algorithm without a double pass

Scaling a cluster with this model requires moving shards from existing subclusters to a new subcluster. Instead of doing this in two steps (adding the subcluster and then rebalancing separately), Uber implemented a greedy algorithm that evaluates, for each candidate shard, the effect of removing it from the source subcluster, and chooses the set that leaves the remaining nodes with the most balanced load possible.

This decision avoids a second rebalancing pass and the network and bootstrap cost that would come from moving the same shard twice: once to accommodate the new subcluster and again to rebalance. The algorithm runs in O(S log S) to sort the candidate shards and O(S × N) to simulate the effect of each move, where S is the number of candidate shards and N is the number of nodes in the subcluster. It's a tractable complexity even for sizable clusters, because the work stays limited to the affected subcluster, not the entire cluster.

It's worth noting that this concern with data movement isn't new to M3DB: the project's placement documentation already treated shard movement as an expensive process, in which the destination node needs to stream data from existing peers before taking ownership of the shard. Any unnecessary movement is pure operational cost, and the new algorithm was designed precisely to minimize that.

The trade-offs that come with the gain

The subcluster model isn't free. Uber explicitly lists the limitations:

• All nodes need to have the same instance weight;
• Cluster scaling only happens in multiples of the subcluster size;
• The subcluster size needs to be a multiple of the replication factor;
• It's not possible to change the replication factor via AddReplica in this model;
• During scaling, there can be temporary cross-sharing of shards between subclusters, and only one partial subcluster is allowed at a time.

These are typical trade-offs of any hierarchical partitioning scheme: you gain predictability and failure isolation in exchange for fine-grained operational flexibility. A team that plans capacity in big jumps (doubling the cluster, for example) lives well with this; a team that needs incremental adjustments of a few nodes at a time feels the friction.

Another point Uber made clear: placement operations remain at the instance level; no atomic subcluster operations were created. This was intentional, to preserve compatibility with existing tooling and avoid triggering a massive bootstrap in which many shards migrate simultaneously. M3DB's placement implementation now includes specific fields for subcluster placement and for the number of instances per subcluster, but the per-instance operation model remains the same.

Why this matters to those building infra outside Uber

M3DB is an open source project born inside Uber to handle metrics at scale, and this kind of sharding redesign is the sort of architecture decision that rarely shows up in a tutorial, only in a post-mortem or an engineering blog post after the problem has already caused pain. For anyone designing or operating distributed databases, partitioned queues, or any system with shard-based replication in Brazil, whether on their own Cassandra, Kafka, ScyllaDB cluster or similar, the underlying lesson is reusable even without switching databases: the right question isn't just