Bird
Raised Fist0

Ticket Server Pattern for Centralized ID Generation

HLDmediumInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Ticket Server Pattern for Centralized ID Generation
45 min · senior
senior

You are designing a centralized ID generation service for a startup with 50 million daily active users (DAU). The system must generate globally unique, monotonically increasing IDs for various entities (e.g., orders, users, sessions) across multiple distributed services. The service must handle high throughput with low latency and guarantee no ID collisions. IDs must be cryptographically secure to prevent guessability. The system should support offline ID generation fallback and maintain P99 latency under 200ms.

Constraints
  • Must support 50M DAU with peak throughput of 1M ID requests per second
  • IDs must be cryptographically secure and non-guessable
  • P99 latency for ID generation must be under 200ms
  • Offline ID generation fallback for services during network partitions
  • Strong monotonicity guarantees per entity type
  • Centralized coordination to avoid collisions but minimize bottlenecks
📋
Guided Steps
1/5
Step 1
Choosing the ID Generation Strategy
What approach will you use to generate globally unique, monotonically increasing IDs at scale?
💡 Hint
Consider a ticket server that allocates ID ranges or tickets to clients to reduce coordination overhead.
Key Decision
Use a centralized Ticket Server implemented with Apache ZooKeeper to allocate ID ranges (tickets) atomically, ensuring monotonicity and uniqueness without per-ID coordination.
Interviewer Expectation
Mid: Names ZooKeeper for coordination. Senior: Explains how ZooKeeper's atomic sequential nodes guarantee monotonic ticket allocation and why per-ID DB writes would bottleneck.
⚠️Common Wrong Answer
Using a relational database with auto-increment IDs causes a bottleneck and high latency at 1M requests/sec.
Step 2
Ensuring Cryptographically Secure and Non-Guessable IDs
How will you design IDs to be cryptographically secure and prevent guessability while maintaining monotonicity?
💡 Hint
Consider combining a monotonic ticket with a cryptographic component or encryption layer.
Key Decision
Generate IDs by encrypting the monotonic ticket number using AES-GCM with a server-held key, producing non-guessable, unique IDs while preserving order via ticket sequence.
Interviewer Expectation
Mid: Mentions encryption for security. Senior: Explains AES-GCM for authenticated encryption and how encrypting the ticket preserves uniqueness and order without exposing raw counters.
⚠️Common Wrong Answer
Using UUIDv4 or random IDs breaks monotonicity and ordering guarantees.
Step 3
Handling Offline ID Generation and Synchronization
How will clients generate IDs offline and later synchronize to avoid collisions and maintain monotonicity?
💡 Hint
Think about pre-allocating ticket ranges and reconciliation protocols upon reconnection.
Key Decision
Clients prefetch ticket ranges from the Ticket Server and generate IDs offline within those ranges; upon reconnection, clients report used ranges to a reconciliation service backed by Cassandra to prevent reuse.
Interviewer Expectation
Mid: Describes prefetching ranges. Senior: Details reconciliation using Cassandra with entity_type partition keys to track used ranges and prevent collisions after offline periods.
⚠️Common Wrong Answer
Allowing clients to generate random IDs offline leads to collisions and breaks global uniqueness.
Step 4
API Design for ID Request, Acknowledgment, and Sync
Design the 3 core API endpoints for clients to request IDs, acknowledge usage, and sync offline-generated IDs.
💡 Hint
Consider batch ID requests, acknowledgment to free unused tickets, and sync endpoints for reconciliation.
Key Decision
Expose REST endpoints: (1) /allocateTickets to request ID ranges, (2) /acknowledgeTickets to confirm usage and release unused IDs, (3) /syncOfflineIDs to reconcile offline-generated IDs with the central store.
Interviewer Expectation
Mid: Lists endpoints with basic functionality. Senior: Explains idempotency, batching, and how acknowledgment reduces ticket wastage and sync prevents collisions.
⚠️Common Wrong Answer
Using a single endpoint without acknowledgment leads to ticket exhaustion and ID reuse.
Step 5
Scaling and Latency Optimization
How will you ensure the Ticket Server scales to 1M requests/sec and maintains P99 latency under 200ms?
💡 Hint
Consider sharding ticket allocation and caching strategies.
Key Decision
Shard ticket allocation by entity type using multiple ZooKeeper ensembles and cache allocated ticket ranges in Redis with TTL to reduce ZooKeeper load and latency.
Interviewer Expectation
Mid: Mentions sharding. Senior: Explains ZooKeeper ensemble scaling limits, Redis caching to reduce coordination, and fallback mechanisms if cache misses occur.
⚠️Common Wrong Answer
Single ZooKeeper cluster for all entities causes coordination bottlenecks and latency spikes.
🔌
API Design Challenge
Sketch 3 core API endpoints for the Ticket Server: how clients request IDs, how they confirm usage, and how they handle offline fallback synchronization.
Hints
  • How does a client request a batch or single ID from the server?
  • How does the client acknowledge or confirm ID usage to prevent reuse?
  • How does the client sync or reconcile IDs generated offline once reconnected?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of ZooKeeper for atomic ticket allocation to guarantee monotonicity and uniqueness
  • Encryption of ticket numbers with AES-GCM to ensure cryptographic security and non-guessability
  • Offline ID generation via pre-allocated ticket ranges with reconciliation to avoid collisions
  • API design covering allocation, acknowledgment, and synchronization endpoints
