System requirements

Functional:

-first api (POST): has a text box, after user enter a link then return a short link on screen.

-second api (GET): if the user enter the short link on browser, api return and redirect the original link

Non-Functional:

• Scalability: server can scale with high traffic (using Kubernete)
• Performance: should return data with minimal latency (consider using distributed server) (caching by Redis)
• Reliability: zero down time, no loss data (distributed server)
• Storage: can handle big data
• backup and recovery: should has back up and auto recover when there are server incident or natural disaster by using database replicated across regions.
• Maintainability: easy to maintain, implement some generic model like MVC, Clean architect
• Security: Basic requirement like Https, user authentication by Oauth2. Has rate limiting to avoid abuse or spam or DDOS.

Capacity estimation

Traffic Estimation:

• New URL Shortening Requests:
  • Let's assume we expect 500 million new URL shortening requests per month.
  • Queries per second (QPS) = 500 million / (30 days * 24 hours * 3600 seconds) ≈ 200 URLs/s
• Read/Write Ratio:
  • A typical read/write ratio for URL shorteners is around 100:1, meaning 100 redirections (reads) for every 1 new URL creation (write).
  • URL redirections per second ≈ 100 * 200 URLs/s = 20,000/s

Storage Estimation:

• Data Retention: Let's assume we want to store URL mappings for 5 years.
• Total URLs: Over 5 years, we'll store approximately 500 million * 12 months/year * 5 years = 30 billion URLs.
• Data per URL:
  • Long URL (average 100 characters) = 100 bytes
  • Short alias (7 characters) = 7 bytes
  • Metadata (timestamps, user ID, etc.) = 50 bytes (estimated)
  • Total per URL ≈ 157 bytes
• Total Storage: 30 billion URLs * 157 bytes/URL ≈ 4.71 TB
• Storage Growth: We need to account for annual growth in data storage needs. Let's assume a 20% annual growth rate.

Memory Estimation (for Caching):

• 80/20 Rule: Assume 20% of URLs generate 80% of the traffic.
• Cache Size: To cache the most frequently accessed URLs, we might need around 20% of 30 billion URLs * 157 bytes/URL ≈ 942 GB of memory.

Bandwidth Estimation:

• Ingress (incoming requests): 20,200 requests/s * 150 bytes/request (estimated) ≈ 3 MB/s
• Egress (outgoing responses): 20,000 redirections/s * 300 bytes/response (estimated) ≈ 6 MB/s

Key Considerations:

• Peak Traffic: These are average estimates. We need to consider peak traffic, which could be significantly higher (e.g., during special events or promotions).
• Growth: The system needs to be designed to scale to accommodate future growth in traffic and data storage.
• Database Choice: The choice of database (e.g., Redis, DynamoDB, Cassandra) will impact storage and performance considerations.

API design

Create short link

-URL: /shorten

-method: POST

-header:

.Authorization: Bearer

-body: {

originalLink: string

}

-Response:

+Success: status code 200

{

success: boolean,

alias: string

}

+Fail: Unauthorized => status code 401

+Fail: invalid url => {success: false, errorMessage: "invalid url"}

Get original link

-URL: /

-method: GET

-Response:

+success: return original link and redirect

+error:

.Not found => return a default page with not found error message

.Link expired => return to error page with expired error message

Additional url (Furture improvement)

-POST /custom/ => allow user to create custom alias

Database design

• Table 1: ShortURLs
  • id (Primary Key)
  • alias
  • original_url
  • created_at
  • expiration_date
  • access_count

• Table 2: User
  • user_id (Primary Key)
  • name
  • email
  • password
  • Created_at

High-level design

Client:

-A website that allow user to login, register

-Has a text box for user to pass their link and receive short url

Api gateway:

-Could use Kong to load balancing, authenticated for whole system

Server:

-Use to check if the url is exist or not then query the data from database or caching service

Database:

-Store the User and Short link data

Caching service:

-store the short link that already query by get method to reduce work load for the server

Cleaning service: use to clean up database or cache

Request flows

Consider sequence diagrams

Detailed component design

Client:

• Implement captcha to protect fraud and abuse
• have simple UI
• have 2 fields,
  • 1 for shorten an url and
  • 1 for user to create customize alias, this field is limited at 8 character.
    • user leave it empty => shorten url with our generated alias
    • user enter customized alias => create custom alias
    • user enter invalid customized alias => throw error message to user

API gateway:

• Rate limiting per IP (using exceptional backoff) address to protect the main service from abuse. 1 IP address should only perform maximum 1RPS. if user try to access more than limited, just return 503 unavailable to user
• Authenticate users with OAUTH2

