Requirements


Functional Requirements:


  • Create a short URL for a given long URL.
  • Return the long URL associated with a given short URL
  • The short URL cannot be updated



Non-Functional Requirements:


  • Low latency: Redis cache for frequently requested URLs
  • High availability:
    • one data center per region (US+South America, Europe, Asia)
    • Anycast on DNS routing to have geo locality
    • Each region has it's own DB (sharding) with replication
    • Shorten service is a layer with multiple instances - traffic distibuted per data center/region through LB and API Gateway
    • Stateless shorten service and Kubernetes to scale out when needed
  • Reliability
  • Short URL lenght should be minimum
  • Persistence: mapping should be available for 5 years
  • 1 000 000 new short URLs created per day



API Design

  • Request for Short URL creation: POST /api/v1/shorten
  • Request parameter: long URL
  • Response returned: short URL, http success code (200)


  • Request to access the long URL page: GET /api/v1/shortUrl
  • Response is HTTP redirect 301 (for easing load on servers) or 302 (for analytics and insights on marketing campaigns) and the long URL


High-Level Design

Geo routing based on DNS is the entry point to ensure each region is benefiting the low latency due to locality


Under each LB for each region there's a similar structure in place.


API GW layer takes care of typical concerns like SSL termination, user auth, rate limiting; it also splits writes and reads since system will be reads intensive; provides business analytics and operational monitoring and logging.


Whole system is stateless.


"Create short URL" request goes to ShortenService. Based on the chosen algorithm a short URL is created and stored in the Persistent Store (also added to the Redis cache with a default TTL of say 1 week - this depends on how much available resources goes into the in-memory component).


A DB synchronization service could be run in the background to make persistence store layer consistent accross all regions.



Detailed Component Design


API GW splits reads and writes. For reads API GW calls the Redis cache. If it's a hit it returns the short URL(potentially prolonging the TTL), if it's a miss it goes to ShortenService layer to fetch it form persistent store, serves it to the client and inserts it into the cache.


ShortenService layer generates the shortUrl value. If considering case-sensitive alpha-numeric values to build up the shortUrl string we can ensure unique values by generating unique ID for each new long URL and do a base 62 (0-9a-zA-Z) conversion. This way we ensue uniqueness and avoid possible hash space collisions (could arise if we would hash the long URL).

Before creating a short URL Shorten service checks to see if the longURL is already in the DB -> can use Bloom filter for speed.


IDgeneration is a layer that generates the unique IDs using a hash ring on which all regions are distributed.