1. The problem: why is generating an ID hard?

On a single-server app you write id SERIAL PRIMARY KEY and forget about it: PostgreSQL hands out 1, 2, 3… Instagram is different. Posts, comments and likes are spread across thousands of database shards (see Sharding), and the write volume is enormous — assume, for practice, ~100M posts, ~1B likes and ~100M comments per day, peaking at well over 100,000 new objects per second.

• If each shard uses its own auto-increment counter, shard 7 and shard 912 will both create a post with ID 1,000,000. IDs collide the moment you look at data across shards (in caches, in Kafka events, in the feed, in URLs).
• If one central database hands out all IDs, every write in the company depends on it: a single point of failure and a throughput ceiling, plus a cross-data-center round trip for each ID.
• If you use random 128-bit UUIDs, you get uniqueness but lose ordering and bloat every index (more on this below).

We want IDs that are unique without asking anyone, small, and that sort by creation time — so "show the newest posts" is just "sort by ID descending".

2. Requirements for Instagram's IDs

"Roughly" time-sortable is deliberate: IDs generated on different machines in the same few milliseconds may be slightly out of order (because their clocks differ slightly). That's fine for a feed; it is not a substitute for a strict global order.

3. The options, one by one

3.1 Database auto-increment

One database with an auto-increment column (SERIAL, AUTO_INCREMENT, IDENTITY) generates every ID.

• Pros: simple, compact (64-bit), perfectly ordered, dense.
• Cons: single point of failure and write bottleneck; doesn't work across shards; IDs are guessable and leak business volume (a competitor can create two posts a day apart and subtract the IDs to learn your daily post count — the classic "German tank problem").

3.2 Multi-master with step offsets

Run N ID databases; server i starts at i and increments by N. With N = 2: server A produces 1, 3, 5…, server B produces 2, 4, 6… MySQL supports this directly with auto_increment_increment = N and auto_increment_offset = i.

• Pros: no SPOF; doubles (N×) throughput; still 64-bit.
• Cons: adding a server changes N and requires re-planning offsets; IDs aren't time-ordered across servers (A may be at 1,000,001 while B is at 5,000,002); still a network round trip per ID.

3.3 UUID v4 — and the index locality problem

