Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

URL Generation Service

scalability - the algorithm chosen should be able to work well with billions of URLs
collision handling - the algorithm should be able to handle duplicate url generations.

Approach 1 : Hashing and encoding

use a hash function e.g. MD5 or SHA-256 to generate fixed length hash of the original URL.
Encode the hash into a shorter form using Base62 (A-Z, a-z, 0-9)
The length of the short url is determined by the number of chars in the Base62 encoded string e.g 7 char Base62 represents 3.5 billion unique URLs

Work flow

user submits a long url request to generate short url
Generation of an MD5 hash of the long url to generate a 128 bit hash i.e 32 char hexadecimal string
Take the first 6 bytes of the hash and convert them to decimal
encode the result into a base62 encoded string i.e 48 bits

Issues that can be encountered with this approach

Possibility of the same shortened url for identical long url requests
possibility of collision where two different long urls generating same hash

Resolution

Re-Hashing - If a collision is detected, the service should rehash the original url with a different seed or additional bits from the original hash to generate a unique short url

increamental suffix - append an incremental suffix e.g. -1 or -2 to the short url until a unique key is found

Approach 2: Unique ID Generation

Involves assigning each new URL added to the system a unique auto-incrementing ID.
After an ID is generated, it is converted into a shorter URL Friendly format using Base62 encoding, which becomes the short url
It is hard that two different URLS receive the same ID as long as the ID generation mechanism functions correctly

Two considerations

The incremental IDs are predictable meaning one can guess the short url . You can mitigate by encoding the ID with a random seed
Scalability - If a single point (centralized db) is used for ID generation, it can become a scalability bottleneck. It can be mitigated using distributed ID generation such as Twitter's Snowflake to ensure scalability why ensuring uniqueness

Custom short urls

look up if it already exists in the db
validate the characters - only alphanumeric chars are allowed
check against a list of reserved words

Link Expiration

User can specify the expiration time, and the system must validate the date given to make sure it is within the limit and in the future.
Also, system can assign the default expiration period
use cron job or background jobs to schedule periodical check for expired urls and make them inactive or delete theme.
also use real time expiration where the redirection does not take place after link expiry.

Redirection Service

In charge of redirecting a user to original array when the link is accessed.
it first of all does a database lookup then redirects
use caching to improve performance , by taking the frequently accessed short URLS and caching them in an in-memory store like Redis.

Analytics Service

Use this service to track the number of times a URL is clicked
event logging using a message queue like Kafka to log each click event.
batch processing - process the logs in batches for aggregation and storage in a data warehouse for later analysis.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10