Uber Redesigns M3DB Sharding with Subclusters to Limit Failure Impact

M3DB Sharding Redesign

Uber has updated the shard placement mechanism within M3DB, its distributed time series database. The new design incorporates fixed-size subclusters to manage shard distribution.

This modification addresses a limitation in the prior placement model where a single node failure or maintenance operation could impact a significant portion of the cluster, potentially affecting up to (n-1)/n of the nodes as shard dependencies increased.

Addressing Scalability Challenges

M3DB divides data into shards, which are then replicated across multiple nodes. The original placement algorithm ensured isolation between replicas, such as placing them in different racks or availability zones.

While effective for smaller clusters, the previous model became operationally complex as clusters grew. A permissive configuration could lead to a dependency graph where topology changes affected a large number of nodes, increasing recovery activity and serializing maintenance.

Subcluster Implementation

The new model partitions nodes into fixed-size subclusters, with each subcluster managing a distinct, nonoverlapping segment of the shard space. For example, a 12-node cluster with a replication factor of three and six nodes per subcluster would have two subclusters, each owning half of the shards.

Within each subcluster, M3DB continues to distribute replicas across isolation groups to maintain data redundancy and availability.

Efficient Scaling and Shard Movement

Scaling the M3DB cluster now involves moving shards from existing subclusters to new ones. Uber employs a greedy algorithm for this process. This algorithm evaluates the effect of removing candidate shards from a donor subcluster and selects those that result in the most evenly loaded remaining nodes.

This approach eliminates the need for a separate rebalancing pass, reducing additional network transfer and bootstrap work. The algorithm operates with O(S log S) sorting and O(S × N) simulation work, where S is the number of candidate shards and N is the number of nodes in the subcluster.