Please enable JavaScript.

Coggle requires JavaScript to display documents.

Design a URL Shortening service like Tiny URL (1H10M) - Coggle Diagram

- - - - User can pass in at most 8 bytes long URL, and we will return a new shortened URL with our domain name plus 7 alphanumeric characters.
      - Given the shortened URL, users should be able to access the original page efficiently without delay.
      - The service should keep all the links safe and periodically prune outdated URL given the expiration date.
      - The URL should be able to be renewed extend the expiration date.
      - :red_flag: Users should optionally be able to pick a custom short link for their URL.
    - - :check: We should moderate the potential attacks caused by XSS or CSRF that shorten their URL to disguise users.
      - :red_flag: The system should be highly available, and it should redirect in real-time with minimal latency.
      - :red_flag: Shortened links should not be guessable (not predictable)
    - - Analytics: e.g. how many times a redirection happened?
      - Our service should also be accessible though REST APIs by other services.
- - - - :red_cross: 50 Million users
      - :check: 500 Million users
    - - 10 Million
  - - - Each user read 5 links per day, then 10 Million users will be 50 Million read requests per day.
    - - :red_cross: Suppose the Read and Write ratio is 1000 : 1, then it will be 50K writes per day.
        
        :check: 100:1 ratio between read and write
        
        50 Billion read, and 500 Million write per month
    - - :check: New URL shortening per second
        
        500 million / (30 days * 24 hours * 3600 seconds) ≈ 200 URL/sec
      - :check: URL query per second
        
        50 billion / (30 days * 86400 sec/day) ≈ 20K URLs/sec = writeRatio * 100
  - - - 5 year * 12 months/year * 500 millions/month = 30 billions Files/objets for storage
      - Assuming 500 bytes each stored object.
        
        30 billions * 500 bytes = 15 trillion bytes = 15 TB for saving all the objects
  - - - 2^(7*8) / 50K / 365 ≈ 4 Billion Years to finish all the options
  - - - We know that we will have 200 new URLs/sec, so the total incoming data will be:
        
        200 urlsObj/sec * 500 bytes/urlObj = 100 KB/sec
    - - Since we know that every second the read request amount will be about 20K, so the outgoing response bandwidth will be:
        
        20K urlObj/sec * 500 bytes/urlObj = 10 MB/sec
  - - - Hotspot incoming bandwidth = 100 KB/sec * 80% = 80 KB/sec, and hotspot outgoing bandwidth = 10 MB/sec * 80% = 8 MB/sec.
      - The hotspot saving will only for one day and read only, and thus
        
        Requests per day = 20 K/sec * 3600 sec * 24 = 1.7 billions`
        
        The requirement will be 20% * 1.7 billion * 500 bytes/urlObj = 170 GB. And since there are many duplications in the URL, we can actually use less than 170 GB for the cache.
  - - - Incoming
        
        20,000/second
      - Outgoing
        
        200/second
    - - 15 TB (30 billion object, with 500 bytes each)
    - - <= 170 GB
    - - Incoming
        
        100 KB/second
      - Outgoing
        
        10 MB/second
- - - - Since the structure of our data format is relatively fixed, and most of the relationships are simple key value pairs. We can use relationship database for storage
    - - We can have one or several Cache servers in from of the DB and after the application server to handle fast read throughput.
      - We can using Load Balancers in between (1) client and application servers, and (2) between application servers and the caches.
      - We can use replication handle most of the fault tolerance, and have several layers in the application server, cache, and Load Balancer layers. (master nodes handle write, and then pass to the slave nodes. slave nodes only need to handle read requests, and take the position of master node when it was down).
    - - We save the key as the shortened URL id (7 bytes), and the value as the original URL (8 bytes?) in a table.
  - - - Key: Hash: varchar(16)
      - Values:
        OriginalURL: varchar(512)
        CreationDate: datetime
        ExpirationDate: datetime
        UserID: int
    - - Key: UserID: int
      - Values:
        Name: varchar(20)
        Email: varchar(32)
        CreationDate: datetime
        LastLogin: datetime
- - - - Since we don't save too much key on Cache, so even when the cache is done and lost some keys, we don't worry too much (cause the options are huge).
    - - Using two tables to store keys: one for visited, and one for unvisited. We can update the table as soon as the key is visited
        :check:
        As soon as the key is loaded to memory of key DB, then they are sent to the used table, so servers are guaranteed to use different keys.
- - - - 170 GB: 20 QPS for read, which means 1.7 billion queries per day. Thus 20% of this is about 170 GB, assuming that each request object takes 500 bytes.
        
        Modern server has 256 GB memory, so this can fit in one.