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
2. Scalability
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 * (200 Byte) = 6.3 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 Byte)

createTime (10 Byte)

url

short_url(50Byte) Primary Key

user_id(20Byte) Secondary index

original_url(200 Byte)

creation_time(10 Byte) Secondary index

expiry_time(10 Byte) SecondaryKey

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...

• 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

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...

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.

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

Future improvements

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.