Bird
Raised Fist0

ULID and KSUID - Sortable Distributed IDs for Modern Systems

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
ULID and KSUID - Sortable Distributed IDs for Modern Systems
Design a scalable, sortable, distributed unique ID generation system using ULID and KSUID
mediumUnique ID GenerationFreq: medium
Prerequisites:Distributed Systems BasicsUnique ID Generation ConceptsTime-based OrderingHigh Throughput Systems
⚙️
Functional Requirements
  • Generate globally unique IDs that are sortable by generation time
  • Support distributed generation without coordination or central bottlenecks
  • Ensure IDs are collision-resistant across multiple data centers
  • Provide IDs with fixed length and encoded in URL-safe format
  • Allow clients to generate IDs locally with minimal latency
  • Support high throughput generation (millions of IDs per second)
📊
Non-Functional Requirements
  • System must support up to 2 billion daily active users generating IDs
  • End-to-end ID generation latency must be under 5ms P99
  • ID generation service availability must be 99.99%
  • IDs must be sortable by generation time with millisecond precision
  • System must handle peak write QPS of at least 1 million IDs/sec
❓
Clarifying Questions to Ask
  • What is the expected ID length and encoding format (e.g., base32, base62)?
  • Is strict global monotonicity required or approximate time ordering sufficient?
  • Are IDs generated only by backend services or also by clients/devices?
  • What is the maximum tolerated clock skew between distributed nodes?
  • Should the system support multiple ID formats (ULID and KSUID) simultaneously?
  • Is there a requirement for ID collision detection or prevention mechanisms?
Out of Scope
✗ ID usage for database sharding or indexing strategies
✗ Long-term archival or analytics on generated IDs
✗ Security features like encryption or access control on IDs
✗ Backward compatibility with legacy ID formats
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 IDs per day on average
  • Average ID size is 16 bytes (128 bits) encoded as 26-character string
  • Retention period for ID storage is 30 days
⚡
QPS Calculation
write qps2,000,000,000 users × 40 IDs/day ÷ 86,400 seconds/day ≈ 925,926 IDs/sec
peak write qpsAssuming 3× peak factor: 925,926 × 3 ≈ 2,777,778 IDs/sec
read qpsAssuming 5× read amplification: 925,926 × 5 ≈ 4,629,630 reads/sec
💾
Storage Estimate
daily storage bytes2,000,000,000 × 40 × 16 bytes = 1,280,000,000,000 bytes ≈ 1.28 TB/day
retention storage bytes1.28 TB/day × 30 days = 38.4 TB
with replication38.4 TB × 3 replicas = 115.2 TB total storage
🖥️
Server Estimate
id generation serviceAssuming each server handles 100K IDs/sec, need ~28 servers for peak write QPS
storage clusterAssuming each storage node handles 5 TB with replication, need ~24 nodes for 115.2 TB
🏗️
Architecture Diagram
Architecture Diagram
          +----------------------+
          |  Client / Backend     |
          |  ID Generation Lib   |
          +----------+-----------+
                     |
                     v
          +----------------------+
          |  ID Generation Svc   |
          |  (ULID/KSUID Logic)  |
          +----------+-----------+
                     |
                     v
          +----------------------+
          |  Kafka (Message Queue)|
          +----------+-----------+
                     |
                     v
          +----------------------+
          |  Storage Cluster      |
          |  (Cassandra / Scylla) |
          +----------------------+
🧩
Components
ID Generation Library
Client-side library to generate ULID/KSUID IDs locally
Why thisEnables low-latency ID generation without network calls, using ULID/KSUID algorithms with embedded timestamp and randomness
Why notCentralized ID generation services add network latency and become bottlenecks at scale
ID Generation Service
Backend service to generate IDs when client-side generation is not possible or for audit logging
Why thisImplements ULID/KSUID generation with monotonic counters to avoid collisions and ensure time-sortability
Why notSnowflake requires centralized coordination and has limited timestamp range; UUIDv4 is not sortable
Kafka (Apache Kafka)
Distributed message queue to buffer generated IDs for asynchronous processing and storage
Why thisKafka supports high throughput (millions of messages/sec), partitioning for scalability, and durability with replication
Why notRabbitMQ lacks horizontal scalability at this scale; Redis Streams has limited persistence guarantees
Storage Cluster (Cassandra / ScyllaDB)
Distributed NoSQL database to store generated IDs and metadata with high write throughput and availability
Why thisCassandra/Scylla provide linear scalability, tunable consistency, and time-series friendly data model for efficient range queries on IDs
Why notPostgreSQL requires complex manual sharding at 2.7M writes/sec; B-tree writes don't scale linearly
Monitoring & Alerting
Track system health, latency, error rates, and capacity to maintain 99.99% availability
Why thisPrometheus + Grafana provide real-time metrics and alerting with minimal overhead
Why notCustom monitoring lacks community support and scalability for large distributed systems
🔄
Data Flow
1
Client / Backend → ID Generation Library
Generate ULID/KSUID locally embedding timestamp and randomness
Minimizes latency and avoids network calls for ID generation
2
ID Generation Library → ID Generation Service
Fallback to service if local generation not possible or for audit
Ensures availability and centralized logging
3
ID Generation Service → Kafka
Publish generated IDs asynchronously to Kafka topic
Decouples ID generation from storage for scalability
4
Kafka → Storage Cluster
Consume IDs from Kafka and write to Cassandra/Scylla
Ensures durable storage with high write throughput
5
Storage Cluster → Clients / Analytics
Serve stored IDs for queries or analytics
Supports range queries by timestamp due to sortable ID design

