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

NoSQL vs SQL

Since we are using SQL, scaling horizontally is more challenging. We can shard the database, but we have to be careful not to shard in a way that slows down complex queries too much. As mentioned before, we chose PostgreSQL because the queries that we anticipated can be quite complex, and we want to optimise for that.

Microservice vs Monolithic architecture

I chose to separate the read and write servers because I prefer microservice instead of monolithic architecture. In this way, we can choose to scale up read or write servers independently.

Write and Read DB

We have both the write and read DB because we want to scale both the write and read DB independently as well. For example if there are many more read requests than write, then we just want to scale the read DB shard cluster.

Failure scenarios/bottlenecks

If there is a failure when writing to the DB, we will return the response to the user, and display an error message.

Optionally, we can implement a queue to write to the logs so that we can monitor the failures. If we find that this is a bottleneck, we may want to implement a messaging queue so that the write to database can happen asynchronously. On the client-side, it will show that the server is processing the user's request, and will continue to check for updated results (we can use polling).

For the tech stack, we can use Kafka and RabbitMQ for the scenario. In order to prevent flooding, we can use the token bucket algorithm so that in cases where there are too many requests, we will throttle the request. If the request or write fails, we will requeue the message if it's a temporary failure, and retry for maximum of 2 times.

Future improvements

We can add a messaging queue for read and write servers, and also log every request so that we understand the pattern of the users. To prevent DB from overloading, we should also have a daemon service that deletes expired links.