Loading...
Throughput:
Storage Estimation:
total storage = 127 bytes
total url per year = 127 * 1000000 * 365 = 127,000,000 = 46 GB
Bandwidth:
Assuming HTTPs 301 request is about 500 bytes(including headers and all)
Caching estimation:
we will use REST API.
Endpoint: POST /shorten
This endpoint creates a new short URL for a given long URL.
sample request:
{
"original_url" : "....",
"custom_name" : "" //optional
"expiration_date" : "....", //optional
"user_id" : "...."
}
sample response:
{
"short_url" : "...",
"original_url" : "...",
"expiation_date" : "...",
"creation_date" : "..."
}
Endpoint: GET /{short_url_key}
This endpoint redirects the user to the original long URL.
Sample Response:
HTTP/1.1 301 Moved Permanently Location: https://www.example.com/some/very/long/url
A NoSQL database like DynamoDB or Cassandra is a better option due to their ability to efficiently handle billions of simple key-value lookups and provide high scalability and availability.
We would need two tables: one for storing url mappings and one for storing user related information.
url_mapping_table features : {url_id , user_id ,short_url ,long_url ,creation_date ,expiration_date ,click_count}
user_table : {user_id ,name ,password ,e_mail}
Load Balancer: Distributes incoming requests across multiple application servers.
Application Servers: Handles incoming requests for shortening URLs and redirecting users.
URL Generation Service: Generates short URLs, handles custom aliases, and manages link expirations.
Redirection Service: Redirects the users to the original URL.
Database: Stores mappings between short URLs and long URLs.
Cache: Stores frequently accessed URL mappings for faster retrieval.
Analytics Service (optional): Tracks usage statistics like the number of clicks, geographic location, etc.
Shortening URL Flow:
User sends a request to Load Balancer to shorten a URL.
Load Balancer forwards the request to an Application Server.
Application Server interacts with the URL Generation Service to generate a short URL.
URL Generation Service stores the mapping in the Database and returns the short URL.
Application Server sends the short URL back to the User via the Load Balancer.
Redirection flow:
The primary function of the service is to generate a short, unique URL for each long URL provided by the user.
Here are some things to think about when picking an algorithm to shorten the URL:
URL Length: Shorter is generally better, but it limits the number of possible distinct URLs you can generate.
Scalability: The algorithm should work well even with billions of URLs.
Collision Handling: The algorithm should be able to handle duplicate url generations.
Approach 1: Hashing and Encoding
A common approach for generating short URLs is to use a hash function, such as MD5 or SHA-256 to generate a fixed-length hash of the original URL.
This hash is then encoded into a shorter form using Base62.
Base62 uses alphanumeric characters (A-Z, a-z, 0-9), which are URL-friendly and provide a dense encoding space.
The length of the short URL is determined by the number of characters in the Base62 encoded string.
A 7-character Base62 string can represent approximately 3.5 billion unique URLs (62^7).
Example Workflow:
User submits a request to generate short url for the long url: https://www.example.com/some/very/long/url/that/needs/to/be/shortened
Generate an MD5 hash of the long URL. MD5 produces a 128-bit hash, typically a 32-character hexadecimal string: 1b3aabf5266b0f178f52e45f4bb430eb
Instead of encoding the entire 128-bit hash, we typically use a portion of the hash (e.g., the first few bytes) to create a more manageable short URL.
First 6 bytes of the hash: 1b3aabf5266b
Convert these bytes to decimal: 1b3aabf5266b (hexadecimal) → 47770830013755 (decimal)
Encode the result into a Base62 encoded string: DZFbb43
The specific choice of 6 bytes (48 bits) is important because it produces a decimal number that typically converts to a Base62 string of approximately 7 characters.
Although this solution works for most cases, it has few issues:
It can generate the same shortened url for the identical long url requests.
Although rare, collisions can happen, where two different URLs generate the same hash.
Collision Resolution Strategies:
Re-Hashing: If a collision is detected, the service can re-hash the original URL with a different seed or use additional bits from the original hash to generate a unique short URL.
Incremental Suffix: Another approach is to append an incremental suffix (e.g., "-1", "-2") to the short URL until a unique key is found.
Approach 2: Unique ID Generation
Instead of hashing, another method to generate short URLs is to use incremental IDs.
In this approach, each new URL that is added to the system is assigned a unique, auto-incrementing ID.
For example, the first URL might be assigned ID 1, the second URL 2, and so on.
Once the ID is generated, it is converted into a shorter, URL-friendly format using Base62 encoding. This encoded string becomes the short URL.
Because the IDs are generated incrementally, each new ID is unique and sequential. There is no possibility that two different URLs will receive the same ID, as long as the ID generation mechanism (e.g., a database with an auto-incrementing primary key) is functioning correctly.
While the incremental ID approach is straightforward and collision-free, there are a few considerations:
Predictability: Incremental IDs are predictable, which means that someone could potentially infer the number of URLs shortened by your service or guess other users' URLs by simply incrementing the short URL.
Mitigation: You can add a layer of obfuscation by encoding the ID with a random seed or shuffling the ID before encoding it with Base62.
Scalability: If not designed properly, a single point of ID generation (like a centralized database) can become a scalability bottleneck.
Mitigation: Distributed ID generation strategies (like Twitter’s Snowflake) can be used to maintain scalability while preserving uniqueness.
Custom Aliasing
Custom aliasing allows users to specify their own short URL instead of accepting a system-generated one.
This feature is especially useful for branding or memorable URLs.
Custom Alias Validation:
Uniqueness Check: The service must ensure that the custom alias provided by the user is unique and not already in use. This requires a lookup in the database to verify that the alias does not exist.
Character Validation: Custom aliases should be validated to ensure they contain only allowed characters (e.g., alphanumeric characters, hyphens). This prevents the creation of problematic or non-URL-friendly aliases.
Reserved Aliases: Some aliases might be reserved for internal use (e.g., "help", "admin", "about"). The Service Layer should check against a list of reserved words to prevent users from using these.
Custom Alias Storage:
Alias Mapping: Once validated, the custom alias is mapped to the original URL and stored in the database, similar to system-generated short URLs.
Conflict Resolution: If the requested custom alias is already taken, the Service Layer should return an appropriate error message or suggest alternatives.
Link Expiration
Link expiration allows URLs to be valid only for a specified period, after which they become inactive.
Expiration Date Handling:
User-Specified Expiration: Users can specify an expiration date when creating the short URL. The service should validate this date to ensure it's in the future and within allowable limits (e.g., not exceeding a maximum expiration period).
Default Expiration: If no expiration date is provided, the service can assign a default expiration period (e.g., 1 year) or keep the link active indefinitely.
Expiration Logic:
Background Jobs: A background job or cron job can be scheduled to periodically check for expired URLs and mark them as inactive or delete them from the database.
Real-Time Expiration: During the redirection process, the service checks whether the URL has expired. If expired, the service can return an error message or redirect the user to a default page.
6.2 Redirection Service
When a user accesses a short URL, this service is responsible for redirecting the user to the original URL.
This involves two key steps:
Database Lookup: The Service Layer queries the database to retrieve the original URL associated with the short URL. This lookup needs to be optimized for speed, as it directly impacts user experience.
Redirection: Once the long URL is retrieved, the service issues an HTTP redirect response, sending the user to the original URL.
Example Workflow:
A user clicks on https://short.ly/abc123.
The Redirection Service receives the request and extracts the short URL identifier (abc123).
The service looks up abc123 in the database or cache to find the associated long URL.
The service issues a 301 or 302 HTTP redirect response with the Location header set to the long URL (e.g., https://www.example.com/long-url).
The user's browser follows the redirect and lands on the original URL.
Caching for Performance
To reduce database load and improve latency, frequently accessed short URLs can be cached in an in-memory store like Redis.
The Redirection Service should first check the cache before querying the database.
6.3 Analytics Service
If the service needs to track analytics, such as the number of times a short URL is clicked, a separate analytics service can be introduced:
Event Logging: Use a message queue (e.g., Kafka) to log each click event. This decouples the analytics from the core redirection service, ensuring that it doesn’t introduce latency.
Batch Processing: Process logs in batches for aggregation and storage in a data warehouse for later analysis.
Incremental IDs are predictable, which means that someone could potentially infer the number of URLs shortened by your service or guess other users' URLs by simply incrementing the short URL.
Mitigation: You can add a layer of obfuscation by encoding the ID with a random seed or shuffling the ID before encoding it with Base62.
Scalability: If not designed properly, a single point of ID generation (like a centralized database) can become a scalability bottleneck.
Mitigation: Distributed ID generation strategies (like Twitter’s Snowflake) can be used to maintain scalability while preserving uniqueness.
When scaling out (adding new shards), re-hashing and redistributing data can be challenging and requires consistent hashing techniques to minimize data movement when adding or removing shards.
Implement collision detection during URL creation to prevent conflicts, and ensure that the Redirection Service always resolves to the correct long URL.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?