TASK
Implementation
Spanner achieves external consistency by waiting out the uncertainty window: before committing a transaction at timestamp T, wait until TrueTime.now().earliest > T. This guarantees causally-later transactions see this commit.
Implement a commit handler with wait-out-uncertainty:
Request: {"type": "commit", "msg_id": 1, "key": "x", "value": "v1"}
Response: {"type": "commit_ok", "in_reply_to": 1, "commit_ts": 1234567, "wait_ms": 7}
Request: {"type": "commit_stats", "msg_id": 2}
Response: {"type": "commit_stats_ok", "in_reply_to": 2, "total_commits": 5, "total_wait_ms": 35, "avg_wait_ms": 7}Sample Test Cases
Commit stores valueTimeout: 10000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"commit","msg_id":2,"key":"x","value":"v1"}}
{"src":"c1","dest":"n1","body":{"type":"kv_read","msg_id":3,"key":"x"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Commit stats with no commitsTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"commit_stats","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "commit_stats_ok", "total_commits": 0, "total_wait_ms": 0, "avg_wait_ms": 0, "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
Before committing, wait until TrueTime.now().earliest > commit_timestamp
Hint 2▾
This guarantees that any future read will see this commit
Hint 3▾
The wait duration equals the uncertainty window
Hint 4▾
This is how Spanner achieves external consistency without locks
Hint 5▾
Track total wait time for performance analysis
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
external consistencycommit waitSpannerlinearizability
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
#!/usr/bin/env python3
import sys, json, time
class Node:
def __init__(self):
self.node_id=None;self.node_ids=[];self.next_msg_id=0;self.
uncertainty_ms=7;self.store={}
self.total_commits=0;self.total_wait_ms=0
def send(self,d,b):b["msg_id"]=self.next_msg_id;self.next_msg_id+=1;print
(json.dumps({"src":self.node_id,"dest":d,"body":b}),flush=True)
def reply(self,r,b):b["in_reply_to"]=r["body"]["msg_id"];self.send(r
["src"],b)
def now_ms(self):return int(time.time()*1000)
def main():
node=Node()
for line in sys.stdin:
line=line.strip()
if not line:continue
msg=json.loads(line);body=msg["body"];t=body["type"]
if t=="init":node.node_id=body["node_id"];node.node_ids=body
["node_ids"];node.reply(msg,{"type":"init_ok"})
elif t=="commit":pass
elif t=="commit_stats":pass
elif t=="kv_read":
k=body["key"]
if k in node.store:node.reply(msg,{"type":"kv_read_ok","key":k,
"value":node.store[k]["value"],"ts":node.store[k]["ts"]})
else:node.reply(msg,{"type":"error","code":20,"text":"Key not
found"})
if __name__=="__main__":main()