Implement Snowflake ID Bit Layout - The Identifier

                      TASK
                    

Implementation

Twitter's Snowflake generates unique, roughly-sorted 64-bit IDs without coordination. The layout is:

| 1 bit unused | 41 bits timestamp | 10 bits machine ID | 12 bits sequence |
|     0        |   ms since epoch  |    0-1023          |    0-4095        |

Your task is to implement functions that:

Compose a Snowflake ID from its three components (timestamp_ms, machine_id, sequence)
Decompose a Snowflake ID back into its components
Handle the Maelstrom generate workload using Snowflake IDs

Implement a generate message handler:

Request:  {"type": "generate", "msg_id": 1}
Response: {"type": "generate_ok", "in_reply_to": 1, "id": 7041429939834880}

And a decompose handler for debugging:

Request:  {"type": "decompose", "msg_id": 2, "id": 7041429939834880}
Response: {"type": "decompose_ok", "in_reply_to": 2, "timestamp_ms": 1678886400000, "machine_id": 1, "sequence": 0}

Sample Test Cases

Init and generate produces an 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}}

Two sequential generates produce different 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","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"generate","msg_id":3}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Hints

Hint 1▾

Use left shift (<<) to position each component in the 64-bit integer

Hint 2▾

Timestamp goes in the top 41 bits, machine ID in the next 10, sequence in the bottom 12

Hint 3▾

Use bitwise OR (|) to combine the components

Hint 4▾

To extract components, use right shift (>>) and bitwise AND (&) with masks

Hint 5▾

Max IDs per ms per node = 2^12 = 4096

Resources

Twitter Snowflake (Original Announcement)

Twitter engineering blog post introducing Snowflake ID generation

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

bit manipulationSnowflake IDbit layoutscalability

main.py

python

#!/usr/bin/env python3
import sys
import json
import time
CUSTOM_EPOCH = 1704067200000  # 2024-01-01 00:00:00 UTC in ms
TIMESTAMP_BITS = 41
MACHINE_BITS = 10
SEQUENCE_BITS = 12
MAX_MACHINE_ID = (1 << MACHINE_BITS) - 1   # 1023
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1     # 4095
class SnowflakeGenerator:
    def __init__(self, machine_id):
        self.machine_id = machine_id & MAX_MACHINE_ID
        self.sequence = 0
        self.last_timestamp = -1
    def compose(self, timestamp_ms, machine_id, sequence):
        # TODO: Combine the three components into a 64-bit Snowflake ID
        # Use bit shifting and OR
        pass
    def decompose(self, snowflake_id):
        # TODO: Extract timestamp_ms, machine_id, sequence from a Snowflake 
        ID
        pass
    def generate(self):
        # TODO: Generate the next Snowflake ID
        # Handle same-millisecond sequences and overflow
        pass
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0