System Design
Published: 2021-05-29 09:49:48

System Design study guide / interview prep for me


Content here is **not original**. It is is a summary of the following sources:
- [freeCodeCamp - System Design Interview Question] (https://www.freecodecamp.org/news/systems-design-for-interviews/) (really comprehensive 20/10 will recommend you give it a read)


#TOC
<u> API design </u>
- [Http methods](#http-methods)
- [Standard Error Codes](#standard-error-codes)
- https://stackprint.io/post/common-api-design-interview-questions

<u>Basics</u>
- [Storage: Memory VS disk](#memory-vs-disk-storage)
- [Latency VS Throughput](#latency-vs-throughput)


<u>System Availability</u>
- [Availability: Intro](#availability-intro)
- [High Availability](#high-availability)

<u> Caching </u>
- [Why caching](#why-caching)
- [Use Cases](#caching-use-case)
- [Caching Strategies](#caching-strategies)

<u> Proxy </u>
- [Proxy & how they work](#proxy-basics)
- [forward proxy VS reverse proxy](#forward-vs-reverse-proxy)


<u> Load Balancing </u>
- [Why load balancing](#why-load-balancing)
- [server selection strategy](#load-balancing-strategy)
  - round robin, weighted round robin
  - load based server selection
  - IP hashing based selection
- Adding servers / handling failing servers

<u> Database design </u>
- [CAP theorem](#CAP-theorem)
- [Scaling: vertical VS horizontal](#vertical-vs-horizontal-scaling)
- [Relational Database](#relational-database)
  - [ACID properties](#rdbms-acid)
- [Non-relational database](#non-relational-database)
  - [BASE properties](#nosql-base)
  - [Types of NoSQL](#types-of-nosql)
      - Graph database
      - Document Store
      - key-value store
      - column-family DB
      - Search Engine DB
- [NoSQL VS relational](#nosql-vs-relational)
- Replication & Sharding

<u>Leader Election</u>
- [Leader Election - Basics](#leader-election-basics)

<u> Endpoint protection </u>
- Use cases
  - protecting against DOS
- rate-limiting

<u> pub-sub Messaging / MQs </u>
- [Benefits](#mq-benefits)
- Use case / purpose
- pub/sub messaging
- comparison to DB


<small><u>References to getting started</u></small>
- <small>[IGotAnOffer - Database: system design interview concepts](https://igotanoffer.com/blogs/tech/databases-system-design-interview) </small>
- <small>[freeCodeCamp - System Design interview concepts](https://www.freecodecamp.org/news/systems-design-for-interviews/)</small>
- <small>[medium - 25 java software design questions](https://medium.com/javarevisited/25-software-design-interview-questions-to-crack-any-programming-and-technical-interviews-4b8237942db0)</small>
### <a name="http-methods">HTTP Methods</a>
- GET
  - retrieve resources
- POST
  - submit **new data**
- PUT
  - **update** / replace existing data
- DELETE
  - removes data 
- PATCH
  - modify resource. *only contains changes* not whole resource
- OPTIONS
  - requests available communication methods
- HEAD
  - request resource metadata without retrieve full resource representation

<small> reference: [SO](https://stackoverflow.blog/2020/03/02/best-practices-for-rest-api-design/) & [stackprint](https://stackprint.io/post/common-api-design-interview-questions)</small>

### <a name="standard-error-codes">Standard Error Code</a>
- 400 Bad request
  - client side input fail validation
- 401 Unauthorized
  - user not authenticated
- 403 forbidden
  - user authenticated but not privileged to access resources 
- 404 Not Found
  - resource not found
- 500 Internal Server Error
  - generic server error. shouldn't be thrown explicitly.
- 502 Bad gateway
  - invalid response from upstream server
- 503 Service Unavailable
  - something unexpected happen on server side (server overload, some parts fiail(
<small> reference: [SO](https://stackoverflow.blog/2020/03/02/best-practices-for-rest-api-design/)</small>



### <a name="memory-vs-disk-storage">Storage: Memory VS Disk</a>
> <u>Disk</u> is persistent. (when power is off, data will "persist").
<u>RAM</u> is transient. When lost power memory is wiped away.

If data is useful only during session of server then keep it in Memory.

> Keeping it in **RAM is much faster and less expensive** than writing to persistent database. 

### <a name="latency-vs-throughput">Latency VS Throughput</a>
> <u>Latency</u>: duration for action to complete / produce result
<u>Throughput</u>: maximum capacity of system / work done in unit time.

- Latency:
  - load site fast & smoothly
  - fast lookups
  - avoid pinging distant servers. 
- Throughput
   - can improve by reducing *bottleneck*
   - system will only be as fast as its slowest *bottleneck*
   - increase by improving *slowest bottleneck*


Hard ware definition from   [compritech](https://www.comparitech.com/net-admin/latency-vs-throughput/):
> <u>Latency</u>: time taken for packet to be transferred across network
<u>Throughput</u>: quantity of data being send & recevied per unit time

### <a name="vertical-vs-horizontal-scaling">Scaling: Vertical VS Horizontal</a>
> **Vertical Scaling**: adding compute (CPU) and memory (RAM, Disk, SSD) resources to a single computer.
**Horizontal Scaling**: adding more computers to a cluster

- Vertical
  - fairly straightforward
  - much lower overall memory capacity
- Horizontal
  - higher overall compute and storage capacity
  - sized dynamically without downtime
  - most popular DB model hard to scale horizontally. 

### <a name="availability-intro">Availability: Intro</a>
> availability is like resiliency of system. fault tolerant system makes an available system. 

<u> Uptime </u>
Measured using (uptime): percentage time system's primary function is available in given window of time

<u>Service Level Agreement / Assurance </u>
set of guaranteed service level metrics. 

### <a name="high-availability">How to achieve High Availability</a>
> Reduce or eliminate **single points of failure**
This is done by designing **redundancy** into the system. 

Eg. two or more servers to provide services. 

### <a name="why-caching">Why Caching</a>
> Caching helps reduce **latency** of system. 

- app can perform faster
  - faster to retrieve data from memory than disk

Works best when
> 1. store static / infrequently caching data
2. source of change is single operations rather than user-generate operations

If **data consistency & freshness is critical**. Caching may **not be optimal** unless cache is refreshed frequently (refresh cache frequently may not be ideal either)

### <a name="caching-use-case">Caching: Use Case</a>
> 1. when using certain piece of data often
2. backend has computationally intensive work (cache reduces complexity to O(1))
3. server makes multiple netwrk requests & API calls 

Example
- CDN (content delivery network)
  - caches content (images / videos/ webpages) in proxy server located closer to end user than origin server
  - can deliver content more quickly. 


### <a name="caching-strategy">Caching Strategy</a>
> deals with the "write" operations of cache.
1. keep cache & DB in sync
2. should it be done synchronously or asyncrhonouslt
3. data eviction - Which old records to "kick out" for new data?

Caching Strategies
- LIFO
- FIFO
- LRU
- LFU 
 ### <a name="proxy-basics">Proxy:basics</a>
*proxy*: basically a middleman between client & origin server. 

There are 2 kinds of proxies
1. forward 
2. reverse
![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9344cfhsnt8pth9gmfuj.png)
Forward
- computer make requests to sites on internet
- proxy server intercepts request
- communicate to web server on behalf of clients 

![alt text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ro2x3wczwuz2xl8vlstn.png)
Reverse
- client send request to origin server of website
- requests intercepted at network edge by reverse proxy server
- reverse proxy sends request to & receive response from origin server

### <a name="forward-vs-reverse-proxy">Forward VS Reverse Proxy</a>
*proxy*: basically a middleman between client & origin server. 

<u> How proxies work</u>

> <u>Forward</u>: sits in front of client, no origin server communicates with specific client. Server has no knowledge of client
<u>Reverse</u>: sits in front of origin server, no client communicate directly with origin server. Client has no knowledge of server. 


- Forward proxy
  - avoid company browsing restrictions. 
    - clients connect to proxy rather than directly to sites they are visiting 
  - block access to certain content
    - school network, configure to connect to web via proxy that blocks stuff
  - privacy
    - IP address of client is harder to tarce, only IP address of prxy server is visible

- Reverse proxy 
  - load balancing
    - distribute incoming traffic among different origin servers
  - protection from attacks
    -  web site/service never needs to reveal IP address of original server
    - harder to have targeted attack against origin server (eg. DDoS). hackers can only target reverse proxy. Reverse proxy will have tighter security & more resources.
  - Global Server Local Balancing
    - website distributed on several servers around the globe. 
    - reverse proxy send clients to server geographically closets to them. 
  - Caching
    - reverse proxy can cache content -> faster performance 
  - SSL encryption
    - reverse proxy can decrypt all incoming requests & encrypt all outgoing repsonses 
    - free up valuable resources on origin server. 



<small>Reference: [cloudflare](https://www.cloudflare.com/learning/cdn/glossary/reverse-proxy/) </small>

### <a name="why-load-balancing">Why Load balancing</a>
> Maintain **availability** & **throughput**
By **distributing incoming request loads across multiple servers**

When server get lots of requests it can:
- slow down (throughput reduces, more latency)
- fail (no availability)

Load Balancing helps this by **Distribute incoming traffic among origin servers**

### <a name="load-balancing-strategy">Load Balancing Strategies</a>

Probability server selection
- Round Robin
  - loop through servers in fixed sequence
- Weighted Round Robin
  - assign different weights / probabilities each server. 
  - traffic split up according to weights
- Load-based server selection
  - monitor current capacity / performance of servers
  - send request to server with highest throughput / lowest latency.
- IP Hashing based selection
  - hash IP address of incoming request
  - use hash value to allocate server 
- Path / Service based selection
  - route requests based on path / service provided.


### <a name="CAP-theorem">CAP Theorem</a>
> any distributed DB can only satisfy 2 of three features
- **Consistency**: every node responds with most recent version of data
- **Availability**: Any node can send a response
- **Partition tolerance**: system continues working even if communication between any of the nodes is broken

DB is usually **CP or AP database**. Since cannot garuntee statbility of network, P is non-negotiable. 

### <a name="relational-database">Relational Database</a>
> database using a **relational data model**, organizes data in tables with rows of data entries and columns of predetermined data types. 

<u> Use when</u>
- many-to-many relatinoship between entries
- data needs to follow predetermined schema
- consistent transactions are important
- relationship between data always need to be accurate

### <a name="rdbms-acid">ACID properties</a>
- Atomicity
  - transaction is atomic / smallest unit. 
  - all instructions in transaction will execute or non at all
- Consistency
  - If DB in initially consistent, it should remain consistent after every transaction
    - eg. write operation (transfer money from A to B) failed & transaction not rolled back. Db is inconsistent because amount of money between A &B (A+B) not equal before & after transaction
- Isolation
  - multiple transaction running concurrently they should be affected by each other
    - result should be same as result obtained if transactions running sequentially.
- Durability
  - changes committed to DB should remain even in case of software & system failure. 

<small> Reference [educative](https://www.educative.io/edpresso/what-are-acid-properties-in-a-database) & [tutorialspoint](https://www.tutorialspoint.com/dbms/dbms_transaction.htm)</small>

### <a name="non-relational-database">Non-relational Database</a>
> also known as NoSQL database. 
at core, DB hold data in hash-table like structure.
**Use cases**: caching, environment variables, configuration files / session state
**Use environment**: in memory & persisten storage

Since their structure is like hashtable there is minimal over head
- extremely fast
- simple & easy to use


### <a name="nosql-base">NoSQL Base properties</a>
> **Basically available**: system guarantees availability
**soft state**: state of system may change over time even without input
**eventual consistency**: system will be consistent over very short period of time unless inputs are received

### <a name="types-of-nosql">Types of Nosql DB</a>

- Graph database
  - many-to-many realtinoships
  - fase at following graph edges
- Document Store
  - isolated documents, retrieve by a key
  - documents with different schemas that are easy to update
  - easy to scale
- Key-value store
  - like a very large hashtable
  - opaque values (DB has no notion of what is stored in value only provides read, overwrite and delete operations)
  - simple operations (no schemas, joins or indices)
  - minimal overhead - easy to scale
  - **suitable for caching implementations**
- column-family DB

### <a name="nosql-vs-relational">NoSQL VS Relational</a>

- NoSQL
  - dynamic schema. 
    - dev can use "unstructured data" can build application without defining schema
  - Scaling
    - scales horizontally over cheap commodity servers
  - Simple Operations
    - data retrieval is simple
  - Cheap hardware
   - app deployed to commodity hardware like public clouds

- SQL
  - workload volume is consistent
  - ACID garuntees required
  - data is predictable & highly structured
  - data est expressed relationally
  - write safety required
  - app deployed to large high-end hardware


https://www.mongodb.com/scale/nosql-vs-relational-databases
https://www.mongodb.com/nosql-explained/when-to-use-nosql
https://docs.microsoft.com/en-us/dotnet/architecture/cloud-native/relational-vs-nosql-data#considerations-for-relational-vs-nosql-systems

### <a name="leader-election-basics">Leader Election: Basics</a>
> When system scales horizontally, some tasks require precise coordination between nodes. Where there is *leader* nodes directing *follower* nodes.

Leader Election algo
> how cluster of nodes without leader communicate with each other & choose one to be leader.

algo executed when cluster starts or when leader node goes down. 

<u> Use Case </u>
- Any node can be leader, no single point of failure required to coordinate system
- System doing complex work that need good coordination 
  - eg. compute how protein folds. cluster needs leader node to assign each node to work on different part then add results together
- System executes many distributed writes to data & requires *strong consistency*
  - no matter which node handles request user will always have most up-to-date version of data. 
  - leader creates consistency by being source of truth on what the most recent state of system is. 

<u> Drawbacks </u>
- split brain
  - bad implementation -> 2 nodes controlling system
- single point of failure / bottleneck
- leader starts making bad decisions entire system will follow

<small> Reference: [iGotAnOffer](https://igotanoffer.com/blogs/tech/leader-election-system-design-interview)</small>

### <a name="mq-benefits">MQ Benefits</a>
- Resilience
  - app specific faults wont impact system
    - if one component fails, all others can continue interacting with queue, processing / producing messages. 


<small>Reference: [IBM](https://www.ibm.com/cloud/learn/message-queues)</small>