System requirements

Functional:

1. Create short URL - given long URL, generate a concise alias or short URL
2. Redirection of short URL - users get redirected to the long URL from the short URL.

Non-Functional:

1. High Availability - especially in the redirection functionality.
2. Short Response Time - under 10ms for redirection. Creation is more relaxed.
3. Scalability - should handle growing data.

Capacity estimation

1. 200M DAU
   1. 2 creation per day - 400M creation daily - (5k creation per second)
   2. 20k redirection requests per second - (1.7B per day)
2. assumes 100 chars in long URL - 100B per long url in storage
   1. but should handle up to 2k chars
   2. 100B * 400M per day = 40GB of new storage needed per day - 40G / day * 365 day / year = 15 TB of new storage per year
3. expiration - can be indefinite
   1. allow customization of expiration.

API design

Because we have two main functionalities for this design, we will have two main APIs:

1. createURL() | POST /create
   1. this will be a POST type API, with the following fields:
      1. longURL: string
      2. expiration_time: int. This is how many days the generated short URL is going to be expired.
2. redirectURL | GET /{alias}
   1. this will be a GET, fields are:
      1. shortURL: string

Database design

Here is the database design for the mapping data:

• [PK] alias
  • string
  • the generated 8 character string in the shortURL
• longURL
  • string
  • the original URL submitted by user
• creation_time
  • timestamp
  • epoch format
• expiration_time
  • timestamp
  • epoch format

We might want to add user_id, to indicate the created_by. but I think this is out of scope for our design, as we do not care much about who created the shortURL and/or who has access to the URL.

High-level design

Since we have two main components, we will use two micro-services: creation service; redirection service.

An API gateway is placed between the user and the service to handle rate-limiting, gatekeeping on malicious activities. Authorization/authentication layer can also be placed here, but I think it is out of scope for this design.

data layer to store the url mapping, caches and CDN is used to improve performance of the system.

We need a sequence generator to generate the alias in the creation service.

Each micro service - creation service and redirection service can have their own load balancer and computing resources. Because we have a higher emphasis on the redirection workflow, we want to put more resource on the redirection service.

Request flows

1. Create URL request flow:
   1. client reaches the API Gateway with the create URL request. The API GW handles the rate limiting and forwards the request to the creation service
   2. the creation service calls the global sequence generator to get a unique 8 character base 62 string, that will be the alias of the short URL.
   3. the creation service writes this data to the cache AND to the URL store [write-through]. - deep dive later
   4. return alias to the user
2. Redirection request flow
   1. client checks the CDN if the data of the url mapping present, if so, great, redirect!
   2. But if it's not in the CDN, the request go to the API Gateway and again forward to the redirection service.
   3. The redirection service checks the cache first if the mapping present,
   4. hit to DB for the mapping.

Detailed component design

1. First, let's discuss the global sequence generator part.
   1. I assume we will use an 8 character base 62 string, but is that enough for our use case?
      1. using this format, there will be a total of 62^8 := 2e14 different alias. We need 400M * 365 := 150B per year let's round up to 2e11 aliases every year. Using 8 characters 62 based encoding, we should be able to handle the service to run for 2e14/2e11 = 1000 years - that's more than enough.
      2. But what about other ID generation?
         1. hash functions like MD5 and SHA256 generate extremely long strings that becomes wasted space.
         2. UUID, same issue, even though it creates globally unique string with really low chance of collision, it still have the problem with long string. It probably defeats the purpose of this service.
      3. We can still use the hash functions to first create a string, then encode in 62 base encoding to get the alias, if the encoded string is > 8 characters, we can just truncate to 8 characters.
      4. What if there's a collision when we generate the alias. We can just request a new sequence again by appending random dummy characters to the original url string. This will be okay since we have more relaxed response time requirement on this component.
2. I want to discuss deeper on the performance of the design, especially for the redirection, since response time is more important here.
   1. I'm using caching and CDN to achieve higher performance, since CDN is more costly, we should be smart what is cached there. What makes more sense to me is that we store most frequent redirection close to the CDN's geo-location. For example, a URL to an article about a celebrity in the US will be available in CDN in North America, where as it probably does not need to be in CDN in East Asia.
   2. The in-memory cache is used to store more url mapping for faster read. We can use LRU or LFU eviction policies here, but I think LRU will suffice here as LFU is more complex.
   3. I also want to talk about the consistency. Since the expiration time is involved, we want to make sure the TTL in the caches lined up with the source (URL datastore). There is no update or delete API, we can guarantee no changes will be made once a data is written to the database. Cache invalidation is not needed in this system.

Trade offs/Tech choices

1. Let's talk about the storage system. Specifically, SQL vs NoSQL. Few things to consider:
   1. High availability
   2. Low response time in read
   3. String consistency is not a requirement - eventual consistency is sufficient.
   4. we have 15 TB of new storage every year
   5. considering all the above, I think NoSQL database would be preferred, since they are more available, low latency, can scale really well. Here I think we can go with a KV store (something like DynamoDB).
   6. SQL works well if we have data that is not growing as fast, strong consistency, or any ACID property is preferred, here, SQL would not work as well as a KV store.

Failure scenarios/bottlenecks

Let's consider the failure scenarios.

1. Failure in database write?
   1. The design here, I'm using synchronous write - meaning we will want to get an ACK from the database before we can say the write is successful. If there's no ACK or system timed out, simply retry the write.
2. Database down?
   1. what happens if a database died suddenly? Redundancy, where copies of data is stored separately on different hardware, so we will not lose data if one machine becomes unavailable.
3. Server in redirection service or creation service becomes unavailable?
   1. in each micro service they have their own load balancer, which periodically sends health check to each node, if a node fails, they we can get replacement.

Future improvements

Say the service scales really fast, the DAU increases 5x, creation requests increases, then perhaps 8 character 62 base string alias can be exhausted. We can update our global sequence generator to start create longer string alias to mitigate this.

Because we have expiration time for some of the URL, we want to have a system where it periodically checks the database and clean up any expired URL. This also frees up some aliases to be reused.

Security - A component to avoid URL abuse will also help improve the service.

Customizable alias.