System requirements

Functional:

1. Submit a URL and get a concise version of the URL that is guaranteed to be unique
   1. Require client to authenticate and provide email address
   2. Optionally, allow client to suggest concise URL
   3. Optionally, allow client to set expiration date
2. Submit a shortened URL and get the full version of the URL
3. Present real-time usage analysis to clients through Google Analytics

Non-Functional:

1. Store 10M URLs for first year with 20% growth every year
2. Support 1M URL translations per day, with peak traffic that is 500% of average
3. Expanding a URL take less than 100ms
4. Service must be always available (99.99% up-time)

Capacity estimation

1. 1M translations per day -> 11.6 translations per second
   1. expect peak traffic that is 500% of average
2. Each URL pair plus metadata should be 512 bytes, for storage of 500GB
   1. Expecting 20% growth year-over-year

API design

POST /api/v1.0/originalurl

{"original_url": url, "suggested_url", "expiration_date": date}

returns

{"original_url": url, "concise_url": url, "creation_date": date, "expiration_date": date, "created_by": email_addr, "used_suggested_url": bool}

If any URLs are invalid, return 400 with details

If suggested_url is available (and acceptable), we use it as concise_url

Otherwise, we generate a unique concise_url and use it

GET /API/v1.0/url/{shorturl}

If present, returns 200 original_url

If not, returns 404

GET /API/v1.0/stat/{shorturl}

returns

{"original_url": url, "concise_url": url, "creation_date": date, "total_hits": int, "hits_last_hour": int, "hits_last_day": int, ...}

Database design

NoSQL solution will be fine because that will allow DB sharding

Table: ConciseUrl

shortenedUrl str -- Primary Key

originalUrl str -- Index

createdDate timestamp

createdBy email_address

expirationDate timestamp

used_suggested_url str

Table: UrlStats

shortenedUrl str -- Primary Key

createdDate timestamp

total_hits int

hits_last_hour int

hits_last_day int

High-level design

We have a Load Balancer to distribute requests across multiple servers.

There is a URL Shortener Service that takes a full URL, checks if the provided URLs are valid, checks to see if it already exists and, if not, it creates a unique, new concise URL. It then returns the concise URL.

There is a URL Expander Service that takes a concise URL, looks to see if it exists and, if so, returns the original URL. If not, returns 404. This service will get the most traffic, so we'll want many redundant service nodes.

There is a Memcached cache that stores most recent URL expansions.

There is a DynamoDB database that stores our two database tables.

Request flows

For Get Concise Url:

1. The request is passed to the URL Shortener Service
2. If any provided URLs are invalid, return 400 Bad Request
3. If the URL has previously been shortened by this client, use the existing concise URL
4. If not, create a new, unique, concise URL and return it

For Expand Concise Url:

1. The request is passed to the URL Expander Service
2. If the URL expansion has been cached, use it
3. If not, see if it is in the ConciseUrl table in the DB
4. If not, return 404
5. Update the UrlStat table with the usage

Detailed component design

For Get Concise Url, the URL Shortener Service does the following:

1. Validates URLs
2. Looks for the original URL in the ConciseUrl table. If it is there, it returns the conciseUrl for the original
3. Follows multiple strategies for shortening a URL, each time seeing if the shortened URL already exists in the ConciseUrl table
4. If it exhausts all strategy, we fall back to a strategy of ending the URL with a base62 value that will guarantee uniqueness

Trade offs/Tech choices

We choose a Load Balancer to provide redundancy across servers and to enable us to scale horizontally. Also, if our service gets big enough, we can shard the DB by Concise URL to improve performance

We use a NoSQL DB to support sharding (Cassandara)

We use a Cache to improve DB performance (Redis)

Failure scenarios/bottlenecks

One challenge will be to deal with collisions when shortening a URL. We have multiple strategies including a fall-back approach to enable us to have both meaningful short URLs and guarantee of uniqueness

I expect the URL Expander Service will get the vast majority of requests, so sharding is a good approach to limit bottlenecks.

Future improvements

1. Check the concise URLs for offensive words
2. Time out URLs that are created but never used.
3. Allow clients to revise their URLs