TASK
Implementation
Build a complete sharded KV store:
- Client determines shard for key
- Client routes to replica group owning shard
- If wrong group, get new config and retry
- Handle concurrent config changes
- Ensure linearizability within each shard
This combines all previous components into a working system.
Sample Test Cases
Route to correct shardTimeout: 5000ms
Input
{"src":"client","dest":"proxy","body":{"type":"init","msg_id":1,"node_id":"proxy","node_ids":["proxy"]}}
{"src":"controller","dest":"proxy","body":{"type":"config","msg_id":2,"version":1,"shards":{"0":"g1","1":"g1","2":"g1","3":"g1","4":"g2","5":"g2"}}}
{"src":"c1","dest":"proxy","body":{"type":"get","msg_id":3,"key":"mykey"}}
Expected Output
{"src":"proxy","dest":"client","body":{"type":"init_ok","in_reply_to":1,"msg_id":0}}
{"src":"proxy","dest":"controller","body":{"type":"config_ok","in_reply_to":2,"msg_id":1}}
{"src":"proxy","dest":"c1","body":{"type":"get_ok","in_reply_to":3,"msg_id":2,"key":"mykey"}}
Hints
Hint 1▾
Route requests to correct shard
Hint 2▾
Handle "wrong group" errors
Hint 3▾
Retry on configuration changes
OVERVIEW
Theoretical Hub
Putting It Together
A sharded KV store has: (1) shard controller managing configuration, (2) multiple replica groups each handling some shards, (3) clients that route requests based on configuration.
Client Retry
When a group receives a request for a shard it doesn't own, it returns an error. The client refreshes configuration and retries. This may happen multiple times during reconfiguration.
Key Concepts
sharded storageroutingend-to-end
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
36
37
38
39
#!/usr/bin/env python3
import sys
import json
class ShardedKVClient:
def __init__(self, controller, groups):
self.controller = controller
self.groups = groups # gid -> client
self.config = None
def _shard_for_key(self, key, num_shards=10):
return hash(key) % num_shards
def _refresh_config(self):
self.config = self.controller.query(-1)
def get(self, key):
# TODO: Route to correct group, handle errors
pass
def put(self, key, value):
# TODO: Route to correct group, handle errors
pass
def _execute(self, shard, operation):
# TODO: Send to group, retry on wrong_group
pass
class ShardedKVServer:
def __init__(self, gid, controller, kv_store):
self.gid = gid
self.controller = controller
self.kv = kv_store
self.current_config = controller.query(-1)
def handle_request(self, shard, operation):
# TODO: Check shard ownership, process or reject
pass