Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• High availability. The urls must always work and redirect correctly
• Low latency. The redirect must happen quick (<200ms) so the user doesn't feel the difference
• Durable: the url must work for the selected time to live

Key design decisions:

• The short url must be easy to read and short. we can use 8 char string. if we use alphanum, we have 26 + 26 + 10 char. (we can remove a few to avoid ambiguity like I l ), so about 52**8, big enough to avoid collisions and last forever
• To avoid collisions, we can implement a url generator that will generate and store in database the available url, so they can only be used once
• We can have a default time to live (e.g 5 years) to avoid infinite storage
• This is a read heavy system, we can guess created urls will be queried a lot
• We must focus on low latency and availability, so we can accept eventual consistency on writes
• key-value pair are small: 8 bytes for short, 100 bytes for long avg

API Design

• post createUrl(user_id, long_url): This takes a long_url and generate and return the short url
• get redirect(short_url): on the https://our-site/<short_url> path, returns a 301 permanent redirect to the long_url. This makes caching available
• deleteUrl(user_id, short_url): delete if owner
• listUrls(user_id): return the list of all user urls

optional:

editUrl(user_id. short_url, long_url)

High-Level Design

On the high level, the user communicate with the apps servers through a load balancer.

The read requests goes through a in memory cache for quick retrieval. In case of miss, the cache fetches the data from a distributed key value store.

On writes, the request is passed to a url manager that create the mapping.

Detailed Component Design

URL worker: on a write request, the long_url is sent to a url worker (from a cluster of them). The url worker load in memory a range of url from the available url database (which is sql for ACID properties). The urls are set to used at this point and no other worker can get them. The URL generator fills the database with new short_url when needed. The url worker verify the auth fo the user, and if good, write to the key value store master node the new mapping short_url:long_url with the ttl. The data will be eventually replicated to the read replicas

Redis cache: The redis cache is on the read path. On read request, the url retriever checks for the presence of the mapping in the cache, and it gets returned fast if there. Else, the cache query a read replica of the key value store and update the cache. Cache eviction policy should be least recently used. As the key value pair are small, we can have a consequent portion of the keys in memory for quick access

The cache ttl is also shorter to avoid long lasting wrong redirects and cache refresh. The caches can be replicated and geodistibuted