Shorten service with some main functionality listed below:

• Shorten Alias: receive a long URL and then hashing with Using MD5 or SHA-256 (only alphabet and numeric character) and length 8 => make an unique alias present for that url.
• Collision handling: when collision detected, we can apply a couple of method below
  • Appending suffix counter: if alias is already existed, appending it with a counter like alias1, alias2 to avoid collision
  • Second method could be generate a new one for this url.
• Customize url: When user enter their customized alias. We check from database to check if it existed or not, it not, we will mapping that customized alias for the original link
• Scalability: use stateless design for service to easier to scale horizontally. Use kubernete for auto scaling to deal with high traffic in peak time. Furthurmore, we can use machine learning to build a model that can predict peak time to manually set scaling server 1 hour beforehand.
• Security and privacy:
  • Fraud detection: in API level, we will add some extra information from client side like IP address or unique ID present for client side to detect if one person can abuse our services by creating multiple accounts and create multiple sections.
  • Rate limiting per user to protect abuse when user can request from anonymous section with same user. When user request out of limited, return server code 503. User exceptional backoff algorithm to implement rate limiting.
  • Detect invalid url
    • URL has invalid format (eg: hiip://abc.com)
    • URL don't use https protocal (eg: http://test.vn)
    • URL in blacklist: could use third party to check if the url could contains malware or not
  • Blacklist: has blacklist feature to black all suspicious user or url that use to spam our service

Query Service:

• Manage original URL: receive short link (with alias) from client, check it with caching service first. If alias is existing, return the original link to the client. If alias is not existed, query the alias from database and return it to client
• Because the get shorten link flow don't required any authentication then its vulnerable for spaming or DDOS so we should split it into separate service
• Scalability: we can also deploy this query-service across multiple regions to improve the query (read) performance in high peaktime

Analytic Service:

• Datadog: observe system healthy with various of dashboad. Set alert for downtime or peaktime for both query service and shorten service
• Google analytic: analytic user interaction data

Caching service:

• using Redis to store alias and url as key-value pair or implement memory-cache with LRU algorithm to cache the alias-url.
• Redis support deploy as a cluster to scale horizontally. Redis also support data sharing replication to improve read performance

Cleaning service: work as a cron job to deactivate all expired url or inactive user. this cron job could run 1 or 2 a day. when the service found an expired link, it will remove the alias from caching service as well

Database:

• Should set up database replication across multiple regions avoid data loss or outstage
• Implement auto backup database schedulely

Trade offs/Tech choices

Client

-ReactJS: simple, fast development, large support community but performance is not the best

-Angular: Full-featured framework with everything included but its don't have good performance compare to the other

=> I will chose React js because this time we should aiming for fast development. We only need a simple UI so it pretty good enough

Server-Main Service:

-Node JS: simple, easy to develop, great concurrent handling but don't have good support for micro-service

-Azure Dotnet: Great supportive for micro-service but quick complicated for development and deployment

=> I will chose Node JS with the same reason i choose for Frontend side. Furthermore, both FE and BE use the same language can help team to easier to hire fullstack developer.

Database and Caching Service

-Relational database like PostgreSQL: have great performance, support indexing for fast query.

-No SQL database like MongoDB: high scale and performance, but its suitable for store document more than a simple string

-DynamoDB: highly scalable, fully managed but higher cost

-Redis: Great performance, simple, in-memory caching

=> I will chose Redis for my caching service solution and DynamoDB to store the data for better scaling performance

Microservice or monolith:

-Microservice: provide better scalability, suitable for complex system, flexibility but introduce complexity in development, deployment and harder to maintain

-Monolith: Simple, easier to learn and fast development, but harder to develop complex system.

=> I will choose Microservice for our current requirements to support better for scale in each service

Failure scenarios/bottlenecks

-Sever is down and cannot return the original link to the user: should use horizontal-scale server strategy like kubernetes to avoid zero downtime.

-Server over-flow in peak time: using auto scaling like kubernete and circle breaker t

-Database is down: should use database cluster or replica read data to avoid database down

-Hackers try to abuse our query service: we all ready implement various of rate limiting methods to protect it

-Some special peak time could overflow our server. For example, some company have chrismas event, propose their million of users click on a same link at a same time

Future improvements

-Adding analytic service to analyze user data

-Switch load balancer layer to API gateway for better management, rate limiting and authentication for api

-Split server layer to 2 separated services for shortening URL and Query URL for better scalability

-Chose better hash algorithm