System requirements

Functional:

support create new short url given a long url

given a short url, support redirect to the original long url

delete/update existing short url

monitoring/analytics/rate accounting

Non-Functional:

should be consistent

redirection should be low latency

should be high availability.

fault tolerance

scalability

security: rate limiting, spam attach,

performance optimization like cache for high hit urls

Clarification: it is allowed that the same original url can have multiple version of shorten urls.

Capacity estimation

2^30 ~ 1B unique url

2^32 ~ 4B unique url

62 ~ 2^5

2^32/2^5 ~ 6 characters

shorten url could have 6 characters

API design

string GetShortURL(string original_url)

// error handling

Invalidate url

ShortURLInfo GetOriginalURL(string short_url)

// get the long url, also other metadata like status, creation date, number of clicks,

boolean deleteShortURL(string short_url)

string updateShortURL(string short_url, string new_original_url)

Database design

Choose MySQL as the storage

create table short_url_info {

VARCHAR(16) short_url_id primary_key not null

VARCHAR(255) short_url unique not null

timestamp creation_date_time default current_time

int clicks

timestamp last_access_time default_current_time

VARCHAR(2048) original_url not null

int user_id

foreign key (user_id) references users(id)

}

create index short_url_idx on short_url_info(short_url)

create index original_url_idx on short_url_info(original_url)

For better scaling, we can choose Amazon DynamoDB

High-level design

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

Detailed component design

URLGen: have a incremental number max_index long

ENcode(62): map = char[A, B, C, D..Z, abcd..z012345..9]

while (max_index > 0) {

result.append(map[max_index/62])

max_index = max_index%62;

}

return result; // shorten url

During Redirection time, given a shorten url, we can reconstruct the original index, which can be used as the primary key to fetch all the information related to the shortenurl.

a1b7v8 -> 50+40*62 + 49* 62*62 ...-> the UUID

Encode62 can avoid collision.

For UpdateURL, we can keep the shortenurl the same but point it to a different original_url. only the same user can update the url. The consideration is assume the shorten_url is already shared publicly, we can keep it stable to avoid breaking the old user. Assume user might have a better version of the long url.

Trade offs/Tech choices

Why Encode62 instead of SHA256 or other hashfunction?

other hashfunction may not guaranty uniqueness

SHA256, given a input->output, but couldn't go from output->input, thus the redirection is hard. we need to introduce additional table to map back the output -> input.

Use Redis or Memcached as the scalable caching solution

Failure scenarios/bottlenecks

if we need to handle >4B of unique urls, we can introduce two long number:

prefix_index and suffix_index, it will cover 16BB unique urls, make the shorten url to be 12 characters.

For redirection, DB access might be a bottleneck, we can introduce cache(Least Access eviction policy) to reduce the load on DB.

MYSQL can horizontally shard, backend services can also shard, cache can also shard

Redirction service can potentially shard by url prefix.

Use Consistent hashing for better scalability, Amazon Elastic LoadBalance to auto adjust according to incoming traffic, handle hotspot

Maintain max_index globally might be a single point of failure.

Each URLGen claim a range, each server will use the local range first.

Encode62 may have security concern because it may allow the users to guess internal details.

Future improvements

URL validation

Rate limit for spam

CDN optimization for low latency high availability

set expiration time in order to clean up old/stale urls no one actually use to control db size.

Have periodical cleanup job to validate original_urls and clean up stale urls.