Bird
Raised Fist0

Twitter Snowflake - Timestamp + Machine ID + Sequence Design

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
🏗️
Twitter Snowflake - Timestamp + Machine ID + Sequence Design
Distributed unique ID generation using timestamp, machine ID, and sequence number for high-scale systems
mediumUnique ID GenerationFreq: common
Prerequisites:Distributed Systems BasicsConcurrency ControlClock SynchronizationScalable ID Generation
⚙️
Functional Requirements
  • Generate globally unique 64-bit IDs without coordination between nodes
  • IDs must be roughly time-sortable to support chronological queries
  • Support at least 1 million ID generations per second cluster-wide
  • Include machine ID and sequence number to avoid collisions within the same millisecond
  • Allow horizontal scaling by adding more ID generator nodes
  • Provide IDs with low latency (<1ms) per generation request
📊
Non-Functional Requirements
  • System must support 2 billion daily active users generating IDs concurrently
  • ID generation latency P99 must be under 1 millisecond
  • System availability SLA of 99.99% to avoid ID generation downtime
  • IDs must be collision-free even under clock skew and node restarts
  • System must handle clock backward jumps gracefully without ID duplication
❓
Clarifying Questions to Ask
  • What is the expected peak QPS for ID generation requests?
  • Are IDs required to be strictly monotonically increasing or only roughly time-sortable?
  • What is the maximum tolerated clock skew between nodes?
  • Is the system expected to run across multiple data centers or a single region?
  • What is the maximum number of ID generator nodes planned?
  • Should the system handle node failures and restarts without ID collisions?
Out of Scope
✗ Designing the entire Twitter messaging or storage system
✗ Handling ID usage or downstream data consistency
✗ Long-term archival or analytics on generated IDs
✗ Security or encryption of IDs
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 messages per day on average
  • Average ID size is 8 bytes (64-bit integer)
  • Peak traffic is 2x average load during peak hours
⚡
QPS Calculation
write qps2B users × 40 msgs/user/day ÷ 86400 sec/day ≈ 925,926 writes/sec
peak write qps925,926 × 2 (peak factor) ≈ 1,851,852 writes/sec
read qpsAssuming 10 reads per write, read_qps ≈ 18.5M reads/sec
💾
Storage Estimate
daily storage bytes2B × 40 × 8 bytes = 640 GB/day
retention days7
total storage bytes640 GB × 7 days = 4.48 TB
with replication 3x4.48 TB × 3 = 13.44 TB
🖥️
Server Estimate
id generator nodesAssuming each node handles 50K writes/sec, need 1,851,852 ÷ 50,000 ≈ 38 nodes
storage nodesAssuming Cassandra nodes with 500 GB usable storage each, need 13.44 TB ÷ 0.5 TB ≈ 27 nodes
🏗️
Architecture Diagram
Architecture Diagram
          +----------------+
          | Client Request |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Snowflake ID   |
          | Generator Node |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Kafka Cluster  |
          +-------+--------+
                  |
                  v
          +-------+--------+
          | Cassandra DB   |
          +----------------+
🧩
Components
Snowflake ID Generator Node
Generate unique 64-bit IDs combining timestamp, machine ID, and sequence number
Why thisCustom service implementing Twitter Snowflake algorithm ensures low-latency, collision-free ID generation without coordination
Why notUUID v4 is random and not time-sortable; Zookeeper-based sequence coordination adds latency and single point of failure
Kafka Cluster
Buffer and asynchronously stream generated IDs to downstream storage and consumers
Why thisKafka provides durable, scalable, ordered log with high throughput for decoupling ID generation from storage
Why notRabbitMQ lacks Kafka's throughput and partitioning scalability at 2M+ writes/sec
Cassandra DB
Store generated IDs and associated metadata for querying and analytics
Why thisCassandra's wide-column model and tunable consistency handle high write throughput and horizontal scaling
Why notPostgreSQL requires manual sharding and does not scale linearly at 2M writes/sec
Monitoring & Alerting System
Track ID generation latency, error rates, clock skew, and node health
Why thisPrometheus + Grafana provide real-time metrics and alerting for SLA adherence
Why notBasic logs lack real-time alerting and aggregation needed at scale
Configuration Service
Assign and manage unique machine IDs to each Snowflake node
Why thisZookeeper provides consistent, distributed coordination to avoid machine ID collisions
Why notStatic config risks ID collisions on node restarts or scaling
🔄
Data Flow
1
Client Request → Snowflake ID Generator Node
Request new unique ID
Client calls ID generator with minimal payload
2
Snowflake ID Generator Node → Snowflake ID Generator Node
Generate ID using current timestamp, machine ID, sequence number
Sequence resets each millisecond; machine ID ensures uniqueness across nodes
3
Snowflake ID Generator Node → Kafka Cluster
Publish generated ID to Kafka topic
Decouples ID generation from downstream processing
4
Kafka Cluster → Cassandra DB
Consume ID messages and persist to Cassandra
Enables querying and analytics on generated IDs
5
Monitoring System → Snowflake ID Generator Node
Collect metrics on latency, errors, clock skew
Ensures SLA and detects anomalies

