System requirements

Functional:

• Given a long URL, a corresponding short URL should be returned.
  • If the long URL has already been shortened, then retrieve the respective value from the database to avoid creating a new one.
  • If not, then create a new mapping using the hash function.
• When a request is made to a short URL, the associated long URL should be returned.

Non-Functional:

• The service needs to be highly available (99.9% uptime)
• The redirection functionality should have a response time of <10ms.
• The service should be horizontally scalable, easily allowing additional servers to be added.

Capacity estimation

• Write operations: 200 per second, about 17 million per day.
• Read operations: 20,000 per second, about 1.7 billion per day.
• If we assume the service will run for 10 years, 17 million * 10 * 365 = 62 billion URLs.
• Storage needed: 100 bytes * 62 billion = 6.2 TB.

API design

• POST /api/v1/shorten
  • Request Header: LongURL: {longURL}
  • returns the corresponding short URL.
  • If the long URL already exists in the database, return the corresponding short URL.
• GET /api/v1/getLongURL
  • Request Header: ShortURL: {shortURL}
  • Returns the corresponding long URL.

Database design

• Database schema for storing URLs:
  • id: unique identifier for each long:short URL relationship
  • short_url: The created short URL
  • long_url: The long URL that the short URL will redirect to
  • created_at: Date URL is created

High-level design

The URL shortener is built around a microservices architecture with the following components:

1. CDN: Serves static content to the user.
2. Load Balancer: Routes the requests to various shards, to ensure maximum performance.
3. Rate Limiter: Checks to ensure that the request is within the allowed limits. If not, the request fails.
4. URL Creation Service: Allows the user to create a short URL. It will first check the cache for existing records, and then the database. It will then create a new record if necessary.
5. URL Redirection Service: Allows the user to convert the short URL back to the corresponding long URL. It will also check the cache and then the database if the record is not found in the cache.
6. Cache: The cache will store records that were recently accessed or created in the database. Say a short URL is recently queried, it would make sense to store that in the cache. This will minimize the amount of database queries. The same goes for if there is a common long URL which is recently shortened.
7. Database: The database will store all of the records. Unlike the cache, this will be rigid, persistent storage. The downside is that it is slower to access. However, it is a necessary component to ensure that all data remains organized and secure.
8. Monitoring and Logging Service: This will track user metrics and overall system performance. It will also be responsible for logging errors.

Request flows

• The client makes a request.
• First, a DNS lookup is conducted and resolved to an IP.
• The CDN then serves any static content to the user.
• The API Request is routed through the load balancer.
• The load balancer routes the request into a rate limiting middleware, ensuring that the request is within the acceptable limits.
• Assuming it is, the request is sent to the server.
• For the URL Creation Service, the cache is first checked.
  • If there is a matching record, the cache returns it, and the user is redirected without querying the database.
  • If there is not a matching record, the database is then checked.
  • If there's no record in the database, then a new record with a new short URL is created.
  • The corresponding short URL is returned to the user.
  • All requests and errors are logged using the logging tools.
• For the URL Redirection Service, the cache is also first checked.
  • If there is not a matching record, the database is then queried.
  • The corresponding long URL is returned to the user.
  • All requests and errors are logged using the logging tools.

Detailed component design

• Cache
  • Redis is used for the cache.
  • This cache will store serialized records, in JSON, with all of the URL record information.
  • If a record already exists in the cache, this improves performance and reduces latency as querying the redis store is faster than querying the main database.
    • This is useful for URLs that are queried very frequently in either service, as it will minimize the amount of queries.
  • Redis allows for good scalability as it supports sharding. It also stores data in memory, which improves performance significantly.
  • The downside of this is that memory stored data is not persistent, but this is not as important for this use case.
• Database
  • SQL is used for the database as it is structured, rigid data.
  • If a record does not exist in the cache, then a hashing function will generate the new short URL and store it in the database.
  • Otherwise, the record is pulled from the database and returned to the user.

Trade offs/Tech choices

• Chose to use SQL even though it doesn't scale as well horizontally. The reason is that the data for this service is structured and rigid, it always follows the same format. It is also persistent, which in the long term matters.
• Chose Redis as it is fast and will help reduce latency. This is especially helpful for URLs that are queried often. It also scales well due to the nature of it, and if more storage or processing power is needed, then more shards can be added to accommodate this.

Failure scenarios/bottlenecks

1. The user can try to access a URL that does not exist in either the database or the cache.
2. The SQL database can act as a single point of failure, creating potential availability issues, and can affect scalability.
3. The Redis cache is not persistent and can easily be wiped out or erased, requiring the cache to be rebuilt.

Future improvements

• Perhaps replacing the SQL with a more scalable database architecture like MongoDB or Cassandra.
• Save snapshots of the redis database to minimize data loss if the server crashes or otherwise loses the non-persistent data.