Requirements

Functional Requirements:

• User can send a long link and get a short link. Service saves the mapping
• User can request a short link. Service have to redirect user to a appropriate long link

Non-Functional Requirements:

• High availability. All redirects have to work
• Low redirect latency. We have more reads than writes. So we have to redirect fast.
• Horizonal scalability. To procees a lot of reads we can add more servers with the same settings

Capacity Estimation

DAU - 100 million

read/write ratio - 100:1. So 100M writes and 10 billions reads a day

QPS - 100M / (24 * 3600) = 120000 read/sec, 10B / (24 * 3600) = 1200 writes/sec

storage requirement - 200 bytes * 100M = 20 Gb/day, 20 * 365 = 7300 Gb/year

API Design

• create a short link

• redirect

High-Level Design

Client sends a request. Load balancer distributes requests between API servers. API servers can be added or removed. It depends on a load. For generating short urls API servers get unique ID generator and and then apply base62 function to ID. API servers write new rows to database. We store often visited urls in cache. If there is not a url in cache, we read from database.

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

We use NoSQL because we have to store a lot of data, we do not have any relations, we just have serialize/ deserialize data.

We have 1 table with columns: short_code - primary key, long_url, created_at, expired_at. We should have the secondary index by long_url to check whether long url is already present in db.

For high availability we should have replicas and sharding by hash(short_code) % (shard number).

Creation requires strong consistency. Short code has to be unique and durable. Reading can be eventually consistent. We can return 404 if not all replicas has not got a new short code yet.

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.

We use Redis for cache. We should have cache replicas. We have to have evict policy least recently used. So often used url will be in cache. When we process redirect by short url, first we should check rows in cache. If we find the row, we will return the response to the client. If we do not find the row, we will look for the row in db. If we find the row in db, we will add the row to the cache and response to the client. If we do not find the row, the return 404 to the client. For deleted or updated links we have to delete them from cache.

There are some ID generator service instances for resilience. We can use UUID for generating ID to provide randomness.

We should add IP rate limiting to prevent a lot of short url creating.