Bitly - Designing Shorten URL Service

Understanding the problem

Functional requirement

If you're not familiar with the product, it's fair to ask your interviewer for clarifying questions. Main goal: list out a few features and don't get distracted by the non important one

For this one, we have

User should be able to submit long URL and get back shroten url
1. Optionally:
  1. should be able to use alias to shorten url
  2. Should be able to specify expire date
Should be able to access original URL by using shortened URL

Below the line (not considered):
These features are excluded to reduce the boat, we can discuss with our interviewer if they want to include it

User authentication
Analytics

Non functional requirements

Refer to how the system operate rather than what tasks it performs. Things like scalability, latency, availability. For this we can have

System should ensure uniqueness for short code
Redirection should occur with minimal delay (<100ms)
System should be reliable and 99.99% available (availability > consistency)
System should scale support 1B shortened URLs and 100M DAU

Below the line (not considered):

Data consistency in real-time analysis
Advnaced security features like spam detection

[!note]
Based on this requirement we can already see that our system is read heavy, the ratio of read to write could be 1000:1

From these, we would have the following in our whiteboard

The set up

Core identity

We dont need to know the detail, so far we would be able to see that we have 3 element:

Original URL (long url): the long url that the user submit
Short URL: the short hand url that generated by the system
User: the user that generate or create the URL

Our whiteboard now have this

The API

From the core identity, the requirement we need to generate the API to satisfy them. Most of the time, we would use REST API, with the following methods:

POST: create new resource
GET: read the resource
PUT: updating existing resource
DELETE: deleting existing resource

We would have something like this:

POST /v1/urls
{
    long_url: "https://google.com/"
    custom_alias?: "my_alias"
    expiration_date?: "1/10/2028"
} -> 
{ 
    short_url: "bit.ly/<code>"
}

GET /{code} -> HTTP 302 redirect

High level design

1) User need to be able to submit long url and get a shortened one

For writing, the client can post the url to the webserver. Our webserver will

Generate the short URL from the long URL
1. It needs to validate if the given URL is in the correct format. This can be using a validation library or we can use simple regex to do so
2. If the user has a custom alias, we need to make sure that the alias has not been used before, if so we save in the database. If the alias is used before, we can return a 409 Conflict error code
Persist it in the database once we have generated the short url
After finish, we return the short url to the client

2) User should be able to access the original URL by using the shortened URL

When the user do GET /{code}. Our server will

Lookup this short URL from the database to get the longURL
1. If no URL exists, we will return a 404 not found
2. If there is URL, but it's expired, we will return 410 Gone
Server then HTTP Redirect 302 to the browser

To cleanup expired URL, we can either do a background job to delete the expired rows.

For redirection there are 2 main way

301 (Permanent Redirect): Indicates that the resource has been moved. After return this, the browser will cache the response and redirect to the destinated URL in the future
302 (Temporary Redirect): indicate temporary redirection Preferred:
1. Give us more control
2. Allow us to track statistic on each redirect url

Deep dives

How to make the short urls unique

Option 1: Hash + Encoding

Given the base url i.e https://very-long-url-to-shorten.com/path1/path2/path3/.... We can follow:

Use SHA-256 to hash this input into a fixed length
Use Base62 to shorten SHA-256
1. We use Base62 instead of the popular Base64 because Base62 only include (a-z, A-Z, 0-9), Base64 will also include + and / which would not work in URL

Since SHA-256 will encode into 256 bit, we have 32 bytes character