Implement Optimistic Concurrency Control - The Store

Implementation

Implement optimistic concurrency control (OCC). Read keys with version tracking, then commit only if no versions changed since the read.

Request:  {"type": "occ_begin", "msg_id": 1}
Response: {"type": "occ_begin_ok", "in_reply_to": 1, "txn_id": "t1"}

Request:  {"type": "occ_read", "msg_id": 2, "txn_id": "t1", "key": "x"}
Response: {"type": "occ_read_ok", "in_reply_to": 2, "value": "42", "version": 5}

Request:  {"type": "occ_commit", "msg_id": 3, "txn_id": "t1", "writes": [{"key": "x", "value": "43"}], "read_versions": [{"key": "x", "version": 5}]}
Response: {"type": "occ_commit_ok", "in_reply_to": 3, "committed": true, "new_version": 6}

Sample Test Cases

OCC commit succeeds with matching versionsTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"occ_begin","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"occ_commit","msg_id":3,"txn_id":"t1","writes":[{"key":"x","value":"1"}],"read_versions":[]}}

Expected Output

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

OCC aborts on version mismatchTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"occ_commit","msg_id":2,"txn_id":"t1","writes":[{"key":"x","value":"new"}],"read_versions":[{"key":"x","version":999}]}}

Expected Output

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

Hints

Hint 1▾

Read a set of keys and record their versions

Hint 2▾

At commit time, check that none of the versions have changed

Hint 3▾

If versions match, the transaction commits. Otherwise, abort and retry

Hint 4▾

OCC works well when conflicts are rare (optimistic assumption)

Hint 5▾

High contention leads to many aborts and retries

Implementation

Sample Test Cases

Hints

Resources

Theoretical Hub

Key Concepts