Practice

(1/5)
1. In a chat system using asynchronous messaging, at step 4 the Delivery Worker reads a message from the queue and attempts to deliver it to the recipient's server. What happens if the recipient's server is temporarily unreachable at this step?
easy
A. The Delivery Worker immediately discards the message and logs an error
B. The Delivery Worker blocks until the recipient server responds or times out
C. The Delivery Worker retries delivery later without blocking the sender
D. The Delivery Worker sends a failure notification back to the sender synchronously

Solution

  1. Step 1: Understand Delivery Worker's role in asynchronous delivery

    It reads messages from the queue and attempts delivery without blocking the sender.

  2. Step 2: Analyze failure handling at delivery

    If recipient is unreachable, the worker retries later, ensuring eventual delivery without blocking upstream.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Delivery Worker retries asynchronously, preserving sender non-blocking [check]
Hint: Delivery Worker retries asynchronously, never blocks sender [check]
Common Mistakes:
2. If the health check module fails to run, what is the exact failure observed in the load balancer's routing behavior?
medium
A. Load balancer reroutes traffic randomly ignoring server health
B. Load balancer blocks all traffic until health checks resume
C. Load balancer routes only to a cached subset of servers marked healthy previously
D. Load balancer continues routing to all servers, including unhealthy ones, causing client errors

Solution

  1. Step 1: Understand health check module role

    Health checks detect unhealthy servers; without them, no updates occur to remove bad servers.

  2. Step 2: Trace routing behavior without health checks

    Load balancer routes to all servers indiscriminately, including unhealthy ones, causing client errors.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    No health checks -> no removal of unhealthy servers -> client errors [check]
Hint: No health checks means no unhealthy server removal [check]
Common Mistakes:
3. If the Key Management Service (KMS) becomes unavailable, what exactly breaks in the system's encryption-at-rest workflow?
medium
A. New encryption keys cannot be generated, but existing data remains accessible and decryptable
B. Data encryption stops, causing all writes to fail immediately
C. Decryption of existing data fails, causing read operations to block or error out
D. The system falls back to unencrypted storage, risking data exposure

Solution

  1. Step 1: Understand KMS role in key lifecycle

    KMS generates and manages encryption keys; if unavailable, new keys can't be created but existing keys cached locally allow decryption.

  2. Step 2: Eliminate incorrect failure modes

    Encryption doesn't stop immediately; decryption continues with cached keys; system does not fallback to unencrypted storage automatically.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    KMS outage blocks new key generation, existing keys still usable [check]
Hint: KMS down -> no new keys, existing keys still decrypt [check]
Common Mistakes:
4. If Zookeeper's session timeout mechanism fails to detect a crashed leader node promptly, what is the most likely failure observed in the leader election process?
medium
A. Multiple nodes simultaneously assume leadership causing split-brain
B. Leader election proceeds normally due to backup leader election mechanism
C. Followers wait indefinitely for leader node removal, blocking leader election
D. Clients receive stale configuration but leader election continues

Solution

  1. Step 1: Understand session timeout role

    Session timeout detects leader failure by ephemeral node removal.

  2. Step 2: Failure of timeout detection

    If timeout fails, ephemeral node remains, so followers do not start election; no split-brain occurs.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Backup election mechanisms prevent split-brain despite timeout failure [check]
Hint: Session timeout failure -> ephemeral node stays -> no immediate election [check]
Common Mistakes:
5. At 10x scale, which component in a NoSQL cluster handling user sessions fails first and why?
hard
A. The load balancer because it cannot distribute requests evenly at scale
B. The session management layer because it maintains stateful connections that can't be sharded easily
C. The storage nodes because disk I/O saturates under high write volume
D. The network switches because they cannot handle increased traffic volume

Solution

  1. Step 1: Identify storage node bottlenecks at high write volume

    Disk I/O can saturate under 10x writes, limiting storage node throughput.

  2. Step 2: Compare other components' scalability

    Session management can shard state; load balancers and network switches scale with hardware upgrades.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Disk I/O saturation -> storage node bottleneck at 10x scale [check]
Hint: Disk I/O saturates first at 10x writes [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