System requirements

Functional:

• web service with user service and redirection service
• user service - create new user, user login, allows users to submit (write) long urls and receive corresponding short url.
• shortening service - generates unique short code and stores the mapping between the short code and URL. Short code will be 8 1-byte characters. It will be produced using MD5 hash (retry on collision).
• redirection service - redirects the user from the shortened url to the original long url. Response code 302 if found, 404 otherwise.
• analytics service (optional) tracks usage metrics

Non-Functional:

• horizontally scalable - loadbalanced microservice architecture to easily increase capacity along with increased future traffic
• high availability
• https

Capacity estimation

• 1 million current active daily users
• average of 100 shortened urls created per user per day
• expected total urls = 100 million per day
• daily growth rate of 1% - 10000 new users per day
• long url size limit is 2083 characters
• user-db capacity estimation: (|user_id| + |user_password_hash|) * 100 million ~=
• url-db capacity estimation: (|short_url_id| + |create_user_id| + |short_url| + |long_url|) * 100 million ~= 2100B * 100000000=210000000000B=210GB

API design

• REST API - returns JSON payload
• user-service
• /login
• POST request with username and password in authorization header (base 64 encoded)
• Returns login token and 200 OK on success (user exists and correct password)
• Returns 401 Unauthorized if invalid login credentials
• /create-user
• PUT request with username and password in authorization header (base 64 encoded)
• Returns 200 OK on success (new user)
• Returns 400 Bad Request on error (e.g. user already exists)
• /create-short-url?url=<long url>
• PUT request with long url as request parameter
• Returns 200 OK and the shortened url on success
• Returns 401 Unauthorized if not logged in
• Returns 400 Bad Request on error (e.g. invalid/duplicate url)
• redirect-service
• /redirect?short-url=<short url>
• GET request with short url as request parameter
• Returns 301 Moved Permanently with original url on success
• Returns 404 Not Found if the short url was not found
• Returns 400 Bad Request on error

Database design

• user-db
• user <user_id VARCHAR(255), user_password_hash CHAR(8), create_date TIMESTAMP, last_login_date TIMESTAMP>
• url-db
• short_url <short_url CHAR(8), create_user_id VARCHAR(255), long_url VARCHAR(2083)>

High-level design

flowchart TD

    user[user] --> reverse-proxy[reverse-proxy]

    reverse-proxy --> user-service-lb{load-balancer}

    reverse-proxy --> redirect-service-lb{load-balancer}

    user-service-lb --> user-service[user-service] <--> user-db[(user-db)]

    user-service --> shortening-service[shortening-service]

    redirect-service-lb --> redirect-service[redirect-service]

    shortening-service --> url-db-master[(url-db-master)]

    redirect-service <--> redirect-cache[redirect-cache]

    redirect-service <--> url-db-replica[(url-db-replica)]

    url-db-master --> url-db-replica

Request flows

1. Create User
2. Reverse proxy sends request to user service load balancer
3. User service load balancer sends request to user service (round robin)
4. User service writes the user to the user-db.
5. User login
6. Reverse proxy sends request to user service load balancer
7. User service load balancer sends request to user service (round robin)
8. User service checks provided credentials against values in db and, on successful authentication, provides authentication token
9. Create short url
10. Reverse proxy sends request to user service load balancer
11. User service load balancer sends request to user service (round robin)
12. Check user login token
13. Generate new short url from long url
14. Write short url record to url master database
15. Url master database updates the url read replica database with the new record
16. Redirect url
17. Reverse proxy sends request to redirect service load balancer
18. Redirect service load balancer sends request to redirect service
19. Check the cache for the short url.
20. If the cache contains the short url and is within TTL, return the long url.
21. If the cache does not contain the short url (cache miss), retrieve the value from the url db (replica) and update the cache.

Detailed component design

• User-service: 1+ servers behind load-balancer, web service (e.g., implemented via Java Spring API) for handling requests.
• User-db: RDBMS (e.g., db2, postgresql)
• Shortening-service: 1+ servers behind load-balancer, web service (e.g., implemented via Java Spring API) creates shortened url by hashing (e.g. MD5 checksum) the long url, ensuring its uniqueness in url-db-master, then writing the value.
• Redirect-service: 1+ servers behind load-balancer, web service (e.g., implemented via Java Spring API) that checks cache for provided short url. If the cache contains the value and is within TTL, return the long url. Otherwise, retrieve the long url from one of the url read replica dbs and update the cache with the retrieved value.

Trade offs/Tech choices

• Lazy cache that relies on TTL has a risk wherein if the long url was updated BEFORE TTL expiration, then the long url would be out of date.
• Use of load-balancers to ensure future-scalability.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?