Requirements

Functional Requirements:

System should allow users to enter a URL.

System should be able to return a short id for the URL

System should be able to return back the original URL given the short URL

Non-Functional Requirements:

System should be scalable. System should be able to withstand the high load

Each call to get the longURL should return same value.

System should be able to return response within milliseconds. p99 should be 10-100ms

System should be persistent and reliable.

System should be highly available.

Capacity Estimation

Lets assume the system has 10 million DAU.

Assume 100:1 for READ:WRITE

Assuming single URL on an avg is of 1KB and there are 1 million writes daily.

Total Size required in a day = 1KB*10 million = 1GB

Total storage requirement required would be 1*365 GB = 365GB in an year

Assuming 5 years of retention lets say, the total space required would be 2 TB.

Now, lets calculate the QPS & Bandwidth

Assuming 100:1 Read : Write

Avg. write / sec = 1 million / 40000 = 25 write/sec

Avg. Read 100 million /40000 = 2500 read/sec

API Design

In order to build such a system here are the APIs that the system needs

1) API to create a shortURL

Sign : /api/v1/create/shortUrl

method : POST

Request Payload : {uri : longUrl}

Response : shortURL

2) API to get the longURL

sign : /api/v1/redirect/?key=12312

method : GET

Return long URL for redirection

Important aspect here is the redirection :

The get response could either return 301 or 302 depending upon the usecase. For example, if the intent is to reduce the load on the server then 301 redirection (hence browser cache the response) is used. If analytics is impt. then 302 redirection (temporarily moved) should be used.

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Before designing this system its imp to decide the aspect of how this longURL will be saved in order to get its short key or id. There could be couple of approaches such as storing longURL in a table and returing its identity col value as a short key. But given the volume of data one table could easily get exhausted. Even if we use an identity column data type as serial the overall intent of generating the short key will be lost. Its imp thus to define what would be best. We could also use uuid but that too has 32 character length which is not what expected. We can have a prebuilt hash function that generates the hashkey against a value. Algorithm such as CRC32, SHA-1 and MD5 are some of the popular algorithm or hash fn used to generate the key. There could be one more approach such as Base62 conversion. Here the idea is to first generate an ID for a given longURL and then generate Base62 value of the ID.

Database Design

The database here would be simple. For example

SchemaName : public

Table Name : url_mapper

id : serial with autoincrement

longurl : varchar

shortUrl : varchar (10)

createdDate : Datetime

Index : create index on longurl & shorturl both using btree

Reason why we need index on both the column is below

Index on longURL : Since every create request will check if the URL is already in the system, its imp to have a index on longURL otherwise there will be high latency in the system as the no of rows increases.

Index on shortURL : This is required to improve the read ops.

Detailed Component Design

In the diagram at right side I have designed 3 diagrams. Each diagram illustrates separate aspects of the system

Dig 1 : Tells overall what requires to convert longURL to shortURL. The representation tells that we can have a shorturl convertor hash fn. This will convert each longurl to a short hash fn. Although it looks simple but it has its challenges. There are different hashing algo which can be used such as CRC32, MD5 or SHA-256. Hashing could be one of the option but hash fn may not result the consistent length in the short key. It also does not answer how will we resolve the conflicts. We can ofcourse use some passcode or prefix to append and then do hashing but that in turn adds complexity.

Dig 2 : This diagram tells that we can use Base62 conversion. Now, we can use [a-z,A-Z,0-9] characters to represent the longURL. The question is what should be length? To ans this first lets understand the algorithm

Any incoming request will be first be converted into random id. This random id generator will ensure that already assigned id is not used again. Now, once an id is generated then we can convert the ID to base62 encoded value. Remember, that this requires an random ID generator component.

Lets focus on DB :

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.