codejump
MediumPro challengePythonJavaScriptTypeScript

System Design — Snowflake ID Generator

System DesignDistributed SystemsBit Manipulation

Distributed systems need unique, roughly time-sortable ids without a central database counter.
Twitter's Snowflake packs three fields into one integer: a timestamp, a worker id
and a per-millisecond sequence.

solve(args, ops) builds new Snowflake(workerId, epoch, sequenceBits) —
args = [workerId, epoch, sequenceBits] — and replays ops:

  • next(now) — return a new id as a decimal string (ids exceed 2^53), or the string

"clock_backwards" if the clock moved back.

The id is (ms << (10 + sequenceBits)) | (workerId << sequenceBits) | sequence, where
ms = now - epoch (use BigInt in JavaScript; Python ints are unbounded). The worker id uses
10 bits.

State: the last millisecond lastMs and the sequence used in it (start with lastMs = -1).

1. ms < lastMs → return "clock_backwards" and change nothing.
2. ms === lastMs → sequence = (sequence + 1) & mask where mask = (1 << sequenceBits) - 1.
 If it wrapped to 0, the millisecond is exhausted: wait for the next one, i.e. use
 ms = lastMs + 1 with sequence = 0.
3. ms > lastMs → sequence = 0.

Finally set lastMs = ms.

Example — args = [1, 1000, 12]

next(1001) → "4198400"   next(1001) → "4198401"   next(1002) → "8392704"   next(1000) → "clock_backwards"

Sample tests

Test #1Sequence, new millisecond and clock going backwards
Input: [[1,1000,12],[["next",1001],["next",1001],["next",1002],["next",1000],["next",1002]]]
Output: ["4198400","4198401","8392704","clock_backwards","8392705"]
Test #2Sequence overflow waits for the next millisecond
Input: [[3,0,2],[["next",5],["next",5],["next",5],["next",5],["next",5],["next",6]]]
Output: ["20492","20493","20494","20495","24588","24589"]
Test #3Worker 0
Input: [[0,0,12],[["next",1],["next",1],["next",2]]]
Output: ["4194304","4194305","8388608"]
← All challenges