System requirements

Functional:

1. We'll return a short URL when user give us a long url to process
2. Return the original long URL when user hit short URL in their browser

Non-Functional:

1. Performance: The system should be able to handle large number of requests per second with low latency. Especially for read performance.
2. Scalability: The service must be scalable when user numbers increase
3. Availability: The service should be highly available(e.g., 99.9% uptime)
4. Usability: We provide both web interface and API access

Capacity estimation

We expact to have 100 M of users. Each users stores 100 url on average. That's 100 M * 100 = 10 Billion Key-value pair. Each K-V pair needs 1k byte. The total storage we need is 100 TB.

Assume 10% of users are DAU. That's 10M DAU. Each user would use 10 time each day.

So QPS = 100M / (24 * 60 * 60) = ~10 ^ 3

API design

With Base62 encoding, we might need log62(10 ^ 10) = 7 characters for short URL

We'll need two API for this service.

Get: tiny.url/abcdXYZ, we'll returns the original URL

POST: tiny.url with original URL in the body. We'll return shorten URL

Database design

The database will show as follows

shorten url - primary key

user id - secondary key

original url

creation time

expiration time

We'll use k-v store to store data to achieve high throughput and availability. We can use DynamoDB or Cassandra and set it to high consistency to meet our performacne requirement

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Start with basic

User → API gateway → read/write server → DB

To improve performance, we’d add a cache layer between server and DB using LRU strategy

We can also use CDN outside the data center to serve global users. Could be expensive so we want to keep it small

Key-value database like Dynamo DB is a great fit here since

It’s easy to scale and partition

Eventual consistency is acceptable

Fits our data model

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Read: User → API gateway → server → cache → DB

Write: User → API gateway → server → DB

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Cache

Use memcache or Redis, Use LRU

Partition

The short_url is the primary key of both cache and the database. It’s randomly generated so would be evenly distributed to be used as a partition key.

Trade offs/Tech choices

We choose Dynamo DB instead of relational databases for better scalability and availability. The potential consistency issue is that it might take some time to see the latest generated shorten_url on all shards.

For shorten_url generating function, there’re two approaches.

Hashing function using MD5, SHA2 etc.

Might encountered hash collision

Base 62 conversion

Depends on Unique ID generator

No collision

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

The servers are stateless. Once a server is down, the other servers will pick up.

DynamoDB and Redis are also highly scalable and fault tolerable

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

Add message queue to decouple server and DB