System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. The system should generate a short unique URL for a given long URL.
2. The tiny url should redirect to the original URL when clicked.
3. Users should be able to customize their short URLS instead of randomly generating one.
4. The system should support url expiration after a certain period or number of uses..
5. The system should provide analytics on the usage of the shorted URLS, such as the geographic data of the users, and number of clicks.

Non-Functional:

List non-functional requirements for the system...

1. High availability.
2. Low latency (The shortening and redirects should take place in under 10 ms) to ensure performance.
3. Security to prevent malicious use.
4. Highly scalable - the system should handle a growing number of requests as adoption increases.

200 requests per second (17 million in a day) in creating short urls

20,000 (1.7 billion) requests per second to access shortened URLs.

Capacity estimation

Estimate the scale of the system you are going to design...

1. Daily requests for URL shortening - 200 requests per second (17 million in a day)
2. Daily requests for for accessing - 20,000 per second (1.7 billion) in a day.
3. Peak traffic - 2x the average load
4. Average length - 100 chars for original, 8 chars for shortened
5. Read:Write ratio: 100: 1

Throughput Requirements

Average writes per second (WPS): 200

Peak writes per second : 2000

Average redirects per second (WPS): 20000

Peak redirects second : 200000

Storage Estimation

original URL: 100 chars

short URL: 8 chars

creation date: 8 bytes (timestamp)

expiration date: 8 bytes (timestamp)

click count: 4 bytes (integer)

total storage per URL: 128 bytes

total urls per year = 17,000,000 X 365 = 6,205,000,000

total storage per year = 128 * 6,205,000,000 = 794,000,000,000 bytes ~ 795GB

Bandwidth Estimation

One request is 500 bytes, so 500 * 17,000,000 = 8.5GB per day

peak bandwidth = 500 * 200000 = 100 MB/s

Caching Estimation

Read heavy system requires caching to reduce the latency of read requests

Consider the 80-20 rule where 20% of the hot URLs generate 80% of the traffic

so, 17,000,000 * 0.2 * 128bytes = 435MB

20000 * 0.10 = 2000 rps

Infrastructure Sizing

API Servers - 7-8 instances behind a load balancer that can handle 200 -300 RPS

Database - Distributed database with 10 to 20 nodes to handle storage, high read/write throughput

Cache Layer - distributed cache with 3 - 4 nodesdepending on the load cache

API design

Define what APIs are expected from the system...

URL Shortening

POST REQUEST /api/v1/shorten

Sample Request

{

"long_url": "https://example.com/needs/shortening" ,

"user_id": "user1",

"custom_option": "https://shortened",

"expiry_date": "12/4/2025"

}

Sample Response

{

"long_url": "https://example.com/needs/shortening" ,

"short_url": "https://shortened/12",

"date_created": "12/4/2024"

"expiry_date": "12/4/2025"

}

URL Redirection API

GET REQUEST /{short_url_key}

response: status 301

location: https://example.com/needs/shortening

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

• we choose the NoSQL database since most operations are simple key-value looksups, the db should be highly scalable, a lot of read queries,and no need for joins between tables.
• Cassandra or Dynamo db

DB Schema

Two tables, one for User Information, another one for URL Mappings

url_mapping

long_url: varchar

short_url: varchar

date_created: Timestamp

expiry_date: Timestamp

user_id: int

click_count: int

user

user_id: int

name: varchar

email: varchar

password: varchar

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Client - send a request to the load balance

load balance - distributes traffic to the available application servers

application servers - handle the incoming requests for shortening and redirecting

URL Generation service - shortens the original urls, stores them and manages link expiration

redirection service - redirects the user to original url

database - stores mapping for short and long urls

analytics service - fetches the data for number of clicks of the short url

cache - stores frequently accessed urls mappings for faster retrieval

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.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

SCALABILITY

API layer - Deploy the API Layer across multiple instances behind a load balancer to distribute incoming requests evenly.

Sharding - if using the auto-increment ID as shard key, first shard can be 1 to I million while second shard can be 1m to 2 million. Only issues is that it can create a hotspot due to uneven load distribution when one shard is bigger than another.

Hash-based sharding - apply hash function to the shard key to determine which shard the data should go to. e.g. hash the short url then modulo with the number of shards to determine the shard it should go to.

The issue with this is when scaling out, redistributing data can be challenging and can be resolved with consistent hashing techniques.

AVAILABILITY

Replication - use database replication to ensure data is available even if some nodes fail.

Failover - use failover mechanisms for the API and data store layers to switch to a backup incase of server failures.

geo-distributed deployment - deploy the servers across multiple geographical locations to reduce latency and improve availability.

Handling edge cases

Expired URLS - Return meaningful response e.g. HTTP410 instead of redirecting.

Non-existent URLS - Return 404

urls conflicts - implement collision detection during URL creation to prevent conflicts.

SECURITY

Rate limiting -implement rate limiting at the API Layer to prevent abuse.

Input validation - Ensure there is no malicious content.

https - communication between clients and services should be encrypted.

monitoring and alerts - check for unusual activity patterns and trigger attacks for potential DDOS attacks or misuse

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?