Loading...
Let us make the following assumptions to estimate the required capacity:
Based on these assumptions, we will need to have the following capacity:
Based on the requirements, we need to support CRUD operations on the Code entity. Here are the REST endpoint definitions:
POST /api/v1/code : Generate short code for a URL
Request Body
{
"target" : "https://www.google.com", // Required field containing the URL the system should redirect to
"expiresAt": "2027-09-16T00:00.000Z" // Optional field indicating when the record expires
}
Response Body
{
"code": "aB3xK9z",
"token": "550e8400-e29b-41d4-a716-446655440000"
}
Response Code
201: Success
400: Invalid request body
Response Headers
Location: /api/v1/aB3xK9z
Content-type: application/json
GET /api/v1/{code}: Redirect to the target URL
Response Code
302: Temporary Redirect // Temporary since codes can expire
404: Invalid code
Response Header
Location: https://www.google.com // target URL associated with the code.
PATCH /api/v1/{code}: Update TTL for a code
Request Body
{
"expiresAt": "2027-09-20T00:00.000Z" // Required
"token": "550e8400-e29b-41d4-a716-446655440000" // Required
}
Response Code
204: Success
404: Invalid code
403: Incorrect token
400: Invalid payload
DELETE /api/v1/{code}: Delete a code
Request Body
{
"token": "550e8400-e29b-41d4-a716-446655440000" // Required
}
Response Code
204: Success
404: Invalid code
403: Incorrect token
400: Invalid payload
In this section, we will cover all the functional and non-functional requirements one-by-one, starting with the functional requirements.
When the user provides a URL, the system shall generate and store a unique 7-character alphanumeric(0-9a-zA-Z) code and return the corresponding shortened URL.
The core problem of this requirement is to generate a unique 7-character alphanumeric code for the provided URL. Since different users might provide the same URL to be shortened, the problem basically requires us to generate a unique code for every request. There are two broad patterns to generate these codes:
Hash Function
We use one of the standard hashing algorithms(MD5, SHA1, SHA256 etc) to generate a hash code for the provided URL and analyse it on the following attributes:
Snowflake ID
A snowflake ID is a 64-bit distributed unique id that can generate 1000s of unique IDs per millisecond for ~70 years from the time of it's inception. We generate a snowflake id, transform into our base62 code and save it our database.
To meet this requirement we will need the following components:
Where the user provides a TTL, the system shall perform redirection only until the TTL expires.
We can use a scheduler that runs every night and deletes entries that have expired.
Figure 2 contains components required to meet all of our functional requirements
Next we analyse the non-functional requirements
The system shall provide high availability.
To ensure high availability we must ensure that there are no single point of failure by adding redundancies for them. Following components are needed:
The system shall resolve redirects in <100ms at p99.
We are expecting a peak traffic of 30000 reads/sec. Reads are also 100 times more than writes. Therefore, we split our core service into two different services:
This would allow us to scale reader service independent of writer. We also configure our API gateway to perform routing to the correct service.
But, even with a multi-node cluster, our servers will query database for every request which could slow down our system. Therefore, we also introduce a caching layer. We also ensure that our scheduler is cleaning expired entries from the cache.
Figure 4 describes our final high level diagram covering all our functional and non-functional requirement.
The system has a fairly simple storage requirement and both SQL and NoSQL can serve them.
Between Postgres and MongoDB, we choose Postgres since it provides strong consistency whereas mongo only provides eventual consistency meaning requests immediately after code generating might fail. We need strong consistency so that we don't end up generating duplicates. Therefore we use Postgres.
tiny_urls is the core entity in this system and it will have the following five attributes:
Refer to the ER diagram for the schema. Because the system is read heavy, we will use a flat, denormalised schema.
Indexes
Sharding
Our service requires 3TB of storage per year which warrants a partitioned database. Since we only get code as an input during read requests, the short code only must be our sharding key. Code is a base62 string which we convert into a base10 string to determine the shard where our key should be placed. This ensures our keys are distributed uniformly.
Redirection
GET /api/v1/{code} returns HTTP status 302 and Location in response header. Browsers on getting 302 response will look for Location header to get the redirection URL. 302 means temporary redirect so browser won't cache it, every read request will reach to our servers. This is intentional so that code stops working once it's TTL is over.
base62 conversion
We can convert our snowflake id into a base62 string using the following algorithm.
private static List<Character> BASE_62_MAP = Arrays.asList(
'0','1',...,'9','a','b',...'z','A','B',...'Z'
);
public String toBase62(long base10) {
return toHigherBase(base10, BASE_62_MAP);
}
private String toHigherBase(long input, List<Character> map) {
StringBuilder sb = new StringBuilder();
int power = 0;
int baseX = map.size();
while (input > 0) {
int lastDigit = input % baseX;
int value = (carry + (lastDigit * Math.pow(baseX, power)));
sb.append(map.get(value % baseX));
carry = value / baseX;
power++;
}
while (carry > 0) {
sb.append(map.get(carry % baseX));
carry = carry / baseX;
}
return sb.reverse().toString();
}