Create a topology-aware sharding scheme: consistent hashing, hotspots, and rebalancing.
- User
Create a topology-aware sharding scheme: consistent hashing, hotspots, and rebalancing.
- Assistant
Topology-Aware Consistent Hashing Sharding Scheme (TACHS)
I'll design a complete, production-ready Topology-Aware Consistent Hashing Sharding (TACHS) scheme for distributed key-value stores or databases. It builds on classic consistent hashing (with virtual nodes for load balancing) while incorporating:
- Topology awareness: Prefers localizing shards and replicas within the same rack/zone/DC to minimize cross-network traffic/latency.
- Hotspot detection and mitigation: Monitors per-shard/node load and proactively splits/migrates hot shards.
- Rebalancing: Handles node join/leave, capacity changes, and load imbalances with minimal data movement.
This scheme is inspired by systems like Cassandra, ScyllaDB, and CockroachDB but extends them with hierarchical topology biasing and automated hotspot splitting.
1. System Model and Assumptions
- Data Model: Keys are hashed to 160-bit tokens (SHA-1 or XXHash). Data is partitioned into shards (contiguous token ranges, e.g., [0xabc... , 0xdef...)).
- Replication: N=3 replicas per shard (1 primary, 2 secondaries). Topology-aware placement for replicas.
- Topology Hierarchy (tree-structured):
Cluster └── DC (Data Center) └── Zone (Availability Zone) └── Rack └── Node (physical machine)- Each node has a topology path: e.g.,
DC1/ZoneA/Rack3/Node42. - Distance metric between nodes A and B: Levenshtein-like distance on paths (0 = same node, 1 = same rack, ..., 4 = different DCs).
- Each node has a topology path: e.g.,
- Nodes: Each physical node runs V=256 virtual nodes (vnodes) for fine-grained load distribution.
- Metrics: Per-node/shard: CPU%, disk IOPS, memory%, network throughput, QPS (queries/sec).
- Cluster Manager: Central service (e.g., like ZooKeeper/Etcd-backed) tracks topology, membership, load, and coordinates rebalancing.
2. Consistent Hashing Ring Construction
- Global Token Ring: 2^160 circle (0 to 2^160-1).
- VNode Placement (topology-biased):
- For each node, generate V positions:
hash(topology_path + node_id + i)for i=0..V-1. - Bias for locality: Multiply position by a locality weight (e.g., 1.0 for local DC nodes, 0.8 for remote). This clusters vnodes by topology, encouraging local shard assignment.
- Sort all vnodes by position in a balanced tree (e.g., CRDT-sorted set or AVL tree) for O(log N) lookups.
- For each node, generate V positions:
- Shard Ranges: Divide ring into ~10K-100K fixed-size shards initially (e.g., 2^160 / num_shards). Adjust dynamically.
Pseudocode: Ring Lookup
def find_shard_owner(token: int, ring: SortedDict[int, VNode]) -> VNode: # Successor: smallest vnode_pos >= token (wraps around) pos = ring.ceiling_key(token) if pos is None: pos = ring.first_key() # Wrap return ring.get(pos) class VNode: node_id: str topo_path: str # e.g., "DC1/ZoneA/Rack3/Node42" vnode_idx: int position: int3. Shard Assignment (Primary + Replicas)
- Primary Shard:
hash(key) -> token -> find_shard_owner(token) -> primary_node. - Replicas (Topology-Aware): For a primary on node P:
- Replica 1: Same rack as P (distance=1). Pick least-loaded vnode in rack.
- Replica 2: Same zone but different rack (distance=2). Or same DC.
- Fallback: Random healthy node minimizing distance, ensuring no more than RF/2 in same failure domain (rack/zone).
- Client Routing: Gossip protocol or central metadata service provides ring + replica locations. Clients cache and refresh every 10s.
Pseudocode: Replica Selection
def select_replicas(primary_vnode: VNode, ring: SortedDict, candidates: List[VNode], rf: int = 3) -> List[VNode]: replicas = [primary_vnode] for i in range(1, rf): # Prefer low distance, then low load best = min(candidates, key=lambda v: (distance(primary_vnode.topo_path, v.topo_path), v.node_load)) if distance(...) <= 2: # Same zone max replicas.append(best) candidates.remove(best) return replicas4. Hotspot Detection
Hotspots occur when a shard/node exceeds thresholds (e.g., 80% CPU, 2x avg QPS).
-
Monitoring:
- Per-shard metrics aggregated every 30s via gossip/central store.
- Hot key detection: Sample 1% requests; if a key >10% of shard QPS, "pre-split".
- Node hotspot: Any metric > threshold for 5min.
-
Detection Levels:
Level Trigger Action Shard QPS > 2x avg Split shard Node CPU > 90% Migrate shards to underloaded nodes Rack/Zone Imbalance > 20% Cross-rack rebalance
Pseudocode: Hotspot Check
def is_hotspot(shard: Shard, avg_qps: float) -> bool: return shard.qps > 2 * avg_qps or shard.cpu > 0.8 def detect_hot_keys(shard_requests: List[Key], sample_rate=0.01) -> List[Key]: counts = Counter(sampled_keys) return [k for k, c in counts.items() if c > 0.1 * len(sampled_keys)]5. Rebalancing Mechanisms
Rebalancing is incremental (batches of 1-5% shards/move at a time) to avoid thundering herd.
5.1 Node Join/Leave
- Join: New node gets ~1/V of tokens from each neighbor vnode on the ring (standard consistent hashing). Insert new vnodes, stream data.
- Leave/Fail: Redistribute its shards to successors. Use hinted handoff for temporary failures.
5.2 Load-Based Rebalancing
- Periodic Scan (every 5min):
- Compute target load: total_shards / num_nodes.
- Overloaded nodes donate shards to underloaded (prefer same zone/rack).
- Move cost:
data_size * network_distance_cost(higher cost for cross-DC).
- Hotspot Mitigation:
- Split: Hot shard -> 2 equal halves. Update metadata, stream half data.
- Migrate: Move entire shard to low-load node (topology-preferred).
- Pre-split: For hot keys, create sub-shards.
Pseudocode: Rebalancer
def rebalance(ring, node_loads: Dict[str, float], topo_tree): donors = [n for n, load in node_loads.items() if load > 1.2 * avg_load] receivers = [n for n, load in node_loads.items() if load < 0.8 * avg_load] for donor in sorted(donors, key=lambda n: node_loads[n], reverse=True): for shard in donor.overloaded_shards: target = min(receivers, key=lambda r: ( distance(donor.topo_path, r.topo_path), node_loads[r] # Least loaded )) if distance(...) <= 2: # Only intra-zone migrate_shard(shard, donor, target) stream_data(shard, donor, target) update_ring(shard.start, shard.end, target_vnode)5.3 Cooldown and Safety
- Rate limit: Max 5% cluster traffic for rebalancing.
- Drain: Stop writes during migration, use versioned reads.
- Backoff: No rebalance on same shard/node for 10min.
6. Implementation Notes
- Metadata: Stored in central config (Etcd) or DHT.
{shard_id: {primary, replicas, load}}. - Consistency: Strong (via Raft/Paxos per shard) or eventual (CRDTs for ring).
- Fault Tolerance: Quorum writes (RF/2+1), anti-entropy repairs.
- Scalability: Handles 10K+ nodes, 1B+ shards.
- Evaluation Metrics:
Property Benefit Data Movement (join/leave) O(1/K) where K=vnodes Cross-DC traffic <5% (topology bias) Hotspot resolution <1min Balance ±10% load variance
7. Example Configuration
topology: hierarchy: [DC, Zone, Rack, Node] replication_factor: 3 vnodes_per_node: 256 hotspot_thresholds: qps_multiplier: 2.0 cpu: 0.8 rebalance: interval: 300s max_concurrent_migrations: 10This scheme ensures consistent hashing for minimal disruption, topology awareness for performance, hotspot resilience, and automated rebalancing. It can be implemented in ~5K LoC (Go/Rust). If you need code prototypes, simulations, or tweaks (e.g., for SQL/NoSQL), let me know!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.