System requirements

Functional:

• Given a Url return the Shortened Url
• Given a Shortened Url Redirect to the Original Url
• Immutable. Unique url, one to one mapping. However, we can have version to make it easy to extend if needed by having many entries pointing to the same original url. this way user can use different versions for different purposes such as a different URL in API
• Return Error if an URL is invalid
• Only Supports HTTPS scheme. Because other schemes such as file or tcp has actual objects such as a file in filesystem or an ip-address. Those objects are generally shortened themselves. However, if we were to implement the url shortening for all schemes we may need to map all filesystem, perform DNS queries, which may increase the complexity and may require a complete different design. So, we will validate URL scheme and return error when scheme is not HTTPS

Non-Functional:

• High Availability
• Low Latency - Performative
• Cost Efficient
• Security

Capacity estimation

• Assuming System is Read heavy
• let say
  • we have 1K read requests per minute
  • we have 1 write request per minute
  • if we have 10 KB as the request size
  • So we have to store 10 MB/min which is 600 MB/hr which is 1300 Mb/day which is 15GB per year or 75GB per 5 year of storage
  • we need about 1GB/min network bandwidth

API design

• Endpoint: Get /id/s_url
• Description: Given a short url return original url

• Endpoint: Post /id/o_url
• Description: Given an original url return short url

• Endpoint: Redirect /id/url
• Description: Given a short url redirect to original url

Database design

Schema: JSON

{

id: JSON

short_url: JSON

original_url: JSON

last_accessed: JSON

total_redirects: JSON

country: JSON

city: JSON

is_active: JSON

state: JSON

}

id: Unique Identifier

short_url: Shortened URL

original_url: Actual URL

last_accessed: When was it last used (this may be useful for caching)

total_redirects: How many times this has been used (this may be useful for rate limiting and saving against DDSO Attacks)

country: Location (this is useful for Load balancing, DNS etc.)

city: Location (this is useful for Load balancing, DNS etc.)

is_active: This is to decommission. this is useful for the cleanups

state: determines pending, progress or complete i.e. the state of the request

we should index on short_url for after redirects along with id which is used by all apis

High-level design

Client -> API Gateway -> Shortening Service -> Cache

Client -> API Gateway -> Shortening Service -> persistent DB

Client -> API Gateway -> Shortening Service -> retry, cache update job/service -> Cache

Client -> API Gateway -> Shortening Service -> retry, cache update job/service -> persistent DB

Request flows

Client -> Give me the Short URL for Original URL

API Gateway ->Authenticate, verify rate limiting, route request to Service

Service -> Does Original URL already exists?

Service -> Create No, if Original URL does not exist, return short url otherwise

Where Client could be User, API, Browser, Curl etc

Detailed component design

We use it because API Gateway can Authenticate and Authorise users of our systems, it also helps with rate limiting . Additionally, API Gateway load balances requests to our Service Deployment. The term Deployment implies that we have more than one replica. This means we perform rolling update and not all at once. This improves our fault tolerance in a way that if there is an error induced in the codebase the rollback happens only for the first replica while traffic is still being served, thus ensuring high availability

cache we use LRU to empty the cache and set TTL for 10 mins. cache provides us with optimum performance for the URLs that are very frequently accessed. when there is a cache miss we read from the database. while there is job that periodically updates the cache i.e. removing stale data and updating with Most recently used data. In case of writes we only write to persistent DB as writing to both persistent DB and cache could bring inconsistencies such as what happens if n/w breaks while writing to DB, but cache gets written successfully. So, it's better to keep this simple we write to Persistent DB and read with cache, if cache is a miss, we read from persistent DB

Trade offs/Tech choices

I would keep this as NoSQL DB because

a. we don't need strict consistency here i.e. ACID compliance does not seem a mandatory requirement here. I think it is fine if a redirect eventually say in 1 to 2 seconds redirects to the original url. Also, since the system is read heavy I believe the NoSQL DB will be more performative. referencing CAP theorem, which implies that we can only guarantee C (Consistency) or A (Availability) but not both. I am trading off C over A. We definitely need P (Partition Tolerance) for Fault tolerance and Scalability needs.

Failure scenarios/bottlenecks

N/W failures

DB Timeout

Cache Timeout

Retry Job looks at the state of the request, if was failed it retries. it's part of the codebase and runs periodically. Also implements Exponential BackOFF i.e. after 10 retries it can now be only manually retried this is for the purpose of keeping the DB sanity and not overloading the system

we can also have a manual API that can be run on demand to handle catastrophic failures such as what is DNS is down?

Future improvements

• Geo based routing
• Analytics: Use location details to track where is the traffic coming from
• monetizing using rate limiting, add subscription fee if more than 1000 redirects are needed in a day. Thus adding a payment service