Uber's M3DB Sharding Redesign with Subclusters for Fault Isolation
Uber redesigned M3DB's sharding mechanism by introducing fixed-size subclusters to significantly limit the blast radius of node failures and improve operational efficiency for large-scale time series data. This new approach addresses limitations in their previous placement model, where single node failures could impact a large portion of the cluster, by partitioning the shard space among distinct subclusters.
Read original on InfoQ ArchitectureUber's M3DB, a distributed time series database, faced operational challenges with its original sharding model as clusters grew. The primary issue was that a node failure or maintenance operation could affect a disproportionately large percentage of the cluster (up to (n-1)/n), leading to extensive recovery activity and serialized maintenance. This was due to the permissive nature of shard placement, where any node could own a shard as long as replica isolation rules (e.g., different racks/AZs) were met, leading to complex dependency graphs.
Introduction of Subclusters for Improved Fault Isolation
To mitigate this, Uber introduced a new sharding model based on fixed-size subclusters. Each subcluster is responsible for a distinct, non-overlapping portion of the overall shard space. Within each subcluster, M3DB continues to distribute replicas across isolation groups, ensuring high availability. This partitioning strategy localizes the impact of failures or scaling events to only the nodes within the affected subcluster, dramatically reducing the blast radius.
- Reduced Failure Impact: A node failure within a subcluster only affects shards owned by that subcluster, not the entire cluster.
- Simplified Operations: Maintenance operations and scaling become more localized and parallelizable.
- Improved Predictability: The fixed-size nature of subclusters provides a more predictable operational footprint.
Greedy Algorithm for Scaling and Rebalancing
Scaling out with the new model involves moving shards from existing subclusters to a new one. Uber employs a greedy algorithm for this process. This algorithm evaluates candidate shards from the donor subcluster and selects those that, when moved, leave the remaining nodes in the donor subcluster as evenly loaded as possible. This smart selection process aims to prevent the need for a separate rebalancing pass, minimizing network transfers and bootstrap work associated with moving shards multiple times.
Algorithmic Efficiency
The greedy algorithm used for shard distribution has a time complexity of O(S log S) for sorting candidate shards and O(S × N) for simulation work, where S is the number of candidate shards and N is the number of nodes in the subcluster. This efficiency is critical for maintaining operational performance during scaling events.
Constraints and Operational Considerations
The subcluster approach comes with certain constraints: it requires equal instance weights, scaling in multiples of the subcluster size, and a subcluster size that is a multiple of the replication factor. It also doesn't natively support changing the replication factor through simple `AddReplica` operations. Uber opted to retain M3DB's existing instance-level placement operations to preserve compatibility with existing tooling and prevent large, simultaneous bootstrap operations.