Bird
Raised Fist0

Twitter Snowflake - Timestamp + Machine ID + Sequence Design

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design Twitter Snowflake: Distributed Unique ID Generation
45 min · senior
senior

You are building a distributed unique ID generation system for a 50M DAU social media startup. The system must generate 64-bit unique IDs composed of a timestamp, machine ID, and sequence number. IDs must be sortable by creation time, generated at high throughput (millions per second), and avoid collisions without centralized coordination. The system must support multiple data centers and handle clock skew gracefully.

Constraints
  • IDs must be 64-bit integers combining timestamp, machine ID, and sequence number
  • System must support 50M DAU generating up to 5M IDs/sec globally
  • P99 latency for ID generation must be under 1ms
  • Must handle clock skew and machine restarts without ID collisions
  • No single point of failure or centralized coordination allowed
  • Machine ID assignment must be secure and prevent collisions
📋
Guided Steps
1/5
Step 1
Define ID Structure and Bit Allocation
How would you design the 64-bit ID structure to encode timestamp, machine ID, and sequence number? What bit lengths do you assign to each component?
💡 Hint
Consider the maximum timestamp range, number of machines, and sequence numbers per millisecond needed to meet scale.
Key Decision
Use a 64-bit integer with 41 bits for timestamp (millisecond precision), 10 bits for machine ID, and 12 bits for sequence number, following Twitter Snowflake's proven bit allocation to support 69 years, 1024 machines, and 4096 IDs/ms per machine.
Interviewer Expectation
Mid: Names bit allocation roughly. Senior: Explains exact bit counts, timestamp epoch choice, and how it supports scale and longevity.
⚠️Common Wrong Answer
Assign equal bits to all fields without scale reasoning - leads to insufficient ID throughput or timestamp overflow.
Step 2
Machine ID Assignment and Collision Avoidance
How do you assign and manage machine IDs to ensure uniqueness across data centers and prevent collisions?
💡 Hint
Think about static vs dynamic assignment and how to avoid duplicate machine IDs in distributed environments.
Key Decision
Use a centralized coordination service like Apache ZooKeeper or etcd to assign and lease unique machine IDs per instance with heartbeat and expiration to prevent collisions and stale assignments.
Interviewer Expectation
Mid: Mentions static config or environment variables. Senior: Explains dynamic leasing with ZooKeeper/etcd, heartbeat mechanism, and failure recovery.
⚠️Common Wrong Answer
Hardcode machine IDs without coordination - causes collisions when machines restart or scale dynamically.
Step 3
Sequence Number Generation and Reset Logic
How do you generate and manage the sequence number to avoid collisions within the same millisecond on a single machine?
💡 Hint
Consider how to handle sequence overflow and clock rollback scenarios.
Key Decision
Use a per-machine in-memory counter reset every millisecond; if sequence overflows (exceeds 4095), block or wait for next millisecond. Detect clock rollback and pause ID generation until clock catches up.
Interviewer Expectation
Mid: Mentions incrementing sequence per request. Senior: Details overflow handling, blocking strategy, and clock rollback detection with wait or error.
⚠️Common Wrong Answer
Reset sequence without clock checks - leads to duplicate IDs during clock skew or fast restarts.
Step 4
Handling Clock Skew and Machine Restarts
How does your system handle clock skew (time going backward) and machine restarts to prevent ID collisions?
💡 Hint
Think about monotonic clocks, waiting strategies, and persistent state.
Key Decision
Implement clock rollback detection: if current timestamp < last timestamp, pause ID generation until clock catches up. Persist last timestamp and sequence in local storage to recover after restart and avoid duplicates.
Interviewer Expectation
Mid: Mentions clock sync or NTP. Senior: Explains rollback detection, wait strategy, and persistence to prevent duplicates after restarts.
⚠️Common Wrong Answer
Ignore clock skew - causes duplicate or out-of-order IDs breaking uniqueness and ordering guarantees.
Step 5
API Design for ID Generation Service
Design 3 core API endpoints for clients to interact with the Snowflake ID generation service.
💡 Hint
Consider endpoints for requesting IDs, decoding IDs, and managing machine ID registration or health.
Key Decision
Expose: (1) POST /generateID to return a new unique ID; (2) GET /decodeID?id= to parse timestamp, machine ID, sequence; (3) POST /registerMachine to acquire machine ID lease with heartbeat.
Interviewer Expectation
Mid: Names generate ID endpoint. Senior: Details decode and registration endpoints with heartbeat and error handling.
⚠️Common Wrong Answer
Only provide generate endpoint without machine registration or decode - limits operational visibility and debugging.
🔌
API Design Challenge
Sketch 3 core endpoints for the Snowflake ID generation service API.
Hints
  • How does a client request a new unique ID?
  • How does the client verify or decode the generated ID?
  • How does the system handle machine ID registration or heartbeat?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Correct bit allocation with timestamp, machine ID, and sequence number supporting scale
  • Dynamic machine ID assignment with coordination service to prevent collisions
  • Sequence number management with overflow and clock rollback handling
  • Clock skew detection and mitigation to avoid duplicate IDs
  • API design covering ID generation, decoding, and machine registration
