Requirements

Functional Requirements:

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

1. Save the original link and generate new random URL that will point to the original one and provide the new URL to the user.
2. Upon accessing the short URL the end user should be redirected to the original URL.
3. The users that created the URL should be able to get the statistict of ttotal calls to the URL available.
4. The new URLs provided should be globally unique.

Non-Functional Requirements:

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

1. The service should support strong consistency on write.
2. Latency: p99 for write 1 second and p99 0.2 sec for reads.
3. Availability: 99.9+%. Redundancy across availability zones.
4. High durability: on create, before responding to the end user with success the data must be written to replica. Synchronous replication.
5. Fault tolerance: reads are served via multiple read replicas and cache.

Capacity Estimation

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

Daily Active Users: 100 million users

Read/Write: 100:1 -> 1 million of URLs are shortned daily and 100 million short requests are redirected.

Storage requirements: the biggest entity is the Short URL table or structure that will hold:

• the original URL up to 128 bytes supported.
• Shortned url should be UUID of 16 bytes.
• creator_id as integer 8 bytes
• created_at as datetime 8 bytes
• total -> 192 bytes per record with alignment

Having 1 million of newly created URLs daily we would need to allocate 192 MB daily or roughly 50 GB per year.

Bandwitdth: on read request the user will send the short url payload mainly 16 bytes + the short url site domain. Having uniformly distributed users across the world, the 100 mln requests daily => 4 mln request per hour or 60k requests per minute or 1k QPS.

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.

1. domain-name.com/short-url POST
   1. payload: valid URL to be shortned
   2. respond on success 201 with new shortned URL created
   3. respond 400 if the URL was already shortned.
2. domain-name.com/<short-url::uuid>:
   1. shortned URL access request that should repond with redirect 302 status code and the redirect URL that will point to the original URL
   2. If the shortned url doesn't exist should return 404
3. domain-name.com/statistics/<short-url::uuid>
   1. Returns the number of times the URL was accessed and 200 status code
   2. Returns 404 if the short url doesn't exist.
   3. Should be available only to user that created the shorten URL.

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.

1. API servers with HPA configured.
2. Redis Cache:
   1. Bloom filters for POST request to check if the long URL was already posted or not. Cache update policy -> write-through.
   2. KeyValue LFU cache for handling read requests, will store the mapping from short url to the original one
3. Postgres DB -> since we will have roughly 15 write QPS per socond we can user relational DB like postgres for storing the data. So one write replica and 10 read replicas to handle spikes of requests. On write the data is written to primary and rplicated to one of the replicas that is standby. It's later asynchrnously replicated to other replicas.
4. NoSQL DB for read counts -> durable replicated persistence for storing the statistic of page access -> High availability support.
5. Kafka -> each successfull read of short url request will produce an event and then will update the counter in NoSQL db.

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...

SQL database horizontally sharded by hash of hte short url.

Tables:

• urls
  • original -> PK varchar 128 unique constraint
  • new -> uuid -> varchar 16 bytest -> BTREE indexed field
  • created_by -> FK to the user id -> 8 bytest
  • created_at -> datetime field

NoSQL table:

• short url -> long-url -> number of reads

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.

Bloom filters: having 365 mln newly created URLs per year and 1 billion URLS approximately in 25 years, we would need the Bloom filter to handle False negative level of 10*-7, so on each 1bln of requests we will get 100 false positives for 1 billion of URLS which is acceptable.

General KV Redis Cache with LFU, will store the most frequently used urls. As some urls will generally be accessed more oftend then others.

Kafka+ NoSQL DB will ensure eventuall consistency and durability for serving statistics API.

Cache TTL / expiry flow: Each mapping is cached in Redis with a TTL (e.g., 24h, refreshed on every hit). On a cache miss or expiry, the redirect service fetches the mapping directly from the shard (hash of short code → one shard), serves the 302, and writes the result back to Redis with a fresh TTL. To protect the DB from a thundering herd on a newly-viral link, concurrent misses on the same key are coalesced (single-flight) so the shard is hit once, and the first response populates the cache for the rest.