[System Design] Process

This can be a web facing service, a RESTful API, a peer-to-peer desktop app, and so on.

Examples : 

• Design a URL shortening service like bit.ly.
• How would you implement the Google search?
• Design a client-server application which allows people to play chess with one another.
• How would you store the relations in a social network like Facebook and implement a feature where one user receives notifications when their friends like the same things as they do?

The idea of these questions is to have a discussion about the problem at hand. What’s important for the interviewer is the process, which you use to tackle the problem.

you should have a strategy for how to approach the different situations.

system design process + knowledge and intuition around designe scalable architecture

3 main factors of Sysmte : 

1. Availability
2. Latency 
3. Reliability

 

System Design Process : 

Scope->Abstract->Bottleneck->Scaling

1 User Case and Constraints : scope

1. identify what use cases the system needs to satisfy(Functional Requirement)
2. clarify the system's constraints (NFR)
1. the amount of traffic the system should handle
1. How to esimate :
1. amount of users
2. amount of operations per month/day/year
3. from these two umber to estimate traffic constraints : 
2. the amount of data the system should handle
1. How to estimate: 
1. what data do we need to store
2. how many data to store per day/month/year...then for example 5 years
3. estimate how many datas tu write and read per second

Ex: 

Design a URL shortening service like bit.ly.
Use case: 

1. Shortening : take a url => return a much shorter url
2. Redirection: take a short url=> redirect to the original url
3. Custom url
4. High availability of the system

Constraints:

1. Traffic:
1. New urls per month : 100 millon (10 ^8)
2. 1BN(10^9) requests per month
3. 10% for shortening and 90% for redirection
4. Requests per second : 10^9 / (60*60*24) ~ 400 :  40 shortening 360 redirections
2. Data Storage:
1. New url should be stored:
1. in 5 years : 10^8 * 10 * 6 = 6 billion new urls
2. 500 bytes per URL ; 
3. 6 bytes per hash
4. 500 * 6 BN = 3000 billions bytes = 3 TB for urls
5. 6 * 6 BN = 36  GB for hashes
2. New data writen per second : 40 * (500 + 6) = 20K write Requests 
3. New data read per second : 360 * (500+6) = 180K read Requests  
3. Bandwidth estimates: For write requests,

1. 200 new URLs every second, total incoming data for our service will be 100KB per second:

   200 * 500 bytes = 100 KB/s
4. Memory estimates: If we want to cache some of the hot URLs that are frequently accessed, how much memory will we need to store them? 
1. follow the 80-20 rule, meaning 20% of URLs generate 80% of traffic, we would like to cache these 20% hot URLs.

1. Since we have 20K requests per second, we will be getting 1.7 billion requests per day:

   20K * 3600 seconds * 24 hours = ~1.7 billion

   To cache 20% of these requests, we will need 170GB of memory.

   0.2 * 1.7 billion * 500 bytes = ~170GB

   One thing to note here is that since there will be many duplicate requests (of the same URL), our actual memory usage will be less than 170GB.

2.  

Ex2 : Twitter:

1. Use case:
1. what use case do we support ?
1. Basic
1. a user can twit a post (Text, Photo)
2. user can follow / unfollow other users
3. user can see followings' Twits  
2. Advanced:
1. like, comments
2. Transfer
3. nofication
4. inscription
5. authentification
2. Constraints:
1. how many users do we support ?
2. how many twits per user per day? 
3. how many requests do we need to support per second?
4. How much data do we need to store, write / read ?
5. 
   

2 Abstract Design

Sketch your main components and the connections between them (interfaces).

Ex:

1. Application service layer
1. shortening service
2. redirection service
2. Data storage layer : hash to url mapping
1. like a big hash table
1. read original url from short url which is a hash
2. write hash the original url and store 

Ex2: Twitter

1. User agregation 
1. User profile
2. Followings
3. Twits
2. Tweets agregation  
1. time stamp
2. content
3. media
3. inscription/authentification part is not special for Twitter, I will not consider them
4. Server
1. PostTweetSevice
1. User--post(user_id, text, img)--> Tweets agregation
2. getFollwingTweets service
1. User--followingTweets(user__id)--> User Agrregation --getFollowings( ): userIds -->  Twits agregation --> getTweets(userIds)
5. storage 
1. User agregation : map<UserId, UserProfil>, set<UserId follow User ID > 
1. write :  only write when follow/unfollow 
2. read: get floowings userID 
2. Twits agregation: map<tweetId,  Twits>, maps<userid, tweetID>
1. write: post
2. read: get twits of followings

3 Understanding Bottlenecks

one or more bottlenecks given the constraints of the problem.

