Multi-Version Concurrency Control (MVCC)

Write a C program that implements a simplified MVCC key-value store.

Requirements:

• Define a Version struct: value (int), commit_ts (int), next (pointer to older version)
• Define a KeyEntry struct: key (int), head (pointer to newest version)
• Implement write_key(store, key, value, commit_ts): add a new version at the head of the chain
• Implement read_key(store, key, read_ts): traverse the version chain and return the value with the largest commit_ts <= read_ts
• Simulate transactions:
  • T1 starts at TS=1, writes key=10 value=100 at TS=2
  • T2 starts at TS=3, reads key=10 (should see 100)
  • T2 writes key=10 value=200 at TS=4
  • T3 starts at TS=1, reads key=10 (should still see 100 — snapshot isolation)
  • T4 starts at TS=5, reads key=10 (should see 200)
• Print the version chain for key=10 showing all versions and their commit timestamps
• Print what each transaction sees
• Implement garbage_collection(store, oldest_active_ts): remove versions with commit_ts < oldest_active_ts
• Run GC with oldest_active_ts=3 and show the remaining version chain
• Explain how MVCC prevents dirty reads and non-repeatable reads