Good to Have - 30%
  • Persistence of last timestamp and sequence for restart recovery
  • Use of monotonic clocks and NTP for clock synchronization
  • Blocking or backoff strategy on sequence overflow
  • Heartbeat mechanism for machine ID lease renewal
Bonus - 10%
  • Explain trade-offs of bit allocation choices and epoch start time
  • Discuss failure modes and recovery scenarios in detail
  • Propose monitoring and alerting for machine ID collisions or clock skew
Anti-patterns to Avoid
Hardcoding machine IDs without coordination - causes collisions and scaling issues when machines restart or scale dynamically
Ignoring clock skew - leads to duplicate or out-of-order IDs breaking uniqueness and ordering guarantees
Using a centralized ID generator - creates a single point of failure and bottleneck, limiting scalability
Not handling sequence overflow - causes ID collisions or dropped requests impacting data integrity
Omitting machine ID lease and heartbeat - stale IDs cause collisions after restarts or failover
Designing APIs without decode or registration endpoints - limits operational visibility and debugging capabilities
✅
Model Answer
▼ Reveal

The Twitter Snowflake ID generation system produces 64-bit unique, time-sortable IDs by combining a 41-bit timestamp, 10-bit machine ID, and 12-bit sequence number. It supports high throughput and distributed environments without centralized bottlenecks.

Key Decisions
  • Bit allocation: 41 bits timestamp, 10 bits machine ID, 12 bits sequence number to support 69 years, 1024 machines, and 4096 IDs/ms per machine
  • Use Apache ZooKeeper or etcd for machine ID assignment with lease and heartbeat to prevent collisions and stale IDs
  • Sequence number resets every millisecond; blocks or waits if overflow occurs to maintain uniqueness
  • Detect clock rollback by comparing current timestamp with last timestamp; pause generation until clock catches up
  • Persist last timestamp and sequence number in local durable storage (e.g., embedded DB or local disk) for recovery after restarts
  • API design includes POST /generateID for new IDs, GET /decodeID to parse IDs, and POST /registerMachine for machine ID leasing with heartbeat
  • 64-bit ID with 41-bit timestamp (ms precision), 10-bit machine ID, 12-bit sequence number to support 5M IDs/sec
  • Apache ZooKeeper or etcd for dynamic machine ID assignment with lease and heartbeat to avoid collisions
  • In-memory per-machine sequence counter reset every millisecond with blocking on overflow to maintain uniqueness
  • Clock rollback detection with wait strategy and persistent last timestamp/sequence to prevent duplicates after restarts
  • REST API with /generateID, /decodeID, and /registerMachine endpoints for client interaction and operational control
  • Use monotonic system clock and NTP synchronization to minimize clock skew impact
  • Avoid centralized ID generation bottlenecks by generating IDs locally on each machine
  • Persist machine ID lease info and last timestamp to durable storage (e.g., local disk or embedded DB) for recovery

Practice

(1/5)
1. In the request flow for posting a new answer, at step 5 the Feed Generator consumes messages from Kafka. What happens if the Feed Generator detects a malformed message at this step?
easy
A. The Feed Generator sends the malformed message to a dead-letter queue for later inspection
B. The Feed Generator pauses consumption and retries the malformed message until fixed
C. The Feed Generator discards the message and continues processing the next message
D. The Feed Generator crashes, causing the entire feed update pipeline to stop

