Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• (Optional), Alias as short key for the url.
• (Optional), Expiration Time.

Non-Functional Requirements:

• Uniqueness of the short key at scale.
• Scalability - Should be able to handle 2 million creations and 20 million redirections.
• Low Latency - Redirect should be within p95 Latency
• Availability - System should be up for 99.99% of the time.
• Consistency - Small degree of eventual consistency.

API Design

POST /create - 200 OK

{

longURL,

userId,

alias?,

expirationTime?,

}

GET - /r/{shortkey} - 302 Redirect

Entities

• User
• Long URL
• Short ULR

Data Model

URL Table

• Short key (PK)
• Long URL
• User Id
• Alias
• Expiration Time
• Creation Time

User Table

• User Id
• ...

High-Level Design

Total number of URLs = 2e6 * 365 * 10 ~= 8 Billion URLs

Standalone Design (to satisfy functional requirements)

• Simple design with a client, server (with shortening logic) and a database to store URL maps
• Shortening Logic:
  • Prefix / Suffix of the URL:
    • Could work if the URLs are from different websites all the tiime.
    • Practically, not the case, we can have many URLs from the same website, so the prefix cant be the key.
    • Different websites may have different contents and routes, but the chances of having same suffix is highly likely, so cant use suffix here too.
  • Hash - MD5/SHA1/SHA256:
    • These could work, as they give different hash for different input.
    • Even a smaller URL will get a bigger hash. Trimming the hash to first x chars or last x chars, increases the chances of collisions so its not worth it.
  • Integer Counter
    • A simple integer based counting function could work, for every ask to the function it increments and returns the number
    • Could work, but a linear 8 billion integer space, can cause predictability and not safe and secure.
  • Base62 based Counter
    • Instead of using the simple integer, we can encode it to base62 (0-9,a-z,A-Z).
    • If you take 8 chars for short key, i.e. 62^8 ~= 220 Trillion URLs (0.003% of our requirement, no overrun of the uniqueness space).
    • So the uniqueness space is quite large, so to avoid predictability we can even add a random seed to the counter.

Storage Estimations

URL Table:

• Short key (PK) - 8 bytes
• Long URL - 200 bytes
• User Id - 8 bytes
• Alias - 100 bytes
• Expiration Time - 8 bytes
• Creation Time - 8 bytes

1 URL ~= 500 bytes

8 Billion URLs = 500 * 8e9 ~= 4 TB

In practice, indexing + sharding + replication - 3-4x ~= 20TB

Scalable Design (To satisfy scalability):

Avg QPS:

Reads = 20 million / day = 24 reads / sec

Writes = 2 million / day = 2.4 writes / sec

Peak QPS:

peak = read - 100x, writes - 50x

headroom = 2

Reads = 2400 reads/sec * headroom = 4800 reads/ sec

Writes = 120 writes / sec * headroom = 240 reads/sec

As the scale is high, we need to move to a staless architecture.

Components:

• LB: Balances the traffic for api gateway and services.
• CDN: Region specific cache.
• API Gateway: Handles AuthN, Rate Limiting, TLS Termination.
• Creation Service and Redirection Service: Stateless services, that can be auto scaled based on the Read/Write QPS.
• Base62 Counter Service:
  • As we scale, we cant keep the counter service as part of the creation service anymore, we need a seperate global counter service, which all the creation services will use to get new short key.
  • Also to reduce the load as more services ask for short key, the counter service instead return a range that a service can use on it own to create the key and return without consulting the shorten service.
  • If a service does go down, its ok as we have enough unique space, we can just allocate a new range and still never go out of scope.
• Cache:
  • As we scale, and the system is more ready heavy, we can add a cache, to reduce the load on database
  • Assuming a hit rate of 90%:
    • Without cache: DB Read QPS - 4800
    • With cache: DB Read QPS - 480
• Database:
  • Needs to be replicated, in case failure

Detailed Component Design

Low Latency

• The total RTT should be within p95(i.e. 100ms)
  • LB and API Gateway: 10 to 20 ms
  • Redirection business logic: 10 ms
  • Cache
    • Cache miss: Database read 10 to 50 ms
    • Cache hit: 1 to 5 ms
• In case of a burst of requests, which could cause the requests queue to fill and hold the requests past the threshold, we can follow some strategies
  • Timeout, with bounded exponential retries
  • Scale up the services
• Introducing replicas for database, such that all the read goes through replicas and writes goes to primary, splitting the load to primary and replicas will ensure that each request is served in time.

Availability

• To ensure the system is high available, we need to remove or fix the system where SPOF is possible because of high load.
• In the current design , i see 3 essential components which could cause the system to go down.
  • Base62 Counter service: As this is a single global service, we can replicate this service with a common store, possible consideration is redis with INCR and using redis in cluster mode, should be able to handle this.
  • Cache: If the cache goes down, the entire load will go to database, which could take the database down, we can use some replicas for the cache as well or use a secondary node for cache, so in case the cache goes down the secondary can take control.
  • Database: The main store, if this goes down, the entire system is useless, so we have to make sure this has replicas and proper failover strategies to ensure the database is up all the time.
• By making sure the counter service, cache and database are Highly available under load, we can acheive the 99.99% Availability

Consistency

• Most of the times, we will read from the cache itself, so we need to make sure the ttl set in the database should match the ttl of the cache, one way is to set a default ttl (around 1 days, short enough for the url to be accessed, a hot url, will be always read from cache), another is set tll based on user's expiration time.
  • Estimated cache size:
    • Read QPS - 2400 / sec
    • Hot urls - 10%
    • TTL - 1 day
    • URL Object data - 500 bytes
    • Total - 2400 * 0.1 * 1e5 * 500 ~= 12GB per day
• From the user point of view, the created short url, should be accessible. The question is a small delay is acceptable here or this needs to be instantly available.
• For this system, from my opinion a small delay is absolutely ok, with that assumption, we can decide how the replicas will get their updated data.
• As the entire system is stateless, a request for same short url, might hit different replicas in the database. So, we need to ensure that the once user sees the url work, it should always work.
• We cannot go with async writes, as the request flow to different replicas, can give stale results, We can go QUORUM based write, with N = 3, R = 2, W = 1, in this way we can ensure that atmost one replica will have the latest updated data.