TASK
Implementation
Build a shard controller that manages shard assignment:
- Maintain configuration: which replica group owns which shards
- Support operations: Join (add group), Leave (remove group), Move (reassign shard)
- Replicate controller state with Raft for fault tolerance
- Distribute shards evenly across groups
- Provide configuration query API
The controller is the source of truth for shard ownership.
Sample Test Cases
Join new groupTimeout: 5000ms
Input
{"src":"c0","dest":"controller","body":{"type":"init","msg_id":1,"node_id":"controller","node_ids":["controller"]}}
{"src":"c1","dest":"controller","body":{"type":"join","msg_id":2,"gid":"g1","servers":["s1","s2"]}}
{"src":"c1","dest":"controller","body":{"type":"query","msg_id":3,"num":-1}}
Expected Output
{"src":"controller","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"controller","dest":"c1","body":{"type":"join_ok","in_reply_to":2,"msg_id":1}}
{"src":"controller","dest":"c1","body":{"type":"query_ok","in_reply_to":3,"msg_id":2,"version":1,"groups":{"g1":["s1","s2"]},"shards":{"0":"g1","1":"g1","2":"g1","3":"g1","4":"g1","5":"g1","6":"g1","7":"g1","8":"g1","9":"g1"}}}
Hints
Hint 1▾
Controller manages shard-to-group mapping
Hint 2▾
Use Raft for controller replication
Hint 3▾
Support join, leave, move operations
Resources
OVERVIEW
Theoretical Hub
Sharding
When data exceeds one machine's capacity, split it across multiple machines (shards). Each shard handles a subset of keys. Sharding provides horizontal scalability.
Shard Controller
The controller decides which shard goes where. It is typically a small Raft group for high availability. Configuration changes are versioned to coordinate migrations.
Key Concepts
shardingconfigurationcoordination
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python3
import sys
import json
class ShardConfig:
def __init__(self, num_shards=10):
self.num_shards = num_shards
self.version = 0
self.shard_to_group = {s: 0 for s in range(num_shards)} # 0 =
unassigned
self.groups = {} # gid -> [server_ids]
def clone(self):
c = ShardConfig(self.num_shards)
c.version = self.version + 1
c.shard_to_group = dict(self.shard_to_group)
c.groups = {gid: list(servers) for gid, servers in self.groups.items
()}
return c
class ShardController:
def __init__(self, raft_node):
self.raft = raft_node
self.configs = [ShardConfig()]
def join(self, gid, servers):
# TODO: Add group, rebalance shards
pass
def leave(self, gid):
# TODO: Remove group, reassign its shards
pass
def move(self, shard, gid):
# TODO: Move specific shard to group
pass