Good to Have - 30%
  • Sharding Ticket Server by entity type to handle scale
  • Caching allocated ticket ranges in Redis to reduce coordination latency
  • Use of Cassandra for tracking used ticket ranges during offline sync
Bonus - 10%
  • Detailed explanation of failure modes and recovery during network partitions
  • Discussion of idempotency and batching in API design to optimize throughput
Anti-patterns to Avoid
Using a relational database with auto-increment IDs causes a bottleneck and high latency at scale, leading to system slowdowns and request queuing.
Generating random UUIDs breaks monotonicity and ordering guarantees, causing issues in systems that rely on ordered IDs for consistency.
Allowing clients to generate IDs offline without pre-allocated ranges leads to collisions and breaks global uniqueness, resulting in data corruption.
Single ZooKeeper cluster for all entities causes coordination bottlenecks and latency spikes, reducing system throughput and increasing response times.
Omitting acknowledgment endpoint causes ticket exhaustion and ID reuse, leading to ID collisions and inconsistent state.
Ignoring encryption leads to guessable and insecure IDs, exposing the system to security vulnerabilities and potential attacks.
✅
Model Answer
▼ Reveal

The system uses Apache ZooKeeper to allocate atomic, monotonic ticket ranges to clients, ensuring global uniqueness and ordering. IDs are generated by encrypting these monotonic ticket numbers using AES-GCM with a server-held key, producing cryptographically secure and non-guessable IDs. Clients prefetch ticket ranges to enable offline ID generation and later synchronize used ranges with a reconciliation service backed by Cassandra to prevent collisions. The system exposes REST API endpoints for ticket allocation, acknowledgment, and offline sync, supporting batching and idempotency to optimize throughput. To scale to 1M requests/sec and maintain P99 latency under 200ms, ticket allocation is sharded by entity type across multiple ZooKeeper ensembles, with Redis caching to reduce coordination overhead and latency.

Key Decisions
  • Use Apache ZooKeeper's atomic sequential nodes to allocate monotonic ticket ranges, avoiding per-ID coordination bottlenecks.
  • Encrypt monotonic ticket numbers with AES-GCM to produce cryptographically secure, non-guessable IDs while preserving order.
  • Clients prefetch ticket ranges to generate IDs offline and report used ranges upon reconnection to a Cassandra-backed reconciliation service.
  • Design REST APIs with endpoints for allocation, acknowledgment, and synchronization, supporting batching and idempotency to optimize throughput and prevent ticket wastage.
  • Shard Ticket Server by entity type across multiple ZooKeeper ensembles and cache allocated ranges in Redis to scale to 1M requests/sec and maintain low latency.
  • Apache ZooKeeper for atomic, monotonic ticket range allocation to clients
  • AES-GCM encryption of ticket numbers to produce cryptographically secure, non-guessable IDs
  • Clients prefetch ticket ranges to enable offline ID generation with reconciliation
  • Cassandra with entity_type partition key to track used ticket ranges and prevent collisions during sync
  • Redis caching of allocated ticket ranges to reduce ZooKeeper load and improve latency
  • REST API endpoints: /allocateTickets, /acknowledgeTickets, /syncOfflineIDs with idempotency and batching
  • Sharding Ticket Server by entity type to scale to 1M requests/sec
  • Reconciliation service to handle offline-generated IDs and prevent reuse

Practice

