Requirement


Functional:

  • RedirectUrl (shortUrl -> originalUrl)
  • ShortenedUrl (LongUrl -> shortUrl)
  • (optional) analytics purpose (most viewed url)


Non-Funcational:

  • Availability : MTTR with 99% high availability that means our service have some SLA that only has downtime about 3 days/year. Do some horizontal scaling for handle high volume traffic
  • Performance : P90 must be < 5ms, this is important for user to get the desired url as fast as they go to the original url.
  • Security : Rate limiter, sanity check for harmful URL


API Design


Data Types:

  • Url table: id, user_id, long_url, short_url
  • User table: id, username, hashedPassword, salt, email
  • (optional) Analytic: id, url_id, total_viewed, last_viewed


API:

  • POST: /shorten
    • Request
      • (string) longUrl
    • Response
      • (string) shortUrl
  • GET: /view/{shortUrl}
    • Request
      • (string) shortUrl
    • Response
      • 301 -> redirect to original URL and cached in the browser to reduce call api to our services
      • (optional) 302 -> need it for analytics

Calculation:

  • LongUrl : 100B
  • ShortUrl : 8B
  • Total: 100 * 8 = 800 B / entry or single shortened url process
  • Expect store more than 10 million urls = 800B * 10 * 10^6 = 48000 * 10^6 bytes or roughly 48GB


High-Level Design


  • Client (registered or public) that access our url
  • API Gateway, act as gateway between client and our services. It also handle for security purposes like handle ddos by rate limiter and also distribute the load between each server via load balancer.
  • User service, service that purposes for login and register user
  • Shortened service, purposes for convert original url to the shortened one via some hashing logic to make it concise and handle duplicate.
    • Hashing logic: it will be generate long url into alphanumberic lower and uppercase based on sequence on the userId (sequence) + long Url
    • Duplicate logic: it will check first in the DB does the generated already there. if yes it will regerenate again with differen UrlId
    • It also can remove the shortened url in the db and cache
  • Redirect service, handle public client request to mapping shortenedUrl to the original one.
  • SQL DB, as mentioned before in the API Design, we have seom relational schema. So it will have several table like : User, Url, Analytic (optional)
  • InMem DB, it act for rate limiter purposes and to decreased the latency of the services by caching heavy read (shortUrl, longUrl) from Url table in SQL into in mem DB. Invalidate cache will be going by TTL or requested by the User


Detailed Component Design


API Endpoint:

  • shorteningUrl will take a long URL and return the short URL
  • redirectUrl will take a short URL and return the original URL


User Service:

  • purposed to handle the login logic, it will check in the db does the user is exist in DB, and will check does the password is equal.
  • Additionally it also can remove/delete the generated url in the db


Shortened Service:

  • It will take a long url and then will generate the shortened one
  • the logic is involved several process
    • hashing -> convert long url with sha256 -> base62
    • collision handling -> if the generated url is exist, we will retry the process by adding a random salt (8 long) in the long url before sha256. If the collision happen, it will retry again with different salt. After 10 retry we will return 500 internal server error
    • saving to db -> it will save the unique shortened url into db first and then will save it into in memory db with some TTL (let say 1 year)
    • after that we will return response to the gateway with property shortenedUrl and its expiration time


Redirect Service:

  • It will redirect user into original url
  • First one it will fetch into the cache for fast lookup, if missing check DB and if missing it will return 404 not found to the user. If exist it will return 301 to the user with the original url value in the location header. Why 301, we will use browser cache to minimize api call to our service. In here we're not implement the analytic feature


Trade-Off:

  • Based on the explanation, we will use 2 types of DB (sql and in-mem)
    • SQL is fit with our requirement that need consistency. However if the user grows up, we will have problem at scaling because the cost will much higher (we only can do vertical scale). One thing maybe that we can do is using some sharding to distributed the data with the sacrifice of the more complext system. To make it high availability, it will has master/slave db so it can delegate the master to the next master candidate if the primary is down
    • in-mem db used to make low latency and fast lookup. The downside is we have tto make appropriate cache invalidation to make it efficient (not consume more memory). This db will have slave/master to mitigate if the master is down