Snowflake ID Generator

Design a unique ID generator in the style of Twitter's Snowflake. Each id fits in a signed 64-bit integer and is roughly time-ordered. IDs are globally unique when workers have distinct machine IDs and follow safe restart and lease-reuse rules — with **no per-id coordination** between workers. A worker mints ids locally from its own clock plus a machine id leased once at start-up, so minting is a clock read and two shifts: no network round trip, no shared counter, no lock in this single-threaded simulation. The id layout is 41 bits of milliseconds since a custom epoch, 10 bits of machine id, and 12 bits of per-millisecond sequence: ``` 0 | 41 bits: ms since epoch | 10 bits: machine id | 12 bits: sequence ^-- always 0 (ids fit in a signed 64-bit integer) ``` That gives 4,096 ids per millisecond per worker (a theoretical bit-budget ceiling of about 4M per second per worker, not a measured Python throughput), 1,024 workers, and a timestamp lifetime of about 69 years from the epoch. The epoch is 2024-01-01T00:00:00Z. Clocks are unreliable, so the generator must survive them: - **The logical clock never moves backwards.** If the wall clock steps backwards, the generator keeps minting from the last millisecond it used, with the sequence still incrementing — a small step is absorbed and ids stay unique and increasing. - **A large backwards step is an incident, never a duplicate.** The generator tolerates the logical clock running ahead of the wall clock by at most `max_drift_ms` (default 10 ms). Beyond that budget it refuses to mint and raises `ClockDriftError` — an operator must fix the clock; the generator must never mint a duplicate. - **Sequence overflow borrows the next millisecond** rather than spinning: if a worker mints more than 4,096 ids in one millisecond, the 4,097th id carries the next millisecond with sequence 0. Borrowing is bounded by the same drift budget. Machine ids are leased once at start-up in the real system (ZooKeeper/etcd, ephemeral node, 30 s lease, renewed every 10 s); a worker that cannot renew its lease must stop minting before the lease expires. Leasing is out of scope for this problem — the machine id is passed to the constructor. Simulation note: the browser cannot run real threads (no SharedArrayBuffer), and this site's Python runs single-threaded in Pyodide — so this problem is a deterministic simulation of the single-worker design. The clock is injected: the generator takes a `clock` argument, a callable returning seconds since the Unix epoch, defaulting to `time.time`. Tests use a fake clock, so behaviour is testable without threads or real time. The scaling discussion below is the real-world version. Constraints - `0 <= machine_id <= 1023` (default layout); otherwise `ValueError`. - `max_drift_ms >= 0`; otherwise `ValueError`. - Bit counts: each `>= 1` and the three total 63; otherwise `ValueError`. - The wall clock must be at or after the epoch and inside the 41-bit lifetime; otherwise `ValueError`. - No `threading`, no randomness, no wall-clock reads inside the generator except through the injected `clock` (which defaults to `time.time`). - Deterministic output contract: `next_id()` returns an `int`; `decompose()` returns a `SnowflakeParts` with exact `timestamp_ms` / `machine_id` / `sequence`; `created_at` is a timezone-aware UTC `datetime`. Examples - `decompose(192656126771200000)` → timestamp `2025-06-15T15:06:40.000Z`, machine `0`, sequence `0` (epoch 2024-01-01T00:00:00Z). - Burst of 5,000 ids in one frozen millisecond → all unique, strictly sorted; the burst borrows 1 ms; the last id is at +1 ms with sequence 903. - Clock steps back 3 ms → the next id is still strictly greater than the previous one. - Clock steps back 50 ms with `max_drift_ms=5` → `ClockDriftError`: `logical clock would be 50 ms ahead of the wall clock (limit 5 ms); refusing to mint`. (Note: the handbook demo quotes "54 ms" for a longer sequence in which the logical clock had already moved 4 ms ahead before the step back. The minimal repro here — one mint, then a single 50 ms step back — has a drift of exactly 50 ms. Do NOT force 54 into the test; the message format is the handbook's verbatim, only the drift number differs because the sequences differ.)

import time
from dataclasses import dataclass
from datetime import datetime, timezone

DEFAULT_EPOCH_MS = 1704067200000  # 2024-01-01T00:00:00Z in Unix ms


class ClockDriftError(Exception):
    """Raised when the logical clock is too far ahead of the wall clock."""


@dataclass(frozen=True)
class SnowflakeParts:
    timestamp_ms: int  # absolute Unix time in ms
    machine_id: int
    sequence: int

    @property
    def created_at(self) -> datetime:
        pass


@dataclass(frozen=True)
class Layout:
    timestamp_bits: int = 41
    machine_bits: int = 10
    sequence_bits: int = 12

    @property
    def max_machine_id(self) -> int:
        pass

    @property
    def max_sequence(self) -> int:
        pass

    @property
    def lifetime_ms(self) -> int:
        pass

    @property
    def machine_shift(self) -> int:
        pass

    @property
    def timestamp_shift(self) -> int:
        pass

    def compose(self, elapsed_ms: int, machine_id: int, sequence: int) -> int:
        pass

    def decompose(self, snowflake_id: int, epoch_ms: int) -> SnowflakeParts:
        pass


class SnowflakeGenerator:
    def __init__(self, machine_id: int, clock=None, layout=None,
                 epoch_ms: int = DEFAULT_EPOCH_MS, max_drift_ms: int = 10):
        pass

    def next_id(self) -> int:
        pass

    def decompose(self, snowflake_id: int) -> SnowflakeParts:
        pass

    @property
    def borrowed_ms(self) -> int:
        pass