Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• Low latency: url creation < 100ms + fast redirect
• Consistency: generated urls should redirected original urls(at least during TTL we originally agreed)
• Reliable
• Scalable: surge of redirect requests and new clients should be supported
• Service should be highly available

API Design

Basic entities:

user

provided_url

generated_url

Data model:

Table USERS:

user_id[pk]

pswd_hash

Table LINKS:

link_id

user_id

original_link(base32 encoded)

generated_link(using sha-256 and base32) [primary key]

created_at [sorting key]

Rest API:

1. POST /user/[id]/urls { url : {original_url} }
2. GET /user?url={tiny_url} -> redirect to original page

High-Level Design

Flow(generate url):

1. User sends request to encode url
2. request touches API Gateway
3. query process by application server
4. app server generates SHA-256 from original url and encode it using base 32 suitable for URL
5. Then we will check if new value is already available in DB, if so will return it, other wise step 6
6. generated value stored into DB as key-value pair {original url, generated url}
7. Api gateway sends back response with generated url

Flow(redirect):

1. request touches api gateway
2. goes to app server redirect service
3. service looks up for original url and sends response with redirect response to the user

Detailed Component Design

1. DB: since the data is well structured we can use SQL db(e.g. postgres). It also grants consistency of our data.
2. to grant horizontal scalability we should enable replication and sharding
3. To garanty low latency response we are going to use key-value cache(Redis) before lookup for the DB. In case of cache miss service will fallback to DB. extracted value will be populated in cache(with TTL=7days). Eviction model is LRU.
4. for scalabilty we can introduce multiple app servers that will partition incoming requests
5. we are also going to use load balancer in front of our api getway
6. To garanty fault tolerance we also will have redundant LB, app servers and DB to hands outages.
7. App servers should contains following services: a. url generation b. redirection c. analytics
8. In case if colision happend for generated url: i.e. generated url coinsides with another previously generated url we could 1. fallback to some reserved urls to workaround it 2. continue incremental url generation until uniq one will be generated
9. to garanty low latency redirection there are some techniques could be used, we could have message queue(kafka) in front of redirect service that will contain all redirect requests, and redirect service will have multiple users that will subscribed on this queue.
10. To speed up redirection we could also use CDN allowing faster url resolve and redirect based on user geographical location

Availability will be acheived because of used redis cache. This sharded cache grants low latency during query processing. Sharded DB also impacts availability. in case of network partition data still will be available.

Horizontal scalability could be achieved by adding new DB shards, new instances of app servers and redis cache. Usage of the load balancer will grand horizontal scalability.

To prevent surge of redirection requests and DDoS attackes we will limit amount of queries per user.

Collision resolving strategies: when newly generated url already exists we don't populate it into DB we continue generation until wont produce uniq shorted url, we can do it in following way, generate ssh-256 hash, and calculate base32(hash), if case of collision just hash++ and repeat until base32(hash) is unique