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.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10