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:

• The URL redirect (query the long url with a given short URL) needs to be very fast with low latency (e.g. less than 10ms)
• The URL redirect needs to scale in/out based on the traffic load.
• The URI redirect needs to have high availability (99.999%).

API Design

Concept (data)

shortUrl

• id
• code (The shorten url. For simplicity, we can use string id as code)
• destination (the origin long url)
• Owner
• LastUpdatedBy
• LastUdpatedDate
• CreatedDate

RESTful API - api/v1/

1. POST shortUrls/
2. GET shortUrls/{id} // id is equal to shortUrl
3. GET shortUrls/by-code/{code} // when id cannot be shortUrl
4. GET shortUrls/{id}?fields=destination
5. PATCH shortUrls/{id}
6. DELETE shortUrls/{id}

High-Level Design

• Client traffic will first hit load balancer to distribute the traffic on to different endpoints.
• Then the request will hit API Gateway for authN/Z, API version, and routed to the backend service based on the business logic - for redirecting a user from a short url to its destination -> goes to redirect service. For short URL creation, goes to short URL mgr service.
• The redirect service will query the cache first to get the destination of a given short URL. If cache missed, it will query the database directly then update the cache.
• The short URL mgr service will update short to long url map records in database. It will use id creation service to create the unique short URL for a given long URL.
• The Id creation service is responsible for creating unique id for a given long URL. It needs to ensure the id is unique and cannot be used by other long URL.
• The long url -> short url mapping is stored in a database.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

API Gateway: it will manage AuthN/Z, API version and route user query based on the request operation type. For read operation, it will route the request to redirect service. For write operation, it will route the request to the short url mgr service.

Redirect service: It's a stateless microservice where it queries the map from cache, if no cache hit, then query database directly and update the cache.

Short URL mgr API: it's a stateless microservice. On short URL creation scenario, it will use Id creation service to generate the unique id, and store it in the database. On failure operation, there is retry with exponential backup mechanism for resilience.

Id creation service: This service creates unique id per given long URL. We assume the URL should be 7-8 char. And we can use base62 algorithm to generate random three three-digits numbers, then encode it as base62. Then return the encoded string back to the caller.

Map cache: The map cache can be any cache service. it can be in-memory cache or cache with storage (e.g. Redis). Cache records use TTL to balance between cache hit and legacy record. When a cache record live exceeds TTL, it will be removed from the cache. So the next query will go directly to the database and update cache.

Database: For this case, it might not make sense to use relational database since we don't have complex data structure. We can use common document db to store the url map records. Based on the query, we will have to turn on indexing of id/code. The database should have replica for data recovery. When there is concurrent write to the same record, we will have a simple lock on the record - one of the write will succeed, the remains will fail. This is acceptable to ensure consistency but tradeoff a bit of availability. Based on the Id creation algorithm, there might be chance where a not unique id is given to another URL. To guarantee the uniqueness of the shortURL, we can turn on "unique" config on the field to fail any attempt operation.