TASK
Implementation
Handle shard configuration changes:
- Replica groups poll controller for configuration updates
- Detect when shard assignment changes
- Start migration: fetch shards assigned to this group
- Complete migration before processing client requests
- Acknowledge migration to source groups
Groups must coordinate to ensure exactly-once transfer.
Sample Test Cases
Detect config changeTimeout: 5000ms
Input
{"src":"c0","dest":"g1","body":{"type":"init","msg_id":1,"node_id":"g1","node_ids":["g1","g2"]}}
{"src":"c0","dest":"g1","body":{"type":"set_config","msg_id":2,"version":1,"shards":[0,1,2]}}
{"src":"controller","dest":"g1","body":{"type":"config_update","msg_id":3,"version":2,"shards":[0,1]}}
Expected Output
{"src":"g1","dest":"c0","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"g1","dest":"c0","body":{"type":"set_config_ok","in_reply_to":2,"msg_id":1}}
{"src":"g1","dest":"controller","body":{"type":"config_update_ok","in_reply_to":3,"msg_id":2,"applied":true}}
Hints
Hint 1▾
Poll controller for new configs
Hint 2▾
Process configs in order
Hint 3▾
Coordinate between replicas
OVERVIEW
Theoretical Hub
Configuration Versioning
Configurations are versioned. Groups must apply configurations in order. Skip a version and you might miss a shard assignment, leading to data loss.
Migration Coordination
When shards move, both source and destination must coordinate. Source stops serving the shard, sends data, destination takes over. Use config version to track progress.
Key Concepts
configurationcoordinationatomic transition
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
35
#!/usr/bin/env python3
import sys
import json
import threading
import time
class ShardedKVGroup:
def __init__(self, gid, controller):
self.gid = gid
self.controller = controller
self.current_config = None
self.data = {} # shard -> {key -> value}
self.lock = threading.Lock()
def poll_config(self):
# TODO: Get latest config from controller
pass
def apply_config(self, new_config):
# TODO: Detect shard changes
# TODO: Start migrations
pass
def _shards_to_receive(self, old_config, new_config):
# TODO: Find shards newly assigned to this group
pass
def _shards_to_send(self, old_config, new_config):
# TODO: Find shards no longer assigned to this group
pass
def receive_shard(self, shard, data):
# TODO: Accept shard data from another group
pass