your system needs a load balancer and many machines behind it to handle the user requests?

the data is so huge that you need to distribute your database on multiple machines ? 

What are some of the downsides that occur from doing that? 

Is the database too slow and does it need some in-memory caching?

Single point failure

Ex:

1. Traffic is probably not a bottleneck:
1. 40 shortening per second : just hash and save
2. 360 redirections per second : just read and internet access
2. data is a bottleneck : 
1. read write speed : 
1. 20K write Requests 
2. 180K read Requests 
2. size of storage : 5 years
1. 3 TB for urls
2. 36  GB for hashes

4 Use Scaling patterns on the bottlenecks  

"

always a balance between price and speed : you can have one super machine or you can have many cheaper machines.

"

"

load banlancer can have a public IP adresse then backend servers can use private adresse, so that they will not be accessed directly by external 

"

Application Service request: 

1. Split reads and writes into separate services : sever connection number limits
2. LoadBalance: for replications of servers
1. first ensure that the server they choose is actually responding appropriately to requests
1. Health check
1.  heart beat 
2. then use a pre-configured algorithm to select one from the set of healthy servers. 
1. with binding (Round Robin) : when you bind several IP adresses of you servers to the DNS server, you DNS will send response the requestes alternativly : server1 for request 1, server 2 for request 2 ...... then come back to server 1.....that's the simple way of load balance strategy. A problem with Round Robin LB is that we do not consider the server load
1. good : simple
2. bad : caching on server 1 is not reused : ex : you need to login again 
2. Weighted Round Robin: weight is the processing capacity, higher weighted servers receive new connection before
3. IP Hash: Hash modulo --> random
4. Least Connection : connection counter : the server with least connections receive requests first
5. Least Response Time : directs traffic to the servers with fewest active connections and the lowest average response time : most powerful among most aviliable
6. Least Bancwidth: least amount of traffic Mbps
3. if we need to replicat LoadBanlencer 
1. we can use DNS to balence the load already to different loadBanlencer
2. LoadBanlencer - loadBalencer  
1. active-active
2. active passive 
3. heartbeat between them
3. Message queue : to make a queue for tasks -->  scalling up! we can spin more tasks
1. will not lost tasks when we cannot handle a pik traffic
2. will help to handle unexpected problems 
1. ex : a task is pulled but the server crashed : queue will wait for a ack to notify the finish of the task, if not, timeout and that task to back to be pullable.
2. (a tasks is failing 10 tries in servers, could be put in to a special queue for later analyze)
4. Caching : reference principle: recently requested data is likely to be requested again. 
1. DB Query Caching (MySQL )
2. facebook : Memcached ： 
1. two pattern
1. Cache query results :  a result of SELECT * from USER can be cached in memory and reused in the server
2. Cache Objects
1. asynchronous processing possible
2. clean architect : repository<Object>
3. application just consumes the latest cached object and nearly never touches the databases anymore!
4. examples： 
1. user sessions
2. fully rendered de blog articles
3. activity streams
4. user-friend relationship
2. cache missed -> redo the select where and add into cache
3. cache could take too much memories and we need to "garbage collection"
1. remove expired data : by date, time...
1. cache hit will update the time stamp of hitted items and they will live longer
4. Cahing is "read heavy"
3. How much cache memory should we have? 20% 2-8 rules
4. Which cache eviction policy would best fit our needs?  
1. least recently used
2. least frequently used
3. FIFO : first in first out
5. How can each cache replica be updated?
1. cache miss-> add new entoy to the cahe
2. cache invalidation--> cross data center data consistency
1. Purge :  DB update will remove key from the cache immidiately
2. Ban : add key into a black list let user to check before accessing the cache
3. Short TTL : make all caches time to live short, so the cache expired quickly 
6. How can we write to cache  ?
1. write-through cache : data a write to cache and DB at the same time
1. two write --> latency
2.  write around cache: data are write only to DB, bypassing the cache, next read will be cache missed and read to cache
1. new inserted miss cach -> latency
3. write-back cach: data are writen only to cache then after a interval we storge them from cache to DB
1. fast but  risk of data loss
7. CDN : content Distribution Network is a kind of cache
5. Purging or DB cleanup
1. default expiration time for each link 
2. A separate Cleanup service can run periodically to remove expired links from our storage and cache. This service should be very lightweight and scheduled to run only when the user traffic is expected to be low.
6. Telemetry
1. Some statictics worth tracking
7. Sticky sessions or persistent sessions
1. you access the web site multiple times, you still go to the same backend server
1. Cookie solution
8. What are the different approaches for sending News Feed contents to the users?
1. Pull: Clients can pull the News-Feed contents from the server at a regular interval or manually whenever they need it. Possible problems with this approach are 
1. a) New data might not be shown to the users until clients issue a pull request 
2. b) Most of the time, pull requests will result in an empty response if there is no new data.
2. Push: Servers can push new data to the users as soon as it is available. To efficiently manage this, users have to maintain a Long Poll request with the server for receiving the updates. A possible problem with this approach is a user who follows a lot of people or a celebrity user who has millions of followers; in this case, the server has to push updates quite frequently.

Data Storage:

1. Data partition
1. mthod:
1. Range partitioning example: from 0 - 100, then 101 - 200....
2. List partitioning ex: user defined list into one partition : all europ countries
3. Composite partitioning: or example first applying a range partitioning and then a hash partitioning
4. Round-robin partitioning : by order : 0 to p0, 1 to p1, 2 to p2 ...
5. Hash partitioning: hash and modulo: when add a server, all data should be re distributed
1. Consistent Hashing ring: 
1. Hash(dataKey) --> , Hash(Node)--> to the ring  data store to next node on the ring
2. Balance : Use Virtual Node 
3. 
   
2. How would we handle hot users? 
1. 
   
2. Vertical scaling VS Horizontal scaling
1. Horizontal scaling means scaling by adding more machines to your pool of resources (also described as “scaling out”), 
2. vertical scaling refers to scaling by adding more power (e.g. CPU, RAM) to an existing machine (also described as “scaling up”).
3. Using NoSQL instead of scaling a relational database :Cassandra 
1. denormalize right from the beginning and include no more Joins in any database query.Joins will now need to be done in your application code
2. Denormalization to speed up read/ write.
   Ex : Feeds/activities followings.
   User send a new instagram post, we will store it to all followers home screens cache, so that speed up the read of new feeds. 
   
   
   

   
   

   
   

   O(N) write and O(1) read, like push / publish
   
4. File system : for img vedio, pdf....
1.  HDFS or S3
5. Being asynchronous
1. Do the time-cosumming work in advance and serve the finished work in a low request time
1. turn dynamic content into static content :  
1. pre-rendered HTML pages 
2. Key generate service can generate unique keys in advance, and when shortening URL, just take the non used keys. --> single point failure ?
1. yes, so we can use two server : even-numbered  and odd-numbered
3. Pre-generating the News Feed
2. Handle the task asynchronously : cannot do it in advance
1. have a queue of tasks that a worker can process : RabbitMQ
6. single point failure
1. Server Replication
1. Master-Master : 
1. write always to master 1 and Master 1 will replicate to master 2
2. or load balance  to Master1 and Master 2 then master replicate between them
2. DB : Replication
1. RAID : Redendant Array of Independent Disk : 
1. RAID0 is for speed up:
1. one logic disk two phisical disk
2. Large data file to write: stripping to two disks -> write takes time and into two will save time
2. RAID1 is for data redendancy:
1. one logic disk two phisical disk
2. data are mirrore in two disks 

DB sharding is for scalling write

DB redendance is for scalling read and security 

Data Aggregation:

Throttling: Rate limiting

• Server : 
• token bucket
• user 1's first request comes : create a token bucket for him
• if second comes inside 1 s, take a token
• if no request for 3 s, remove the bucket to release memory
• we don't need to keep the bucket for all users
• User side
• backoff and jitter (2s , later 4 s to retry)
• 
  

How to identify bottlenecks ?

• By testing : 
• Load test : load the system with 3-4 times traffic to test if scale well
• Stress test : identify a break point which will be down first with large traffic
• memory/CPU/IO/network

How to check the system's health ?

• monitoring based on : trace/events/log 
• Metric/ dashboard/alert
• latency
• traffic
• errors
• saturation

How to guarentee accurate results ? 

• Audit system
• send data to stream and batch system at the same time : lambda archtecture

Tips:

1. Everything is a tradeoff
1. balancing between time to market, system complexity, cost of development, cost of maintenance, availability, and many other things.
2. follow the System Design Process. You already know how to apply it, so we'll be brief. Don't skip steps, don't make assumptions, start broad and go deep when asked.
3. Be prepared for discussions about tradeoffs, about pros and cons. Be prepared to give alternatives, to ask questions, to identify and solve bottlenecks, to go broad or deep depending on your interviewer's preferences.

Examples:

How to design Netflix : http://highscalability.com/blog/2021/12/13/designing-netflix.html

     

 Ref: 

https://www.hiredintech.com/classrooms/system-design/lesson/52

https://www.educative.io/courses/grokking-the-system-design-interview

https://en.wikipedia.org/wiki/RAID