parikshan

System: ID Generation

Reading time: ~22 minutes  ·  Prerequisites: Bit Manipulation, Binary Search  ·  Capstone: id-generation design problem (parikshan systems track). Generate 1M IDs/sec across 10 regions, collision-free, time-sortable, B-tree-friendly, leaking nothing about volume to outside observers.

ID generation looks trivial until the first time it isn't. Auto-increment in a single database works to a few thousand requests per second; UUIDs solve uniqueness but destroy locality; Snowflake fixes locality but reveals capacity; UUIDv7 looks like the modern compromise but has its own pitfalls. The choice ripples into B-tree page layout, cache locality, partition routing, and what an external observer can infer from your IDs. This primer walks the space of options used at Twitter/X, Instagram, Stripe, Discord, and the modern Postgres ecosystem, and shows where the bit-level patterns from the bank live.

The product behind the system

Twitter Snowflake is the canonical reference. Introduced around 2010 to replace MySQL auto-increment when Twitter's write rate outgrew a single master. The format is well known: 1 sign bit, 41 bits of timestamp (ms since a custom epoch of 2010-11-04 01:42:54.657 UTC, lasting about 69 years), 10 bits of machine ID (5 datacenter + 5 worker), 12 bits of sequence (4096 IDs per machine per ms). Twitter retired its original Scala implementation but the structure is preserved across re-implementations.

Instagram described their sharded ID scheme in a 2012 engineering post: 41 bits timestamp, 13 bits shard, 10 bits sequence, packed into a 64-bit BIGINT. The choice was driven by Postgres: they wanted the ID to encode the shard so the application could route reads without an extra lookup.

Discord publishes that they use Snowflake-style IDs (because they ingest from the Discord API which is Snowflake-shaped), and at one point exposed timestamp extraction in their developer docs as a feature. Discord makes millions of messages per second; an ID-per-message at that rate is a hard problem on its own.

Stripe uses prefixed, typed IDs like cus_abc123 and ch_xyz789. Internally they are random but encode a type prefix and a checksum. This is not for sortability; it is for typed parameter checks in code review and for "no, that is a charge ID, not a customer ID" debugging.

ULID and UUIDv7 (RFC 9562, published 2024) are the open-standard answers to "Snowflake but without the central registry". UUIDv7 is 128 bits: 48 bits of Unix-epoch milliseconds, 4 bits version (7), 12 bits random or counter, 2 bits variant, 62 bits random. Postgres 18 (2025) shipped native UUIDv7 support, which validated the format for the boring database world.

All these systems answer the same question with different bit budgets and operational stories: how do you generate unique, sortable, scalable identifiers without a single point of contention?

What the requirements actually are

Functional:

  1. Uniqueness: no two events ever get the same ID, globally, forever.
  2. Generation latency: an ID is produced in microseconds, ideally with no network round-trip.
  3. High generation rate: millions per second across the fleet.
  4. No central bottleneck: any node can generate an ID without coordinating with any other node.
  5. Sortable by time: newer IDs sort lexicographically (or numerically) after older ones. This is for database locality and human debuggability.
  6. Compact representation: 64 or 128 bits, ideally embedding in a database column without bloating the index.