(1/5)
1. A distributed key-value store must remain operational during network partitions but can tolerate stale reads temporarily. Which system design choice best supports this requirement?
easy
A. Use a CP system that blocks writes during partitions to maintain consistency
B. Use a CA system that rejects requests during partitions to maintain availability and consistency
C. Use a synchronous replication system that waits for all replicas before responding
D. Use an AP system that serves reads and writes with eventual consistency during partitions

Solution

  1. Step 1: Identify CAP constraints

    During network partitions, a system must choose between consistency and availability.

  2. Step 2: Match system behavior

    AP systems prioritize availability and partition tolerance, allowing stale reads but remaining operational.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    AP systems allow availability during partitions with eventual consistency [check]
Hint: AP favors availability over consistency during partitions [check]
Common Mistakes:
2. A web API receives sudden bursts of 10,000 requests per second but must process them at a steady rate of 1,000 requests per second to avoid backend overload. Which component best smooths this traffic to a steady rate without dropping requests?
easy
A. A leaky bucket queue that drains requests at a fixed rate
B. A token bucket that allows bursts up to a maximum token count
C. A fixed-size thread pool that rejects excess requests immediately
D. A simple FIFO queue without rate limiting

Solution

  1. Step 1: Identify smoothing mechanism

    The leaky bucket algorithm enforces a fixed output rate by draining requests steadily, smoothing bursts.

  2. Step 2: Eliminate alternatives

    A fixed-size thread pool that rejects excess requests immediately rejects excess requests immediately, not smoothing them. A token bucket that allows bursts up to a maximum token count (token bucket) allows bursts, not smoothing to steady rate. A simple FIFO queue without rate limiting has no rate control, so bursts pass through.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Leaky bucket drains at fixed rate, smoothing bursts [check]
Hint: Leaky bucket smooths bursts by fixed-rate draining [check]
Common Mistakes:
3. In an Active-Passive failover setup without a quorum-based consensus mechanism, what exactly breaks when the active node crashes and the passive node mistakenly assumes active role while the original active recovers?
medium
A. The system automatically merges data without conflicts
B. Split-brain occurs causing data divergence and inconsistent writes
C. Passive node refuses to accept writes until manual intervention
D. Active node permanently loses all data on crash

Solution

  1. Step 1: Understand lack of quorum impact

    Without quorum, passive node cannot safely confirm active node failure, risking split-brain.

  2. Step 2: Failover behavior without consensus

    To avoid split-brain, passive node blocks writes until manual resolution, causing availability loss.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    No quorum -> passive blocks writes to prevent split-brain [check]
Hint: No quorum -> passive blocks writes, avoids split-brain [check]
Common Mistakes:
4. In a sharded CRDT counter system, what exactly breaks if the shard state replication mechanism fails silently for several minutes?
medium
A. Local shard increments continue, but the global aggregated count lags behind until replication resumes
B. All increments are lost because shards cannot merge without replication
C. The global counter value becomes permanently inconsistent and cannot be recovered
D. The system blocks all increments until replication is restored to maintain consistency

Solution

  1. Step 1: Understand replication role in CRDT counters

    Replication propagates shard states to other replicas for merging. Without it, shards cannot merge and increments are isolated.

  2. Step 2: Trace failure impact

    Without replication, increments on isolated shards are effectively lost from global view until replication resumes; no blocking occurs.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Replication failure isolates shards, causing lost increments globally [check]
Hint: No replication -> isolated shards -> lost global increments [check]
Common Mistakes:
5. For a high-traffic API with strict memory limits and tolerance for bursty traffic, which rate limiting approach is best and why?
medium
A. Leaky bucket, because it enforces a steady output rate regardless of bursts
B. Sliding window counter, because it tracks exact request times for precise limits
C. Token bucket, because it smooths bursts and uses fixed memory for tokens
D. Fixed window counter, because it uses constant memory and handles bursts at window edges

Solution

  1. Step 1: Analyze memory constraints and burst tolerance

    Sliding window counters require storing timestamps, which grows with request volume, unsuitable for strict memory limits.

  2. Step 2: Fixed window counters use constant memory by counting requests per fixed interval, allowing bursts at window edges but fitting memory constraints

    Token and leaky buckets smooth bursts but require token state management and may not tolerate bursts as well.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Fixed window uses constant memory, tolerates bursts, fits strict memory limits [check]
Hint: Fixed window uses constant memory, sliding window stores timestamps [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