Solution

  1. Step 1: Understand Feed Generator error handling

    Discarding (A) loses data silently; pausing and retrying (B) blocks the pipeline indefinitely; crashing (D) causes system downtime.

  2. Step 2: Dead-letter queue usage

    Sending malformed messages to a dead-letter queue (C) isolates bad data for manual or automated inspection without blocking the main pipeline.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Dead-letter queue isolates bad messages without blocking processing [check]
Hint: Dead-letter queues isolate bad messages, keep pipeline flowing [check]
Common Mistakes:
2. For a stock exchange system requiring low-latency order matching and high availability, which architecture is best suited to handle failover without losing in-flight orders?
medium
A. Use a distributed matching engine with partitioned order books per stock symbol and asynchronous replication
B. Use a single centralized matching engine with synchronous replication to a hot standby
C. Use multiple independent matching engines with eventual consistency and conflict resolution
D. Use a cloud-managed database with built-in failover and no dedicated matching engine

Solution

  1. Step 1: Analyze architecture requirements

    Low latency and high availability require partitioning to avoid bottlenecks and asynchronous replication to avoid blocking on failover.

  2. Step 2: Evaluate options

    Use a single centralized matching engine with synchronous replication to a hot standby blocks on synchronous replication causing latency; Use multiple independent matching engines with eventual consistency and conflict resolution risks conflicts and inconsistent order books; Use a cloud-managed database with built-in failover and no dedicated matching engine lacks dedicated matching engine causing latency and complexity.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Partitioned matching engine + async replication -> low latency + availability [check]
Hint: Partition and async replication for low latency failover [check]
Common Mistakes:
3. For intent classification in the bot, which architecture best balances latency and model update frequency given a high volume of diverse user queries?
medium
A. Use a single large LLM instance serving all queries synchronously
B. Run multiple LLM replicas behind a load balancer with synchronous inference
C. Deploy a lightweight intent classifier for fast routing, with LLM fallback for complex queries asynchronously
D. Use batch processing of queries offline to update intents periodically

Solution

  1. Step 1: Analyze latency and update frequency constraints

    High volume requires low latency for common intents and flexibility for complex queries.

  2. Step 2: Evaluate architectures

    A single large LLM (A) has high latency and update overhead. Multiple replicas (C) improve throughput but still synchronous latency is high. Batch offline (D) delays updates and user experience. Lightweight classifier with async LLM fallback (B) balances fast routing and complex understanding.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Lightweight classifier + async LLM fallback balances latency and accuracy [check]
Hint: Fast lightweight routing, async LLM fallback for complexity [check]
Common Mistakes:
4. At 10x scale, which component of a Bloom filter system is most likely to fail first and why?
hard
A. The client application, due to increased latency in membership queries
B. The bit array storage, because increased insertions cause saturation and higher false positive rates
C. The hash functions, because their computation time grows linearly with scale
D. The network bandwidth, due to Bloom filter synchronization overhead

Solution

  1. Step 1: Identify scaling impact on Bloom filter components

    At very high scale, hash function computation cost increases linearly with insertions, becoming a CPU bottleneck.

  2. Step 2: Evaluate other components

    Bit array saturation affects false positives but does not cause immediate failure; network and client latency scale better.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Hash function CPU cost grows linearly, causing first failure at scale [check]
Hint: Hash function CPU cost grows linearly at scale [check]
Common Mistakes:
5. At 10x scale, which component in a Redis Cluster using consistent hashing is most likely to become the first bottleneck, and why?
hard
A. The client-side slot cache, because it grows linearly with cluster size and increases latency
B. The network bandwidth between nodes, due to increased replication traffic
C. The cluster management node, because it handles all slot reassignments centrally
D. The individual Redis nodes, because maintaining many virtual nodes increases CPU overhead

Solution

  1. Step 1: Identify cluster management role

    Cluster management node coordinates slot assignments and node membership changes.

  2. Step 2: Analyze scaling impact

    At 10x scale, centralized management node becomes bottleneck due to coordination overhead (The cluster management node, because it handles all slot reassignments centrally).

  3. Step 3: Eliminate other options

    Network bandwidth (A) and Redis nodes (D) scale better; client slot cache (C) is local and does not cause cluster-wide bottleneck.

  4. Final Answer:

    Option C -> Option C

  5. Quick Check:

    Centralized cluster manager -> coordination bottleneck at large scale [check]
Hint: Central cluster manager bottlenecks slot coordination at scale [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard