Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Overview

  • Scoping out the question is important
  • Do not assume anything! Always ask for clarification!
  • Handling non-functional part of a design question might be more important:
  • Scalability
  • Throughput
  • Storage Capacity
  • Performance
  • Latency
  • Availability
    • Improving the availability of e.g. Twitter from 99.9999% (5 minutes/year) to 99.99999% (30 seconds/year) might not worth the effort! Tradeoff here is important.
Back of the envelope calculation

This is the calculation that you do on a piece of paper or on your mind instead of formally calculate it!

Design a Rate Limiter

  • It is used for security reasons
  • It is used for business reasons:
    • For example you cannot upload more than 20 videos in 24 hours!
      • You can upload lots of videos and use all the capacity available!
    • You cannot post more than for example 1,000,000 comments on a post
    • The main reason is essentially preventing bots to make too many request in a short period of time!

You can protect each microservice! However, it might be better to implement it as a bigger entity!

  • There could be multiple instances of a particular API and these need to be in sync with a time limiting service! Therefore, implementing a time limiter for each instance does not satisfy the requirements!

Discussion:

  • Implement the rate limiter on backend!
  • When the limit is reached, for a request we should send a 429 (rate limit error) HTTP response (this is not a server error! Instead it is a client error!)
  • Note: Can we implement a rate limiter from client-side code? Yep!
    • It is not sufficient! Because they can use our API!

How do we identify a user?

  • Should we use userId?
  • Instead it should be more general like IP address!

What is the latency/throughput implications?

What is the Storage implications?

What if the Rate Limiter goes down?

  • Fail-Open: if something in our system goes down, the whole system should continue working as if that component never existed
  • Fail-Closed: if something in our system goes down, the whole system should go down!

Let's design it now!

  • We need some type of storage to store our rules! It needs to be persistent!
  • Then, how the rate limiter knows for example how many videos are uploaded withing last 24 hours?
    • In-memory KV store like Redis cache.
  • What kind of algorithm for rate limiting?
    • Look at the Token Bucket and Sliding Window Counter algorithms

Design TinyUrl

Functional Requirements:

  • A long url should be mapped to a shorter url
    • It might be better to map to some words like happySOMETHING which is not always possible
  • Users might delete a Url if they own it which needs keeping tracking of the ownership.
  • Every Url should be expired after some time!
  • What would happen if multiple users attempt to map the same URL to a tinyUrl? Should all of them be mapped to the same TinyUrl?\
    • It is better to map it to different TinyUrl to for example have different expiration date for every owner

Non-Functional Requirements:

  • Make it reliable
  • What about the scale?
    • Is read more frequent or write?
    • Something 1B/Month write is reasonable?

Discussion:

  • If we can use digits, lowercase and uppercase, it gives us 62 characters to choose from: we can have 8-character urls which is about 256T. It then gives us almost 20000 Years! :|

  • 1B/Month is equal to roughly 385 write/second.

  • If write to read is 1:100 ratio, we end up with 38500 read/second.

  • What about the storage?

    • Let's say average of 100 characters per original Url and then we need to store userId and other stuff: around 1000 bytes/url

  • What kind of storage are we going to use?

    • More frequent reads
    • NoSQL is better since they are designed to be scalable.
    • It does NOT need complicated join queries
    • We do NOT need ACID or atomic transactions
    • Instead we need eventual consistency

Design:

  • A URL generator
  • Users will hit the main server first
  • The data will be stored in database
  • Since read are more frequently, we will use a cache for the database (in-memory cache like Redis)

Caching:

  • What kind of algorithm can we have? LFU or LRU
    • LRU seems better => A URL may experience a surge in traffic due to a trend, followed by a decline as the trend diminishes over time.
  • What should be the size of the cache?
    • 1TB/Month for write. However, not everything will be saved in the cache => 256GB for memory should be fine.

Url generation:

  • Hashing has the collision problem.
  • We can generate a list of 8-character and store them in a database. Whenever a new request comes in, we can use this list. When we fetch as key, we mark it as used!
    • Why not just easily remove a used key? After the key expires, we can re-use it.
  • What if two request goes to the database? How do we prevent assigning one key to both of them?
    • Atomic transaction in ACID will take care of it.

Remove expired urls:

  • It does not hurt if some urls get deleted after 10 minutes or so!
  • We need a cleanup service that run every 10 minutes for example.

Scalability

  • Use load balancer
  • Partition our database as well as replicas

How does it work in action?

  • If you browse to the tinyUrl, the server sends a 300 code, meaning the resource has been moved. There are two options here:
    • Code 301: the resource has been moved permanently to the new Url. The browser cache this information. Next time the browser automatically will send the complete Url.
    • Code 302: the resource has been temporarily moved to the new Url. The browser does not cache it.