Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• High Availability
• Low Redirect latency

API Design

The following are the APIs that we need

• /shorten (POST API): Takes original long url(string), takes expiration date (date time). Returns shortened API, creation date, expiration date.

• /{shortened_url} (GET API) : Takes the shortened url in parameters, in response redirects to the long url.

Capacity Estimations

• Traffic estimates: Lets say we get 100 url shortenings per second. And lets say we get 10,000 redirect requests per second. This gives us an idea that the system is read heavy. Let us say we are planning for 5 years.
• Storage estimates: So we decided on 100 writes/second so 100*86400 = 8.64 million urls/day. So for 5 years we get 8.64 million *5*365 = 15.768 billion urls over 5 years. Let us say each record is 500 bytes, so for 15.768 billion * 500 bytes = 7.844 TB round off to 8TB which is quite easily manageable.

High-Level Design

• There is client, it sends request to a Load Balancer. Which then sends request to API gateway.
• Then we have application server.
• Application server has a DB for it. Application server calls the URL generation service when /shorten API is called, when /{shortened_url} is called, it doesnt call Key generation service(KGS) , instead it redirected to the original url.
• We have a key generation service which communicates with the application server.
• We have Keys DB that is tied to KGS, KGS asynchronously keeps generating urls.
• We have caching that caches recently used URLs.
• We have cleanup service that cleans up expired URLs so they can be reused.
• Application DB is NoSql and stores everything in a collection. The schema is id, original_url, short_url, expiration_date.
• Keys DB is NoSql and stores everything in a collection. The schema is id, key(String), in_use(boolean).

Detailed Component Design

• When client calls /shorten API, request goes to LB and then to API gateway then to application server.
• Application service then takes the original_url, pulls a key from KGS then encodes this key with base62. Using base62 gives us over 56.8 billion urls, as we calculated before that over a lifetime of years we get to 15.768 billion urls, thus chances of collision are near to none and they are unique. Since they are base62 encoded, they cannot be easily guessed.
• In the KGS, instead of generating the short_url from the original_url, we asynchronously generate 6 letter random strings and store them in KGS's DB, these strings are the keys. Initially these are stored in the DB with their in_use field set to false. Thus, when our application service generates a url, KGS gives a "key" whose in_use is set to false, when KGS gives this key it sets in_use to true at the same time.
• Once the shortened URL is generated, a record is created in application service's DB storing the original URL and the shortened version.
• When the user hits /{shortened_url} api, the request goes to our application server, which then checks if the url is in the cache. If the url is in cache, we redirect to original_url. If not, we pull the original_url from the DB, then check expiration_date, if the link hasn't expired we save this to cache and redirect with code 302. If url has expired or doesn't exist, we send it to cleanup service and send a response (code 404) to client notifying the shortened_url has expired.
• Now, we know our URL shortener application is very read heavy, so to combat this we create a read replica of the application service's DB, that way all the traffic isn't redirected to a single DB and prevents latency.
• Also, since our DBs are NoSql , horizontal scaling is easily possible and thus availability is achieved.
• We use CDN so that our application is available across the globe.
• The cleanup service cleans up the Application DB by removing the records of shortened_url which have gone past expiration date. Then, in the URL DB, this shortened_url is set to in_use = false. Also, when the client hits /{shortened_url} api, this cleanup is done then as well.