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:

• List the key non-functional requirements (eg low latency, scalability, reliability, etc.)...
  • Read latency = 100 ms for p95, write latency = 200 ms for p95
  • High availability - five 9s of uptime = 5 minutes down time per year
  • Assumptions : 100 K new URLs per day, Store URLs for 3 years. 2K chars per URL, 2 bytes per char with utf8
  • Data size = 2K*2*100K *365*3 = 438 GB
  • 100 M requests per day

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

• tinyURL.com/getlongURL?shorturl=surl //returns long url
• tinyURL.com/createshortURL?longurl=lurl // returns short url

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Client - any web/app client uses HTTPS to communicate

API gateway - SSL termination, Authentication

Load balancer - for sending requestes to one of the nodes in the service layer. Simplest is round robin

Service = n number of servers to handle the requests

Cache layer - LRU cache

DB - permanent storage. TTL based eviction. Removes data after 3 years

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

createShortURL algorithm

• total # of unique urls for 3 yrs = 100K365*3 = 1Billion unique urls.
• map 2k char long url to a shorter string that gives 1B space
• Create a unique ID using a ID generator. It can use TS and machine address (MAC). Use base 64 give encoding which has 64 chars to get the short url from the unique id . This will support more than 1B unique values
  • Convert long URL to short. Check if short url already exists in the cache. If not run . put itas (K,V) of (sURL, lURL) in cache
• Service layer.
  • How many requests can be handled per server.? 100M requests/day. Assuming 80% of requests in day time of 8 hrs its 10M request per hour i.e 20K requests per sec. . Assuming 500 threads per machine we need 40 machines
  • Will need to rate limit and exponential back off
• Cache
  • Multiple cache nodes arranged supporting consistent hashing
  • Write through to cache and DB for durability
  • hold 80% of data in cache. Needs 350 GB memory. 25 servers with 16 GB memory servers
  • on cache miss look up and fetch from DB and add to cache
• To scale you can add more cache nodes and service nodes
• HA - use Replication: Keep 3 copies of data, need 120 cache nodes