Non-functional:

  1. Clock-skew tolerance: if a node's clock jumps backward, the system must not produce duplicates.
  2. Privacy / information leakage: an outsider should not be able to count your daily transaction volume from sequential IDs (Snowflake's original sin: timestamp + sequence reveals your TPS).
  3. Predictability resistance: an attacker cannot guess the next ID. Required for any URL exposed publicly (the Snapchat user-ID enumeration leak is the canonical lesson).
  4. Operational simplicity: no service to deploy, no config to manage if possible.
  5. Cross-language portability: produced and parsed in every language the company uses.
  6. Stable across replication and reshuffling: an ID survives a database resharding without renumbering.

The architect's framing

Four schemes cover 95% of production systems. The architecture for each is one component (a library) and one decision (which scheme).

  1. Auto-increment: the database assigns IDs sequentially as a side effect of insert. Works until write throughput exceeds one node.

  2. Snowflake-family: 64 bits split into (timestamp, machine ID, sequence). The machine ID is registered out-of-band, often via Zookeeper or via static config. Within a machine, generation is a local counter; no network round-trip per ID.

  3. UUIDv4 (random): 122 bits of randomness in a 128-bit field. Zero coordination, but no time ordering and large index bloat in B-trees.

  4. UUIDv7 / ULID (time-sortable): 48-bit ms timestamp followed by random/counter bits in a 128-bit field. Time-sortable like Snowflake, no central registry like UUIDv4, slightly more entropy than Snowflake. Now the default recommendation for new systems.

Architectural shape for the Snowflake family:

                +-----------------------+
   client --->  |  Process / SDK        |
                |  (local ID generator) |
                +--+----+----+----+-----+
                   |    |    |    |
                   v    v    v    v
   read clock --> [41-bit ms since epoch]
                   |
   load machine -> [10-bit machine ID]      <- registered at boot
                   |
   per-ms counter->[12-bit sequence]        <- atomic int, reset every ms
                   |
                   v
            pack into 64-bit long
                   |
                   v
                  ID

The "service" here is just a library; the only shared state is the machine ID, distributed once at boot. That single-decision-once-per-process is the whole reason Snowflake scales: every subsequent ID is local.

For UUIDv7, the picture is even simpler: drop the machine ID entirely, use cryptographic randomness for the lower 74 bits. No registry, no shared state, ever. The trade-off is that you cannot infer "which machine made this" from the ID; the bytes that used to identify the worker now identify nothing.

UUIDv7 layout (128 bits)

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                  unix_ts_ms (48 bits)                          |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          ...                                  |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 1 1 1|     rand_a (12 bits)     |1 0|         rand_b (62)     |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       rand_b continued                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

rand_a doubles as a monotonic counter within the same millisecond; this is what lets a single process generate millions of IDs per ms while keeping them in order.

The trade-offs we will name

64-bit vs 128-bit. A 64-bit BIGINT fits in a register, doubles up nicely in B-tree pages, and ships everywhere. A 128-bit UUID needs two registers, doubles the size of every index, doubles the size of every foreign key column. Postgres benchmarks show UUIDv7 indexes about 30-40% larger than BIGINT indexes for the same rows. If your database is going to hold a billion rows, that is real money. Pick BIGINT when you can; pick UUID when global uniqueness matters more than storage.

Time-ordered vs random. Time-ordered IDs (Snowflake, UUIDv7) insert at the right edge of a B-tree, which is sequential and cache-friendly. Random IDs (UUIDv4) insert all over the tree, causing page splits and write amplification. Instagram saw this concretely: switching from UUIDv4 to time-sortable IDs reduced write IO by an order of magnitude. The cost of time ordering is that an external observer can count your daily volume.

Information leakage. Snowflake IDs leak two things: rate (count IDs in a second, you have TPS) and timing (read the timestamp). For a public API like Twitter, this is okay; the tweet rate is already public. For a payments API like Stripe, this is unacceptable, which is why their public IDs are random (ch_3LkP9hL2QwXrYz) and the time ordering lives only in the internal database. Decide whether the ID is exposed externally and pick accordingly.

Machine ID assignment. Snowflake requires every worker to know its 10-bit machine ID, which means 1024 workers max. Zookeeper-based dynamic registration (the original Twitter approach) has operational cost. Static config has the risk of duplicate IDs after a misconfiguration. K8s-friendly approaches use the pod name's hash. UUIDv7 sidesteps this whole problem by using random bits instead of machine identity; this is one of the biggest reasons it has won mindshare.

Clock skew. If a node's clock jumps backward (NTP correction, VM live-migration), Snowflake will start generating IDs that look "earlier" than ones already issued. Standard mitigations: wait until the clock catches up before issuing more IDs, or detect skew and refuse to generate. UUIDv7 has the same problem but tolerates it slightly better because of the random tail. Practical advice: prefer a monotonic clock source (CLOCK_MONOTONIC) for the high bits where possible, even if it costs a bit of accuracy.

Predictability. Snowflake IDs are guessable: knowing one ID's timestamp and seeing roughly when others were created lets an attacker enumerate. Public-facing IDs must include unpredictable bits. UUIDv7 has 74 bits of randomness, which is enough to prevent enumeration. Snowflake-style IDs exposed publicly often add a checksum or a separate "slug" field.

Where the algorithms from this bank actually appear

Bit manipulation (primer 15). ID generation is bit packing in its purest form. Twitter's Snowflake packs three integers into a single 64-bit long by shifting and OR-ing: (timestamp << 22) | (machine_id << 12) | sequence. Extracting any of the three is (id >> shift) & mask. The exact patterns from single-number and number-of-1-bits. Many production ID libraries fail their unit tests on bit-mask boundaries; a senior reviewer with the primer-15 reflex catches these in code review.

Binary search (primer 05). Sharded systems route an ID to its database partition. If you partition by ID range ("IDs 0-999 go to shard A, 1000-1999 to shard B"), the routing layer does a binary search of the shard map. Same pattern as search-insert-position. Time-sortable IDs (Snowflake, UUIDv7) make this work; random IDs do not.

Arrays and hashing (primer 01). Database indexes over IDs are hash tables (for equality lookup) or B-trees (for range lookup). Both have well-known performance properties tied to insertion order. The locality argument for time-sortable IDs is exactly the subarray-sum-equals-k pattern flipped: instead of "remember the running sum so we can find one quickly", it is "produce values in order so the tree finds the right spot quickly".

Cycle / collision detection. A robust ID library tests itself against UUID collision rates at scale. The probability calculation is closer to the birthday problem: with 122 random bits, you can generate ~2^61 IDs before a 50% collision probability. The intuition transfers from happy-number (cycle in a stream) to "what is the expected first collision in a sequence of random draws".

Modular arithmetic. Per-millisecond sequence wrap is (sequence + 1) % 4096. The boundary handling (wait until next ms when sequence hits the cap) is exactly the kind of edge case that interview questions probe: what happens when 4096 IDs are requested in a single millisecond?

Sketch implementation

A production-grade Snowflake generator and a UUIDv7 generator, ~50 lines:

import time
import os
import threading
import secrets

class Snowflake:
    """Twitter-style 64-bit ID generator. Local, no network calls."""
    EPOCH_MS = 1288834974657  # 2010-11-04 01:42:54.657 UTC, the Twitter epoch

    def __init__(self, datacenter_id: int, worker_id: int):
        assert 0 <= datacenter_id < 32 and 0 <= worker_id < 32
        self.datacenter_id = datacenter_id
        self.worker_id = worker_id
        self._lock = threading.Lock()
        self._last_ms = -1
        self._sequence = 0

    def _now_ms(self):
        return int(time.time() * 1000)

    def next_id(self) -> int:
        with self._lock:
            now = self._now_ms()
            if now < self._last_ms:
                # Clock went backward. Refuse rather than risk a duplicate.
                raise RuntimeError(f"clock skew: now={now} last={self._last_ms}")
            if now == self._last_ms:
                self._sequence = (self._sequence + 1) & 0xFFF  # 12-bit mask
                if self._sequence == 0:
                    # Sequence exhausted this ms. Spin until next ms.
                    while now <= self._last_ms:
                        now = self._now_ms()
            else:
                self._sequence = 0
            self._last_ms = now

            timestamp = now - self.EPOCH_MS
            return (
                (timestamp << 22)
                | (self.datacenter_id << 17)
                | (self.worker_id << 12)
                | self._sequence
            )

    @staticmethod
    def extract_timestamp(snowflake_id: int) -> int:
        return (snowflake_id >> 22) + Snowflake.EPOCH_MS


def uuid7() -> bytes:
    """RFC 9562 UUIDv7. 128 bits, time-sortable, mostly random."""
    ts_ms = int(time.time() * 1000) & ((1 << 48) - 1)
    rand_a = secrets.randbits(12)              # 12 bits
    rand_b = secrets.randbits(62)              # 62 bits

    high = (ts_ms << 16) | (0x7 << 12) | rand_a   # version 7 in bits 48-51
    low  = (0b10 << 62) | rand_b                  # variant 10 in top two bits

    return high.to_bytes(8, "big") + low.to_bytes(8, "big")


def uuid7_to_timestamp_ms(b: bytes) -> int:
    return int.from_bytes(b[:6], "big")

What this sketch leaves out: NTP-skew detection that pauses generation rather than crashing, per-process counters that survive bursts above 4096/ms by stealing from rand_a (UUIDv7 supports this), monotonic counter mode of UUIDv7 (rand_a as a sub-ms counter), benchmark-grade thread safety using lock-free atomic CAS, and the K8s registration story for the machine ID.

What breaks at scale

Tier 0 (single process, single DB): SERIAL / AUTO_INCREMENT works fine. The first 10 million rows of any startup live happily on auto-increment.

Tier 1 (multi-region, low traffic): writes start hitting multiple regions and contention on the auto-increment counter becomes painful. Switch to UUIDs (v4 is acceptable here; volume is too low to suffer index bloat).

Tier 2 (10K-100K writes/sec): B-tree page splits from random UUIDs cause visible IO. Switch to UUIDv7 or Snowflake. Time-sortable IDs eliminate the page-split problem and bring write IO back to near-sequential.

Tier 3 (millions/sec across services): Snowflake's 4096-per-ms-per-worker becomes a real cap if not enough workers are deployed. Either provision more workers (each gets a unique machine_id) or use UUIDv7 with full 62 bits of entropy per ms (effectively no cap). Discord and Twitter both run at this scale.

Tier 4 (planet scale, regulatory-sensitive): predictability and information leakage become bigger problems than throughput. Public IDs become opaque tokens (Stripe's ch_* prefix scheme, Shopify's encrypted IDs); internal IDs stay Snowflake or UUIDv7 for database efficiency. The split between "internal ID" and "external token" is permanent at this scale.

Common permanent failure modes:

  • Clock skew duplicates: a VM live-migrates, its clock jumps, two IDs share a timestamp + sequence. Mitigation: refuse to issue while clock < last_seen_ms. Better mitigation: hybrid logical clocks for the high bits.
  • Worker ID collision: two workers boot with the same machine_id (config error). Result is silent duplicate IDs. Mitigation: register machine_id with a coordination service (etcd, Zookeeper) at boot; refuse to start if already taken.
  • Sequence exhaustion under burst: 4096/ms exceeded. Mitigation: spin until next ms (Twitter's choice) or steal bits from the random region (UUIDv7's choice). Never produce duplicates.
  • Index bloat from misuse: someone switched a high-traffic table to UUIDv4 "for security". The index doubled in size and writes slowed 10x. Mitigation: use UUIDv7 if you need UUID semantics; never UUIDv4 on a primary key for a high-write table.
  • Cross-system ID confusion: 123 could be a user or a project. Mitigation: typed prefixes (usr_123, prj_123) at every public surface. Stripe's pattern is the gold standard.

What an interview / staff-engineer review will ask

Q1: Why not just use auto-increment? A: Two reasons. (1) It serialises writes through one node, capping throughput at that node's write rate. (2) It leaks total volume to anyone who can see one ID. Auto-increment is correct for small systems and educational examples; it fails on both scaling and information-leakage criteria past a certain size.

Q2: Twitter Snowflake vs UUIDv7. Which would you pick today for a new service? A: UUIDv7 unless I need to fit in a 64-bit column. UUIDv7 has no machine-ID registry (operational simplicity), 74 bits of randomness (no enumeration risk), time-sortable (B-tree friendly), and is now an RFC standard with library and database support. Snowflake's only remaining edge is being 64 bits, which matters for storage if you have a billion-row table.

Q3: What happens when the clock goes backward? A: With Snowflake, you risk producing duplicates. Standard answer: refuse to issue new IDs until the clock catches up, log the event loudly, page someone. Better answer: use a hybrid logical clock so the timestamp portion is monotonic even when wall-clock isn't.

Q4: How do you make IDs unguessable for public URLs? A: Either use a fully random scheme (UUIDv4 is fine here since this is the rare case where the public ID is not also the primary key) or sign / encrypt the database ID before exposing it. Stripe wraps with a typed prefix and includes enough entropy that enumeration is infeasible. Snapchat learned this lesson the hard way when their user-ID enumeration enabled a phone-number scrape of 4.6M accounts.

Q5: A bug duplicated a million IDs into a database. What now? A: Find them: GROUP BY id HAVING count(*) > 1. Decide policy: keep first, keep last, merge, or fail. Then prevent recurrence: add a unique constraint at the database level (which exposes new duplicates as constraint violations rather than silent corruption), log the worker_id of every insert so you can blame correctly, and add tests for the boundary conditions (sequence wrap, clock skew).

In the AI-integrated workspace

ID generation is mostly invisible to the AI workspace until it isn't. Three places where it bites:

Agent-generated database schemas. An LLM asked to design a schema will reliably pick UUIDv4 as the default primary key, citing "uniqueness". This is the wrong default for any high-write table. A senior reviewer with the primer-15 reflex (bit packing, time ordering, B-tree locality) catches this immediately and rewrites to UUIDv7.

Idempotency keys. Every payment API exposes an idempotency key parameter (Stripe documented this pattern; everyone copies it). The key is a client-generated unique identifier. AI agents that retry failed API calls are big consumers of idempotency keys; they need to generate them correctly, which means UUIDv4 or a UUIDv7 from the agent's local clock. Wrong: reusing a key across logically distinct operations. Wrong: generating a new key on each retry (defeats the idempotency).

Trace IDs and span IDs. Every observability platform expects 128-bit trace IDs and 64-bit span IDs (the W3C Trace Context spec). For LLM-agent tracing (every tool call gets a span), the agent must generate these correctly. Most LLM frameworks (LangChain, LangGraph) now do this; older code rolled its own and produced collisions.

For parikshan, every problem submission gets a UUIDv7. The time-sortable property means querying "show me submissions from the last hour" hits a contiguous range in the index. The randomness in the lower bits prevents an attacker from enumerating submissions to scrape solutions. The 128 bits cost a few extra bytes per row, well worth it.

Variants and adjacent systems

ULID (Universally Unique Lexicographically Sortable Identifier): 128 bits, 48-bit ms timestamp, 80 bits random, encoded in Crockford Base32 (26 characters). Predates UUIDv7 by years and is essentially the same idea with a different encoding. Still widely used; UUIDv7 is taking over because it has an RFC.

KSUID (Segment's "K-Sortable Unique Identifier"): 27 bytes, second-resolution timestamp, 128 bits of randomness, Base62 encoded. Similar to ULID with different bit budget choices.

Nano ID: short (21 chars), URL-safe, random. Good for public-facing IDs where collision risk is acceptable.

Sortable IDs in NoSQL (DynamoDB, Cassandra): time-sortable IDs interact badly with hash-partitioned stores because all recent writes go to one partition (hot partition problem). Solution is to bucket the prefix so writes spread across partitions, or to use a composite key.

Hashids / Sqids: reversibly encode integers to short URL-safe strings. Used to expose database row IDs in URLs without leaking the numeric ID. Not a real obfuscation (the encoding is reversible without the salt) but enough to deter casual enumeration.

Versioned ULIDs and monotonic UUIDs: extensions that enforce strict monotonicity even within the same millisecond. Useful when you need a strict total order across all IDs from a process.

TSID (Time-Sorted Identifier): a 64-bit Snowflake-alike with a different bit layout. Popular in some Java ecosystems (the "tsid-creator" library).

The common pattern: any ID that has a timestamp prefix needs randomness to prevent enumeration, machine identity or per-process counters to handle the same-ms case, and a documented behavior on clock skew. Pick the bit budget to match your storage and exposure requirements; the algorithms are the same.