Requirements

Functional Requirements:

List the key functional requirements for the system (Ask the AI for hints if stuck)...

1. input a long url and return a short url
2. redirect the short url to the original long url

Non-Functional Requirements:

List the key non-functional requirements (performance, scalability, reliability, etc.)...

1. high availability
2. low redirect latency - <100ms
3. horizontal scalability
4. read : write = 100 : 1
5. support few million regular users
6. 100m URLs created a day
7. 1.2k QPS for URL creation
8. 200-300k peak read QPS

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

• for each entry short and long URL, assume 500 bytes
• 100m URLs a day x 500 bytes = 50GB/day
• ~1000 days in 3 years -> 100 billion URLs in 3 years and 50TB in 3 years -> 1 trillion URLs in 30 years
• using base62 conversion 7 characters give us 62^7 = 3.5 trillion combinations
  • therefore, 7 characters of base62 is the minimum

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

• POST /v1/urls/shorten
• GET /v1/urls/:shorturl

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

• user calls API on the client
• gateway functions:
  • load balancing to ensure the horizontally scaled server has each pod receiving appropriate traffic
  • rate limiting
• server receives API request and queries database to retrieve short and long url mapping
  • single instance needs to scale horizontally by spinning up more pods/containers
  • server contains the shortening algorithm/logic
    • can be algorithm like base62 or hash function like SHA-256
• cache is added in between the server and database so that reads hit the cache without touching the database
• database uses dynamoDB since it can handle the high read QPS and writes are appended only
• to prevent key collisions,
  • firstly, we can estimate the number of bits given to a unique key: require 36bits to represent 3.5T / 62^7
  • each machine at each datacenter tracks its own unique key given per second in memory
  • lets assign the number of bits to create a unique key - [timestamp, datacenter, machine, unique sequence]
  • lets set aside the number of bits for the timstamp - 2^22 gives us 48 years with the precision of 1s
  • at 1.2k QPS, we need a minimum of 1.2k unique keys. therefore, we can assign 10 bits (2^10 = 1024) combinations for each machine in each data center. since not every request will hit the same machine at the same datacenter
  • we are left with 4 bits. since we are horizontally scaling the server, lets assign 2bits for each data center, 2bits for each machine. this assumes 4 data centers world wide and 4machines at each data centers.
  • this gives us a 36bit unique key generated at each machine
    • we can then use base62 conversion to convert the 36bit value to a string within 7 characters
  • overall, the primary key can be a base2 36bit value converted to base10 value (using an integer as primary key). the short url will be a 7 character base62 conversion of the 36bit unique key
• for the POST API:
  • 1.2k QPS writes to database is not a lot to dynamoDB that is a distributed server that can scale horizontally. all writes can be done synchronously from server to cache to db.
  • using a write through strategy, we write the entry into cache followed by database synchronously.
• for the GET API:
  • 200-300k read QPS hits the cache. redis is able to handle that load with multi threading for the reads. elasticache is able to handle millions of QPS as well.
  • where there is a cache miss, those queries hit dynamoDB to repopulate the cache.
  • dynamoDB is able to handle that read QP

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

• access patterns:
  • using longurl get shorturl
  • using shorturl get longurl
• single database needed without relations, therefore i can use a NoSQL database like dynamoDB
• dynamoDB natively scales horizontally, so reads can reach millions of QPS. we will use an append only table so that writes has lower latencies too. this works as we do not have requirement to replace the longurl and shorturl mapping

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

1. ID Generation — Snowflake-style → base62 We mint a 36-bit unique numeric key: [timestamp | datacenter ID | machine ID | sequence], then encode to base62 → 7 chars (62⁷ ≈ 3.5T keys ≈ 96 years of headroom at 100M/day). Uniqueness is guaranteed by construction — no collision check or retry loop on the write path. Datacenter + machine bits plus a per-machine monotonic sequence prevent split-brain duplicates; a machine with clock skew relies on the sequence counter continuing from its last value.

Alternatives considered and rejected: 128-bit UUID → ~22 base64 chars, too long for a shareable short URL; shared autoincrement DB → becomes a single-point bottleneck to scale; hash-and-check loop → extra disk seek per create. Keys are enumerable, but the data (URL mappings) isn't sensitive, so guessability is an accepted trade-off.

2. Write path — synchronous write-through (no queue) Create flow: gateway rate-limit check → URL validation → generate key → insert into DynamoDB → populate cache → return short URL. Write volume is only 1.2K QPS, which DynamoDB absorbs trivially, so Kafka is unnecessary: a queue only decouples a write rate that doesn't need decoupling, and async writes open a consistency window where a fresh link can 404 if the cache is lost before the batch lands. Write-through costs a few ms of create latency and guarantees the mapping is durable before the user ever sees it — so a cache failure can never lose or 404 a valid link.

3. Read path — L1 → L2 → DynamoDB

• L1: per-node in-memory cache, 1s TTL (~0.5MB per node). Handles hot-key skew by design — a viral key replicates across every node, so no single node or shard bears the burst.
• L2: Redis/ElastiCache cluster, LRU + TTL eviction, shared across nodes.
• Miss path: fetch from DynamoDB → serve redirect → repopulate L2.

DynamoDB scales horizontally to 300K+ read QPS with no sharding logic to maintain, so read replicas aren't needed — the store is the horizontally scaled tier. Request coalescing is therefore optional polish, not survival machinery: single-flight per key (lease + waiter timeout) is only added if measured p99 degrades under extreme hot-key skew.

4. Abuse protection — tiered access + delayed activation Rate limiting alone can't stop a distributed botnet (per-IP limits leak IPs × limit), and banning IPs collateral-damages shared-NAT users. So access is tiered:

• Anonymous: per-IP rate limit (sliding window) + delayed activation — new links are scanned asynchronously (create event → Kafka → scanner → domain reputation/blocklist verdict) before serving live; users see a "link being checked" interstitial meanwhile.
• Authenticated (API key): higher limits, immediate activation, revocable keys → abuse is attributable.

Banned links live in a key-value store mirrored into gateway local memory via pub/sub; the gateway returns 403 before any cache or app node is consulted, so 1s L1 staleness never serves a banned link. Client blocking (edge ban) is used for clear abuse, but layered behind the tiering so good users aren't collateral damage.

5. Load balancing L4 load balancer for low latency and uniform distribution; L7 grouping of reads/writes causes hotspots with a few million always-active users.