Build a Mini TiKV with Raft + MVCC Regions - The Store

Implementation

Build a mini version of TiKV: partition the key space into regions, each with its own Raft group and MVCC storage.

Request:  {"type": "region_put", "msg_id": 1, "key": "user:1", "value": "Alice"}
Response: {"type": "region_put_ok", "in_reply_to": 1, "region_id": 1, "key_range": ["a", "m"]}

Request:  {"type": "region_get", "msg_id": 2, "key": "user:1"}
Response: {"type": "region_get_ok", "in_reply_to": 2, "value": "Alice", "region_id": 1}

Request:  {"type": "region_info", "msg_id": 3}
Response: {"type": "region_info_ok", "in_reply_to": 3, "regions": [
    {"id": 1, "range": ["a", "m"], "leader": "n1", "size_bytes": 1024},
    {"id": 2, "range": ["m", "z"], "leader": "n2", "size_bytes": 512}
]}

Request:  {"type": "region_split", "msg_id": 4, "region_id": 1, "split_key": "g"}
Response: {"type": "region_split_ok", "in_reply_to": 4, "new_regions": [
    {"id": 1, "range": ["a", "g"]},
    {"id": 3, "range": ["g", "m"]}
]}

Sample Test Cases

Put routes to correct regionTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"region_put","msg_id":2,"key":"apple","value":"fruit"}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Region info shows partitionsTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"region_info","msg_id":2}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

TiKV splits the key space into ranges called regions

Hint 2▾

Each region has its own Raft group for replication

Hint 3▾

A region splits when it gets too large (e.g., > 96MB)

Hint 4▾

Cross-region transactions use 2-phase commit

Hint 5▾

The placement driver (PD) manages region-to-node mapping

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts