System requirements

Functional:

1. Short URL generation: Users input long URL, the system could generate unique short URL
2. Redirection: when user input the short URL in the browser, the system could redirect it to the long URL
3. Expiry Time: The relationship should be have a expiration time
4. Deletion: user could delete the short URL; after the deletion, user could not redirect to the long URL by using the short one
5. (optional) user sign in
6. (optional) custom short links
7. (optional) data analysis

Non-Functional:

1. Availability, the servise has to be highly available. Especially for rediraction
2. Scalability, we will get more and more requests to create short URLs, so the storage has to be highly scalable
3. Low latency, especially for the redirect and generate

Capacity estimation

Q: How many URLs are generated per second? 200

Storage: 200 * 60 * 60 * 24 * 365 * 5 * (300 Byte) = 9.5 TB

Q: How many URLs are redirected per second?

20,000

Query rate: 20,000 URLs / s

Bandwidth:

shorten: 200 * 200Byte * 8 bits = 320 Kbps

redirect: 20000 * 200Byte * 8bits =32 Mbps

Cache Memory: cache 20% daily

20000 * 60 * 60 * 24 * (200 Byte) * 20% = 69 GB

Servers needed at peak load

20000 * 5000 / 64000 RPS = 1562 servers

API design

• Request: shortenURL(api_dev_key, original_url, expiry_date=None)

Response: short_url

• Request: redirectURL(short_url, expiry_date)

Response: original_url

• Request: deleteURL(api_dev_key, short_url)
• Response: system message: url delete successful

Database design

Store

1. User detail
2. map of short_url and original_url

MongoDB

1. NoSQL
2. follow lead-followers protocol; read-heavily
3. ensure atomicity in concurrent write operations

User

userId (20 byte) Primary Key

user_name (20 bytes)

createTime (10 Byte)

every row is 50 byte

url

short_url (50 bytes) Primary Key

user_id (20 bytes) Secondary index

original_url (200 bytes)

creation_time (10 bytes) Secondary index

expiry_time (10 bytes) SecondaryKey

every row is 300 byte

High-level design

flowchart TD C[client] --shortenURL(), redirectURL()--> API[API Gateway] API --shortenURL()--> SHORT[Shortening Service] C --redirectURL()-->CDN[CDN] API-->Map[Mapping Service] SHORT --> MQ[Message Queue] QW[Queue Worker] --> MQ QW --> Cache[Cache] QW --> DB[Database] Map --> Cache Map --> DB

Request flows

shortenURL() API:

Client sends the request. API Gateway forwards it to Shortening Service. It creates the short URL -> long URL mapping and store it in the database.

redirectURL() API:

Client sends the request. If the mapping is found in a regional, nearby CDN, it is returned from the CDN. Otherwise, the request reaches API Gateway and the Mapping Service. It checks if the mapping exists in Redis Cache. If it does, the mapping is returned. If not, it reads the Database.

• shorten:
  1. Client Request: The client sends a POST request with the long URL to the system through the API Gateway.
  2. Authentication: The API Gateway checks authentication and rate limits via the AuthService.
  3. Forward to ShortenURLServer: If the request passes, it is forwarded to the Shorten URL server.
  4. Cache Lookup: The Shorten URL server first checks cache for the existence of the long URL.
  5. Database Check:
     • If the cache misses, it checks the database.
     • If the long URL is found in the database, it returns the existing short URL.
     • If the long URL does not exist, it proceeds to the new creation flow.
  6. Short URL Generation: A new short URL is generated by the URLGenerator component.
  7. Storage: The new mapping of long URL to short URL is stored in the database. Optionally, it can also be cached.
  8. Response: The short URL (either pre-existing or newly created) is returned to the client.

sequenceDiagram

participant Client

participant APIGateway

participant AuthService

participant ShortenURLServer

participant Cache

participant Database

participant URLGenerator

Client->>APIGateway: POST {long_url}

APIGateway->>AuthService: Check Auth

AuthService-->>APIGateway: Auth Success

APIGateway->>ShortenURLServer: Forward Request

ShortenURLServer->>Cache: Check Cache for {long_url}

Cache-->>ShortenURLServer: Miss (No Result)

ShortenURLServer->>Database: Check Database for {long_url}

alt Long URL exists

Database-->>ShortenURLServer: Found {short_url}

ShortenURLServer-->>Client: Return {short_url}

else Long URL does not exist

Database-->>ShortenURLServer: Not Found

ShortenURLServer->>URLGenerator: Generate new {short_url}

URLGenerator-->>ShortenURLServer: New {short_url}

ShortenURLServer->>Database: Store {long_url, short_url}

ShortenURLServer->>Cache: Optionally Cache {long_url, short_url}

ShortenURLServer-->>Client: Return new {short_url}

end

• delete
  1. Client Request: The client sends a POST request with the short URL to the system through the API Gateway.
  2. Authentication: The API Gateway checks authentication and rate limits via the AuthService, like OAuth.
  3. Forward to DeleteURLServer: If the request passes, it is forwarded to the Delete URL server.
  4. Database Check:
     • If the short URL is not found in the database, return 404 not found
     • If the short URL is found in the database, delete it or set it as deleted
  5. Cache change: Set all corresponding cache invalid
  6. Response: Sending a system message that delete success and returned to the client.
  7. sequenceDiagram participant Client participant APIGateway participant AuthService participant DeleteURLServer participant Cache participant Database Client->>APIGateway: POST {short_url} APIGateway->>AuthService: Check Auth (OAuth) AuthService-->>APIGateway: Auth Success APIGateway->>DeleteURLServer: Forward Request DeleteURLServer->>Database: Check Database for {short_url} alt Short URL not found Database-->>DeleteURLServer: Not Found DeleteURLServer-->>Client: Return 404 Not Found else Short URL found Database-->>DeleteURLServer: Found and Deleted DeleteURLServer->>Cache: Invalidate {short_url} DeleteURLServer-->>Client: Return Delete Success Message end

