TASK
Implementation
Within a single millisecond, each Snowflake node can generate up to 4096 unique IDs (12-bit sequence counter). When traffic bursts exceed this limit, the generator must handle sequence overflow gracefully.
Your task is to implement the sequence counter:
- Initialize to 0 at the start of each new millisecond
- Increment by 1 for each ID generated in the same millisecond
- On overflow (sequence > 4095), spin-wait until the next millisecond, then reset
- Track maximum sequence reached per millisecond for throughput analysis
Implement a generate_batch message that generates N IDs at once:
Request: {"type": "generate_batch", "msg_id": 1, "count": 10}
Response: {"type": "generate_batch_ok", "in_reply_to": 1, "ids": [1, 2, 3, ...], "max_sequence": 9}All generated IDs must be unique and monotonically increasing.
Sample Test Cases
Single generate worksTimeout: 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}}
Batch of 5 produces 5 unique IDsTimeout: 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_batch","msg_id":2,"count":5}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
The sequence counter increments for each ID generated in the same millisecond
Hint 2▾
Reset the sequence to 0 when moving to a new millisecond
Hint 3▾
If the sequence overflows (>4095), wait until the next millisecond
Hint 4▾
Spin-waiting is acceptable here since millisecond transitions are fast
Hint 5▾
Track the max sequence reached for throughput analysis
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
sequence numberoverflow handlingspin waitthroughput limits
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
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
self.max_sequence_seen = 0
def current_time_ms(self):
return int(time.time() * 1000) - CUSTOM_EPOCH_MS
def wait_next_ms(self):
# TODO: Spin until the clock moves to the next millisecond
pass
def generate(self):
# TODO: Generate a single Snowflake ID
# Handle sequence rollover within same millisecond
pass
def generate_batch(self, count):
# TODO: Generate 'count' unique Snowflake IDs
# Return (ids_list, max_sequence_in_batch)
pass
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.generator = None