System requirements

Functional:

1. Create a Short URL: Given a long URL, the service should generate a short URL that redirects to the original one.
2. Redirect Short URL: When provided with a short URL, the service should redirect the user to the original long URL.
3. Custom Alias support: Users would be able to define an Alias for short URLs.
4. Timestamp: Short URLs would have an specific time to work.
5. Analytics: Gathers data about hits and analytics to understand the traffic patterns.

Non-Functional:

1. Reliability: The service must ensure that redirections are reliably correct, meaning any short URL consistently redirects to its associated long URL without failure.
2. Low Latency: Redirections must be fast, ideally with a response time of less than 10 milliseconds for optimal user experience.
3. High Availability: The service must be highly available, ensuring that even in the event of some component failures, the system can continue to function, especially for redirecting short URLs.
4. Scalability: Data would increase rapidly, so it is a good idea to have an appropriate DB to not have performance issues.
5. Security: URLs must not be guessable.

Capacity estimation

Storage Estimation

1. Data Stored per URL Mapping: Assume each URL mapping stores the following information:
   • Long URL: Approximately 100 characters.
   • Short URL: Typically 8 characters.
   • Metadata (e.g., created time, user ID, expiration time): Approximately 36 bytes.
2. Total storage per entry can be estimated as about 144 bytes. To simplify calculations, let's round this up to 256 bytes for additional metadata or padding.
3. Daily Storage:
   • Assuming 1 million URL creations per day:
4. [ 1,000,000 URL/day x 256 bytes/URL = 256 MB/day ]
5. Yearly Storage:
   • Over one year, this equates to approximately:
6. [ 256 MB/day x 365 days/year = 93.44 GB/year ]
7. With a 10x traffic spike, let's plan for:
8. [ 93.44 GB/year x 10 = 934.4 GB/year ]

1,000,000 * 365 URLs to short per year = 365,000,000 urls

Bandwidth Estimation

1. Redirection Requests: The bulk of the bandwidth usage comes from redirection requests.
   • If each redirection involves roughly a 1KB request/response (including headers and actual URL data), and with 20 million redirections per day:
2. [ 20,000,000 redirects/day x 1 KB/request = 20 GB/day ]
3. Yearly Bandwidth:
   • Over one year, bandwidth would be:
4. [ 20 GB/day x 365 days/year = 7,300 GB/year = 7.3 TB/year ]
5. Considering a 10x traffic spike:
6. [ 7.3 TB/year x 10 = 73 TB/year ]

API design

• POST: /shorten_url
  • api_key: (string) to protect from spammers, access, and resource control for users
  • original_url: (string)
  • expiration_time: (datetime) it is optional to specify it
  • personalized_url: (string) it is optional to specify it
• GET: /redirect/{short_url}
  • short_url: the one generated earlier

Database design

• USER:
  • user_id
  • email
  • PRIMARY_KEY(id)
• URLs:
  • id:
  • user.id: as Foreign Key to know who created this url
  • original URL:
  • shorten URL:
  • expiration_time:
  • PRIMARY_KEY(id)

High-level design

1. API Gateway:
   • Serves as the initial entry point for all incoming requests, handling tasks like routing, security, and rate limiting.
2. Shortening Service:
   • Responsible for generating short URLs from long URLs.
   • Interacts directly with the database to store URL mappings.
3. Redirect Service:
   • Handles redirect requests by resolving short URLs back to their corresponding long URLs.
   • Utilizes caching for fast lookups, improving performance.
4. Database:
   • Stores mappings between short URLs and long URLs, along with metadata such as creation time and expiration.
5. Cache:
   • Holds frequently accessed URL mappings to reduce database load and latency for redirect requests.
   • Uses Redis: There are a few advantages over Memcached:
     • It is possible to have consistency due to Snapshotting or Append Only File.
     • Also could be used for Analytics as future improvement.
6. Message queue:
   1. Could be used for incoming requests to shorting a URL.
7. MQ worker:
   1. Kafka: due to analytics
   2. Shorts the URL
   3. Updates the DB with the new short URL and necessary info
   4. Updates the cache for future requests.
8. CDN:
   1. API Gateway first will will in the CDN to see if has cached the requested short URL.

Request flows

• Shortening Service:
  • User sends a request to create a short URL via API Gateway
  • API Gateway routes the request to the shortening service
  • shortening service puts the request in the message queue
  • then message queue worker takes a request from the queue and creates a short URL, stores in the DB, and updates the Cache
  • Then responds with the created short URL to the user
• Redirect service:
  • User access with the short url, which hits the API gateway
  • Api gateway first looks up for it in the CDN
  • If not in CDN, API gateway routes the request to the redirect service
  • The redirect service checks for it in the cache
  • If not in cache, retrieves the full URL from the database and updates the cache, then performs the redirection.

Detailed component design

• CDN:
  • I selected CDN because of geographically could have the most visited URLs per regions.
• MQ Worker:
  • If we hash using MD5 and then encoding it in base62 (a-z, A-Z, 0-9),
  • then taking the first 8 characters we could have upto 8^62 options, so we could have a good space to avoid collisions because we expect 365,000,000 short urls per year.

Trade offs/Tech choices

• Redis over memcached:
  • Redis is more complex than memcached but I selected because there are a few advantages like:
    • possible consistency when the system crashes
    • could help us for Analytics as future improvement
• Kafka over rabbitMQ:
  • kafka is more complex in operations but it is configurable for message persistence and efficient in reads and writes

Failure scenarios/bottlenecks

• If there are collisions when generating short URLs

Future improvements

• Analytics for redirections