System requirements

Functional:

Users can create short urls of given long urls

Users can redirect to long urls from given short urls

Non-Functional:

System should be highly available, low latency.

API design

There will be 2 urls:

1) /create POST API, it takes in the original long url and returns a short url

2) /redirect/url_key GET API, it redirects to the original url

Envelope Estimations

• Lets say we have 100,000 daily active users. Lets assume each user creates 10 short urls in a day.
• So our write requests per second becomes ~10 requests per second.
• Lets say each day 1 short url is clicked on by 1000 people, so our read requests per second becomes ~1000 requests per second.
• The short URL will be of 6 characters of alphanumeric characters which gives us around 7 million combinations. So, each short url is 6 bytes. Per day total of 1million urls are created so in 1 day our system uses 6 MB of space. In 1 year it uses ~2.5 GB. Now, since the max expiration of a url will be 1 year, we will be cycling urls. So over 10 years we would need ~5GB of space to store short urls.

High-level design

We have the client, then comes GeoDNS which will route the request to the appropriate cluster. Then we got load balancers which route the request to appropriate app instance.

Then sits our cache, which caches 1000 urls and stores according to LRU policy. We then have a separate Key Generation Service (KGS) which is responsible for asynchronously creating 6 character strings called keys. We have a coordinator service which assigns a range of keys to each instance, that way we prevent race condition.

We then have a cleanup service that is responsible of cleaning the expired short urls so they can be reassigned.

KGS has sharded DBs to store keys. The DBs have table short_urls having 3 columns id, url_key(string), active(boolean).

Our app server has DB with tables users and user_urls. user_urls has columns id, user_id, long_url, url_key, created_at, expiration_date. We have multiple replicas of this DB to support high read frequencies.

The final piece is our cleanup service. Cleanup service is responsible for recycling the urls and it works with the main app's DBs and the DBs of KGS.

Detailed component design

Create flow:

• User hits the /create POST API, enters a long url. The request hits our app instance. App requests a url_key from the KGS, which is a 6 byte unique string.
• KGS then pulls a unique string from the KGS DB whose active column is false. Once pulled, KGS marks its active column as true so it cant be pulled again until expiration.
• Once our app receives the url_key, it writes a new row to the user_urls table in App DB using the long_url, url_key and with expiration as exactly 1 year later.
• Once the write is complete, the app instance caches the new short url to cache.
• Now, since our app is highly available, we have multiple instances of the main app service. Thus, there can be a race condition where 2 instances get the same url_key from KGS. To resolve this, we introduce a coordinator service. Coordinator service assigns a range of keys (for example keys starting with 'a' to 'c', assigned to instance 1, 'd' to 'f' to instance 2, etc).
• We create indexes on url_key and expiration_date for faster access and low latency.

Redirection flow:

• Whenever user goes to a generated short url, our GET API is called. Once the request reaches the main app, the app first checks cache for the short url. If cache hit, it returns the respective long url and redirects to it. In case of cache miss, the app queries the DB, gets the long url and caches the long urls and respective long short url, and then returns back the long url and redirects.
• In any case, our app checks if the accessed url has expired or not, if expired then redirects to an error page stating the short url has expired. Then sends the short url to our cleanup service to be recycled.
• The cache keeps 1000 recently accessed urls, and uses LRU to keep top 1000.
• Since our app is read heavy, we shall introduce multiple replicas of our App DB, so it doesn't get bottlenecked and doesn't become a single point of failure.

Cleanup flow:

• Since our short urls expire within 1 year of creation, we need to recycle and cleanup the expired urls. For that we have our cleanup service.
• Cleanup service checks the App DB for expired short_urls and removes the expired url rows from App DB. Then finds the respective row of KGS DB's short_urls table and sets its active flag to false so our expired url_key is ready to be reused.
• Cleanup service also gets short urls from our main app and recycles them the same way.