Practice

(1/5)
1. A distributed cache system must evenly distribute keys across nodes and gracefully handle node failures without massive key remapping. Which component or technique best addresses this requirement?
easy
A. Implementing consistent hashing with virtual nodes
B. Storing all keys in a single master node for centralized control
C. Using a simple modulo hash function on node count to assign keys
D. Using random key assignment to nodes without hashing

Solution

  1. Step 1: Understand key distribution needs

    Simple modulo hashing (Using a simple modulo hash function on node count to assign keys) causes massive remapping when nodes change, failing graceful scaling.
  2. Step 2: Evaluate consistent hashing benefits

    Consistent hashing with virtual nodes (Implementing consistent hashing with virtual nodes) minimizes remapping and balances load even with node failures.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Consistent hashing with virtual nodes -> minimal key remapping on node changes [check]
Hint: Consistent hashing + virtual nodes minimize remap on node changes [OK]
Common Mistakes:
2. In a gRPC streaming call, at step 4 the server-side stream handler checks the client connection status before sending a message. What happens if the client has disconnected at this step?
easy
A. The server immediately cancels the stream and releases resources
B. The server buffers the message indefinitely until the client reconnects
C. The server retries sending the message up to 3 times before dropping it
D. The server switches to unary RPC mode to deliver the message

Solution

  1. Step 1: Understand server stream handler behavior

    When client disconnects, server detects cancellation via context and stops streaming.
  2. Step 2: Trace server reaction at step 4

    Server cancels the stream and frees resources immediately; it does not buffer or retry indefinitely.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Client disconnect -> server cancels stream and frees resources [check]
Hint: Disconnected client -> server cancels stream immediately [check]
Common Mistakes:
3. In a post-mortem process, at Step 4 the Root Cause Analysis (RCA) team reviews the timeline and identifies contributing factors. What is the state of the RCA team's findings at this step?
easy
A. They have identified multiple contributing factors but have not prioritized them
B. They have finalized the action items and assigned owners
C. They have blamed specific individuals for the failure
D. They have ignored system logs and rely only on anecdotal evidence

Solution

  1. Step 1: Trace RCA team's role at Step 4

    At this stage, the team analyzes the timeline to identify contributing factors but has not yet prioritized or assigned action items.
  2. Step 2: Eliminate incorrect states

    They have finalized the action items and assigned owners is premature; action items come after prioritization. They have blamed specific individuals for the failure violates blameless culture. They have ignored system logs and rely only on anecdotal evidence ignores critical data sources.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    RCA identifies factors before prioritizing or assigning actions [check]
Hint: RCA finds causes first, acts later [check]
Common Mistakes:
4. If the sliding window counter's timestamp cleanup process fails, what is the most likely failure observed in rate limiting?
medium
A. Requests are allowed without limit because counters reset incorrectly
B. Fixed window counters reset too frequently causing bursty traffic spikes
C. Rate limiter blocks requests indefinitely due to stale timestamps inflating counts
D. Token bucket refills tokens too slowly causing underutilization

Solution

  1. Step 1: Understand sliding window cleanup role

    Cleanup removes timestamps outside the window; failure causes stale timestamps to accumulate.
  2. Step 2: Accumulated stale timestamps inflate request counts, causing the rate limiter to block legitimate requests indefinitely

    This leads to false positives in rate limiting, denying service unnecessarily.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Failed cleanup -> stale timestamps inflate counts -> requests blocked indefinitely [check]
Hint: No cleanup means stale timestamps block requests falsely [check]
Common Mistakes:
5. For a system requiring cost optimization with infrequent data access but occasional retrieval within hours, which storage architecture is preferable?
medium
A. Implement warm storage with HDDs and cold storage with object storage, migrating data based on access patterns
B. Use only hot storage with SSDs for all data to ensure fastest access
C. Archive all data immediately to tape storage to minimize cost
D. Store all data in cold storage with no tiering to simplify design

Solution

  1. Step 1: Analyze access and cost requirements

    Data is infrequently accessed but needs retrieval within hours, so cold storage alone is too slow.
  2. Step 2: Evaluate tiering benefits

    Warm storage offers moderate cost and latency; cold storage reduces cost further. Tiering balances cost and retrieval time.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Warm + cold tiering balances cost and retrieval latency [check]
Hint: Warm + cold tiering balances cost and latency [check]
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