System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. Company client should send a long url and the server could returns a short url
2. User client should send a short url and server returns the long url for redirection
3. short url should be within 10 letters following domain

Non-Functional:

List non-functional requirements for the system...

1. latency should be around 200ms
2. client should have the option to create a custom domain url
3. client should be able to add an expiration time
4. server should records the # clients hit the short url
5. if the url expires, or hasnt been added to the db, server should returns 503 for retires in 1 min or 410 for url expired

Capacity estimation

Estimate the scale of the system you are going to design...

long: 100 character = 100 byte

short:short domain + 10 characters -- 20 characters 20 byte

createAt: 10 bytes

updatedAt: 10 bytes

1 million url, 0.14GB

(1000 new url per day * 30 *12 * 3years= 1 million url in db)

shortUrl: 20 byte

count: each url is touched 1000 times -- 4 bytes

1 million url, 10E6 * 25 = 25 MB

target market small business, peek estimation:

• 1000 new url perday, urls created last week are more likely to be clicked
• each url has 1000 clicks per day
• E7 total clicks, peek is at off time 7pm to 11 pm
• 600 per second

load balancing, redis, cdn?

API design

Define what APIs are expected from the system...

• POST/shorten

request body: {"url": "https://...", "expiration?: "}

response: {"shorturl": "https://short.url"}

• GET/{shortUrlPath}

response: 302/301 redirect, 302 is more suitable since its temporary redirect so the site doesnt cache the redirect

error response:

503 service unaviable, short url hasnt been updated to the db yet, ask client to retry in 1 min

410 gone, short url has expired, notify the client

• Get/shorten/stats/{shortUrl}

Response:

{"shortUrl": "https://shorturl/...",

"longUrl": "https://...",

"cliclCount": 100,

"createdAt": "*******"

"expiredAt": "*******"

}

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

a sql db:

INDEX on shortUrl

url: [shortUrl, longUrl, expiratedAt, createdAt]

stat: [shortUrl, count]

the url is high read low write, stat is high write low read

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

• User Interface: web front end
• Load Balancer: distributes incoming traffic across multiple web server, distributes based on network since creating and fetching isnt a resource / cpu heavy work
• webserver: handle http requests + url shorten service
• db: url db and stat db

SQL:

INDEX on shortUrl

url: [shortUrl, longUrl, expiratedAt, createdAt]

stat: [shortUrl, count]

the url is high read low write, stat is high write low read

choose sql over nosql because:

1. 1. the table is highly structured and requires Atomic (nosql is eventual consistency), which means a new put/longUrl might not be added to db very quick.
   2. update count: url table is high read low write, stat is high write low read. placing them in nosql will heavily increase the latency on read case while updating the count, while count isnt related to GET/{shorturl}. and its easier to increase more scheme in stat
   3. query: i need to join the url and stat table, generally its easier and quicker to access in sql
   4. scalability isnt a hugh factor per earlier calculation

• redis:
  • cache the long url for quicker access, per calculation, it could easily save the newly created url (7-days) in cache, which most likely are the url that the clients would request
  • If a url is not found in cache, fetch the longUrl from db and add to cache
  • if a url expired in db, notice the cache to mark not active to the short url. if the client requests this url, notify the url that the url expires
  • ICNR count when creating url (the logic is explained later)
  • TTL of 3/7 days; log the cache hit/miss ratio so
  • Least Recently Used (LRU) Eviction
• Monitoring & logging: keep track of system health, user activities, errors, and peek for further development

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

check my sequence diagram

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

URL shortening service:

• general case:

1 url + timestamp -> hash -> base 62; then check for conflict. if conflict, hash again

2 INCR the count -> hash -> base 62 -> check for conflict. if conflict regenerate hash

option 2 is favored here since each count is unique, so its likely to create a unique url

• custom alias:

1 check for conflict

2 if conflict, fall back to incr -> hash -> base 62, add the part to the end the alias

Load Balancer:

• Request Handling/reroute
• scalability/load balancing: it can easily scale horizontally; when more traffic, add more server
• SSL/TLS
• rate limiting
• logging and monitoring for error and user pattern

Server:

• easy scalable, add more server

DB:

url table:

• our current calculation proves we can save whole urls in one db
• but if we need more db, we can partition them
• replication in case one of the db went down, failover strategy to exchange slave to master if master goes down
  • peer to peer replication: every nodes are both a master and a slave, higher availbility and redundency

stat table:

• separate table for stat, since its generally smaller than url, it can saved more space and scale separately if needed

Redis:

• frequent fetched url are saved in the redis so the server doesnt need to read from the db again
• use INCR to add the count of created urls, to ensure uniqueness
• if we are using multiple redis, each redis could have different ranges

cache TTL:

• 3 day for rarely accessed url; 7 days for frequently accessed url
• log the hit/miss ratio for optimized ttl time
• Least Recent Used Eviction
• rarely accessed and so is check using ____
• Expired url will send a expired flag on cache in case client requests it

Database:

• two table of url and stat, so they can be scaled separately
• ensure the url is more high read low write and stat is high write low read
• replicate on peer-to-peer (tradeoff discussed later)

Database TTL:

• Expiration checked every 5 min
• permanent entries with a soft-delete flag to allow analytics retrieval
• Regular check for stale entries

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Master slave replication vs peer to peer replication:

Master-slave: 1db handles all write and all handles read

peer-peer: all serves as write and read

peer-to-peer is preferable because:

• even though peer peer copy the full db, the url tabe is generally small
• not a single failure logic, shorter off time
• cons: eventual consistency, reads from slave might results in reading from stale data, hitting more unavibility; but since its a low write high read case, its fine
• conflict handling: if it happens that 2 post creates same url, just ask them to create new hash on new INCR

AWS Lambda vs batch update count through redis:

Lambda:

• save the memory in redis
• can easily add more stat later, or trigger other events if needed
• priced on time

Through redis:

• save cost,
• batch add then update the count table
• implement acid
• still decouple using job processor, if succeed, return a confirmation and delete the increment table on job processor

Currently, redis batch count is perferable, but if more stat is requried, we can add the microservice here

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

webserver is off:

• we are currently load balancing to reroute the service based on network since network is more important on low latency culture and post and get url is generally less cpu intensive
• health check to auto reroute traffic to healthy instance
• fallback page to handle errors gracefully

Redis failure:

• we use LRU to save the redis memory, and log to find the best ttl
• have secondary redis for failure, the url coule just be reloaded from db
• the only lost is the stat count, which is lowkey fine? other option is use microservice for stat

DB failure:

• peer to peer replication (reason explained earlier in tradeoff)
• find the optimal ttl so we are less likely to hit the db and create a heavy load

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

added lambda to give more stat

check for url security in case some site use our service for phishing