txdat's notes

url shortener

3 min read

systemdesign.one

  • given a long url, create a shortened url (as short as possible) and redirect to original url: https://abc.xyz/... -> https://tinyUrl.com/{shortUrl}
    • 2 endpoints
      • [POST] /shorten -> shorten url
      • [GET] /{shortUrl} -> redirect shortened url to original url (status code 301)
        • code 301 (to GET), 308 (use original method) (permanent redirect): browser sends subsequent requests to original url servers directly instead of shortenUrl service
        • code 303 (to GET), 307 (use original method) (temporary redirect): browser keep sending subsequent requests to shortenUrl service first and redirect to original url servers
  • store in DB: {unique id, shortened url (hashed from unique id), original url}

solution

encoding (encode token to readable shortened url)

base62

  • convert number to base-62 representation. if length of shortened url is 7, it produces 62^7~3.5 trillion urls
  • pros:
    • collision is impossible (because id is unique)
  • cons:
    • length of shortened url is not fixed (increasing)
    • depends on unique id generator
    • can guess next available shortened url

write path (write long url to shortened url/token)

random id generator solution

  • stateless for scaling -> not use random id generator solution: higher of collision, and predictable due to overlapping bits

hash & collision

  • use well-known hash functions like CRC32, MD5, SHA-1, … and get X first characters
  • collision can be solved by append predefined string to original url and re-hash -> use bloom filter to improve performance when searching in DB
  • pros:
    • fixed shortened url length
    • doesn’t need a unique id generator
    • cannot find next available shortened url
  • cons:
    • may yield same prefix for urls, result in collision -> have to solve collision -> not use hash function

token range solution

  • token is generated by token service (from given token range - integer number range) and it is monotonically increasing

  • maximum range of token range depends on length of shortened url

    • eg. 7-length url with base62 -> 62^7 combinations -> range is [1…62

  • the output of token service must be non-overlapping to prevent collision -> token-range service: returns range of token to token service

  • use high quorum for key-value storage -> keep strong consistency to prevent collision -> collision-free and scalable

  • find shortened url of used long url

    • use bloom filter for data lookup on url shortening
    • use additional data storage (inverted index) to map long url -> shortened url. this additional storage is partitioned with consistent hashing

read path (read long url from shortened url and redirect)

  • use cache (cache-aside) to map shortened url to long url
  • use bloom filter to reduce load on cache and data storage (filter before query cache and storage), return 404 error if bloom filter returns not found
  • cache/data storage can be partitioned by shortened url (primary key) to improve availability (loader-followers pattern)
  • when shortened url is required in a short time, these requests may be collapsed and a single request will be forwarded to target server

concurrency

  • token service uses lock mechanism to prevent distribute same shortened url to distinct requests from key generation service (lead to collision)
  • all clients send a same long url to KGS at the same time must receive same shortened url
    • use message queue and group all duplicate requests (same long url?)
    • use reverse proxy (collapsed forwarding)
    • use distributed lock (acquired on long url) with TTL -> slight degradation of latency

Graph View