Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Update/ Modify the short URL value
• Delete the URL

Non-Functional Requirements:

• Low latency
• High reliability
• High Scalability
• Eventual consistency within bound of <10 secs

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

• REST API
  1. POST /shorten
  2. GET /sURL
• Data Model
  • shorten(String short URL)
  • getLongURL(String shortURL)
• Message Format
  • shotURL string
  • longURL string
  • createdAt datetime
  • expirationDate datetime
• Error Handling
  • 404 - the long URL does not exist or already expired
  • 503 - Unable to generate the short URL or fetch back long URL
  • 400 - bad input data
• Rate Limiting
• Load Balancer to distribute load
• API gateway to provide the security and logging /monitoring

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Main Components

1. Clients send requests which are first hitting the API gateway endpoint , which provide the Security/ Logging , Monitoring , Authentication/Authorization , TLS termination.
2. API gateway forwards the requests to LB for efficient incoming requests handling.
3. Incoming request for shorten API land on the Data server. LongURL is passed through a hash function to generate a unique but determined shortURL. (same value of short URL will be generated for a given value of longURL each time it is input)
4. The generated shortURL is added to a cache layer and also distributed hash table on a DB server
5. Requests for the getLongURL land on the read servers , which first refer to the cache . If the data is found on cache , it is returned else fetch request is sent to DB servers
6. DB servers use consistent hashing to handle the scalability challenges and sharding of data
7. Data on the DB can also be replicated based on some quorum to ensure consistency
8. Read requests for getLongURL can be served from dedicated read servers to optimize for read heaviness of the systems to return the longUrl for a given short URL. Since the use case is more biased to generate URL once and use many time

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.

The design can be implemented internally as a 2 separate micro service. 1 micro-service generates the shortURL while the other one reads the short URL to return long URL

1. The workload is read heavy so we can optimize the latency for the read path by adding dedicated read servers which only handle the read traffic.
2. To further optimize the read latency a layer of cache is added and the cache can be MRU cache to ensure the most recently frequently accessed values are in the cache and only cache miss is sent to the DB. In case of cache miss the request is then served from data stored in the database.
3. Further we can have a higher number of read servers compared to the generated data servers and the system overall can be uncoupled.
4. The database will be a key value store since there is no need to maintain data in multiple different tables or even database joins.
5. Data in the DBs is replicated to ensure high reliability and since we are ok with eventual consistency of upto 10 secs to be replicated everywhere , we can use consensus protocol to replicate and return data and gossip protocol to ensure the data stays up to data across different copies of data . This provides high reliability.
6. DB also leverages consistent hashing to ensure the easy scalability of database layer and also sharding the data for easy partitioning along with easy to manage data re-distribution or handling hot shard problem
7. Data base can be exposed via DB API to ensure we don't tie the business logic to internal database platform/implementation logic
8. The generate Short URL API has to generate a unique URL very quickly and ensure the uniqueness is maintained in a distributed hash table across all the distributed database shards. But distributed data storage and URL generation creates a challenge for uniqueness of the result.
9. To ensure the uniqueness of the generated short URL we can use hash function with more sophisticated collision resolution approaches
   1. Use a centralized unique key generator service which generates monotonically increasing integers and prepend or append it to the generated hash for the shortURL to ensure uniqueness
   2. Or allocate range for the hash function to each app server to generate the URL within that range
10. Use loadbalancer to handle the performance and scalability/latency requirements for handling the request distibution along with rate Limiting and API quotas in place to avoid the issues like noisy neighbors /resource abuse or even configurable quotas for the premium customers
11. Rate throttling Algo like leaky bucket algorithms can be implemented to handle the traffic burst effectively
12. In case of generator service outage , we need to have a fall back mechanism like a local cache of previously generated ids or a secondary generator identifiers that can take over in case of failure
13. In case of network partition , we can use a consensus Algo like Paxos or Raft to ensure that only 1 node can generate an ID at a time and each app server should query the centralized Id service before a new URL is created.