TASK
Implementation
The timestamp component of a Snowflake ID uses 41 bits to represent milliseconds since a custom epoch. Using Unix epoch (1970-01-01) wastes over 50 years of timestamp space. A custom epoch starting in 2024 gives the system ~69 years of IDs.
Your task is to:
- Implement timestamp generation relative to a custom epoch (2024-01-01 00:00:00 UTC)
- Validate that the timestamp fits within 41 bits
- Implement a
time_infomessage that reports the current timestamp state
Request: {"type": "time_info", "msg_id": 1}
Response: {"type": "time_info_ok", "in_reply_to": 1,
"current_ms": 1234567,
"custom_epoch_ms": 1704067200000,
"max_timestamp_ms": 2199023255551,
"years_remaining": 69}Also implement generate that uses the custom epoch for timestamps, and verify IDs are monotonically increasing:
Request: {"type": "generate", "msg_id": 1}
Response: {"type": "generate_ok", "in_reply_to": 1, "id": 1234567890}Sample Test Cases
Generate produces a numeric IDTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"generate","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Time info returns epoch and years remainingTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"time_info","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
A custom epoch starting in 2024 gives you ~69 years before 41 bits overflow
Hint 2▾
Unix epoch (1970) would waste 54 years of timestamp space
Hint 3▾
Use time.time() * 1000 to get current timestamp in milliseconds
Hint 4▾
Subtract the custom epoch to get relative milliseconds
Hint 5▾
Check that the timestamp fits in 41 bits before composing the ID
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
timestampepochtime representationoverflow planning
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
CUSTOM_EPOCH_MS = 1704067200000 # 2024-01-01T00:00:00Z
MAX_TIMESTAMP = (1 << 41) - 1 # 2199023255551
SEQUENCE_BITS = 12
MACHINE_BITS = 10
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1
class SnowflakeGenerator:
def __init__(self, machine_id):
self.machine_id = machine_id
self.sequence = 0
self.last_timestamp = -1
def current_time_ms(self):
# TODO: Return current time in ms relative to custom epoch
pass
def validate_timestamp(self, timestamp_ms):
# TODO: Check if timestamp fits in 41 bits
# Return True if valid, raise ValueError if not
pass
def time_info(self):
# TODO: Return a dict with current_ms, custom_epoch_ms,
# max_timestamp_ms, and years_remaining
pass
def generate(self):
# TODO: Generate a Snowflake ID using the custom epoch
pass
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0