Implement Multi-Version Concurrency Control - The Store

                      TASK
                    

Implementation

Implement MVCC: keep multiple versions of each key. Readers get a consistent snapshot without blocking writers.

Request:  {"type": "mvcc_put", "msg_id": 1, "key": "x", "value": "v1", "timestamp": 100}
Response: {"type": "mvcc_put_ok", "in_reply_to": 1, "version": 1, "timestamp": 100}

Request:  {"type": "mvcc_put", "msg_id": 2, "key": "x", "value": "v2", "timestamp": 200}
Response: {"type": "mvcc_put_ok", "in_reply_to": 2, "version": 2, "timestamp": 200}

Request:  {"type": "mvcc_get", "msg_id": 3, "key": "x", "read_timestamp": 150}
Response: {"type": "mvcc_get_ok", "in_reply_to": 3, "value": "v1", "version": 1, "as_of_timestamp": 100}

Request:  {"type": "mvcc_get", "msg_id": 4, "key": "x", "read_timestamp": 250}
Response: {"type": "mvcc_get_ok", "in_reply_to": 4, "value": "v2", "version": 2, "as_of_timestamp": 200}

Sample Test Cases

Read at old timestamp gets old versionTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_put","msg_id":2,"key":"x","value":"old","timestamp":100}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_put","msg_id":3,"key":"x","value":"new","timestamp":200}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_get","msg_id":4,"key":"x","read_timestamp":150}}

Expected Output

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

Read at current timestamp gets latestTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_put","msg_id":2,"key":"x","value":"old","timestamp":100}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_put","msg_id":3,"key":"x","value":"new","timestamp":200}}
{"src":"c1","dest":"n1","body":{"type":"mvcc_get","msg_id":4,"key":"x","read_timestamp":300}}

Expected Output

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

Hints

Hint 1▾

Keep N versions of each key, each tagged with a commit timestamp

Hint 2▾

Readers get a consistent snapshot at their start timestamp

Hint 3▾

Writers create new versions without blocking readers

Hint 4▾

Garbage collect old versions that are no longer needed

Hint 5▾

This is how PostgreSQL, MySQL InnoDB, and TiKV work internally

Resources

MVCC in PostgreSQL

How PostgreSQL implements MVCC for concurrent access

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

MVCCversioned storagesnapshot isolationreaders never block writers

main.py

python