system design

Load Balancer

Distributes incoming network traffic across multiple servers to ensure reliability and performance

Caching

Storing frequently accessed data in a temporary location for faster retrieval

CDN (Content Delivery Network)

A distributed network of servers that deliver content to users based on their geographic location

Database Sharding

Partitioning a database into smaller

Horizontal Scaling

Adding more servers to handle increased load

Vertical Scaling

Upgrading a single machine’s resources (CPU

Microservices

An architectural style where applications are composed of small

Monolithic Architecture

A single-tiered application structure where all components are interconnected and deployed together

Message Queue

A system for asynchronously passing messages between components or services

API Gateway

A single entry point that manages requests

Rate Limiting

Restricting the number of requests a user or client can make to prevent abuse

Replication

Creating copies of data across multiple servers for redundancy and high availability

CAP Theorem

States that in distributed systems you can only have two of three: Consistency

Consistency

Every read receives the most recent write or an error

Availability

Every request receives a response

Partition Tolerance

The system continues to function despite network partition failures

Eventual Consistency

A consistency model where all replicas become consistent over time

Proxy Server

A server that acts as an intermediary for requests between clients and other servers

Reverse Proxy

A server that forwards client requests to backend servers

DNS (Domain Name System)

Translates human-readable domain names into IP addresses

Data Replication

Copying and maintaining database objects in multiple databases

Failover

Automatically switching to a standby system when the primary system fails

Heartbeat

Regular signals sent between systems to monitor health and availability

Throughput

The number of requests a system can handle per second

Latency

The time it takes for a request to travel from the client to the server and back

Load Testing

Testing how a system performs under expected user load

Stress Testing

Testing a system beyond normal capacity to observe its breaking point

Autoscaling

Automatically adjusting the number of servers based on current load

Session Management

Mechanism for tracking user interactions across multiple requests

Data Partitioning

Dividing data into segments for scalability and performance

Indexing

Creating data structures that improve the speed of data retrieval

Write-Ahead Log (WAL)

A method ensuring data integrity by writing changes to a log before applying them

Distributed System

A collection of independent computers that appear to users as a single system

Leader Election

Process of designating one node as the coordinator among distributed systems

Heartbeat Mechanism

Method used by systems to check if nodes are alive or failed

CDN Edge Server

Server close to users that caches content for faster delivery

API Rate Limit

Control mechanism to restrict the number of API calls per user or app

Event-Driven Architecture

Architecture based on events triggering services or actions asynchronously

Idempotency

Ensuring that performing the same operation multiple times has the same effect as doing it once

Service Discovery

Mechanism by which microservices locate each other dynamically

Circuit Breaker

Pattern that prevents repeated failed calls to an unresponsive service

Database Index

A data structure that speeds up data retrieval at the cost of additional writes and storage

Content Hashing

Generating a unique hash to detect changes or duplicates in content

Distributed Cache

A cache system spread across multiple machines for scalability

Data Lake

A centralized repository for storing large amounts of raw data in native format

Blob Storage

Storage for large binary files like images

Request Queue

Stores requests temporarily until they can be processed

Strong Consistency

Guarantees that all users see the same data at the same time

Soft State

System state that may change over time even without input due to eventual consistency

Stateless Architecture

Design where each request is independent and does not rely on previous interactions

Stateful Architecture

Design where the system keeps track of client state between requests

CAP Theorem:

States that it is impossible for a distributed software system to simultaneously provide more than two out of three of the following guarantees (CAP): Consistency, Availability, and Partition tolerance.

Consistency - Every read receives the most recent write or an error

Availability - Every request receives a response, without guarantee that it contains the most recent version of the information

Partition Tolerance - The system continues to operate despite arbitrary partitioning due to network failures

If there is a partition, your system has to choose between being available or consistent

Consistent Hashing

when the hash table is resized (e.g. a new cache host is added to the system), only 'k/n' keys need to be remapped where 'k' is the total number of keys and 'n' is the total number of servers

ACID Properties

In the context of transaction processing, the acronym ACID refers to the four key properties of a transaction: atomicity, consistency, isolation, and durability. All changes to data are performed as if they are a single operation.

SHA-256

A hashing algorithm that produces a 64 character string

Whats the memory of a high end commerical server?

256GB

How many seconds in a day

86400

How many connections can a server hold?

about 500

HDFS or GlusterFS.

a network-attached storage filesystem that allows you to pool storage resources of multiple machines. In turn, this lets you treat multiple storage devices that are distributed among many computers as a single, more powerful unit.

How full should storage get

80%

How may disk space does a modern server have

4TB

How many bytes in a char in a word

4 bytes

How many ids fit in one byte, two bytes, 3 bytes, 4 bytes....

1 byte = 256

2 byte = 65,000

3 bytes = 16 million

4 bytes = 4 billion

5 bytes = max

Back of the envelope

1. Traffic estimates

2. Storage Estimates

3. Bandwidth estimates

4. Memory Estimate

How many bytes in epoch time?

4 bytes

Unit Tests

testing software with a small piece of source code (unit, component, and/or function

Integ Tests

Integration testing is the phase in software testing in which individual software modules are combined and tested as a group. Integration testing is conducted to evaluate the compliance of a system or component with specified functional requirements

End to End tests

A helper robot that behaves like a user to click around the app and verify that it functions correctly.End to End: A helper robot that behaves like a user to click around the app and verify that it functions correctly.

Load Tests

Load testing is the process of putting demand on a system and measuring its response. An example of a test is to concurrently download large files

Security Tests

Security testing is a process intended to reveal flaws in the security mechanisms of an information system that protect data and maintain functionality as intended

NP-complete problems

a class of computational problems for which no efficient solution algorithm has been found. Polynomial-time algorithms are considered to be efficient, while exponential-time algorithms are considered inefficient.

polynomial time: n^10

exponential time: 10^k

ex: Traveling salesman

N Choose K problems

C(n, k)= n!/[k!(n-k)!]

Processes vs threads

Processes have their own heap, they don't share memory

Threads have share a heap. Starting a thread is cheaper, as fewer resources need to be allocated. The threads within a process are concurrent and can execute in parallel

Semephore

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system

Concurency Issues

Lost Update: if a resource is read and updated by 2 transactions, the first update is lost.

Dirty Read Problem: A dirty read occurs when one transaction is permitted to read data that is being modified by another transaction which is running concurrently but which has not yet committed itself.

Unrepeatable read: n a transaction calculates some summary (aggregate) function over a set of data while other transactions are updating the data.

Mutexes

allow one thread access to a section of memory at any one time. If one thread locks the mutex, any other lock attempts will block until the first one unlocks

Context Switching

This is a feature of a multitasking operating system and allows a single CPU to be shared by multiple processes.

Resource Allocation For threads or Processes

In a multitasking environment, a process is switched out of the CPU so another process can be run. The state of the old process is saved and the state of the new process is loaded. On a pre-emptive system, processes may be switched out by the scheduler.

Scheduling in an OS

the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process

Routers

One of the primary jobs of a router is to assign IP addresses to the computers on a home network. The router has a "pool" of IP addresses that it keeps track of. When a computer connects to it and asks for an IP address, the router picks an IP address from the pool and assigns it to the computer.

One of the primary jobs of a router is to assign IP addresses to the computers on a home network. The router has a "pool" of IP addresses that it keeps track of. When a computer connects to it and asks for an IP address, the router picks an IP address from the pool and assigns it to the computer.

Routers can be used to create networks

Domain Names

Domain Names are names of locations on the internet. They map to an IP address and can be used to lookup an ip address in a dns sesrver.

Firewalls

prevents unauthorized access to or from a private network. monitors and controls incoming and outgoing network traffic based on predetermined security rules.

How does Google Search Work?

Crawling: Google searches the web with automated programs called crawlers, looking for pages that are new or updated. Google stores those page addresses (or page URLs) in a big list to look at later. We find pages by many different methods, but the main method is following links from pages that we already know about.

Indexing: Google visits the pages that it has learned about by crawling, and tries to analyze what each page is about. Google analyzes the content, images, and video files in the page, trying to understand what the page is about. This information is stored in the Google index, a huge database that is stored on many, many (many!) computers.

Serving search results: When a user performs a Google search, Google tries to determine the highest quality results. The "best" results have many factors, including things such as the user's location, language, device (desktop or phone), and previous queries. For example, searching for "bicycle repair shops" would show different answers to a user in Paris than it would to a user in Hong Kong. Google doesn't accept payment to rank pages higher, and ranking is done algorithmically.

Compilers

a compiler is a computer program that translates computer code written in one programming language into another language. The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a lower level language to create an executable program

Multi Core

a single physical processor incorporates the core logic of more than one processor. Processor can run instructions on separate cores at same time. This increases overall speed of program execution in system. Thus heat generated by processor gets reduced and increases overall speed of execution.

Multicore systems support MultiThreading and Parallel Computing

Networks

A network consists of two or more computers that are linked in order to share resources

Map Reduce

used for generating big data sets with a parallel, distributed algorithm on a cluster. A MapReduce program is composed of a map procedure, which performs filtering and sorting, and a reduce method, which performs a summary operation.

concurrency vs parallelism

concurrency is about composing independent processes (in the general meaning of the term process) to work together, while parallelism is about actually executing multiple processes simultaneously.

kernel

The kernel is a computer program at the core of a computer's operating system that has complete control over everything in the system. It is the "portion of the operating system code that is always resident in memory", and facilitates interactions between hardware and software components

coroutine/ fibers

Coroutines (fibers) are very similar to threads. However, coroutines are cooperatively multitasked, whereas threads are typically preemptively multitasked. They work within threads, and are great for handling asynchronousity like network calls

Cooperative multitasking

a technique in which different pieces of software give up their immediate control of the processing unit of a computer so that another software can use it. The programs voluntarily give up their control as this allows other programs to use the processor of the computer

preemptive multitasking

an OS uses some criteria to decide how long to allocate to any one task before giving another task a turn to use the CPU

Performance Tests

testing practice performed to determine how a system performs in terms of responsiveness and stability under a particular workload

64-bit checksum

a value used to verify the integrity of a file or a data transfer. In other words, it is a sum that checks the validity of data. Checksums are typically used to compare two sets of data to make sure they are the same. ... For example, a basic checksum may simply be the number of bytes in a file

trade offs:

range based partitioning

vertical partitioning

hash based partitioning

range based partitioning - Range partitioning maps data to partitions based on ranges of values of the partitioning key that you establish for each partition. But it can lead to uneven distribution and higher latency for hot data

hash based partitioning - Partition based on a hash of the data. It distributes data evenly but data will need to be queried from each of the servers in the distributed system

Tradeoff: How does the load balancer choose the backend server

1. Least Connection Method — This method directs traffic to the server with the fewest active connections. This approach is quite useful when there are a large number of persistent client connections which are unevenly distributed between the servers.

2. Least Response Time Method — This algorithm directs traffic to the server with the fewest active connections and the lowest average response time.

3. Least Bandwidth Method - This method selects the server that is currently serving the least amount of traffic measured in megabits per second (Mbps).

tradeoffs long polling, polling, server sent events, websockets

Long Polling: a variation of the traditional polling technique that allows the server to push information to a client whenever the data is available

Polling:the client repeatedly polls (or requests) a server for data. The client makes a request and waits for the server to respond with data. If no data is available, an empty response is returned.

Server Sent Events: Under SSEs the client establishes a persistent and long-term connection with the server. The server uses this connection to send data to a client. The connection isn't closed after each response

Websockets: It provides a persistent connection between a client and a server that both parties can use to start sending data at any time.

Tradeoffs Databases

relational database - supports joins and is acid compliant

Dynamo - key value store

MongoDB - document

Cassandra,- wide columnar

InfiniteGraph - graph

HBase - wide-columnar, groups data together to store new data in a memory buffer and, once the buffer is full, it dumps the data to the disk

Bigtable-multiple files into one block to store on the disk and is very efficient in reading a small amount of data. (good for storing things like thumbnails)

tradeoffs: cache invalidation

Write-through cache: Under this scheme, data is written into the cache and the corresponding database at the same time. The cached data allows for fast retrieval and, since the same data gets written in the permanent storage, we will have complete data consistency between the cache and the storage. Also, this scheme ensures that nothing will get lost in case of a crash, power failure, or other system disruptions.

Although, write through minimizes the risk of data loss, since every write operation must be done twice before returning success to the client, this scheme has the disadvantage of higher latency for write operations.

Write-around cache: This technique is similar to write through cache, but data is written directly to permanent storage, bypassing the cache. This can reduce the cache being flooded with write operations that will not subsequently be re-read, but has the disadvantage that a read request for recently written data will create a "cache miss" and must be read from slower back-end storage and experience higher latency.

Write-back cache: Under this scheme, data is written to cache alone and completion is immediately confirmed to the client. The write to the permanent storage is done after specified intervals or under certain conditions. This results in low latency and high throughput for write-intensive applications, however, this speed comes with the risk of data loss in case of a crash or other adverse event because the only copy of the written data is in the cache.

Cache eviction policies

tradeoffs: cache eviction

First In First Out (FIFO): The cache evicts the first block accessed first without any regard to how often or how many times it was accessed before

Least Recently Used (LRU): Discards the least recently used items first.

Least Frequently Used (LFU): Counts how often an item is needed. Those that are used least often are discarded first.