A UUID is a 128-bit identifier, written as 36 characters like 9f1c2a7e-3b4d-4e8f-a1b2-c3d4e5f60718. Version 4 fills 122 bits with randomness. Any machine can generate one offline; the chance of a collision is negligible (you'd need ~2.7 × 10¹⁸ UUIDs for a 50% chance of a single duplicate).

So why not use them everywhere? Two reasons: size (16 bytes binary, 36 as text — every index and every foreign key that references it doubles or more) and, more importantly, randomness destroys index locality.

 B-tree primary index (leaf pages ordered by key)

 Time-ordered IDs:  [p1][p2][p3] ... [p97][p98][p99*] ← every insert lands in the LAST page
                                                       (it stays hot in RAM; pages fill 100%)

 Random UUID v4:    [p1][p2*][p3] ... [p41*][p42] ... [p97][p98*][p99]
                         ↑ inserts land on random pages all over the index
                         → each insert may read a cold page from disk
                         → full pages split in half (~50-70% fill), index bloats
                         → WAL / replication volume grows, cache hit ratio falls

With billions of rows, the index is far larger than RAM. Time-ordered keys keep the "insert frontier" (the right-most pages) in memory; random keys make every insert a potential random disk read and page split. Benchmarks routinely show insert throughput dropping several-fold once a random-UUID index outgrows memory. Random IDs also give no time ordering, so you need an extra created_at index for "newest first" queries. (See Indexing for how B-trees work.)

3.4 UUID v7 and ULID — time-ordered 128-bit IDs

Newer formats keep the "generate anywhere" property but put a timestamp first:

 UUID v7 (RFC 9562, 2024) — 128 bits
 | unix_ts_ms (48) | ver=7 (4) | rand_a (12) | var (2) | rand_b (62) |

 ULID — 128 bits, encoded as 26 Crockford base32 chars, e.g. 01JAZ3K5T8X2N9QW4VBCDEFGHJ
 | timestamp ms (48) | randomness (80) |

• Pros: time-sortable (good B-tree locality), no coordination, no machine IDs to assign, standard library support growing (PostgreSQL 18 adds a native uuidv7() function). ULID's text form is URL-friendly and lexicographically sortable.
• Cons: still 128 bits (2× a BIGINT); ordering within the same millisecond on different machines is random; carries no routing information. A great default when 128 bits is acceptable — and a common modern interview answer.

3.5 Ticket servers (Flickr)

Flickr publicly described a "ticket server": a dedicated MySQL database whose only job is handing out IDs from an auto-increment column, using a one-row table trick:

CREATE TABLE tickets64 (
  id   BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  stub CHAR(1) NOT NULL DEFAULT '',
  PRIMARY KEY (id), UNIQUE KEY (stub)
) ENGINE=InnoDB;

REPLACE INTO tickets64 (stub) VALUES ('a');   -- deletes + reinserts the single row, bumping id
SELECT LAST_INSERT_ID();                       -- per-connection, so concurrent clients don't clash

For availability they ran two ticket servers, one producing odd and one even numbers (step offsets), with clients round-robining between them.

• Pros: 64-bit, compact, simple, roughly ordered, battle-tested.
• Cons: a network round trip per ID; the ticket servers are a central dependency and a throughput ceiling; odd/even servers drift apart so ordering is loose.
• Common improvement — segment (range) allocation: instead of one ID per request, each app server grabs a block (e.g. 1,000 IDs: UPDATE seq SET max_id = max_id + 1000) and hands them out locally from memory. One DB round trip per 1,000 IDs; a crash wastes at most the unused part of a block. Meituan's open-source Leaf uses this "segment mode" with double buffering.

3.6 Twitter Snowflake

In 2010 Twitter moved off MySQL auto-increment and published Snowflake, a service that composes a 64-bit ID from three fields, so each generator can work independently:

• 41-bit timestamp — milliseconds since a custom epoch (Twitter used 1288834974657 = 2010-11-04 01:42:54.657 UTC). 2⁴¹ ms ≈ 69.7 years, so Twitter's IDs last until ~2080. A custom epoch (instead of 1970) avoids wasting 40 years of range.
• 10-bit machine ID — up to 1,024 generators (Twitter split it as 5 bits data center + 5 bits worker). Assigned via configuration or a coordination service like ZooKeeper — coordination only at startup, never per ID.
• 12-bit sequence — a counter that resets every millisecond: up to 4,096 IDs per millisecond per machine (~4.1M/s per machine). If exhausted, the generator waits for the next millisecond.

Snowflake-style IDs are used widely: Discord, Mastodon and many others use variants; Sony's Sonyflake uses 39 bits of 10 ms units, 8 bits of sequence and 16 bits of machine ID (more machines, fewer IDs per machine, longer lifetime).

3.7 Comparison

4. Instagram's ID scheme

In 2012 Instagram's engineering team published a well-known post ("Sharding & IDs at Instagram") describing how they generate IDs for their sharded PostgreSQL. They considered the options above and rejected them: UUIDs were too big and unordered; a Snowflake service was another moving part to run (with ZooKeeper for machine IDs); ticket servers were a central dependency. Their solution: make each logical shard generate its own IDs inside PostgreSQL, embedding the shard number in the ID.

4.1 The bit layout

• 41 bits — time: milliseconds since a custom epoch in 2011 → ~69.7 years of range. (Because PostgreSQL's BIGINT is signed and this layout uses all 64 bits, the top bit becomes 1 after 2⁴⁰ ms ≈ 34.8 years — around 2045–2046 — at which point IDs would turn negative and sort incorrectly unless the scheme is adjusted. A fun detail to mention in an interview.)
• 13 bits — logical shard ID: up to 8,192 logical shards. Instagram described creating thousands of logical shards (implemented as PostgreSQL schemas) mapped onto a much smaller number of physical database servers, so shards can later be moved to new machines without re-sharding data.
• 10 bits — sequence: each table in each shard has a normal PostgreSQL sequence; take nextval() mod 1024. Up to 1,024 IDs per shard per millisecond.

4.2 Generated inside PostgreSQL

The ID is produced by a PL/pgSQL function used as the column default, so every INSERT gets an ID atomically in the same database that stores the row — no extra service, no extra network hop. A function in the spirit of the published one (each logical shard is a schema, here shard_1341, with its own copy of the function and its own shard constant):

CREATE SEQUENCE shard_1341.post_id_seq;

CREATE OR REPLACE FUNCTION shard_1341.next_id(OUT result BIGINT) AS $$
DECLARE
    our_epoch  BIGINT := 1293840000000;   -- 2011-01-01T00:00:00Z in ms (custom epoch)
    shard_id   INT    := 1341;            -- this schema's logical shard number
    seq_id     BIGINT;
    now_millis BIGINT;
BEGIN
    SELECT nextval('shard_1341.post_id_seq') % 1024 INTO seq_id;
    SELECT FLOOR(EXTRACT(EPOCH FROM clock_timestamp()) * 1000) INTO now_millis;
    result := (now_millis - our_epoch) << 23;   -- 41 bits of time in the high bits
    result := result | (shard_id << 10);          -- 13 bits of shard
    result := result | seq_id;                    -- 10 bits of sequence
END;
$$ LANGUAGE plpgsql;

CREATE TABLE shard_1341.posts (
    id         BIGINT NOT NULL DEFAULT shard_1341.next_id() PRIMARY KEY,
    user_id    BIGINT NOT NULL,
    caption    TEXT,
    media_key  TEXT NOT NULL
);

Notes: clock_timestamp() (not now()) is used because now() is frozen at the start of the transaction; PostgreSQL sequences are non-transactional and lock-free enough to handle very high rates; and the PRIMARY KEY constraint is a final safety net — in the unlikely event of a duplicate, the insert fails and can be retried instead of silently corrupting data. (Instagram's post used its own epoch constant and schema names; the structure is the same.)

4.3 Worked example: encoding an ID

User 31341 posts a photo on 2026-10-23 at 09:20:00.000 UTC (14:50 IST). Suppose users map to logical shards by user_id % 2000, so the shard is 31341 mod 2000 = 1341, and this shard's sequence returns 1001.

 Step 1 — time since epoch
   now   = 1,792,747,200,000 ms   (2026-10-23T09:20:00Z in Unix ms)
   epoch = 1,293,840,000,000 ms   (2011-01-01T00:00:00Z)
   t     =   498,907,200,000 ms   (needs 39 of the 41 bits)

 Step 2 — shift each field into position
   t     << 23  = 4,185,136,929,177,600,000
   1341  << 10  =                 1,373,184
   1001 mod 1024 =                     1,001

 Step 3 — OR them together (no overlapping bits, so OR = add)
   id = 4,185,136,929,177,600,000 + 1,373,184 + 1,001
      = 4,185,136,929,178,974,185          (hex 0x3A1497DD0014F7E9)

 Binary view (64 bits):
   00111010000101001001011111011101000000000 | 0010100111101 | 1111101001
   └──────────── time (41) ────────────────┘   └ shard 1341 ┘   └ seq 1001 ┘

4.4 Worked example: decoding an ID

id    = 4185136929178974185
t     = id >> 23            = 498907200000      → + epoch = 1792747200000 ms = 2026-10-23 09:20:00 UTC
shard = (id >> 10) & 0x1FFF = 1341              → lives on logical shard 1341
seq   = id & 0x3FF          = 1001

Any service — the feed, the like service, a debugging tool — can therefore answer "when was this created?" and "which shard holds it?" from the ID alone.

4.5 Why embedding the shard ID enables routing without lookups

Without it, a request like GET /media/4185136929178974185 would need a directory lookup ("which shard owns post X?") — another distributed table with billions of entries, another hop, another thing to cache and keep consistent. With the shard in the ID, routing is pure arithmetic plus a tiny, static map:

• The logical → physical map has at most 8,192 entries — small enough to cache in every app server and update rarely (when shards move).
• Co-location: Instagram described sharding by user, so a post's ID carries the author's shard. Objects that belong together (a user's posts, likes stored with the post) can be placed on the same shard by reusing the same shard ID, enabling single-shard queries.
• Resharding friendliness: because IDs point at logical shards, moving logical shard 1341 from pg-db-07 to a new server changes one map entry; no IDs change.

5. Clocks: skew, NTP and time going backwards

Time-based IDs are only as good as the clocks that produce them. Server clocks are quartz oscillators that drift (tens of parts per million — up to a few seconds per day if uncorrected), so they're continuously disciplined by NTP (Network Time Protocol) or PTP, which typically keeps servers in a data center within about a millisecond of each other (better with modern setups like chrony + PTP).

5.1 Clock skew between machines: harmless-ish

If machine A's clock runs 3 ms ahead of machine B's, an ID created on B slightly after one on A may get a smaller value. Result: IDs are k-sorted ("roughly sorted, within the skew") rather than strictly ordered. For a feed this is invisible. It only matters if you wrongly rely on IDs for strict ordering — e.g. "process events in ID order to get causality". Use a log/sequence (e.g. Kafka offsets within a partition) for that. See Consistency Models.

5.2 The clock going backwards: dangerous

A clock can jump backwards when NTP steps a badly-off clock, after a VM migration or snapshot restore, from manual changes, or around leap seconds. If a generator issued IDs at t = 1000 ms and the clock jumps back to t = 990, it could re-issue the same (time, machine, sequence) triples → duplicate IDs. Defences:

1. Remember the last timestamp used. If now < last_ms, never generate with the smaller time.
2. Small regression (a few ms): wait until the clock passes last_ms again, then continue. Costs a few ms of latency, rarely.
3. Large regression: refuse (raise an error, mark the node unhealthy, alert) so a load balancer routes ID generation elsewhere. Twitter's original Snowflake did exactly this.
4. Alternatively, "borrow from the future": keep using last_ms (logically) and keep incrementing the sequence until real time catches up. Never goes backwards, but drifts from real time while borrowing.
5. Prevent big jumps operationally: configure NTP/chrony to slew (gradually speed up/slow down) instead of step after boot; use leap-second smearing (spreading the extra second over many hours, as Google and AWS time services do); monitor clock offset.

Instagram's in-database scheme has a natural extra safety net: the 10-bit sequence comes from a monotonically increasing PostgreSQL sequence, so after a small backwards jump a duplicate would require the sequence to wrap to the same value within the same repeated millisecond, and the primary-key constraint would reject it anyway.

6. Throughput and lifetime math

Snowflake (per worker): 2^12 = 4,096 IDs/ms  → 4,096,000 IDs/s per worker
   × 1,024 workers (2^10)                     → ~4.2 billion IDs/s theoretical ceiling

Instagram (per logical shard): 2^10 = 1,024 IDs/ms → 1,024,000 IDs/s per shard
   × 8,192 shards (2^13)                      → ~8.4 billion IDs/s theoretical ceiling
   Realistic need (assumption): ~1.2B objects/day ≈ 14K/s avg, ~50K/s peak
   Even a single hot shard at 10K inserts/s uses only ~10 of 1,024 sequence values per ms.

Lifetime: 2^41 ms = 2,199,023,255,552 ms ≈ 69.7 years
   Twitter epoch 2010-11-04 → exhausted ~2080
   41-bit signed caveat (all 64 bits used): top bit flips after 2^40 ms ≈ 34.8 years

The design question is how to split the bits: more machine/shard bits → more generators; more sequence bits → more IDs per generator per ms; more time bits → longer lifetime or finer resolution. Instagram traded Snowflake's 12 sequence bits for 13 shard bits because their bottleneck is per-shard insert rate (a database can't do a million inserts per second anyway), while having many logical shards gives room to grow.

7. A Snowflake-style generator in Python

import threading
import time


class Snowflake:
    """64-bit IDs: 1 unused sign bit | 41 bits ms since EPOCH | 10 bits worker | 12 bits sequence."""
    EPOCH_MS = 1288834974657            # custom epoch (Twitter's: 2010-11-04T01:42:54.657Z)
    WORKER_BITS, SEQ_BITS = 10, 12
    MAX_WORKER = (1 << WORKER_BITS) - 1  # 1023
    MAX_SEQ = (1 << SEQ_BITS) - 1        # 4095
    MAX_TIME = (1 << 41) - 1
    MAX_BACKWARD_MS = 10                 # tolerate tiny clock regressions by waiting

    def __init__(self, worker_id: int):
        if not 0 <= worker_id <= self.MAX_WORKER:
            raise ValueError("worker_id must be in [0, 1023]")
        self.worker_id = worker_id       # must be unique per running generator!
        self.last_ms = -1
        self.seq = 0
        self._lock = threading.Lock()

    def _now(self) -> int:
        return time.time_ns() // 1_000_000 - self.EPOCH_MS

    def next_id(self) -> int:
        with self._lock:
            now = self._now()
            if now < self.last_ms:                       # clock moved backwards
                drift = self.last_ms - now
                if drift > self.MAX_BACKWARD_MS:
                    raise RuntimeError(f"clock moved back {drift} ms; refusing to generate")
                while now < self.last_ms:                # small drift: wait it out
                    time.sleep((self.last_ms - now) / 1000)
                    now = self._now()
            if now == self.last_ms:
                self.seq = (self.seq + 1) & self.MAX_SEQ
                if self.seq == 0:                         # 4,096 IDs used this ms
                    while now <= self.last_ms:            # spin until the next millisecond
                        now = self._now()
            else:
                self.seq = 0                              # new millisecond: restart sequence
            if now > self.MAX_TIME:
                raise RuntimeError("41-bit timestamp exhausted; pick a new epoch")
            self.last_ms = now
            return (now << (self.WORKER_BITS + self.SEQ_BITS)) | (self.worker_id << self.SEQ_BITS) | self.seq

    @classmethod
    def decode(cls, id_: int) -> dict:
        return {
            "unix_ms": (id_ >> (cls.WORKER_BITS + cls.SEQ_BITS)) + cls.EPOCH_MS,
            "worker_id": (id_ >> cls.SEQ_BITS) & cls.MAX_WORKER,
            "sequence": id_ & cls.MAX_SEQ,
        }


gen = Snowflake(worker_id=37)
ids = [gen.next_id() for _ in range(5)]
assert ids == sorted(ids) and len(set(ids)) == 5      # unique and increasing on one worker
print(ids[0], Snowflake.decode(ids[0]))

Implementation notes:

• Worker IDs must be unique among live generators. Assign from deployment config, a Kubernetes StatefulSet ordinal, or lease them from ZooKeeper/etcd (ephemeral nodes released when a process dies). Two processes sharing a worker ID will eventually collide — the most common real-world Snowflake bug.
• The lock makes it thread-safe within one process; across processes, each needs its own worker ID.
• Embed vs service: run the generator as a library inside every service (no network hop — preferred) or as a small HA service that hands out IDs (simpler worker-ID management, but a dependency).
• JSON and JavaScript: JS numbers are doubles and represent integers exactly only up to 2⁵³. A 64-bit ID sent as a JSON number gets silently rounded in browsers. Send IDs as strings (Twitter's API added id_str for exactly this reason).

8. How Instagram uses ID generation

1. When user 31341 creates a post, the service computes the user's logical shard and inserts the row there; the database assigns the ID via next_id().
2. That single ID then flows everywhere: object-storage keys for media renditions (with a hash prefix for load spreading — see Object Storage), the "post created" Kafka event (see Message Queues), the follower timelines in Redis (see News Feed), the search index and the URL.
3. Feed pagination uses the ID as a cursor: "next page = posts with ID < last_seen_id", which is "older than" thanks to time-ordering (see API Design).
4. Any service holding an ID can route reads to the owning shard without a lookup.

9. Trade-offs & common pitfalls

Common pitfalls

• Duplicate worker IDs after autoscaling or copy-pasted config → silent collisions. Lease IDs and fail fast on conflict.
• Using now() inside a transaction (frozen time) or a non-monotonic clock source.
• Sending 64-bit IDs as JSON numbers to JavaScript clients → rounding. Use strings.
• Using IDs as Redis sorted-set scores → precision loss above 2⁵³ (see Caching).
• Relying on ID order for strict causality across machines — it's only k-sorted.
• Hot prefixes when time-ordered IDs are used directly as prefixes of object-storage keys or as the first part of a range-partitioned key — all new writes hit the same partition. Hash first.
• Exposing sequential IDs where enumeration matters (private resources). Time-based IDs are hard to guess exactly but not secret; authorization must not depend on ID secrecy.
• Forgetting the epoch end — pick an epoch near your launch, and note the signed-bit caveat.

10. Real-world technologies

11. Interview corner

12. Check your understanding

Related lessons

• Sharding — logical vs physical shards and why the shard ID in the ID matters
• Database Indexing — B-trees and why key order affects insert performance
• Databases: SQL vs NoSQL — PostgreSQL and Cassandra, where these IDs live
• News Feed — time-sortable IDs as feed cursors
• API Design — cursor-based pagination with IDs
• Object Storage — avoiding hot prefixes with time-ordered IDs
• CAP & Consistency — why clock-based ordering is only approximate