TASK
Implementation
Hybrid Logical Clocks (HLC), used in CockroachDB and Spanner, combine physical time with a logical counter. The format is (physical_ms, logical_counter).
Rules for updating HLC on a local event or send:
- Get current physical time
pt - If
pt > hlc.pt: sethlc.pt = pt,hlc.lc = 0 - Else: keep
hlc.pt, incrementhlc.lc += 1
Implement an HLC with hlc_tick and hlc_get handlers:
Request: {"type": "hlc_tick", "msg_id": 1}
Response: {"type": "hlc_tick_ok", "in_reply_to": 1, "pt": 1234567, "lc": 0}Request: {"type": "hlc_get", "msg_id": 2}
Response: {"type": "hlc_get_ok", "in_reply_to": 2, "pt": 1234567, "lc": 0}Sample Test Cases
HLC tick returns pt and lcTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"hlc_tick","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
HLC get returns initial zero stateTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"hlc_get","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": "hlc_get_ok", "pt": 0, "lc": 0, "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
HLC is a tuple: (physical_time_ms, logical_counter)
Hint 2▾
Physical time comes from the system clock
Hint 3▾
Logical counter disambiguates events within the same millisecond
Hint 4▾
HLC always moves forward, even if clock goes backward
Hint 5▾
On send: if pt > max_pt, reset counter; else increment counter
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
HLChybrid clockphysical timelogical counter
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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
import time
class HLC:
def __init__(self):
self.pt = 0 # physical time in ms
self.lc = 0 # logical counter
def now_ms(self):
return int(time.time() * 1000)
def tick(self):
# TODO: Update HLC on local event
pass
def get(self):
return {"pt": self.pt, "lc": self.lc}
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.hlc = HLC()
def send(self, dest, body):
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
msg = {"src": self.node_id, "dest": dest, "body": body}
print(json.dumps(msg), flush=True)
def reply(self, request, body):
body["in_reply_to"] = request["body"]["msg_id"]
self.send(request["src"], body)
def main():
node = Node()
for line in sys.stdin: