System requirements

Functional:

1. Given a normal URL, the system MUST be able to return the short version of it.
2. Given a short URL, the system MUST be able to return the expanded(normal) version of it.
3. Given a short URL, the system MUST be able to delete the short URL.
4. Given a short URL, the system MUST be able to return the statistic of it
5. Given a normal URL and a valid custom shorten alias, the system must be able to return the short URL according to alias.

Non-Functional:

1. Low latency of APIs: 50 to 200 milliseconds.
2. Security:
   1. Data encryption at rest.
   2. Data encryption in transit.
   3. Rate limiting.
3. Scaling: see below capacity estimation session.

Capacity estimation

1. Rate of around 10 to 100 requests per second per instance of your service
2.  Store between 10 million to 1 billion URLs in the database.

API design

1. String expand(String shortUrl) - Given a short Url, return the normal version of it. It can throw 404 if the shortUrl doesn't exist
2. String shorten(String url) - Given a Url, return the short version of it.
3. String shorten(String url, String customAlias) - Given a Url and a custom alias, return the shorten url using the custom alias if that's applicable.
4. boolean deleteShortUrl(String shortUrl) - given a valid shortUrl, delete the short url from the system. It can throw 404 as well when short URL is not available.
5. Statistics getUrlStats(String shortUrl) - given a shortUrl, return the total clickCount of this shorten Url.

Database design

We'll go with a key-value NoSQL store assuming that no new significant feature development is required in near future. Considering that we'd like to focus on a rapid prototyping and we'd start with DynamoDB.

All the related ER graph are drew. They will be stored in different tables as they are serving different kind of traffic and scaling can vary.

High-level design

Components:

1. API Gateway - handling authentication, authorization and throttling of the incoming requests.
2. Load Balancer Component. The incoming requests will be routed to the load balancer and distributed to service instances.
3. Application Serverst: Service instances will perform corresponding business logic and store the shortUrl, Url and log the click events.

• Database Layer:Stores information about shortened URLs, click statistics, and user data (if applicable). This is where you would interface with your key-value or wide-column store.

1. Batch process component for processing and aggregate click events. This would use a message queue to persist the data before they come to the processor. The processor will aggregate the data for a certain interval(e.g. 1 min) and then update the count number in the database.
2. For user management, it is not the key workflow in our use case but we do need to consider the

Request flows

1. For a typical shorten request, it will go through the APIGW, to load balancer and get proceed in application server. After we get the shortUrl, we can check in datastore if it already exists, if not , then we store it in the database.
2. For a typical expand request:

1. User initiates a GET request to /expand endpoint with the shorten URL.2. The API Gateway receives the requests and forward it to the Load balancer.3. Load balancer routes the requests to one of healthy Application Servers with certain routing algorithm.4. The Application server checks the Database to see if a shorten URL exists, if so, it retrieves the corresponding full URL and return to customer. If not, it will return a 404(ResourceNotFound) back to customer.5. Application server will invoke the log click processor to report its statistic. 6. Response will be sent all

Detailed component design

1. For APIGateway, we can have multiple layers of request validation, from the basic length validation and syntax validation(e.g. parameters that are required v.s. optional). Before any deep validation, we can do the authentication and even authorization here. For sake of the interview, we will just do AuthN with our own solution. We can use token-based approach to create short-term credentials for customers and provide corresponding APIs for the customers to retrieve and use token. As for rate limiting, that's an interesting topic and requires additional effort as it might involve some host communication protocols and other topics. For simplicity of this design, we can say we just have a host-based(local) throttling for now and to protect hosts from getting overloaded. However, we definitely need to have user-based throttling to ensure the "fairness" of the system and customers won't be impacted by noisy neighbors.
2. For load balancer, we can go with hardware load balancer / software load balancer. I will go with software load balancer(e.g. Nginx for open-source and ELB for cloud-based solutions) here considering the rate of the load. There are several routing algorithm like round-robin, least connections, random weight. If you have different host types where some of them are more powerful then you can go random weight. Considering all those APIs are I/O bounded instead of CPU bounded and they have similar level of complexity so we can have a group of similar hosts and just use round robin to start simple. As for health check, there are multiple strategies here, including local health check to ensure the instance is healthy, liveness health check to ensure the instance is able to respond to requests, dependency checks which check if it is able to talk to dependency. Health check need to be carefully set up as it sometimes can return false positive and bring down the entire fleet of instances. For example, in dependency health check, if it fails due to dependency unavailable, all servers will shown as unhealthy although they are healthy. One good rule of thumb is to fail-open when all hosts are unhealthy to handle this false positive case. Besides, perform fast and reliable tests(liveness/local host check) on the work producer. For dependency / anonymous check, they can be done through a independent workflow and alert engineers if it happens - as those are "deep" validation and should be taken care of with caution.
3. For Application Server, for shorten -> We need to first validate if the given url is in a valid format. If not, we'd return a validation error to customers. Then, apply an algorithm to shorten it. One way is to generate a unique identifier(e.g. via UUID). However, there is a chance that it can conflict with some existing FullURL. To minimize the chance of conflict, we can append some random characters at the end. There is still a small chance to conflict but we can make it almost impossible practically. Afterwards, we can check the datastore if the shorten Url already exists, if not, we can put it in the database. Afterwards, the server will return the shorten url back to customer. For expand API, once we get the shortenUrl, we can query the database to see if it exists. If not, we will return 404. If so, we will return the full URL back to customers. As we can expect this is a read-heavy application and the mapping between shortenUrl and fullUrl won't change so there is a chance that we can establish a local LRU cache on the host to accelerate the requests to "hot" shortenUrl.
4. For Database layer, we have decided to go with NoSQL based off of the data access pattern. since we're favoring strong consistency so I would use the typical pb replication(e.g. chain replication) to provide durability and ensure data won't be lost even one of the storage node corrupted. There are some other ways to do replication like leaderless but usually that's for higher write throughput and favor of eventually consistency so it is not inclined here. Besides, I think as we already have a local cache on the application server layer, it should help mitigate the hot partition issue to a certain degree(needed to be tested out). If hot partition still exists due to very popular URL, there are some other approaches to mitigate the issue including adding more replicas for certain partitions to serve read traffic. If we are on managed solutions like DynamoDB, we probably don't have that level of control but can still manually split a partition into multiple ones and evenly distribute traffic to those partitions to serve requests. Besides, regular backup can help with data recovery for some events. The backup can be done during midnight to avoid impacting the customers' usage. It can be done via taking a snapshot of the storageNode - if we want to support point-in-time-recovery, that's possible to combine the snapshot and the WAL(or whatever implementation of your replication logs). For DynamoDB, you can enable it and integrate with AWSBackup for your data recovery solution.

Trade offs/Tech choices

1. Data Aggregation approach for click events(batch v.s. streaming) => batch is preferred considering no near-realtime requirement here for getting statistic of click data.
2. Replication of data storage node: single leader replication v.s. leaderless replication=> single leader replication is preferred for strong consistency.
3. NoSQL v.s. SQL: as no cross-table query is used in any data access pattern, we'd like to use NoSQL for better scalability and good extensibility.
4. shorten algorithm: we don't want to have different fullURL share the same shorten URL, therefore, we will keep checking database whenever we generate a new shorten URL.

Failure scenarios/bottlenecks

I'd like to analyze component by component and assume the failure mode one by one.

1. APIGateway failure=> Some of the hosts are down and cannot serve traffic. We need high availability so internally it also needs to have a load balancer to distribute traffics. Client-side can apply the retry logic and circuit breaker patterns to provide better resilience. Note that those can also have some negative impacts like generate retry storm and overload the service, we can dive deep into it if we would like to.
2. Load balancer failure => There would be always a secondary load balancer standby and it will monitor the health of the primary load balancer and takes over whenever needed.
3. Application server - if one of them is unhealthy, traffic will no longer be routed to the unhealthy host. The requests served by unhealthy host will return 503 to indicate the server is unavailable and customers can retry it. Load shedding is required as well sometimes if network was partitioned.
4. Database failure=> it is a fully managed database solution as we discussed(DynamoDB), it will return 5xx to application server if it is down. Sometimes there can be a hot partition issue even with local cache if it happens, we can consider investing in distributed cache or consider adding more read replica or we have to manually split one shard to multiple ones.
5. Event processor failure => for transient failures, events will still be available in the persistent layer(e.g. queue) so no event should be lost. Idempotency and DLQ should be considered for duplicate events and failed events.
6. For network failures, DNS failover is also a strategy to re-route traffic to different regions / alternative providers. Besides, monitoring the latency of network can be.

Future improvements

1. Pricing system and analytic system to see how system behaves and its usages. Those are important for long-term business growth and identify customer access/usage pattern.
2. Conduct regular or even automatic load tests to identify the system capacity and set up proper capacity management tools.
3. For simplicity, we don't touch the cost reduction perspective here. There are multiple areas we can reduce the cost per current design, for example, leveraging TTL(Time-to-live) feature of the data store to purge old data(or rolling them up and put in a cold storage instead).
4. For simplicity, we don't talk a lot on the security here. There are some areas where it can be improved. for example, right now the data encryption at rest is done by a centralized data key generated by envelop encryption. It is safe but there is still a chance of large blast radius if it gets compromised. Therefore, it would be nice if customers can have their own key used to encrypt their data(e.g. fullUrl). Besides, some logging should be redacted if they are logging customer data...