HLD Basics | Expertifie - sulabh84/SystemDesign GitHub Wiki
Reference Document
Four major parts of HLD
1) Requirement gathering
- Functional requirements
- Non-functional requirements - Consistency, Availability, Latency, Reliability, Serviceability, Manageability, Security, Scalability
2) Estimation
- Assumptions - like load on the system
- QPS (Query per second) planning - Read QPS, Write QPS
- Capacity planning - amount of cache or memory needed
3) Detailed design and architecture
- Apis
- Database -> SQL or NoSQL
- Tables in the database - Indexing
- High level architecture
- Load balancing
- Sharding
- Replication
- Caching
- Authentication / Authorization
- Client server connection
- CAP Theorem
4) Dashboards, Monitoring, Alerting and Maintenance
Scalability
Scaling up or down system resources based on traffic
Resources:
CPU
Memory
Hard Disk
Cache
Types of Scaling:
Horizontal Scaling
Vertical Scaling
Pros and Cons:
Initial cost is lesser - HS
Under utilization - VS
Managing data and load is difficult - HS
Migrations are easy - HS
Querying data and performing joins are easy - VS
Can't scale if hit on the maximum resource size - VS
Latency
turn around time from request sent to response received for a particular request
Note: latency should be low and throughput should be high for overall system not for one request
A B
---------
100 KM
Car -> 100 km/hr, 4 people
Bus -> 50 km/hr, 50 people
Latency ->
Car -> 1 Hr
Bus -> 2 Hr
Throughput ->
1 hr/4 -> .25 hr/person
2 hr/50 -> .04 hr/person
Availability
time system is up and running for a defined time period and responding within expected period of time
(5 9's availability) -> service will not be down more than 6 minutes within an year
Consistency
Response is identical for two similar request in the same instant
Reliability
Available or consistent (depends on the API contract)
Secure
Low latency
Desired response
Backups in case of data loss
Serviceability and Manageability
should be able to provide services to the end user, easily manageable and maintainable
Security
Prevention from attacks
- DDos attack
- IP checks - if you get more than X no of requests from a particular IP within a window then do not honor those requests.
- Man in middle attack
- someone is looking at the data over the network
- Encryption and decryption of data over network
- Hitting the request when keys are compromised
- 2 way SSL
- SQL Injection
Load balancer
- distributing the load/data between multiple instances of the app/service/server/database
- tracks the status of each of the servers involved based on the response distribute the load - if machine goes down then send request to other live instances
- three layer to put load balancers : web servers/ app servers / databases
Algorithms
- least connection : requests should be sent to the service which has least connection at a time
- least bandwidth : send the request where less size of data sent
- least response time: send request which respond fast
- round robin : even distribution of the requests
- waited round robin (Preferred) : based on the machine capacity like one machine can handle 200 tps and other can 500 tps
- IP Hash : based on the IP address send request to specific machine
Cache
Standard way to store the data near to the user so that response time is faster than the usual time
Hard disk -> Memory (RAM) -> L1,L2 Cache -> Registers
-------------------------------------------->
Cost increase
<--------------------------------------------
Time to fetch data increase
80-20 Rule:
- In general, 80% of data is queried 20% of the time and 20% of the data is queried 80% of the time
- 100GB hard disk then 20GB of Cache
Ways to store data into the cache and DB:
- Write around cache : Write happen in DB and cache is updated when data is read from the DB for the first time
- Pros : write will be faster than write through cache but slower than write back cache
good for write intensive cache
- cons : stale data because data updated only in DB but cache is not updated
- Write back cache : write the data into the cache during write call and return the success response and DB is updated async with cache. Read is from the cache if miss then call goes to DB
- Pros : writes will be faster
- Cons : if cache dies then might end up loosing data if data is not synced with DB
- Write through cache : write is performed db as well as cache before returning successful response
- Pros : Reads are faster for latest data
you won't return stale data
- Cons : writes will be very slow since write has to be performed on both DB and Cache
Eviction strategies:
Removing data from the cache if the cache is full
Least recently used : Remove least recently used data
Least frequently used : remove least frequently used data
Most frequently used
Most recently used : remove most recently used data
FIFO : remove data in the order the data was inserted
Time to live (TTL): if data is not updated for a specific time then remove it so that stale data will not be served by cache
Cache Hit : data read successfully from cache
Cache Miss : data is not present in the cache and call goes to DB to fetch the data
Calculating Cache hit and miss avg time:
Time for all the requests to return the response from the cache within a window of H hours
Considering 80-20 rule
There are total R requests in H hours then the avg time for each request to return the response will be:
Cache -> X seconds/request
DB -> Y Seconds/request
Cache hit -> 0.8R
Cache miss -> 0.2R
Avg time = (R*x + 0.2R*Y)/R
Partitioning/Sharding
- Distribute data across different machines
Advantages
- load can be distributed across machine
- performance of the system will improve
- availability is relatively higher
- distribute data across multiple machines
Scaling:
Horizontal (Multiple Machines) -> Partitioning is required
- Vertical partitioning
- Complete table will be stored in single machine
- 1st Partition (Machine-1) -> User table
- 2nd Partition (Machine-2 or Machine-1)-> Order table
- 3rd Partition (Machine-3 or Machine-1) -> Inventory table
- Pros
- Its easier to maintain data in one machine
- Cons
- You can't insert more data if machine reaches to full capacity
- Joins are difficult, data has to be fetched in the memory and then query can be performed on another partition
- Horizontal partitioning
- Distribution of the same table is across multiple machines
- 1st Partition -> User/Order table (A - F)
- 2nd Partition -> User/Order table (G - P)
- 3rd Partition -> User/Order table (Q - Z)
- 4th Partition -> Inventory table (A - P)
- Further partition on the table can be made easily created if machine reaches its capacity to store more data
- 5th Partition -> Inventory table (Q - Z)
- Pros
- scaling up and distributing of data is always possible
- Cons
- Difficult to maintain the data across multiple machines
- Query different machines if you have to fetch the data for multiple users
- Joins can be slower
- Different ways of horizontal partitioning
- Hash based approach
- Based on Userid (Int64)
- Hash can be equivalent to no of machines (10 partition)
- UserId%10 -> Partition number to store data
- Pros
- Easier to figure out shard number and no need to maintain the mapping
- Load will be distributed in a better way across machines
- Cons
- if you plan to add another machine then you need to bring your complete system down and re-distribute the complete data again
- Solution : Consistent Hashing
- Range based approach
- Based on Region
- Based on Date
- Based on Initials of the name of the user
- Partition is based on range so whenever we need to add more partition then only the effected partition needs to be down no need to bring down the other partition
- Pros
- Easier to manintain the data if you know the shard number
- Scaling and re-distribution of data while adding more partition is much more easier compared to hash based approach
- Cons
- Load might not be evenly distributed
- Data might not be evenly distributed
- Mapping has to be maintained to query the data from a particular shard
- Note: we can use Hash and Range based partition in same solution:
Ex: first partition is based on Continent [Range]
Second partition is based on Country [Range]
Third partition is based on UserName [Range]
Fourth partition is based on UserId [Hash]
Vertical (Single Machine) -> no partitioning required
Replications
- Creating a copy of same data to handle fault tolerance, having a better distribution of load and making multiple copies of same data in case of disaster recovery
-
Consistent Hashing
Problem: In Hash based partitioning, if new node added then we need to re-balance the data across all the partitions and this will require a down time of complete system
Solution: Consistent Hashing
Disadvantages of Consistent Hashing
- There can be a lot of load on one particular shard because of the way we have kept our shards in the ring based on the user id
- if one complete shard along with its replication goes down then there is no way to server the request
Solution: Modified Consistent Hashing
Client Server Connection
1) Http Connection: Client connects with the server. Handshake is performed between client and server and then the request is sent from client to the server
Three steps for communication between Client and Server:
- Connection Establishment: Handshake
- One way handshake
- Two way handshake
- Processing request
- Connection Closed
Limitation:
- Server can't push the data to the client unless client sends the request for receiving response
- Every time you send a request there is a handshake and that will increase overall latency of the request
Example:
- Uber Driver and Uber Rider
- Uber Rider what to check the location of the Driver
- Uber Rider has to make connection every second to get the location
- So every time Uber Rider needs to make connection first
- Every time Uber Rider makes connection it will spend 500 millis for establishing connection
- this is an overhead
2) BOSH (Bi-direction stream over Synchronous HTTP) : When the request is sent from the client to the server, the request will be hold by the server for a small time window and if the data on the server has been updated within that time then the response is sent immediately else the data present in the server is sent as a response once the time window is crossed.
- Advantages
- less no of connections are created compared to above approach
- Request is hold at the server and response is returned on the update at the server, also continuous polling is in control compared to the above approach
3) Web Socket Connection: bi-directional connection where both client and server initiate the request and server can push the data to the client even if the request is not sent from the client
4) Long Polling connection: keep polling the data from the server at a regular interval of time and ignore the response if the response returned from the server is same as before.
Questions:
- Difference between Web Socket and WebRTCs?
Security
- SSL (Secure socket layer) : Share certificate with your client and you ask your client to send the certificate whenever the request is sent and Server will validate if the certificate shared by the client are valid certificates or not.
- PGP (Pretty good privacy) : Encrypt the request with the public key shared by the partner and sign the request with your private key. Partner will unsign the request with your public key and decrypt the request with their private key
- Payload level encryption / decryption
- Both the parties have to share their public keys and private key is used to decrypt the request, public key is used to encrypt the request
- OAuth : Generate tokens and send tokens as part of the request to the server. Tokens are validated and then request is processed.
Attacks:
- DDOS : Block the IP if you receive more than the threshold value from particular IP within a time window
Indexing on databases
- Faster retrieval of data
- Might want to put some constraints based on the indexes in your table
Disadvantages:
- Makes your writes slow, Indexes needs to be update every time there is write
- overall throughput / latency of the system might decrease if you have too many indexes
Note: Avoid indexes if system is write heavy system and prefer to create indexes if the system is read heavy system and reads are not based on the primary key
SQL Vs NoSQL
SQL ->
- Relational DB which satisfies ACID properties
- Atomicity
- Consistency
- Isolation
- Durability
- SQL DBs are preferred when the table are well structured and you want to maintain the transaction functionalities in the DB
NoSQL ->
- key value stores and preferred over SQL DB whenever the data is not well structured and there is good chance of data fields getting modified/added in future
- NoSQL DBs are preferred in distributed system environment because of some of the properties they provide out of the Box required for distributed systems
- Types:
- Graph DB
- Document DB
- Columnar DB
CAP Theorem
C -> Consistency
- All nodes in the cluster of distributed system has latest data anytime when we query
A -> Availability
- Every node which is live and responsive should return the response within expected time
P -> Partition Tolerance
- even if there is network failure or disturbance in a distributed system environment then user should be able to receive response in the expected time
Note:
- Consistency over availability (Consistent)
- Availability over Consistency (Eventually Consistent)
