URL Shortening Service

Summary

Requirements

• Functional Requirements
  • Given a URL, generate a shorter and unique alias (short link).
  • When users access a short link, redirect to the original link.
  • Users should optionally be able to pick a custom short link for their URL.
  • Links will expire after a standard default timespan. Users should also be able to specify the expiration time.
• Non-Functional Requirements
  • The system should be highly available. This is required because, if our service is down, all the URL redirections will start failing.
  • URL redirection should happen in real-time with minimal latency.
  • Shortened links should not be guessable (not predictable).
• Extended Requirements
  • Analytics; e.g., how many times a redirection happened?
  • Be accessible through REST APIs by other services.

Capacity Estimation and Constraints

• Assumption
  • Read-heavy. More redirection requests compared to new URL shortenings.
  • Assume 100:1 ratio between read and write.
• Traffic estimates
  • 500M new URL shortenings per month, 100 * 500M => 50B redirections per month.
  • New URL shortenings per second
    • 500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s
  • URLs redirections per second
    • 50 billion / (30 days * 24 hours * 3600 sec) = ~19K/s
• Storage estimates
  • Assume storing every URL shortening request for 5 years, each object takes 500 bytes
  • Total objects: 500 million * 5 years * 12 months = 30 billion
  • Total storage: 30 billion * 500 bytes = 15 TB
• Bandwidth estimates
  • Write: 200 URL/s * 500 bytes/URL = 100 KB/s
  • Read: 19K URL/s * 500 bytes/URL = ~9 MB/s
• Cache memory estimates
  • Follow the 80-20 rule, assuming 20% of URLs generate 80% of traffic, cache 20% hot URLs
  • Requests per day: 19K * 3600 seconds * 24 hours = ~1.7 billion/day
  • Cache 20%: 0.2 * 1.7 billion * 500 bytes = ~170GB
• Summary
  • Assuming 500 million new URLs per month and 100:1 read:write ratio

  Category	Calculation	Estimate
  New URLs	500 million / (30 days * 24 hours * 3600 seconds)	200 /s
  URL redirections	500 million * 100 / (30 days * 24 hours * 3600 seconds)	19 K/s
  Incoming data	500 bytes/URL * 200 URL/s	100 KB/s
  Outgoing data	500 bytes/URL * 19K URL/s	9 MB/s
  Storage for 5 years	500 bytes/URL * 500 million * 60 months	15 TB
  Memory for cache	19K URL * 3600 seconds * 24 hours * 500 bytes * 20%	170 GB

System APIs

createUrl

• Parameters Name | Type | Note —- | —- | —- api_dev_key | string | The API developer key of a registered account. This will be used to, among other things, throttle users based on their allocated quota. original_url | string | Original URL to be shortened. custom_alias | string | Optional custom key for the URL. user_name | string | Optional user name to be used in encoding. expire_date | string | Optional expiration date for the shortened URL.
• Return
  • string
  • A successful insertion returns the shortened URL; otherwise, it returns an error code.

deleteUrl

• Parameters Name | Type | Note —- | —- | —- api_dev_key | string | The API developer key of a registered account. This will be used to, among other things, throttle users based on their allocated quota. url_key | string | Short URL.
• Return
  • string
  • A successful deletion returns ‘URL Removed’.

Database design

• Observations
  • Need to store billions of records.
  • Each object is small (less than 1K).
  • No relationships between records—other than storing which user created a URL.
  • Read-heavy.
  • A NoSQL choice would also be easier to scale.
  • Comment: SQL with sharding should also work
• Schema
  • URL Column | Type —- | —- hash | varchar(16) original_url | varchar(512) creation_date | datetime expiration_date | datetime user_id | int
  • User Column | Type —- | —- name | varchar(20) email | varchar(32) creation_date | datetime last_login | datetime

Basic System Design and Algorithm

Encoding actual URL

• Compute unique hash
  • base64: A-Z, a-z, 0-9, -, .
  • 6 letters: 64 ^ 6 = ~68.7 billion
  • 8 letters: 64 ^ 8 = ~281 trillion
  • Use 6 letters
  • MD5 generates 128 bit hash value
  • Each base64 character encodes 6 bits
  • base64 encoding generates 22 characters
  • Select 8 characters
• Issues with this approach
  • Same URL from multiple users
  • URL-encoded
• Workaround
  • Append an increasing sequence number to each input URL, and generate a hash for it
  • Append user id to input URL

Generating keys offline

• Standalone Key Generation Service (KGS)
  • Generate random 6 letter strings and store them in a database (key DB)
  • When a short URL is needed, take one from the key DB
• Key DB size
  • 6 characters/key * 68.7B unique keys = 412 GB
• Concurrency issue
  • If there are multiple servers reading keys concurrently, two or more servers try to read the same key from the database.
• Workaround
  • Servers can use KGS to read/mark keys in the database.
  • KGS can use two tables to store keys: one for keys that are not used yet, and one for all the used keys.
  • KGS can always keep some keys in memory so that it can quickly provide them whenever a server needs them.
  • KGS needs to make sure not to give the same key to multiple servers.
  • Comment: keys are sharded. Each KGS server only serves one application server.
• Key lookup
  • When a key is found, issue an “HTTP 302 Redirect” status and passing the stored URL.
  • When a key is not found, issue an “HTTP 404 Not Found”, or redirect to homepage.

UUID

Replace KGS with UUID.

Data Partitioning and Replication

• Range Based Partitioning
  • Store URLs in separate partitions based on the first letter of the URL or the hash key.
  • Combine certain less frequently occurring letters into one database partition.
• Problem with this approach
  • Unbalanced servers.
• Hash-Based Partitioning
  • Take a hash of the short URL we are storing, and calculate which partition to use based upon the hash.
  • Use consistent hashing

Cache

• Eviction policy
  • LRU: discard the least recently used URL first
• Cache update
  • Cache miss: hit backend database and pass new entry to all cache replicas

Load Balancer (LB)

• LB locations
  • Between Clients and Application servers
  • Between Application Servers and database servers
  • Between Application Servers and Cache servers

DB Sweeping

A separate Cleanup service can run periodically to remove expired links from our storage and cache.

Telemetry

Statistics about the system: how many times a short URL has been used

Security and Permissions

• Store permission level (public/private) with each URL in the database
• Send an error (HTTP 401) for unauthorized access