Bitly - Designing Shorten URL Service

Read Design a URL shortener

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

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

1. User authentication
2. 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

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

Below the line (not considered):

1. Data consistency in real-time analysis
2. Advanced 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:

1. Original URL (long url): the long url that the user submit
2. Short URL: the short hand url that generated by the system
3. 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:

1. POST: create new resource
2. GET: read the resource
3. PUT: updating existing resource
4. 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

1. 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
2. Persist it in the database once we have generated the short url
3. 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

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

1. 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
2. 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:

1. Use SHA-256 to hash this input into a fixed length
2. 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
3. This would still produce around 40+ character, we will then take the first n character to satisfy the requirement of 1B URL.
   1. To determine n, we take 62^n >= 1B, in this case n = 6 is the minimum, 62^6 = 56,800,235,584 reaching the billion mark

Since SHA-256 will encode into 256 bit (256 the 1000101xxx) this can feed into Base62 to present to reduce to around 43 characters. From this, we splice n character to get the desired code

def shorten(input: str, n: int = 6):
    url = normalise_url(input) # normalise .lower(), strip whitespace etc
    sha_256 = hashlib.sha256(url)
    base_62 = base62(url)
    return base_62[:n]

However, this would still lead to collision, taking the first n is not a great solution. To detect collision we can do

1. add UNIQUE constraint on the short code
2. retry 3-5 time with random salt until the constraint validate

However this still not 100% make sure that collision will resolve

Option 2: Unique incremental id + encoding

The idea is we have a continuous incremental id for each url we will increment this id and then simply Base62 the id instead of the hash, this will guarantee that we have a unique and short link.

In order to do this, we need something to generate continuous id, we can either use:

1. Database Sequence: No new infras needed
2. Redis if we need a fast and performance wise solution
   1. Redis is single thread per shard so all operation is atomic, which will work great in a distributed scale.

Each counter is always unique, we reduce the complex of having hash function

Challenges: An attacker could bruteforce and find all the possible link due to the id is incremented

We can use a secret salt to XOR our id so that the attacker cannot reverse the id. This would work because (id XOR secret) XOR secret = id so we can revert the XOR.

SECRET = 123_456_789

def shorten(input: str):
    id = get_incremented_id()
    secret_id = id ^ SECRET
    return base62(id)

def reverse(secret_id: str):
    id = secret_id ^ SECRET
    return id

Challenges: Size of the short code increasing overtime as the id growth

To support 1B URLs, we only need 6 character short code since 62^6 > 1B. We can consider increase this number to 7 or 8 to support more urls since with 7 or 8 characters, our URLs still relatively short

How to make sure that redirect are fast

Using database index to reverse lookup is not fast enough, the reason is indexing still based on disc. Disk I/O is slower than memory access.

1. Memory Access: 100 nano seconds (0.0001 ms), support millions read per second
2. SSD Access: 0.1 ms, support 100,000 IOPS
3. HDD Access: 10 ms, 100-200 IOPS

The solution here is to add a Cache layer of Redis - which store our shortURL: longURL for quick lookup

However, we need to take care of

1. Cache invalidation — we can consider Write through > Write through with invalidation
2. Cache need time to warm up, initial requests may still hit the database. We can prewarm the cache if we can predict the traffic
3. We need to make sure that the cache TTL is the same or less than the expiry date

Beside from this, we can add a layer of CDN to redirect requests to be handled close to user location. This redirect will happen at the CDN level

This will add some complexity onto our webserver in terms of invalidate the cache on CDN.

How to scale to support 1B shortened urls and 100M DAU

Given that the short code is around 8 bytes (8 character), long URL is 100 bytes, custom alias 100 bytes and expiration date 8 bytes, we have a total of 200 bytes per row. Lets round up to 500 bytes to account for addtional analysis data.

If we need 1B, we have 0.5 KB x 1,000,000,000 = 500,000,000 KB = 500GB. A single database instance is suit here.

Which database technology we use?

We can assume we have 100k new rows per day ~ 1 row per second. Any database technology can work. We can default to postgres.

What if db goes down?

We need to have 2 mechanism

1. Database replication: we create multiple identical copy on different server, if 1 server down, we can redirect to the other
2. Database backup: we snapshot the database every hour from the replication database to avoid production traffic usage. The backup can be stored on blob storage for recovery when necessary

How do we scale read and write?

Since read is much more than write, we need to use CQRS (Command Query Responsibility Segregation) to separate this into different responsibility. After that, we can scale these independently.

This can be scale like microservices, and then we can add a load balancer and scale out

When separating like this, we can use a centralized redis instance to store the counter so that we make each of the write service sharing the same counter. When the user request for a shorten URL, write service will fetch the id from there. To ensure the global counter is good, we can use Redis Sentinel or Redis Cluster will automatic failover.

For each write request, there would be a network overhead, how would we deal with this?

Reality, network requests are relatively fast and neglibile. In the case we really want to eliminate this, we can do a "counter batching"

1. The Write Service will request a range of number from redis, 1000 values at a time. i.e serivce A: 1000 -> 2000, service B: 2000 -> 3000
2. The redis instance atomically INCR 1000 for each value and return the start of the batch
3. The Write Service can internally use these 1000 value to increment without needing to contact Redis for each new URL
4. Once it's exhausted, Write Service would just request a new batch

How do we do multi-region deployment

Each region would have each own range to avoid conflict

• Region A gets 0 → 1B
• Region B gets 1 → 2B

Write go to the local regions redis. Read can serve globally via distributed cache. If need, we can scale Read per region as well and then query the database once there is no cache.

If the region exhausted the URL, we can assign a new range for the region i.e Region A can take 19B → 20B or something beside 0 → 1B.

Final design

Important HTTP code