System requirements

Functional:

• generate a unique tiny-url from long url
• get the original long-url from the tiny url
• 2 persons sharing same long-url should get different tiny url

Non-Functional:

• tiny url should be unique
• it should be highly available
• it should have low latency
• the tiny url life will be of 5 years
• the operation would be read heavy
• If same user gives same long url again, it should return same short url.
• short-url is of fixed length

Capacity estimation

• Lets assume the read/write ratio as 10:1.
• assume that we are getting around 1e6 read requests per day, which gives around 11TPS read call-volume
• since read/write ratio is 10:1, write volume is 1 TPS

API design

Define what APIs are expected from the system...

• Request-type1(write call): POST generateShortUrl(userId, <api_key>, long_url)
  • request-params:
    • userId:- unique user-id for each user.
    • <api_key>:- apiKey is used to manager authZ, throttling where we can use rate-burst kind of algorithm to throttle based upon the apiKey.
  • response: { short-url: "short-url", expiry_date: "timestamp"}
    • response-params:-
      • short-url-> generated short url
      • expiry_date-> epoch time-stamp for the expiration date of the current short-url.

• Request-type2(read-call): Get redirectToLongUrl(userId, <api_key>, short_url)
  • request-params:
    • userId-> same as explained above
    • <api_key>-> same as explained above
    • short_url-> corresponding short url
  • response: {long_url: ""}
    • long_url: original long url

Database design

• We would need following Tabes:
  • User-Details(user-id, user-meta-information)
  • short_to_long_url(short-url(index-key), long-url, expiry-date, isActive)
  • url_mapper(user-id(partition-key), long-url(sort-key), short-url)
• I follow following parameters to decide b/w sql vs. no-sql:
  • data is some-what structured
  • don't want tables to be highly coupled
  • no need to support ACID properties
  • Queries on the table would be simple and not complex
• As the data volume would be large and we want to avoid the running joins between the tables, it is preferred to use a key-value pair

High-level design

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

• Client: make a generateShortUrl call with user_id, api-key and long_url as reqeust params
  • Once the request is authn/authz and passed throttling(we could use rate-burst algo) on api-gateway(it acts as a reverse-proxy server for us)
  • Api-gateway will make call to key-provider service to provide the short-url for the user-id, long_url pair.
  • App-cache: it will have the caching schemas as:
    • {<userid, long_url>, <short_url, expiry>}, using <expiry> we can leverage cache-invalidation in outlier cases. For general case, to optimize on cache-size, we can follow TTL based caching
    • {short_url, long_url}: we will have either TTL based caching here as our TTL is in minutes, and it doesn't matter if we allow a url to be available for 5 more minutes as our expiry is 5 years. We can live with that..
  • KPS will first of all check the value existence in url_mapper table,
    • if it is there and isActive flag is true for it.
      • it will return from there.
      • it will update the app-cache for the cache-key (<user_id, long_url>, <short_url>)
    • if it isn't there or isActive flag is false
      • it will ask key-generator service to provide an unique unused short-key from its store
      • it will update its url_mapper, short_to_long_url and app-cache
  • KGS: it can use base64 encoding to have a fixed length short-key stored. the short-key of length 6 would be supporting 1e10 unique combinations for <userid, longURL> which should suffice our use-case(as our write tps is 1, and we are keeping default expiry of around 5 years, we would be practically handling around: 1e9 unique combination, and our system supports 10 times of that which should be fine.
    • Internally, it maintains 2 DDBs, used keys and unused-keys.
    • When a getCalls lands upon KGS, it moves record from unused-keys-ddb to used-keys-ddb.
    • To avoid two <user-id, long_url> combinations using the same unused-key, it creates a transaction by marking a particular key as isAvailable=false and then returning it to the KPS service(thus leveraging conditional-check facility and consistent-read:true property to avoid race condition for 2 concurrent reads)
    • After marking an entry in unused-keys-ddb as un-available, it fires an async job to move this key from unused-keys-ddb list to used-keys-ddb.
    • Why didn't perform the above row-move task as part of transaction as it involves 2 write operations where as marking a flag isAvailable involves only single write operation.

Detailed component design

discussed above..

Trade offs/Tech choices

discussed above..

Failure scenarios/bottlenecks

We will be having multiple replicas of KPS, we can use AWS-APiGateway, which can acts as LB for us as well.. we added cache before KPS to handle the scalibility, we could also add cache-layer b/w KPS and KGS, to have small set of unused short-urls pre-picked. If this cache goes down, we should be fine as the amount of unused-short-urls lost is very low as compared to what is available in unused-keys-ddb..

Future improvements

Our services interacts interally via means of Grpc clients with exponential back-off retry strategy in place..

We could have a few customer-imitating user-ids available which would fire get/set calls and validate the outputs. These imitators we could use to create auto-cut tickets in case of any failure.

We will be emitting faults/error/P90 latency spike metrics and will have graphs/dashboards built over these(with alarm thresholds set) to pre-emptly catch any failure/fault/error.