• redirect
  1. Client Request: The client sends a GET request with a short URL to the system through the API Gateway.
  2. Authentication: The API Gateway checks authentication and rate limits via the AuthService like OAuth.
  3. Forward to RedirectURLServer: If the request passes, it is forwarded to the Redirect URL server.
  4. Cache Lookup: The Redirect URL server first checks cache for the short url, if it exist, and not expire/delete, return 301 redirect to the original url, if it is not exist, return 404/410
  5. Database Check:
     • If the cache misses, it checks the database.
     • If the long URL is found in the database, it returns the existing short URL.
     • If the long URL does not exist, it proceeds to the new creation flow.
  6. Short URL Generation: A new short URL is generated by the URLGenerator component.
  7. Storage: The new mapping of long URL to short URL is stored in the database. Optionally, it can also be cached.
  8. Response: The short URL (either pre-existing or newly created) is returned to the client.

sequenceDiagram participant Client participant APIGateway participant AuthService participant RedirectURLServer participant Cache participant Database participant URLGenerator Client->>APIGateway: GET {short_url} APIGateway->>AuthService: Check Auth (OAuth) AuthService-->>APIGateway: Auth Success APIGateway->>RedirectURLServer: Forward Request RedirectURLServer->>Cache: Check Cache for {short_url} alt Short URL in Cache and Valid Cache-->>RedirectURLServer: Found and Valid RedirectURLServer-->>Client: Return 301 Redirect to Original URL else Short URL not in Cache or Expired/Deleted Cache-->>RedirectURLServer: Not Found RedirectURLServer->>Database: Check Database for {short_url} alt Short URL in Database Database-->>RedirectURLServer: Found RedirectURLServer-->>Client: Return 301 Redirect to Original URL RedirectURLServer->>Cache: Optionally Cache {short_url} else Short URL not in Database Database-->>RedirectURLServer: Not Found RedirectURLServer->>URLGenerator: Generate new {short_url} URLGenerator-->>RedirectURLServer: New {short_url} RedirectURLServer->>Database: Store {long_url, short_url} RedirectURLServer->>Cache: Optionally Cache new {short_url} RedirectURLServer-->>Client: Return New {short_url} end end

Detailed component design

Caching

[Mid-level deep dive topic]

Performance and scalability of redirectURL() API is extremely important for this system. As such, we employ two levels of caching. Requests will naturally have locality of access, so caching will be effective.

At the closest location from the clients, we will have CDN storing short -> long mappings for the most frequently requested URLs. For example, if a celebrity posts a short URL link in their Social Network post, this mapping should be in CDN. CDN can be hosted at Internet Exchange Points (IXPs), making the response time from client quite short. It has limited storage space, so it should store a small set of the most frequently accessed mappings. High volume of requests are handled by CDN, without even reaching the API Gateway. It is quite beneficial from scalability & fault tolerance perspective.

In the data center, we will employ a caching node, e.g., Redis. As we can install multiple Redis nodes with 100s of GBs of memory, it can store larger set of mappings. It is still faster than accessing the database, so this would provide performance and scalability gain.

Both CDN and Redis Cache can employ Least Recently Used eviction algorithm to ensure currently popular mappings stay in cache.

Partitioning

[Mid-level deep dive topic]

Database and Cache should be partitioned for improved scalability.

Short URL is a good choice for a partitioning key because:

• The services primarily look up cache & Database by short URL. By having this as the partitioning key, the services can find the right Cache & Database node to access quickly.
• It is randomly generated, so it would be evenly distributed across nodes.

Other partitioning keys (long URL, user ID) would have disadvantages about these points.

Trade offs/Tech choices

Database: MongoDB, because the system is read heavily and the data is unstructured. atomatically when write.

Message queue like Kafka for the invalidate cache, because the async protocol and eventual consistency.

Short URL generation

[Junior-level deep dive topic]

There are two ways to create a short URL:

1. Hash (e.g. MD5, SHA2) the long URL.
2. Randomly generate it.

There is a tradeoff:

Pro of Hash approach is that you don't have to generate random numbers. Con is that the created hashes might collide. In particular, since our random string (8 characters) will be shorter than what the hash algorithms generate (20 bytes or larger), the risk of collision would increase.

Pro of random generation is the possibility of collision is lower. If a newly created random string collides with an already existing one, we can simply generate one more random string. Con is that it would require computational power to generate random numbers. However, since Linux and other OSes support fast random number generation with /dev/urandom, we assume the cost is manageable.

We will pick random generation in this exercise.

Failure scenarios/bottlenecks

1. Too many shorten url requests
2. Too many redirect url requests
3. The number of the data almost get the database limit
4. latency

we can add read limiter to limit the number of requests for the short-term reduce the query

and add cache for all levels, local, DNS, webserver, apiserver, database to avoid the database hit and improve the latency.

For the long term, we can add more server, use the database sharding and database geologically distribute to improve the database query efficiency.

Future improvements

supporting custom URL