Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Users can create accounts for authentication and manage URLs they have created
• Users can create also custom short urls
• Provide users with analytics on their shortened URLs, such as click counts and geographic data
• Batch URL shortening
• Expire URLs

Non-Functional Requirements:

• The system should be highly available, scalable (storage) and low latency when redirecting URLs

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...

1. createShortURL

1. redirectURL

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.

• shortURLsvc: service to shorten URL and store it in a database. It should store when will that shortened url expires. Let's assume that all shortened urls expire in 24 hours.
• redirectionURLsvc: takes the shortened URL, finds it in the database or distributed cache (redis), returns the original url
• Database: to store all URLs (created by shortURLsvc or by a backend process)
• distributed redis cache: cache to store most frequently accessed short urls.
• backend process: create unique keys in database to be used as short urls. Meaning that keys will be created, but they won't map to an original url.
• Analytics service: service to track analytics of urls (whenever people get redirected to that url)
• analyticsdb: store analytics of urls.

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.

• shortURLsvc: How to shorten URL? We can hash the url and take the first 6-8 characters as the key for the short url. Ex: user enters thisismycoolwebsiteletsgo.com. Our service would hash the url and get a result like guahfiulhfa..weriosc. We would then take the first 6 characters of that encoding. So final URL, would look like tinyurl/abc324.com. So in our database we would store tiny.com/guahfi -> thisismycoolwebsiteletsgo.com.
  • Con: We can get duplicate hash keys. To fix this, we can keep a counter whenever we get a duplicate and keep regenerating the unique key or rely on our backend process to get unique keys to shorten urls.
• redirectionURLsvc: it just looks into the database to find the shortened url and get the original url as a value. If it is not in distributed cache, we store it in the distributed cache.
  • Cache miss: If the url is not in cache, look for the shortened url in database. If the url is not in database, return an error saying that user needs to create a valid shortened url.
  • TTL expiration policy: When setting the shortened url in cache, the expiration policy is 24 hours from now because url's expire after 24 hours in our system.
  • Eviction policy: remove shortened urls with least recently used.
• backend process: These unique keys will be stored in database and they can have a field as not used(meaning that it has not been assigned as a short url. It isn't mapping to any url). This is useful when we don't want to perform a calculation like hashing and then encoding, let's just take a unique key and use that as a shortened url.
  • con: we would need to keep track of the keys not being used as urls

Trade offs (things to consider):

• If a shortened url expired, should we reuse it? or will reusing it mess up the analytics service? Maybe we can store versions of that hash key (how many times has been used)
• What happens if millions of requests are coming in to create short urls, there would definitely be collisions of duplicate short urls and maybe we can face a race condition. We can add a locking mechanism to make sure that only one short url is created at a time or we leveraged all the keys created by our backend process to assign it as a short url of an original url.

Scaling:

1. use load balancer to redistribute traffic in api gateway. Assume that API gateway and the other services scale horizontally.
2. Assume that database to store all URLs and distributed redis cache have read replicas. That way, if primary database is down, one of our read replicas will step up as primary.
3. As data grows, we can partition our database by shortened url's by hashing it again and assign it to a partition. We can use consistent hashing for whenever a new node gets added or one node gets removed.