System requirements

Functional:

• Users can paste the URLs that they want to shorten
  • If URL has been shortened by other user, reuse the same link
• Shortened URL is randomly generated
• Users can edit or remove URL
• Users can analyze the click rate in a graph

Non-Functional:

• Availability (99.99% availability)
• We want low latency (100ms) for getting the redirect URL
• Scalability (we assume that there will be many writes per second)
• Security (user account to manage the links)

Capacity estimation

Assume we have 1M monthly active users.

DAU = 1M / 30 = 33k users

Assume that each user shorten 8 links a day (5 links are unique), and for each links, there are 3 clicks

writes per day = 33k * 5 = 165k

Let's say long URL average length is 150 characters, so that's 150 bytes. For shortened URL, let's say there are 8 characters. Each write will take 158 bytes

Bytes per day = 165k * 158 = 26MB / day

storage for 5 years = 26MB * 365 * 5 = 47.45TB

reads per day = 165k * 3 = 495k

read per second = 495k / 24 / 60 / 60 = 5.7 read / s

To account for spike in traffic, we should support 50 read / s.

API design

Shorten URL

• POST /url
  • Request: Original URL, shortened URL (optional)
  • Response: ID, shortened URL (200) or failure

Edit URL

• PUT /url
  • Request: ID, new_url, new_shortened_url
  • Response: 200 or error

Access URL

• GET /url
  • Request: shortened_url
  • Response: original_url or 404

Delete URL

• DELETE /url
  • Request: ID (of the entry to delete)
  • Response: 200 or failure

For delete, we have to ensure that the entry is not owned by other users. Otherwise, we should still keep it.

Database design

User

• ID
• username
• password
• create_time

Subscription

• ID
• user_id
• subscription_type

UrlMap

• original_url (key)
• shortened_url
• create_time (can be used to expire the links)
• update_time
• status (active, expired, deleted)

UserUrl (composite keys for both IDs)

• user_id
• url_map_id
• create_time

For analytics

ClickUrl

• ID
• click_time
• url_id

We want to retain data for only 30 days. Or up to 90 days for higher tier subscription users.

Given the relationships of users and URLs and clicks can be complex, we will use relational database (e.g. PostgreSQL) to support complex queries and joins.

High-level design

We want to have API routers that route to either the read or write server depending on the request.

Before reaching the write or read server, we also want to have a load balancer, so that we can scale the system to more users (by scaling it horizontally).

We also have a write and read database, where periodically, write DB will update the read DB. Because of this, the data may not be consistent (users may not immediately be able to redirect). So on the webpage, we should warn users that it may take 5 seconds for URL shortening to take into effect.

Request flows

User shorten a new URL

• Client sent request to API routers, but it goes through load balancer before hitting API routers
• API routers route user to 1 of the write servers (chosen by the LB)
• Write server may write the URL link to the database (if it does not exist), and write to database to connect user to the URL map that was just written.

User goes to a shortened URL

• Same as before, but user goes to read server
• If the request is cached, we return the original URL. Otherwise, we access the read DB

Detailed component design

Sharding

• Hash the user ID and URL ID and distribute them evenly
• If the service has geographical distributed user base, we will shard by the location
• Also, we will use consistent hashing to easily add or remove shards (only portion of the database needs to be redistributed

Rate limiting

• Rate limiting on load balancer
• E.g. token bucket algorithm
• Allow users to create a certain number of short URLs

Message queues

• We may want to implement a messaging queue in the write server. When the write servers want to write to DB, we write to the queue instead, so that we can ensure responsiveness in the app. We can also handle high traffic volumes efficiently

Replication

• We can replicate the read DB to scale up if there are too many reads. However, there will be consistency issues, so we may have to consider the trade-off for that as well.
• strong consistency vs eventual consistency (lower latency, but stale reads)
• I think in this case, we prefer having lower latency, and consistency is not an issue. Therefore we will do asynchronous replication (changes made to primary database, and then propagated to replicas). Or semi-synchronous replication (updated to at least 1 replica)
• Conflict resolution: last write wins (based on timestamp)

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

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

Future improvements

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