TASK
Implementation
Different ID schemes have different tradeoffs. Your task is to implement all three and return a comparison table.
Implement a compare_ids handler that generates one ID of each type and reports their properties:
Request: {"type": "compare_ids", "msg_id": 1}
Response: {"type": "compare_ids_ok", "in_reply_to": 1, "comparison": [
{"scheme": "uuid_v4", "id": "550e8400-e29b...", "bits": 128, "sortable": false, "causal": false},
{"scheme": "snowflake", "id": "7041429939834880", "bits": 64, "sortable": true, "causal": false},
{"scheme": "hlc", "id": "1234567-0-n1", "bits": 96, "sortable": true, "causal": true}
]}Sample Test Cases
Compare IDs returns three schemesTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare_ids","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
UUID v4 is random: 128 bits, no ordering, no coordination needed
Hint 2▾
Snowflake is timestamped: 64 bits, sorted, needs machine_id assignment
Hint 3▾
HLC is timestamped + causal: variable size, captures causality, needs clock sync
Hint 4▾
Compare: storage size, generation speed, uniqueness guarantee, sortability
Hint 5▾
Each approach has different tradeoffs for different use cases
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
UUIDSnowflakeHLCID tradeoffsbenchmarking
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
import uuid
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.hlc_pt = 0
self.hlc_lc = 0
self.sf_sequence = 0
self.sf_last_ts = -1
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 gen_uuid_v4(self):
# TODO: Generate a UUID v4 string
pass
def gen_snowflake(self):
# TODO: Generate a Snowflake ID integer
pass
def gen_hlc_id(self):
# TODO: Generate an HLC-based ID string "pt-lc-node"
pass
def main():
node = Node()